一般来说，所有 Krylov 方法本质上都是在矩阵的谱上求值时寻找一个小的多项式。特别是，$n$Krylov 方法的残差（初始猜测为零）可以写成以下形式

$$r_n = P_n (A) b$$

在哪里$P_n$是一些次数的单项多项式$n$.

如果$A$是可对角化的，有$A=V\Lambda V^{-1}$， 我们有

$$\begin{eqnarray*} \|r_n\| &\leq& \|V\|\cdot \|P_n(\Lambda)\|\cdot \|V^{-1}\|\cdot \|b\|\\ &=& \kappa(V) \cdot \|P_n(\Lambda)\| \cdot \|b\|. \end{eqnarray*}$$

在这种情况下$A$是正常的（例如，对称的或单一的）我们知道$\kappa(V) = 1.$GMRES 通过 Arnoldi 迭代构造这样的多项式，而 CG 使用不同的内积构造多项式（有关详细信息，请参阅此答案）。类似地，BiCG 通过非对称 Lanczos 过程构造其多项式，而 Chebyshev 迭代使用关于谱的先验信息（通常是对称定矩阵的最大和最小特征值的估计）。

作为一个很酷的例子（由 Trefethen + Bau 提出），考虑一个矩阵，其谱如下：

在 MATLAB 中，我使用以下方法构造了它：

A = rand(200,200);
[Q R] = qr(A);
A = (1/2)*Q + eye(200,200);

如果我们考虑 GMRES，它构造的多项式实际上最小化了所有单项多项式的残差$n$，我们可以通过查看候选多项式轻松预测残差历史

$$P_n (z) = (1-z)^n$$

在我们的例子中给出

$$|P_n(z)| = \frac{1}{2^n}$$

为了$z$在频谱范围内$A$.

现在，如果我们在随机 RHS 上运行 GMRES 并将残差历史与该多项式进行比较，它们应该非常相似（候选多项式值小于 GMRES 残差，因为$\|b\|_2 > 1$):

关于规范

作为 Reid.Atcheson 回答的附录，我想澄清一些有关规范的问题。在$n^{\mathrm{th}}$迭代，GMRES 找到多项式$P_n$最小化$2$- 残差范数

$$r_n = A x_n - b = \big(P_n(A) - 1 \big)b - b = P_n(A) b .$$

认为$A$是 SPD，所以$A$产生一个规范，所以$A^{-1}$. 然后

$$\begin{align*} \lVert r_n \rVert_{A^{-1}} &= r_n^T A^{-1} r_n \\ &= (A e_n)^T A^{-1} A e_n \\ &= e_n^T A e_n \\ &= \lVert e_n \rVert_{A} \end{align*}$$

我们在哪里使用了错误

$$e_n = x_n - x_* = x_n - A^{-1} b = A^{-1} r_n$$

就这样$A$-范数的错误等同于$A^{-1}$残差的范数。共轭梯度最小化$A$- 误差范数，使其在解析低能量模式时相对更准确。这$2$-GMRES 最小化的残差范数就像$A^T A$- 误差范数，因此在低能量模式分辨率较差的意义上较弱。请注意，$A$残差的范数本质上是毫无价值的，因为它在低能量模式下甚至更弱。

收敛界限的锐度

最后，有一些关于不同 Krylov 方法和 GMRES 收敛的微妙之处的有趣文献，特别是对于非正态算子。

• Nachtigal、Reddy 和 Trefethen (1992) 非对称矩阵迭代有多快？ （作者的 pdf）给出了矩阵的示例，其中一种方法以一个很大的因素（至少是矩阵大小的平方根）击败所有其他方法。

• Embree (1999) GMRES 收敛界限的描述性如何？给出了关于伪谱的有见地的讨论，它给出了更清晰的界限，也适用于不可对角化的矩阵。

• Embree (2003) 龟兔赛跑 GMRES (作者 pdf)

• Greenbaum、Pták 和 Strakoš (1996) 对于 GMRES，任何非递增收敛曲线都是可能的

迭代方法简而言之：

1. 平稳方法本质上是定点迭代：解决$Ax=b$，你选择一个可逆矩阵$C$并找到一个固定点

   $$x = x + Cb- CAx$$ 这由巴拿赫不动点定理收敛，如果$\|I-CA\|<1$. 然后，各种方法对应于特定的选择$C$（例如，对于 Jacobi 迭代，$C=D^{-1}$， 在哪里$D$是一个对角矩阵，包含对角元素$A$）。

2. Krylov 方法子空间方法本质上是投影方法：你选择子空间$U,V\subset \mathbb{C}^n$并寻找一个$\tilde x \in U$这样残差$b-A\tilde x$正交于$V$. 对于 Krylov 方法，$U$当然是权力所跨越的空间$A$应用于初始残差。然后，各种方法对应于特定的选择$V$（例如，$V=U$对于 CG 和$V=AU$GMRES）。

   这些方法（以及一般的投影方法）的收敛特性源于以下事实：由于各自选择$V$， 这$\tilde x$是最优的$U$（例如，它们使 CG 的能量范数或 GMRES 的残差最小化）。如果增加维度$U$在每次迭代中，您都可以保证（以精确的算术方式）在有限多步之后找到解决方案。

   正如 Reid Atcheson 所指出的，使用 Krylov 空间$U$允许您根据特征值（以及条件数）证明收敛速度$A$. 此外，它们对于推导计算投影的有效算法至关重要$\tilde x$.

   Youcef Saad 的迭代方法一书中很好地解释了这一点。