Matrix Compututations-Classical iteration method for solving linear equations

迭代法及其收敛条件

一般来说，$l$步迭代可以表示为:

$$\tag{3.2} \boldsymbol{x_k}=\phi_k(\boldsymbol{x_{k-1}},\cdots,\boldsymbol{x_{k-1}})$$

其中，$\phik$为迭代算子，$\boldsymbol x_0,\cdots \boldsymbol x{l-1}$为迭代初值，当$l=1$的时候是单步迭代法；

若迭代过程中，迭代算子不变则称改迭代法为定常迭代法，否则为不定长迭代；

若迭代算子为线性算子，则称改迭代法为线性迭代法，否则为非线性迭代。

线性定常迭代法收敛的充要条件

迭代法（3.2）收敛充要条件为 $\rho(\boldsymbol G)<1$

收敛的性质1

若相容矩阵范数$\lVert ·\rVert_M$ 满足$\lVert G\rVert_M<1$ 则迭代公式（3.2）收敛，且

$$\tag{定理3.2} \lVert\boldsymbol x_k-\boldsymbol x_*\rVert_V\le\frac{\lVert \boldsymbol G\rVert_M^k}{1-\lVert \boldsymbol G\rVert_M} \lVert\boldsymbol x_0-\boldsymbol x_1\rVert_V$$

可以发现，$\boldsymbol x_k$收敛的速度依赖于$\lVert \boldsymbol G\rVert_M$和$1$的接近程度，当$\lVert \boldsymbol G\rVert_M$很接近$1$的时候，收敛速度很慢，当$\lVert \boldsymbol G\rVert_M$很小的时候，收敛较快。

收敛的性质2

设一阶线性定常迭代法的迭代算子为 $\boldsymbol G$,如果其范数$\lVert G\rVert_M=q<1$，那么很显然其收敛，我们有以下结论:

$$(1).&\lim_{k\to\infty}\boldsymbol x_k=\boldsymbol x_*\\ (2).&\lVert \boldsymbol x_*-\boldsymbol x_k\rVert\leq q^k\lVert \boldsymbol x_*-\boldsymbol x_0\rVert\\ (3).&\lVert \boldsymbol x_*-\boldsymbol x_k\rVert\leq\frac{q}{1-q}\lVert \boldsymbol x_k-\boldsymbol x_{k-1}\rVert\\ (4).&\lVert \boldsymbol x_*-\boldsymbol x_k\rVert\leq\frac{q^k}{1-q}\lVert \boldsymbol x_1-\boldsymbol x_0\rVert$$

Jacobi迭代法

Gauss-Seidel迭代法