數(shù)值分析：2-2(a) Gauss消去法

1、第二章 解線性方程組的直接法K 由消元過程和回代過程構(gòu)成高斯高斯(Gauss)消去法消去法. 基本思想 用矩陣行的初等變換將方程組系數(shù)矩陣A約化為簡單的三角形矩陣,然后回代求解. P25 實(shí)例實(shí)例 (用增廣矩陣表示)2.2 Gauss消去法消去法習(xí)題習(xí)題 -要有解答過程要有解答過程 P15 復(fù)習(xí)題 1.5、1.7 P21 習(xí)題 1.12 P58 習(xí)題 2.1(1) ),(bAA 2.2 Gauss消去法消去法一、消元與回代計算一、消元與回代計算)1()1()1(2)1(1)1(2)1(2)1(22)1(21)1(1)1(1)1(12)1(11nnnnnnnbaaabaaabaaabAx 對線性

2、方程組對線性方程組對其增廣矩陣施以行初等變換:),()1()1(bA記0)det(A如果)2()2()2(2)2(2)2(2)2(22)1(1)1(1)1(12)1(1100nnnnnnbaabaabaaa),()2()2(bA011)1(11ak）：假定）第一步（定義行乘數(shù)乘數(shù)（消元因子）：niaalii, 3 , 2)1(11)1(11則行第行第,11 ili)1(11)1()2(jiijijalaa)1(11)1()2(blbbiiinji, 3 ,2,ni, 3 ,2),()1()1(bA0)1(11a如果0)det(A由于元素不為零的第一列中至少有一個則 A行交換后消元的第一行與第則

3、將如1)1()1()1(1),(, 01ibAai)2()2()2(2)2(2)2(2)2(22)1(1)1(1)1(12)1(1100nnnnnnbaabaabaaa且0)det(化為步并將步：設(shè)已完成前）第（),(12)1()1(bAkk()()()()()()()2(2)2(2)2(22)1(1)1(1)1(12)1(11knknnknkkkkknkkknnbaabaabaabaaa),()()(kkbA),()1()1(bA0)det(定義行乘數(shù)定義行乘數(shù)nkiaalkkkkikik, 1)()(則行第行第,iklki)()()1(kkjikkijkijalaa)()()1(kkikk

4、ikiblbbnkji, 1,nki, 1 )()()2(2)2(2)2(22)1(1)1(1)1(12)1(11nnnnnnnbabaabaaa),()1()1(bA將化為步后）當(dāng)經(jīng)過（),( ,13)1()1(bAnk),()()(nnbA0)det(A由于niaiii,2 , 10)(可知的解：因此可得線性方程組bAx 有唯一解上三角形方程組因此)()(,nnbxA主元主元)()(nnnnnnabx 1 ,2 ,2, 1nni)(1)()(iiinijjiijiiiaxabx( n次除法 及 次乘法 )211()22ninnni全部回代過程需作乘除法的總次數(shù)為222nn二、二、Gauss

5、消去法的運(yùn)算量消去法的運(yùn)算量計算機(jī)作乘除運(yùn)算所耗時間要遠(yuǎn)遠(yuǎn)多于加減運(yùn)算計算機(jī)作乘除運(yùn)算所耗時間要遠(yuǎn)遠(yuǎn)多于加減運(yùn)算且在一個算法中，加減運(yùn)算和乘除運(yùn)算次數(shù)大體相當(dāng)且在一個算法中，加減運(yùn)算和乘除運(yùn)算次數(shù)大體相當(dāng)故在衡量一個算法的運(yùn)算量時只需統(tǒng)計乘除的運(yùn)算次數(shù)故在衡量一個算法的運(yùn)算量時只需統(tǒng)計乘除的運(yùn)算次數(shù)步消元時作第k乘法次數(shù)：次)1)(knkn除法次數(shù)：次)(kn數(shù)為步消元乘除法運(yùn)算總次作第k次)2)(knkn總次數(shù)為步消元需作乘除法運(yùn)算完成全部1n11)2)(nkknkn652323nnn全部回代過程需作乘除法的總次數(shù)為222nn于是Gauss消去法的乘除法運(yùn)算總的次數(shù)為3323nnn)(323nOn數(shù)量級很大時當(dāng)n3323nnn33n時如