第三章解线性方程组的直接法 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 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
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...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 */ 可能导致计 算失败。 §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