迭代法

将 $Ax=b$ 改写为等价的不动点方程 $x = Bx + f$，构造迭代格式： $\(x^{(k+1)} = Bx^{(k)} + f$\) 其中 $B$ 称为迭代矩阵。

收敛性

对任意初始向量 $x^{(0)}$ ,由 $x^{(k+1)} = Bx^{(k)} +f$ 可求得向量序列 ${\{x^{(k)}\}}^{\infty}_0$ ，若 $\lim\limits_{k\to \infty} x^{(k)}=x^*$，则 $x^*$ 就是方程组的解，此时称迭代公式是收敛的，否则则是发散的。（迭代公式是否收敛取决于迭代矩阵B的性质）

雅可比 (Jacobi) 迭代法

分量形式（用于代码更简单的形式）： $x_i^{(k+1)} = \frac{1}{a_{ii}} \left( b_i - \sum_{j=1, j\neq i}^n a_{ij}x_j^{(k)} \right)$
矩阵形式（用于讨论迭代法的收敛性，还是我们考试重点）： $$ \begin{aligned} A = D - L - U&\implies Dx=(L+U)x+b \ &\implies x=D^{-1}(L+U)x+Db \end{aligned} $$ 则：$B_J = D^{-1}(L+U), \quad f_J = D^{-1}b$。其中： $$ \begin{aligned} D &= \begin{pmatrix} a_{11} & & & \ & a_{22} & & \ & & \ddots & \ & & & a_{nn} \end{pmatrix}\ L &= \begin{pmatrix} 0 & & & & \ -a_{21} & 0 & & & \ -a_{31} & -a_{32} & 0 & & \ \vdots & \vdots & \ddots & \ddots & \ -a_{n1} & -a_{n2} & \cdots & -a_{n,n-1} & 0 \end{pmatrix}\ U &= \begin{pmatrix} 0 & -a_{12} & -a_{13} & \cdots & -a_{1n} \ & 0 & -a_{23} & \cdots & -a_{2n} \ & & 0 & \ddots & \vdots \ & & & \ddots & -a_{n-1,n} \ & & & & 0 \end{pmatrix} \end{aligned} $$

高斯-赛德尔 (Gauss-Seidel) 迭代法

对于雅可比迭代法，每次都是通过 $x^{(k)}$ 的全部分量求出 $x^{(k+1)}$ 的全部分量，计算时需要保留两个近似解分量，但是每次已经计算出的信息都没有得到充分的利用。

而如果我们能够利用新的分量，那么如果收敛，则收敛速度和效果会更好一些，并且只需要对旧分量进行替换迭代就好，不需要两个空间进行保存。

分量形式（用于代码更简单的形式）： $x_i^{(k+1)} = \frac{1}{a_{ii}} \left( b_i - \sum_{j=1}^{i-1} a_{ij}x_j^{(k+1)} - \sum_{j=i+1}^n a_{ij}x_j^{(k)} \right)$
矩阵形式（用于讨论迭代法的收敛性，还是我们考试重点）： $$ \begin{aligned} A &= D - L - U \ &\implies Dx=Lx+Ux+b\ & \implies
(D - L)x^{(k+1)}=Ux+b \ & \implies x^{(k+1)} = (D-L)^{-1}Uxb \end{aligned} $$ 则 }+(D-L)^{-1$B_{G-S} = (D-L)^{-1}U, \quad f_{G-S} = (D-L)^{-1}b$

为什么会取L作为系数的部分进行更新呢？观察 $L,U$ 的形式可知，对于第 $i$ 个分量 $x_i$ 的计算，需要取 $L$ 第 $i$ 行非零元与之前的分量相乘，取 $U$ 的第 $i$ 行非零元与 $i$ 之后的分量相乘，但是我们已经求出新的分量了，直接用新的替换即可，所以取 $L$ 作为系数的部分进行更新。

收敛性分析

对于迭代公式 $x^{(k+1)} = Bx^{(k)}+f$ 有下面判断条件：

充要条件：迭代法收敛的充要条件是迭代矩阵 $B$ 的谱半径 $\rho(B) < 1$。
- 什么是谱半径？：$B$ 所有特征值的模的绝对值的最大值，即$\rho(B) = \max\{\left\vert \lambda_1 \right\vert,\left\vert \lambda_2 \right\vert,\cdots,\left\vert \lambda_n \right\vert\}$
收敛充分条件：
- 定理3.5：若 $\left\Vert B\right\Vert < 1$，则迭代法收敛。且有误差公式： $$ \begin{aligned} \left\Vert x^{(k)} - x^ \right\Vert &\leq \frac{\left\Vert B\right\Vert}{1 - \left\Vert B\right\Vert} \left\Vert x^{(k)} - x^{(k-1)} \right\Vert \ \left\Vert x^{(k)} - x^ \right\Vert &\leq \frac{\left\Vert B\right\Vert^k}{1 - \left\Vert B\right\Vert} \left\Vert x^{(1)} - x^{(0)} \right\Vert \end{aligned} $$
定理3.6：若 $A$ 严格对角占优或不可约对角占优，则雅可比法和高斯-赛德尔法均收敛。
定理3.7：若 $A$ 对称正定，则高斯-赛德尔法收敛；若 $A$ 对称正定， $2D-A$ 也对称(不)正定，则雅可比迭代法（不）收敛，

收敛速度

收敛速度：$R(B) = -\ln \rho(B)$。$\rho(B)$ 越小，收敛越快。