2-1Gauss消去法

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

2、sGauss迭代法迭代法迭代法：迭代法SORSeidelGaussJacobi2.1 Gauss消去法問題：n元線性方程組nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111（2.1.1）。，其中簡(jiǎn)寫：TnTnnnijbbbbxxxxaAbAx,2121）有唯一解。非奇異，則方程組（設(shè)系數(shù)矩陣結(jié)論：1 . 1 . 2A基本思想：對(duì)方程組（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依次解出，然后通過逐步回代，）的最后一個(gè)方程解出由（。12,xxn一、順序Gauss消去法（簡(jiǎn)稱Gauss消去法）1、算法 。，記nibbnjiaaiiijij, 2 , 1, 2 , 1,11（1）消元過程執(zhí)行對(duì)于1, 2 , 1nk ；算；否則轉(zhuǎn)，則算法失效，停止計(jì)如果ba

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

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

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