第3章301高斯消元法,列主元法

1、第第3 3章章 線性代數(shù)方程組的數(shù)值解法線性代數(shù)方程組的數(shù)值解法3.1 3.1 高斯消去法高斯消去法3.2 3.2 矩陣三角分解法矩陣三角分解法3.3 3.3 平方根法平方根法3.4 3.4 向量和矩陣的范數(shù)向量和矩陣的范數(shù)3.5 3.5 迭代法迭代法3.6 3.6 迭代法的收斂性迭代法的收斂性3.7 3.7 方程組的形態(tài)和誤差分析方程組的形態(tài)和誤差分析 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111 矩陣形式矩陣形式 Ax=b,其中其中1112111212222212,nnnnnnnnaaaxbaaaxbxaaaxbAbn n個未知量個

2、未知量n n個方程的線性代數(shù)方程組個方程的線性代數(shù)方程組11,2,nijjija xbin或?qū)懗苫驅(qū)懗?若矩陣A非奇異，方程組有惟一解，可用克萊姆（Cramer）法則求解 kkDxD， （1,2,kn） 其中detDA，kD是用向量b代替A的第k列后所得矩陣的行 列式。 克萊姆法則解線性方程組的計算量（乘法次數(shù)） (1)! (1)(1) !(1)nSnnnnn 例如20n ，乘法次數(shù)為2110。計算量很大！ 兩類數(shù)值解法：兩類數(shù)值解法： 直接解法直接解法: :假定計算過程沒有舍入誤差的情況下，假定計算過程沒有舍入誤差的情況下，經(jīng)過有限步算術運算后能求得線性方程組精確解的經(jīng)過有限步算術運算后能求

3、得線性方程組精確解的方法。經(jīng)過有限步運算就能求得精確解的方法，但方法。經(jīng)過有限步運算就能求得精確解的方法，但實際計算中由于舍入誤差的影響，這類方法也只能實際計算中由于舍入誤差的影響，這類方法也只能求得近似解；例如：求得近似解；例如：高斯消去高斯消去法法、三角分解、三角分解法等。法等。 迭代解法迭代解法: : 構造適當?shù)南蛄啃蛄?，用某種極限構造適當?shù)南蛄啃蛄校媚撤N極限過程去逐步逼近精確解。例如：過程去逐步逼近精確解。例如：雅可比迭代雅可比迭代法、法、高高斯斯- -賽德爾迭代賽德爾迭代法等。法等。上三上三 角形方程組角形方程組 回代求解，得回代求解，得 3211,0,1xxxnnnnnnnnyx

4、uyxuxuyxuxuxu22222112121114 5 6 10 2 3 3 7 71232334561023377xxxxxx33232132112532yxyxxyxxx2/32/12/1321 xxx1121237723245610 xxxxxx1231,0,1xxx下三角形方程組下三角形方程組 順代可求得順代可求得 7 72 3 24 5 6 10323721321211yyyyyy1891321 yyy1223345423377xxxxx3211,0,1xxx上二對角方程組上二對角方程組 回代求解，得回代求解，得 4 5 0 4 2 3 3 7 7nnnnnndxdxcxdxcx

5、dxcx1112322121111121222321,11,nnnnnnnuuduuduuud1122377464233xxxxx1231,0,1xxx下二對角方程組下二對角方程組 順代可求得順代可求得 7 7 6 0 440 2 3 33.1 高斯消去法高斯消去法 3.1.1 順序順序高斯消去法高斯消去法 ( (按方程和未知量的自然順序進行按方程和未知量的自然順序進行) )基本思想：用逐次消去未知數(shù)的方法把原方程組化為基本思想：用逐次消去未知數(shù)的方法把原方程組化為上三角形上三角形方程組進行求解方程組進行求解 。求解求解 分成兩步：分成兩步： 1.1.消元消元過程：用過程：用初等行變換初等行變

6、換將原方程組的系數(shù)矩陣將原方程組的系數(shù)矩陣化為上三角形矩陣（簡稱上三角陣）?；癁樯先切尉仃嚕ê喎Q上三角陣）。 2.2.回代回代過程：對上三角形方程組的最后一個方程求過程：對上三角形方程組的最后一個方程求解，將求得的解逐步往上一個方程代入求解。解，將求得的解逐步往上一個方程代入求解。 順序高斯消去法消元過程順序高斯消去法消元過程: : 依從左到右、自上而下的次序?qū)⒅鲗窃路降脑鼗癁榱?。依從左到右、自上而下的次序?qū)⒅鲗窃路降脑鼗癁榱恪?1 1 不作行交換。不作行交換。 2 2 用不等于零的數(shù)乘某行，加至另一行。用不等于零的數(shù)乘某行，加至另一行。 用高斯消去法解下列線性方程組 52262

7、342321321321xxxxxxxxx 解解 對 線 性 方 程 組 第 1 次 消 元 ，0211a， 確 定 乘 數(shù)5 . 021112121aam，5 . 021113131aam，則有 ) 1 ()3() 1 ()2(3121mm35 . 15 . 1045 . 15 . 2042321321321xxxxxxxxx，第 2 次消元，05 . 222a，確定乘數(shù)6 . 05 . 25 . 1223232aam，有 )2()3(32 m6 . 06 . 00045 . 15 . 2042332321xxxxxx 回代 3211,1,1xxx 系數(shù)行列式的計算：系數(shù)行列式的計算： (1

8、)(2)( )1122detnnnAa aa例例 211132122A消元過程消元過程 主元為主元為 2，2.5，0.6 det A = 22.50.6 = 3 2112.51.50.6A 引進記號 (1)(1)(1)11121(2)(2)222( )( )( )( )( )nnkkkkkknkkknnnaaaaaAaaaa ，(1)1(2)2( )( )( )kkkknbbbbb，(1,2, )kn 矩陣形式 ( )( )kkAxb，(1,2, )kn 設 主元(1)(2)( )11220,0,0nnnaaa 消元過程 ( )( )(1,2,1),(1,2, ) ( )kikikkkkika

9、mknikknaimki 消元過程消元過程設 主元(1)(2)( )11220,0,0nnnaaa 消元過程 ( )( )(1)( )( )()( )( )(1,2,1)( ,1,2, ) kikikkkkkkkijijikkjkkkiiikkamknaaam ai jkknbbm b 回代過程回代過程上三角形方程組( )( )nnA xb求解過程 ( )( )( )( )1( )nnnnnnniiiijjj iiiiibxaba xxa ， （1,2,1inn ） 順序高斯消去法的順序高斯消去法的使用條件使用條件 使用條件之一使用條件之一 定理定理 線性方程組系數(shù)矩陣線性方程組系數(shù)矩陣A A

10、的順序主子矩的順序主子矩陣陣A Ak k ( (k k=1,2,=1,2,n n) )非奇異非奇異 ，則順序高斯消去法能，則順序高斯消去法能實現(xiàn)方程組的求解。實現(xiàn)方程組的求解。 即方程組能用順序高斯消去法求解的即方程組能用順序高斯消去法求解的充要條件充要條件是是系數(shù)行列式的順序主子式非零系數(shù)行列式的順序主子式非零。 高斯消去法能按順序進行到底的充要條件是高斯消去法能按順序進行到底的充要條件是 在原方程組的系數(shù)矩陣中如何反映出這個條件呢在原方程組的系數(shù)矩陣中如何反映出這個條件呢?( )0,1,2,kkkaknA的的k階順序主子矩陣階順序主子矩陣Ak的行列式的行列式 (1)1112111121(2

11、)(2)21222(1)(2)( )2221122( )120det00kkkkkkkkkkkkkkkaaaaaaaaaaaAa aaaaaa，nk, 2 , 1 使用條件之二使用條件之二 n階矩陣A為嚴格對角占優(yōu)矩陣是指其每個主對角元的絕對值大于同一行其他元素絕對值之和，即niaanijjjiii, 2 , 1,1 一階嚴格對角占優(yōu)矩陣指一個非零數(shù)。 定理 方程組系數(shù)矩陣A為嚴格對角占優(yōu)矩陣則可實現(xiàn)用順序高斯消去法求解。 順順序序高高斯斯消消去去法法的的計計算算量量 消元中各步需乘除法次數(shù) 第i步 乘法次數(shù) 除法次數(shù) 1 2(1)n 1n 2 2(2)n 2n 1n 1 1 合計 (1) (

12、 21)6nnn (1)2n n 3.1.2 列主元高斯消去法列主元高斯消去法 為什么列選主：數(shù)值不穩(wěn)定 當高斯消去法的主元當高斯消去法的主元 時時 , 盡管盡管“當當 A A 非奇異時，非奇異時，det A0det A0，方程組有唯一解，方程組有唯一解”，也不能實現(xiàn)，也不能實現(xiàn)高斯消去法求高斯消去法求解。解。 例例 ， A A 非奇異，非奇異，det A0det A0，方程組有，方程組有唯一解，但唯一解，但 ，不能實現(xiàn)，不能實現(xiàn)高斯消去法求解。高斯消去法求解。( )0kkka0111A(1)110a 高斯消去法的主元 ，但絕對值很小時，用絕對值小的數(shù)做除數(shù)，會導致其它元素數(shù)量級的嚴重增長和舍

13、入誤差的擴大。 ( )0kkka經(jīng)過1k 次消元后得到增廣矩陣( )( )(|)kkAb，在此增廣矩陣的第k列的元素( )( )( )1,kkkkkkknkaaa中選取絕對值最大的一個， 記為( )krka， 然后交換( )( )(|)kkAb中的第k行與第r行后，再進行第k次消元。 列選主元高斯消去法 ：避免用絕對值小的元素，作除數(shù)。每次消元前選取一列中絕對值最大的元素作為主元素。用這個主元素作除數(shù)，這樣便可以減少舍入誤差。 列選主元高斯消去法的優(yōu)越性，不增加求解過程的運算量，而大大減小誤差。例例 用列主元高斯消去法求解方程組用列主元高斯消去法求解方程組(用三位有效數(shù)字計算用三位有效數(shù)字計算

14、)解解123123123354157324422xxxxxxxxx 12rr 22113311rmrrmr 選主元選主元選主元選主元3215m 31m 455 7 3 23 5 4 -1 4 4 2 23 5 4 -1 , 5 7 3 2 4A b 4 2 25 7 3 200.8 2.2 -2.2 0.6.4 0.4 -1 -032rr573201.60.4 0.400.82.22.2320.80.51.6m 3322r m r 12323357321.60.40.422xxxxxx 3211,0,1xxx 消元過程完成，得到上三角形方程組消元過程完成，得到上三角形方程組 再作回代可求得再作回代可求得 573201.60.40.40022 行列式的計算：行列式的計算： (1)(2)( )1122d