數(shù)值計(jì)算方法課件：第二章-解線性方程組的迭代法

第二章解線性方程組的迭代法第二章解線性方程組的迭代法2.3Jacobi方法與Gauss-Seidel方法22.3Jacobi方法與Gauss-Seidel方法2一般迭代法的求解步驟依據(jù)方程組分離x得到迭代格式判斷迭代格式是否收斂迭代求解滿足終止條件,迭代結(jié)束3一般迭代法的求解步驟依據(jù)方程組分離x32.3.1Jacobi方法考慮方程組

Ax=b

(2.3.1)其中是非奇異的,為已知向量.將矩陣A寫成如下

A=D-L-U(2.3.2)其中為對(duì)角陣,-L,-U分別為A的嚴(yán)格下,上三角部分構(gòu)成的三角陣42.3.1Jacobi方法考慮方程組455當(dāng)D非奇異,即aii≠0(i=1,2,…,n)時(shí),利用(2.3.2)式,可將方程組(2.3.1)寫成于是可得迭代格式稱此格式為求解方程組(2.3.1)的Jacobi迭代法.注意到L+U=D-A,故(2.3.3)式也可寫成(2.3.3)(2.3.4)6當(dāng)D非奇異,即aii≠0(i=1,2,…,n)時(shí),利用(2.Jacobi方法的迭代矩陣為Jacobi迭代法(2.3.4)式的分量形式為(2.3.6)7Jacobi方法的迭代矩陣為(2.3.6)7例2.1用Jacobi方法解方程組8例2.1用Jacobi方法解方程組82.3.2Gauss-Seidel方法簡(jiǎn)單迭代法(2.2.3)的分量形式是可以用這些新值來計(jì)算,于是可得迭代格式這種方法稱為Seidel迭代法.(2.3.7)92.3.2Gauss-Seidel方法簡(jiǎn)單迭代法(2.2.對(duì)Jacobi迭代(2.3.6)式運(yùn)用Seidel技巧得到稱(2.3.9)式為Gauss-Seidel迭代法,其矩陣形式為并可整理成一般迭代法的形式(2.3.9)(2.3.10)10對(duì)Jacobi迭代(2.3.6)式運(yùn)用Seidel技巧得到(例2.1用Jacobi和Gauss-Seidel方法解方程組11例2.1用Jacobi和Gauss-Seidel方法解方程小結(jié)12小結(jié)12小結(jié)Jacobi迭代法迭代矩陣迭代格式13小結(jié)Jacobi迭代法13G－S方法迭代矩陣迭代格式14G－S方法14例利用迭代法求解方程組討論Jacobi和Gauss-Seidel方法的收斂性15例利用迭代法求解方程組152.3.3對(duì)角占優(yōu)矩陣與不可約矩陣定義2.4若矩陣A=(aij)滿足條件且至少有一個(gè)i,使不等式嚴(yán)格成立,則稱A為(按行)對(duì)角占優(yōu)矩陣;若對(duì)i=1,…,n嚴(yán)格不等式均成立,則稱A為(按行)嚴(yán)格對(duì)角占優(yōu)矩陣.類似地,可以定義(按列)對(duì)角占優(yōu)矩陣和(按列)嚴(yán)格對(duì)角占優(yōu)矩陣.(2.3.14)162.3.3對(duì)角占優(yōu)矩陣與不可約矩陣定義2.4若矩陣A1717定義2.5

設(shè),若存在置換矩陣P,使得其中B和D是階數(shù)≥1的方陣,O是零矩陣,則稱A為可約的,否則稱A為不可約的.定理2.6

若A為嚴(yán)格對(duì)角占優(yōu)矩陣(或?qū)钦純?yōu)不可約矩陣),則A是非奇異的.18定義2.5設(shè)2.3.4迭代法收斂的充分條件定理2.7

若系數(shù)矩陣A滿足1)按行(或列)嚴(yán)格對(duì)角占優(yōu),或者2)不可約按行(或列)對(duì)角占優(yōu),則Jacobi迭代法(2.3.6)式和Gauss-Seidel迭代法(2.3.9)式均收斂.(2.3.9)(2.3.6)192.3.4迭代法收斂的充分條件定理2.7若系數(shù)矩陣A滿足定理2.8若A是對(duì)角元素大于零的實(shí)對(duì)稱矩陣,則Jacobi方法收斂的充分必要條件是A和2D-A皆為正定矩陣.定理2.9設(shè)A為對(duì)稱正定矩陣,則解Ax=b的Gauss-Seidel方法收斂.20定理2.8若A是對(duì)角元素大于零的實(shí)對(duì)稱矩陣,則Jacobi2.4松弛法

2.4松弛法

松弛技術(shù)的設(shè)計(jì)思想在實(shí)際計(jì)算中常?？梢垣@得目標(biāo)值F*的兩個(gè)相伴隨的近似值F0與F1,于是可以取兩者的某種加權(quán)平均去改善精度，即也就是說，適當(dāng)選取權(quán)值系數(shù)ω來調(diào)整校正量，以將F0與F1加工成更高精度的結(jié)果。由于這種方法基于校正量的調(diào)整與松動(dòng)，通常稱之為松弛技術(shù)。松弛技術(shù)的設(shè)計(jì)思想在實(shí)際計(jì)算中常?？梢垣@得目標(biāo)值F*的兩個(gè)相2.4.1Richardson迭代一般迭代法：Ax=bx=Hx+g2.4.1Richardson迭代一般迭代法：2.4.1Richardson迭代一般迭代法：Ax=bx=Hx+g記令2.4.1Richardson迭代一般迭代法：2.4.1Richardson迭代一般迭代法：Ax=bx=Hx+g記令得到：2.4.1Richardson迭代一般迭代法：2.4.1Richardson迭代一般迭代法：Ax=bx=Hx+g記令得到：2.4.1Richardson迭代一般迭代法：2.4.1Richardson迭代收斂性：H=I-

ωA(H)=(I-ωA)<1|1-

ωA|<1A為A任意特征值當(dāng)A為對(duì)稱正定矩陣時(shí)0<ω<2/max

A2.4.1Richardson迭代收斂性：2.4.2Jacobi松弛法Jacobioverrelaxation(JOR)Jacobi迭代法：x(k+1)=(I-D-1A)x(k)+D-1b2.4.2Jacobi松弛法Jacobioverrela2.4.2Jacobi松弛法Jacobi迭代法：x(k+1)=(I-D-1A)x(k)+D-1b記令2.4.2Jacobi松弛法Jacobi迭代法：2.4.2Jacobi松弛法Jacobi迭代法：x(k+1)=(I-D-1A)x(k)+D-1b記令得到：或者2.4.2Jacobi松弛法Jacobi迭代法：2.4.2Jacobi松弛法Jacobi迭代法：x(k+1)=(I-D-1A)x(k)+D-1b記令得到：或者2.4.2Jacobi松弛法Jacobi迭代法：2.4.3SOR方法對(duì)Gauss-Seidel方法施加松弛技術(shù)Successiveoverrelaxation(SOR)Gauss-Seidel迭代法：2.4.3SOR方法對(duì)Gauss-Seidel方法施加松弛2.4.3SOR方法Gauss-Seidel迭代法：記令2.4.3SOR方法Gauss-Seidel迭代法：2.4.3SOR方法得到：矩陣形式：2.4.3SOR方法得到：2.4.3SOR方法得到：矩陣形式：2.4.3SOR方法得到：第二章小結(jié)36第二章小結(jié)36小結(jié)向量范數(shù)矩陣范數(shù)譜半徑37小結(jié)37常見的三種向量范數(shù)“1－范數(shù)”“2－范數(shù)”（歐氏范數(shù)）“∞－范數(shù)”（最大范數(shù)）38常見的三種向量范數(shù)“1－范數(shù)”38(ATA之最大特征值)1/2行和范數(shù)列和范數(shù)譜范數(shù)（2.1.15）39(ATA之最大特征值)1/2行和范數(shù)列和范數(shù)譜范數(shù)（2.1.譜半徑矩陣A的特征值的按模最大值稱為A的譜半徑記作，即其中是A的特征值。定理2.3對(duì)任意，有40譜半徑矩陣A的特征值的按模最大值稱為A的譜半徑記作，即4一般迭代法的求解步驟依據(jù)方程組分離x得到迭代格式判斷迭代格式是否收斂迭代求解滿足終止條件,迭代結(jié)束41一般迭代法的求解步驟依據(jù)方程組分離x41小結(jié)42小結(jié)42小結(jié)Jacobi迭代法迭代矩陣迭代格式43小結(jié)Jacobi迭代法43G－S方法迭代矩陣迭代格式44G－S方法44定理2.7

若系數(shù)矩陣A滿足1)按行(或列)嚴(yán)格對(duì)角占優(yōu),或者2)不可約按行(或列)對(duì)角占優(yōu),則Jacobi迭代法和Gauss-Seidel迭代法均收斂.定理2.8若A是對(duì)角元素大于零的實(shí)對(duì)稱矩陣,則Jacobi方法收斂的充分必要條件是A和2D-A皆為正定矩陣.定理2.9設(shè)A為對(duì)稱正定矩陣,則解Ax=b的Gauss-Seidel方法收斂.45定理2.7若系數(shù)矩陣A滿足1)按行(或列)嚴(yán)格對(duì)角占優(yōu),作業(yè)P58，3，6，7,9(1)，證明定理2.2列和范數(shù)46作業(yè)46第二章解線性方程組的迭代法第二章解線性方程組的迭代法2.3Jacobi方法與Gauss-Seidel方法482.3Jacobi方法與Gauss-Seidel方法2一般迭代法的求解步驟依據(jù)方程組分離x得到迭代格式判斷迭代格式是否收斂迭代求解滿足終止條件,迭代結(jié)束49一般迭代法的求解步驟依據(jù)方程組分離x32.3.1Jacobi方法考慮方程組

Ax=b

(2.3.1)其中是非奇異的,為已知向量.將矩陣A寫成如下

A=D-L-U(2.3.2)其中為對(duì)角陣,-L,-U分別為A的嚴(yán)格下,上三角部分構(gòu)成的三角陣502.3.1Jacobi方法考慮方程組4515當(dāng)D非奇異,即aii≠0(i=1,2,…,n)時(shí),利用(2.3.2)式,可將方程組(2.3.1)寫成于是可得迭代格式稱此格式為求解方程組(2.3.1)的Jacobi迭代法.注意到L+U=D-A,故(2.3.3)式也可寫成(2.3.3)(2.3.4)52當(dāng)D非奇異,即aii≠0(i=1,2,…,n)時(shí),利用(2.Jacobi方法的迭代矩陣為Jacobi迭代法(2.3.4)式的分量形式為(2.3.6)53Jacobi方法的迭代矩陣為(2.3.6)7例2.1用Jacobi方法解方程組54例2.1用Jacobi方法解方程組82.3.2Gauss-Seidel方法簡(jiǎn)單迭代法(2.2.3)的分量形式是可以用這些新值來計(jì)算,于是可得迭代格式這種方法稱為Seidel迭代法.(2.3.7)552.3.2Gauss-Seidel方法簡(jiǎn)單迭代法(2.2.對(duì)Jacobi迭代(2.3.6)式運(yùn)用Seidel技巧得到稱(2.3.9)式為Gauss-Seidel迭代法,其矩陣形式為并可整理成一般迭代法的形式(2.3.9)(2.3.10)56對(duì)Jacobi迭代(2.3.6)式運(yùn)用Seidel技巧得到(例2.1用Jacobi和Gauss-Seidel方法解方程組57例2.1用Jacobi和Gauss-Seidel方法解方程小結(jié)58小結(jié)12小結(jié)Jacobi迭代法迭代矩陣迭代格式59小結(jié)Jacobi迭代法13G－S方法迭代矩陣迭代格式60G－S方法14例利用迭代法求解方程組討論Jacobi和Gauss-Seidel方法的收斂性61例利用迭代法求解方程組152.3.3對(duì)角占優(yōu)矩陣與不可約矩陣定義2.4若矩陣A=(aij)滿足條件且至少有一個(gè)i,使不等式嚴(yán)格成立,則稱A為(按行)對(duì)角占優(yōu)矩陣;若對(duì)i=1,…,n嚴(yán)格不等式均成立,則稱A為(按行)嚴(yán)格對(duì)角占優(yōu)矩陣.類似地,可以定義(按列)對(duì)角占優(yōu)矩陣和(按列)嚴(yán)格對(duì)角占優(yōu)矩陣.(2.3.14)622.3.3對(duì)角占優(yōu)矩陣與不可約矩陣定義2.4若矩陣A6317定義2.5

設(shè),若存在置換矩陣P,使得其中B和D是階數(shù)≥1的方陣,O是零矩陣,則稱A為可約的,否則稱A為不可約的.定理2.6

若A為嚴(yán)格對(duì)角占優(yōu)矩陣(或?qū)钦純?yōu)不可約矩陣),則A是非奇異的.64定義2.5設(shè)2.3.4迭代法收斂的充分條件定理2.7

若系數(shù)矩陣A滿足1)按行(或列)嚴(yán)格對(duì)角占優(yōu),或者2)不可約按行(或列)對(duì)角占優(yōu),則Jacobi迭代法(2.3.6)式和Gauss-Seidel迭代法(2.3.9)式均收斂.(2.3.9)(2.3.6)652.3.4迭代法收斂的充分條件定理2.7若系數(shù)矩陣A滿足定理2.8若A是對(duì)角元素大于零的實(shí)對(duì)稱矩陣,則Jacobi方法收斂的充分必要條件是A和2D-A皆為正定矩陣.定理2.9設(shè)A為對(duì)稱正定矩陣,則解Ax=b的Gauss-Seidel方法收斂.66定理2.8若A是對(duì)角元素大于零的實(shí)對(duì)稱矩陣,則Jacobi2.4松弛法

2.4松弛法

松弛技術(shù)的設(shè)計(jì)思想在實(shí)際計(jì)算中常?？梢垣@得目標(biāo)值F*的兩個(gè)相伴隨的近似值F0與F1,于是可以取兩者的某種加權(quán)平均去改善精度，即也就是說，適當(dāng)選取權(quán)值系數(shù)ω來調(diào)整校正量，以將F0與F1加工成更高精度的結(jié)果。由于這種方法基于校正量的調(diào)整與松動(dòng)，通常稱之為松弛技術(shù)。松弛技術(shù)的設(shè)計(jì)思想在實(shí)際計(jì)算中常常可以獲得目標(biāo)值F*的兩個(gè)相2.4.1Richardson迭代一般迭代法：Ax=bx=Hx+g2.4.1Richardson迭代一般迭代法：2.4.1Richardson迭代一般迭代法：Ax=bx=Hx+g記令2.4.1Richardson迭代一般迭代法：2.4.1Richardson迭代一般迭代法：Ax=bx=Hx+g記令得到：2.4.1Richardson迭代一般迭代法：2.4.1Richardson迭代一般迭代法：Ax=bx=Hx+g記令得到：2.4.1Richardson迭代一般迭代法：2.4.1Richardson迭代收斂性：H=I-

ωA(H)=(I-ωA)<1|1-

ωA|<1A為A任意特征值當(dāng)A為對(duì)稱正定矩陣時(shí)0<ω<2/max

A2.4.1Richardson迭代收斂性：2.4.2Jacobi松弛法Jacobioverrelaxation(JOR)Jacobi迭代法：x(k+1)=(I-D-1A)x(k)+D-1b2.4.2Jacobi松弛法Jacobioverrela2.4.2Jacobi松弛法Jacobi迭代法：x(k+1)=(I-D-1A)x(k)+D-1b記令2.4.2Jacobi松弛法Jacobi迭代法：2.4.2Jacobi松弛法Jacobi迭代法：x(k+1)=(I-D-1A)x(k)+D-1b記令得到：或者2.4.2Jacobi松弛法Jacobi迭代法：2.4.2Jacobi松弛法Jacobi迭代法：x(k+1)=(I-D-1A)x(k)+D-1b記令得到：或者2.4.2Jacobi松弛法Jacobi迭代法：2.4.3SOR方法對(duì)Gauss-Seidel方法施加松弛技術(shù)Successiveoverrelaxation(SOR)Gauss-Seidel迭代法：2.4.3SOR方法對(duì)Gauss-Seidel方法施加松弛2.4.3SOR方法Gauss-Seidel迭代法：記令2.4.3SOR方法Gauss-Seidel迭代法：2.4.3SOR方法得到