迭代法的收斂性與穩(wěn)定性ppt課件1迭代法的收斂性與穩(wěn)定性ppt課件2插值法主講教師：劉春鳳線性方程組的迭代解法第六章插值法主講教師：劉春鳳線性方程組的迭代解法第六章3五、迭代法的收斂性與穩(wěn)定性一階定常迭代法的基本定理關(guān)于解某些特殊方程組迭代法的收斂性五、迭代法的收斂性與穩(wěn)定性一階定常迭代法的基本定理關(guān)于解4迭代法的收斂性與穩(wěn)定性

一階定常迭代法的基本定理常用結(jié)論設(shè)為階方陣的特征值，的譜半徑定義為：的譜定義為：事實(shí)上：對的及特征向量由的任意性：當(dāng)對稱時，矩陣的譜半徑由的任意性迭代法的收斂性與穩(wěn)定性一階定常迭代法的基本定理常5迭代法的收斂性與穩(wěn)定性

一階定常迭代法的基本定理設(shè)線性方程組其中為非奇異矩陣，記為精確解，且設(shè)有等價的方程組于是設(shè)有解的一階定常迭代法迭代法的收斂性與穩(wěn)定性一階定常迭代法的基本定理設(shè)6迭代法的收斂性與穩(wěn)定性

一階定常迭代法的基本定理有意義的問題是：迭代矩陣

滿足什么條件時，由迭代法產(chǎn)生的向量序列

收斂到

.誤差向量的遞推公式引進(jìn)誤差向量由(3.3)式減(3.2)得到

研究迭代法(3.3)收斂性問題就是要研究迭代矩陣滿足什么條件時，有迭代法的收斂性與穩(wěn)定性一階定常迭代法的基本定理7迭代法的收斂性與穩(wěn)定性

一階定常迭代法的基本定理定義設(shè)有矩陣序列及，如果個數(shù)列極限存在且有，則稱收斂于記為

其中||·||為矩陣的任意一種算子范數(shù).都有定理1定理2迭代法的收斂性與穩(wěn)定性一階定常迭代法的基本定理定8迭代法的收斂性與穩(wěn)定性

一階定常迭代法的基本定理例3設(shè)有矩陣序列

，其中而且設(shè)，考查矩陣序列極限.解析顯然,當(dāng)時,則有迭代法的收斂性與穩(wěn)定性一階定常迭代法的基本定理例9迭代法的收斂性與穩(wěn)定性

一階定常迭代法的基本定理設(shè)，則（零矩陣）的充要條件：證明必要性充分性若，則對必存在一種范數(shù)，使得而，于是定理3即迭代法的收斂性與穩(wěn)定性一階定常迭代法的基本定理設(shè)10迭代法的收斂性與穩(wěn)定性

一階定常迭代法的基本定理證明迭代法基本原理設(shè)有方程組及一階定常迭代法對任意選取初始向量，迭代法收斂的充要條件是定理4迭代法的收斂性與穩(wěn)定性一階定常迭代法的基本定理證11迭代法的收斂性與穩(wěn)定性

一階定常迭代法的基本定理定理3和定理4的結(jié)論和起來即為(1)迭代法收斂(2)迭代法收斂推論設(shè)，其中為非奇異矩陣且為非奇異矩陣則有(1)Jacobi迭代法收斂，其中(2)G-S迭代法收斂，其中(3)SOR迭代法收斂，其中迭代法的收斂性與穩(wěn)定性一階定常迭代法的基本定理12迭代法的收斂性與穩(wěn)定性

一階定常迭代法的基本定理例4考察用Jacobi方法解方程組的收斂性.解析因?yàn)榉匠探M的矩陣

及迭代矩陣為得迭代矩陣

的特征方程為解得迭代法的收斂性與穩(wěn)定性一階定常迭代法的基本定理例13迭代法的收斂性與穩(wěn)定性

一階定常迭代法的基本定理例4考察用Jacobi方法解方程組的收斂性.解析解得即所以用Jacobi方法解方程組是收斂的.迭代法的收斂性與穩(wěn)定性一階定常迭代法的基本定理例14迭代法的收斂性與穩(wěn)定性

一階定常迭代法的基本定理例5解析考察用迭代法解方程組的收斂性.其中方程組的迭代矩陣B的特征方程為這說明用迭代法解此方程組不收斂.矩陣B的特征值為，即迭代法的基本定理在理論上是重要的，根據(jù)譜半徑的性質(zhì)，下面利用矩陣的范數(shù)建立判別迭代法收斂的充分條件.迭代法的收斂性與穩(wěn)定性一階定常迭代法的基本定理例15迭代法的收斂性與穩(wěn)定性

一階定常迭代法的基本定理(迭代法收斂的充分條件)定理5及一階定常迭代法設(shè)有方程組如果有

的某種算子范數(shù)，則迭代法收斂，即對任取有且迭代法的收斂性與穩(wěn)定性一階定常迭代法的基本定理(16迭代法的收斂性與穩(wěn)定性

一階定常迭代法的基本定理證明(1)由基本定理4結(jié)論(1)是顯然的.(2)顯然有關(guān)系式及反復(fù)利用(b)即得(2).于是有(3)考查即得迭代法的收斂性與穩(wěn)定性一階定常迭代法的基本定理證17迭代法的收斂性與穩(wěn)定性

一階定常迭代法的基本定理證明

(4)利用(3)的結(jié)果反復(fù)利用(a)，則得到(4).即迭代法的收斂性與穩(wěn)定性一階定常迭代法的基本定理證18迭代法的收斂性與穩(wěn)定性

關(guān)于解某些特殊方程組迭代法的收斂性在科學(xué)及工程計(jì)算中，要求解方程組，其矩陣常常具有某些特性.例如，具有對角占優(yōu)性質(zhì)或

為不可約陣，或

是對稱正定陣，下面討論用基本迭代法解這些方程組的收斂性.定義(1)如果A的元素滿足稱A為嚴(yán)格(按行)對角占優(yōu)陣.對角占優(yōu)陣設(shè)

(2)如果A的元素滿足且上式至少有一個不等式成立，稱A為弱(按行)對角占優(yōu)陣.迭代法的收斂性與穩(wěn)定性關(guān)于解某些特殊方程組迭代法19迭代法的收斂性與穩(wěn)定性

關(guān)于解某些特殊方程組迭代法的收斂性定義可約與不可約矩陣設(shè)，如果存在置換陣P使其中為

階方陣，為

階方陣，則稱

為可約矩陣.否則，如果不存在這樣置換陣

使上式成立，則稱

為不可約矩陣.為可約矩陣意即

可經(jīng)過若干行列重排化為上式或

可化為兩個低階方程組求解(如果

經(jīng)過兩行交換的同時進(jìn)行相應(yīng)兩列的交換，稱對

進(jìn)行一次行列重排).迭代法的收斂性與穩(wěn)定性關(guān)于解某些特殊方程組迭代法20迭代法的收斂性與穩(wěn)定性

關(guān)于解某些特殊方程組迭代法的收斂性事實(shí)上，由

可化為，且記其中為維向量。于是，求解

化為求解由上式第2個方程組求出

,再代入第1個方程組求出

.顯然，如果所有元素都非零，則

為不可約陣.迭代法的收斂性與穩(wěn)定性關(guān)于解某些特殊方程組迭代法21

(對角占優(yōu)定理)

如果A=(aij)n×n為嚴(yán)格對角占優(yōu)矩陣或A為不可約弱對角占優(yōu)矩陣，則A為非奇異矩陣.迭代法的收斂性與穩(wěn)定性關(guān)于解某些特殊方程組迭代法的收斂性定理6證明只就A為嚴(yán)格對角占優(yōu)矩陣證明此定理.采用反證法，如果det(A)=0，則Ax=0有非零解，記為，則由齊次方程組第k個方程則有即這與假設(shè)矛盾，故det(A)≠0.(對角占優(yōu)定理)22迭代法的收斂性與穩(wěn)定性關(guān)于解某些特殊方程組迭代法的收斂性設(shè)方程組Ax=b，如果

(1)A為嚴(yán)格對角占優(yōu)陣，則解Ax=b的Jacobi迭代法,Gauss-Seidel

迭代法均收斂.

(2)A為弱對角占優(yōu)陣，且A為不可約矩陣,則解Ax=b的Jacobi迭代法,Gauss-Seidel迭代法均收斂.定理7證明只證(1)，(2)作為練習(xí)因?yàn)锳是嚴(yán)格對角占優(yōu)陣，所以Jacobi迭代陣則||J||

<1，所以Jacobi迭代法收斂.迭代法的收斂性與穩(wěn)定性關(guān)于解某些特殊方程組迭代法的收斂性設(shè)方23迭代法的收斂性與穩(wěn)定性關(guān)于解某些特殊方程組迭代法的收斂性下面證明Gauss—Seidel

迭代法收斂.下面證明|

|<1.若不然,即|

|1,則由于所以由，得迭代法的收斂性與穩(wěn)定性關(guān)于解某些特殊方程組迭代法的收斂性24迭代法的收斂性與穩(wěn)定性關(guān)于解某些特殊方程組迭代法的收斂性即矩陣是嚴(yán)格對角占優(yōu)矩陣，故可逆，這與(*)式矛盾，所以|

|<1,從而(G)<1，即Gauss—Seidel迭代法收斂.迭代法的收斂性與穩(wěn)定性關(guān)于解某些特殊方程組迭代法的收斂性即矩25迭代法的收斂性與穩(wěn)定性關(guān)于解某些特殊方程組迭代法的收斂性若A為正定矩陣，則方程組Ax=b的Gauss-Seidel迭代法收斂.則內(nèi)積從而

因?yàn)锳正定，所以D正定，故定理證明因?yàn)?，設(shè)

為G

的特征值，y為對應(yīng)的特征(復(fù))向量，即迭代法的收斂性與穩(wěn)定性關(guān)于解某些特殊方程組迭代法的收斂性26迭代法的收斂性與穩(wěn)定性關(guān)于解某些特殊方程組迭代法的收斂性所以|

|<1,從而

(G)<1,故Gauss-Seidel迭代法收斂.下面研究對于解方程組Ax=b的SOR方法中松弛因子ω在什么范圍內(nèi)取值，SOR方法才可能收斂.令，則由復(fù)向量內(nèi)積的性質(zhì)有迭代法的收斂性與穩(wěn)定性關(guān)于解某些特殊方程組迭代法的收斂性所以27迭代法的收斂性與穩(wěn)定性關(guān)于解某些特殊方程組迭代法的收斂性

(SOR方法收斂的必要條件)

設(shè)解方程組Ax=b的SOR迭代法收斂，則0<

<2.定理8證明由于SOR迭代法收斂，則

設(shè)迭代矩陣L

的特征值為

i(i=1,

,n)，則有于是所以|1-

|<1，即

0<

<2.迭代法的收斂性與穩(wěn)定性關(guān)于解某些特殊方程組迭代法的收斂性28迭代法的收斂性與穩(wěn)定性關(guān)于解某些特殊方程組迭代法的收斂性定理8說明解Ax=b的SOR迭代法，只有在(0,2)范圍內(nèi)取松弛因子

，才可能收斂.

(SOR方法收斂的充分條件)

設(shè)有方程組Ax=b，如果：

(2)0<

<2.則解方程組Ax=b的SOR迭代法收斂.在上述假定下，設(shè)迭代矩陣L

的任一特征值為

，只要證明|

|<1即可.定理9

(1)A為對稱正定矩陣，;證明事實(shí)上，設(shè)y為對應(yīng)

的Lω的特征向量，即迭代法的收斂性與穩(wěn)定性關(guān)于解某些特殊方程組迭代法的收斂性定29亦即有內(nèi)積則

因?yàn)锳正定，所以D正定，記迭代法的收斂性與穩(wěn)定性關(guān)于解某些特殊方程組迭代法的收斂性令，則由復(fù)向量內(nèi)積的性質(zhì)有亦即有內(nèi)積則因?yàn)锳正定，所以D正定，記迭代法的收斂性與穩(wěn)定30當(dāng)0<

<2時，有(分子減分母)即L

的任一特征值滿足|

|<1,故SOR迭代法收斂.迭代法的收斂性與穩(wěn)定性關(guān)于解某些特殊方程組迭代法的收斂性因?yàn)楫?dāng)0<<2時，有(分子減分母)即L的任一特征值滿足||31及一階定常迭代法迭代法的收斂性與穩(wěn)定性迭代法的收斂速度則且設(shè)迭代法收斂，即對任取，記

由定理3證明中可知，如果且越小時，迭代法收斂越快.現(xiàn)設(shè)有方程組由基本定理有，且誤差向量滿足及一階定常迭代法迭代法的收斂性與穩(wěn)定性迭代法的收斂速度則且設(shè)32迭代法的收斂性與穩(wěn)定性迭代法的收斂速度故現(xiàn)設(shè)B為對稱矩陣，則有下面確定使初始誤差縮小

所需的迭代次數(shù),即使取對數(shù)，得到所需最少迭代次數(shù)為此式說明，滿足精度所需迭代次數(shù)與成反比，當(dāng)越小，越大，則滿足所需迭代次數(shù)越少，即迭代法收斂越快.迭代法的收斂性與穩(wěn)定性迭代法的收斂速度故現(xiàn)設(shè)B為對稱矩陣33迭代法的收斂性與穩(wěn)定性迭代法的收斂速度

稱為迭代法的漸近收斂速度，簡稱迭代法收斂速度.定義5對于SOR迭代法希望選擇松弛因子

使迭代過程收斂較快，在理論上即確定最佳因子

opt使

對某些特殊類型的矩陣，建立了SOR方法最佳因子理論.