武汉大学数学与统计学院：《数值分析》第二章 求解线性方程组的数值解法（2.2）线性方程组的迭代法

22解线性方程组的送代法 Iterative Methods for Solving Linear Systems */ 将Ax=b改写为等价形式x=Bx+g 、峥建立迭代x1=Bx+8。从初值x出发, 得到序列{xk}。 研究内容: a如何建立迭代格式? a收敛速度? a向量序列的收敛条件?a误差估计?

2.2 解线性方程组的迭代法 /* Iterative Methods for Solving Linear Systems */ 思 路 将 A x b = 改写为 等价形式 ， 建立迭代 。从初值 出发， 得到序列 。 x B x g = + x B x g k k +1 = + 0 x { } xk 研究 内容：  如何建立迭代格式？  收敛速度？  向量序列的收敛条件？  误差估计？

2.21逐次逼近法〔迭代格式的构造) 把矩阵A分裂为 Q-C,Q≠O Ax=b冷(-C)x=b 冷(-QC)x=Qb 冷x=Bx+g

2.2.1 逐次逼近法(迭代格式的构造) 把矩阵A分裂为 则 A Q C Q = −  , 0,1 1 ( ) ( ) . Ax b Q C x b I Q C x Q b x Bx g − − =  − =  − =  = +

将上式写为迭代过程 k+1 B x H k (2) 这种迭代过程称为逐次逼近法,‘称为迭代矩阵。 给定初值x,就得到向量序列 0,x1∵, 收敛性定义:若lmx称逐次逼近法收敛 ,否则,称逐次逼近法不收敛或发散

将上式写为迭代过程 这种迭代过程称为逐次逼近法，B称为迭代矩阵。 1 , (2) k k x Bx g + = + * lim , n n x x → 收敛性定义：若 = 称逐次逼近法收敛 ，否则，称逐次逼近法不收敛或发散。 0 x , 0 1 , , , n x x x 给定初值 就得到向量序列

问题:x是否是方程组Ax=b的解? 定理221任意给定初始向量X,如果由逐次 逼近法产生的向量序列收敛于向量x*,那么, x是方程组X=BX+g的解 证明:ix1=lim(Bx+g)→x=Bx+g

问题： x * 是否是方程组Ax=b的解？ * * 1 lim lim( ) . k k k k x Bx g x Bx g + → → = +  = + 定理2.2.1 任意给定初始向量x0，如果由逐次 逼近法产生的向量序列收敛于向量x * ，那么， x *是方程组x=Bx+g的解 证明：

逐次逼近法收敛的条件 补充定理当→时,B→0分p(B)0 k

逐次逼近法收敛的条件 补充定理 当k→ 时，Bk → 0   ( B ) < 1 定理2.2.2 设线性方程组x=Bx+g有惟一解，那 么逐次逼近法对任意初始向量X０收敛的充分必 要条件是迭代矩阵B的谱半径  ( B ) <1 * * 1 * * 1 * 1 0 ( ) ( ). k k k k k x Bx g x Bx g x x B x x B x x + + +  = +    = + − = − = = − 证明： * 1 1 lim( ) 0 lim 0 ( ) 1. k k k k x x B B  + + → → 因此 − =  =  <

要检验一个矩阵的谱半径小于1比较困难 所以我们希望用别的办法判断收敛性 定理2.2.3若逐次逼近法的迭代矩阵满 足B川!<1,那么逐次逼近法收敛 Remark:因为矩阵范数·酬,嘟可以 直接用矩阵的元素计算,因此用定理2.2.3 容易判别逐次逼近法的收敛性

要检验一个矩阵的谱半径小于1比较困难， 所以我们希望用别的办法判断收敛性 定理2.2.3 若逐次逼近法的迭代矩阵满 足‖B‖<1， 那么逐次逼近法收敛 Remark:因为矩阵范数 都可以 直接用矩阵的元素计算，因此,用定理2.2.3， 容易判别逐次逼近法的收敛性。 1 B , F B , B 

问题:如何判断可以终止迭代?(误差估计) 定理224充分条件)若存在一个矩阵范数使得‖B<, 则迭代收敛,且有下列误差估计: B‖ k+1 k+1 B |B‖ X不x k+1 1-‖1B3‖1 k+1 k 误差表达 证明:②x*-x=B(x4x)式及收敛 B(x Fk+1+xk+ 速 x和-x 停机准则。 k|) X-x k+1/s-TDT 1-|B∥x-x

定理2.2.4（充分条件）若存在一个矩阵范数使得 || B || < 1, 则迭代收敛，且有下列误差估计： 1 1 || || || * || || || 1 || || k k k B x x x x B −  − + + − ② ① 1 1 1 0 || || || * || || || 1 || || k k B x x x x B + −  − + − 证明： ② 1 1 1 * ( * ) ( * ) k k k k k x x B x x B x x x x + + + − = − = − + − 1 1 1 || * || || || (|| * || || ||) k k k k x x B x x x x + + + −  − + − 问题：如何判断可以终止迭代？（误差估计） 1 1 || || || * || || || 1 || || k k k B x x x x B −  − + + − 误差表达 式及收敛 速度。 停机准则

① k+1 x k= b(xx-xk-d=.=B(x-xo) xk+1-x|1‖BHx-x0 B k+1 米 Bl -x k+ 1-‖B‖ k+1 1-‖B 0

1 1 1 0 ( ) ... ( ) k k k k k x x B x x B x x + − − = − = = − 1 1 1 1 0 || || || || || * || || || || || 1 || || 1 || || k k k k B B x x x x x x B B + −  −  − + + − − ① 1 1 0 || || || || || || k k k x x B x x + −  −

§222 Jacobi法( Jacobi lterative methods) aux +a22x2 +.+al,,=b 2x1+a2x2+…+a2nxn=b,1≠ 0写成矩阵形式 In11十ln,x十,十lnx Ax=b e(D-L+u)x nn 冷Dx=(L+U/)x+b 冷x=D(L+U/)x+Db U B XR=D(L+U)xk+Db Jacobi迭代阵

      + + + = + + + = + + + = n n nn n n n n n n a x a x a x b a x a x a x b a x a x a x b ... ... ... ... ... ... ... 1 1 2 2 2 1 1 2 2 2 2 2 1 1 1 1 2 2 1 1  0 ii a 写成矩阵形式： A = -L -U D ( ( )) ( ) Ax b D L U x b Dx L U x b =  − + =  = + + 1 1 x D L U x D b ( )  = + + − − B f  Jacobi 迭代阵 1 1 1 k ( ) k x D L U x D b + − − = + + §2.2.2 Jacobi 法 ( Jacobi Iterative Methods )

12 D L U 2 0 B=D(L+0= In -an -an2

11 22 33 nn a a D a a       =           21 31 32 1 2 3 0 0 0 0 n n n a L a a a a a     −   = − −       − − −   12 13 1 23 2 3 0 0 0 0 n n n a a a a a U a   − − −   − −   =   −       33 1 1 11 12 13 1 1 22 21 23 2 1 31 32 3 1 1 2 3 ( ) 0 0 0 0 0 0 0 0 J n n n n n n nn B D L U a a a a a a a a a a a a a a a a − − − − − = + =        − − −        − − −             − − +   −                     − − −      