【正文】 第三章 線性方程組求解的數(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???這 種 方 法 需 要 計(jì) 算 行 列 式 并 作 ， 而 每 個(gè)階個(gè) 階 次 除行 列 式 計(jì) 算 需 作法次 乘 法 。353 0 , 2 . 3 8 1 0nn??如 需 次 乘 法 。 理 論較 大 時(shí) ， 實(shí)上 是 絕 對(duì) 正 確際 計(jì) 算，但 不 可 行 。計(jì) 算 量 十 分 驚 人 !!在實(shí)際中 如何利用計(jì)算機(jī) 這一強(qiáng)有力工具求解線性方程？ 167。 消元法 ——計(jì)算機(jī)解線性方程組的一種直接法 思路： 1） 先將 A化為上三角陣 (消元 ) 2）再回代求解 。 (回代 ) = 高斯消元法 消元 記 ,)( )1()1(nnijaAA ???????????????)1()1(1)1(...nbbbb??Step 1： 設(shè) ，計(jì)算因子 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è) ，計(jì)算因子 且計(jì)算 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 如果 ? 沒(méi)有唯一解 . )1. .. ,1()( 1)()(??????? niaxabx iiinijjiijiii)iii如果 ? 定理 若 A的所有 順序主子式 均不為 0，則高斯消元無(wú)需換行即可進(jìn)行到底，得到唯一解。 iiiiiaaaaA. ... ... ... ... ..)d e t (1111?注 ： 事實(shí)上，只要 A 非奇異，即 A?1 存在，則可通過(guò)逐次消元及行交換，將方程組化為三角形方程組，求出唯一解。 ? 消去法是按照系數(shù)矩陣的主對(duì)角線上的元素（主元）進(jìn)行消元。從而可能出現(xiàn)： （ 1）某個(gè) 主元為零 ，導(dǎo)致消元過(guò)程無(wú)法進(jìn)行。 （ 2）當(dāng)某個(gè) 主元的絕對(duì)值很小 時(shí)，計(jì)算結(jié)果誤差很大。 問(wèn)題 ? 例： 單精度解方程組 ????????211021219xxxx 精確解為 和 ...1000...101191?????? ?x8個(gè) ...8999... 12 ?????? xx8個(gè) 用單精度 (8位 )高斯消元法計(jì)算： 9112121 10/ ?? aam? 9992122 10101010... ???????? ?ma8個(gè) 9212 1012 ????? ?mb?????? ????9991010011100,1 12 ??? xx原因： 小主元 導(dǎo)致計(jì)算失敗 。 （大數(shù)吃小數(shù)） （大數(shù)吃小數(shù)） （結(jié)果差異很大） 全主元消去法 每一步選絕對(duì)值最大的元素為主元素 ，保證 。 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 的順序，須記錄 交換次序 ，解完后再換回來(lái)。 列主元消去法 省去換列的步驟 ，每次僅選一列中最大的元。 0||m a x|| , ?? ?? iknikki aa k 交換第 k 行與第 ik 行 。 在 第 k～ n行，第 k～ n列選擇 kkija在第一行是個(gè)小數(shù)，仍是小主元 導(dǎo)致計(jì)算失敗 例： ?????? ?2111110 91,1 12 ??? xx??????? 110211??????? ? 11102119? 注 ： 列主元法 沒(méi)有全主元法穩(wěn)定 。 0,1 12 ??? xx例： ??????21110101 99????????? 99991010010101注意：這兩個(gè)方程組在數(shù)學(xué)上 嚴(yán)格等價(jià) 。 ? 取 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??? ? ??? ? ? ? ???? ? ? ? ? ???直接計(jì)算 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? ? ? ???行直接比對(duì)等式兩端矩陣元素 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??? ? ??? ? ? ???對(duì) 計(jì) 算一般計(jì)算公式： LU分解系數(shù)的計(jì)算順序 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