Gram-Schmidt正交化算法的计算复杂度
Computational complexity of Gram-Schmidt orthogonalization algorithm
Gram-Schmidt 正交化算法的计算复杂度是多少？
假设一个 m 行和 k 列的矩阵，计算正交化需要多少次操作？
如果可能的话我想知道乘法和加法的确切数目。
编辑：
在我看来，操作总数（乘法+加法）是3/2k^2m + 3/2mk +k^2/2 +k/2.
我想知道这是否正确，是否有更快的版本。
Gram-Schmidt算法的整体复杂度为O(m.k^2):
该过程必须应用 k 次，并且每次正交化都需要 O(m.k) 次运算（乘法和加法），因此总共使 O(m.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 正交化算法的计算复杂度是多少？
假设一个 m 行和 k 列的矩阵，计算正交化需要多少次操作？
如果可能的话我想知道乘法和加法的确切数目。
编辑：
在我看来，操作总数（乘法+加法）是3/2k^2m + 3/2mk +k^2/2 +k/2.
我想知道这是否正确，是否有更快的版本。
Gram-Schmidt算法的整体复杂度为O(m.k^2):
该过程必须应用 k 次，并且每次正交化都需要 O(m.k) 次运算（乘法和加法），因此总共使 O(m.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² 操作。