《數(shù)值分析第二章》ppt課件

1、2.1 Gauss2.1 Gauss消去法消去法u高斯消元法步驟高斯消元法步驟： (1) 首先將增廣陣 A, b 化為上三角陣; (2) 用三角方程組，回代求解 .例例1 1 用消去法解方程組12323123 645221xxxxxxxx(1)(2)(3)解解 (1) 化上三角方程組12323123 645221xxxxxxxx 1232323 645411xxxxxxx +(-2) + 123233 64526xxxxxx 123233 64526xxxxxx (2)回代過程. 得到同解方程組后,如下求解3( 6)/( 2)3x 從下向上逐步求解從下向上逐步求解把x3的值代入求x2用x3,

2、x2的值求x1235 / 42xx1236()1xxx上三角方程組上三角方程組：對(duì)應(yīng)增廣陣的變化1116(| )04152211A b1116041504111111604150026(-2)r1 + r3 r3r2 + r3 r3上三角上三角陣陣u高斯消元法的基本思想將原方程組逐次消去未知元， 變?yōu)榕c之同解的上三角方程組， 再回代求解 。n用矩陣語(yǔ)言敘述是，僅用行初等變換把增廣陣約化為上三角陣，對(duì)上三角方程組，回代求解 。 u高斯消元法的一般性敘述高斯消元法的一般性敘述11121121222212nnnnnnnaaabaaabaaab(1)(1)(1)(1)111211(2)(2)(2)22

3、22( )( )000nnnnnnnaaabaabab用行變換用行變換根據(jù)下面的上三角方程組,逐次回代求解 xk(1)(1)(1)(1)11111221(2)(2)(2)22222(1)(1)(1)1,11,1( )( ) nnnnnnnnnnnnnnnnnnnnba xa xa xbaxaxaxaxbaxb(2.5)11nnxxx2.1.1 2.1.1 順序順序GaussGauss消去法消去法在使用高斯消去法的過程中，僅對(duì)方程組做行倍加變換，就是順序高斯消去法。1.1.消元過程消元過程對(duì)于 k =1,2,n -1 執(zhí)行(1)如果 ,則算法失效,停止計(jì)算;否則轉(zhuǎn)(2)(2)對(duì)于 i = k +

4、1,k +2,n 計(jì)算 ( )0kkka(1)(1)( ,1,2,., );(1,2,., ).ijijiiaai jnbbinn 算法算法如下：記( )( )(1)( )( )(1)( )( )(1,2,., )/kkikikkkkkkijijikkjkkkiiikkjkknmaaaam abbm b(1)(1)(1)(1)11121( )( )( )( )( ),( )( )( ),00,0000nkkkkkk kk nkkkkn kn nnaaabAbaabaab Mi k 行乘數(shù)行乘數(shù)(1)(1)(1)(1)11121( )( )( )( )( ),(1)(1)(1),(1)(1)(1

5、),0000,0000nkkkkkk kk nkkkkk kk nkkkkn kn nnaaabaabAbaabaab第第 k 次消元后次消元后, 增廣陣變?yōu)樵鰪V陣變?yōu)?.2.回代過程回代過程( )( )( )( )( )1/(1,2,.,1)nnnnnnnkkkkkkjjkkj kxbaxbaxaknn 順序高斯消去法求解n 元線性方程組的乘除運(yùn)算總次數(shù)為32(3)/3nnn順序高斯消去法計(jì)算過程中出現(xiàn)的 稱為主元素主元素. 出現(xiàn) 消元過程就進(jìn)行不下去了.( )kkka( )0kkka即使 detA 0，也可能對(duì)某個(gè) k n， 出現(xiàn) . 下面的定理給出了避免出現(xiàn)這種情況的條件。( )0kkk

6、a定理定理2.1 順序高斯消去法的前順序高斯消去法的前 n1 個(gè)主元個(gè)主元 均均不為零的充要條件是不為零的充要條件是 Ax b 的系數(shù)矩陣的系數(shù)矩陣 A 的前的前 n 1個(gè)順序主子式個(gè)順序主子式( )kkka(1)(1)(1)11121(1)(1)(1)21222(1)(1)(1)120(1,2,.,1).kkkkkkkaaaaaaDknaaa證證 因?yàn)? 第 k 個(gè)順序主子式 Dk 等于前 k 個(gè)主元之積!(1)(2)( )1122.kkkkDa aa例子例子此式 解釋又第 k 個(gè)主元被順序主子式所確定:(1)111( )1,/,2,3,., .kkkkkaDaDDkn注解注解：方程組(2.

7、1) 的系數(shù)矩陣 A 的 n 個(gè)順序主子式 Dk 均不為零，保證了主元均不為零, 使順序消去法得以進(jìn)行。 但，當(dāng)遇到某個(gè)主元的絕對(duì)值很小時(shí)，將使行乘行乘數(shù)數(shù) -mik 的絕對(duì)值很大，則舍入誤差的積累會(huì)很大，計(jì)算出的近似解會(huì)有很大的誤差。順序高斯消去法的數(shù)值穩(wěn)定性是沒有保證的順序高斯消去法的數(shù)值穩(wěn)定性是沒有保證的! 順序主元消去法可能計(jì)算失敗之例順序主元消去法可能計(jì)算失敗之例例：例：?jiǎn)尉冉夥匠探M 211021219xxxx/* 精確解為 和 */.1000.00. 1101191 x8個(gè)個(gè).8999.99. 0212 xx8個(gè)個(gè)用Gaussian Elimination計(jì)算：911212110

8、/ aam999212210101010.0 . 011 ma8個(gè)個(gè)92121012 mb 9991010011100, 112 xx 小主元 /* Small pivot element */可能導(dǎo)致計(jì)算失敗。大數(shù)吃小數(shù)!2.1.2 2.1.2 列主元列主元 Gauss Gauss 消去法消去法定義定義 使用高斯消去法的過程中，在第使用高斯消去法的過程中，在第 k 次消元前，先對(duì)次消元前，先對(duì)第第 k 個(gè)增廣陣個(gè)增廣陣 A(k), b(k) 做交換二行的變換，把做交換二行的變換，把 中絕對(duì)值最大的元素?fù)Q到中絕對(duì)值最大的元素?fù)Q到 (k, k) 位置，再消元。此方法位置，再消元。此方法叫叫列主元

9、高斯消去法列主元高斯消去法。其算法如下：記(1)(1)( ,1,2,., );(1,2,., ).ijijiiaai jnbbin1.1.消元過程消元過程對(duì)于k =1,2,n -1執(zhí)行(1)選行號(hào)ik，使(2)交換第 k 行與第 ik 行（中數(shù)值）。 ( )( )max.kkki kikk i naa ( )(,1,., )kikaik kn(3)(3)對(duì)于 i = k +1,k +2,n 計(jì)算 ( )( )(1)( )( )(1)( )( )/(1,2,., )kkikikkkkkkijijikkjkkkiiikkmaaaam ajkknbbm b2.2.回代過程回代過程( )( )( )(

10、 )( )1/(1,2,.,1)nnnnnnnkkkkkkjjkkj kxbaxbaxaknn 注解注解：此算法中的 稱為第 k 個(gè)列主元素，它的值總要被換到位置 (k, k) 。( )(1,2,.,1)kki kakn定理定理2.2 設(shè)方程組設(shè)方程組 (2.1) 的系數(shù)矩陣的系數(shù)矩陣 A 非奇異，則用非奇異，則用列主元素消去法求解方程組時(shí)，各個(gè)列主元素列主元素消去法求解方程組時(shí)，各個(gè)列主元素 均不為零。均不為零。( )kki ka證證 設(shè)有一個(gè)列主元素 為零，當(dāng)消元進(jìn)行到第 r 次時(shí)，由行列式性質(zhì)，容易知道，系數(shù)矩陣 A 的行列式有下面的形狀:( )rri ra矛盾于矛盾于 A 非奇異非奇異

11、。第第r 行行 r 列下方列下方元素全為元素全為0 0評(píng)論評(píng)論：列主元素消去法，所需條件較少，僅僅要求方程組的系數(shù)矩陣 A 非奇異。 而且，對(duì)一般的方程組，它還具有良好的數(shù)值穩(wěn)定性，其計(jì)算量與順序消去法的計(jì)算量相當(dāng)。例例1 在四位十進(jìn)制的限制下，分別用 順序消去法 與 列主元素消去法 求解下列方程組1231231230.012 0.0100.1670.67810.83345.91012.132001200 4.2981xxxxxxxxx解解 用順序消去法的消元過程：0.01200.0100.16700.67811.0000.83345.91012.10320012004.200981.0320

12、.01200.0100.16700.678100.1000 108.01044.41014674454 101798 103550.01200.0100.16700.678100.1000 108.01044.41001175 106547 103215.546,100.0,104.0 xxx 回代后，得(-1/0.012)r1 + r2 r2(-3200/0.012)r1 + r3 r3完全失真完全失真 !1231231230.012 0.0100.1670.67810.83345.91012.132001200 4.2981xxxxxxxxx原方程組：3215.546,100.0,104.

13、0 xxx 近似解：近似解：把上近似解代入第 3 個(gè)方程后，得3200(-104)+1200100 +4.25.546 = -2.1278e+005檢驗(yàn)檢驗(yàn)列主元素列主元素2320012004.200981.000.45845.90911.7900.5500 100.16700.67440.01200.0100.16700.67811.0000.83345.91012.10320012004.200981.0列主元素法的消元過程：列主元素法的消元過程：3215.546,45.76,17.46xxx 回代后，得列主元素列主元素320012004.200981.000.45845.90911.79

14、000.096090.5329由此看出，列主元法的精度明顯高于順序消去法列主元法的精度明顯高于順序消去法 !1231231230.012 0.0100.1670.67810.83345.91012.132001200 4.2981xxxxxxxxx原方程組：3215.546,45.76,17.46xxx 近似解：把上近似解代入第 3 個(gè)方程后，得320017.46 +1200(-45.76)+4.25.546 = 983.2932983.2932檢驗(yàn)檢驗(yàn)數(shù)學(xué)符號(hào) x0 x1, , xm, 0 x,1x, , nx, , a x0 x1 xmb , f (x) a0 a1x amxma1 a2 ak a1, , am,L0 x, L1x, , Lnx, k=0,1, , n (x) , x0 n 20 a x b k 1, nm, q 0, q 1, (a) 0 n k 0 f (x)Ca, b (xj,yj),j=0,1,m, A, A