这样，经过n-1步后，即可得到一个上三角矩阵Am): (1) 012 a) ,(2) A(n)= 02 ar 四 最后，回代求解 1 In= n) ( i=n-1,n-2,,1. ann =i+1 以上就是Gauss消去法的整个计算过程， 由上面的计算过程可知，Gauss消去法能顺利进行下去的充要条件是a促≠0，k= 1,2,.,n,这些元素被称为主元 http://math.ecnu.edu.cn/-jypan 10/52
这样, 经过 n − 1 步后, 即可得到一个上三角矩阵 A(n) : A (n) = a (1) 11 a (1) 12 · · · a (1) 1n b (1) 1 a (2) 22 · · · a (2) 2n b (2) 2 . . . . . . . . . a (n) nn b (n) n . 最后, 回代求解 xn = b (n) n a (n) nn , xi = 1 a (i) ii b (i) i − Xn j=i+1 a (i) ij xj , i = n − 1, n − 2, . . . , 1. 以上就是 Gauss 消去法的整个计算过程. ✍ 由上面的计算过程可知, Gauss 消去法能顺利进行下去的充要条件是 a (k) kk ̸= 0, k = 1, 2, . . . , n, 这些元素被称为 主元. http://math.ecnu.edu.cn/~jypan 10/52
主元 定理设A∈Rmxm,则所有主元保都不为零的充要条件是A的所有顺序主子式都不为 零，即 a11 alk D1a11≠0，Dk≌ .: ≠0， k=2,3,,n akl akk 事实上，如果A的所有顺序主子式都不为零，则主元为 =D,=D， ΓDk-1 k=2,3,.n 推论Guss消去法能顺利完成的充要条件是A的所有顺序主子式都不为零. http://math.ecnu.edu.cn/-jypan 11/52
主元 定理 设 A ∈ R n×n , 则所有主元 a (k) kk 都不为零的充要条件是 A 的所有顺序主子式都不为 零, 即 D1 ≜ a11 ̸= 0, Dk ≜ a11 · · · a1k . . . . . . . . . ak1 · · · akk ̸= 0, k = 2, 3, . . . , n. ✍ 事实上, 如果 A 的所有顺序主子式都不为零, 则主元为 a (1) 11 = D1, a (k) kk = Dk Dk−1 , k = 2, 3, . . . , n. 推论 Gauss 消去法能顺利完成的充要条件是 A 的所有顺序主子式都不为零. http://math.ecnu.edu.cn/~jypan 11/52
2-1-2 Gauss消去法的运算量 在第k步中，我们需要计算 k=a限/限，i=k+1,,n→n-k次除法 g+=哈-u图，i,j=k+1…,n→(m-次乘法 +=)-l,i=k+1,,n→ n-k次乘法 所以整个消去过程的乘除运算为 -月+a-护-2+-a-+血-gn-习 n-l n-1 6 易知，回代求解过程的乘除运算为 《-+1=2之小 2 http://nath.ecnu.edu.cn/-jypan 12/52
2-1-2 Gauss 消去法的运算量 在第 k 步中, 我们需要计算 lik = a (k) ik /a (k) kk , i = k + 1, . . . , n → n − k 次除法 a (k+1) ij = a (k) ij − lika (k) kj , i, j = k + 1, . . . , n → (n − k) 2 次乘法 b (k+1) i = b (k) i − likb (k) k , i = k + 1, . . . , n → n − k 次乘法 所以整个消去过程的乘除运算为 nX−1 k=1 2(n − k) + (n − k) 2 = nX−1 ℓ=1 2ℓ + ℓ 2 = n(n − 1) + n(n − 1)(2n − 3) 6 . 易知, 回代求解过程的乘除运算为 1 + nX−1 i=1 n − i + 1 = n(n + 1) 2 . http://math.ecnu.edu.cn/~jypan 12/52
计算复杂度 所以整个Gauss消去法的乘除运算为 +n2、 3 书同理，也可统计出，Gauss消去法中的加减运算次数为 n3. 2 5n 3+2 61 所以总运算量为 2m+ n2 7m_ 2n3 3 2 6 = 3 +0(m2) http://nath.ecnu.edu.cn/-jypan 13/52
计算复杂度 所以整个 Gauss 消去法的乘除运算为 n 3 3 + n 2 − n 3 . 同理, 也可统计出, Gauss 消去法中的加减运算次数为 n 3 3 + n 2 2 − 5n 6 . 所以总运算量为 2n 3 3 + 3n 2 2 − 7n 6 = 2n 3 3 + O(n 2 ) http://math.ecnu.edu.cn/~jypan 13/52
算法评价 评价算法的一个重要指标是执行时间，但这依赖于计算机硬件和编程技巧等，因此直 接给出算法执行时间是不太现实的.所以我们通常是统计算法中算术运算（加减乘除） 的次数 凸为了尽可能地减少运算量，在实际计算中，数，向量和矩阵做乘法运算时的先后执行次 序为：先计算数与向量的乘法，然后计算矩阵与向量的乘法，最后才计算矩阵与矩阵的 乘法 http://math.ecnu.edu.cn/-jypan 14/52
算法评价 ✍ 评价算法的一个重要指标是 执行时间, 但这依赖于计算机硬件和编程技巧等, 因此直 接给出算法执行时间是不太现实的. 所以我们通常是统计算法中算术运算 (加减乘除) 的次数. ✍ 为了尽可能地减少运算量, 在实际计算中, 数, 向量和矩阵做乘法运算时的先后执行次 序为: 先计算数与向量的乘法, 然后计算矩阵与向量的乘法, 最后才计算矩阵与矩阵的 乘法. http://math.ecnu.edu.cn/~jypan 14/52