在沒有舍入誤差的情況下,經(jīng)過有限次運算可以得到方程組的

1、在沒有在沒有舍入誤差舍入誤差的情況下，經(jīng)過有限次的情況下，經(jīng)過有限次 運算可以得到方程組的運算可以得到方程組的精確解精確解的方法。的方法。 第六章第六章 線性方程組的數(shù)值解法線性方程組的數(shù)值解法 /*Numerical Method for Solving Linear Systems*/ 求解求解, n n AXB AR 0det()A Cramer法則法則: :1 2 det , , det i i A xin A 所需乘除法的運算量大約為所需乘除法的運算量大約為( (n+1)!+)!+n n=20時，每秒時，每秒1億億次運算速度的計算機要算次運算速度的計算機要算30多萬年！多萬年！ 直接

2、法直接法 6.2.1 Gauss消元法消元法/*Gaussian Elimination Method*/ 一、一、 基本基本Gauss消去法消去法 通過通過初等變換初等變換逐步消去未知元，將逐步消去未知元，將 原方程組化為原方程組化為同解同解的的三角三角方程組。方程組。 三角三角（系數(shù)矩陣）方程組易于求解（系數(shù)矩陣）方程組易于求解 11 2122 12 00 0 nnnn a aa aaa 11121 222 0 00 n n nn aaa aa a 取取 0 11 0 1 11 1 2 3 ( ) ( ) ( ) , , , j j a ajn a 00 1011 0 11 2 3 1 2

3、 3 ( )( ) ( )( ) ( ) , , , , , ji ijij inaa aa a jn 10 10 11 0 11 2 3 ( )( ) ( )( ) ( ) , , i ii ba bbin a Step 1第一列消元過程第一列消元過程：消去第一個方程以下各個方：消去第一個方程以下各個方 程的變量程的變量x1 11 2122 1 22 3 4 2 3 ( )( ) ( )( ) ( ) , , , , ji ijij inaa aa a jn 11 21 22 1 22 3 4 ( )( ) ( )( ) ( ) , , i ii ba bbin a Step 2第第2列消元

4、過程列消元過程：消去第：消去第2個方程以下各個方程個方程以下各個方程 的變量的變量x2 Step k：第第k步步消元消元過程的計算公式過程的計算公式 上三角上三角矩陣矩陣 11 1 1 12 1 ()() ( )() () , , kk kkkjik k ijij kk ikknaa aa a jk kn 11 1 1 1 ()() ( )() () , kk kk kik k ii kk ba bbikn a 1 21, ,kn 0000 111 11121 111 221 222 11 1 ( )( )( )( ) , ( )( )( ) , ()() , . . . nn nn nn n

5、n n nn xaaaa xaaa xaa 經(jīng)過經(jīng)過n-1次消元，原方程組化為等價的次消元，原方程組化為等價的上三角上三角方程組方程組 21 l 1n l 31 l 32 l 2n l 1, nn l 回代過程回代過程的計算公式：的計算公式： 1 1 11 1 1 () () ()() () () n n n n nn n ii iijj j i i i ii b x a bax x a 等價等價方程組方程組 11()()nn AXB 121,inn 例例5 5：用用基本基本Gauss消元法求解下列方程組消元法求解下列方程組 123 123 12 231 4254 27 xxx xxx xx

6、解：解：將第一個方程的將第一個方程的x1的系數(shù)化為的系數(shù)化為1，消去其它方程中的，消去其它方程中的x1 123 23 23 0 51 50 5 42 2 51 56 5 . . xxx xx xx 321 619,xxx 將第二個方程的將第二個方程的x2的系數(shù)化為的系數(shù)化為1，消去其它方程中的，消去其它方程中的x2 123 23 3 0 51 50 5 0 250 5 6 . . xxx xx x 回代，得回代，得 基本基本Gauss消元法的工作量消元法的工作量 消元過程：消元過程： 11 11 1()()() nn kk nknk nk 回代過程：回代過程：1 2 ()n n 32 5 32

7、6 nnn 33 2 333 nnn n 加減法的次數(shù)加減法的次數(shù) 323 5 3263 nnnn 乘除法的次數(shù)乘除法的次數(shù) 3 ()O n 6 1 .Def 順序主子式順序主子式 11121 21222 12 1 2, , k k k kkkk aaa aaa kn aaa 對于對于mn階矩陣階矩陣A,由由A的即在前的即在前k（ ）行）行 又在前又在前k列列的的k2個元素，保持在矩陣個元素，保持在矩陣A中的相對位置而組中的相對位置而組 成的矩陣，稱為矩陣成的矩陣，稱為矩陣A的的k階主子矩陣階主子矩陣，其對應(yīng)的，其對應(yīng)的行列式行列式 稱為稱為A的的k階順序主子式階順序主子式。 1min(, )

8、km n 基本基本Gauss消元法的實現(xiàn)條件消元法的實現(xiàn)條件 全不為全不為零零的充要條件是的充要條件是1 2 ( ) (, , () i ii aik kn 的的順序主子式順序主子式都不等于都不等于零零，即，即 A 11121 21222 12 01 2, , () i i i iiii aaa aaa ikn aaa 小主元小主元 可能可能 導(dǎo)致計算失導(dǎo)致計算失 敗敗 例例6 6：在在8位制計算機上解方程組位制計算機上解方程組 9 12 12 101 2 xx xx 要求用要求用Gaussian Elimination計算。計算。 9 212111 10/laa 999 2221 110 0

9、01 101010. .al 8個個 9 221 2110bl 9 99 1011 01010 21 10,xx 解：解： 12 1xx 二、二、列主元列主元消去法消去法/* Column Pivoting Strategies*/ 每次每次消元之前消元之前，在剩余元素中選擇，在剩余元素中選擇絕對值最大絕對值最大的的 非零元素作為主元，非零元素作為主元， 然后經(jīng)過然后經(jīng)過換行換行換到換到主元位置主元位置 列主元列主元消去法消去法/* Column Pivoting Strategies */ Step k：第第k步首先選擇步首先選擇主元主元1 21, ,kn 尋求尋求 滿足滿足 l 11 1

10、()() max, kk lkik k i n aaik kn 然后交換矩陣然后交換矩陣 的第的第 行和行和 行，再進行行，再進行消元消元過程過程 1()k A kl 算法算法: : Gauss列主元列主元消去算法消去算法 求方程組求方程組AX=B 的解的解. . 輸入輸入: :增廣矩陣增廣矩陣An (n+1)=（ （A|B）. 輸出輸出: 近似解近似解 xk=ak,n+1(k=1,2,n) 或失敗信息或失敗信息. 消元消元過程過程 for k = 1,2,n-1 do Step 1 - Step 4 Step 1 尋找行號尋找行號 l , 使得使得 Step 2 如果如果 ，則交換第，則交換

11、第k行和行和l行；行； 否則轉(zhuǎn)否則轉(zhuǎn)Step 7 1max, lkik k i n aaik kn 0 lk a 算法算法: : Gauss列主元列主元消去算法（續(xù)）消去算法（續(xù)） Step 3 for i=k+1,n 計算計算 Step 4 for j=k+1,n+1 計算計算 回代回代過程過程 Step 5 Step 6 for i=n-1,1 計算計算 Step 7 Output (系數(shù)矩陣奇異系數(shù)矩陣奇異); /*不成功不成功 */ STOP. ik ik kk a l a ijijikkj aal a 1, , n n n n n a x a 1 1 , ()/ n ii ni jji i j i xaa xa 例例7 7：用用Gauss列主元列主元消去法求解下列方程組消去法求解下列方程組 123 123 12 231