2

我很难理解为什么这个 Matlab 代码在不使用 LU 分解进行旋转的情况下执行高斯消除会(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：我不是在这里谈论算法复杂性。

4

1 回答 1

2

我终于自己弄清楚了。

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

但是，这条线有两个浮点运算：一个-运算和一个*运算。

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

于 2013-10-15T01:13:56.100 回答