数值分析：2-2(a) Gauss消去法

1、第二章 解线性方程组的直接法K 由消元过程和回代过程构成高斯高斯(Gauss)消去法消去法. 基本思想 用矩阵行的初等变换将方程组系数矩阵A约化为简单的三角形矩阵,然后回代求解. P25 实例实例 (用增广矩阵表示)2.2 Gauss消去法消去法习题习题 -要有解答过程要有解答过程 P15 复习题 1.5、1.7 P21 习题 1.12 P58 习题 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）：假定）第一步（定义行乘数乘数（消元因子）：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(化为步并将步：设已完成前）第（),(12)1()1(bAkk()()()()()()()2(2)2(2)2(22)1(1)1(1)1(12)1(11knknnknkkkkknkkknnbaabaabaabaaa),()()(kkbA),()1()1(bA0)det(定义行乘数定义行乘数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将化为步后）当经过（),( ,13)1()1(bAnk),()()(nnbA0)det(A由于niaiii,2 , 10)(可知的解：因此可得线性方程组bAx 有唯一解上三角形方程组因此)()(,nnbxA主元主元)()(nnnnnnabx 1 ,2 ,2, 1nni)(1)()(iiinijjiijiiiaxabx( n次除法 及 次乘法 )211()22ninnni全部回代过程需作乘除法的总次数为222nn二、二、Gauss

5、消去法的运算量消去法的运算量计算机作乘除运算所耗时间要远远多于加减运算计算机作乘除运算所耗时间要远远多于加减运算且在一个算法中，加减运算和乘除运算次数大体相当且在一个算法中，加减运算和乘除运算次数大体相当故在衡量一个算法的运算量时只需统计乘除的运算次数故在衡量一个算法的运算量时只需统计乘除的运算次数步消元时作第k乘法次数：次)1)(knkn除法次数：次)(kn数为步消元乘除法运算总次作第k次)2)(knkn总次数为步消元需作乘除法运算完成全部1n11)2)(nkknkn652323nnn全部回代过程需作乘除法的总次数为222nn于是Gauss消去法的乘除法运算总的次数为3323nnn)(323nOn数量级很大时当n3323nnn33n时如