algorithm - Gram-Schmidt正交化算法的计算复杂度

Question

Gram-Schmidt 正交化算法的计算复杂度是多少？

假设一个m 行和k 列的矩阵，计算正交化需要多少次操作？

如果可能的话，我想要乘法和加法的确切数量。

编辑:在我看来，操作总数(乘法 + 加法)是 3/2k^2m + 3/2mk +k^2/2 +k/2。
我想知道这是否正确以及是否有更快的版本。

Answer 1

点积需要 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² 操作。