matlab - 高斯消元法 Matlab 代码中的失败次数

Question

我很难理解为什么这个在不使用 LU 分解进行旋转的情况下执行高斯消除的 Matlab 代码需要 (2/3) * n^3 次失败。 (FLOPs:浮点运算，非 FLOPS:每秒浮点运算)

function x = GaussianElimination(A,b)

n = length(b);
for k = 1:n-1
    for i = k+1:n
        mult = A(i,k)/A(k,k);
        A(i,k+1:n) = A(i,k+1:n)-mult*A(k,k+1:n);
        b(i) = b(i) - mult*b(k);
    end
end

x = zeros(n,1);
x(n) = b(n)/A(n,n);

for k = n-1:-1:1
    x(k) = (b(k) - A(k,k+1:n)*x(k+1:n))/A(k,k);
end

end

如果有人可以向我解释如何计算从 k+1 开始的嵌套循环的失败次数，我将不胜感激。

PS:我在这里不是在谈论算法复杂性。

Answer 1

我终于自己弄清楚了。

FLOP 的计算方式与算法复杂度略有不同，因为低阶项仍然被忽略，但最高阶项前面的系数确实很重要。

在这个具体示例中，由于我们忽略低阶项，因此我们只查看 +, -, *, /三重嵌套循环中的操作并忽略算法其余部分中的其他浮点操作。即以下行

    A(i,k+1:n) = A(i,k+1:n)-mult*A(k,k+1:n);

• 第一个循环从 1 运行到 n
• 第二个循环从 k 运行到 n
• 第三个循环从 k 运行到 n(在 Matlab 代码中隐式使用 : )

因此，这条线几乎运行 n^3时间和精确n*n + (n-1)*(n-1) + ... + 2*2 + 1*1次，相当于 (1/3)*n^3忽略低阶项时会失败。

但是，这一行有两个浮点运算:a -操作和*操作。

因此，这给出 (2/3)*n^3 .