迭代法基本概念和迭代公式、迭代法收敛性理论
《应用数值分析》
目录
5. 线性代数方程组数值解法——迭代法
5.1 迭代法基本概念和迭代公式
解线性代数方程组
AAxx=bb（AA∈RRn×n 非奇异，bb=(b1,b2,⋯,bn)T≠0，xx=(x1,x2,⋯,xn)T 为解向量）的迭代法具体做法是，将上述方程组变形为等价形式：
xx=FF(xx)特别的，这里仅研究其线性的形式：
xx=BBxx+ff其中，BB∈RRn×n 非奇异，ff∈RRn。构造迭代公式：
xx(k+1)=BBxxk+ff(k=0,1,⋯)- 每一步迭代值 xx(k+1) 仅依赖于前一步迭代值 xx(k)，这称为单步迭代
- BB 和 ff 与 k 无关，这称为定常情形
- BB 称为迭代矩阵
- 按照迭代公式可产生向量序列 {xx(k)}(k=0,1,⋯)，如果 limk→∞xx(k)=xx∗，即序列 {xx(k)} 收敛于 xx∗
5.2 Jacobi 迭代法
设方程组 AAxx=bb 中 AA=(aij)∈RRn×n，bb=(bi)∈RRn×n 且 aii≠0 (i=1,2,⋯,n)
假设系数矩阵 A 的对角元 aii≠0 (i=1,2,⋯,n)，则对角矩阵 DD=diag(a11,a22,⋯,ann) 非奇异。可将矩阵 AA 分解为：
AA=DD−LL−UU其中，
LL=−[0a210⋮⋮⋱an1an2an30],UU=−[0a12⋯a1n0⋯a2n⋱⋮0]此时原方程组可改写为：
xx(k+1)=BBJxx(k)+ff(k=0,1,⋯)其中，
BBJ=DD−1(LL+UU) 或BBJ=II−DD−1AA,ff=DD−1bb则 Jacobi 迭代公式为：
{xx(0)=(x(0)1,x(0)2,⋯,x(0)n)Tx(k+1)i=(bi−n∑j=1,j≠iaijx(k)j)/aii, i=1,2,⋯,n5.3 Gauss-Seidel 迭代法
原方程组可改写为：
xx(k+1)=BBGSxx(k)+ff(k=0,1,⋯)其中，
BBGS=(DD−LL)−1UU, ff=(DD−LL)−1bb则 Gauss−Seidel 迭代公式为：
{xx(0)=(x(0)1,x(0)2,⋯,x(0)n)Tx(k+1)i=(bi−i−1∑j=1aijx(k+1)j−n∑j=i+1aijx(k)j)/aii, i=1,2,⋯,n5.4 迭代法收敛性理论
5.4.1 迭代法收敛性基本定理
设方程组为 xx=BBxx+ff，对任意的初始向量 xx(0)，解此方程组的迭代法
xx(k+1)=BBxxk+ff(k=0,1,⋯)收敛的充分必要条件是迭代矩阵 BB 的谱半径 ρ(BB)<1
5.4.2 迭代法收敛性充分条件
如果迭代法 xx(k+1)=BBxxk+ff(k=0,1,⋯) 的迭代矩阵 BB 的某一种算子范数 ‖BB‖<1，则：
- 对任意初始向量 xx(0)，迭代法收敛；
- 迭代序列与方程组的解 x∗ 存在误差估计式：
或
‖x∗−x(k)‖⩽‖BB‖(k)1−‖BB‖‖xx(1)−xx(0)‖5.4.3 严格占优对角矩阵
设 AA=(aij)∈RRn×n，若满足
|aii|>n∑j=1,j≠i|aij|(i=1,2,⋯,n)则称 AA 为严格对角占优矩阵；若满足其中至少有一个严格不等式成立，则称 AA 为弱对角占优矩阵。
定理：若方程组 AAxx=bb 中，AA=(aij)∈RRn×n 为严格对角占优矩阵，或为不可约弱对角占优矩阵，则解此方程组的 J 法和 GS 法均收敛。
5.4.4 收敛速度问题
设迭代法收敛，定义
R(BB)=−lnρ(BB)称 R(BB) 为迭代法的渐近收敛速度。由定义可知，R(BB) 越大，收敛越快，也即 ρ(BB)(0<ρ(BB)<1) 谱半径越小，收敛速度越快。
