例:|10 ① 112 10-71 →x 1√ 注:列豆法没有全主元法稳定。 { 110 10 =0 109-10 g 标度化列主元消去法/ Scaled Partial Pivoting 对每一行计算m这介谢间,s;只在初始时计 Sisn vIa 算一次。以后每 虑子列.中最大的a1k为主元 注:稳定性介于列主元法和全主元法之间
例： − 1 1 2 10 1 1 9 x2 = 1 , x1 = 1 0 1 1 1 1 2 − 10 1 1 1 1 2 9 ✓ 注：列主元法没有全主元法稳定。 例： x2 = 1 , x1 = 0 1 1 2 1 10 10 9 9 − − 9 9 9 9 0 10 10 1 10 10 注意：这两个方程组在 数学上严格等价。 标度化列主元消去法 /* Scaled Partial Pivoting */ 对每一行计算 。为省时间，si 只在初始时计 算一次。以后每一步考虑子列 中 最大的 aik 为主元。 max | | 1 ij j n si a = nk kk a a . . . i ik s a 注：稳定性介于列主元法和全主元法之间
实际应用中直接调用 Gauss 结合全主元消去后的 Elimination解3阶线性方程 结果: 组的结果:
实际应用中直接调用Gauss Elimination 解3阶线性方程 组的结果： 结合全主元消去后的 结果：
>高斯若当消去法/ Gauss-Jordan method 与 Gaussian Elimination的主要区别: 每步不计算mk,而是先将当前主元ak)变为1; 把a④所在列的上、下元素全消为0; Ax=b→Ix=Ab Youd better wait till we go through the next section to draw your conclusion
➢ 高斯-若当消去法 /* Gauss-Jordan Method */ 与 Gaussian Elimination 的主要区别： 每步不计算 mik ，而是先将当前主元 akk (k) 变为 1; 把 akk (k) 所在列的上、下元素全消为0; Ax b I x A b −1 = = Hey! Isn’t it better than Gaussian Elimination? What makes you say so? Obviously we no longer need the backward substitution! You’d better wait till we go through the next section to draw your conclusion…
>运算量/* Amount of Computation 由于计算机中乘除/ multiplications/ divisions+运算的时 间远远超过加减/ additions/ subtractions*运算的时间,故 估计某种算法的运算量时,往往只估计乘除的次数,而且通 常以乘除次数的最高次幂为运算量的数量级。 e Gaussian elimination: (n-k)次 k Step k:识 目 Gaussian elimination的总乘除次数为(m-6)(n-k+2)次 运算量为"级。 消元乘除次数: 共进行 8(n-k)n-k+2) x=b(m/a(n 5 (n-世澡除次数 bo-auix 326 =n-,…,1)1+∑(m-i+1) 22
➢ 运算量 /* Amount of Computation */ 由于计算机中乘除 /* multiplications / divisions */ 运算的时 间远远超过加减 /* additions / subtractions */ 运算的时间，故 估计某种算法的运算量时，往往只估计乘除的次数，而且通 常以乘除次数的最高次幂为运算量的数量级。 Gaussian Elimination: Step k：设 ，计算因子 且计算 0 ( ) k akk / ( 1, ..., ) ( ) ( ) m a a i k n k kk k ik = ik = + ( , 1, ..., ) ( 1) ( ) ( ) ( 1) ( ) ( ) i j k n b b m b a a m a k ik k k i k i k ik kj k ij k ij = + = − = − + + 共进行n − 1步 = ( ) (2) 2 (1) 1 2 1 ( ) (2) 2 (2) 22 (1) 1 (1) 12 (1) 11 . . . . . . . . . ... ... ... n n n n nn n n b b b x x x a a a a a a ( ) ( ) / n nn n xn = bn a ( 1, ..., 1) ( ) 1 ( ) ( ) = − − = = + i n a b a x x i ii n j i j i ij i i i ((n n −−kk)) 2次次 (n − k) (n − k + 2) 次 n n n n k n k n k 6 5 3 2 ( )( 2) 3 2 1 1 = + − − − + − = 消元乘除次数： (1 n 次− i +1) 次 2 2 1 ( 1) 1 2 1 n n n i n i + − + = + − = 回代乘除次数： Gaussian Elimination 的总乘除次数为 n n ，运算量为 级。 n 3 1 3 2 3 + − 3 3 n
r Complete Pivoting: 比 Gaussian Elimination多出o|"|比较,保证稳定,但费时。 e Partial Pivoting 比 Gaussian Elimination只多出0,比较,略省时,但不保 证稳定。 h Scaled Partial Pivoting: 比 Gaussian elimination多出o(n)除法和3比较,比列主 元法稳定。但若逐次计算s④),则比全主元法还慢。 n Gauss-Jordan method. 运算量约为O(n3/2)故通常只用于求逆矩阵,而不用于解方 程组。求逆矩阵即[A]→[A]
Complete Pivoting: 比 Gaussian Elimination多出 比较，保证稳定，但费时。 3 3 n O Partial Pivoting: 比 Gaussian Elimination只多出 比较，略省时，但不保 证稳定。 3 2 n O Scaled Partial Pivoting: 比 Gaussian Elimination多出 除法和 比较，比列主 元法稳定。但若逐次计算 si (k)，则比全主元法还慢。 ( ) 2 O n 3 2 n O Gauss-Jordan Method: 运算量约为 。故通常只用于求逆矩阵，而不用于解方 程组。求逆矩阵即 。 ( 2 ) 3 O n 1 | | − A I I A