數(shù)值計算方法第講迭代法的收斂性和穩(wěn)定性

1、插 值 法主講教師：劉春鳳8/eol/jpk/course/welcome.jsp?courseId=1220線性方程組的迭代解法主講教師：龔佃選第第 六章六章一階定常迭代法的基本定理關于解某些特殊方程組迭代法的收斂性迭代法的收斂性與穩(wěn)定性 一階定常迭代法的基本定理常用結論 設 為 階方陣的特征值， 的譜半徑定義為： (1,2, )iin n1( )maxii nA AA的譜定義為：12.n， ，kkAA)()( AA )( xxAxAxkk iiiiiiuuAuAu 事實上：對 的 及特征向量Ai iuAi 1( )maxii nAA i 由 的任意性：1

2、( )max.ii nAA 當 對稱時，A2( ).AA 矩陣的譜半徑由 的任意性i 迭代法的收斂性與穩(wěn)定性 一階定常迭代法的基本定理.fBxxbAx 設線性方程組,(3.1)Axb 其中 為非奇異矩陣，記 為()n nijAaR *x(3.1)精確解，且設有等價的方程組于是(3.2)xBxf )3 . 3(.)()1(fBxxkk 設有解 的一階定常迭代法Axb 迭代法的收斂性與穩(wěn)定性 一階定常迭代法的基本定理有意義的問題是：迭代矩陣 滿足什么條件時，由迭代法產(chǎn)生的向量序列 收斂到 .B( )kx*x誤差向量的遞推公式誤差向量的遞推公式)., 2 , 1 , 0(,)0()()()1( kB

3、Bkkkk )., 2 , 1 , 0()()( kxxkk 引進誤差向量由(3.3)式減(3.2)得到 研究迭代法(3.3)收斂性問題就是要研究迭代矩陣 滿足什么條件時，有B).)(0 kBk零零矩矩陣陣迭代法的收斂性與穩(wěn)定性 一階定常迭代法的基本定理定 義設有矩陣序列 及 ，如果( )()kn nkijAaR ()n nkijAaR 2n個數(shù)列極限存在且有( )lim( ,1,2, )kijijkaai jn ，則 稱收斂于kAAlim().k 記為其中|為矩陣的任意一種, 0limlim AAAAkkkk算子范數(shù).limnkkAAxR 都有l(wèi)im.kkA xAx 定理定理1定理定理2迭代

4、法的收斂性與穩(wěn)定性 一階定常迭代法的基本定理例例 3設有矩陣序列 ，其中 而kAkkAB ,0,02,011222 kkkkkBBB 且設 ，考查矩陣序列極限.1 顯然, 當 時, 則有1 .0000limlim kkkkBA迭代法的收斂性與穩(wěn)定性 一階定常迭代法的基本定理設 ，則 （零矩陣）的充要條件： ()ijn nAa lim0kkA 1.A 必要性0lim0lim kkkkAAkkkAAA )()(0 lim ( )0kkA ( )1A 充分性若 ，則對( )1A 1( )12A 必存在一種范數(shù) ，使得.12)(1)( AAA 0lim kkAkkAA 而limlim0kkkkAA ，

5、于是lim0kkA 定理定理3即迭代法的收斂性與穩(wěn)定性 一階定常迭代法的基本定理迭代法基本原理設有方程組 及一階定常迭代法xBxf(1)( )kkxBxf )1.B （對任意選取初始向量 ，迭代法收斂的充要條件是(0)x定理定理40.)0()1()( kkkkBBxx）（xxkk )(lim0lim kk 0lim kkB1)( B )()0()0(xx 迭代法的收斂性與穩(wěn)定性 一階定常迭代法的基本定理 定理3和定理4的結論和起來即為(1)迭代法 收斂(1)( )kkxBxf lim0kB(2)迭代法 收斂(1)( )kkxBxf ( )1.B 推論推論設 ，其中 為非奇異矩陣且 為非奇異矩陣

6、Axb ADLUD則有 (1) Jacobi迭代法收斂 ，其中( )1J 1().JDLU (2) G-S迭代法收斂 ，其中( )1G 1().GDLU (3) SOR迭代法收斂 ，其中()1L 1() (1).LDLDU 迭代法的收斂性與穩(wěn)定性 一階定常迭代法的基本定理例例 4考察用Jacobi方法解方程組 的收斂性.12312312383220,41133,631236.xxxxxxxxx 因為方程組的矩陣 及迭代矩陣 為AJ.012/312/611/1011/48/28/30)(,123611142381 ULDJA得迭代矩陣 的特征方程為J, 0039772727. 003409090

7、9. 0)det(317638833 JI解得,3445. 01841. 0,3445. 01841. 0,3082. 0321ii 迭代法的收斂性與穩(wěn)定性 一階定常迭代法的基本定理例例 4考察用Jacobi方法解方程組 的收斂性.12312312383220,41133,631236.xxxxxxxxx . 13592. 0, 13082. 0321 解得,3445. 01841. 0,3445. 01841. 0,3082. 0321ii 即 所以用Jacobi方法解方程組是收斂的.( )1J 迭代法的收斂性與穩(wěn)定性 一階定常迭代法的基本定理例例 5考察用迭代法解方程組的收斂性. 其中.5

8、5,0320,)()1( fBfBxxkk方程組的迭代矩陣B的特征方程為22det()63IB 這說明用迭代法解此方程組不收斂. 矩陣B的特征值為 ，即1,26 ( )1.B 迭代法的基本定理在理論上是重要的，根據(jù)譜半徑的性質 ，下面利用矩陣 的范數(shù)建立判別迭代法收斂的充分條件.( )BB B迭代法的收斂性與穩(wěn)定性 一階定常迭代法的基本定理(迭代法收斂的充分條件) 定理定理5及一階定常迭代法設有方程組,()n nijxBxf BbR (1)( )kkxBxf 如果有 的某種算子范數(shù) ，則B1Bq 迭代法收斂，即對任取 有(0)x.xBxf ( )limkkxx 且.)2()0()(xxqxxk

9、k .1)3()1()()( kkkxxqqxx.1)4()0()1()(xxqqxxkk (1)迭代法的收斂性與穩(wěn)定性 一階定常迭代法的基本定理(1) 由基本定理4結論(1)是顯然的.(2) 顯然有關系式 及反復利用(b)即得(2). *(1)*( )()kkxxB xx (1)( )( )(1)()kkkkxxB xx于是有(1)( )( )(1)( )kkkkaxxq xx*(1)*( )( )kkbxxq xx (3) 考查(1)( )*( )*(1)()kkkkxxxxxx*( )*(1)kkxxxx *( )(1)kqxx即得 .111)1()()()1()( kkkkkxxqqx

10、xqxx迭代法的收斂性與穩(wěn)定性 一階定常迭代法的基本定理 (4) 利用(3)的結果反復利用(a)，則得到(4). 即 .11)0()1()1()()(xxqqxxqqxxkkkk 迭代法的收斂性與穩(wěn)定性 關于解某些特殊方程組迭代法的收斂性 在科學及工程計算中，要求解方程組 ，其矩陣 常常具有某些特性. 例如， 具有對角占優(yōu)性質或 為不可約陣，或 是對稱正定陣，下面討論用基本迭代法解這些方程組的收斂性.Axb AAAA定 義(1) 如果A的元素滿足)., 2 , 1(1niaanijjijii 稱A為嚴格(按行)對角占優(yōu)陣.對角占優(yōu)陣設()ijn nAa (2) 如果A的元素滿足)., 2 ,

11、1(1niaanijjijii 且上式至少有一個不等式成立，稱A為弱(按行)對角占優(yōu)陣.迭代法的收斂性與穩(wěn)定性 關于解某些特殊方程組迭代法的收斂性定 義可約與不可約矩陣可約與不可約矩陣設(),2ijn nAan ，如果存在置換陣P使1112220TAAP APA 其中 為 階方陣， 為 階方陣 ，則稱 為可約矩陣. 否則，如果不存在這樣置換陣 使上式成立，則稱 為不可約矩陣.11Ar22Anr (1)rnAPA 為可約矩陣意即 可經(jīng)過若干行列重排化為上式或 可化為兩個低階方程組求解(如果 經(jīng)過兩行交換的同時進行相應兩列的交換，稱對 進行一次行列重排).AAAxb AA迭代法的收斂性與穩(wěn)定性 關

12、于解某些特殊方程組迭代法的收斂性 2121,ddbPdyyxPyTT 事實上，由 可化為Axb ()TTTP AP P xP b ，且記其中,iiyd為 維向量。r于是，求解 化為求解Axb .,22221212111dyAdyAyA由上式第2個方程組求出 ,再代入第1個方程組求出 .2y1y 顯然，如果 所有元素都非零，則 為不可約陣.AA (對角占優(yōu)定理) 如果A=(aij)nn為嚴格對角占優(yōu)矩陣或A為不可約弱對角占優(yōu)矩陣，則A為非奇異矩陣.迭代法的收斂性與穩(wěn)定性關于解某些特殊方程組迭代法的收斂性定理定理6 6111|,nnnkkkkjjkjjkkjjjjj kj kj ka xa xax

13、xa只就A為嚴格對角占優(yōu)矩陣證明此定理. 采用反證法，如果det(A)=0，則Ax=0有非零解，記為 ，則12(,)Tnxxxx 1max0kix nxx 由齊次方程組第k個方程, 01 njjijxa則有即,1 nkjjkjkkaa這與假設矛盾，故det(A)0.迭代法的收斂性與穩(wěn)定性關于解某些特殊方程組迭代法的收斂性設方程組Ax=b，如果(1) A為嚴格對角占優(yōu)陣，則解Ax=b的Jacobi迭代法, Gauss-Seidel 迭代法均收斂.(2) A為弱對角占優(yōu)陣，且A為不可約矩陣, 則解Ax=b的Jacobi迭代法, Gauss-Seidel 迭代法均收斂.定理定理7 7只證(1)，(2

14、)作為練習因為A是嚴格對角占優(yōu)陣，所以0(1, )iiainJacobi迭代陣)(1ULDJ 0002122222211111112nnnnnnnnaaaaaaaaaaaa則|J| 1，所以 Jacobi 迭代法收斂.迭代法的收斂性與穩(wěn)定性關于解某些特殊方程組迭代法的收斂性)(det)det(1ULDIGI . 0)(det)det(1 ULDLD )(. 0)(det ULD 下面證明GaussSeidel 迭代法收斂.下面證明|1. 若不然, 即|1, 則. ),2, 1(|111 ijnijijijijijiiniaaaa 由于. 0)det(1 LD所以由 ，得1()GD L U 迭代

15、法的收斂性與穩(wěn)定性關于解某些特殊方程組迭代法的收斂性. ), 2 , 1(|111 ijnijijijijijiiniaaaa 即矩陣 ULD)( 是嚴格對角占優(yōu)矩陣，故可逆，這與(*) 式矛盾，所以|1, 從而 (G)1，即GaussSeidel迭代法收斂.212222111211 nnnnnnaaaaaaaaa 迭代法的收斂性與穩(wěn)定性關于解某些特殊方程組迭代法的收斂性若A為正定矩陣，則方程組 Ax=b的Gauss-Seidel 迭代法收斂. .),(),(),(yLyyDyyyLT 則內積從而 因為A正定，所以D正定，故定理定理1(),()TTD LL yyL yD L y (, )()

16、, )TL y yDL y y 因為 ，設為G 的特征值，y為對應的特征(復)向量，即1,()TTA D L L GD L L (, )0Dy y 迭代法的收斂性與穩(wěn)定性關于解某些特殊方程組迭代法的收斂性).(),(),(),(ibayLyLyyyyLT 所以|1, 從而(G)1, 故Gauss-Seidel迭代法收斂.1)(|22222 baba .)(),(),(),(ibaibayLyyDyyyLT 下面研究對于解方程組Ax=b的SOR方法中松弛因子在什么范圍內取值，SOR方法才可能收斂. 令 ，則由復向量內積的性質有(, )Ly yaib迭代法的收斂性與穩(wěn)定性關于解某些特殊方程組迭代法

17、的收斂性(SOR方法收斂的必要條件) 設解方程組 Ax=b的SOR迭代法收斂，則02.定理定理8 8 由于SOR迭代法收斂，則 設迭代矩陣L的特征值為i (i=1,n)，則有1,() (1)A D L U LDLDU ()1L 12det() | ()1nnLB . 1)1()1()()1det()det()det(1111 nniiiniiiaaUDLDL 于是所以|1-|1，即 02.迭代法的收斂性與穩(wěn)定性關于解某些特殊方程組迭代法的收斂性定理8說明解Ax=b的SOR迭代法，只有在(0, 2)范圍內取松弛因子，才可能收斂.(SOR方法收斂的充分條件) 設有方程組 Ax=b，如果：(2) 0

18、2.則解方程組 Ax=b的SOR迭代法收斂. 在上述假定下，設迭代矩陣L的任一特征值為，只要證明|1即可. 定理定理9 9(1) A為對稱正定矩陣， ;TA D L L 事實上，設y為對應的L的特征向量，即, 0),(,21 TnyyyyyyL ,)1()(1yyLDLDT 亦即.)()1(yLDyLDT 有內積),)(),)1(yyLDyyLDT 則,),(),(),(),(),(yLyyDyyyLyDyyDyT 因為A正定，所以D正定，記).(),(),(),(ibayLyLyyyyLT 迭代法的收斂性與穩(wěn)定性關于解某些特殊方程組迭代法的收斂性(, )0Dy y 令 ，則由復向量內積的性質

19、有(, )Ly ya ib 0(, )() , )2 ,TAy yDLL y ya .)()(biabia (,)(,)(,)(,)(,)TDy yDy yL y yDy yLy y .)()(2222222baba 當02時，有(分子減分母). 0)2)(2()()(22 aaa即L的任一特征值滿足|1, 故SOR迭代法收斂.迭代法的收斂性與穩(wěn)定性關于解某些特殊方程組迭代法的收斂性因為及一階定常迭代法迭代法的收斂性與穩(wěn)定性迭代法的收斂速度()lim,.kkxxxBxf 則且設迭代法收斂，即對任取 ，記0 x由定理3證明中可知，如果 且 越小時，迭代法收斂越快. 現(xiàn)設有方程組( )1B ( )

20、B 由基本定理有 ，且誤差向量 滿足0( )1B ( )( )*kkxx ( )(0)kkB (1)( )(0,1,)kkxBxfk ,()n nijxBxfBbR 迭代法的收斂性與穩(wěn)定性迭代法的收斂速度故()( 0 ).kkB 現(xiàn)設B為對稱矩陣，則有()( 0 )( 0 )2222().kkkBB 下面確定使初始誤差縮小 所需的迭代次數(shù), 即使10s .10)(skB 取對數(shù)，得到所需最少迭代次數(shù)為.)(ln10lnBsk 此式說明，滿足精度所需迭代次數(shù)與 成反比，當 越小， 越大，則滿足所需迭代次數(shù)越少，即迭代法收斂越快. ( )1B ln( )RB ln( )RB 迭代法的收斂性與穩(wěn)定性

21、迭代法的收斂速度 稱 為迭代法 的漸近收斂速度，簡稱迭代法收斂速度.定義定義 5ln( )RB (1)( )(0,1,)kkxBxfk 對于SOR迭代法希望選擇松弛因子 使迭代過程收斂較快，在理論上即確定最佳因子opt使).()(min20optLL 對某些特殊類型的矩陣，建立了SOR方法最佳因子理論. 例如，對所謂具有“性質A”等條件的線性方程組建立了最佳松弛因子公式.)(1122Jopt 其中 為解 的Jacobi迭代法的迭代矩陣的譜半徑.( )J Axb 迭代法的收斂性與穩(wěn)定性迭代法的收斂速度 若Jacobi 迭代矩陣J 為非負矩陣，則下列關系有一個且僅有一個成立： (1) (J)= (G)=0； (2) 0 (G) (J)1；(3) (J)= (G)=1； (4) 1 (J) (G).說明：當Jacobi 迭代矩陣J為非負矩陣時, Jacobi方法和 GaussSeidel 方法同時收斂或同時發(fā)散, 若為同時收斂, 則后者比前者收斂快.迭代法的收斂性與穩(wěn)定性迭代法的收斂速度已知方程組.9.08.07.015.005.015.005.01321 xxx判斷雅可比迭代法