第二章线性代数方程组的直接解法

1、数数 值值 分分 析析武武 汉汉 大大 学学数学与统计学院基础数学系数学与统计学院基础数学系刘丁酉 主页主页2 2 线性代数方程组的直接解法线性代数方程组的直接解法主页主页 2.1 2.1 引论引论 2.2 2.2 GaussGauss消去法消去法 2.3 2.3 直接三角分解方法直接三角分解方法 2.4 2.4 矩阵的条件数与病态方程组矩阵的条件数与病态方程组 2.1 2.1 引论引论主主nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111 nnnnnnnnbbbbxxxXaaaaaaaaaA21212122221112112.2 Gaoss

2、2.2 Gaoss消去法消去法2.2.1 2.2.1 顺序消去与回代过程顺序消去与回代过程2.2.2 2.2.2 顺序消去能实现的条件顺序消去能实现的条件2.2.3 2.2.3 矩阵的三角分解矩阵的三角分解2.2.4 2.2.4 列主元素消去法列主元素消去法主页主页2.2.1 2.2.1 顺序消去与回代过程顺序消去与回代过程1,3322111, 223232221211, 11313212111nnnnnnnnnnnnnnaxaxaxaxaaxaxaxaxaaxaxaxaxa主页主页(0)(0)(0)(0)(0)111122133111(1)(1)(1)(1)222233221(2)(2)(2

3、)333331(1)(1)1nnnnnnnnnnnnnnnnaxaxaxaxaaxaxaxaaxaxaaxa主页主页消元公式消元公式( 1)( 1)(k)( 1)( 1)ij, 1 k n-1, k+1 i na, k+1 i n, k+1 j n+1kikikkkkkkijik kjalaal a 回代公式回代公式(1)1(1)(1)(1)11(1),1,2,1nnnnnnnniiinijjj iijiiaxaaaxxinna 在上面的消元过程中在上面的消元过程中,应特别注意到元素应特别注意到元素(称之为主称之为主元素元素).因为如果主元素为因为如果主元素为0,消元过程将无法进行下去消元过程

4、将无法进行下去.如如果主元果主元 的绝对值较小的绝对值较小,作为除数也不合适作为除数也不合适.所以这种所以这种方法是不恰当的方法是不恰当的. 另外另外,我们总是通过乘数我们总是通过乘数 来消元来消元,从而称从而称 为乘为乘数数.(1)kkka主页主页iklikl2.2.2 2.2.2 顺序消去实现的条件顺序消去实现的条件n nA R120,0,0k (0)(1)(1)11220,0,0kkkaaa主页主页定理定理2.2.12.2.1 设设，若对若对k=1,2,k=1,2,，n n，A A的顺序主子式的顺序主子式，则每步消去过程的对角元，则每步消去过程的对角元定理2.2.1的逆定理也成立，即若则

5、则120,0,0k (0)(1)(1)11220,0,0kkkaaa2.2.3 2.2.3 矩阵的三角分解矩阵的三角分解主页主页引理引理3.13.1 用用m m阶单位下三角方阵阶单位下三角方阵L L左乘左乘m mn n阶矩阵阶矩阵A A所得所得矩阵矩阵B,B,则则A A与与B B的的p p阶主子式相等阶主子式相等.21m m12,10010 L1m nm nmmBlll 证 设A11111211122122212221220BB, , B=BBLAALALLAA11111112211122212112222211122122LALALALALALALABBBB111111,L A B11111

6、1L AB111111111111L ALAAB1112112122, 0,0aaAaAaa证 设依条件1112(0)(0)11121221(1)22221100aaaaAa aaaa(0)(0)111221(1)221110aa, U=10aLaaALU所以,当n=2时,定理成立. 设当n=k时,定理成立. 则,当n=k+1时,有:11,1,11,11,12,13,11,1 (i=2,3,k+1) a0(,)TkiiTkarASAalamlll11121,k+121222,k+1k+1,1k+1,2k+1,k+1aaaaaaaaa其中 1,1110TkkkarAmESB于是,kkL Ukkk

7、BL U11010kkm Em E11111111111101000101000100TTkkkkkkTkkkTkkkkararAmEmEBLUarmELUarL UmLUkB又所以,.ALU ALULULU11U ULL1-1, LUUELE由于此式左边上三角矩阵由于此式左边上三角矩阵, ,右边为下三角矩阵右边为下三角矩阵, ,所所以必有以必有, U=ULL1122nnALUL UUu uu 此定理是矩阵分解的重要定理,称作矩阵的LU分解,也叫杜利特尔分解. 它是用直接法解线性方程组的理论基础.此外,可利用LU分解来计算A的行列式的值.即:), 3 , 2(111niylbybykikiki

8、i) 1, 2, 1(1niuxuyxuyxiiknikikiinnnn（4）（5）进而,由 LY=b, UX=Y, 有: 解决问题的方法是:在系数矩阵中按列选取绝对值最大的元素作为主元素进行消元.以后每一步都作一次这样的调整.直至将系数矩阵化为上三角矩阵.称这种消元法为: 列主元消元法. 另外还有: 全主元消元法.2.2.4 2.2.4 列主元素消去法列主元素消去法主页主页2.3 2.3 直接三角分解方法直接三角分解方法2.3.1 Doolittle2.3.1 Doolittle分解方法分解方法2.3.2 2.3.2 三对角方程组的追赶法三对角方程组的追赶法2.3.3 2.3.3 对称正定矩

9、阵的对称正定矩阵的CholeskyCholesky分解、分解、 平方根法平方根法主页主页 杜杜立特分解法立特分解法 / /* * Doolittle Factorization Doolittle Factorization LULU 分解的紧凑格式分解的紧凑格式反复计算反复计算,很浪费哦很浪费哦 通过比较法直接导出通过比较法直接导出L 和和 U 的计算公式。的计算公式。思思路路2.3.1 Doolittle2.3.1 Doolittle分解方法分解方法主页主页 nnnnnnnnuuullaaaa.1.11.1111211111 j ia ),min(1jikjkkiul直接三角分解法解直接三

10、角分解法解AX = b的计算公式的计算公式niauii, 2 , 111niualii, 2 , 11111对对于于r = 2, 3, , n计算计算（2 2）计算）计算U U的第的第r r行元素行元素 ), 1,( 11nrriulaurkkirkriri（3 3）计算）计算L L的第的第r r 列元素列元素 ( (r r n n) ), 1()(11nriuulalrrrkkrikirir(1)2.4 2.4 矩阵的条件数与病态方程组矩阵的条件数与病态方程组2.4.1 扰动方程组、病态现象2.4.2 矩阵的条件数与扰动方程组的 误差分析2.4.3 病态方程组的解法主页主页2.4.1 2.4

11、.1 扰动方程组、病态现象扰动方程组、病态现象A,det0.n nRA,AAbb和()()AA xxbb 主页主页设方程组Ax=b的系数矩阵A和右端向量b若有扰动，分别成为那么实际解的是方程组这里1.xA b我们要问，若|Ab和都是小的实数，|x是否也是小的？这就是扰动方程组的误差分析问题。主页主页例例2.4.1 方程组123143.0001 14.0001xx123142.99914.0002xx(1,1) .Tx ( 2,10) .Tx 的准确解是若A及b有微小的变化，扰动后方程组为则其解可见A,b的微小变化可以使解有很大的变化。从上面的例子可以看到，方程组的解对A或b的扰动可能是敏感的，

12、这时称方程组是病态方程组（或A是病态矩阵），病态与否决定于A。求解求解 时，时，A A 和和 的误差对解的误差对解 有何影响？有何影响？bxA bx 设设 A 精确，精确， 有误差有误差 ，得到的解为，得到的解为 ，即，即bb xx bbxxA )(bAx 1 |1bAx 绝对误差放大因子绝对误差放大因子|xAxAb 又又|1bAx |1bbAAxx 相对误差放大因子相对误差放大因子2.4.2 2.4.2 矩阵的条件数与扰动方程组的误差分析矩阵的条件数与扰动方程组的误差分析bxxAA )( 设设 精确，精确，A有误差有误差 ，得到的解为，得到的解为 ，即，即bA xx bxxAxxA )()(

13、 )(1xxAAx |11AAAAAAxxx 是关键是关键的误差放大因子，称为的误差放大因子，称为A的的条件数条件数，记为，记为cond (A) ,越越 则则 A 越病态，越病态，难得准确解。难得准确解。|1 AA大大定义定义6 6：设设A A 为为n n 阶非奇矩阵，称数阶非奇矩阵，称数 为矩阵为矩阵A A的的 条件数，条件数，AA1条件数的性质：条件数的性质： ）cond ( A )1）cond ( kA )= cond ( A ) k k 为非零常数为非零常数）若若 ， 则则1A1)(cond AA记为记为cond( A )。 iv ) 设对角矩阵设对角矩阵D D非奇异非奇异, ,则则1

14、1max()minii nii ndcond Dd 定义7:设A是非奇异矩阵,若Cond(A)远大于1,则称方程组AX=b是病态的,否则称方程组是良态的.对于先前的例子114111.000111,11.0001110.0001()2.0001* 2.0001*10 40000AACond AAA所以是病态方程组,从而不能用直接法求解. 一个方程组是否病态，由一个方程组是否病态，由A的性质决定，与用什么数值的性质决定，与用什么数值解法无关。对于病态的方程组。数值求解要小心进行，否解法无关。对于病态的方程组。数值求解要小心进行，否则可能得不到所要求的精确度。则可能得不到所要求的精确度。 解病态方程组，可以采用高精度运算，例如双倍或更多解病态方程组，可以采用高精度运算，例如双倍或更多倍字长的运算，使由于误差放大而损失若干有效数位之倍字长的运算，使由于误差放大而损失若干有效数位之后，还能保留一些有效位。后，还能保留一些有效位。2.4.3 2.4.3 病态方程组的解法病态