Gram-Schmidt正交化算法的计算复杂度是多少？
假设一个m行和k列的矩阵，需要多少次运算才能计算正交化？
如果可能的话，我想知道确切的乘法和加法数。
编辑:
在我看来，操作(乘法+加法)的总数是3/2k^2m + 3/2mk +k^2/2 +k/2。
我想知道这是否正确以及是否有更快的版本。
最佳答案
点积乘m-1加m乘。
向量归一化需要1个向量平方(点积)，1个平方根和m个分割，即
m-1 +, m *, m /, 1 √
向量投影的减法需要1个点积，m个乘积和m个加法，即
2m-1 +, 2m *
第j个向量的计算需要减去(j-1)个投影，然后进行归一化处理，即
(2m-1)(j-1)+m-1 +, 2m(j-1)+m *, m /, 1 √
您可以计算从j = 1到k的向量，因此因数(j-1)变为三角数(k-1)k/2，并且独立于j的项乘以k:
(2m-1)(k-1)k/2+(m-1)k +, 2m(k-1)k/2+mk *, mk /, k √
在点积中，可以将m个除数乘以m乘以逆，得出
(2m-1)(k-1)k/2+(m-1)k +, 2m(k-1)k/2+2mk *, k /, k √
因此基本上是2mk²的操作。