计算科学 - 矩形上的高斯消除/行减少的运行时间米× ñm×n矩阵 - 吾爱随笔录

计算科学线性代数复杂

2021-12-25 02:18:45

高斯消元的运行时间 $n \times n$ 矩阵是 $O(n^3)$ . 什么是运行时 $m \times n$ 矩阵？

我采用高斯消元法表示将矩阵置于简化的行梯形中。（虽然我猜减少的行梯形和仅行梯形之间没有复杂性差异。）

令人惊讶的是，我似乎无法在网上的任何地方找到答案。

1个回答

它是 $\Theta(mn\min(m,n))$ ,大乘小平方。

为了得到行梯形，每一步通过操作更新一个所以特别是每一步最多需要次失败，其中至少一半需要至少操作。这两个界限让你得出结论。 $k=0,1,\dots,\min(m,n)-1$ $(m-k)(n-k)$ $O(m-k)(n-k)$ $O(mn)$ $\frac{m}{2}\frac{n}{2}$

对于减少的 REF 的附加步骤，分析是相似的，由于零点，最多可达因子 2。尽管出于稳定性原因，您最好在 REF 处停下来，然后依靠反向替换。

其它你可能感兴趣的问题