在什么情况下,两个(几乎)相同的稀疏矩阵可以对 Mx = b 给出不同的解?

计算科学 线性代数 matlab 有限差分 线性求解器 精确
2021-12-07 12:04:44

假设我有两个稀疏矩阵,AB, 大小N×N. 它们每个都具有相同的稀疏模式(“足迹”)。它们每个都有理论上应该相同的值,但不是由于机器精度误差。

MATLAB 语法中的一个简单示例:

% Dimensions of square, sparse matrices
N = 10;
A = sparse(N,N);
B = sparse(N,N);

% Add a dozen nonzero entries at random locations
numEntries = 12;
rows = randi( N, numEntries,1 );
cols = randi( N, numEntries,1 );

% Populate the entries, one at a time
for entry = 1:numEntries
    i = rows(entry);
    j = cols(entry);

    % Generate random numbers
    x = rand(1,1);
    y = rand(1,1);

    % Populate matrices
    % Note: (x^2-y^2) / (x-y) == (x+y)*(x-y)/(x-y) == x+y
    A(i,j) = (x^2-y^2) / (x-y);
    B(i,j) = x + y;

end

diffMat = A - B;
disp(diffMat);

显然的价值观AB 应该是相同的,但它们不是。该脚本的输出如下:

   1.0e-15 *

   (1,2)     -0.222044604925031
   (2,2)      0.222044604925031
  (10,3)      0.111022302462516
   (8,4)     -0.222044604925031
   (3,5)      0.222044604925031
  (10,5)      0.555111512312578
   (3,6)      0.222044604925031

假设一对这样的矩阵给出截然不同的结果xAxB对于矩阵方程AxA=bBxB=b(相同的b在每种情况下)。假设我已经确认AB与 1e15 中的不到一个部分相同(即abs( (A(A~=0)-B(B~=0)) ./ A(A~=0) ) < 1e-15)。进一步假设condest()每个矩阵的估计条件数 ( ) 相同。

我的问题:在什么情况下会发生这种情况?

免责声明

我最初问这个问题是因为我的代码中有这个问题。原来我的b由于生成它们的代码中有一个小错字,向量并不相同(感谢@JesseChan!)。

我仍然对这是否以及如何发生感兴趣。我的猜测是非常高的条件数可以产生这种结果,但我很好奇是否有人可以产生并解释这种行为的最小工作示例。

2个回答

这不可能发生,除非矩阵表现得很糟糕。如果你有两个非奇异矩阵A,B

AB=O(ϵ),
那么求解的相对误差Ax=b
A1bB1bA1bsupxA1xB1xA1xsupyyB1AyyIB1AB1(BA)B1ABκ(B)BAB

因此,如果内相同,并且如您所说,也具有相同的条件数,那么相对误差最多可以是ABϵκ(A)=κ(B)κ(A)ϵ/A.

特别是,对于的条件数必须在量级。O(1)AAϵ1

很高兴答案在向量中。原始方程的答案取决于您用来求解系统的方法(反斜杠内置了大量不同的选项)。您通常认为解决方案中的相对差异是,其中是矩阵之间的差异,而的条件数。一种更简单的思考方式是,调节的数量级大致说明了您可以预期多少位数的差异(对于求解系统的稳定方法)。bO(κϵ)ϵκA,B