大一线代学的高斯消元法不适合高阶线性方程组。因此发展新的方法——迭代法。

迭代法的基本概念

设方程组 $Ax=f$ 有唯一解 $x^*$。可将方程组变形为：

$x=Bx+f$

由此建立迭代公式：

$x^{(k+1)}=Bx^{(k)}+f \quad (k=0,1,2,...)$

再给定 $x^{(0)}$，即可得到近似解序列 $\{x^{(k)}\}$。

若 $\lim\limits_{k\to\infty}x^{(k)}=x^*$，有 $x^*=Bx^*+f$（$x^*$为不动点），则称迭代法是收敛的，否则是发散的。

$B$ 称为迭代矩阵，$B$ 的取法不同，就是各种迭代法的区别。各种方法是否收敛？速度如何？如何进行误差估计？这就是我们要研究的问题。

迭代法适用于解大型稀疏方程组。

雅可比迭代法

最简单的方法是将每个方程组左边留一个变量，其他全部丢到右边，这就是一个最简单的迭代矩阵。

具体的来说，对于方程组中第 $i$ 个方程，

$\sum_{j=1}^n a_{ij}x_j = b_i \quad (i=1,2,...,n)$

我们把 $a_{ii} x_i$ 留在左边，其他丢到右边，再两边同时除以 $a_{ii}$，得到迭代公式为：

$x_i^{(k+1)} = \frac{1}{a_{ii}} [b_i - \sum_{j = 1}^{i-1}a_{ij}x_j^{(k)} - \sum_{j = i+1}^{n}a_{ij}x_j^{(k)}]$

（迭代公式中后面两项其实可以合并为一个求和符号，但是这里分开写，是为了给后面做铺垫）

初始点任取，进行迭代即可。

不过呢，这玩意不一定收敛。

高斯——赛德尔迭代法

注意到，如果上面如果收敛，一般来说，新值比旧值优秀。
所以我们尽可能使用新的值，把第 $k+1$ 次迭代前面算出来的数用到该次迭代中（迭代表达式中只改了一个上标）：

$x_i^{(k+1)} = \frac{1}{a_{ii}} [b_i - \sum_{j = 1}^{i-1}a_{ij}x_j^{(k+1)} - \sum_{j = i+1}^{n}a_{ij}x_j^{(k)}]$

理论上，如果使用两个方法都收敛，高斯——赛德尔方法会略快于雅可比迭代。

雅可比迭代法的矩阵表示

（这一段的公式也太长了叭）

将 $Ax=b$ 的 $A$ 分裂

$A= D - U -L$

$D = \left[\begin{matrix} a_{11} \\ & a_{22} \\ & & \ddots \\ & & & a_{nn} \end{matrix}\right] \quad L = -\left[\begin{matrix} 0 \\ a_{21} & 0 \\ \vdots & \ddots & \ddots \\ a_{n1} & \cdots & a_{n,n-1} & 0 \end{matrix}\right] \quad U = -\left[\begin{matrix} 0 & a_{12} & \cdots & a_{1n} \\ & \ddots & \ddots & \vdots \\ & & 0 & a_{n-1,n} \\ & & & 0 \end{matrix}\right]$

有：

$\begin{aligned} AX = b \Rightarrow DX^{(k+1)} &= (U+L)X^{(k)} + b \\ X^{(k+1)} &= D^{-1}(U+L)X^{k} + D^{-1}b \end{aligned}$

记

$B_J=D^{-1}(U+L) \qquad f_J=D^{-1}b$

$X^{(k+1)}=B_JX^{(k)}+f_J$

进一步计算 $B_J$ 和 $f_J$：

$\begin{aligned} B_J &=\begin{bmatrix} a_{11} & & & \\ & a_{22} & & \\ & & {\ddots} & \\ & & & {a_{n n}} \end{bmatrix}^{-1} \begin{bmatrix} {0} & {-a_{12}} & \cdots & {-a_{1 n}} \\ {-a_{21}} & {0} & \cdots & {-a_{2 n}} \\ \cdots & \cdots & \cdots & \cdots \\ {-a_{n 1}} & {-a_{n 2}} & \cdots & {0} \end{bmatrix} \\ &= \begin{bmatrix} 0 & -a_{12}/a_{11} & \cdots & -a_{1n}/a_{11} \\ -a_{21}/a_{22} & 0 & \cdots & -a_{2n}/a_{22} \\ \cdots & \cdots & \cdots & \cdots \\ -a_{n1}/a_{nn} & -a_{n2}/a_{nn} & \cdots & 0 \end{bmatrix} \end{aligned}$

$f_J=D^{-1}b=\begin{bmatrix} b_1/a_{11} \\ b_2/a_{22} \\ \vdots \\ b_n/a_{nn} \end{bmatrix}$

高斯-赛德尔迭代法的矩阵表示

高斯-赛德尔的矩阵会复杂一点，因为上面方法被求逆的矩阵是一个对角矩阵，而这里是一个下三角矩阵。

$\begin{aligned} (D-L)X^{(k+1)} &= UX^{(k)} + b \\ X^{(k+1)} &= (D-L)^{-1}UX^{k} + (D-L)^{-1}b \end{aligned}$

记

$B_{G-S}=(D-L)^{-1}U \qquad f_{G-S}=(D-L)^{-1}b$

$X^{(k+1)}=B_{G-S}X^{(k)}+f_{G-S}$

进一步计算 $B_{G-S}$ 和 $f_{G-S}$ 有（其实没有必要往下写了）：

$B_{G-S} =\begin{bmatrix} a_{11} & & & \\ a_{21} & a_{22} & & \\ {\vdots} & {\vdots} & {\ddots} & \\ a_{n1} & a_{n2} & {\cdots} & {a_{n n}} \end{bmatrix}^{-1} \begin{bmatrix} {0} & {a_{12}} & \cdots & {a_{1 n}} \\ & {0} & \ddots & {a_{2 n}} \\ & & \ddots & \vdots \\ & & & {0} \end{bmatrix}$

$f_J=D^{-1}b= \begin{bmatrix} a_{11} & & & \\ a_{21} & a_{22} & & \\ {\vdots} & {\vdots} & {\ddots} & \\ a_{n1} & a_{n2} & {\cdots} & {a_{n n}} \end{bmatrix}^{-1} \begin{bmatrix} b_1 \\ b_2 \\ \vdots \\ b_n \end{bmatrix}$

向量的收敛性

范数知识请看范数简介

迭代的收敛性

在基本概念中提到，迭代即是

$\lim_{k \to \infty}X^{(k)} = X^* \Leftrightarrow \lim_{k \to \infty}\| X^{(k)} - X^* \|_2 = 0$

令 $\varepsilon^{(k)} = X^{(k)} - X^*$，则上述结论可以写为

$\lim_{k \to \infty}X^{(k)} = X^* \Leftrightarrow \lim_{k \to \infty}\| \varepsilon^{(k)} \|_2 = 0$

（利用向量范数的等价性，我们还可以进一步推出上述结论对任意范数同样成立）

接下来，我么换一个角度，看从迭代法的定义还能推出什么关于 $\varepsilon^{(k)}$ 的结论：

$\begin{aligned} X^{(k+1)} &= BX^{(k)}+f \quad (k=0,1,2,...) \\ X^* &= BX^* + f \\ X^{(k+1)} - X^* &= B(X^{(k)}-X^*) \end{aligned}$

则有：

$\varepsilon^{(k)} = B \varepsilon^{(k-1)} \quad (k=1,2,3,...)$

递推一下，

$\varepsilon^{(k)} = B \varepsilon^{(k-1)} = B^2 \varepsilon^{(k-2)} = \cdots = B^k \varepsilon^{(0)}$

得出结论：

$\lim_{k\to\infty}\varepsilon^{(k)} = \mathbf{0} \Leftrightarrow \lim_{k\to\infty} B^k = \mathbf{0}$

结论非常漂亮，就是没法用（逃

于是出现了范数：

$\lim_{k\to\infty}\varepsilon^{(k)} = \mathbf{0} \Leftarrow \|B\| < 1$

证明如下：

由 $\varepsilon^{(k)} = B \varepsilon^{(k-1)}$ 和范数的相容性，有

$\begin{aligned} \| \varepsilon^{(k)} \| &\leq \|B \| \| \varepsilon^{(k-1)} \| \\ \| \varepsilon^{(k)} \| &\leq \|B \|^k \| \varepsilon^{(0)} \| \end{aligned}$

由于 $\|B \| < 1$，

$\lim_{k \to \infty} \| \varepsilon^{(k)} \| \leq \lim_{k \to \infty} \|B \|^k \| \varepsilon^{(0)} \| = 0$

所以有 $\lim_{k\to\infty}\varepsilon^{(k)} = \mathbf{0}$。

然而我们还是不知道当 $\|B\| \geq 1$ 时会发生什么。因此我们要进行推广：

矩阵的谱

定义 矩阵的谱 $\rm{ch}\;B$ （或$\sigma(B)$）就是矩阵特征值的集合 $\{\lambda_1, \lambda_2, ..., \lambda_n\}$。

定义 矩阵 $B$ 的谱半径 $\rho(B) = \max\limits_{1\leq k\leq n}|\lambda_k|$

那么，关于在 范数的相容性 中提到的最大特征值的结论都可以套过来：

结论 1：当 $B$ 是对称矩阵时，$\|B\|_2 = \rho(B)$
结论 2：对于任意范数都有：$\rho(B) \leq \|B\|_2$

定理：

$\lim_{k\to\infty}\varepsilon^{(k)} = \mathbf{0} \Leftrightarrow \rho(B) < 1$

这里就是充要条件了。

对于有些问题，雅可比不收敛、高斯——赛德尔收敛；也有前者收敛，后者不收敛。

套用雅可比和高斯——赛德尔方法中的 $B$ 的结果，可以得到判断该方法是否收敛的算法：

% 雅可比迭代法 B=D\(U+L)
D=diag(diag(A1));
B=D\(D-A);
max(abs(eig(B1))); % 值小于 1 则收敛，大于 1 则不收敛

% 高斯——赛德尔迭代法 B=(D-L)\U
DL=tril(A1);
B1=DL\(DL-A1);
max(abs(eig(B1))); % 值小于 1 则收敛，大于 1 则不收敛

定理：设 $X^*$ 是方程组 $AX=b$ 的解，迭代形式为：$X^{(k+1)}=BX^{(k)}+f$。若 $\|B\| < 1$，则有：

• $\| X^{(k)} - X^* \| \leq \frac{\|B\|}{1-\|B\|} \|X^{(k)} - X^{(k-1)}\|$
• $\| X^{(k)} - X^* \| \leq \frac{\|B\|^k}{1-\|B\|} \|X^{(1)} - X^{(0)}\|$

PPT 上给了第一条的证明，但是太硬核了（给刚接触范数的同学看这些真的看得懂吗），如果需要的话，再来翻 PPT 重学吧。

至于第二条，真的不懂了（逃