Gram-Schmidt正交化算法的计算复杂度 [英] Computational complexity of Gram-Schmidt orthogonalization algorithm

问题描述

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²操作。

这篇关于Gram-Schmidt正交化算法的计算复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！