数值代数中的迭代法加速技术
好的，我们开始讲解“数值代数中的迭代法加速技术”。这是一个计算数学中极其重要的主题，旨在提升基本迭代法（如雅可比法、高斯-赛德尔法）求解大型线性方程组 \(A\mathbf{x} = \mathbf{b}\) 的效率。我们循序渐进地展开。
第一步：回顾基础——基本迭代法及其瓶颈
首先，你需要理解基本迭代法的核心思想。对于一个线性方程组 \(A\mathbf{x} = \mathbf{b}\)，我们将系数矩阵 \(A\) 分解为 \(A = M - N\)，其中 \(M\) 是一个容易求逆的矩阵（称为分裂矩阵）。
- 迭代格式： 基本的迭代格式为：
\[ M\mathbf{x}^{(k+1)} = N\mathbf{x}^{(k)} + \mathbf{b} \quad \text{或} \quad \mathbf{x}^{(k+1)} = M^{-1}(N\mathbf{x}^{(k)} + \mathbf{b}) \]
这等价于：
\[ \mathbf{x}^{(k+1)} = \mathbf{x}^{(k)} + M^{-1}(\mathbf{b} - A\mathbf{x}^{(k)}) \]
这个形式揭示了迭代的本质：每一步都是在当前解 \(\mathbf{x}^{(k)}\) 上加上一个基于当前残差 \(\mathbf{r}^{(k)} = \mathbf{b} - A\mathbf{x}^{(k)}\) 的修正项 \(M^{-1}\mathbf{r}^{(k)}\)。
-
收敛性与速度： 记迭代矩阵 \(G = M^{-1}N\)。迭代收敛的充要条件是 \(G\) 的谱半径 \(\rho(G) < 1\)。收敛速度由谱半径 \(\rho(G)\) 决定：\(\rho(G)\) 越接近于 0，收敛越快；越接近于 1，收敛越慢。
-
瓶颈： 对于许多实际问题（例如来自椭圆型偏微分方程离散化），矩阵 \(A\) 的条件数很大，或具有特定性质（如强对角占优但不那么强），导致基本迭代法（如雅可比、高斯-赛德尔）的 \(\rho(G)\) 非常接近 1。这意味着每次迭代对误差的衰减非常微小，需要成千上万次迭代才能达到可接受的精度，计算成本极高。
核心问题： 如何对这样一个收敛缓慢的基本迭代过程进行“加速”，使其用少得多的迭代步数达到收敛？
第二步：核心加速思想——外推与多项式加速
迭代法加速技术的核心源于一个深刻的观察：基本迭代过程产生的迭代序列 \(\{ \mathbf{x}^{(k)} \}\) 可以看作是某个线性过程的输出，我们可以对其进行“组合”或“校正”来得到更好的新序列。
- 外推（松弛）思想： 考虑最简单的情况。假设我们从一个猜测 \(\mathbf{x}^{(k)}\) 开始，用基本迭代法（如高斯-赛德尔）计算出一个中间结果 \(\tilde{\mathbf{x}}^{(k+1)}\)。与其直接接受它作为新的迭代值，我们问：能否在从 \(\mathbf{x}^{(k)}\) 到 \(\tilde{\mathbf{x}}^{(k+1)}\) 的这个“方向”上，找一个“更好”的点？
这引出了松弛技术：
\[ \mathbf{x}^{(k+1)} = \omega \tilde{\mathbf{x}}^{(k+1)} + (1-\omega)\mathbf{x}^{(k)} \]
其中 \(\omega\) 是松弛因子。
- 当 \(\omega = 1\) 时，就是原始迭代。
- 当 \(\omega > 1\) 时，称为超松弛，试图走得更远。
- 当 \(\omega < 1\) 时，称为低松弛，用于稳定不收敛的迭代。
- 多项式加速的抽象： 更一般地，我们可以将第 \(k\) 步的误差 \(\mathbf{e}^{(k)} = \mathbf{x}^* - \mathbf{x}^{(k)}\) （其中 \(\mathbf{x}^*\) 是精确解）与迭代矩阵联系起来：\(\mathbf{e}^{(k)} = G^k \mathbf{e}^{(0)}\)。
如果我们不是只取最后一步的迭代值，而是取前面若干步迭代值的一个线性组合来构造新的近似解，即：
\[ \mathbf{y}^{(k)} = \sum_{j=0}^{k} \alpha_j^{(k)} \mathbf{x}^{(j)} \quad \text{且} \quad \sum_{j=0}^{k} \alpha_j^{(k)} = 1 \]
那么新解的误差为：
\[ \mathbf{y}^{(k)} - \mathbf{x}^* = \sum_{j=0}^{k} \alpha_j^{(k)} (\mathbf{x}^{(j)} - \mathbf{x}^*) = \left( \sum_{j=0}^{k} \alpha_j^{(k)} G^j \right) \mathbf{e}^{(0)} = P_k(G) \mathbf{e}^{(0)} \]
这里 \(P_k(t) = \sum_{j=0}^{k} \alpha_j^{(k)} t^j\) 是一个满足 \(P_k(1) = 1\) 的 \(k\) 次多项式。
加速的目标就转化为：如何选择多项式 \(P_k\) （即选择组合系数 \(\alpha_j^{(k)}\)），使得新的迭代矩阵（现在是 \(P_k(G)\)）的谱半径 \(\rho(P_k(G))\) 远小于 \(\rho(G)\)，从而误差衰减更快。本质上，我们希望 \(P_k(t)\) 在 \(t\) 接近 \(\rho(G)\) 的区域（即 \(G\) 的特征值分布区域）尽可能地小，同时满足 \(P_k(1)=1\)。
第三步：具体技术（一）——逐次超松弛法
逐次超松弛法是多项式加速思想最经典、最直接的应用，它将松弛技术系统地应用于高斯-赛德尔迭代。
- 公式： 对于方程组 \(A\mathbf{x} = \mathbf{b}\)，SOR方法将高斯-赛德尔迭代与松弛结合：
\[ x_i^{(k+1)} = x_i^{(k)} + \frac{\omega}{a_{ii}} \left( b_i - \sum_{j=1}^{i-1} a_{ij}x_j^{(k+1)} - \sum_{j=i}^{n} a_{ij}x_j^{(k)} \right), \quad i=1,\ldots,n \]
- 关键： 存在一个最优松弛因子 \(\omega_{opt}\)，它能使SOR方法的收敛速度达到最快。对于一大类重要问题（如具有性质-A的矩阵，来自矩形网格上拉普拉斯方程五点差分格式的矩阵），\(\omega_{opt}\) 可以通过理论公式计算：
\[ \omega_{opt} = \frac{2}{1 + \sqrt{1 - [\rho(G_J)]^2}} \]
其中 \(\rho(G_J)\) 是雅可比迭代矩阵的谱半径。当 \(\omega = \omega_{opt}\) 时，SOR的收敛速度比高斯-赛德尔法快一个数量级。
- 作用： SOR法通过引入一个可调参数 \(\omega\)，将固定方向的迭代修正进行了“拉伸”或“收缩”，使得修正方向更接近误差的真实下降方向，从而显著加快了收敛。它是许多更复杂加速技术的先驱和基础。
第四步：具体技术（二）——Chebyshev半迭代法
当迭代矩阵 \(G\) 的特征值是实数且分布在一个已知区间 \([\alpha, \beta] \subset (-1, 1)\) 内时，我们可以采用一种更强大的多项式加速技术。
-
思想： 我们不再每一步都进行松弛，而是在进行若干步（比如 \(m\) 步）基本迭代（如雅可比法）后，将这些中间结果通过一个最优的线性组合起来，得到一个新的、更精确的近似解。然后以此为新起点，重复这个过程。
-
最优多项式： 这个“最优组合”对应的多项式 \(P_m(t)\)，是在所有满足 \(P_m(1)=1\) 的 \(m\) 次多项式中，在区间 \([\alpha, \beta]\) 上最大绝对值最小的那个。这个多项式就是缩放平移后的 Chebyshev 多项式。
-
递推实现： 实际操作中，不需要显式存储所有中间迭代值。利用Chebyshev多项式的三项递推关系，可以构造出一个等价的、只依赖前两步结果的迭代格式：
\[ \mathbf{x}^{(k+1)} = \rho_k ( \gamma ( \mathbf{b} - A\mathbf{x}^{(k)} ) + \mathbf{x}^{(k)} ) + (1 - \rho_k) \mathbf{x}^{(k-1)} \]
其中参数 \(\gamma, \rho_k\) 由特征值边界 \(\alpha, \beta\) 计算得到。这实现了隐式的多项式加速。
- 优势与局限： Chebyshev半迭代法可以显著加速收敛，且不需要估计特征向量。但它的主要局限是需要预先知道（或准确估计）迭代矩阵特征值的上下界 \(\alpha, \beta\)，并且要求特征值是实数。
第五步：具体技术（三）——共轭梯度法的视角（Krylov子空间方法的基础）
最强大的一类迭代加速技术是现代Krylov子空间方法（如共轭梯度法CG，广义最小残差法GMRES）。从加速技术的角度看，它们是多项式加速思想的终极发展和智能化体现。
-
Krylov子空间： 在第 \(k\) 步，基本迭代法（如最速下降法）产生的序列张成一个子空间：\(\mathcal{K}_k(A, \mathbf{r}^{(0)}) = \text{span}\{ \mathbf{r}^{(0)}, A\mathbf{r}^{(0)}, \ldots, A^{k-1}\mathbf{r}^{(0)} \}\)，称为Krylov子空间。
-
最优准则： Krylov子空间方法（如CG法）不再使用固定的多项式（如Chebyshev），也不依赖于特征值分布的先验知识。相反，它在第 \(k\) 步，直接在Krylov子空间 \(\mathcal{K}_k\) 中寻找一个近似解 \(\mathbf{x}^{(k)}\)，使得其满足某种最优性条件：
- CG法（对于对称正定矩阵）： 在 \(\mathbf{x}^{(0)} + \mathcal{K}_k\) 中寻找解，使得能量范数误差 \(\| \mathbf{x}^* - \mathbf{x}^{(k)} \|_A\) 最小。
- GMRES法（对于一般矩阵）： 在 \(\mathbf{x}^{(0)} + \mathcal{K}_k\) 中寻找解，使得残差2-范数 \(\| \mathbf{b} - A\mathbf{x}^{(k)} \|_2\) 最小。
-
作为多项式加速： 上述最优解 \(\mathbf{x}^{(k)}\) 可以表示为 \(\mathbf{x}^{(0)}\) 加上一个由 \(A\) 和 \(\mathbf{r}^{(0)}\) 构造的修正项。数学上可以证明，这等价于选择了一个依赖于当前问题数据（矩阵 \(A\) 和初值残差）的最优多项式 \(P_k(A)\) 作用在初始误差上。这个多项式是在运行时动态构造的，它自动适应矩阵的特征值分布。
-
核心优势： Krylov方法将“选择加速多项式”这个任务，转化为一个在逐次扩大的子空间上进行最优化的过程。它不需要特征值范围的先验信息，并且通常能产生比固定多项式（如Chebyshev）更快的收敛速度。因此，现代科学计算中，对于大型稀疏线性方程组，以CG和GMRES为代表的Krylov子空间方法，已经成为了“迭代法加速技术”的代名词和事实上的标准工具。 它们常常与预处理技术（改变矩阵特征值分布，本身也是一种加速思想）结合使用，形成威力无比的求解器。
总结
让我们串联一下这个知识链：
- 起点： 基本迭代法（如雅可比、高斯-赛德尔）简单但收敛慢，因迭代矩阵谱半径接近1。
- 核心思想： 对基本迭代序列进行线性组合（多项式加速），构造新的迭代矩阵 \(P_k(G)\)，使其谱半径更小。
- 经典技术：
- SOR： 通过单个最优松弛因子 \(\omega\)，实现一步多项式加速。
- Chebyshev半迭代： 利用已知特征值边界，使用最优（极小极大）多项式进行多步显式加速。
- 现代技术：
- Krylov子空间方法（如CG， GMRES）： 将多项式加速的思想智能化、最优化。它在线运行时，在逐次扩张的Krylov子空间中求解一个优化问题，从而自动生成（隐式地）当前步骤下“最优”的加速多项式，无需特征值先验知识，收敛速度通常最快。
因此，“数值代数中的迭代法加速技术”是一个从简单参数松弛，到基于特征值分析的系统多项式构造，最终发展到基于子空间最优化的自适应过程的理论与方法体系，它是使迭代法能够应用于大规模科学计算问题的关键。