第二章解线性方程组的直接法 Direct Method for Solving Linear Systems * 求解Ax=b §1高斯消元法/ Gaussian Elimination >高斯消元法: 思首先将4化为上三角阵 upper-triangular matrix*, 路再回代求解/ bac kward substitution
第二章 解线性方程组的直接法 /* Direct Method for Solving Linear Systems */ 求解 Ax b = §1 高斯消元法 /* Gaussian Elimination */ ➢ 高斯消元法： 思 路 首先将A化为上三角阵 /* upper-triangular matrix */， 再回代求解 /* backward substitution */。 =
消元记x=A=(c)y,b (1) b (1) Step1:设am≠叶算因子mn=am/l(i=2,…,m) 将增广矩阵/ augmented matrix第i行-m1×第1行 得到 (1)!b 其中 (1) m2,a(1 (1) (i,j=2,…,n) Step k:设a≠叶算因子mk=a/m(i=k+1,…,n) (k+1) (k) 且计算4=a-mka「aa (k+1) (k) (,j=k+1,…,n) 共进行n-15 (n)
消元 记 ( ) , (1) (1) A = A= aij nn = = (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
回代xn=b)/am) ∑ =十 定理若的所有顺收南式 determinant of leading principal submatrices)高斯硝元无需换行即可 进行到底,得到唯解。 注:事实上,只要A非奇异,即A1存在,则可通过逐次 消元及行交换,将方程组化为三角形方程组,求出唯 解
回代 ( ) ( ) / 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 存在，则可通过逐次 消元及行交换，将方程组化为三角形方程组，求出唯 一解
>选主元消去法/ Pivoting Strategies 例:单精度解方程组 10x,+x 2 8个 8个 /精确解为x 1.0.00..x2=2-x1=0.99.9899.* 10 用 Gaussian elimination计算: m21=a21a1=10 8个 a2=1-m21×1=0.0…01×10-10=-10 b,=2-m,×1÷-109 10y 小主元/ Small pivot element可能导致计 0 10-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...0110 −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 */ 可能导致计 算失败
全主元消去法/ Complete Pivoting 每一步选绝对值最大的元素为主元素,保证|mk|≤ Step k:④选取a1k=,n1 an;|≠0 ②Ifik≠ k then交换第k行与第i行 Ifj≠ k then交换第k列与第j列; ③消元 注:列交换改变了x的顺序,须记录交换次序,解完后再 换回来 列主元消去法/ Partial Pivoting, or maximal column pivoting 省去换列的步骤,每次仅选一列中最大的元。 k =max a k≤i≤n
全主元消去法 /* 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
例:|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