增广矩阵 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