浙江大学：《数值分析》课程PPT教学课件（双语版）第三章 解线性方程组的直接法 §1 Gaussian Elimination – Amount of Computation

第三章解线性方程组的直接法 Direct Method for Solving Linear Systems */ 求解Ax=b §1高斯消元法/ Gaussian Elimination >高斯消元法: 思首先将4化为上三角阵/ upper-triangular matrix 路再回代求解/ backward substitution

第三章 解线性方程组的直接法 /* Direct Method for Solving Linear Systems */ 求解 Ax b   = §1 高斯消元法 /* Gaussian Elimination */ ➢ 高斯消元法： 思 路 首先将A化为上三角阵 /* upper-triangular matrix */， 再回代求解 /* backward substitution */。 =

8 1 Gaussian Elimination-The Method 消元 已记A=A b b Step1:设a≠叶算因子mn=m/a(i=2,…,n 将增广矩阵 augmented matrix*第i行-m1×第1行 得到 其中 (1) (1) i1""1j (1) i,j=2, Step k:设≠计算因子m=ah/m(i=k+1,…,n) 且计算4 (k+1)二 1 (1)x (k+1) (k) (k) (i,j=k+1,…,n) 共进行n-15 (n)

§1 Gaussian Elimination – The Method 消元 记 ( ) , (1) (1) A = A= aij nn           = = (1) (1) 1 (1) . . . bn b b b   Step 1：设 ，计算因子 0 (1) a11  / ( 2, ..., ) (1) 11 (1) mi1 = ai1 a i = n 将增广矩阵/* augmented matrix */ 第 i 行 − mi1  第1行， 得到 (1) 1 (1) 1 (1) 12 (1) 11 a a ... a n b (2) A (2) b  ( , 2, ..., ) (1) 1 1 (2) (1) (1) 1 1 (2) (1) i j n b b m b a a m a i i i ij ij i j =    = − = − 其中 Step k：设 ，计算因子 且计算 0 ( )  k akk / ( 1, ..., ) ( ) ( ) m a a i k n k k k k i k = i k = + ( , 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) 2 2 (1) 1 (1) 1 2 (1) 1 1 . . . . . . . . . ... ... ... n n n n nn n n b b b x x x a a a a a a

8 1 Gaussian Elimination-The Method 回代xn=b)/am) ∑ j=i+1 l=n ·· What if ye 924 定理若的所有减/ determinantof leading principal submatrices8y分则高斯消元无需换行即可 进行到底,得到唯解 人○ 注:事实上,只要A非奇异,即A-1存在,则可通过逐次 消元及行交换,将方程组化为三角形方程组,求出唯 解

回代 ( ) ( ) / n nn n xn = bn a 0 ( ) = n What if ? No unique ann solution exists. ( 1, ..., 1) ( ) 1 ( ) ( ) = − − = = + i n a b a x x i i i n j i j i i j i i i 0 ( ) = i aii Then we must find the smallest integer k  i with , and interchange the k-th row with the i-th row. 0 ( )  i ki a What if we can’t No unique find such k ? solution exists. 定理 若A的所有顺序主子式 /* determinant of leading principal submatrices */ 均不为0，则高斯消元无需换行即可 进行到底，得到唯一解。 i ii i i a a a a A ... ... ... ... ... det( ) 1 11 1 注：事实上，只要 = A 非奇异，即 A−1 存在，则可通过逐次 消元及行交换，将方程组化为三角形方程组，求出唯 一解。 §1 Gaussian Elimination – The Method

8 1 Gaussian Elimination-Pivoting Strategies >选主元消去法/ Pivoting Strategies 例:单精度解方程组{0+ 8个 8个 /精确解为x1=,1=100.00.和x2=2-x1=099.99.*/ 用 Gaussian elimination计算: 21- 11 8个 2=1-m21×1=0.0…01×10-10=-10 b,=2 1 l=-10 Go 小主元/ Small pivot element>可能导致计 0-103-10 算失败

➢ 选主元消去法 /* Pivoting Strategies */ 例：单精度解方程组    + = + = − 2 10 1 1 2 1 2 9 x x x x /* 精确解为 1.00...0100... 和 */ 1 10 1 1 9  = − = − x 8个 2 0.99 ... 9899... 2 1  x = − x = 8个 用Gaussian Elimination计算： 9 m21 = a21 / a11 = 10 9 9 9 a2 2 = 1− m2 1 1 = 0.0...0110 −10 = −10 8个 9 b2 = 2− m21 1 =  −10      − −  − 9 9 9 0 10 10 10 1 1  x2 =1, x1 = 0 小主元 /* Small pivot element */ 可能导致计 算失败。 §1 Gaussian Elimination – Pivoting Strategies

8 1 Gaussian Elimination-Pivoting Strategies 全主元消去法/ Complete Pivoting 每一步选绝对值最大的元素为主元素,保证|m1k|≤1 Step k:④选取|aA|=max|an|≠0; k≤i,j≤n ②Ifi≠ k then交换第k行与第i行; Ifj≠ k then交换第k列与第j列; ③消元 注:列交换改变了x的顺序,须记录交换次序,解完后再 换回来。 列主元消去法/ Partial Pivoting, or maximal column pivoting 省去换列的步骤,每次仅选一列中最大的元。 ir.k kss“k|≠0

 全主元消去法 /* Complete Pivoting */ 每一步选绝对值最大的元素为主元素，保证 | mik |  1 。 Step k: ① 选取 | | max | | 0; , =    ij k i j n ai j a k k ② If ik  k then 交换第 k 行与第 ik 行; If jk  k then 交换第 k 列与第 jk 列; ③ 消元 注：列交换改变了 xi 的顺序，须记录交换次序，解完后再 换回来。  列主元消去法 /* Partial Pivoting, or maximal column pivoting */ 省去换列的步骤，每次仅选一列中最大的元。 | , | = max | |  0   i k k i n ai k a k §1 Gaussian Elimination – Pivoting Strategies

8 1 Gaussian Elimination-Pivoting Strategies 例:10 ① 112 2 101 1√ 注:列豆法没有全主元法稳定。 侧{」 11010 0 109-10 狄标度化列主元消去法/ Scaled Partial Pivoting 对每一行计算荘意血这两介方弱谢间,s:只在初始时计 算一次。以后每 虑子列中4最大的a为主元 注:稳定性介于列主元法和全主元法之间

例：       − 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 注：稳定性介于列主元法和全主元法之间。 §1 Gaussian Elimination – Pivoting Strategies

8 1 Gaussian Elimination-Pivoting Strategies 实际应用中直接调用 Gauss 结合全主元消去后的 Elimination解3阶线性方程 结果: 组的结果:

§1 Gaussian Elimination – Pivoting Strategies 实际应用中直接调用Gauss Elimination 解3阶线性方程 组的结果： 结合全主元消去后的 结果：

8 1 Gaussian Elimination-Gauss-Jordan Method >高斯-若当消去法/ Gauss-Jordan Method 与 Gaussian Elimination的主要区别: 每步不计算mk,而是先将当前主元a4)变为1; 矿把ak()所在列的上、下元素全消为0; Ax=b→Ix=Ab You'd 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… §1 Gaussian Elimination – Gauss-Jordan Method

8 1 Gaussian Elimination - Amount of Computation >运算量/* Amount of Computation 由于计算机中乘除/ multiplications/divisions*运算的时 间远远超过加减/ additions/ subtractions运算的时间,故 估计某种算法的运算量时,往往只估计乘除的次数,而且通 常以乘除次数的最高次幂为运算量的数量级。 6 Gaussian elimination: (n-k)次 Step k:识 Gaussian elimination的总乘除次数为(m-6)(m-k+2)次 运算量为"级。 消元乘除次数: 共进行 ∑(n-kn-k+2 x=b/a (n-澡除次数 -一 n-,…)1+∑(m-i+1)=+ 2

➢ 运算量 /* Amount of Computation */ §1 Gaussian Elimination – 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

g Complete pivoting 1 Gaussian Elimination-Amount of Computation 比 Gaussian elimination多出0|比较,保证稳定,但表时。 6 Partial Pivoting: 比 Gaussian elimination只多出"比较,略省时,但不保 证稳定。 n scaled partial Pivoting: 比 Gaussian elimination多出o(n)除法和3比较,比列主 元法稳定。但若逐次计算s,则比全主元法还慢。 6 Gauss-Jordan method 运算量约为o(n/2)故通常只用于求逆矩阵,而不用于解方 程组。求逆矩阵即[4]→[A]。 HW:p.42#1 p43#6

§1 Gaussian Elimination – Amount of Computation  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 HW: p.42 #1 p.43 #6