第五章解线性方程组的迭代法课件.ppt

1、数值分析 主讲教师1第五章 解线性方程组的迭代法 线性方程组虽有直接解法，但对大型组，对时间和空间要求严格。数值分析 主讲教师2第五章 解线性方程组的迭代法n 5.1 迭代法及其收敛性迭代法及其收敛性 n 5.2 向向量和矩阵的范数量和矩阵的范数n 5.3 迭迭代过程的收敛性代过程的收敛性数值分析 主讲教师35.2 向量和矩阵的范数向量范数向量范数(vector norms)的范数。为向量则称实数三角不等式有）对于任意向量及任意向量对于任意实数时，当且仅当）任意满足：如果实数任意向量xxyxyxyxxxxxxxxxxxxxn)(,3,)2.00,0,1,21数值分析 主讲教师4/p111/21

2、12211:max21nippinininiiiixxpxxxxxx范数一般的，定义范数范数范数常见范数：数值分析 主讲教师5范数的等价性：等价，定理：具有传递性。显然，范数的等价关系均有使对任意向量等价，如果存在正数称范数212121,pqqpqpxcxxcxxcc数值分析 主讲教师6向量序列的极限使如果存在中的向量序列定义：设,),(,),(,1)()(1)(0)(nTnTknkkknRxxxxxxxR,2,1,lim)(nixxikik。对矩阵类似定义。记作收敛于则称向量序列xxxxkkk )()(limlim,0显然有：()()limlim0kkkkxxxx（依分量收敛）（依范数 收敛

3、）数值分析 主讲教师7矩阵范数、谱半径111111A,AmaxAmax(A)=maxAA(A)A,A(A)ijn nniji njnijj nijjj npaaap 对于方阵有矩阵的行范数矩阵的列范数称为 的谱半径，其中为 的特征向量定理：1）为任意范数。2）存在某个矩阵范数数值分析 主讲教师8 j()()()()()()()()()k()()jj()1lim0lim0,:,lim0lim00lim0 x e,limelimA0,j0j=1,2,nlim0.kknkkkkkkkkkkkkkkkkkkAAxxRAxAxAAAxAxAxAAA 命题的充分必要条件是。证 对任意从属范数有由，知，因此

4、由，得到。反之，取=则即的 列元素为，则数值分析 主讲教师9为谱半径。其中命题)(,1)A(0Alim2kk证明:由范数等价性,仅就某一从属范数证明即可.lim00,()()0(1,)()1()1,()1,limlim0.(1,2)kkkkkAAkkkAAAAAA xxAAAAAA 而或按命题 考虑其中 为特征向量由知，使而对此，存在某种从属范数，使故命题通常结合起来用数值分析 主讲教师10命题3 对任意从属范数有：)(limlimBBkkk 1性保证命题成立。次方根便可，范数等价再两边满足：范数证明：对kBBBBBkkkkk )()()()(,0见数值计算原理，李庆扬，关治P193数值分析

5、主讲教师115.1 迭代法的构造及收敛称为迭代矩阵。其中并由此构造迭代公式，改写为不动点形式造迭代序列，可将方程，首先要构程组非奇异，用迭代法解方设nnkknnRBkfBxxfBxxbAxRA ,)()(101则称迭代法收敛的。满足生成的序列定义：若迭代法nkkkkkRxxxxkfBxx)0(*)()()()1(,lim,1,0,数值分析 主讲教师12 12321312123123123k+1kkk+1kkk+1kk+1kk38x3x2x2014x11xx336x3x12x361x(3x2x20)81x(-4xx33)xBxf,111x(-6x3x36)123108441B=0f1111110

6、24例 解可构造如下迭代 ，即这里，-，-010503.000032323,x0,x1.99983802300.9998031 若取则数值分析 主讲教师135.1.1 迭代法的收敛性(1)()(0),0,1,()1()B,1kknxBxf kxRBBB迭代收敛基本定理：迭代法对收敛，其中为矩阵 的谱半径。存在某种范数使得数值分析 主讲教师14()*(0)()()*k 1*(0)(0)(),0,12()1;kkkkxx kxxBxfxfxxBxfBxfBxB 证明：设则 满足此时对由于任意,故由命题，知：),(,)()(,limlim,)()()(*)()(*fxBxxfBxxxfxBIBIBB

7、BBkkkkk00010211 对此时即有唯一解，记为可逆，从而表明且知存在某范数使，由命题设 数值分析 主讲教师15 32 1.3108441:B=0,11111102437:I-B0,B0.35921,.881763:B1,BB1,.4例 考察例 迭代法的收敛性解-方法一迭代收敛方法二因此迭代收敛数值分析 主讲教师16*()()(1)(1)(0)1,11(B1.1,)kkkkBqqqxxxxxxqqBB推论（收敛速度与误差估计）若对某种从属范数，迭代阵满足则迭代法收敛，且有估计：反之不成立，即收敛不能但至少能找到一种范数成立.数值分析 主讲教师17)()()()(*)(*)()()(*)(

8、)()(*)()()(*)(*10111111111xxqqxxqxxxxBxxxxxxxxxxxxxkkkkkkkkkkkkkk 同时有：收敛性已由定理给出。的存在性及迭代序列的证明：数值分析 主讲教师18120.9030.30.81.1,1.2,1.043,1.541()0.91,FBBBBBBB例：有迭代矩阵则虽然 的这些范数均大于，但由于故由定理知迭代序列仍收敛。数值分析 主讲教师195.1.2 迭代法的收敛速度()()*(0)111()1,ln,lnln()kkkkkkkkkkBkxxBBkBkBkB 设迭代法收敛，即经过 步迭代后的误差可估计为：这样平均每次迭代后误差的压缩率可看成

9、是由决定。通常对给定的 步压缩量，若要求，这说明为达到一定的压缩量要求的最小迭代次数反比于类似于时间反比于速度。数值分析 主讲教师201(1)()()limlnln()kkkkkR BBBxBxf 定义：称为迭代法的渐近收敛速度。步的平均收敛速度。称为迭代法迭代定义：kBBRkkk1lnln)(该定义依赖于范数的选取和迭代次数，为刻画方法本身的速度，引入仅与迭代阵有关的量：数值分析 主讲教师21 1()(0)-51()32BlnBln1010.()4 110,sln10sln101B0.3592,k11.99,k=12.R B-lnBkkksBBskR B注定义中是命题 的结果；注可以推知，越

10、小,渐进收敛速度-越大。且当时有：例若例 中要球相对误差小于则至少要迭代几次?解:例 中故数值分析 主讲教师225.3 Jacobi迭代法和Gauss-Seidel迭代法n5.3.1 Jacobi迭代法n5.3.2 Gauss-Seidel迭代法n5.3.3 J法与GS法的收敛性数值分析 主讲教师235.3.1 Jacobi迭代法nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111设有方程组作等价变形，得不动点形式：数值分析 主讲教师245.3.1 Jacobi迭代法 )()()(nnnnnnnnnnnbxxaxaaxbxaxxaaxbxaxa

11、xax0101012211222121222112121111fBxx 即数值分析 主讲教师255.3.1 Jacobi迭代法可构造迭代公式：)()()()()()()()()()()()()()()(nknknknnnknknnkkkknnkkkbxxaxaaxbxaxxaaxbxaxaxax0101012211122212122121121211111数值分析 主讲教师265.3.1 Jacobi迭代法););()(ADiagDULDARaAnnij 分解为：这里是把系数矩阵 0000000021122121nnnnaaaUaaaL,数值分析 主讲教师275.3.1 Jacobi迭代法非奇

12、异，则得：，则假定的严格上三角矩阵。的严格下三角矩阵与分别为DniaAAULii),(,210 ,)()(101 kfBxxkk11111(),1B=,BDLUID A fD bJacobiJID A fD b 其中称为解方程组的迭代法，简称 法。例:验证上节例 中。定理 Jacobi迭代法收敛的充分必要条件是 1I-D A1数值分析 主讲教师285.3.1 Jacobi迭代法:形式计算时可写成如下分量nibxaxaaxinijkjijijkjijiiki,),),()()()(2111111 ,21 k数值分析 主讲教师295.3.2 Gauss-Seidel迭代法法变成如下迭代公式：值，则

13、如果将这些新值代替旧均已算出，步迭代值个值的前面时，到在计算法的计算公式中，注意在JxxkixJkikki)()()(,1111111 nibxaxaaxinijkjijijkjijiiki,),),()()()(21111111 法。迭代法，简称称为GSSeidelGauss 数值分析 主讲教师305.3.2 Gauss-Seidel迭代法法矩阵表示：GS。充分条件是对某种范数的谱半径是迭代矩阵法收敛的充分必要条件定理：11 GGGGS,)(1)()(1)()111,()(),().1GS.kkkkGGDL xUxbGSxGxfGDLUIDLA fDLb 又可由上式得到于是可表示为：便于讨论

14、收敛性其中例写出上节例 的迭代公式 ;)()()(便于迭代的形式 bUxLxDxkkk111数值分析 主讲教师31注1：当然可有其他的迭代法如:bxAIxkk )()()(1注2：在收敛的情况下，一般说来，Gs法的收敛性能较J法好，然而情况并不总是如此，存在方程组按J法收敛，而按Gs法不然，因此两种方法均很重要，如组：1111111221112210)(,xbA数值分析 主讲教师325.3.3 J法与GS法的收敛性讨论方程组J法及GS法的收敛性，除用收敛基本定理外，还可直接由给定的系数矩阵A来判断收敛性（代数判据），为此先给出定义：满足：若定义nnijRaA)(1为弱对角占优矩阵。称等式成立则

15、式中至少有一个严格不格对角占优矩阵；若上为严立，则称，上面的严格不等式成若对所有AniA21,1412,1,2,:A=140141niiijjj iaain如数值分析 主讲教师335.3.3 J法与GS法的收敛性使若存在排列矩阵：假定定义,2,2nnnnRPnRA2212110AAAAPPT不可约。否则称可约，则称其中AAnrRARArnrnrr)(,)()(12211A可约的代数意义是通过行列的相应调换化为解耦方程组。数值分析 主讲教师345.3.3 J法与GS法的收敛性法均收敛。法和非奇异，对角占优矩阵，则：不可约弱为严格对角占优矩阵或定理：若GSJiiAniaiRaAiinnij)(;)

16、,()()(10 说明：此定理实际含有四个命题。数值分析 主讲教师35证明（严格对角占优时的J法收敛性）：110max1()34 2p62iiijij iiiaaJID AaIID AAJ直接由条件得知；对 法，考虑所以可逆，故 可逆，同时说明 法收敛。(.定理)数值分析 主讲教师36证明（严格对角占优时的GS法收敛性）：.1yaa1aayaayaayy),n,1i(xaayaay,UxDLyDy,Gxy,GxmaxG,ULDGGS1k1jkkkjn1kjkkkjn1kjkkkj1k1jkkkjkn1ijjiiij1i1jjiiiji111x1整理并利用对角占优得得：两边取模并用范数放大写成分

17、量形式有：则有记并考虑）（法的迭代阵考虑数值分析 主讲教师37（不可约弱对角占优时的J法收敛性）可逆，矛盾！仍为弱对角占优的，故且零元素位置相同）（有相同的不可约性与另方面；此时由有某特征值反设迭代矩阵。否则就有零行而可约致不可约且弱对角占优导首先DADADADDADBIBaAii 0010,)(数值分析 主讲教师38（不可约弱对角占优时的GS法收敛性）法收敛。，故）（，矛盾。这就表明），角占优（故仍应是不可约且弱对同，的零元位置与另方面，由于：此时关于特征方程应有法发散，从而，满足即有特征根反设这里事实上只须证明GSBULDULDULDULDULDLDULDIGSBULDAULDBB1011

18、1010111111 )det(det()det(det()(det(det()det(det()(det(det(,)(.,)(,)(数值分析 主讲教师395.3.3 J法与GS法的收敛性对称正定，则定理：若nnijRaA )(法也收敛。也对称正定，则若迭代收敛定理的特例后面法收敛。的解方程组JADSORbAx 22GS1)()(数值分析 主讲教师405.4 逐次超松弛迭代法n5.4.1 SOR迭代公式n5.4.2 SOR迭代法收敛性数值分析 主讲教师415.4.1 SOR迭代公式nixaxabaxGSnijkjijijkjijiiiki,),),()()()(21111111 法：回顾 逐

19、次超松弛(Successive Over Relaxation)迭代法，简称SOR迭代法，它是在GS法基础上为提高收敛速度，采用加权平均而得到的新算法。加权和得：与上式对)()(1 kikixxnixxxkikiki,)()()()(21111 数值分析 主讲教师425.4.1 SOR迭代公式nixaxabaxxGSnijkjijijkjijiiikiki,),),()()()()()(211011111 法得：称为松弛参数，代入这里法。时即为当称为松弛因子。迭代法，称为GSSOR10 数值分析 主讲教师435.4.1 SOR迭代公式阵形式：迭代法的便于迭代的矩SORbLDfUDLDGfxGx

20、SORbxUDxLDkkkk111111 )()()()()()()()()(其中：矩阵表示：法的便于讨论收敛性的从而得合并有关项得：)()()()()()(kkkkUxLxbDxx 1111 数值分析 主讲教师44法：从而得到法进行加权和，法，可利用注：仿照JORJacobiSOR bDxADIxxxxkkkkk111111 )()()()()()()()(数值分析 主讲教师451234302434130014241()1.24xxxGS例：设有方程组，分别取法 和（最优因子）迭代公式。(1)()()112(1)()(1)()2213(1)()(1)332(1)(243)4(1)(303)4

21、(1)(24)4kkkkkkkkkkSORxxxxxxxxxx迭代公式为：数值分析 主讲教师46 k+1k12k+1k+1k213k+1k+132k+1kk112k+1kk+1k2213k+1kk+1332k 11x243x411GSx303xx41x-24x41.24x0.24x243x41.241.24SORx0.24x303xx41.24x0.24x-24x4JacobixB 得迭代公式：得迭代公式：法:k3004631xf,B=0f7.5.4461004其中，数值分析 主讲教师475.4.2 SOR迭代法收敛性。收敛的充分条件是仍为法收敛的充分必要条件，根据迭代法收敛性定理11 GGS

22、OR,)(是非常必要的。寻找收敛性的代数判据）较复杂，因此（和但计算 GG数值分析 主讲教师48。迭代法收敛，则的且解方程定理：设20210 SORbAxniaRaAiinnij),),(,)(11111112121111nnnninGGGUDILDIG再由收敛性得得：的特征值，由韦达定理为若记知证明：由detdet必要条件（逆否定理）数值分析 主讲教师495.4.2 SOR迭代法收敛性002n nnARAxbSORxR定理：若对称正定，且，则解的迭代法对迭代法收敛。(充分条件)分析：即讨论谱半径。0 ),(););,(),(),(););,(),(;),(),(xxzyzxzyxyxyxxy

23、yx 复内积：预备知识数值分析 主讲教师50 .,),)(),()()()()()()()()()()()()(),(),(),()(:)(102221111011222222211111 结合上式知而此时便有：和记意味着意到对上式两边作内积并注应满足的特征向量迭代矩阵pxxUDLxAxppppppipipipippxDxixUxxLxULxLDIxUDIxUDILDIGSORT证明：数值分析 主讲教师515.4.2 SOR迭代法收敛性为法的最优松弛因子则记法迭代矩阵，若的是解方程阵，为对称正定的三对角矩定理：设bJJJnnSORBBJbAxBRA ),),(,)(12112b2014/)1(4)(222bbG且.)(问题弛因子有关，故应讨论最优松与由于bG 数值分析 主讲教师52推论及其他有关结果。其速度；法有：推论：关于)()(lnln)(lnln)()()(JJBRBGGRGGGS2221 正定。时松弛法收敛则对称（或共轭对称）且）若（松弛法收敛。则对不可约且弱对角占优，）若（有关结果：AaAAii 2002101 ,