线性方程组的古典迭代法

线性方程组的迭代法求解主要可以分成两类方法：古典迭代法和 Krylov 子空间方法。古典迭代法的特点是格式简单，收敛性与迭代初值无关，与迭代矩阵的谱半径有关。古典迭代法可以解释为基于矩阵的近似逆设计的不动点迭代法，与此不同的是共轭梯度法为代表的 Krylov 子空间方法，它们可以解释为最优化思想在矩阵求解问题上的实现。

迭代格式与收敛性

为了求解非奇异的线性方程组

Copy LaTeX

可以设计一般的不动点迭代格式

Copy LaTeX

最终希望收敛到 $Ax=b$ 的精确解 $x$ （在向量范数意义下）

Copy LaTeX

此时 $x$ 满足如下等式

Copy LaTeX

因此迭代格式必须要满足如下相容性条件

Copy LaTeX

分析易知，迭代格式收敛与迭代初值无关，收敛的充要条件仅与 $B$ 的谱半径有关：

Copy LaTeX

收敛的充分条件有很多，例如 $B$ 的某个矩阵范数小于 1 即可。收敛的效率也直接取决于 $B$ 的谱半径： $\rho(B)$ 越接近 0 则收敛越快。

为了下文的需要，基于方阵 $A$ 定义几个矩阵：

$D$ 为 $A$ 的对角线部分组成的对角阵
$L$ 为 $-A$ 的下三角部分组成的下三角矩阵，对角线全零
$U$ 为 $-A$ 的上三角部分组成的上三角矩阵，对角线全零

满足

Copy LaTeX

Remark

有的资料中使用的记号为 $A = D + L + U$ 。

Richardson 迭代法

Richardson 迭代法的格式非常简单，将方程等价变形为

Copy LaTeX

其中松弛因子 $w > 0$ 。直接利用方程的残差进行修正

Copy LaTeX

Jacobi 迭代法

将线性方程组整理为如下形式：

Copy LaTeX

定义

Copy LaTeX

就可以得到 Jacobi 迭代

Copy LaTeX

G-S 迭代法

作为 Jacobi 迭代的改进，假设每一次更新从上到下进行，那么更新后面的元素时可以直接利用新算出来的值，得到 G-S 迭代法。此时 $x$ 每个分量的更新顺序必须是从上往下的，不可以改变。

Copy LaTeX

或者整理成统一的形式

Copy LaTeX

当然在编程中不应采用这种形式，因为无法实际算出 $(D-L)^{-1}$ ，这种形式只适用于理论分析。

SOR 迭代法

超松弛迭代法可以视作 G-S 迭代法的推广或加速：引入松弛因子 $w > 1$ ，极限情况 $w=1$ 退化为 G-S 迭代法。

Copy LaTeX

推导一下迭代格式

Copy LaTeX

其中迭代矩阵

Copy LaTeX

可以证明 SOR 迭代法收敛的必要条件

Copy LaTeX

因此通常取参数 $w\in(1,2)$ ，对于具体问题，存在最优的 $w$ 使得收敛速度最快，称为最佳松弛因子。

近似逆

古典迭代法实质是取了 $A$ 的一个可计算的近似逆 $M$ ，这里称 $M$ 为 $A$ 的近似（左）逆，含义为

Copy LaTeX

即 $MA$ 在矩阵范数意义下（或谱半径意义下）近似为单位阵 $I$ 。那么

Copy LaTeX

由此诱导出迭代格式

Copy LaTeX

这里的 $I-MA$ 即前文中的迭代矩阵 $B$ ，因此收敛性充要条件为

Copy LaTeX

含义为：当可计算的 $M$ 可以作为 $A$ 的一个近似逆时，对应的迭代格式收敛； $M$ 越接近 $A^{-1}$ ，收敛速度越快。

使用近似逆可以统一解释前文中的几种迭代法：

Richardson 迭代法：取 $w I$ 近似 $A^{-1}$
Jacobi 迭代法：取对角阵的逆 $D^{-1}$ 近似 $A^{-1}$
G-S 迭代法：取对角线和下三角部分之和的逆 $(D-L)^{-1}$ 近似 $A^{-1}$
SOR 迭代法: 取 $w(D-wL)^{-1}$ 近似 $A^{-1}$

Remark

近似逆的概念也可以进一步推广为预条件方法。