武汉大学数学与统计学院：《数值分析》第二章 求解线性方程组的数值解法（2.1）线性方程组的直接法

第二章求解线性方程组的数值解法 (Numerical Solution of linear equations)

第二章 求解线性方程组的数值解法 (Numerical Solution of Linear Equations)

x,+a1xn+∴.a,x.=b nn 1X1十a2x+… Ixt anax x= b nn n 矩阵表示记为AX=b 这里A=(an)n,我们假设A|≠0, ⅹ=(x1, xn), b=(b bn)

11 1 12 2 1 1 21 1 22 2 2 2 1 1 2 2 (1) n n n n n n nn n n a x a x a x b a x a x a x b a x a x a x b                     , 0, X , . 1 1 ij n n T AX b A T n n a (x , , x ) b (b , ,b )         矩阵表示记为 这里 我们假设 A

解线性方程组的两类方法 直接法:经过有限步运算后可求得方程组精确解的方 法(不计舍入误差!)(2.1节) 迭代法:从解的某个近似值出发,通过构造一个无穷 序列去逼近精确解的方法。分为两类: 逐次逼近法(一般有限步内得不到精确解)(2.2节) 共轭斜量法(不考虑计算过程的舍入误差,只用有 限步就收敛于方程组的精确解)(2.3节)

直接法: 经过有限步运算后可求得方程组精确解的方 法(不计舍入误差!)（2.1节） 迭代法：从解的某个近似值出发，通过构造一个无穷 序列去逼近精确解的方法。分为两类： 逐次逼近法(一般有限步内得不到精确解) （2.2节） 共轭斜量法（不考虑计算过程的舍入误差，只用有 限步就收敛于方程组的精确解）（2.3节） 解线性方程组的两类方法

§21解线性方程组的直接法 Direct Method for Solving Linear Systems) §2.11求解Ax=b的高斯消去法和选主元高斯消去法 >高斯消去法( Gaussian Elimination) 思首先将A化为上三角阵( upper-triangular 路 matrix),此过程称为消去过程,再求解如 下形状的方程组,此过程称为回代求解 backward substitution

§2.1 解线性方程组的直接法 ( Direct Method for Solving Linear Systems) Ø高斯消去法 (Gaussian Elimination) 思 路 首先将A化为上三角阵 ( upper-triangular matrix )，此过程称为消去过程，再求解如 下形状的方程组，此过程称为回代求解 ( backward substitution )。 = §2.1.1求解 A x  b的高斯消去法和选主元高斯消去法

消去过程: 记A(=A=( b(1)…b(1))7 第一步:设a0≠0,计算因子l=一1 将增广矩阵的第i行+l×第1行,得到: 其中 l”+la),j=23…1n 162=60+1 6

将增广矩阵的第 i 行 + li1  第1行，得到： 记 ( ) , (1 ) (1 ) A  A  aij n n ( 1 ) ( 1 ) ( 1 ) ( ) 1 T b b b b n    消去过程： 第一步：设 0 ，计算因子 (1) a11  (1) 11 (1) 1 1 a a l i i   (1 ) 1 (1 ) 1 (1 ) 12 (1 ) 11 a a ... a b n (2) A (2) b  其中         (1) 1 1 (2) (1) (1) 1 1 (2) (1) , , 2,3, , b b l b a a l a i j n i i i ij ij i j 

第k步:设a≠0,计算因子l=-a)/a)(=k+1…,m 将增广矩阵的第i行+l×第k行,得到: lk 1k+1 In 0 (k) (k) (k) kk k.k+1 0 0 (k+1) (k+1) k+1) k+1 b (k+1) (k+1) n.k+1 n (k+1) (k) +. a 其中 (k+1) k b(k)+ b (k) ikk

0 ( )  k 第k步：设 a kk ，计算因子 ( ) ( ) / ( 1, ..., ) k k ik ik kk l  a a i  k  n 将增广矩阵的第 i 行 + lik  第k行，得到： ( 1 ) ( ) ( ) ( 1 ) ( ) ( ) ( , 1, ..., ) k k k ij ij ik k j k k k i i ik k a a l a b b l b i j k n            其中 (1) (1) (1) (1) (1) 11 1 1, 1 1 1 1 ( ) ( ) ( ) ( ) , 1 ( 1) ( 1) ( 1) 1, 1 1, 1 1 ( 1) ( 1) ( ) , 1 0 0 0 0 0 k k n k k k k kk k k kn k k k k k k k k n k k k k k n k nn n n a a a a x b a a a x b a a x b a a x b                                                       

共进行n-1步,得到 ,(1) (1) (1) (1) 12 In (2) n (n 回代过程:x =ba o - x 丿=+1 定理:若A的所有顺序主子式均不为0,则高斯消 去法能顺序进行消元,得到唯一解

( ) ( ) / n nn n n n x  b a ( 1, ..., 1) ( ) 1 ( ) ( )       i n a b a x x i ii n j i j i ij i i i 定理：若A的所有顺序主子式 均不为0，则高斯消 去法能顺序进行消元，得到唯一解。 回代过程： 共进行 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

运算量( Amount of Computation) (1)用克莱姆( Cramer)法则求解n阶线性方程组 Ol=1.2 每个行列式由n!项相加,而每项包含了n个因子 相乘,乘法运算次数为(n-1)n!次.蕌 仅考虑乘(除)法运算,计算解向量包括计算 n+1个行列式和n次除法运算,乘(除)法运算次 数N=(n+1)(n-1)n!+n 当n=8时,N=200,0000

Ø 运算量 （Amount of Computation） （1）用克莱姆（Cramer）法则求解n阶线性方程组 每个行列式由n!项相加，而每项包含了n个因子 相乘，乘法运算次数为(n-1)n !次. , 1, 2 , ..., i i D x i n D   仅考虑乘(除)法运算,计算解向量包括计算 n+1个行列式和n次除法运算,乘(除)法运算次 数N=(n+1)(n-1)n!+n. 当n=8时,N＝200，0000

(2)高斯消去法: 第1个消去步,计算11(i=2,3,…,n),有n-1次 除法运算.使a1;①变为a1;(2)以及使b;①变为b1(2) 有n(n-1)次乘法运算 第k个消去步,有n-k次除法运算、(n-k+1)(n-k)次 乘法运算 乘法运算总次数为: ∑k(k-1)=( k=1 除法运算总次数为:(n-1)+.+1n(n-1)/2

（2） 高斯消去法: 第1个消去步， 计算li1(i=2,3，…，n)， 有n-1次 除法运算. 使aij (1)变为 aij (2) 以及使bi (1)变为bi (2) 有n(n-1)次乘法运算. 第k个消去步，有n-k次除法运算、(n-k+1)(n-k)次 乘法运算. 乘法运算总次数为： 除法运算总次数为: (n-1)+…+1=n(n-1)/2 3 1 1 ( 1 3 n k k k ) ( n n)    

回代过程的计算 除法运算次数为n次.乘法运算的总次数为 n+(n-1)+…+1=n(n-1)2次 > Gauss消去法 除法运算次数为:n(n-1)/2+n=n(n+1)/2, 乘法运算次数为:蕌 n(n-1)(n+1)/3+n(n-1)/2=n(n-1)(2n+5)/6, (n=30,为9890) 通常也说Gaus消去法的运算次数与n3同阶,记为0(n3)

回代过程的计算 除法运算次数为n次. 乘法运算的总次数为 n+(n-1)+…+1=n(n-1)/2次 Ø Gauss消去法 除法运算次数为:n(n-1)/2+n=n(n+1)/2， 乘法运算次数为: n(n-1)(n+1)/3+n(n-1)/2=n(n-1)(2n+5)/6， 通常也说Gauss消去法的运算次数与n 3同阶，记为O(n 3) (n  30,为9890)