改进已知零元素时的朴素高斯消除

Question

我写了朴素高斯消除而不旋转：

function [x] = NaiveGaussianElimination(A, b)
    N = length(b);
    x = zeros(N,1);
    mulDivOp = 0;
    subAddOp = 0;
    for column=1:(N-1)
        for row = (column+1):N
            mul = A(row,column)/A(column,column);
            A(row,:) = A(row,:)-mul*A(column,:);
            b(row) = b(row)-mul*b(column);
            mulDivOp = mulDivOp+N-column+2; 
            subAddOp = subAddOp +N-column+1;
        end
    end
    for row=N:-1:1
        x(row) = b(row);
        for i=(row+1):N
            x(row) = x(row)-A(row,i)*x(i);
        end
        x(row) = x(row)/A(row,row);
        mulDivOp = mulDivOp + N-row + 1;
        subAddOp = subAddOp + N-row;
    end
    x = x';
    mulDivOp
    subAddOp
    return
end

但我很好奇，如果我知道矩阵的哪些元素为 0，我是否可以减少乘法/除法和加法/减法的数量：

当 N = 10 时：

A =
    96   118     0     0     0     0     0     0     0    63
   154   -31  -258     0     0     0     0     0     0     0
     0  -168   257  -216     0     0     0     0     0     0
     0     0   202    24   308     0     0     0     0     0
     0     0     0  -262   -36  -244     0     0     0     0
     0     0     0     0   287  -308   171     0     0     0
     0     0     0     0     0   197   229  -258     0     0
     0     0     0     0     0     0   -62  -149   186     0
     0     0     0     0     0     0     0   -43   255  -198
  -147     0     0     0     0     0     0     0  -147  -220

（非零值来自兰迪）。一般来说，当abs（i-j） <= 1时，非零元素是a_{1， N}， a_{N，1} 和 a_{i，j}。

Answer 1

可能不是。有一些很好的算法可以将三对角矩阵（这些不是，但它们很接近）减少到对角矩阵。事实上，这是产生矩阵SVD的一种方式，使用正交相似性变换，而不是高斯消除。

问题是，当您使用高斯消除来删除第一列中的非零条目时，您将在其他列中引入额外的非零条目。你走得越远，你破坏矩阵的结构就越多。对于您尝试解决的问题，高斯消除可能只是错误的方法，至少如果您试图利用矩阵的结构。