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

1、第二章 解線性方程組的直接法K 由消元過程和回代過程構(gòu)成高斯高斯(Gauss)消去法消去法. 基本思想 用矩陣行的初等變換將方程組系數(shù)矩陣A約化為簡單的三角形矩陣,然后回代求解. P25 實例實例 (用增廣矩陣表示)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將化為步后）當經(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、消去法的運算量消去法的運算量計算機作乘除運算所耗時間要遠遠多于加減運算計算機作乘除運算所耗時間要遠遠多于加減運算且在一個算法中，加減運算和乘除運算次數(shù)大體相當且在一個算法中，加減運算和乘除運算次數(shù)大體相當故在衡量一個算法的運算量時只需統(tǒng)計乘除的運算次數(shù)故在衡量一個算法的運算量時只需統(tǒng)計乘除的運算次數(shù)步消元時作第k乘法次數(shù)：次)1)(knkn除法次數(shù)：次)(kn數(shù)為步消元乘除法運算總次作第k次)2)(knkn總次數(shù)為步消元需作乘除法運算完成全部1n11)2)(nkknkn652323nnn全部回代過程需作乘除法的總次數(shù)為222nn于是Gauss消去法的乘除法運算總的次數(shù)為3323nnn)(323nOn數(shù)量級很大時當n3323nnn33n時如