迭代法基本概念和迭代公式、迭代法收敛性理论
目录
5. 线性代数方程组数值解法——迭代法
5.1 迭代法基本概念和迭代公式
解线性代数方程组
（$\pmb{A} \in \pmb{R}^{n \times n}$ 非奇异，$\pmb{b}=(b_1,b_2,\cdots,b_n)^T \neq 0$，$\pmb{x}=(x_1,x_2,\cdots,x_n)^T$ 为解向量）的迭代法具体做法是，将上述方程组变形为等价形式：
特别的，这里仅研究其线性的形式：
其中，$\pmb{B} \in \pmb{R}^{n \times n}$ 非奇异，$\pmb{f} \in \pmb{R}^n$。构造迭代公式：
- 每一步迭代值 $\pmb{x}^{(k+1)}$ 仅依赖于前一步迭代值 $\pmb{x}^{(k)}$，这称为单步迭代
- $\pmb{B}$ 和 $\pmb{f}$ 与 $k$ 无关，这称为定常情形
- $\pmb{B}$ 称为迭代矩阵
- 按照迭代公式可产生向量序列 $\left\{ \pmb{x}^{(k)} \right\}(k=0,1,\cdots)$，如果 ，即序列 收敛于
5.2 $Jacobi$ 迭代法
设方程组 $\pmb{A}\pmb{x}=\pmb{b}$ 中 $\pmb{A}=(a_{ij}) \in \pmb{R}^{n \times n}$，$\pmb{b} = (b_i)\in \pmb{R}^{n \times n}$ 且 $a_{ii} \neq 0 \ (i=1,2,\cdots,n)$
假设系数矩阵 $A$ 的对角元 $a_{ii} \neq 0 \ (i=1,2,\cdots,n)$，则对角矩阵 $\pmb{D}=diag(a_{11},a_{22},\cdots,a_{nn})$ 非奇异。可将矩阵 $\pmb{A}$ 分解为：
其中，
此时原方程组可改写为：
其中，
则 $Jacobi$ 迭代公式为：
5.3 $Gauss$-$Seidel$ 迭代法
原方程组可改写为：
其中，
则 $Gauss-Seidel$ 迭代公式为：
5.4 迭代法收敛性理论
5.4.1 迭代法收敛性基本定理
设方程组为 $\pmb{x} = \pmb{B} \pmb{x} + \pmb{f}$，对任意的初始向量 $\pmb{x}^{(0)}$，解此方程组的迭代法
收敛的充分必要条件是迭代矩阵 $\pmb{B}$ 的谱半径 $\rho(\pmb{B}) < 1$
5.4.2 迭代法收敛性充分条件
如果迭代法 $\pmb{x}^{(k+1)} = \pmb{B} \pmb{x}^{k} + \pmb{f} \quad (k=0,1,\cdots)$ 的迭代矩阵 $\pmb{B}$ 的某一种算子范数 ，则：
- 对任意初始向量 $\pmb{x}^{(0)}$，迭代法收敛；
- 迭代序列与方程组的解 $x^*$ 存在误差估计式：
或
5.4.3 严格占优对角矩阵
设 $\pmb{A} = (a_{ij}) \in \pmb{R}^{n \times n}$，若满足
则称 $\pmb{A}$ 为严格对角占优矩阵；若满足其中至少有一个严格不等式成立，则称 $\pmb{A}$ 为弱对角占优矩阵。
定理：若方程组 $\pmb{A}\pmb{x}=\pmb{b}$ 中，$\pmb{A} = (a_{ij}) \in \pmb{R}^{n \times n}$ 为严格对角占优矩阵，或为不可约弱对角占优矩阵，则解此方程组的 $J$ 法和 $GS$ 法均收敛。
5.4.4 收敛速度问题
设迭代法收敛，定义
称 $R(\pmb{B})$ 为迭代法的渐近收敛速度。由定义可知，$R(\pmb{B})$ 越大，收敛越快，也即 $\rho(\pmb{B})(0<\rho(\pmb{B})<1)$ 谱半径越小，收敛速度越快。
