2-1Gauss消去法

1、第二章 線性方程組的解法線性代數(shù)中我們已學過Cramer法則來求解線性方程組，但其計算量（乘除法次數(shù)）至少為(n+1)!+n次。計算機上常用的求解線性方程組的數(shù)值解法大致分為兩類：（1）直接法。經(jīng)過有限步運算，如果運算過程中沒有舍入誤差，可以求得方程組的精確解。其基本思想是把原方程組的系數(shù)矩陣化為對角矩陣、上（下）三角矩陣、正交矩陣之一來求解；（2）迭代法。其基本思想是按照某種規(guī)則生成一向量序列，若此向量序列收斂，則取該向量序列中的某一充分大的一項作為方程組的近似解。正交分解法追趕法平方根分解法分解法三角分解法消去法全主元素消去法列主元素消去法順序消去法：直接法LUGaussGaussGaus

2、sGauss迭代法迭代法迭代法：迭代法SORSeidelGaussJacobi2.1 Gauss消去法問題：n元線性方程組nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111（2.1.1）。，其中簡寫：TnTnnnijbbbbxxxxaAbAx,2121）有唯一解。非奇異，則方程組（設(shè)系數(shù)矩陣結(jié)論：1 . 1 . 2A基本思想：對方程組（2.1.1）的增廣矩陣作有限次的初等行變換，使其系數(shù)矩陣部分變?yōu)樯先蔷仃嚒?1121111211121221211111211111|nnnnnnnbbbaaaaaaaaabA增廣矩陣：消元過程： ，令第一步

3、：設(shè)1111211111111111, 3 , 2,0jiijijiiiiamaanirmraama ，njibmbbiii, 3 , 2,11112 222112222222211112111221100|nnnnnnbbbaaaaaaabAbA ，bbAA11）（步第1, 2 , 1nkk ,|00000|1122112222211112111kkknkkknnknkkknkkknnkkbAbbbbaaaaaaaaabA ，令設(shè)nkkirmraamakikikkkkikikkkk, 2, 1,0 。，nkkjibmbbamaakkikkikikkjikkijkij, 2, 1,11次消元經(jīng)

4、過1n 。nnnnnnnnnbbbaaaaaabA22112222211112111000| 。，設(shè)1, 2 , 10niaiii ，設(shè)回代過程：0nnna nnnnnnkknkknkkkknnnnbxabxaxabxaxabxaxaxa22222222111121121111（2.1.2）,2 . 1 . 21nnxx依次解出，然后通過逐步回代，）的最后一個方程解出由（。12,xxn一、順序Gauss消去法（簡稱Gauss消去法）1、算法 。，記nibbnjiaaiiijij, 2 , 1, 2 , 1,11（1）消元過程執(zhí)行對于1, 2 , 1nk ；算；否則轉(zhuǎn)，則算法失效，停止計如果ba

5、akkk0 計算，對于nkkib, 2, 1 ；kkkkikikaam ；，nkkjamaakkjikkijkij, 2, 11 ；kkikkikibmbb1（2）回代過程 ；nnnnnnabx 。，1 , 2, 11nnkaxabxkkknkjjkkjkkk2、計算量次乘除法；：消元11111nknkknknkn次乘除法。：回代21nn。：總計算量3323nnn3、消元過程進行下去的條件 若為零怎么辦？能否為零？如何判別？元素問題：每一步消元中主kkka 很小怎么辦？若kkka 均不）（個主元素消去法的前順序：定理1, 2 , 111 . 2nkanGausskkk個順序主的前）的系數(shù)矩陣方

6、程組（為零的充分必要條件是11 . 1 . 2nA 。，子式1, 2 , 1011111111nkaaaaDkkkkk證明：其精確解為，消去法求解線性方程組用順序：例2321210121215-xxxxGauss。499998749. 0250001875. 021xx解：在四位計算機上用順序Gauss消去法，則有5551025102104012102321210152rr。，回代解得05 . 012xx值很小，則乘數(shù)這說明若主元素的絕對，分析：22511102xxxx 加到其他行行的數(shù)據(jù)有誤差，這樣的絕對值很大，若第kaamkkkkikik嚴重失真。重擴散，使得計算結(jié)果后必然會造成誤差的嚴二

7、、列主元素Gauss消去法 做行陣次消元前，先對增廣矩。第基本思路：按列選主元kkbAk 中絕對值目的是已是最大則不必換行，交換，若nkiaakikkkk, 1然后再進行消元。行的主對角線位置上，最大的元素交換到第k數(shù)與誤差的傳播。乘除法次，在一定程度上抑制了優(yōu)點：乘數(shù)1ikm對值大小的計了按列比較矩陣元素絕消去法相同，只是增加順序Gauss算量。 。均不為零）（）時，各個主元素去法求解（1, 2 , 11 . 1 . 2nkakkk消非奇異，則用列主元素）的系數(shù)矩陣設(shè)方程組（：定理GaussA1 . 1 . 22 . 2。消去法求解例用列主元素：例12Gauss12232121023223212101522110215-5rrrr。，回代解得25. 05 . 012xx三、全主元素Gauss消去法 最大者交換到第一中的所有元素的絕對值第一次消元時，找到、11AA行第一列，再作消元；次消元時，進行第、k2主元素，再作消元。最大者作為此次消元的從上述框內(nèi)選出絕對值注1：若交換了兩列，應(yīng)記錄自變量的排列次序。整個消元過程結(jié)束后，再按記錄恢復(fù)自變量為自然次序?？偨Y(jié)：實際應(yīng)用中常采用列主元素Gauss消