【正文】 a l u u?????(行 ) 167。 三角分解法 11, , 1 , . . .kk j k j k m m jmu a l u j k k n??? ? ? ? ??(列 ) 11kik im m k ik k kma l u l u?????11( ) / , 1 , . . .ki k i k i m m k k kml a l u u i k n??? ? ? ? ??直到第 n步， A全部分解成 LU。 167。 三角分解法 167。 追趕法 ( Forward elimination and backward substitution ) 第三章 線性方程組解法 ? 在很多實(shí)際問題中，方程組 Ax=b的系數(shù)矩陣 A是一個稀疏矩陣。 167。 追趕法 1 1 12 2 2 21110 ... 0 0 0 0 0 0 0... 0 0 0 0 0 0 0... ... ... ... ... ... ... ... ... 0 0 ...0 0 0 0 0 0 0 0 ...... ... ... ... ... ... ... ... ... ... ... ...0 0 0 0 0 0 0 0 ...0 0 0 0 0 0 0 0 0iiinnnn n nb c xa b c xa b ca b ca b x???? ? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ?? ? ?? ? ? ?12............nddd?????????????????? ? ?? ? ???假設(shè)非零元素集中分布在對角線及其相鄰兩個次對角線上，且系數(shù)陣為對角占優(yōu)陣，即有： 11, 2 , 3 , ... 1i i innbcb a c i nba???? ? ? ?????167。 追趕法 把系數(shù)矩陣三角分解有 11222110 .. . 01 0 0 00 .. . 01 0 0, .. . .. . .. . .. . .. ... . .. . .. . .. .0 0 00 0 10 0 0 0nnnnqrqrpqrpq?????? ???? ???? ?????? ???? ????????LU167。 追趕法 利用 LU分解公式，寫出 1 1 1 111, 2 , 3 , .. .,kkk k kk k k kq b r crcp q aq p c b k n???????????? ? ? ??167。 追趕法 得到 11 , kkq b r c??11, , 2 , 3 , . . . ,kk k k k kkap q b p c k nq ??? ? ? ?于是 ,??L y d U x y得到 111 , 2 , 3 , . . . ,k k k kydy d p y k n????? ? ??167。 追趕法 1/1( ) , 1 , 2 , .. ., 1n n nk k k kkx y qx y c x k n nq?????? ? ? ? ???167。 追趕法 167。 其它應(yīng)用 第三章 線性方程組解法 ? 計(jì)算行列式值 167。 其他應(yīng)用 ?A L U11 22de t( ) de t( ) ... nnu u u??AU? 求矩陣逆 1? ?A A I11 12 121 22 212... 1 0 0 0... 0 1 0 0... ... ... ... ... ... ... ...... 0 0 0 1nnn n nnx x xx x xx x x?? ???? ???? ????? ???? ??????A分別由 120..., 1 , 2 , ...,... 10iinixxinix?? ???? ???? ?????? ?? ???? ??????A解出 xij, ij=1,2,…, n 于是 1ijx? ??? ??A167。 其他應(yīng)用 167。 誤差分析 (Error analysis) 第三章 線性方程組解法 167。 誤差分析 ? 定義： 設(shè) 為方程組 Ax=b的精確解，近似解與精確解之間的 誤差向量 定義為 * * * *12 ...Tnx x x??? ??x*1 11*2 *22*... ...n nne xxe xxe xx?? ????????????? ? ? ?????????????? ??e x x? 一種衡量近似解精確度的方法是把近似解 代入方程組，看 殘差向量 的大小。 *x??r b Ax于是 1 1 * 1? ? ?? ? ? ?x A b A r x A r*1 ?? ? ? ?e x x A r167。 誤差分析 由范數(shù)性質(zhì)有 11????e A r A r 而 * ?A x b*??b A x 1* ???Axb上面兩個式子相乘得 1*() ??erAAbx167。 誤差分析 這個式子左端計(jì)算的是近似解 x的相對誤差，而 是 相對殘差 。 /rb近似解的相對誤差小于相對殘差的一個倍數(shù)： 。這個倍數(shù)對于近似解的誤差估計(jì)很重要，定義為矩陣 A的 條件數(shù) 1?AA1()c on d ??A A A11 ( ) 1c o n d??? ? ? ?I A A A A A167。 誤差分析 ? 線性方程組 Ax=b的解 x*是由系數(shù)矩陣A和向量 b決定的，那么如果 A和 b有微小的變化 (擾動 )時，解會如何變化呢？ (1) 假設(shè) b有微小變化 ，此時解有變化 ，即 ?b*?x**() ??? ? ?A x x b b注意到 * ?A x b167。 誤差分析 于是 *???A x b 即 *1?? ??x A b兩邊取范數(shù)得 *1?? ???x A b*??b A x利用 得 *11*?? ?????? ? ? ?x A b A bAAbbx167。 誤差分析 (2) 假設(shè) A有微小變化 ，此時解有變化 ，即 ?A*?x**( ) ( )??? ? ?A A x x b整理并注意到 得 * ?A x b* * *()? ? ?? ? ?A x x A x 0即 * 1 * *()? ? ??? ? ? ?x A A x x兩邊取范數(shù)得 167。 誤差分析 即 * 1 * *? ? ??? ? ? ?x A A x x*11**? ?????? ? ? ? ??x AA A A AAxx于是從 (1),(2)兩種情況可以看出，如果 b或者 A有誤差，則解的相對誤差不超過它們相對誤差的 倍。 1?AA167。 誤差分析 Remark: 條件數(shù)刻畫了線性方程組的解對于初始數(shù)據(jù) (b,A)誤差的靈敏度，條件數(shù)是方程組的固有屬性，與求解該方程組的方法無關(guān)。對于病態(tài)方程組，一般不能得到令人滿意的結(jié)果。 167。 誤差分析 定義 為線性方程組的 條件數(shù) 1?AA? 當(dāng) 時，方程“病態(tài)”。 ( ) 1c o n d ??A? 通常使用的條件數(shù)有 1( 1 ) ( )c o n d ?? ? ??A A A1 m a x2 2 2m i n()( 2 ) ( )()TTc o n d????? AAA A AAA其中 是 ATA的絕對值最大、最小的特征值。 m ax m i n,??167。 誤差分析 ? 當(dāng) A對稱時 1()nc o n d???A 是 A的最大特征值， 是 A的最小特征值。 1? n?167。 誤差分析 Remark: 為了計(jì)算方程組的條件數(shù)，需要計(jì)算矩陣 A的逆陣，求逆陣的工作量很大，而且， 如果 A是病態(tài)時，其逆陣的計(jì)算也不準(zhǔn)確 。 (2)系數(shù)陣某些行 (列 )近似線性相關(guān) 167。 誤差分析 ? 判斷方程組病態(tài)的參考： (1)用選主元消去法求解時出現(xiàn)小主元 (3)系數(shù)陣元素量級相差很大 , 且無規(guī)則 本章小結(jié) 第三章 線性方程組解法 167。 小結(jié) ?迭代法： ?雅克比迭代法 ?高斯－塞德爾迭代法 ?超松弛迭代法 SOR。 ?追趕法。 ?直接解法： ?高斯消去法 ?高斯主元素消去法 ?三角分解法 LU ?其它應(yīng)用 ?條件數(shù) 167。 小結(jié)