计算科学 - 对于这个不可对角化的矩阵，gmres 方法迭代的行为如何？ - 吾爱随笔录

对于这个不可对角化的矩阵，gmres 方法迭代的行为如何？

计算科学 matlab 特征值收敛格瑞斯

2021-12-24 20:50:25

最近，我学习了关于gmres迭代的课程，这可能是一般大型稀疏线性方程组Ax=b最流行的迭代方法。并且收敛是在矩阵A可对角化的条件下获得的，但在实际应用中，很少有这样好的可对角化矩阵A出现这种情况。那么， GMRES迭代还有其他收敛结果吗？或者换句话说，当我们选择一个预处理器M来求解我们应该考虑哪些方面来保证这个预处理的 GMRES更好的收敛性？因为

M^{- 1} A x = M^{- 1} b,

$M^{-1}Ax=M^{-1}b,$

M^{- 1} A

$M^{-1}A$ 在一般情况下不能对角化，是否足以对的光谱分布进行聚类？的哪些方面？

M^{- 1} A

$M^{-1}A$

M^{- 1} A

$M^{-1}A$

一个奇怪的例子如下：用，我们设置使用 matlab 命令gmres解决此系统。我们将此结果与 matlab A\b进行比较，但 gmres 失败（我的 CPU 内存为 8GB），A\b

A = (\begin{array}{cccccc} 1 & c_{1} \\ 0 & 1 & c_{2} \\ ⋱ & ⋱ \\ 1 & c_{n - 2} \\ 1 & c_{n - 1} \\ 1 \end{array}) \in R^{n \times n},

$A=\left(\begin{array}{cccccc}{1} & {c_{1}} & {} & {} & {} & {} \\ {0} & {1} & {c_{2}} & {} & {} & {} \\ {} & {} & {\ddots} & {\ddots} & {} & {} \\ {} & {} & {} & {1} & {c_{n-2}} & {} \\ {} & {} & {} & {} & {1} & {c_{n-1}} \\ {} & {} & {} & {} & {} & {1}\end{array}\right)\in\mathbb{R}^{n\times n},$

c_{i} \neq 0

$c_i\neq 0$

b = A * [1, 1, . . ., 1]^{T}

$b=A*[1, 1,...,1]^T$

A x = b

$Ax=b$ 反而成功了。我只是不明白为什么会这样，因为我们常说对于大型稀疏矩阵，直接方法可以被迭代方法击败。你能给我一些关于 gmres 收敛的建议和对上面例子Ax=b的一些解释，因为矩阵A的所有特征值都是单位，理论上 gmres 会很快收敛。非常感谢。

下面是我的简单测试matlab代码

%   just a simple test
clc;clear;
rng(0)% fix the random number
n=1e+5;
c = rand(n,1);% c_i
A = spdiags([ones(n,1)  c],[0 1],n,n);
b = A*ones(n,1);
%   mdirect method
A\b;
%   iterative method
x=gmres(A,b,[],[],n);

4个回答

不幸的是，GMRES 的收敛对特征值的分布没有明确的依赖性。

Greenbaum、Ptak 和 Strakos 在 1996 年证明，您可以构建具有任意谱和任意收敛历史的示例：即，给我任意非零复数和任意递减序列，我可以用该谱和向量，以便在每一步都达到这些残差范数。基本上你听说的关于频谱和 GMRES 收敛之间关系的一切都可能会失败。 $n$ $\|r_k\|$ $A$ $b$ gmres(A, b)

这里有更多参考资料 http://www.cs.cas.cz/duintjertebbens/Talks/Liblice12.pdf。

基于特征值分布的 GMRES 收敛估计通常隐含地假设矩阵是正态的。有时，在非正态情况下，收敛速度在渐近意义上仍然是可证明的，但如果矩阵严重非正态，那么“前渐近”行为将使这种收敛速度在实践中永远无法达到。

您的矩阵不正常，并且随着大小的增长，它的非正态性会变得更糟。

好吧，我只能提出一个潜在的原因来解释为什么 GMRES 方法对于你所展示的问题失败了。我没有足够的声誉，所以我无法评论。

由于 GMRES 使用 Anorldi 过程在 Krylov 子空间中生成一组正交向量，如果矩阵本身非常大，则意味着生成的 Q 和 H 矩阵可能非常大。所以如果你要解决一个非常大的问题，你需要使用limited-GMRES（或者limited-memory GMRES，具体名字记不清了）。但关键是求解器会重置正交矩阵并重新启动整个过程来处理内存限制。这可能是您的 GMRES 失败的原因。检查 MatLab 命令中是否存在有限选项。

A\b 立即起作用，因为这是一个非常稀疏且对角线的系统，非常适合向后消除。

希望这可以帮助。干杯!

首先是关于为什么这样的矩阵对求解器来说很难的一些评论。请注意，如果是上对角线 $U$

[[. 2 . . .]
 [. . 2 . .]
 [. . . 2 .]
 [. . . . 2]
 [. . . . .]]

然后。对于这个例子， $(I - U)^{-1} = I + U + U^2 + ... U^{n-1} \ (U^n = 0)$ $(I - U)^{-1} =$

[[ 1  2  4  8 16]
 [ .  1  2  4  8]
 [ .  .  1  2  4]
 [ .  .  .  1  2]
 [ .  .  .  .  1]]

有角。巨大的条目会给任何求解器带来麻烦——浮点上溢或下溢，或者极端病态。使用 random-Cauchy 而不是 random-normal（放大问题），的奇异值是 $2^{blksize - 1}$ $U$ $I - U \ \ 300 \times 300$

[6.7e-18 1.2e-06 2.1e-05 0.0025 0.0026 0.005 0.0063 0.0068 0.0083 0.011 ... 18 22 22 25 30 32 35 37 45 610]

并且伪逆不是三角形的。（这是用 python numpy 和 scipy，我没有 Matlab。）

Krylov 方法是否适用于无法对角化的矩阵，例如特征值全为？求解线性方程组的 krylov 子空间收敛方法的原理是什么？，清楚地说“如果 A 是可对角化的……”。但如果不是，如何找到一个多项式，其中？不知道——交给专家。 $I - U$ $p(A) \, b \approx A^{-1} \, b$

另见 Trefethen 等人的许多论文。以及 Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and Operators 2005，606 页。

其它你可能感兴趣的问题

上一篇不基于主/从概念的并行计算编程范式/模型？下一篇如何“平滑”（不仅仅是细化）2D/3D 多边形网格