【正文】 632321321323332321)1(22)1(3232)1(223232321????????????????????????????????????????????????????????????????xxxxxxxxxxxxxxxaamaxxxxxxx故說求解為回代求得完成第二步消元得 例 1:考慮如下線性方程組的 Gauss消元法 求解性 2x2=1 2x1+3x2=2 解 :因?yàn)?a11= 0 ,故此題不能用 Gauss消元法求解 ,但交換方程組的順序后 ,就可 用 Gauss消元法求解了 . 選主元素的必要性 。 1 Gaussian Elimination – The Method ??????????????6239432632321321321xxxxxxxxxG a u s s 消元發(fā)求解方程組用例下面給出例題。 iiiiiaaaaA. ... ... ... ... ..)d e t (1111?注 ： 事實(shí)上，只要 A 非奇異，即 A?1 存在，則可通過逐次消元及行交換，將方程組化為三角形方程組，求出唯一解。 = 167。 (一 ) 高斯消去法的求解過程 ,可大致分為兩個(gè)階段 :首先 ,把原方程組化為上三角形方程組 ,稱之為 “ 消去 ” 過程 。然后 ,用逆次序逐一求出三角方程組 (原方程組的等價(jià)方程組 )的解 ,并稱之為 “ 回代 ” 過程 .,下面分別寫出 “ 消去 ” 和 “ 回代 ” 兩個(gè)過程的計(jì)算步驟 . 消去過程 : 第一步 : 設(shè) a11?0,取 做 (消去第 i個(gè)方程組的 x1) mi1?第一個(gè)方程 +第 i個(gè)方程 i=2,3,… n 則第 i個(gè)方程變?yōu)? 1111 aam ii ??)1()1(2)1(1)1(21 in bxaxaxa inii ???? ?可得第一步消元后的方程組為 ?????????????????)1()1(2)1(2)1(2)1(22)1(22)0(1)0(12)0(121)0(11nnnnnnnnnbxaxabxaxabxaxaxa?????????????i,j=2,3,… ,n iiijijiiijiijij bbaabmbbamaa ?????? )0()0()0(11)0()1()0(11)0()1( ,i,j=2,3,… ,n 第二步 : 設(shè) ,取 做 (消去第 i個(gè)方程組的 x2,i=3,4,… n) mi2?第二個(gè)方程 + 第 i個(gè)方程 i=3,4,… n 類似可得第二步消元后的方程組為 0)1(22 ?a)1(22)1(22aam ii ????????????????????????)2()2(3)2(3)2(3)2(33)2(33)1(2)1(22)1(22)0(1)0(12)0(121)0(11nnnnnnnnnnnbxaxabxaxabxaxabxaxaxa?????????????????njibmbbamaa iiijiijij,...,4,3, )1(22)1()2()1(22)1()2(?????第 k步 : 設(shè) ,取 做 (消去第 i個(gè)方程組的 xk,i=k+1,k+2,… ,n) mik?第 k個(gè)方程 + 第 i個(gè)方程 i= k+1,k+2,… n 類似可得第 k步消元后的方程組為 0)1( ??kkka )1()1(???? kkkkikik aam?????????????????????????????)()(1)(1)(1)(11)(11)1(2)1(22)1(22)0(1)0(12)0(121)0(11knnknnkkknkknknkkkkknnnnbxaxabxaxabxaxabxaxaxa???????????????????????????????????????nkkjibmbbamaa kkikkikikkjikkijkij,...,2,1, )1()1()()1()1()(??????? ????繼續(xù)下去到第 n1步消元 ,可將線性方程組化為如下上三角方程組 : nkkjibmbbamaaaamnkkkbabxabxaxabxaxaxakkikkikikkjikkijkijkkkkikikkikijnnnnnnnnnn, .. .,2,1,/1,3,21)1()1()()1()1()()1()1()()()1()1()1(2)1(22)1(2211212111???????????????????????????????????????????，對計(jì)算公式為次消元后的系數(shù)，表示第的上標(biāo)和其中 高斯消元法 /* Gaussian Elimination */ 思路 首先將 A化為上三角陣 /* uppertriangular matrix */，再回代求解 /* backward substitution */。 1 Gaussian Elimination – The Method 消元 記 ,)( )1()1( nnijaAA ???????????????)1()1(1)1(...nbbbb??Step 1： 設(shè) ，計(jì)算因子 0)1(11 ?a ).. .,2(/ )1(11)1( 11 niaam ii ??將增廣矩陣 /* augmented matrix */ 第 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)( ?nnnaWhat if ? No unique solution exists. )1. .. ,1()( 1)()(??????? niaxabx iiinijjiijiii0)( ?iiiaWhat if ? Then we must find the smallest integer k ? i with , and interchange the kth row with the ith row. 0)( ?ikiaWhat if we can’t find such k ? No unique solution exists. 定理 若 A的所有 順序主子式 /* determinant of leading principal submatrices */ 均不為 0，則高斯消元無需換行即可進(jìn)行到底，得到唯一解。 167。為具體認(rèn)識這種方法，完成第一步消元得。 例 2： 單精度解方程組 ????????211021219xxxx/* 精確解為 和 */ ...1000...101191?????? ?x8個(gè) ...8999... 12 ?????? xx8個(gè) 用 Gaussian Elimination計(jì)算： 9112121 10/ ?? aam? 9992122 10101010... ???????? ?ma8個(gè) 9212 1012 ????? ?mb?????? ????9991010011100,1 12 ??? xx小主元 /* Small pivot element */ 可能導(dǎo)致計(jì)算失敗。 1 Gaussian Elimination – Pivoting Strategies 例題 3:討論下面方程組的解法 +x2=1 x1+x2=2 假設(shè) 求解是在四位浮點(diǎn)十進(jìn)制數(shù)的計(jì)算機(jī)上進(jìn)行 ?103 x1 + ?101 x2