Chap7迭代解法(全章)講解課件

1、第六章 線性方程組的迭代解法1 向量和矩陣的范數(shù) 1.1 向量的范數(shù) 1.2 矩陣的范數(shù)2 迭代解法與收斂性 2.1 迭代法的構(gòu)造 2.2 迭代法的收斂性條件3 常用的三種迭代解法 2.1 Jacobi迭代法 2.2 Gauss-Seidel迭代法 2.2 超松弛(SOR)迭代法10/10/20221第六章 線性方程組的迭代解法第六章 線性方程組的迭代解法1 向量和矩陣的范數(shù) 101 向量和矩陣的范數(shù)一、向量的范數(shù) 為了對線性方程組數(shù)值解的精確程度，以及方程組本身的性態(tài)進行分析，需要對向量和矩陣的“大小”引進某種度量，范數(shù)就是一種度量尺度，向量和矩陣的范數(shù)在線性方程組數(shù)值方法的研究中起著重要的

2、作用。 定義6.1設(shè)|是向量空間Rn上的實值函數(shù)，且滿足條件 求解線性方程組的數(shù)值解除了使用直接解法，迭代解法也是經(jīng)常采用的一種方法，這種方法更有利于編程計算，本章將介紹這種方法。10/10/20222第六章 線性方程組的迭代解法1 向量和矩陣的范數(shù)一、向量的范數(shù) 為則稱 | 為 Rn 空間上的范數(shù)，| x |為向量 x 的范數(shù)。 理論上存在多種多樣的向量范數(shù)，但最常用的是如下三種。（2）齊次性：對任何實數(shù)和向量x | x| | | x |（3）三角不等式：對任何向量x和y，都有 | xy | x | y |設(shè)向量x（x1，x2，xn）T，定義 （1）非負性：對任何向量 x， | x |0，且

3、| x |0當且僅當x010/10/20223第六章 線性方程組的迭代解法則稱 | 為 Rn 空間上的范數(shù)，| x |為向向量1-范數(shù)： 向量2-范數(shù)： 向量-范數(shù)： 容易驗證，以上三種范數(shù)都滿足向量范數(shù)的三個條件。 例6.1 設(shè)向量x（1，3，2，0）T，求向量范數(shù)| x |p，P1，2，。 10/10/20224第六章 線性方程組的迭代解法向量1-范數(shù)： 向量2-范數(shù)： 向量-范數(shù)： 容易驗證，以 解:對于 向量 x(1，3，2，0)T ，根據(jù)定義可以計算出： | x|1| 1 |3 | 2 | 0 |6 由此例可見，向量不同范數(shù)的值不一定相同，但這并不影響對向量大小做定性的描述，因為不同

4、范數(shù)之間存在如下等價關(guān)系。 10/10/20225第六章 線性方程組的迭代解法 解:對于 向量 x(1，3，2，0)T 定理6.1 （范數(shù)的等價性）對于Rn上任何兩種范數(shù)|和|，存在著正常數(shù) m，M，使得： 范數(shù)的等價性表明，一個向量若按某種范數(shù)是一個小量，則它按任何一種范數(shù)也將是一個小量。容易證明，常用的三種向量范數(shù)滿足下述等價關(guān)系。 | x | | x |1 n| x | x | | x |2 | x | x | 2| x |1 n| x |2 例如：10/10/20226第六章 線性方程組的迭代解法 定理6.1 （范數(shù)的等價性）對于Rn上任何兩定義6.2 對于向量序列 向量序列 x(k)

5、 收斂于向量 x*，當且僅當它的每一個分量序列收斂于x*的對應分量，即 及向量如果則稱向量序列 x(k) 收斂于向量 x* 。記作 或10/10/20227第六章 線性方程組的迭代解法定義6.2 對于向量序列 向量序列 x二、矩陣的范數(shù) 矩陣范數(shù)是反映矩陣“大小”的一種度量，具體定義如下。 定義6.3 設(shè)|是以n階矩陣為變量的實值函數(shù)，且滿足條件： （1）| A |0，且| A |0時，當且僅當A0 （2）|A| | A|，R （3）|AB| | A | B | （4）| AB | A | | B |則稱| A |為矩陣A的范數(shù)。10/10/20228第六章 線性方程組的迭代解法二、矩陣的范數(shù)

6、 矩陣范數(shù)是反映矩陣“大小”的一種度量，具設(shè) n 階矩陣 A（aij），常用的矩陣范數(shù)有： 矩陣1-范數(shù)： 矩陣2-范數(shù)： 矩陣-范數(shù)： 以上三種范數(shù)都滿足矩陣范數(shù)的條件，通常將這三種矩陣范數(shù)統(tǒng)一表示為| A |p，P1，2，。 列和行和10/10/20229第六章 線性方程組的迭代解法設(shè) n 階矩陣 A（aij），常用的矩陣范數(shù)有： 矩陣1-例6.2 設(shè)矩陣求矩陣A的范數(shù)| A |p，P1，2，。 解 根據(jù)定義 由于則它的特征方程為: 10/10/202210第六章 線性方程組的迭代解法例6.2 設(shè)矩陣求矩陣A的范數(shù)| A |p，P1，2此方程的根為矩陣ATA的特征值，解得 因此 在線性方程

7、組的研究中，經(jīng)常遇到矩陣與向量的乘積運算，若將矩陣范數(shù)與向量范數(shù)關(guān)聯(lián)起來，將給問題的分析帶來許多方便。設(shè)|是一種向量范數(shù)，由此范數(shù)派生的矩陣范數(shù)定義為 注意，此式左端|A|表示矩陣范數(shù)，而右端是向量Ax 和 x 的范數(shù)，利用向量范數(shù)所具有的性質(zhì)不難驗證，由上式定義的矩陣范數(shù)滿足矩陣范數(shù)的條件。10/10/202211第六章 線性方程組的迭代解法此方程的根為矩陣ATA的特征值，解得 通常將滿足上式的矩陣范數(shù)稱為與向量范數(shù)相容的矩陣范數(shù)。 可以證明，前述的三種矩陣范數(shù)| A |p，P1，2，就是由向量范數(shù)| x |p派生出的矩陣范數(shù)，即通過向量范數(shù)定義的矩陣范數(shù)，滿足不等式關(guān)系：均為相容范數(shù)，即1

8、0/10/202212第六章 線性方程組的迭代解法通常將滿足上式的矩陣范數(shù)稱為與向量范數(shù)相容的矩陣范數(shù)。 三、矩陣的譜半徑 矩陣范數(shù)同矩陣特征值之間有密切的聯(lián)系，設(shè)是矩陣A相應于特征向量x的特征值，即 Axx,于是利用向量-矩陣范數(shù)的相容性，得到| | x |x|從而，對A的任何特征值均成立=| Ax| | A | |x| A | （6.1） 設(shè)n階矩陣A的n個特征值為1,2，n。稱為矩陣A的譜半徑，從（6.1）式得知，對矩陣A的任何一種相容范數(shù)都有 (A)|A| （6.2）10/10/202213第六章 線性方程組的迭代解法三、矩陣的譜半徑 矩陣范數(shù)同矩陣特征值之間有密切的聯(lián)系， 另一個更深

9、刻的結(jié)果,對于任意的0，必存在一種相容的矩陣范數(shù)，使| A | (A) （6.3） 式（6.2）和（6.3）表明，矩陣A的譜半徑是它所有相容范數(shù)的下確界。 定義6.4 設(shè)有矩陣序列 和矩陣A（aij）。稱 A（k）收斂于A，如果 記作 A（k）A，或 A（k）A。 10/10/202214第六章 線性方程組的迭代解法 另一個更深刻的結(jié)果,對于任意的0，必存四、矩陣的條件數(shù) 引進了矩陣的度量標準范數(shù)，就可以對方程組求解進行誤差分析，對于方程組Ax =b如果常數(shù)項產(chǎn)生了誤差b, 并設(shè)求解時產(chǎn)生的誤差為x，則有A(x + x) =b+ b兩式相減得到 A x = b當系數(shù)矩陣可逆時x = A-1b取

10、范數(shù)|x| = |A-1b|A-1 | |b|再由 Ax =b，得到| b|= | Ax |A | |x|10/10/202215第六章 線性方程組的迭代解法四、矩陣的條件數(shù) 引進了矩陣的度量標準范數(shù)，于是，由 | x |A-1 | |b|得到解的相對誤差為及 |b | |A | |x|令 Cond(A)=|A | |A-1 | ,并稱其為矩陣A的條件數(shù)。這時可見，求解線性方程組所產(chǎn)生的誤差與系數(shù)矩陣的條件數(shù)有關(guān)。10/10/202216第六章 線性方程組的迭代解法于是，由 | x |A-1 | |b| 對于線性方程組 Ax=b，如果系數(shù)矩陣的條件數(shù)Cond(A)=|A | |A-1 | 太大

11、，則稱相應的方程組為病態(tài)方程組。 病態(tài)現(xiàn)象是方程組的固有屬性，無法改變，因此在求解時為了不至于產(chǎn)生太大的誤差，應該盡量減少原始數(shù)據(jù) A、b 的誤差，或者用高精度的計算機計算。例如：對于方程組系數(shù)矩陣和逆矩陣分別為可以求得條件數(shù)比較大，可見該方程組為病態(tài)方程組。10/10/202217第六章 線性方程組的迭代解法 對于線性方程組 Ax=b，如果系數(shù)矩陣的條件數(shù)2 迭代解法與收斂性一、迭代解法設(shè)有線性方程組 AX=b (1) ARnn, bR .對A 進行分裂， A=A1+A2 , 其中 A1 可逆，則 (A1+A2)x=b A1x = - A2x+b令 B= - A1-1 A2 , F =A1-

12、1 b則 x= Bx+F （2） x = - A1-1 A2 x + A1-1 b10/10/202218第六章 線性方程組的迭代解法2 迭代解法與收斂性一、迭代解法設(shè)有線性方程組 得到 x(1)= Bx(0)+F 稱(3)為求解(1)的近似解的迭代解法，稱x(k)為(1)近似解序列，稱B為迭代矩陣。如果則有 x(2)= Bx(1)+F x(k+1)= Bx(k)+F , k=0 ,1 , , （3）x*= Bx*+F （4）我們稱迭代法(3)收斂，否則為發(fā)散。下面分析迭代格式(3)收斂的條件. 由 x= Bx+Fx(0)Rn10/10/202219第六章 線性方程組的迭代解法得到 x(1)=

13、 Bx(0)+F 稱(3)為求解(1)的近由(3) (4)得 x(k+1) - x* = B(x(k)- x* ) 令 e(k)= x(k)- x* , 則有若 x(k+1) x* ,則 e(k) 0。這時只有 Bk+1 0 （k ）。x(k+1)= Bx(k)+F , k=0 ,1 , , （3）x*= Bx*+F （4）而 Bk+1 0 (B)1，由此可得如下的收斂性條件。10/10/202220第六章 線性方程組的迭代解法由(3) (4)得 x(k+1) - x* = B二、迭代法收斂性條件 x(k+1)= Bx(k)+F , k=0 ,1 , , （3）定理6.3 若 |B|1 ，則迭

14、代法(3)收斂. 定理6.4 若 |B|1 ，則有估計式 定理6.2 迭代法格式(3)收斂的充要條件是(B)1. 這是一個充分條件，根據(jù)范數(shù)與譜半徑的關(guān)系式 (A)|B| ，容易推出該充分條件.10/10/202221第六章 線性方程組的迭代解法二、迭代法收斂性條件 x(k+1)= Bx(k)+F , 3 常用的三種迭代解法一、Jacobi迭代法對于線性方程組 Ax=b (1) A=L+D+U (2)設(shè) det(A) 0 ，aii 0,i=0,1,2,n ，按照如下方式對A進行分裂：10/10/202222第六章 線性方程組的迭代解法3 常用的三種迭代解法一、Jacobi迭代法對于線性方程則由

15、 Ax=b 得到令 BJ=-D-1(L+U) ， FJ= D-1 b.(L+D+U) x=b D x=-(L+U)x+b x=-D-1(L+U)x+ D-1 b則有 x= BJ x+ FJ (3)任取初始向量 x(0)Rn , 則可以由上式得到如下的迭代格式：并稱其為Jacobi迭代格式，迭代矩陣為 x(k+1)= BJ x(k)+ FJ (4)BJ=-D-1(L+U)= -D-1(A - D)= E - D-1 A10/10/202223第六章 線性方程組的迭代解法則由 Ax=b 得到令 BJ=-D-1(L+U) ， F例如, 對于三元線性方程組10/10/202224第六章 線性方程組的迭

16、代解法例如, 對于三元線性方程組10/9/202224第六章 線性 得到具體的迭代格式由定理6.4的結(jié)論,可以通過| x(k+1)-x(k)|控制迭代次數(shù)。x(0)Rn10/10/202225第六章 線性方程組的迭代解法 得到具體的迭代格式由定理6.4的結(jié)論,可以通過| x(k對于 n 元線性方程組其一般式為：從中解出： 得Jacobi迭代格式通過| x(k+1)-x(k)| 控制迭代次數(shù)。10/10/202226第六章 線性方程組的迭代解法對于 n 元線性方程組其一般式為：從中解出： 得Jacobi二、 Gauss-Seidel迭代法對于三元方程組，將Jacobi迭代格式改進為并稱其為Gau

17、ss-Seidel迭代格式。10/10/202227第六章 線性方程組的迭代解法二、 Gauss-Seidel迭代法對于三元方程組，將Jac對于n元方程 先寫出Jacobi迭代格式同樣可以用 | x(k+1)-x(k)| 控制迭代次數(shù)。 再寫出Gauss-Seidel迭代格式10/10/202228第六章 線性方程組的迭代解法對于n元方程 先寫出Jacobi迭代格式同樣可以用 | x 為討論收斂性方便，下面再寫出Gauss-Seidel迭代格式的矩陣表示式。首先改寫Gauss-Seidel迭代格式為：10/10/202229第六章 線性方程組的迭代解法 為討論收斂性方便，下面再寫出Gauss-

18、Se令 則有 其中 BG 為迭代矩陣。 例6.3 用Jacobi迭代法和Gauss-Seidel迭代法解下列方程組,已知方程組得精確解為 x*=(1，1，1)T 。 10/10/202230第六章 線性方程組的迭代解法令 則有 其中 BG 為迭代矩陣。 例6.3 用解：先改寫方程如下再寫出Jacobi迭代格式取初值為: x(0)=(0，0，0)T , 求得:x(1)=(1.4，0.5，1.4)Tx(6)=(1.00025，1.00580，1.00251)T誤差為由x*=(1，1，1)T 得到 |x(6)-x*|=0.00580 。10/10/202231第六章 線性方程組的迭代解法解：先改寫方

19、程如下再寫出Jacobi迭代格式取初值為: x(初值也取為: x(0)=(0，0，0)T , 求得近似解：Gauss-Seidel迭代格式為誤差為由x*=(1，1，1)T 得到 |x(4)-x*|=0.00846 。 Jacobi迭代法迭代6次與Gauss-Seidel迭代法迭代4次的精度一致，說明Gauss-Seidel迭代法收斂的較快。x(1)=(1.4，0.78，1.026)Tx(4)=(0.99154，0.99578，1.00210)T10/10/202232第六章 線性方程組的迭代解法初值也取為: x(0)=(0，0，0)T , 求得近似解：三.超松弛(SOR)迭代法 (Succes

20、sive Over Relaxation Method)對Gauss-seidel迭代進行改寫令 10/10/202233第六章 線性方程組的迭代解法三.超松弛(SOR)迭代法 (Successive Over再通過加權(quán)加速收斂： 并稱其為超松弛迭代法，稱為松弛因子。當 0 1 時，稱為低松弛； 當 =1 時，為Gauss-Seidel 迭代格式 ；當 1 2 時，稱為高松弛。 10/10/202234第六章 線性方程組的迭代解法再通過加權(quán)加速收斂： 并稱其為超松弛迭代法，稱為松弛因子。超松弛迭代法(SOR)也可以用矩陣的形式來表示令 B =(D+ L)-1D- (D+U)則有 x(k+1)=

21、B x(k)+F , k=0,1, 2 , 。改寫SOR為或者F = (D+wL)-1 b10/10/202235第六章 線性方程組的迭代解法超松弛迭代法(SOR)也可以用矩陣的形式來表示令 B =( 定理6.6 Gauss-Seidel 迭代法 收斂的充要條件是(BG)1 ，收斂的充分條件是 |BG|1 。 定理6.7 對于 線性方程組 AX=b ，如果系數(shù)矩陣A嚴格對角占優(yōu)，則Jacobi、G-S迭代法都收斂。定理6.8 SOR迭代法收斂的必要條件是 0 2 。 定理6.9 如果系數(shù)矩陣A對稱正定，且 0 2 ，則SOR 法收斂定理6.10 如果系數(shù)矩陣A對稱正定，則G-S迭代法收斂。四、

22、收斂性條件 定理6.5 Jacobi迭代法收斂的充要條件是(BJ)1 ，收斂的充分條件是 |BJ |1,還無法判斷迭代法是否收斂。10/10/202238第六章 線性方程組的迭代解法例6.5 用Jacobi迭代法解下列方程組，問是否收斂？ 這時只能通過求迭代矩陣的譜半徑來判斷，由迭代矩陣解得特征值譜半徑 (BJ)1故Jacobi迭代法收斂.10/10/202239第六章 線性方程組的迭代解法這時只能通過求迭代矩陣的譜半徑來判斷，由迭代矩陣解得特征值譜 例6.6 分別用Jacobi迭代法和Gauss-Seidel迭代法解下列方程組，問是否收斂？ 由于該矩陣非嚴格對角占優(yōu)，無法判斷；但由于對稱，再

23、看是否正定。解：系數(shù)矩陣為 各階順序主子式 |A1|=1, |A2|=3/4, |A3|=1/2, 說明矩陣對稱正定所以Gauss-Seidel迭代法收斂。但無法判斷Jacobi迭代法是否收斂，再利用迭代矩陣的范數(shù)或者譜半徑進行判斷。10/10/202240第六章 線性方程組的迭代解法 例6.6 分別用Jacobi迭代法和Gauss由系數(shù)矩陣寫出Jacobi迭代矩陣其-范數(shù) |BJ |=1 和 1-范數(shù)|BJ |1=1，不小于1，還無法判斷是否收斂。再求其譜半徑進行判斷。由 det(I-BJ)=0 求得特征值1 = -1，2= 3=0.5 譜半徑 (BJ)=|1| = 1，由此可知Jacobi

24、迭代法是發(fā)散的。10/10/202241第六章 線性方程組的迭代解法由系數(shù)矩陣寫出Jacobi迭代矩陣其-范數(shù) |BJ | 例6.7 取初值 x(0)=(0，0，0)T 用Jacobi迭代法解下列方程組，如果要保證各分量的誤差的絕對值小于10-6,問需要迭代多少次？ 解：由于方程組得系數(shù)矩陣嚴格對角占優(yōu)，所以Jacobi迭代法收斂。要確定迭代次數(shù)需要用到估計式其中 BJ=E-D-1A ， FJ= D-1 b，范數(shù)用-范數(shù) 。10/10/202242第六章 線性方程組的迭代解法 例6.7 取初值 x(0)=(0，0，0)T 由方程組得到系數(shù)矩陣和常數(shù)項迭代矩陣為-范數(shù) |BJ |=1/3 1 , |FJ |