【正文】 第三章 線性方程組求解的數(shù)值方法 求解 bxA ?? ?線性方程組的基本概念 2 3 21 2 31 3 21 2 30 3 1 01 2 31?016x x xx x xx x x???? ? ? ??? ? ? ??? ? ? ??1 2 31 2 3232 3 21 2 331 2 33 1 0231 0 2 3 2 l n ( 1 0 )1 3 06 3 1 0 l n ( 6 )x x xx x xxxe x x xe x x xe x x??????? ? ? ? ??? ?? ? ? ? ????? ? ? ? ???? 將一般方程組轉(zhuǎn)化為線性 方程組 ： – 如：取 log，將乘法轉(zhuǎn)化為加法，得到線性方程組。 12212121212122 3 1( 2 3 ) 1012 3 1 0xxxxxxxxexxxx???? ?? ??????? ??? ? ??? ????克萊姆（ Cramer）法： ——一種解線性代數(shù)方程組的直接法 1 1 1 1 2 2 1 12 1 1 2 2 2 2 21 1 2 2 nnnnn n n n n nna x a x a x ba x a x a x ba x a x a x b? ? ? ???? ? ? ?????? ? ? ??階 線 性 方 程 組 ： [ ] , X ,11TnnijAX bTA nn , , ) , , )( x ( bxbab??? ? ?矩 陣 表 示 記 為這 里 de t ( ) 0de t ( ) ( 1 , 2 , , )de t ( )iiAAx i nA???根 據(jù) 克 萊 姆 (cramer) 法 則 ， 若 方 程 組 系 數(shù) 行 列 式 不 為 零 ，即 ， 則 該 方 程 組 有 唯 一 解 。 其 解 為1 ( 1 ) !nn n nnn???這 種 方 法 需 要 計 算 行 列 式 并 作 ， 而 每 個階個 階 次 除行 列 式 計 算 需 作法次 乘 法 。353 0 , 2 . 3 8 1 0nn??如 需 次 乘 法 。 理 論較 大 時 ， 實上 是 絕 對 正 確際 計 算，但 不 可 行 。計 算 量 十 分 驚 人 !!在實際中 如何利用計算機 這一強有力工具求解線性方程？ 167。 消元法 ——計算機解線性方程組的一種直接法 思路： 1） 先將 A化為上三角陣 (消元 ) 2）再回代求解 。 (回代 ) = 高斯消元法 消元 記 ,)( )1()1(nnijaAA ???????????????)1()1(1)1(...nbbbb??Step 1： 設(shè) ，計算因子 0)1(11 ?a ).. .,2(/ )1(11)1( 11 niaam ii ??將增廣矩陣 第 i 行 ? mi1 ? 第 1行 ，得到 )1(1)1(1)1(12)1(11 .. . baaa n)2(A )2(b? ).. .,2,()1(11)1()2()1(11)1()2(njibmbbamaaiiijiijij????????其中 Step k： 設(shè) ，計算因子 且計算 0)( ?kkka ). .. ,1(/ )()( nkiaam kkkkikik ???). .. ,1,()()()1()()()1(nkjibmbbamaakkikkikikkjikkijkij???????????共進(jìn)行 ？ 步 n ? 1 ?????????????????????????????????????????)()2(2)1(121)()2(2)2(22)1(1)1(12)1(11.......... . .. . .. . .nnnnnnnnbbbxxxaaaaaa回代 )()( / nnnnnn abx ?0)( ?nnna 如果 ? 沒有唯一解 . )1. .. ,1()( 1)()(??????? niaxabx iiinijjiijiii)iii如果 ? 定理 若 A的所有 順序主子式 均不為 0，則高斯消元無需換行即可進(jìn)行到底，得到唯一解。 iiiiiaaaaA. ... ... ... ... ..)d e t (1111?注 ： 事實上，只要 A 非奇異，即 A?1 存在，則可通過逐次消元及行交換，將方程組化為三角形方程組，求出唯一解。 ? 消去法是按照系數(shù)矩陣的主對角線上的元素（主元）進(jìn)行消元。從而可能出現(xiàn)： （ 1）某個 主元為零 ，導(dǎo)致消元過程無法進(jìn)行。 （ 2）當(dāng)某個 主元的絕對值很小 時，計算結(jié)果誤差很大。 問題 ? 例： 單精度解方程組 ????????211021219xxxx 精確解為 和 ...1000...101191?????? ?x8個 ...8999... 12 ?????? xx8個 用單精度 (8位 )高斯消元法計算： 9112121 10/ ?? aam? 9992122 10101010... ???????? ?ma8個 9212 1012 ????? ?mb?????? ????9991010011100,1 12 ??? xx原因： 小主元 導(dǎo)致計算失敗 。 （大數(shù)吃小數(shù)） （大數(shù)吃小數(shù)） （結(jié)果差異很大） 全主元消去法 每一步選絕對值最大的元素為主元素 ，保證 。 1|| ?ikmStep k: ① 選取 | | m a x | | 0 。kki j ijk i nk j naa??????② If ik ? k then 交換第 k 行與第 ik 行 。 If jk ? k then 交換第 k 列與第 jk 列 。 ③ 消元 注 ： 列交換改變了 xi 的順序，須記錄 交換次序 ，解完后再換回來。 列主元消去法 省去換列的步驟 ，每次僅選一列中最大的元。 0||m a x|| , ?? ?? iknikki aa k 交換第 k 行與第 ik 行 。 在 第 k～ n行，第 k～ n列選擇 kkija在第一行是個小數(shù)，仍是小主元 導(dǎo)致計算失敗 例： ?????? ?2111110 91,1 12 ??? xx??????? 110211??????? ? 11102119? 注 ： 列主元法 沒有全主元法穩(wěn)定 。 0,1 12 ??? xx例： ??????21110101 99????????? 99991010010101注意：這兩個方程組在數(shù)學(xué)上 嚴(yán)格等價 。 ? 取 a21為主元，避免大吃小 (G a u s s L U由 消 元 法 加 上 列 主 元 或 全 主 元 ） 法 有 分 解 ：用矩陣?yán)碚摲治鱿ǎ? 矩陣三角分解法 11 12 1n21 22 2n31 321 2 ( 1) nn111 U 1n n n nA L ULu u ul uulll l l u???? ???? ???? ?????? ??????L——單位下三角矩陣 U——上三角矩陣 11 12 13 14 11 12 13 142121 22 23 24 22 23 4431 3231 32 33 34 33 3441 42 4341 42 43 44 441 0 0 01 0 0 010 001 0 0 0a a a a u u u ula a a a u u ulla a a a uul l la a a a u?? ?????? ??????? ?????? ???? ?? ????11 12 13 1421 11 21 12 22 21 13 23 21 14 2431 11 31 12 32 22 31 13 32 23 33 31 14 32 24 3441 11 41 12 42 22 41 13 42 23 43 33 41 14 42 24 43 34 44u u u ul u l u u l u u l u ul u l u l u l u l u u l u l u ul u l u l u l u l u l u l u l u l u u??? ? ??? ? ? ? ???? ? ? ? ? ???直接計算 A 的 LU 分解： 1 2 1 2 1 1 1 3 1 3 1 1 1 4 1 4 1 1 1i1 1 1 1 , , 。 , i 2 , ,nil l a u l a u l a ul a u?????列1 1 1 1 1 1 2 1 2 1 3 1 3 1 4 1 41 j 1 , , , 。 , j 1 , ,n ju u a u a u a u aua? ? ? ???行直接比對等式兩端矩陣元素 22 22 21 12 23 23 21 13 24 24 21 142j 2 21 132 32 31 12 22 42 42 41 12 22i2 2u2 , , 。 , j 2, ,n 2 ( ) , ( ) 。 ( jjilu a l u u a l u u a l uu a l ul a l u u l a l u ula? ? ??????行列i2 12 22) i 3, , n .l u u ?i1 1 1111 , i 2 , , j 1 , ,n , njjiual a u????k 1ikk 1kj kmkmim km11 j k , 2 , 3 , , ( ) / i k 1, , , n n ik m kk j m jknu a ll a l u uu??? ? ??? ? ? ???對 計 算一般計算公式： LU分解系數(shù)的計算順序 2131413242 433 3 31 1 1 2 1 32 2 2 3 4 42 1 1 3 2 3 21 1 1 2 1 3 1 42 1 22 1 1 1 2 1 1 2 22 2 3 2 43 1 3 2 3 3 3 44 1 4 2 4 3141 1 1 2 1 3 1 41442 144441 0 0