第五章線性代數(shù)方程組的解法

1、上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院1上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院2nnnnnnnbxaxabxaxa1111111本章討論求解線性方程組：本章討論求解線性方程組：的數(shù)值方法的數(shù)值方法.上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院3,Axb 12,Tnxxxx 12,.Tnbbbb 其中其中111212122212,nnnnnnaaaaaaAaaa 上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院4 但當(dāng)方程組的階數(shù)但當(dāng)方程組的階數(shù) 很大時，計(jì)算量為很大時，計(jì)算量為n( !)O n假設(shè)假設(shè)系數(shù)矩陣行列式系數(shù)矩陣行列式|0, A由由Cramer法則法則

2、, ,方程組有唯一解，且解可表示為：方程組有唯一解，且解可表示為：1212,.nnDDDxxxDDD11111111111,detiininn inn innaabaaDaabaa 其其中中 上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院5 常用的計(jì)算方法常用的計(jì)算方法: 直接法和迭代法直接法和迭代法 直接法：直接法：若不考慮計(jì)算過程中的舍入誤差，若不考慮計(jì)算過程中的舍入誤差， 則通過有限步運(yùn)算可以獲得方程組的精確解則通過有限步運(yùn)算可以獲得方程組的精確解. Gauss 消去法、消去法、Gauss列主元消去法、矩陣分解法等列主元消去法、矩陣分解法等.上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算

3、科學(xué)學(xué)院6 迭代法：迭代法：采用逐次逼近的方法采用逐次逼近的方法, 即從一個初始即從一個初始 近似解出發(fā)近似解出發(fā), 按某種迭代格式按某種迭代格式, 逐步逼近方程組逐步逼近方程組 的解的解, 直至滿足精度要求為止直至滿足精度要求為止. 經(jīng)典迭代法有經(jīng)典迭代法有： 迭代法、迭代法、 迭代法、迭代法、JacobiGaussSeidel 逐次超松弛（逐次超松弛（SOR）迭代法等）迭代法等.上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院7 上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院85.1.1 向量空間及相關(guān)概念和記號向量空間及相關(guān)概念和記號 1. 向量的范數(shù)向量的范數(shù)1/1|,1,),p

4、npipixxp 1211|nniixxxxx 1max(|,|)nxxx 1/2221niixx 上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院9例例 : 設(shè)設(shè)(1,3, 5,4) ,Tx ,1,2,pxp 求求根據(jù)定義根據(jù)定義:411|13iixx 1/2422151iixx 14max(|,|)5xxx 上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院102( , ).xx x 上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院11定義定義 對于任意兩種范數(shù)對于任意兩種范數(shù) | |A，| |B ，總存在常數(shù)，總存在常數(shù) C1、C2 0 使得使得 ， 則稱則稱 | |A 和和| |B

5、 等價等價。（范數(shù)等價性）（范數(shù)等價性）BABxCxxC|21 對于常用的范數(shù)對于常用的范數(shù) , , ,可以算出可以算出 px1,2,p 1211xxxn1xxn x 2xxn x上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院12定義定義向量序列向量序列 收斂收斂于向量于向量 是指對每一個是指對每一個 1 i n 都都有有 。)(kx*x*)(limikikxx 可以理解為可以理解為0|*|)( xxk可以理解為對任何向可以理解為對任何向量范數(shù)都成立。量范數(shù)都成立。2. 上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院13對于對于 上的任何向量范數(shù)上的任何向量范數(shù),我們可以定義矩陣范數(shù)我

6、們可以定義矩陣范數(shù).nR1. 1. 矩陣的范數(shù)矩陣的范數(shù)5.1.2 矩陣的一些相關(guān)概念及記號矩陣的一些相關(guān)概念及記號上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院14定理定理5.3 矩陣的從屬范數(shù)具有下列基本性質(zhì)：矩陣的從屬范數(shù)具有下列基本性質(zhì)：1） ，當(dāng)且僅當(dāng)，當(dāng)且僅當(dāng) 時，時， 0A 0A 0A ,R |AA 2)3),;n nABABA BR nxR AxAx 4)時時5),A BAB A、Bn nR 定理5.3中的性質(zhì) 1), 2) 和 3)是一般范數(shù)所滿足的基本性質(zhì)，性質(zhì) 4)、5) 被稱為相容性條件，一般矩陣范數(shù)并不一定滿足該條件. 上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科

7、學(xué)學(xué)院15非從屬范數(shù)的矩陣范數(shù)非從屬范數(shù)的矩陣范數(shù) 例如，矩陣?yán)?，矩?的的Frobenius范數(shù)（范數(shù)（F-范數(shù)）范數(shù)）()ijAa 2 1/211,nnijFijAa 可以證明可以證明Frobenius范數(shù)滿足相容性條件范數(shù)滿足相容性條件 對方陣對方陣 以及以及 有有nnRA nRx 22|xAxAF 上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院16三種重要的從屬范數(shù)是：三種重要的從屬范數(shù)是：（1）矩陣的）矩陣的1-范數(shù)范數(shù)(列和范數(shù)列和范數(shù)): 11max|nijjiAa （2）矩陣的）矩陣的 -范數(shù)范數(shù)(行和范數(shù)行和范數(shù)): 1max|nijijAa （3）矩陣的）矩陣的2-范

8、數(shù)范數(shù): 12A 其中其中 : 的最大特征值的最大特征值1 TA A 上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院17 對任何對任何 11x 11111| |nnnnijjijjijijAxa xax 1111|max|,nnnjijijjjiixaax從而從而11max|nijjiAxa niijaAnj11|max|1（列和范數(shù)列和范數(shù)）上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院18現(xiàn)設(shè)現(xiàn)設(shè)11max|nnijikjiiaa 令令1,0,jjkyjk 若若若若12(,)Tnyy yy 顯然顯然11y 滿足滿足111111max|nnijjxijAxAya y 且且11| ma

9、x|nnikijjiiaa上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院191312101424341420TA A2101430401420TIA A 15221 2()152215.46TAA A 解：解：16A 7A 按定義按定義例例 已知矩陣已知矩陣 12,34A ,1,2,pAp 求求上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院20矩陣范數(shù)的矩陣范數(shù)的等價定理等價定理：A A 對對 、 ，存在常數(shù)，存在常數(shù) 和和 ，使得：，使得：mMm AAM A 幾種常用范數(shù)的等價關(guān)系：幾種常用范數(shù)的等價關(guān)系：22FAAn A 21AAn An1211AAn An上一頁上一頁下一頁下一頁

10、湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院212. 2. 譜半徑譜半徑2()TAA A 此時此時n nAR 2()AA 若若 為對稱陣，為對稱陣，2()()TA AA （ 因?yàn)橐驗(yàn)?）上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院22證明證明 首先證明（首先證明（1）. 關(guān)于矩陣的譜半徑與矩陣的范數(shù)之間有如下關(guān)系.上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院23AxAx今設(shè)今設(shè) 為為 的特征值的特征值 A0,v 則有則有使得使得Avv | vvAvAv 從而從而即即 |A ()AA 由由 的任意性得的任意性得證畢證畢給定給定 的某一種范數(shù)的某一種范數(shù) ， AAnxR 則對任何則對任何有有上一頁上一頁

11、下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院24 (2) 對對 A 做做 Jordan 分解，有分解，有 ，其中，其中 ， ， i 為為 A 的的 特征值。特征值。 令令 ，則有，則有 易證：易證： 是由是由 導(dǎo)出的從屬范數(shù)。導(dǎo)出的從屬范數(shù)。 所以只要取所以只要取 ，就有，就有| A | 0? 因?yàn)橐驗(yàn)閐et(Ak) 02/1LDL 則則 仍是下三角陣仍是下三角陣TLLA nnRL 設(shè)矩陣設(shè)矩陣A對稱正定，則存在非奇異下三角陣對稱正定，則存在非奇異下三角陣 使得使得 。若限定。若限定 L 對角元為正，則分解唯一。對角元為正，則分解唯一。TLLA 定理定理上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)

12、學(xué)院611111121112112122212222211,11200nnnnnnnnnnnnnnnnlaaalllllaaalllllaaal 對于對稱正定陣對于對稱正定陣 A ，從，從 可知對任意可知對任意k i 有有 。即即 L 的元素不會增大，誤差可控，不的元素不會增大，誤差可控，不需選主元。需選主元。21 iiiikkaliiikal |上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院62 算法算法: Cholesky分解分解將對稱正定將對稱正定 n n n n矩陣矩陣 A A分解成分解成 LLLLT T, , 這里這里 L L是下三角陣是下三角陣 Input: 矩陣矩陣A A的維

13、的維數(shù)數(shù)n n; ; 矩陣矩陣A A的元素的元素 aij 1 i, j n .Output: 矩陣矩陣L 的元素的元素 lij ： 1 j i and 1 i n . Step 1 Set ;Step 2 For j = 2, , n, set ;Step 3 For i = 2, , n 1, do steps 4 and 5Step 4 Set ; Step 5 For j = i+1, , n, set ; Step 6 Set ;Step 7 Output ( lij for j = 1, , i and i = 1, , n ); STOP. 1111al 1111/laljj 12

14、1 iiiiiikklal( () )11 ijijijkikiiklal ll121 nnnnnnkklal運(yùn)算量為運(yùn)算量為 O(n3/6)， 比普通比普通LU分解少一半，但有分解少一半，但有 n 次開方。用次開方。用A = LDLT 分解，可省開方時間分解，可省開方時間。上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院63 解解三對角方程組三對角方程組的的追趕法追趕法 nnnnnnnfffxxxbacbacbacb212111122211步驟步驟1: 對對 A 作作Crout 分解分解 111121nnnA 直接比較等式兩邊直接比較等式兩邊的元素，可得到計(jì)的元素，可得到計(jì)算公式算公式。步

15、驟步驟2: 追追即解即解 ：fyL ,111 fy ),.,2()(1niyrfyiiiii 步驟步驟3: 趕趕即解即解 ：yxU )1,., 1(,1 nixyxyxiiiinn 與與Gauss消去法類似，一旦消去法類似，一旦 i = 0 則算法中斷，故并非任何則算法中斷，故并非任何三對角陣都可以用此方法分解。三對角陣都可以用此方法分解。上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院64 如果如果 A 是是嚴(yán)格嚴(yán)格對角占優(yōu)陣，則不要求三對角線上的對角占優(yōu)陣，則不要求三對角線上的所有元素非零。所有元素非零。根據(jù)不等式根據(jù)不等式 可知：分解過程中，矩陣元素不會過分增大，算法可知：分解過程中，

16、矩陣元素不會過分增大，算法保證穩(wěn)定。保證穩(wěn)定。運(yùn)算量為運(yùn)算量為 O(6n)。|,1|1iiiiiiiiabbab 若若 A 為為對角占優(yōu)對角占優(yōu) 的三對角矩陣，且滿足的三對角矩陣，且滿足 ，則追趕法可解以，則追趕法可解以 A 為系數(shù)矩陣的方程組。為系數(shù)矩陣的方程組。0,0, 0|, 0|11 iinncaabcb定理定理上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院65上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院66求解求解 時，時，A 和和 的誤差對解的誤差對解 有何影響？有何影響？bxA bx 設(shè)設(shè) A 精確，精確， 有誤差有誤差 ，得到的解為，得到的解為 ，即，即bb xx b

17、bxxA )(bAx 1 |1bAx |xAxAb 又又|1bAx |1bbAAxx 上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院67 設(shè)設(shè) 精確，精確，A有誤差有誤差 ，得到的解為，得到的解為 ，即，即bA xx bxxAA )( bxAAxAA )()(xAxAA )(xAxAAIA )(1xAAAAIx 111)( (只要只要 A充分小，使得充分小，使得)1|11 AAAA |1|1|1111AAAAAAAAAAAAxx 上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院68注注: cond (A) 的具體大小與的具體大小與 | | 的取法有關(guān)。的取法有關(guān)。 cond (A) 取決

18、于取決于A，與解題方法無關(guān)。，與解題方法無關(guān)。 |)(1)(|bbAAAAAcondAcondxx 上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院69精確解精確解為為.11 x例：例： 97.199.1,98.099.099.01bA計(jì)算計(jì)算cond (A)2 。 10000990099009800A 1 = 解：解：考察考察 A 的特征根的特征根 0)det(AI 000050504. 0980050504. 121 212)( Acond 39206 1給一個擾動給一個擾動b 3410106.01097.0b ，其相對誤差為，其相對誤差為%01.010513.0|422 bb 此時此時

19、精確解精確解為為 0203. 13*x 0203.22*xxx 22|xx 2.0102 200%上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院70 Gauss消去法的舍入誤差消去法的舍入誤差 舍入誤差分析方法 1. 向前誤差分析方法：按照所執(zhí)行的運(yùn)算次序而估計(jì)舍入誤差積累的界限. 這種方法的好處是估計(jì)比較準(zhǔn)確，但對復(fù)雜算法（如Gauss消去法）一般難以進(jìn)行。 2. 向后誤差分析方法：將實(shí)際計(jì)算過程的誤差轉(zhuǎn)換為關(guān)于原始數(shù)據(jù)的誤差。 上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院71對對GaussGauss消去法消去法, ,其具體提法是：其具體提法是：對于系數(shù)矩陣擾動：對于系數(shù)矩陣擾動：

20、, AAA 求解求解 時時, , 所得的計(jì)算解所得的計(jì)算解 是是如下擾動方程如下擾動方程 Axb x ().AA xbd+=%的精確解。的精確解。上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院72GaussGauss消去法由兩個獨(dú)立算法所組成消去法由兩個獨(dú)立算法所組成: :一是一是對對A做做LU分解分解; ;二是二是求解三角方程組求解三角方程組. .這兩個獨(dú)立運(yùn)算均會產(chǎn)生舍入誤差這兩個獨(dú)立運(yùn)算均會產(chǎn)生舍入誤差. .如果是選主元的如果是選主元的GaussGauss消去法消去法, ,由于只增加了由于只增加了矩陣行、列的交換，并不產(chǎn)生新的舍入誤差，矩陣行、列的交換，并不產(chǎn)生新的舍入誤差，因此并不

21、影響誤差分析。因此并不影響誤差分析。上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院73(2),.()()()LLUUxbL ybAU xxbyAddd+=%(1),;AL UAEL U=+=上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院74上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院75上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院76由上可見，對由上可見，對GaussGauss消去法，消去法，3215()1.01(3)101()AxcondAnnAxcondAA 只要只要 不是很大，則不是很大，則GaussGauss消去法是消去法是數(shù)值穩(wěn)定的數(shù)值穩(wěn)定的 ()condA 結(jié)論

22、：條件數(shù)越大，擾動對解的影響越大結(jié)論：條件數(shù)越大，擾動對解的影響越大. .上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院774 4 解線性方程組的迭代法解線性方程組的迭代法 上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院78bxA 將將 等價等價bxA 改寫為改寫為 形式，建立迭代形式，建立迭代 。從初值從初值 出發(fā)，得到序列出發(fā)，得到序列 。fxBx fxBxkk )()1()0(x)(kx研究研究 內(nèi)容：內(nèi)容： 如何建立迭代格式？如何建立迭代格式？ 收斂速度？收斂速度？ 向量序列的收斂條件？向量序列的收斂條件？ 誤差估計(jì)？誤差估計(jì)？思思路：路：上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與

23、計(jì)算科學(xué)學(xué)院79 Jacobi 法和法和 Gauss - Seidel 法法 Jacobi 迭代方法迭代方法 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa.22112222212111212111( () )( () )( () ) nnnnnnnnnnnnbxaxaaxbxaxaaxbxaxaax11112212122211212111.1.1.10 iia ()()()nknnnknnnknknnkkknnkkbxaxaaxbxaxaaxbxaxaax)(11)(11)1(2)(2)(12122)1(21)(1)(21211)1(1.1.1.1上一頁上一頁下一頁下一頁湘潭

24、大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院80 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa.22112222212111212111寫成寫成矩陣形式矩陣形式：A =LUDbxULxDbxULDbxA )()(bDxULDx11)( BfJacobi 迭代陣迭代陣bDxULDxkk1)(1)1()( 上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院81 例例求求1235131241246113xxx 的的Jacobi迭代格式。迭代格式。 解解 31164242135321321321xxxxxxxxx1232133121(13)51(22)41(346)11xxxxxxxxx 上一頁上一頁下一

25、頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院821232133121(13)51(22)41(346)11xxxxxxxxx (1)( )( )123(1)( )( )213(1)( )( )3121(13)51(22)41(346)11kkkkkkkkkxxxxxxxxx 上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院83 算法算法: Jacobi: Jacobi迭代方法迭代方法 求解求解 給定初始值給定初始值 . .Input: 方程和未知量的個數(shù)方程和未知量的個數(shù) n n; ; 矩陣元素矩陣元素 a a ; ; 元素元素 b b ; ; 初始近似值初始近似值 X X0 ; 0 ; 誤差容限誤差

26、容限 TOLTOL; ; 最大迭代次數(shù)最大迭代次數(shù) N Nmaxmax. .Output: 近似解近似解 X 或失敗的信息或失敗的信息.Step 1 Set k = 1;Step 2 While ( k Nmax) do steps 3-6Step 3 For i = 1, , n Set ; /* 計(jì)算計(jì)算 xk */Step 4 If then Output (X ); STOP; /* 成功成功 */Step 5 For i = 1, , n Set X 0 = X ; /* 更新更新 X0 */ Step 6 Set k +;Step 7 Output (超過最大迭代次數(shù)超過最大迭代次

27、數(shù)); STOP. /* 失敗失敗 */bxA )0(xiinjijjijiiaXabX 1)0(TOLXXXXiini |0|max|0|1如果如果 aii = 0，怎么辦怎么辦?迭代過程中，迭代過程中，A 的元素的元素不改變，故可以不改變，故可以事先調(diào)整事先調(diào)整好好 A 使得使得aii 0，否則否則 A不可逆不可逆。必須等必須等X X( (k k) )完全計(jì)算完全計(jì)算好了才能計(jì)算好了才能計(jì)算X X( (k k+1)+1)，因此，因此需要需要兩組向量兩組向量存儲。存儲。上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院84 Gauss - Seidel 迭代方法迭代方法)(11)(1)(41

28、4)(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 只存一組向量即可。只存一組向量即可。寫成寫成矩陣形式矩陣形式：bDxUxLDxkkk1)()1(1)1()( bxUxLDkk )()1()(bLDxULDxkk1)(1)1()()( BfGauss-Seidel 迭代陣迭代陣

29、上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院85例例 求方程組求方程組1235131241246113xxx 的的GaussSeidel迭代格式。迭代格式。上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院861235131241246113xxx 1232133121(13)51(22)41(346)11xxxxxxxxx (1)( )( )123(1)(1)( )213(1)(1)(1)3121(13)51(22)41(346)11kkkkkkkkkxxxxxxxxx 上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院87 松弛法松弛法 換個角度看換個角度看Gauss - Seide

30、l 方法：方法： nijkjijijkiijiiikixaxabax1)(11)1()1(1iikikiarx)1()( 其中其中ri(k+1) = ijijkjijkjijixaxab)()1(殘量殘量相當(dāng)于在相當(dāng)于在 的基礎(chǔ)上的基礎(chǔ)上加個余項(xiàng)加個余項(xiàng)生成生成 。)(kix)1( kix下面令下面令 ，希望通過選取合適的，希望通過選取合適的 來來加速收斂，這就是加速收斂，這就是松弛法松弛法 。iikikikiarxx)1()()1( 0 1(漸次漸次)超松弛法超松弛法 上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院88 寫成寫成矩陣形式矩陣形式：iikikikiarxx)1()()1(

31、)1()()1(1)()1(bxUxLDxxkkkk bLDxUDLDxkk 1)(1)1()()1()( Hf松弛迭代陣松弛迭代陣 ijikjijijkjijiikibxaxaax)1()()1()( 上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院89例例 求方程組求方程組1235131241246113xxx 的的SOR迭代格式。迭代格式。1235131241246113xxx 解解上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院901232133121(13)51(22)41(346)11xxxxxxxxx (1)( )( )( )1231(1)(1)( )( )2132(1)(1

32、)(1)( )31231(13)(1)51(22)(1)41(346)(1)11kkkkkkkkkkkkxxxxxxxxxxxx 上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院91的收斂條件的收斂條件fxBxkk )()1(*)1()1(xxekk )()()(*)()*()(kkkeBxxBfxBfxB )0()(eBekk |.|)0() 1()(eBeBekkk 充分條件充分條件: |B| 1 kBk as0|0|)(ke必要條件必要條件:kkBke as0)(00 迭代法的收斂性迭代法的收斂性*xBxf 上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院920|xBk對對任意非零向

33、量任意非零向量 成立成立x迭代迭代證明：證明：Bk 0| Bk | 00|max0 xxBkx0 xBk對對任意非零向量任意非零向量 成立成立x從任意從任意 出發(fā)，出發(fā)， 記記 ，則，則)0(x*)0()0(xxe 0)0()( eBekkas k )( kx收斂收斂設(shè)設(shè)fxBx 存在唯一解，則從任意存在唯一解，則從任意 出發(fā)，出發(fā)， )0(xfxBxkk )()1(收斂收斂0kB ( ( B ) 1 ) 1定理定理上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院93 （充分條件）（充分條件）若存在一個矩陣范數(shù)使得若存在一個矩陣范數(shù)使得 | B | = q 1, 則則迭代收斂，且有下列誤差估

34、計(jì)：迭代收斂，且有下列誤差估計(jì)：證明：證明：)*()*(*)1()()()1()( kkkkkxxxxBxxBxx|)|*(|*|)1()()()( kkkkxxxxqxx )(.)()0()1(1)2()1()1()(xxBxxBxxkkkkk |)0()1(1)1()(xxqxxkkk |1|*|)1()()( kkkxxqqxx|1|*|)0()1()(xxqqxxkk 定理定理上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院94 證明：證明：首先需要一個引理首先需要一個引理 若若A 為嚴(yán)格對角占優(yōu)陣，則為嚴(yán)格對角占優(yōu)陣，則det(A) 0，且所有的，且所有的 aii 0。 證明：證明

35、：若不然，即若不然，即det(A) = 0，則，則 A 是奇異陣。是奇異陣。存在非零向量存在非零向量 使得使得 Tnxxxx),(210 .00 xA記記|max|1inimxx niiimxa10 miimmmiiimmmmaxxaxa|我們需要對我們需要對 Jacobi 迭代和迭代和 Gauss-Seidel迭代分別迭代分別證明：任何一個證明：任何一個| | 1 都都不可能不可能是對應(yīng)迭代陣的是對應(yīng)迭代陣的特征根，即特征根，即 | I B | 0 。Jacobi: BJ = D 1( L + U )| )(|1ULDIBI | | )(|11ULDDULDD aii 0ijaija nna

36、a 11如果如果 | | 1 則則 ijijiiiiaaa| 是嚴(yán)格對角占優(yōu)陣是嚴(yán)格對角占優(yōu)陣| I B | 0 關(guān)于關(guān)于Gauss-Seidel迭代的證明迭代的證明與此類似。與此類似。 （充分條件）（充分條件）若若A 為為嚴(yán)格對角占優(yōu)陣，嚴(yán)格對角占優(yōu)陣， 則解則解 的的Jacobi 和和 Gauss - Seidel 迭代均收斂。迭代均收斂。bxA 定理定理上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院95 （充分條件）（充分條件）若若A 為為不可約對角占優(yōu)陣，不可約對角占優(yōu)陣，則解則解 的的Jacobi 和和 Gauss - Seidel 迭代均收斂。迭代均收斂。bxA 定理定理上一頁

37、上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院96 若線性方程組若線性方程組 的系數(shù)矩陣的系數(shù)矩陣 是是對角元素為正的實(shí)對稱陣，則對角元素為正的實(shí)對稱陣，則Jacobi方法收斂的充方法收斂的充分必要條件是分必要條件是 和和 同時正定同時正定.AXb AA2DA 設(shè)線性方程組設(shè)線性方程組 的系數(shù)矩陣的系數(shù)矩陣 為為實(shí)對稱正定的，則實(shí)對稱正定的，則G-S方法收斂方法收斂 .AXb A定理定理定理定理上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院97 JacobiJacobi方法和方法和GSGS方法的收斂條件大多數(shù)是互不包含的方法的收斂條件大多數(shù)是互不包含的. . 二種方法都存在二種方法都存在收斂

38、性問題收斂性問題。 Gauss-Seidel方法收斂時，方法收斂時，Jacobi方法可能不收斂；方法可能不收斂； 而而Jacobi方法收斂時，方法收斂時， Gauss-Seidel方法也可能不收斂。方法也可能不收斂。上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院98例例：給出方程組：給出方程組 其中其中,iiA xb 1,2,i 1122111,221A 2211111112A 問問:Jacobi:Jacobi迭代法和迭代法和Gauss-SeidelGauss-Seidel迭代法是否收斂？迭代法是否收斂？解：解：11A xb 對對022101,220JB 022021086GB 上一頁上一

39、頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院993det()0JIB ()0JB 2det()(44)0GIB 而而12,30, 22 2 ()22 2GB 即即所以，對所以，對11,A xb JacobiJacobi方法收斂，方法收斂，G-SG-S方法發(fā)散方法發(fā)散 同理，對于同理，對于22,A xb 2211111112A 其中其中上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院10001/21/2101,1/21/20JB 01/21/201/21/2001/2GB 35det()04JIB 2,35 / 2i 10 , ()5/2JB 即得即得2det()(1/2)0GIB 而而12,30

40、,1/2 上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院101()1/2GB 則則22,A xb 所以，對所以，對Jacobi方法發(fā)散，方法發(fā)散，G-S方法收斂方法收斂. 上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院102 設(shè)設(shè) A 可逆，且可逆，且 aii 0，松弛法從任意松弛法從任意 出發(fā)對出發(fā)對某個某個 收斂收斂 ( ( H ) 1 ) 1。)0(x H 的計(jì)算是太復(fù)雜，的計(jì)算是太復(fù)雜， 譜半徑難于獲得譜半徑難于獲得! 定理定理上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院103 （Kahan 必要條件）必要條件）設(shè)設(shè) A 可逆，且可逆，且 aii 0，松弛法松弛法 從任意

41、從任意 出發(fā)收斂出發(fā)收斂 0 0 2 2 。)0(x證明：證明：從從 出發(fā)出發(fā))1()(1UDLDH niiH1)det( 利用利用，而且收斂，而且收斂 | | i | 1 | 1 總成立總成立可知收斂可知收斂 | | det(H ) | 1| 1 niiiaLDLD111)det(1)det( niiinaUD1)1()1det( nH)1()det( | | det(H ) | | 1 | | 1 |n 1 1 0 0 2 2 定理定理上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院104 （Ostrowski-Reich 充分條件）充分條件）若若A 對稱正定，且有對稱正定，且有 0 0 2 2，則，則松弛法從任意松弛法從任意 出發(fā)收斂出發(fā)收斂。)0(x定理定理上一頁上一頁下一頁下一頁湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院105Q: 什么因素決定收斂的速度什么因素決定收斂的速度?A: ( ( B )