迭代法基本概念和迭代公式、迭代法收敛性理论

《应用数值分析》
《应用数值分析》

目录

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)$ 谱半径越小,收敛速度越快