武汉大学：《数值分析》课程教学资源（PPT课件讲稿）第二章 求解线性方程组的数值解法 2.1 线性方程组的直接法

第二章求解线性方程组的数值解法 武汉大学数学与统计学院

第二章 求解线性方程组的数值解法 武汉大学数学与统计学院

n阶线性方程组: aux+anx2++aux=b ax+a2x2++a nx=b2 anxi+amx++amx=b 矩阵表示记为AX=b 这里A=[anm,X=(x1,…,xn),b=(b bn) 解线性方程组的两类方法: 直接法:经过有限次运算后可求得方程组精确解的方法 (不计舍入误差!) 迭代法:从解的某个近似值出发,通过构造一个无穷 序列去逼近精确解的方法(一般有限步内得不到精确解)

11 1 12 2 1 1 21 1 22 2 2 2 1 1 2 2 n n n n n n nn n n n a x a x a x b a x a x a x b a x a x a x b  + + + =   + + + =    + + + =  阶线性方程组： [ ] , X , 1 1 T ij n n AX b T A n n a b  (x (b , , ) , , ) x b = = = = 矩阵表示记为 这里 解线性方程组的两类方法: 直接法: 经过有限次运算后可求得方程组精确解的方法 (不计舍入误差!) 迭代法：从解的某个近似值出发，通过构造一个无穷 序列去逼近精确解的方法(一般有限步内得不到精确解)

§21解线性方程组的直接法 §211高斯消去法和选主元高斯消去法 高斯消去法 思首先将方程组4xb化为上三角方程组, 路此过程称为消去过程,再求解上三角方程 组,此过程称为回代过程

§2.1 解线性方程组的直接法 一、高斯消去法 思 路 首先将方程组Ax=b 化为上三角方程组， 此过程称为消去过程，再求解上三角方程 组，此过程称为回代过程. §2.1.1 高斯消去法和选主元高斯消去法

消去过程: 己4)=A=(a0),b(1)=b=(h1)b(1))7 (1) 第一步:设d1≠叶针算因子1= (1) 将增广矩阵的第i行+l×第1行,得到 其中 12 In b 2 2.3.….n A42 b2=bo+1bo

将增广矩阵的第 i 行 + l i1  第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 n b (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 i j i j i j 

第k步:设≠叶计算因子l1=-a)1a(i=k+1,,m) 且计算{4" (k) (k+1) (k) b (k) kk (ij=k+1,…,n) 共进行n-1步,得到 (1) (1) n b1) 11 1 (2) 2 2 (n)

0 ( )  k 第k步：设 akk ，计算因子 且计算 ( ) ( ) / ( 1, ..., ) k k ik ik kk l a a i k n = − = + ( 1) ( ) ( ) ( 1) ( ) ( ) ( , 1, ..., ) k k k ij ij ik kj k k k i i ik k a a l a b b l b i j k n + +  = +   = + = + 共进行 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=bm)/am j=i+1 (L=n 定理:若4的所有顺序主子式均不为0,则高斯消 去法能顺序进行消元,得到唯一解。 det(A)

( ) ( ) / n nn n xn = bn a ( 1, ..., 1) ( ) 1 ( ) ( ) = − − = = + i n a b a x x i i i n j i j i i j i i i 定理：若A的所有顺序主子式 均不为0，则高斯消 去法能顺序进行消元，得到唯一解。 i ii i i a a a a A ... ... ... ... ... det( ) 1 11 1 = 回代过程：

二、选主元消去法 在高斯消去法消去过程中可能出现qk=0的情况,这时 高斯消去法将无法进行;即使主因素a≠0但很小 其作除数,也会导致其它元素数量级的严重增长和舍 误差的扩散 为避免这种情况的发生,可通过交换方程的次序,选取 绝对值大的元素作主元基于这种思想导出了主元素法

二、 选主元消去法 为避免这种情况的发生, 可通过交换方程的次序，选取 绝对值大的元素作主元. 基于这种思想导出了主元素法 在高斯消去法消去过程中可能出现 的情况，这时 高斯消去法将无法进行；即使主因素 但很小， 其作除数 ，也会导致其它元素数量级的严重增长和舍 误差的扩散 ( ) 0 k kk a = ( ) 0 k kk a 

列主元消去法 在第/步消元前,在系数矩阵第刚列的对角线以 下的元素中找出绝对值最大的元。 a4|=max|ak|≠O 眷pk,交换第k个与第p个方程后,再继续消去计算 这种方法称为列主元 Gauss消去法。 列主元 Gauss消去法保证了|lk|≤1 i=k+1k+2…,n)

❖ 列主元消去法 在第k步消元前，在系数矩阵第k列的对角线以 下的元素中找出绝对值最大的元。 | | max | | 0 pk k k ik k i n a a   =  若p≠k，交换第k个与第p个方程后，再继续消去计算. 这种方法称为列主元Gauss消去法。 列主元Gauss消去法保证了｜lik｜≤1 (i=k+1,k+2,…，n)

冷全主元消去法 在第/步消去前,在系数矩阵右下角的n-k+1 阶主子阵中,选绝对值最大的元素作为主元素。 a|= max a≠0 k≤i,j≤n (1)Ifp≠ k then交换第k行与第p行; Ifq≠ k then交换第k列与第q列; (2)消元 注:列交换改变了x的顺序,须记录交换次序, 解完后再换回来

❖ 全主元消去法 在第k步消去前， 在系数矩阵右下角的n-k+1 阶主子阵中，选绝对值最大的元素作为主元素。 (1) If p  k then 交换第 k 行与第p行; If q  k then 交换第 k 列与第 q 列; (2) 消元 注：列交换改变了 xi 的顺序，须记录交换次序， 解完后再换回来。 , | | max | | 0 pq k k ij k i j n a a   = 

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

➢ 运算量 （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