计算方法第5章解线性方程组直接方法

1、2021-7-10计算方法第5章解线性方程组直接 方法 1 解线性方程组的直接方法解线性方程组的直接方法 2021-7-10计算方法第5章解线性方程组直接 方法 2 第五章第五章 解线性方程组的直接方法解线性方程组的直接方法 5.1 5.1 引言引言 解线性方程组的两类方法： 直接法: 经过有限次运算后可求得方程组精确解的 方法(不计舍入误差) 迭代法：从解的某个近似值出发，通过构造一个无穷 序列去逼近精确解的方法。（一般有限步内得不到精 确解） 2021-7-10计算方法第5章解线性方程组直接 方法 3 , X , 11 T n n ij AXb T A nn , , ) , , )(x(b

2、 xbab 矩阵表示记为 这里 nnnnnn nn nn bxaxaxa bxaxaxa bxaxaxa 2211 22222121 11212111 n阶线性方程组 2021-7-10计算方法第5章解线性方程组直接 方法 4 35 det( )0, det() (1,2, ) det( ) 1 (1)! 30,2.38 10 i i A A xin A nnn nnn n n 如果线性方程组的系数行列式不为零，即 则该方程组有唯一解。由克莱姆(cramer)法则，其解为 这种方法需要计算个 阶行列式并作 次除法，而每个 阶行列式计算需作次乘法，计算量十分惊人。 如需次乘法。可见其在理论上是绝

3、对正确， 但在 较大时，在实际计算中确实不可行的。 35 det( )0, det() (1,2, ) det( ) 1 (1)! 30,2.38 10 i i A A xin A nnn nnn n n 如果线性方程组的系数行列式不为零，即 则该方程组有唯一解。由克莱姆(cramer)法则，其解为 这种方法需要计算个 阶行列式并作 次除法，而每个 阶行列式计算需作次乘法，计算量十分惊人。 如需次乘法。可见其在理论上是绝对正确， 但在 较大时，在实际计算中确实不可行的。 2021-7-10计算方法第5章解线性方程组直接 方法 5 5.2 5.2 高斯消去法高斯消去法 11112211 2112

4、2222 1122 nn nn nnnnnn n a xa xa xb a xa xa xb a xa xa xb 对 阶线性方程组： 11 , nn xxx 称消元过程。 逐次计算出称回代过程。 (1)(1)(1)(1)(1) 11112213311 (2)(2)(2)(2) 22223322 (3)(3)(3) 33333 nn nn nn a x a xa xa xb a xa xa xb a xa xb ( )( ) nn nnnna xb 转化为同解的方程组 2021-7-10计算方法第5章解线性方程组直接 方法 6 11 bbaa )( ii )( ijij , 统一记号： 111

5、11 11 1 T ( )( )( )( )( ) ij ( )( ) X : , n (, , )babAA bb 原方程 )( )( :0 1 11 1 21 )1( 11 新第二行（第一行）第二行 若 aa a )()( )( )()( 1 11 1 31 新第三行第一行第三行 aa )()( )n(n aa )()( n 行新第（第一行）行第 )( 1 11 1 1 5.2.1 5.2.1 高斯消去法计算过程高斯消去法计算过程 2021-7-10计算方法第5章解线性方程组直接 方法 7 (1)(1)(1)(1)(1) 11112213311 (2)(2)(2)(2) 22223322

6、(2)(2)(2)(2) 32233333 (2)(2) 2233 nn nn nn nn a x a xa xa xb a xa xa xb a xa xa xb a xa x (2)(2) nnnna xb 2021-7-10计算方法第5章解线性方程组直接 方法 8 22 x bA （ ）（ ） 得到新同解方程组： b b b b aa aa aaa A nnnn n n )2( )2( 2 )1( 1 (2) )2()2( 2 )2( 2 )2( 22 )1( 1 )1( 12 )1( 11 )2( 0 0 ，其中 aamamaa )()( ii )( ji )( ij )( ij 1

7、11 1 11 1 11 12 211 11 2 3 , ()()() iii , , ,n i jbbbm 2021-7-10计算方法第5章解线性方程组直接 方法 9 子阵作如上计算： 对除第一行第一列外的，若第二步消元： 0 )2( 22a 00 00 0 3 3 3 2 2 1 1 (3) 33 3 3 3 3 33 2 2 2 23 2 22 1 1 1 13 1 12 1 11 3 b b b b b aa aa aaa aaaa A )( n )( )( )( )( nn )( n )( n )( )( n )()( )( n )()()( )( =， aamamaa ijijij

8、 )2( 22 )2( 2i2 )2( 2i2 )2()3( 322 22 3 4, ()()() iii , , ,n i j bbbm 2021-7-10计算方法第5章解线性方程组直接 方法 10 bxA )()(33 =得到同解方程组 行下去则此消去过程可依次进，若 0 )3( 33 a ( )( ) 1 nn n x bA 第步消去过程后， 得到等价三角方程组。 (1)(1)(1)(1)(1) 11112213311 (2)(2)(2)(2) 22223322 (3)(3)(3) 33333 nn nn nn a x a xa xa xb a xa xa xb a xa xb ( )(

9、 ) nn nnnna xb 2021-7-10计算方法第5章解线性方程组直接 方法 11 (1)(1)(1)(1)(1) 11121311 (2)(2)(2)(2) 222322 (n)( ) (3)(3)(3) 3333 ( )( ) 0 00 000 b n n n n nn nnn aaaab aaab A aab ab ， 系数矩阵与常数项： 2021-7-10计算方法第5章解线性方程组直接 方法 12 回代过程: (1)(1)(1)(1) 111111 ( )( )( ) (1)(1)(1) 11111 iinn iii iiiinni nnn nnnnnnn a xa xa xb

10、 a xa xb axaxb ( )( ) nn nnnna xb abx )n( nn )n( nn = ( )( )( ) 1 () in1 , n2 , , 1 n iii iiijjii j i xba xa 2021-7-10计算方法第5章解线性方程组直接 方法 13 123 23 123 133233 6; 45; 221. 11161116 |04150415 221104111 1116 0415 0026 ( 2), xxx xx xxx A b rrrrrr 例1：用消去法解方程组 解：用增广矩阵表示求解过程 2021-7-10计算方法第5章解线性方程组直接 方法 14 消

11、去第一列的 n-1 个系数要计算n*(n-1） 个乘法。 1 2 2)n()*(n-n二 )(n n k) (k n k 1 3 2 1 2 乘法总计 2 1 1 1 )n(n k n k 除法 1 2 n(n) 回代总计算量 3 21 (30,9890) 33 nn n n 总乘除法共为 5.2.2 5.2.2 高斯消去法计算量高斯消去法计算量 2021-7-10计算方法第5章解线性方程组直接 方法 15 (2)(1)(2)(1) 11 1121 1111 311 1 , 1 1 01 2 3 001 L ( )( ) ii n i, ,n bbAL AL m m aa m m 记： 其中

12、每一步消去过程相当于左乘初等变换矩阵Lk 5.2.3 5.2.3 矩阵的三角分解矩阵的三角分解 2021-7-10计算方法第5章解线性方程组直接 方法 16 (3)(2)(3)(2) 22 22 2222 322 2 , 1 01 01 3 4 001 L ()() ii n i, ,n bbAL AL m aa m m 记： (3)(1)(3)(1) 2121 , bbAL L AL L 2021-7-10计算方法第5章解线性方程组直接 方法 17 1 121 1 121 (n)() nn (n)() nn ALLL A bbLLL -1 i 1, 1, 1 1 01 01 1 1 01 0

13、1 01 01 i i ii ii ni ni LL m m m m 列 i列 i+1行 i+1行 -1 iiLL 与依次递推 2021-7-10计算方法第5章解线性方程组直接 方法 18 LUULLLAA n 1 1 1 2 1 1 )1( 1 1 1 21 211 1 1 2 1 1 mm m nn n LLLL 定理定理7 7（矩阵的（矩阵的LULU分解）分解） 设A为n阶矩阵，如果A的顺序主子式顺序主子式 D Di i0 0（i=1，2，n-1），则A可分解为一个单位下 三角矩阵L和一个上三角矩阵U的乘积，且这种分解是 唯一唯一的。 )(n AU 2021-7-10计算方法第5章解线性

14、方程组直接 方法 19 ( ) ( ) 213132 1 11161116 |04150415 221104111 1116 0415 0026 (1, ) 0,2,1, k ik kik kk A b a mikn a mmm 例2：对于例 ，由增广矩阵表示消元过程有 由 故有 100111 010041. 211002 ALU 2021-7-10计算方法第5章解线性方程组直接 方法 20 5.3 5.3 高斯主元素消去法高斯主元素消去法 ( ) ( ) 0 0 k kk k kk a a 在高斯法消元过程中可能出现的情况，这时消去法 将无法进行；即使主元素但很小，用其作除数，也会 导致其他

15、元素数量级的严重增长和舍入误差的扩散。 为避免此种情况的发生，可通过交换方程的次序，选取绝对值大绝对值大 的元素作主元。 5.3.1 列主元素消去法 2021-7-10计算方法第5章解线性方程组直接 方法 21 nkkjiaa k ij k kk , 1,max )()( 选取 或 nkkiaa k ik k kk , 1,max )()( 称此方法为全主元素高斯消去法 称此方法为列主元素高斯消去法 2021-7-10计算方法第5章解线性方程组直接 方法 22 1 2 3 * 0.0012.0003.0001.000 31.0003.7124.6232.000 2.0001.0725.6433

16、.000 ( 0.4904, 0.05104,0.3675) 1 0.0012.0003.0001.000 |1.000 T x x x x A b 例 ：阶方程组 四位有效数字精确解为 解：（ ）高斯消去法 21 22 32 1000 2000 1.997 3.7124.6232.000 2.0001.0725.6433.000 0.001 2.0003.000 1.0000.001 2.0003.0001.000 02004300510020200430051002 0400160062003005.0002.000 ( 0. m m m x 400, 0.09989,0.4000)T 3

17、 2021-7-10计算方法第5章解线性方程组直接 方法 23 21 22 0.5000 0.0005 2 2.0001.0725.6433.000 |1.0003.7124.6232.000 0.0012.0003.0001.000 2.0001.0725.6433.000 03.7121.8010.500 02.001 3.003 1.002 m m A b （ ）交换行，避免绝对值小的主元作除数。（列主元素法） 32 0.6300 2.0001.0725.6433.000 03.7121.8010.500 001.8680.687 ( 0.4900, 0.05113,0.3678) m

18、T x 31 rr 2021-7-10计算方法第5章解线性方程组直接 方法 24 定理8（列主元素的三角分解定理） 如果A为非奇异 矩阵，则存在排列矩阵P使 PA=LU 其中L为单位下三角阵，U为上三角阵。 2021-7-10计算方法第5章解线性方程组直接 方法 25 3 2 GaussJordan A n 消去对角线下方和上方的元素，此方法称 消去法。G-J方法将 约化为单位矩阵，计算解就在常数项 得到，无需回代求解。计算量大约需次乘除法，要比高 斯消去法大。G-J方法主要用途是求一个矩阵的逆矩阵。 1 123 5 G-J245. 356 123100356001 |245010245010

19、 356001123100 n AA A I 例 ： 用法求的逆矩阵 解： 5.3.2 5.3.2 高斯高斯若当消去法若当消去法 2021-7-10计算方法第5章解线性方程组直接 方法 26 1 15/32001/3 02/31012/3 01/31101/3 101/205/22 013/203/21 001/211/20 100132 010331|. 001210 n IA 2021-7-10计算方法第5章解线性方程组直接 方法 27 本章作业 P176 7 2021-7-10计算方法第5章解线性方程组直接 方法 28 5.4 矩阵三角分解法矩阵三角分解法 5.4.1 直接三角分解法直接

20、三角分解法 将高斯消去法改写为紧凑形式，可以直接从矩阵A的元素 得到计算L,U元素的递推公式，而不需要任何中间步骤， 这就是直接三角分解法。 由于A=LU，求解Ax=b的问题就等价于求解两个三角形方程组 Ly=b，求y； Ux=y，求x. 2021-7-10计算方法第5章解线性方程组直接 方法 29 1、不选主元的三角分解法 nn n n nn u uu uuu ll l A 222 11211 21 21 1 1 1 A=LU 其中L为单位下三角阵，U为上三角阵 （4.1） 2021-7-10计算方法第5章解线性方程组直接 方法 30 一、直接计算 A 的 LU 分解(例) 000 00 0

21、 1 01 001 0001 44 3433 442322 14131211 434241 3231 21 44434241 34333231 24232221 14131211 u uu uuu uuuu lll ll l aaaa aaaa aaaa aaaa uululululululululul uululuululululul uuluuluulul uuuu 44344324421441334323421341224212411141 34243214313323321331223212311131 2414212313212212211121 14131211 + + + 202

22、1-7-10计算方法第5章解线性方程组直接 方法 31 uululululululululul uululuululululul uuluuluulul uuuu 44344324421441334323421341224212411141 34243214313323321331223212311131 2414212313212212211121 14131211 + + + n. , 3,i - ; - , - 2 n , 2,j , - ; - , - , - u2 n ,2,i , ; , , 1 n , 1,j , ; , , , 1 2212i22i2 2212414242221

23、2313232 12122j 142124241321232312212222 111i1114141113131112121 11j1414131312121111 uulal uulaluulal ulau ulauulauulau ualualualual auauauauau )( )()(l l u i jj i j 列 行 列 行 2021-7-10计算方法第5章解线性方程组直接 方法 32 二、一般计算公式 n , 2,i , n, 1,j , 111i1 11 ual au i jj n)r , n; , r (i )/( , nr , ri n),(rrLrU uulal ulau rr r k krikirir r k kirkriri 且1 );1( 32 1 1 1 1 列元素的第行，的第计算 2021-7-10计算方法第5章解线性方程组直接 方法 33 三、LU 分解求解线性方程组 LY b , UXY AXb 11 2221 3132 12(1) 11 11121n 22 222n nn 1 1 1 1 UX nnnnn n nn y