电子科技大学：《数值分析 Numerical Analysis》课程教学资源（课件讲稿）高斯消元法

高斯消元法 方程组化简一消元过程 高斯消元与矩阵分解 三对角方程组的追赶法 1/25

1/25 高斯消元法 方程组化简—消元过程 高斯消元与矩阵分解 三对角方程组的追赶法

>线性方程组的矩阵形式 41心1+4122++41Xn=b1 21心1+L22X2++2mXn=b2 a,= n比1+n2++AnXn=bn (i=1,2,…,n) 12 b 线性方程组求解： L21 A22 X2 b2 ①.直接方法； 2.基本迭代法； An2 Xn」 3.子空间方法. AX=b X?→ b 2/25

2/25 Ø线性方程组的矩阵形式 a11x1+ a12x2+····+ a1nxn = b1 a21x1+ a22x2+····+ a2nxn = b2 ··································· an1x1+ an2x2+····+ annxn = bn i n j aij x j  b 1                    n n nn n n n n b b b x x x a a a a a a a a a          2 1 2 1 1 2 21 22 2 11 12 1 A X = b ( i=1,2,···,n ) 线性方程组求解: 1. 直接方法; 2. 基本迭代法; 3. 子空间方法. X ?  b

>解线性方程组的克莱姆方法 1.输入矩阵A和右端向量b; 2.计算A的行列式D,如果D=0,则输出错信息结束， 否则进行3； 3.对=1,2，…，n用b替换A的第k列数据，并计算 替换后矩阵的行列式值Dk; 4.计算并输出X1=D1/D,,XnDm/D,结束。 计算量： n+1)n:(n-l) 高斯消元法 第一步：将方程组化简为三角形方程组； 第二步：解三角形方程组，获方程组的解。 3/25

3/25 Ø解线性方程组的克莱姆方法 1. 输入矩阵 A 和右端向量 b; 高斯消元法 第一步: 将方程组化简为三角形方程组; 第二步: 解三角形方程组,获方程组的解。 4. 计算并输出 x1 = D1 / D,····, xn =Dn /D, 结束。 3. 对 k=1,2,···,n 用 b 替换 A 的第 k 列数据,并计算 替换后矩阵的行列式值 Dk; 2. 计算 A 的行列式 D,如果 D=0,则输出错信息结束, 否则进行 3 ; 计算量： (n+1)n!(n-1)

>解上三角方程组 011x1+012x2++a1mn=b1 22x2++2mn=b2 (a1.m0) annXn bn 计算：xn=bn lann X=[bk一(ak,k+Xk++…+aknI/akk (k=n-1,…,1) 除法：n次；乘法：n(n-l)/2次， 乘、除法运算共n(n+1)/2次，简记为O(n2) 4/25

4/25 Ø解上三角方程组              nn n n n n n n a x b a x a x b a x a x a x b    22 2 2 2 11 1 12 2 1 1 计算：xn = bn /ann (a11…ann≠0) xk =[bk－(ak , k+1xk+1+ … + ak n)] / ak k ( k =n－1,···,1 ) 除法: n次; 乘法: n(n-1)/2次, 乘、除法运算共 n(n+1)/2 次, 简记为 O( n2 )

>消元过程（化一般方程组为上三角方程组） 01X1+12x2+413X3+414x4=b 21X1+22X2+23X3+424X4=b2 L31七1+L32七2+033X3+0344=b3 L41X1+L42X2+043七3+44x4=b4 11X1+12X2+413X3+0144=b1 a2x2+ax3+ax=b ax+ax=b ax=b 5/25

5/25 Ø消元过程(化一般方程组为上三角方程组)                      41 1 42 2 43 3 44 4 4 31 1 32 2 33 3 34 4 3 21 1 22 2 23 3 24 4 2 11 1 12 2 13 3 14 4 1 a x a x a x a x b a x a x a x a x b a x a x a x a x b a x a x a x a x b                (3) 4 4 (3) 44 (2) 4 3 (2) 3 34 (2) 33 (1) 4 2 (1) 3 24 (1) 2 23 (1) 22 11 1 12 2 13 3 14 4 1 a x b a x a x b a x a x a x b a x a x a x a x b 

增广矩阵 w 12 013 l14 A= ( 22 A2 24 b2 U32 l33 L34 b3 042 043 L44 计算：[m21m31m41lT=[214314lT /11 用-21乘矩阵第一行加到矩阵第二行； 用-m31乘矩阵第一行加到矩阵第三行； 用-m41乘矩阵第一行加到矩阵第四行； 6/25

6/25      41 42 43 44 4 31 32 33 34 3 21 22 23 24 2 11 12 13 14 1 a a a a b a a a a b a a a a b a a a a b A 增广矩阵 计算: [m21 m31 m41]T = [a21 a31 a41]T / a11 用–m21乘矩阵第一行加到矩阵第二行; 用–m31乘矩阵第一行加到矩阵第三行; 用–m41乘矩阵第一行加到矩阵第四行;

实现第一轮消元 L14 A 计算：[m32m4lT=[ag2aW]/a 用-M2乘矩阵第二行加到矩阵第三行； 用-m42乘矩阵第二行加到矩阵第四行； 实现第二轮消元、第三轮消元… 7/25

7/25 实现第一轮消元        (1) 4 (1) 44 (1) 43 (1) 42 (1) 3 (1) 34 (1) 33 (1) 32 (1) 2 (1) 24 (1) 23 (1) 22 11 12 13 14 1 (1) a a a b a a a b a a a b a a a a b A 计算: [m32 m42]T = 用–m32乘矩阵第二行加到矩阵第三行; 用–m42乘矩阵第二行加到矩阵第四行; 实现第二轮消元、第三轮消元········· (1) 22 (1) 42 (1) 32 [a a ]/ a

1 3 上三角方程组 n阶方程组消元过程乘法次数： (n-1)n+(n-2)n-1)+..+1X2=(n3-n/3 除法次数：(n-1)+(n-2)+..+1=n(n-1)/2 回代过程：n(n+1)/2 总：n2+(n3-n)/3,简记O(n3 n 2 3 4 5 6 高斯 6 17 36 65 106 克莱姆 8 51 364 2885 25206 8/25

8/25 n阶方程组消元过程乘法次数: (n-1)n+(n-2)(n-1)+…+1×2=(n3-n)/3 除法次数: (n-1)+(n-2)+…+1=n(n-1)/2 回代过程：n(n+1)/2 总: n2+(n3-n)/3, 简记 O(n3) n 2 3 4 5 6 高斯 6 17 36 65 106 克莱姆 8 51 364 2885 25206                  (3) 4 (2) 3 (1) 2 1 4 3 2 1 (3) 44 (2) 34 (2) 33 (1) 24 (1) 23 (1) 22 11 12 13 14 b b b b x x x x a a a a a a a a a a 上三角方程组

原始高斯消元法算法： 1.Fork=1,…,n-1Do 2. Fori=k+1,…,nDo 3. ak←Lk/Lkk 4. For jk+1,…,nDo 5. a←L-akX时 6. EndDo 7. b:←b;-aikX bk 8. EndDo 9. EndDo 9/25

9/25 原始高斯消元法算法: 1. For k=1,···,n-1 Do 2. For i=k+1,···,n Do 3. aik  aik / akk 4. For j=k+1,···,n Do 5. aij  aij – aik×akj 6. EndDo 7. bi bi – aik×bk 8. EndDo 9. EndDo

定理1约化主元ak+1,k+1因≠0(k=0,1,,n-1)的 充分必要条件是矩阵A的各阶顺序主子式不 为零即 三 : ≠0 (k=1,2,…,n) … kk 10/25

10/25 定理1 约化主元ak+1,k+1 (k) ≠ 0 (k=0,1,···,n-1)的 充分必要条件是 矩阵A的各阶顺序主子式不 为零.即 0 1 11 1   k kk k k a a a a D      ( k = 1,2,····,n)