Don*_*beo 6 algorithm complexity-theory time-complexity
Gram-Schmidt正交化算法的计算复杂度是多少？
假设m行和k列矩阵,计算正交化需要多少操作？
如果可能的话,我希望得到确切的乘法和加法数.
编辑:在我看来,操作的总数(乘法+加法)是3/2k^2m + 3/2mk +k^2/2 +k/2.
我想知道这是否正确,是否有更快的版本.
Dot产品需要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²的操作.