迭代方法是否适用于奇异一致线性系统 Ax=b?

计算科学 迭代法
2021-12-19 23:14:26

最近在研究大型稀疏线性系统Ax=b的迭代方法,其中A是非奇异的,所以存在唯一解x并且停止标准通常选择为 norm(b-Ax_k)/norm(b)< tol (may 1e-6)。

但在某些情况下,矩阵A可能是奇异的,例如在求解具有 Neumann 边界条件的 Poisson 方程时。我的问题是,对于那些奇异的线性系统,我们还可以使用迭代方法吗?此外,在那些奇异系统中,右手边brange(A),即b在矩阵A的范围内,使得系统Ax=b是一致的。

Jacobi、SOR、CG、minres 或 gmres 等迭代方法仍可用于计算解决方案吗?但在这种情况下,有无限的解决方案。迭代方法如何计算解决方案?非常感谢。

2个回答

是的,许多迭代方法仍然会收敛,或者至少在它们已经用尽与对应于非零特征值的特征向量的跨度相对应的所有搜索方向时会崩溃。例如,您可以将 CG 用于纯 Neumann 问题。

因为所有这些方法都是确定性的,如果它们收敛,它们将收敛到解决方案集中的特定元素。例如,对于应用于纯 Neumann 问题的 CG 方法,我怀疑可以证明解向量的元素的平均值等于初始猜测的元素的平均值,因为人们只会将向量添加到平均值为零的迭代。换句话说,你最后得到的向量将是无限多个中的一个特定解;当然,它是否是您想要的那个是另一个问题。

使用 Krylov 求解器求解时Ax=b系统,奇点A只要是良性的b是一致的。考虑将共轭梯度 (CG) 算法应用于对称正半定A(单数,但所有非零特征值仍然为正)。进一步假设b是在范围内A,我们选择初始猜测为x=0. 然后,搜索向量/残差r=bAx将始终与零空间正交A(因为在 CG 中,搜索向量/残差总是通过应用来绘制A到以前的残差,这个乘以A不能在零空间中生成任何组件)。该算法永远无法“感知”A,并将收敛到(唯一!)x这样Ax=bxnull(A)

matlab 中的一个简短演示:

clear all
close all

% Form positive semidefinite A.
N = 10;
[Q,~] = qr(rand(N));
D1 = linspace(1,N/2,N/2);
D2 = zeros(1,N/2);
D = diag([D1 D2]); 
A = Q*D*Q';
kappa = cond(A) % infinite/singular

% Form random b in range(A).
b = A * rand(N,1);

% Solve A*x=b using CG.
x = pcg(A,b);

% Check properties.
residual = norm(A*x-b)
nullity = norm(x'*null(A))

可以为其他 Krylov 求解器提出类似的论点,但我不能真正与“经典”迭代求解器(Gauss-Seidel 等)交谈。我怀疑它们是否表现良好。

有完全基于这个想法的预处理策略(通货紧缩):找到特征向量的基础A对求解器有某种问题,然后将它们“放气”/投影出来(更改运算符,使相应的特征值映射为零),然后将相同的投影应用于b, 并迭代。有关通货紧缩预处理(涉及奇异系统的收敛性分析)的更多信息,我建议:

唐,JM,等。“基于多重网格和通缩的两级预处理器的比较。”

Erlangga、Yogi A. 和 Reinhard Nabben。“适用于非对称矩阵的 Krylov 子空间方法的通缩和平衡预调节器。”