《线性代数》课件D2-1线性方程组的直接解法（2）.ppt

1、第二章第二章1 线性方程组的直接解法线性方程组的直接解法四、矩阵的三角分解四、矩阵的三角分解五、平方根法及改进的平方根法五、平方根法及改进的平方根法六六、追赶法追赶法七七、列主元三角分解法列主元三角分解法2023-4-24第二章 第一节 线性方程组的直接解法2矩矩阵阵的的初初等等变变换换与与初初等等复复习习 矩矩阵阵的的联联系系(),(1,2,3).ijm nAaAtmtA t 设设矩矩阵阵则则对对 做做一一次次第第 种种初初等等行行变变换换,相相当当于于用用一一个个阶阶的的第第 种种初初等等矩矩阵阵左左乘乘(2)-2(1)(3)-3(1)132132:211055325071A 如如=110

2、0132132-210211055-301325071L A =2023-4-24第二章 第一节 线性方程组的直接解法37(3)-(2)5132132055055071006B 210013213201005505507/51071006L B 112112132055,006L L AU AL L ULU 2023-4-24第二章 第一节 线性方程组的直接解法4111112100100-210010-30107/51LL L 10010010021001021030107/5137/51 10013221005537/51006ALU 2023-4-24第二章 第一节 线性方程组的直接解法5

3、(1)(1)(1)11121(1)(1)(1)(1)21222(1)(1)(1)12,nnnnnnn naaaaaaAAaaa )1()1(1)1(.nbbbb 复习：复习：高斯消元法的矩阵形式高斯消元法的矩阵形式四、矩阵的三角分解四、矩阵的三角分解2023-4-24第二章 第一节 线性方程组的直接解法6Step n 1:)()2(2)1(1)()2(2)2(22)1(1)1(12)1(11121.nnnnnnnnnbbbaaaaaabALLL其中其中 Lk=Step 1:)0(/111111 aaamii记记 L1=1.11121nmm ，则，则)1()1(1bAL)1(1)1(1)1(11

4、.baan)2(A)2(b1.11,1knkkmm Step 1:Step n 1:2023-4-24第二章 第一节 线性方程组的直接解法7 1kL1.11,1knkkmm 111211.nLLL111jim,记为记为L记记 U=)()2(2)2(22)1(1)1(12)1(11.nnnnnaaaaaaLUA 2023-4-24第二章 第一节 线性方程组的直接解法8 Doolittle分解法分解法 LU 分解的紧凑格式分解的紧凑格式反复计算反复计算,很浪费哦很浪费哦 通过比较法直接导出通过比较法直接导出L 和和 U 的计算公式。的计算公式。思思路路 nnnnnnnnuuullaaaa.1.11

5、.11112111112023-4-24第二章 第一节 线性方程组的直接解法9 nnnnnnnnuuullaaaa.1.11.1111211111 ),min(1jikjkkiul jia计算步骤计算步骤：11,1,2,;jiuajn1j第一步，令 得 11111,2,3,.iiajlinu再令 得 2023-4-24第二章 第一节 线性方程组的直接解法10 nnnnnnnnuuullaaaa.1.11.1111211111 ),min(1jikjkkiul jia2222,=1,ijl第二步，令，对注意到 得21122222,2,3,.iiial ujilinu再令 对得 2211,2,;j

6、jual ujn2j2023-4-24第二章 第一节 线性方程组的直接解法1111rrjrkkjrjkal uu考虑考虑A的第的第r 行主对角元右边的元素行主对角元右边的元素:对对 j=r,r+1,n 有有lrr=1 nnnnnnnnuuullaaaa.1.11.1111211111假设完成假设完成r-1步步.此时此时U的第的第r-1 行已知，行已知，L的前的前r-1列已知列已知.),min(1jikjkkiuli ja11,1,rrjrjrkkjkual ujr rn2023-4-24第二章 第一节 线性方程组的直接解法12考虑考虑A的第的第r列主对角元以下的元素列主对角元以下的元素:对对

7、i=r+1,n 有有111.rririkkrikkrirrrkkal ul ul u11()/riririkkrrrklal uurrn，=+1,+2,i.nnnnnnnnuuullaaaa.1.11.1111211111 ),min(1jikjkkiuli ja2023-4-24第二章 第一节 线性方程组的直接解法13111212122212nnnnnnLUuuuluullu 分分解解的的紧紧凑凑格格式式第一步计算第一步计算第二步计算第二步计算第第n步计算步计算如此下去直到第如此下去直到第n步。步。把把L,U放在同一个矩阵放在同一个矩阵A内，计算过程图示如下：内，计算过程图示如下：见见教教材

8、材(2.1.11)-(2.1.12).(2.1.11)-(2.1.12).2023-4-24第二章 第一节 线性方程组的直接解法1413221132-5A例例4 对矩阵对矩阵 作作LU三角分解。三角分解。132100132211210055.32-537/51006ALU解解Crout分解分解-U单位上三角矩阵；单位上三角矩阵；L下三角矩阵下三角矩阵111211112121222212221212111nnnnnnnnnnnnaaaluuaaalluaaalllL计算步骤：先计算 的列，再计算U的行。11,;1,2,riririkkrklal uirn rn11,1,;1,2,1.rrirkk

9、ikrirral uuirn rnl上述算法能有效使用的必要条件是上述算法能有效使用的必要条件是lrr不能太小。不能太小。2023-4-24第二章 第一节 线性方程组的直接解法16111212122212 (),(1,.2,)ijkkkkkkkAanaaaaaaaaaAAknk 阶阶顺顺序序主主子子式式回回顾顾（线线性性设设为为阶阶矩矩阵阵,代代）为为的的记记数数作作2023-4-24第二章 第一节 线性方程组的直接解法17111212122212 (),(1,2,).ijkkkkkkkAanaaaaaaaaaAAkn 设设为为阶阶矩矩阵阵,为为的的记记作作主主回回顾顾（线线性性代代）子子矩矩

10、阵阵数数2023-4-24第二章 第一节 线性方程组的直接解法18()(1)()1111,|,2,3,.|kkkkkkkkAAaAaAaknA 以以上上对对矩矩阵阵 进进行行三三角角分分解解 均均要要求求 的的各各阶阶顺顺序序主主子子式式都都不不为为零零，这这个个条条件件就就是是高高斯斯消消去去法法过过程程中中的的各各个个主主元元不不为为零零的的充充要要条条件件.事事实实上上有有 2023-4-24第二章 第一节 线性方程组的直接解法19,.2TAnAAALDLLD 设设 为为 阶阶对对称称矩矩阵阵，且且 的的各各阶阶顺顺序序主主子子式式都都不不为为零零，则则 可可唯唯一一分分解解为为 其其中

11、中 为为单单位位下下三三角角阵阵，定定为为对对角角阵阵理理 211)-nnAAn 阶阶(矩矩阵阵 有有唯唯一一杜杜里里特特尔尔分分解解（或或克克劳劳定定理理特特分分解解）的的充充要要条条件件是是 的的前前个个顺顺序序主主子子式式都都不不为为零零.证证明明：见见教教材材2 29 9-3 30 0页页或或下下面面第第5 5段段.2023-4-24第二章 第一节 线性方程组的直接解法20解单位解单位下三角下三角方程组方程组 Ly=b1111,2,3,.iiiijjjybybl yin1,1,2,2,1.nnnnniijjjiiiiyxuyu xxinnu 解上三角解上三角方程组方程组Ux=yDool

12、ittleDoolittle分解的应用分解的应用-解线性方程组解线性方程组2023-4-24第二章 第一节 线性方程组的直接解法21.11345-23112231321xxx例例4（续）（续）用用LU三角分解法求解方程组三角分解法求解方程组2023-4-24第二章 第一节 线性方程组的直接解法22132100132211210055.32-537/51006ALU解解 已知已知想了解更多想了解更多,可输入右边的帮助命令可输入右边的帮助命令!X=A B 左除左除;表示表示 AX=B 的解的解,X=A-1B=ABX=B/A 右除右除.表示表示 XA=B 的解的解,X=BA-1=B/Ahelp 例例

13、 用上面介绍的命令求解一个方程组用上面介绍的命令求解一个方程组A=-0.04 0.04 0.12;0.56-1.56 0.32;-0.24 1.24-0.28 b=3;1;0 x1=Ab%方程组的数值解方程组的数值解x2=sym(A)sym(b)%方程组的符号解方程组的符号解sym(A),sym(b)%观察观察sym(A),sym(b)形式形式在在Matlab中实现上面的内容中实现上面的内容,并观察结果并观察结果!23在求解方程组在求解方程组 Ax=b 时时,尽量不要用尽量不要用 inv(A)*b 命令命令,而应采用而应采用 Ab 的解法的解法.注意注意:因为后者的计算速度比前者快、精度高，尤

14、其当因为后者的计算速度比前者快、精度高，尤其当矩阵矩阵 A 的阶数比较大时的阶数比较大时.而且后者可以用于求解矩阵方程，即而且后者可以用于求解矩阵方程，即x,b可以是矩阵可以是矩阵.25lu lu 分解分解.L,U=lu(X)L,U,P=lu(X)help lu请同学们自己学习这个命令请同学们自己学习这个命令,了解上面了解上面两种调用格式两种调用格式的区别的区别!例例X=1 2-1;3-1 2;-2 1 4%输入矩阵输入矩阵 XL1,U1=lu(X)%进行进行 lu 分解分解L1*U1%验证验证 X=L1*U1 成立成立L2,U2,P=lu(X)%进行进行 lu 分解分解P*X,L2*U2%验

15、证验证 P*X=L2*U2 成立成立inv(P)*L2,L1%验证验证 P-1*L2=L1 成立成立2023-4-2426A=-0.04 0.04 0.12;0.56-1.56 0.32;-0.24 1.24-0.28 b=3;1;0;L,U,P=lu(A)%进行进行 lu 分解分解y=L P*b;x=U y%解方程组解方程组 Ly=Pb,Ux=y2023-4-24).4(TAnCholesLLyALk 设设 为为 阶阶对对称称正正定定矩矩阵阵，则则存存在在唯唯一一的的主主对对角角线线元元素素都都是是正正数数的的下下三三角角阵阵,使使得得 定定理理分分解解五、平方根法及五、平方根法及*改进的平

16、方根法改进的平方根法1.正定矩阵及其性质（见教材正定矩阵及其性质（见教材30页）页）2.对称正定矩阵的三角分解对称正定矩阵的三角分解2023-4-24第二章 第一节 线性方程组的直接解法27本段内容本段内容 平方根法平方根法 对称对称 正定正定 矩阵的分解法矩阵的分解法定义定义一个矩阵一个矩阵 A=(aij)n n 称为称为对称阵对称阵，如果，如果 aij=aji。定义定义一个矩阵一个矩阵 A 称为称为正定阵正定阵，如果，如果 对任意非对任意非零向量零向量 都成立。都成立。0 xAxTx回顾：回顾：对称正定阵的几个重要性质对称正定阵的几个重要性质 A 1 亦对称正定，且亦对称正定，且 aii

17、0若不然，则若不然，则0 xA存在非零解，即存在非零解，即0 xAxT存在非零解。存在非零解。其中其中0 xAxaTiiTx)0.1.0(第第 i 位位 A 的顺序主子阵的顺序主子阵 Ak 亦对称正定亦对称正定对称性显然。对任意对称性显然。对任意 有有 ,其中其中 。kkRx 00 xAxxAxTkkTknkRxx 00 A 的特征值的特征值 i 0 设对应特征值设对应特征值 的非零特征向量的非零特征向量为为 ，则，则 。20 xxxxAxTT x A 的全部顺序主子式的全部顺序主子式 det(Ak)0因为因为 niiA1)det(1111)()(,AAIAAIAATTT对任意对任意 ,存在存

18、在 ,使得使得 ,即即 。0 x0yxyAxAy1 011 yAyyAAAyxAxTTT2023-4-24第二章 第一节 线性方程组的直接解法28复习复习(1,2,1)iA in 如果矩阵如果矩阵A的的 i 阶顺序主子阵阶顺序主子阵 均为非奇异的，则存在唯一的单位下三角均为非奇异的，则存在唯一的单位下三角矩阵矩阵L和上三和上三角矩阵角矩阵U使得使得 A=LU。定理定理12023-4-24第二章 第一节 线性方程组的直接解法29将将对称对称 正定阵正定阵 A 做做 LU 分解分解U=uij=u11uij/uii111u22unn记为记为UD A 对称对称TUL 即即 (定理定理2)TLDLA n

19、nRL 定理定理4 设矩阵设矩阵A对称正定，则存在非奇异下三角阵对称正定，则存在非奇异下三角阵 使使得得 。若限定。若限定 L 对角元为正，则分解唯一。对角元为正，则分解唯一。TLLA 记记 D1/2=11u22unnu2/1LDL 则则 仍是下三角阵仍是下三角阵TLLA 2023-4-24第二章 第一节 线性方程组的直接解法30下面证明uii0.因LT非奇异，故存在一非零向量X,使得 LTX=ei=(0,0,1,0,0)T,由A的正定性得0()()TTTTTTTiiiiX AXX LDL XL XD L Xe Deu直接分解直接分解(Cholesky分解分解)1112111112112122

20、121222221212nnnnnnnnnnnnnnaaallllaaallllaaallll1121122322,nnnnlllllll求解顺序：按L的列求2023-4-24第二章 第一节 线性方程组的直接解法31直接分解的计算公式：直接分解的计算公式：11221111,2,1,.jjjjjjkkjijikjkkijjjjnlalal llijnl对于有11,1,.jijikjkijjjkal ll lij jni=j2023-4-24第二章 第一节 线性方程组的直接解法32应用应用Cholesky分解解线性方程组分解解线性方程组111111,1,2,3,.iiikkkiiibylLybbl

21、 yyinl（）解1,2,1,1.nnnnTnikikkiiiiyxlL xyyl xxinl（）解2023-4-24第二章 第一节 线性方程组的直接解法33 对于对称正定阵对于对称正定阵 A，从，从 可知对任意可知对任意k i 有有 。即即 L 的元素不会增大，误差可控，不需的元素不会增大，误差可控，不需选主元。选主元。ikikiila12iiikal|平方根法的数值稳定性平方根法的数值稳定性.320641482121321xxx例例5 用平方根法求解方程组用平方根法求解方程组2023-4-24第二章 第一节 线性方程组的直接解法3435help cholR=chol(X)X是对称正定矩阵是

22、对称正定矩阵,R是上三角矩阵是上三角矩阵,使使 R*R=X.如果矩阵如果矩阵X是非正定的是非正定的,则会给出错误信息则会给出错误信息.请同学们自己学习这个命令请同学们自己学习这个命令!chol cholesky分解分解,对称正定矩阵的分解对称正定矩阵的分解.例例X=2 2-2;2 5-4;-2-4 5%输入对称正定矩阵输入对称正定矩阵XR=chol(X)%进行进行cholesky分解分解R*R%验证验证R*R=X成立成立2023-4-2436A=3 2 3;2 2 0;3 0 12b=5;3;7R=chol(A);L=R y=Lb;x=L y2023-4-24 三对角方程组三对角方程组Ax=f

23、 nnnnnnnfffxxxbacbacbacb212111122211110,0,2,3,1,0,iiiiinnbcAbacacinba满足A称 为对角占优的三对角矩阵。六、追赶法追赶法2023-4-24第二章 第一节 线性方程组的直接解法37 追赶法解追赶法解三对角三对角方程组方程组 nnnnnnnfffxxxbacbacbacb212111122211Step 1:对对 A 作作Doolittle分解分解112111nnnA 直接比较等式两边的直接比较等式两边的元素，可得到计算公元素，可得到计算公式。式。Step 2:追追即解即解 ：fyL 11,yf1(2,.,)iiiiyfr yin

24、Step 3:赶赶即解即解 ：yxU 1,(1,.,1)niiininiyyxxxin2023-4-24第二章 第一节 线性方程组的直接解法38如果如果 A 是是严格严格对角占优阵，则不要求三对角线上的所有元素对角占优阵，则不要求三对角线上的所有元素非零。非零。根据不等式根据不等式 可知：分解过程中，矩阵元素不会过分增大，算法保证稳定。可知：分解过程中，矩阵元素不会过分增大，算法保证稳定。运算量为运算量为 O(6n)。|,1|1iiiiiiiiabbab Hey,what does diagonally dominant mean?It means that the diagonal entr

25、ies of the matrix are very LARGE.Well,how large is LARGE?They satisfy the following inequality:ijijiiaa|定理定理 若若 A 为为对角占优对角占优 的三对角阵，且满足的三对角阵，且满足则追赶法可解以则追赶法可解以 A 为系数矩阵的方程组。为系数矩阵的方程组。0,0,0|,0|11 iinncaabcb2023-4-24第二章 第一节 线性方程组的直接解法39例例6 用追赶法求解下列线性方程组：用追赶法求解下列线性方程组：121232343423,233,37410,252.xxxxxxxxxx

26、 2110 x112223334421123 ,4.37425bcabcAnabcab解2023-4-24第二章 第一节 线性方程组的直接解法4011/21,2121L213/231413U11122233341111LU 2023-4-24第二章 第一节 线性方程组的直接解法4133,102LYb39/2,10Y,UXY21.10X推广：推广：考虑如下结构的矩阵的矩阵分解考虑如下结构的矩阵的矩阵分解111222111(|)(1,2,)iiinnnnnnbbbAinbb12211121nnnnLsss112211111nnuuUu2023-4-24第二章 第一节 线性方程组的直接解法425()

27、,.(,APPAPALULUPA 若若 为为非非奇奇异异矩矩阵阵，则则存存在在排排列列矩矩阵阵,使使得得有有唯唯一一的的杜杜里里特特尔尔(D Do oo ol li it tt ti ie e)分分解解 其其中中是是单单位位下下三三角角阵阵,其其元元素素的的绝绝对对值值不不大大于于1 1,是是上上定定理理列列主主三三角角阵阵在在同同样样条条件件下下 也也可可推推出出有有唯唯一一的的克克元元的的三三角角分分解解劳劳特特分分解解)七、列主元三角分解法列主元三角分解法2023-4-24第二章 第一节 线性方程组的直接解法43111212122212nnnnnnLUuuuluullu 分分解解的的紧紧

28、凑凑格格式式第一步计算第一步计算第二步计算第二步计算第第n步计算步计算（每一步先选定主元（每一步先选定主元urr）把把L,U放在同一个矩阵放在同一个矩阵A内，计算过程图示如下：内，计算过程图示如下：2023-4-24第二章 第一节 线性方程组的直接解法44111111111121221,11,1,11,1,112,11,11,11,21,11,1,11,1,112,11,rrrnnrrrrrrrnrnrrr rrrrrrnr nrrrrrrrrrnrnnnn rrA buuuuuuluuuuuulllaaaalllaaaallla假设已经完成步分解，即,1,1n rn rnnn naaa202

29、3-4-24第二章 第一节 线性方程组的直接解法451,2,1r rn第步分解：11(1),:,iriirikkrkSA i rA i rSaluirn计算中间量并存在(2),:max.ririir i nSiSS 选取绝对值最大的即确定行号满足(3),.rrriruA r r如果换行。换行后有2023-4-24第二章 第一节 线性方程组的直接解法461,2,1r rn第步分解（续）：11(4),1,1irirrrrririrkkikaA i rlirnuA r iualuirn计算分解 11(5),1.nnrnrnkkrkA n rualurn n2023-4-24第二章 第一节 线性方程组的直接解法47作业作业习题二习题二1.(1)(LU分解法分解法),3.(2),5.(2).2023-4-24第二章 第一节 线性方程组的直接解法48