数值分析—第3章 线性方程组迭代法

1、数值分析数值分析1第第4 4章章 线性方程组的迭代法线性方程组的迭代法&3.1 向量和矩阵的范数向量和矩阵的范数 &3.2 Jacobi迭代法迭代法&3.3 Gauss-Seidel迭代法迭代法&3.4 迭代法的收敛性迭代法的收敛性&3.5 逐次超松弛迭代法逐次超松弛迭代法 Iterative Techniques for Solving Linear Systems数值分析数值分析23.1.1 向量范数向量范数3.1 向量和矩阵的范数向量和矩阵的范数 定义定义3-1 Rn上的上的向量范数向量范数|.|是一个从是一个从Rn到到R的函数，它满足以下性质：的函数，它满足以下性质：00|;0|)1(

2、 xxx（正定性（正定性)|)2(xx C 对任意对任意(齐次性齐次性) |)3(yxyx （三角不等式（三角不等式) 为了误差的度量为了误差的度量数值分析数值分析3 2. 2. - -范数范数( (最大范数最大范数) )： 1. 1-1. 1-范数：范数： 3. 2-3. 2-范数：范数： 3. 3. p- -范数：范数： 其中其中 . .),1p 例例 计算向量计算向量 的各种范数的各种范数. . Tx)3 ,2, 1 ( 解解 16123,x 3x 222123142()x 定义定义3-2 设向量设向量x=(x1, x2, , xn)T，定义，定义 niixx11| |max|1inix

3、x niixx122| pnipipxx/11| |limxxpp常用向量范数：常用向量范数：数值分析数值分析4向量序列的收敛性向量序列的收敛性定义定义3-3 设有设有n维向量序列维向量序列xk=(x1(k), x2(k), , xn(k)T，及，及n维向量维向量x=(x1, x2, , xn)T ，如果，如果1 2()lim,(, , ),kiikxxin 成立，则称成立，则称 xk 收敛于收敛于x，记为记为 lim.kkxx 定理定理3-1 对任意向量对任意向量xRn， （1） x的范数的范数x是各分量是各分量x1, x2, , xn的的n元连续函数；元连续函数； （2） x的任意两种范数

4、均等价，即设的任意两种范数均等价，即设xr和和xs为为Rn上的任意两种范数，上的任意两种范数，则存在常数则存在常数m，M，使得，使得 m xrxs Mxr，任意任意xRn ；（3）向量序列）向量序列xk收敛于向量收敛于向量x 等价于向量序列等价于向量序列xk依范数收敛于向量依范数收敛于向量x，即即向量范数的连续性向量范数的连续性0lim.kkxx 推论推论Rn 上一切范数都等价。上一切范数都等价。数值分析数值分析5证（证（2）只要就只要就 证明上式成立即可，即证明证明上式成立即可，即证明sxx 与与存在常数存在常数 使使 0,mM 0s, R.nxmMxxx 且考虑泛函考虑泛函 0(),R.n

5、sfxxx 记记 则则 是一个有界闭集是一个有界闭集. . 1 ,R,nSxxx S 由于由于 为为 上的连续函数，所以上的连续函数，所以 于于 上达到上达到最大值最大值M M，最小值，最小值m m，)(xfS)(xfS设设 且且R,nx ,0 x,Sxx则则从而有从而有 ,sxmMx 即即 12, R .nscxxcxx 数值分析数值分析6证证(3), 0*lim*lim)()( xxxxkkkk显然，显然，,0*lim*lim)()( xxxxkkkk()()* kkmxxxx 于是于是.0*lim0*lim)()( xxxxkkkk 其中其中为向量的任一种范数为向量的任一种范数. . 使

6、使 而对于而对于 上任一种范数上任一种范数，由，由(2)(2)，存在常数，存在常数m,MnR()*, kMxx 证明证明 如果在一种范数意义下向量序列收敛时，则在任如果在一种范数意义下向量序列收敛时，则在任何一种范数意义下该向量序列均收敛何一种范数意义下该向量序列均收敛. . 数值分析数值分析73.1.2 矩阵范数矩阵范数 定义定义3-4 如果如果Rnn上的某个实值函数上的某个实值函数| . |满足：满足： (4)* | AB | | A | | B | （相容（相容)00|;0|)1( AAA（正定性（正定性)|) 2(AA C 对任意对任意(齐次性齐次性) |) 3(BABA （三角不等式

7、（三角不等式) 则称则称 是是 上的一个上的一个矩阵范数矩阵范数（Matrix Norm）. nnR . xAAx 定义定义3-5 如果对于任意一个向量如果对于任意一个向量 和任意一个矩阵和任意一个矩阵 都有不等式：都有不等式：nnARnxR则称矩阵范数和向量范数是则称矩阵范数和向量范数是相容的相容的。数值分析数值分析8定义定义3-6设设 , , ，nxRnnA R给定一种向量范数给定一种向量范数 ( (如如 或或) )，相应地定义矩，相应地定义矩阵阵A的一个实值函数的一个实值函数vx2,1v( (矩阵的算子范数矩阵的算子范数) ) . max 0vvxvxAxA 则称则称 是通过向量范数是通

8、过向量范数 导出的导出的算子范数算子范数，或向，或向 量范数量范数 的的从属范数从属范数. . vA v v 定理定理3-2 njijaAni1|max|1（行和范数行和范数） niijaAnj11|max|1（列和范数列和范数）)(|max2AAAT （谱范数谱范数 ）矩阵矩阵 ATA 的最大的最大特征根特征根数值分析数值分析9 例例3-2设设 ，计算，计算 的各种范数的各种范数. . 1223A A 解解 112235max,A 1223TA ，12max,23 5,A 29454 263max().TAA A 1212232358813TA A 2136418105-8(5)()-813

9、TIA A 21818494 52 数值分析数值分析103.1.3 矩阵谱半径矩阵谱半径1maxii n 定义定义3-7 设设 的特征值为的特征值为 则称则称 为为A的的谱半径谱半径。nnA R12,n 谱半径谱半径ReIm (A)数值分析数值分析11 证明证明 设设 是是 的任一特征值，的任一特征值， 为相应的特征向量，为相应的特征向量，Ax则则 ，xAx由相容性条件得由相容性条件得 xxAx,xA 注意到注意到 , , 即得即得 0 x,A 定理定理3-3 设设 ，则对任一种算子范数，则对任一种算子范数 ，均有，均有Rn nA A()AA 定理定理3-4 如果如果 ，则，则 的充分必要条件

10、是的充分必要条件是A的谱的谱半径半径nnA R()1.A ( ).AA 故故0kAk （）数值分析数值分析12定理定理若若A对称，则有对称，则有)(|2AA 证明：证明：)()(|2maxmax2AAAAT A对称对称若若 是是 A 的一个特征根，则的一个特征根，则 2 必是必是 A2 的特征根。的特征根。又：对称矩阵的特征根为实数，即又：对称矩阵的特征根为实数，即 2(A) 为非负实数，为非负实数，故得证。故得证。)()(22maxAA 对某个对某个 A 的特征根的特征根 成立成立所以所以2-范数亦称为范数亦称为谱范数谱范数。数值分析数值分析133.2 Jacobi迭代法迭代法 考虑线性方程

11、组考虑线性方程组 ,bAx 其中其中A为非奇异矩阵。为非奇异矩阵。 迭代法通常都可利用迭代法通常都可利用A 中有中有大量零元素大量零元素的特点的特点. 当当A 为为低阶稠密矩阵低阶稠密矩阵时，选主元消去法是有效方法时，选主元消去法是有效方法. 迭代法适用于求解迭代法适用于求解大型稀疏大型稀疏的线性方程组。的线性方程组。基本思想：基本思想： 从一个从一个初始向量初始向量出发出发，按照一定的按照一定的递推格式递推格式 ， 产生逼近方产生逼近方程组的程组的近似解序列近似解序列。思思路路与解与解f (x)=0 的的不动点迭代不动点迭代相似相似 ，将方程组将方程组Ax=b等价改写成等价改写成x=Bx+f

12、形式，从而建立形式，从而建立迭代格式迭代格式 x(k+1)=Bx(k)+f ，从从x（0） 出发，生成迭代序列出发，生成迭代序列x(k) .数值分析数值分析14 例例3-3 求解方程组求解方程组 .361236,33114,20238321321321xxxxxxxxx记为记为 , , bAx ,12361114238A方程组的精确解是方程组的精确解是 . . Tx)1,2,3(* 其中其中 ,321xxxx.363320b现改写为现改写为 ).3636(121),334(111),2023(81213312321xxxxxxxxx或写为或写为 , , fxBx0数值分析数值分析15,0123

13、1261110114828300B其中其中 .12361133820f代入代入 任取初始值，例如取任取初始值，例如取 . . Tx)0,0,0()0( 得到新的值得到新的值 ).3636(121),334(111),2023(81213312321xxxxxxxxx,) 3 , 3 , 5 . 2(),() 1 (3) 1 (2) 1 (1) 1 (TTxxxx,)(3)(2)(1)()1(3)1(2)1(1)1()0(3)0(2)0(1)0( kkkkxxxxxxxxxxxx数值分析数值分析16, 8/ )2023()(3)(2)1(1kkkxxx,11/ )334()(3)(1)1(2kk

14、kxxx.12/ )3636()(2)(1)1(3kkkxxx简写为简写为 ,)(0)1(fxBxkk其中其中 表示迭代次数表示迭代次数 k).,2, 1 ,0(k 迭代到第迭代到第10次有次有 ;)9998813. 0,999838. 1 ,000032. 3()10(Tx 从此例看出，由迭代法产生的向量序列从此例看出，由迭代法产生的向量序列 逐步逼近逐步逼近)(kx方程组的精确解方程组的精确解 . .*x*).(000187.0)10()10()10(xx 以上过程称为以上过程称为Jacobi迭代法迭代法。数值分析数值分析17 Tnxxx),()0()0(1)0(,/1)()1(iinij

15、jkjijikiaxabx ).10(), 2 , 1(表表示示迭迭代代次次数数,kni 解解 Ax=b 的雅可比迭代法的的雅可比迭代法的分量计算公式分量计算公式 Jacobi方法是由方程组第方法是由方程组第i个方程解出个方程解出xi得到的等价方程组。得到的等价方程组。.ADLU Jacobi迭代的矩阵形式迭代的矩阵形式1122nnaaDa 1211121210000,nnnnnnaaaaaUa 2111121210000,nnnnnnaLaaaaa 数值分析数值分析18 Jacobi 迭代法迭代法 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa.221122222121112

16、12111 nnnnnnnnnnnnbxaxaaxbxaxaaxbxaxaax11112212122211212111.1.1.10 iia写成写成矩阵形式：矩阵形式：A =-L-UD()()AxbDL U xbDxLU xb11()xDL U xD bBfJacobi 迭代阵迭代阵.ADLU 010 1 2()()(), ,kkxxBxfk 初初 始始 向向 量量 ，其中其中 1,BIDA 1.fD b 迭代矩阵迭代矩阵常数项常数项数值分析数值分析193.3 Gauss-Seidel迭代法迭代法高斯高斯- -塞德尔迭代法塞德尔迭代法 )(11)(1)(414)(313)(21211)1(1b

17、xaxaxaxaaxknnkkkk )(12)(2)(424)(323)1(12122)1(2bxaxaxaxaaxknnkkkk )(13)(3)(434)1(232)1(13133)1(3bxaxaxaxaaxknnkkkk )(1)1(11)1(33)1(22)1(11)1(nknnnknknknnnknbxaxaxaxaax 写成写成矩阵形式：矩阵形式：BfGauss-Seidel 迭代阵迭代阵1 ()()()kkDL xUxb 1111()()()()kkkxDLxUxDb 111()( )()()kkxDLUxDLb 数值分析数值分析200000 0() (,)Tx 取取 ， 例例

18、3-4 用用Gauss-Seidel迭代法解线性方程组迭代法解线性方程组. . 按高斯按高斯- -塞德尔迭代公式塞德尔迭代公式 迭代迭代5 5次，得次，得 ，51 0001 2 00001 0000 1 0000()( .,.,., .)Tx 12312341234234102611325210113815, ,. xxxxxxxxxxxxxx 112311213411131244261032511211100 1()()()()()()()()()()()()/, ()/, ()/.(, ,)kkkkkkkkkkkkxxxxxxxxxxxkx 111233158)()()()/ . kkxx

19、 54110()*.xx 且且 解解数值分析数值分析21 对于任何由对于任何由 变形得到的等价方程组变形得到的等价方程组 ，fBxxbAx 迭代法产生的向量序列迭代法产生的向量序列 是否都能逐步逼近方程组是否都能逐步逼近方程组的解的解 ？ )(kx*x如方程组如方程组.53,521221xxxx构造迭代法构造迭代法.53,52)(1)1(2)(2)1(1kkkkxxxx则对任何的初始向量，得到的序列都不收敛则对任何的初始向量，得到的序列都不收敛. .二种方法都存在二种方法都存在收敛性问题收敛性问题。 有例子表明：有例子表明：Gauss-Seidel法收敛时，法收敛时，Jacobi法可能法可能不

20、收敛；而不收敛；而Jacobi法收敛时，法收敛时， Gauss-Seidel法也可能法也可能不收敛。不收敛。数值分析数值分析223.4 迭代法的收敛性迭代法的收敛性的收敛条件的收敛条件fxBxkk )()1(*)1()1(xxekk )()()(*)()*()(kkkeBxxBfxBfxB )0()(eBekk |.|)0() 1()(eBeBekkk /* Convergence of Iterative methods */*xBxf数值分析数值分析23Gauss-Seide迭代法收敛的充分条件是迭代法收敛的充分条件是 ，其中，其中1().B 定理定理3-5（迭代收敛基本定理）（迭代收敛基

21、本定理）设有方程组设有方程组x=Bx+f的及的及任意初始向量任意初始向量x（0），求解该方程组的迭代法，求解该方程组的迭代法收敛当且仅当迭代矩阵收敛当且仅当迭代矩阵B的谱半径的谱半径10 1 2()( ), , , ,kkxB xfk （1）迭代法是否收敛取决于迭代矩阵的迭代法是否收敛取决于迭代矩阵的谱半径谱半径，与初始，与初始 向量和常数项无关。向量和常数项无关。 （2）而对于同一个方程组，不同的迭代法对应的迭代而对于同一个方程组，不同的迭代法对应的迭代 矩阵的矩阵的谱半径谱半径一般不会相同，因而收敛性也不同。一般不会相同，因而收敛性也不同。上述定理说明：上述定理说明：（3） Jacobi迭

22、代法收敛的充分条件是迭代法收敛的充分条件是 ,其中其中1( )J 1( )G 1().JDL U 1().GDLU 数值分析数值分析24232-=-6=0-IB ，例例3-5 考察用迭代法解以下方程组的收敛性：考察用迭代法解以下方程组的收敛性：解解 迭代矩阵迭代矩阵B的特征方程为的特征方程为025, =.305xB xfBf 其其中中 ，特征根为：特征根为：=6 ，6661 ()max,B 因此迭代法发散。因此迭代法发散。数值分析数值分析25定理定理3-6（迭代法收敛的充分条件）（迭代法收敛的充分条件）如果迭代法如果迭代法 x(k+1)=Bx(k)+f的迭代矩阵的迭代矩阵B的某一种范数的某一种

23、范数B1，则，则（1）对任意初始向量）对任意初始向量x(0) ，迭代法收敛；，迭代法收敛；11( )( )()kkkBxxxxB 证明：证明： 1( )BB （2）迭代误差满足）迭代误差满足101( )( )( )kkBxxxxB （1）由条件）由条件故迭代法收敛。故迭代法收敛。数值分析数值分析2611( )( )()kkkBxxxxB 证明：证明： （2）迭代误差满足）迭代误差满足101( )( )( )kkBxxxxB （2）由条件）由条件111111( )()()( )()( )()( )()( )( )()( ) ()() ()() kkkkkkkkkkkkkxxxxxxxxxxB x

24、xB xxB xxB xx 11( )( )()()kkkBxxB xx 1,B 由条件由条件 即即 ，于是，于是10B 11( )( )()kkkBxxxxB 数值分析数值分析2711( )( )()kkkBxxxxB 证明：证明： （2）迭代误差满足）迭代误差满足101( )( )( )kkBxxxxB （2）由）由11( )( )()kkkBxxxxB 121()()()kkBB xxB 2121()()kkBxxB 101( )( )kBxxB 误差估计式误差估计式的用处？的用处？数值分析数值分析28例例 用用Jacobi迭代法求上例中方程组的解，取迭代法求上例中方程组的解，取x(0)

25、=(0,0,0)T，若，若使误差使误差 x(k)-x* 10-5，问需要迭代多少次，问需要迭代多少次?由上例知由上例知, x(1)=(1.4,0.5,1.4)T,于是有于是有 x(1)-x(0) =1.4 , B =0.5 .00010310110351101103Bk应满足应满足095.185 . 0ln/ )4 . 1105 . 0ln(5 k故取故取k=19, 即需要迭代即需要迭代19次次.解解若使若使x(k) x* ，只需只需 )0()1(1xxBBk，即即BkxxBln/ )ln(0)(1)(1 事前估计迭代次数事前估计迭代次数数值分析数值分析291( )( )()kkkxxAxbA

26、xb 迭迭代代过过程程 求求解解方方程程组组例例， 问问取取什什么么实实数数 可可使使迭迭代代收收敛敛？ 其其中中323,221Ab 解解 迭迭代代矩矩阵阵 13212BIA (14 )(1)EB 1()max14, 1102B 故故时时, ,迭迭代代法法收收敛敛. .数值分析数值分析30例例3-6 已知方程组已知方程组解：解：1 20 6,. Jacobi法收敛法收敛1100202010 300 30()*,.JDLU Gauss-Seidel法的迭代矩阵为：法的迭代矩阵为：Gauss-Seidel法收敛法收敛Jacobi法的迭代矩阵为：法的迭代矩阵为：121210 312.xx 判断用判断

27、用Jacobi法和法和Gauss-Seidel法求解此方程组的收敛性。法求解此方程组的收敛性。120 31,.A 220 600 3.,. 1110021002020 31000 310000 6().GDLU 20 6000 6(. ),. 1 20 0 6, , 数值分析数值分析31)., 2 , 1(1niaanijjijii 则称则称A为为严格对角占优矩阵严格对角占优矩阵. . 定义定义 设设 满足满足()n nijAaR 定理定理4 ( (对角占优定理对角占优定理) ) 如果如果 为严格对角占优矩阵，则为严格对角占优矩阵，则aii 0 , ,且且A为为非奇异非奇异矩阵矩阵. . ()

28、nnijAaR 如果如果det(A) =0，则，则 Ax=0有非零解，有非零解， 记为记为 , 12(,)Tnxxxx 齐次方程组第齐次方程组第k个方程个方程 ,01njjkjxa则有则有 .0max1inikxx设设 证明证明,1 nkjjkjkkaa即即 与假设矛盾，故与假设矛盾，故 0det().A nkjjjkjkkkxaxa1反证法反证法 nkjjjkjxa1,1 nkjjkjkax假定假定 为严格对角占优矩阵，由定义知为严格对角占优矩阵，由定义知()nnijAaR 10,niiijjj iaa 故故aii 0.数值分析数值分析32 定理定理6,7 设设 为严格对角占优矩为严格对角占

29、优矩阵，则解方程组阵，则解方程组Ax=b的的Jacobi法及法及Gauss-Seidel 法法均收敛均收敛. ()nnijAaR 定理定理 设设 为对称正定矩阵，为对称正定矩阵，则解方程组则解方程组Ax=b的的Gauss-Seidel法收敛法收敛. ()nnijAaR 以下两个定理给出判别以下两个定理给出判别Jacobi迭代及迭代及Gauss-Seidel迭代收敛的简便方法：迭代收敛的简便方法： 定理表明若定理表明若A对称正定对称正定, ,则则Gauss-Seidel法法一定一定收敛，但收敛，但Jacobi法法不一定收敛不一定收敛. .数值分析数值分析33 例例 在线性方程组在线性方程组 中中

30、bAx ,111 aaaaaaA证明当证明当 时高斯时高斯- -塞德尔法收敛，而雅可比迭代法塞德尔法收敛，而雅可比迭代法只在只在 时才收敛时才收敛. .121a2121a证明证明由由 的顺序主子式的顺序主子式A011122aaa1 a, 0)21 ()1 (321det2233aaaaA21 a当当 时，时， 正定，故高斯正定，故高斯- -塞德尔法收敛塞德尔法收敛. .121aA雅可比迭代雅可比迭代,000 aaaaaaJ, 0)2()()det(2 aaJI 当当 ，即，即 时雅可比法收敛时雅可比法收敛. .12)(aJ21a 当当 时高斯时高斯- -塞德尔法收敛，而塞德尔法收敛，而 ，雅可

31、比法不收敛，此时雅可比法不收敛，此时 不是正定的不是正定的. .8.0a16.1)(JAD 2数值分析数值分析343.4 逐次超松弛迭代法逐次超松弛迭代法 (SOR法法)11111()()( )/,inkkkiiijjijjiijj ixba xa xa )()1()1()1(kikikixxx ,/)(11)1()()1(iinijkjijijkjijikikiaxaxabxx )()()1()()1(kikikikixxxx )()()()1()()1(kkkkkDxUxLxbDxDx bxUDxLDkk )()1()1()(1()(),kkxB xf 思想：思想：修正修正Gauss-Se

32、idel迭代法迭代法11() ()BDLDU ALDI1)( 设已知设已知 及已计算及已计算 的分量的分量 )(kx)1(kx).1,2, 1()1(ijxkj (1) 首先用首先用Gauss-Seidel迭代法迭代法定义辅助量定义辅助量 ,)1(kix (2) 再由再由 与与 加权平均定义加权平均定义 ，)(kix)1(kix)1(kix 其中其中 为为松弛因子松弛因子. 0数值分析数值分析35解解 的逐次超松弛迭代法的逐次超松弛迭代法(Successive Over Relaxation） bAx ,2,1 ,0,)()1()0(kfxLxxkk ），（ 初初始始向向量量其中其中 ),)1

33、()(1UDLDL.)(1bLDf解解 的的SOR方法的分量计算公式方法的分量计算公式 bAx ,),()0()0(1)0(Tnxxx,/)(11)1()()1(iinijkjijijkjijikikiaxaxabxx .为松弛因子 ), 1 , 0;, 1( kni注注(1) 当当 时，时，SOR方法即为方法即为Gauss-Seidel迭代法迭代法. 1 (2) 每迭代一次主要运算量是计算一次矩阵与向量的乘法每迭代一次主要运算量是计算一次矩阵与向量的乘法. (3) ，称为超松弛法；，称为超松弛法； 时，称为低松弛法时，称为低松弛法. 11数值分析数值分析36例例 用用SOR方法解方程组方法解

34、方程组,111141111411114111144321 xxxx 精确解为精确解为 .)1, 1, 1, 1(*Tx 取取 ，0)0(x ;4/ )41()(4)(3)(2)(1)(1)1(1kkkkkkxxxxxx ;4/ )41()(4)(3)(2)1(1)(2)1(2kkkkkkxxxxxx ;4/ )41()(4)(3)1(2)1(1)(3)1(3kkkkkkxxxxxx . 4/ )41()(4)1(3)1(2)1(1)(4)1(4kkkkkkxxxxxx 解解取取 ，3.1,)999999120,999999530,000003101,999996460()11(T.x .1046.052)11( 第第1111次迭代结果为次迭代结果为 迭代公式为迭代公式为数值分析数值分析3755223210101 0221 5171 1171 6231 2121 7331 3111 8531 4141 9109( )( )*.kkxxxx 表表满满足足误误差差满满足足误误差差松松弛弛因因子子松松弛弛因因子子的的迭迭代代次次数数的的迭迭代代次次数数最最少少迭迭代代次次数数() 总结：总结：松弛因子选择得好，会使松弛因子选择得好，会使SOR迭代法的迭