数值分析(第二章：线性方程组求解1207)

1、第二章第二章 线性代数方程组的解法线性代数方程组的解法高斯高斯(Gauss)(Gauss)消元法消元法 矩阵的三角分解法矩阵的三角分解法 矩阵的条件数与方程组的性态矩阵的条件数与方程组的性态 迭代求解法迭代求解法11112211211222221122 nnnnnnnnnnna xa xa xba xa xa xba xa xa xb阶线性方程组： , X ,11Tn nijTA nn , , ) , , )(x(bxbab这里解线性方程组的两类方法解线性方程组的两类方法: :直接法直接法: : 经过有限次运算后可求得方程组精确解的方法经过有限次运算后可求得方程组精确解的方法( (不计舍不计舍

2、入误差入误差!)!)迭代法：从解的某个近似值出发，通过构造一个无穷序列去逼迭代法：从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法近精确解的方法( (一般有限步内得不到精确解一般有限步内得不到精确解) )第一节第一节 高斯消元法高斯消元法 AXb矩阵表示记为一、一、高斯消元法高斯消元法思思路路首先将方程组首先将方程组Ax=b 化为上三角方程组化为上三角方程组，此过程称为此过程称为消元过程消元过程，再求解上三角方程，再求解上三角方程组，此过程称为组，此过程称为回代过程回代过程. .设有线性方程组：AXAX=b b. , ,nnnnnnnnbbbxxxaaaaaaaaa21212122

3、22111211b bX XA Av（1）消元过程,)(记)1()1(nnijaAA( 1 )( 1 )( 1 )()1Tbbbbn其中第一步：若, 0)1 (11a用)1 (11)1 (11/aamii乘第一行加到第i行中，得到. 00)2()2(2) 1 (121)2()2(2)2(2)2(22) 1 (1) 1 (12) 1 (11nnnnnnnbbbxxxaaaaaaa), 3 , 2,( ,) 1 (11) 1 ()2(njiamaajiijij), 3 , 2( ,) 1 (11) 1 ()2(nibmbbiii第二步：若, 0)2(22a用 . 第k步：若, 0)(kkka用)(

4、)(/kkkkikikaam乘第k行加到第i行中，得到. 00) 1() 1(1)() 1 (111) 1() 1(1) 1(1) 1(11)()(1)() 1 (1) 1 (11) 1 (1) 1 (11knkkkknkkknnknkknkkkkkknkkkkkknkkbbbbxxxxaaaaaaaaaaa其中), 1,( ,)()() 1(nkjiamaakkjikkijkij), 1( ,)()() 1(nkibmbbkkikkiki共进行n-1步得到：. 000)()2(2) 1 (121)()2(2)2(22) 1 (1) 1 (12) 1 (11nnnnnnnnbbbxxxaaaa

5、aa（2）回代过程若, 0)(nnna则 )()(nnnannbnx) 1 , 1( ,)(1)()(nkkkkankjjxkkjabxkkk(1)(1)(1)11111, nnnnnnnnnnxbaxa设有线性方程组：AX=b. , ,nnnnnnnnbbbxxxaaaaaaaaa2121212222111211b bX XA A(1) 列主元消去法列主元消去法二、二、选主元消去法选主元消去法.0, 0)()(，使得计算结果不可靠增长和舍入误差的扩散级严重，会导致其他元素数量很接近于或若kkkkkkaa 为避免上述情况的发生为避免上述情况的发生, 可通过交换方程的次序，选取绝对值可通过交换方

6、程的次序，选取绝对值大的元素作主元大的元素作主元. 基于这种思想导出了主元素法，主要有全主元基于这种思想导出了主元素法，主要有全主元消去法消去法;列主元消去法列主元消去法. 第k步选主元素,. 0max,iknikkiaak然后交换第k行和第ik行(当ikk时),再进行第k次消元. 第n-1步. 000212122211211nnnnnnbbbxxxaaaaaa然后交换第1行和第i1行(当i11时),再进行第1次消元. 0max111 ,1iniiaa第一步:先在A的第一列选取绝对值最大的元素作主元素,回代求解 nnnabnx) 1 , 1( ,1nianijxabxiijijii|m ax

7、|0pkkkikkinaa 若若pk, 交换第交换第k个与第个与第p个方程后个方程后, 再继续消去计算再继续消去计算. .这种方法这种方法称为列主元称为列主元Gauss消去法。消去法。 注意：注意：n阶方程组第阶方程组第k 轮消元时，选第轮消元时，选第k 列的后列的后( n k + 1 )个个元素中绝对值最大作主元。即元素中绝对值最大作主元。即(2)全主元消去法全主元消去法 在第在第k 步消去前，步消去前， 在系数矩阵右下角的在系数矩阵右下角的n- k+1阶主子阵中，阶主子阵中，选选绝对值最大的元素作为主元素。绝对值最大的元素作为主元素。,|m ax |0pqkkijkijnaa(1) If

8、p k then 交换第交换第 k 行与第行与第p 行行; If q k then 交换第交换第 k 列与第列与第 q 列列;(2) 消元消元例例 列主元法列主元法 6745150710623321xxx第一列中绝对值最大是第一列中绝对值最大是10，取，取10为主元为主元 6515707104623 6515462370710 5 . 255 . 21 . 661 . 070710 2 . 62 . 65 . 255 . 270710第二列的后第二列的后两个数中选两个数中选出主元出主元 2.5 x1=0 x2= -1 x3=1x3=6.2/6.2=1x2=(2.5-5x3)/2.5= -1x1

9、=(7+7x2-0 x3)/10=0 三、三、运算量比较运算量比较 （1 1）用克莱姆用克莱姆（CramerCramer）法则法则nnn312331每个行列式由每个行列式由n!项相加项相加, 而每项包含了而每项包含了n个因子相乘个因子相乘,乘法运算乘法运算次数为次数为(n-1) n!次次.乘乘(除除)法运算次数法运算次数N=(n+1)(n-1)n!+n.,1, 2,.,iiDxinD（2 2）用高斯消去法用高斯消去法消元过程乘除法次数：回代过程乘除法次数：总的乘除法运算次数约为： 1(1)2n n13251263nnn通常也说通常也说Gauss消去法的运算次数与消去法的运算次数与n3同阶同阶,

10、记为记为O(n3)（3）列主元消去法）列主元消去法:（4）全主远消去法）全主远消去法: 比比 高斯消去法只多出高斯消去法只多出 , 略省时略省时. 32nO比比 高斯消去法多出高斯消去法多出 , 保证稳定保证稳定, 但费时但费时. 33nO第二节第二节 直接三角分解法直接三角分解法一、一、 高斯消元法的矩阵形式：高斯消元法的矩阵形式：L U 分解分解 每一步消去过程相当于左乘初等变换矩阵每一步消去过程相当于左乘初等变换矩阵L1(2)(1)(2)(1)11213111111111 , 1101 001 2 3Ln()()ii i, ,nbbAL ALllllaa记：其中(3)(2)(3)(2)2

11、23222222222 , 10101 001 3 4Ln()()iii, ,nbbAL ALlllaa记：其中11,1,11010111= 01010101 iiiiiininiLiiLllll列列()(1 )121()(1 )121nnnnnn ALLL AbbLLL(1)111( )( )121nnnLLUAL LL AAA 的的 LU 分解分解(3)(1)(3)(1)2121 , bbAL L AL LL 为单位下三角阵而为单位下三角阵而 U 为为一般一般上三角阵的分解上三角阵的分解称为称为Doolittle 分解分解 （2）L 为一般下三角阵而为一般下三角阵而 U 为为单位单位上三角

12、阵的分解称为上三角阵的分解称为Crout 分解分解。 Doolittle分解法分解法 ： 利用矩阵乘法，通过比较直接导出利用矩阵乘法，通过比较直接导出L 和和 U 的计算公的计算公式。式。思思路路 nnnnnnnnuuullaaaa.1.11.1111211111 ),min(1jikjkkiul jia一般计算公式L第一行乘第一行乘U 每一列：每一列： a11= u11, , a1n= u1nL每一行乘每一行乘U 第一列：第一列： a21 = l 21u11, , an1 = ln1u1111i1111 , 1, ,2, , jji jn inuala u注：注：该公式的特点：该公式的特点：

13、U 的元素按行求的元素按行求, L 的元素按列求的元素按列求; 先求先求 U 的第的第k 行行, 再求再求 L 的第的第k 列列, U 和和 L 一行一列交叉计算一行一列交叉计算. 计算计算量与量与 Gauss 消去法同消去法同.1kjkr11ikirkk1 3, , jk , , n ( )/ ik1 , , nkkjrjrkikrkrknual ulal uu对计 算 u22=a22 - l21u12, , u2n=a2n- l21u1n l32=(a32- l31u12)/u22, , ln2=(an2- ln1u12)/u22一般地：一般地： l31u12+ l32u22=a32, ,

14、 ln1u12+ ln2u22=an2L每一行乘每一行乘U 第二列：第二列：l 21u12+ u22=a22, , l21u1n+ u2n=a2nL第二行乘第二行乘U 每一列：每一列：1121 04-1-21ALU，作分解。例例.200140111112010001 LUA1kjkr1 kkjrjrual u1ikirkk1 ( )/kikrkrlal uu解：由公式得解：由公式得2131322223330,2,1,4,1,2llluuu 具体分解不必用公式，可直接利用矩阵乘法计算具体分解不必用公式，可直接利用矩阵乘法计算二、LU 分解求解线性方程组112221313212(1)111 1nn

15、nnn nybybLYbybllllll,nnnnnnuuuuulllLUA0001010012211211112111-11 , 2, 3, , (1) Y iiijijjinybyybl解： LY b , U X Y AX b1111121n22222nnn UXnnxyxyYxyuuuuuu ijii1( , in1, , 1 2) x nnnnnijij iyxuyxu xu 解：.,974,432232112 bAXLUAbA求解分解作，将设：练习练习.200120112111011001LU解：.111,234XyUXybLy1kjkr1 kkjrjrual u1ikirkk1 (

16、 )/kikrkrlal uu称为Cholesky分解，据此解AX=b即为平方根法平方根法,0000002221211121222111nnnnnnnnllllllllllllA即：三、三、 求解正定方程组的平方根法求解正定方程组的平方根法 如果系数矩阵是对称正定的（ aii 0 ），则可用相应的三角分解法即平方根法求解。优点：优点： 乘除法运算量比一般乘除法运算量比一般 LU分解要小得多；分解要小得多；缺点：缺点：有有n 个开方运算。个开方运算。为避免过多的开方运算，在更多情况下是将A分解为A=LDLT，其中L为下三角，D为对角阵。 在数值求解常微分方程边值问题、热传导方程时，常会要解三对角

17、方程组：AX=bAX=b并且满足. , ,212111122211nnnnnnndddxxxbacbacbacbb bX XA A02,01,(i) () ();iiaici| |(ii) | | | iiibac四、四、 解三对角方程组的解三对角方程组的追赶法追赶法A称为对角占优 的三对角阵。用相应的三角分解法即追赶法求解。第一步第一步 : 对对 A 作作Doolittle 分解分解追赶法计算步骤简介：追赶法计算步骤简介：（以四阶为例）以四阶为例）11112222223333334444112121223232334343411222133321111(1,2,3);iibcudlabcud

18、ALUlabcudlabuudl ul dudl ul dudl ul duububl ddciubl d 比较对应位置的元素，得递推公式：第二步：2213324434443/;/laulaulauubl d1111212222233332334444344112221333244431111yfyfl yyflyfLyflyfl yyfyfll yyfyfyfl yyfl yLyyfl yyf第三步：由：先求该过程称为该过程称为“追追”的过程。的过程。1111222233334444443334333432223211121/() /() /() /() /udxyudxyUxyudxyux

19、yxyuxyd xuyc xuxyc xuxyc xUxyxu第四步：再由回代解得解得：该过程称为该过程称为“赶赶”的过程。的过程。一、一、 向量和矩阵的范数向量和矩阵的范数 为了研究线性方程组的近似解的误差估计和迭代法的收敛性, 我们需要对Rn中的向量(或Rnn中的矩阵)的大小引进某种度量向量(或矩阵)的范数. 第三节第三节 矩阵的条件数与方程组的性态矩阵的条件数与方程组的性态1、 向量的范数向量的范数满足的某个非负实值函数或如果向量范数 |,|)()( xxNCRxnn) )定定义义2 2( (0 x(1) 正定性：,|0 x等号当且仅当时成立；(2) 齐次性：; | , xxR(3) 三

20、角不等式：., , |nRyxyxyx则称| x为向量x的范数范数或模模. 由(3)得., , |nRyxyxyx(4)几种常用向量范数 |,|max|1inixx(无穷范数) |,|nxxx11(1-范数) ,|2212nxxx(2-范数)., 1 ,1)|(|/1pnixxppip(p-范数)可以验证它们都是范数. 易见前三种范数是p-范数的特殊情况).|lim|(|ppxx2、 矩阵的范数矩阵的范数中矩阵的一种范数范数得到上的向量，则由中中矩阵为视广到矩阵上下面把向量范数概念推nnnnnnRRRR2 .22)( 11|2FrobeniusFninjijaAF范数，定义定义(矩阵的范数)

21、满足的某个非负实值函数如果 |,|)( AANRAnn(1) 正定性：,|0A等号当且仅当0A时成立；(2) 齐次性：; | , AAR(3) 三角不等式：., , |nnRBABABA则称| A为 矩阵A的范数范数或模模。., , | )(nnRBABAAB4.|上的一个矩阵范数就是nnFRA(5.5) ., |,| nnnRxRAxAAx性，即满足和向量范数的相容我们希望一种矩阵范数（矩阵范数的相容性）.般定义下面给出矩阵范数的一例例 计算矩阵4321A的几种常用范数1312101424341420T=A A 11|max| 61=j nnAaiji 1|max| 71=i nnAaijj

22、 2122max1014|30 +40142029.866-0.134|()29.8665.0465TTEA AAA A令得，故解：解：对矩阵的常用范数有：列范数 , |max|niijaAnj111行范数 , |max|njijaAni11范数的最大特征值矩阵22 ,|AAAT2max|(),T AA A常用条件数有：常用条件数有：cond 2(A)maxmin122| |()/()TTAAA AA A特别地，若特别地，若 A 对称，则对称，则max2min|( )|cond ( )|( )|AAAcond 1 (A)=A1 11Acond (A)=A 1A3、矩阵的条件数、矩阵的条件数De

23、f：设设 存在，则称数存在，则称数 cond ( A )=| | A | 为矩阵为矩阵 A 的的条件数，其中条件数，其中 是矩阵的某种范数。是矩阵的某种范数。1A1A| | 1-1-条件数条件数- -条件数条件数2-2-条件数条件数若若 A 对称正定，则对称正定，则max2min()cond ()()AAA二、二、线性方程组的性态（误差分析）线性方程组的性态（误差分析） 例：方程组例：方程组1226826.000018.00001xx有精确解有精确解(1,1),(1,1),对系数矩阵和右端常数项作微小变化对系数矩阵和右端常数项作微小变化, ,则则1226825.999998.00002xx的解

24、为的解为(10, -2). 扰动后方程组的解面目全非。扰动后方程组的解面目全非。定义定义:如果方程组如果方程组 Ax = b 中中, 矩阵矩阵A和右端项和右端项 b 的变化的变化|A|和和|b |微小微小, 引起解向量引起解向量 x 的变化的变化|x |很大很大, 则称则称A为关于解为关于解方程组和矩阵求逆的病态矩阵方程组和矩阵求逆的病态矩阵, 称相应的方程组为病态方程组称相应的方程组为病态方程组.反之反之, 如果如果|A|和和|b |微小微小, |x |也微小也微小, 则称则称 A为良态矩为良态矩阵阵, Ax=b 为良态方程组为良态方程组. 即即:求解求解 时时, A 和和 的误差对解的误差

25、对解 有何影响有何影响？Axbbx 设设 A 精确，精确， 有误差有误差 ，得到的解为，得到的解为 ，即，即bbxx1xAb1| | |xAb绝对误差放大因子绝对误差放大因子| |bAxAx又又1|Axb1| |xbAAxb相对误差放大因子相对误差放大因子()A xxbb矩阵和方程组病态程度的刻划矩阵和方程组病态程度的刻划说明说明: : 设线性方程组的系数矩阵是非奇异的设线性方程组的系数矩阵是非奇异的, 如果如果cond(A)越大越大, 就就称这个方程组越病态称这个方程组越病态. 反之反之, cond(A) 越小越小, 就称这个方程组越良态就称这个方程组越良态.1122A例例1：求矩阵：求矩阵

26、 的条件数的条件数11111112121 211/21/4211/21/44|4,|3/4.cond ( ) | 3.|3,|1.cond ( )3.12115312223553|(5)903582TTAAAAAAAAAA AEA A解：又令得，故2max|()82 2TAA A111112maxmax2()1/8,1/ 2|() ()() 1/ 22 / 2cond ( )2 22 / 22TTTA AAAAAAA的特征值:例例2: 2: 设设11710,57cond ( )17 17289cond (A)17 17289AA：解解71057A1cond ( ), cond (A)A求求设矩

27、阵设矩阵A A可逆，把矩阵可逆，把矩阵A A分裂为分裂为,0,AQCQ1111()()+=.A xbQCxbIQCxQbxQC xQbB xf迭代过程迭代过程B称为称为迭代矩阵迭代矩阵。1,(1)kkxBxf给定初值给定初值 就得到向量序列就得到向量序列0,x01,nxxx第四节第四节 线性方程组的迭代解法线性方程组的迭代解法则则*lim,nnxx定义：定义：若若 称简单迭代法收敛，称简单迭代法收敛，x x* *是方程组是方程组 x = B x + f x = B x + f 的解的解. .否则，称逐次逼近法不收敛或发散。否则，称逐次逼近法不收敛或发散。一、迭代法概念一、迭代法概念( )*(

28、)(1)( )*(1)(0)| |1 |1 |kkkkkBBxxxxxxxxBB，定理定理：若迭代法的迭代矩阵满足：若迭代法的迭代矩阵满足 （矩阵的某一种算子范（矩阵的某一种算子范数），则迭代格式数），则迭代格式 产生的序列产生的序列 收敛收敛于于x = B x + f 的精确解的精确解 x*，且有误差估计式：，且有误差估计式：1B (1)()kkxBxf( )kx 注注 : 因为矩阵范数因为矩阵范数 ， 都可以直接用矩阵的元素计都可以直接用矩阵的元素计算，因此用上述定理，容易判别迭代法的收敛性。定理的条件算，因此用上述定理，容易判别迭代法的收敛性。定理的条件只只是充分的是充分的，而，而不是必

29、要的不是必要的，也就是说：如果，也就是说：如果 ，则迭代，则迭代法收敛；但若法收敛；但若 ，我们并不能断定迭代法就一定发散，此，我们并不能断定迭代法就一定发散，此时需要用其他定理来判定迭代法的敛散性。时需要用其他定理来判定迭代法的敛散性。 1BB1B 1B 二、迭代法收敛的条件二、迭代法收敛的条件三三、Jacobi迭代法迭代法例例1：用迭代法解方程组：用迭代法解方程组12312312381210453xxxxxxxxx解解: 将方程组化为等价形式将方程组化为等价形式:12321331281102453xxxxxxxxx 0 iiaAADLU当时 ，可 将写 成其中D是对角阵，L和U分别是对角元

30、素为零的下和上三角阵11(1 )1()111()()(). ()kkJA xbD xLUxbxDLUxDbxDLUxDbBDLUIDA 上述求解方程组的迭代方法称为上述求解方程组的迭代方法称为JacobiJacobi迭代法迭代法。称为称为Jacobi迭代矩阵迭代矩阵。(1)(2)(3)(4)(5)(0.125,0.40, 0.6) ,(0.25,0.315, 0.495) ,(0.22625,0.3005, 0.487) ,(0.223438,0.30605, 0.49465) ,(0.225088,0.305847, 0.494102) ,TTTTTxxxxx注：注： 利用定理利用定理2的误

31、差估计式可以判断迭代过程是否可以终的误差估计式可以判断迭代过程是否可以终止，但这种方法比较麻烦，通常采用的方法是通过前后两次止，但这种方法比较麻烦，通常采用的方法是通过前后两次迭代近似值的差来判断，即利用：迭代近似值的差来判断，即利用：(1)( )(1)( )1max|kkkkiii nxxxx 或终止迭代过程。终止迭代过程。取初始值取初始值 代入计算，得代入计算，得(0)(0,0,0)Tx(1)( )( )123(1)( )( )213(1)( )( )3120.1250.1250.1250.20.10.40.20.20.6kkkkkkkkkxxxxxxxxx 构造迭代格式构造迭代格式:四、高斯四、高斯-赛德尔（赛德尔（Gauss-Seidel ）迭代法）迭代法1(1)()()111(),inkkkiijj