收斂性討論續(xù)課件

1、收斂性討論續(xù) nknnnknnnknknnkkknnkkbxaxaaxbxaxaaxbxaxaax)()()()()()()()()(.1 11 11 11 11 12 22 21 12 21 12 22 21 12 21 11 12 21 12 21 11 11 11 11 11 11 1bDxADIxkk1 11 11 11 1 )()()().矩陣形式：Jacobi Jacobi 迭代格式迭代格式分量形式：).2 2.)()1 13 31 1 ADI 格式收斂條件.1 11 1 ADIULDA bDxULDxkk1 11 11 1 )()()(第六節(jié)收斂性討論第六節(jié)收斂性討論 /* On

2、 Convergence of Iterative methods */收斂性討論續(xù)6 On Convergence of Iterative methods)(11)(1)(414)(313)(21211)1(1bxaxaxaxaaxknnkkkk )(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 2 2）矩陣形式）矩陣形式：bDUxLxDxkk

3、k1 11 11 11 1 )()()()(bLDUxLDxkk1 11 11 1 )()()()(Bg分量形式：)1 11 11 1 )(ULD 3 3）迭代格式收斂條件）迭代格式收斂條件.)(1 11 1 ULD收斂性討論續(xù) nxxxx.,2 21 1 nyyyy.,2 21 1 ininiiiibxaxaay .2 22 21 1nifor, 2 21 1 ? xyyoutputstopyes ,xyN o, nxxxx.,2 21 1 nifor, 2 21 1 ininiiiibxaxaax .2 22 21 1Mk 1 1 kxoutputstopyes ,No1 1 kkJaco

4、bi 迭代格式迭代格式Gauss - Seidel 迭代格式迭代格式收斂性討論續(xù)二種方法都存在二種方法都存在收斂性問題收斂性問題。 有例子表明：有例子表明：Gauss-Seidel法收斂時，法收斂時，Jacobi法可能法可能不收斂；而不收斂；而Jacobi法收斂時，法收斂時， Gauss-Seidel法也可能法也可能不收斂。不收斂。收斂性迭代法求解下面方程組考察用SeidelGaussJacobi .),()(迭代兩次并就初始迭代向量Tx0 00 00 00 0 1 12 22 21 11 12 22 23 32 21 13 32 21 13 32 21 1xxxxxxxxx 1 12 22

5、21 11 11 12 22 21 1A 0 02 22 21 10 01 12 22 20 01 11 1ADIULDB)(6 On Convergence of Iterative methods收斂性討論續(xù) 0 02 22 21 10 01 12 22 20 01 11 1ADIULDB)(.),max(,),max(1 14 43 34 43 31 14 44 42 24 41 1 BB顯然.充分性條件失效2 22 22 20 02 22 20 01 11 12 22 22 22 21 11 12 22 21 11 12 22 22 2 BI0 02 22 22 22 22 23 32

6、 2 )()(0 0 )(B .迭代法收斂Jacobi6 On Convergence of Iterative methods收斂性討論續(xù)?)(1 11 1 ULD 1 12 22 21 11 11 12 22 21 1A 1 12 22 20 01 11 10 00 01 1LD 0 00 00 01 10 00 02 22 20 0U 1 12 20 00 01 11 10 00 01 11 1)(LD 2 20 00 03 32 20 02 22 20 01 1ULDB)(0 02 22 20 00 03 32 20 02 22 22 2 )( BI1 12 2 )(B .發(fā)散Seid

7、elGauss 6 On Convergence of Iterative methods收斂性討論續(xù)!,的收斂性很繁從迭代矩陣討論SeidelGaussJacobi ?,迭代格式的收斂性自身就可以判斷能否直接由系數(shù)矩陣SeidelGaussJacobiA 迭代格式的收斂性！以判斷滿足一定條件時，就可當(dāng)系數(shù)矩陣SeidelGaussJacobiA ,定義（對角占優(yōu)陣）nnijaA )(設(shè)的元素滿足、如果A)(1 1niaaiinijjij, 2 21 11 1 .為嚴(yán)格對角占優(yōu)矩陣稱A的元素滿足、如果A)(2 2niaaiinijjij, 2 21 11 1 立，且至少有一個不等式成.為弱對角

8、占優(yōu)矩陣稱A6 On Convergence of Iterative methods收斂性討論續(xù)）定義（可約與不可約陣使得如果存在置換矩陣設(shè),)(PaAnnij (1) 2222121211110 0AAAAPPT.為可約陣階方陣，則稱為階方陣，為其中ArnArA 22221111.為不可約陣否則，稱A.),式新排列可以化成即對進(jìn)行若干行列的重為可約陣1 1 (A事實上可以化為低階方程求解為可約陣，如果.bAxA bPxPAPPTTT )(bAx TPTP(2) )()()()(2 21 12 21 12 22 21 12 21 11 10 0ddyyAAAbPdT xPyT 6 On Co

9、nvergence of Iterative methods收斂性討論續(xù))()()(1 12 21 12 21 11 11 1byAyA )()(2 22 22 22 2byA .為不可約的情形下面我們只討論A.為不可約矩陣A,的元素都不為零時顯然，A定理：陣為不可約陣弱對角占優(yōu)為嚴(yán)格對角占優(yōu)陣或如果AA.()det(為非奇異矩陣）AA0 0 .)(給出為嚴(yán)格對角占優(yōu)陣情形只對證明A.()det(為奇異矩陣）若AA0 TnxxxxAx),(2 21 10 0 有非零解，記作 xxxxxnk,max2 21 16 On Convergence of Iterative methods收斂性討論續(xù)

10、0 01 1 jnjkjxakkkjnkjjkjxaxa 1 1 nkjjkjkjnkjjkjjnkjjkjkkkkkkaxxaxaxaxa1 11 11 1 nkjjkjkkaa1 1個方程有對于第k6 On Convergence of Iterative methods收斂性討論續(xù)定理：陣為不可約陣弱對角占優(yōu)為嚴(yán)格對角占優(yōu)陣或如果AA0 0 A.)(給出為嚴(yán)格對角占優(yōu)陣情形只對證明A.,迭代都收斂則SeidelGaussJacobi 1 11 11 11 1 )()(ULDULD（，只需證明 不是迭代矩陣的數(shù)于只需證明任意絕對值大 1的特征值！（，)(ULDULD 1 11 1!)(0

11、00 01 11 1 ULDIULDI（，也就是 )()()(ULDLDULDI 1 11 1)()()(ULDLDULDI 1 11 10 01 1 )(LD0 )(ULD 往證6 On Convergence of Iterative methods收斂性討論續(xù) nnnnnnaaaaaaaaaULD 2 21 12 22 22 22 21 11 11 12 21 11 1)(AULD niaaanijijijijii, 2 21 11 11 11 1 nijijijijiiiiaaaa1 11 11 1 nijijijijaa1 11 11 1 .)(det(,)(0 0 ULDULD 嚴(yán)

12、格對角占優(yōu)6 On Convergence of Iterative methods收斂性討論續(xù)定理：證明nL ,2 21 1的特征值為. 2 0 0方法收斂，則的設(shè)SORbAx,)(,1 1 LSOR方法收斂設(shè)nnLL)()det( 2 21 11 12 21 11 1 )()det( LLnnn)det()det()det(UDLDL 1 11 1nL)()det( 1 12 20 01 11 1 6 On Convergence of Iterative methods收斂性討論續(xù)定理：證明.,120 的特征值時往證在L.方法收斂的求解SORbAx 則如果對稱正定，設(shè),2 2 0bAxy

13、yLy 即的特征向量為對應(yīng)于設(shè),yyUDLD )()(1 11 1yLDyUD)()( 1 1),)(),)(yyLDyyUD 1 1),(),(),(),(),(yLyyDyyUyyDyyDy ),(),(),(),(),(yLyyDyyUyyDyyDy 6 On Convergence of Iterative methods收斂性討論續(xù)0 02 21 1 iniiiyayDy),( :顯然 iyLy ),(: 記),(),(),(),(),(yLyyDyyUyyDyyDy TTLUAA ,),(TTTULDAULDA iyLyLyyyyLyUyT ),(),(),(),()()( ii

14、),)()()()(2 21 12 21 12 21 12 22 22 22 22 2zzzzzzzz ( ii )6 On Convergence of Iterative methods收斂性討論續(xù) 2 22 22 22 22 2)()()()( 只需證觀察分子分母,2 2)()( 2 1 2 2 就有2 22 2)()()()( 222 2 2)()( 222 )()( 222 2)2 )(的符號看 2 ),(),(),(),)(),(yUyyLyyDyyyULDyAy 0 00 02 2 ii2 0 01 2 2 6 On Convergence of Iterative method

15、s收斂性討論續(xù)定理：陣為不可約陣弱對角占優(yōu)為嚴(yán)格對角占優(yōu)陣或如果AA略）證明(.方法收斂的時，解則當(dāng)SORbAx 1 10 0 .的情形的特例，是1 1 SORSeidelGaussbAx 求解如果對稱正定由定理知,.方法收斂的SG 6 On Convergence of Iterative methods收斂性討論續(xù)本章重點總結(jié)本章重點總結(jié)bDxULDxkk1 11 11 1 )()()(bDUxLxDxkkk1 11 11 11 1 )()()()(gBxxkk )()(1 1 一般迭代法1 1 )(B SG )2 2 Jacobi)1 1SOR )3 3bLDxUDLDxkk1 11 11 11 1 )()()()