三角分解 3.3 矩阵的三角分解法

1、兰州交通大学数理与软件工程学院3.3 矩阵的三角分解法 我们知道对矩阵进行一次初等变换，就相当于用相应的初等矩阵去左乘原来的矩阵。因此我们这个观点来考察gauss消元法用矩阵乘法来表示，即可得到求解线性方程组的另一种直接法：矩阵的三角分解。兰州交通大学数理与软件工程学院 gauss消元法的矩阵形式)2()1(1)2()2(2)2()2()1()1()1()1()1()1()1()1()1()1()1()1(131211)1(11)1(1111131121)1(11.1.00.1011.,32i)()(1),.,0:122211211212222111211aalaaaaaaaaaaaaaaaa

2、lllni-laalaaaannnnnnnnnnnniiin，其矩阵形式为，行行令消零时，将步等价于第则）（）（）（兰州交通大学数理与软件工程学院)3()3()3(3)3(3)3(33)2(2)2(23)2(22)1(1)1(13)1(12)1(11222)2(22)2(222322)2(22.00.00.0.:),.,4, 3(1.00.0.100.0100.00102aaaaaaaaaaaaalaniaallllannnnnn)()(iin，即有左乘时，用矩阵步等价于：若同理第兰州交通大学数理与软件工程学院1.1111.11.000.00.0.2321212111)()3(3)3(33)2

3、(2)2(23)2(22)1(1)1(13)1(12)1(111221nnnnnnnnnnlllllluaaaaaaaaaaallll因为以此类推可得兰州交通大学数理与软件工程学院为上三角阵为单位下三角阵，其中所以u1.111.).(1213231211112121111221lluullllllullllullllannnnnnnn兰州交通大学数理与软件工程学院分解。行直接进否对矩阵因此，关键问题在于能个三角方程：就等价于解两由此解线性方程组luayuxblyulabxbx)(兰州交通大学数理与软件工程学院 doolittle分解1131313111311121212111211111232

4、322131211323121333231232221131211)3 , 2 , 1(11113,ualluaualluajauuakuuuuuulllaaaaaaaaanuljjjj得由；得由时：为例的各元素，以此分解在于如何算出兰州交通大学数理与软件工程学院)(322332133133333323321331332212313232233212313213212323231321231221222222122122ululauuululakuulalululaulauuulaulauuulak得时：由得由；得由；得时：兰州交通大学数理与软件工程学院doolittle分解 若矩阵a有分解：

5、a=lu，其中l为单位下三角阵，u为上三角阵，则称该分解为doolittle分解，可以证明，当a的各阶顺序主子式均不为零时，doolittle分解可以实现并且唯一。兰州交通大学数理与软件工程学院 a的各阶顺序主子式均不为零，即),.2 , 1(0.1111nkaaaaakkkkk兰州交通大学数理与软件工程学院doolittle分解各元素方法逐行逐列求解用比较等式两边元素的令uluuuuuulllaaaaaaaaannnnnnnnn,.1.11.222112112121n2n1n2222112111兰州交通大学数理与软件工程学院doolittle分解。得再由；得由时：。得再由；得由时),.,4

6、, 3(),.,3 , 2(12),.,3 , 2(),.2 , 1(1:12212122222121212222121211111111 i1111niuulalululanjulauuulakniualluanjauuakiiiiiijijjjjjiiijjjj兰州交通大学数理与软件工程学院doolittle分解1111211211,.1,000.10.,.,kttjktkjkjktkjtjktjjjjkkkkkjknkkkknkkjulauuuluuulllakjuuuk）（有步时：计算第兰州交通大学数理与软件工程学院doolittle分解11111111,.1/)(000.0 , 1

7、,.,.,ktkktkitikikktkkiktkitkkkikiiknkkknkiuulalululuullakill）（得，于是由由于计算兰州交通大学数理与软件工程学院doolittle分解nnnnnnkkkttkitikikkttjktkjkjulluuluuunkuulalnkinkjulau.a,.,2 , 1/)(),.,1;,.,(2122221112111111的各位各元素在计算机内存于即兰州交通大学数理与软件工程学院doolittle分解。可获解得及再由tniinijjijiiijjijiixxxnniuxuyxniylbyulxyxby),.,(1,.1,/)(,.,2 ,

8、 121111兰州交通大学数理与软件工程学院例题30191063619134652.d. 1321xxxoolittle分解求解方程组试用例兰州交通大学数理与软件工程学院例题。，；，令、分解解：326246521101001636191346521311121131211332322131211323121luluuukuuuuuulllalu兰州交通大学数理与软件工程学院例题luaululaukuulalulauulauk473652143121434/)(7)6(21935213223321331333322123132321321232312212222所以时：，时：兰州交通大学数理与软

9、件工程学院例题tyyyyyyybly)4 , 1,10(43034, 12019,1030191014312112321321即得）解（、解方程组兰州交通大学数理与软件工程学院例题。所以方程组的解为解得：解txxxxxxxyux)1 ,2,3(3,2,2(123321兰州交通大学数理与软件工程学院doolittle分解).,.,()(),.,(/)(;/)2),.,)(;)1)(),.,(/)(),.,(,.,)2),.,(/)(),.,(),.,()1(nixniuxuyxayxniylbybyyuxblynkiuulalankkjulauankniaalaluan

10、ibnjiaiiinijjijiinmnnijjijiikkkttkitikikikkttjktkjkjkjiiiiij2141212311323212212111111111111111输出：方程组的解；和解；做对；分解输入：兰州交通大学数理与软件工程学院对称矩阵的cholesky分解 在应用数学中，线性方程组大多数的系数矩阵为对称正定这一性质，因此利用对称正定矩阵的三角分解式求解对称正定方程组的一种有效方法，且分解过程无需选主元，有良好的数值稳定性。兰州交通大学数理与软件工程学院对称矩阵的cholesky分解 a对称：at=a a正定：a的各阶顺序主子式均大于零。即),.2 , 1(0.1

11、111nkaaaaakkkkk兰州交通大学数理与软件工程学院对称矩阵的cholesky分解 由doolittle分解，a有唯一分解。，也就是所以，有即tttttttttllaulullululululualu)(a兰州交通大学数理与软件工程学院对称矩阵的cholesky分解 定理3.2.4 设a为对称正定矩阵，则存在唯一分解a=ldlt，其中l为单位下三角阵，d=diag(d1,d2,dn)且di0(i=1,n)兰州交通大学数理与软件工程学院对称矩阵的cholesky分解 证明：nddduulluadoolittle21111,a令非奇异的上三角阵。为为单位下三角阵，其中分解为分解可唯一是对称

12、正定，由因为兰州交通大学数理与软件工程学院对称矩阵的cholesky分解均大于零即。得由；得；由得故有的顺序主子式均大于零是正定的，则又因为nnnndddddddddddda,.,00.;0000a21212212111兰州交通大学数理与软件工程学院对称矩阵的cholesky分解。所以为单位上三角阵。为对角阵其中故lduauddudddddddun,1.1*.*1*.*12211211兰州交通大学数理与软件工程学院对称矩阵的cholesky分解 推论：设a为对称正定矩阵，则存在唯一分解 其中l为具有主对角元素为正数的下三角矩阵。，所以故有对称，即又因为ttttttldlauladlulduaa

13、)(tlla 兰州交通大学数理与软件工程学院 证明： 0,.,0, 0)(4 . 2 . 3),.,(2121212121ntttndddlllldldldladdddiagd的主对角元素为其中则由定理令兰州交通大学数理与软件工程学院cholesky分解的求法332322131211333231222111333231232221131211212221113?.,llllllllllllaaaaaaaaanllllllllllaaijnnnnt为例。以如何求令则对称正定设兰州交通大学数理与软件工程学院cholesky分解的求法。，得由；，得时：由。；同理得，得由；，得时：由222131323

14、2223221313222122222222212211313111212111212111112111121lllalllllalalllaklallalllaallak兰州交通大学数理与软件工程学院cholesky分解的求法njnjilllallalnlallllakjjjkjkikijijjkjkjjjjii,.,2 , 1,.,1/ )()(,311211122123333323323223133有阶行列式推广到，得时：由兰州交通大学数理与软件工程学院cholesky分解法 cholesky分解法缺点及优点 优点：可以减少存储单元。 缺点：存在开方运算，可能会出现根号下负数。ttlla

15、yxlblybaxcholesky其中分解法解线性方程组用兰州交通大学数理与软件工程学院改进cholesky分解法 改进的cholesky分解a=ldltnnnnnnnntnnnnnndlddldlddldldlddlllllldlladdddlllllll.1.111)(1.11133322322211311211112132312121121323121由兰州交通大学数理与软件工程学院改进cholesky分解1121111211,.,2, 1)1,.,2, 1(/)(),.,2, 1()1,.,2, 1(jkkikiiijjkjkkikijijjkikikiijijjkjkkikijnid

16、ladijdldlalniddlaijdlldlaji由此可得有逐行相乘，并注意到兰州交通大学数理与软件工程学院改进cholesky分解)1,.,2, 1,.,3 ,2(,1111ijnilcaddcllcacdcldlcikikikiiijijijjkjkikijijjijijjijij，成所以可将上述公式改写，则可令为减少计算量兰州交通大学数理与软件工程学院tnnntdydydyyddddddllacholeskyyxbybx),.,(111221112111故即等价于求分解法解线性方程组用兰州交通大学数理与软件工程学院改进的cholesky分解算法；做对做对分解，输入1111)2(1,.

17、,2, 1)1(,.,3,2.2);,.2, 1(),.,2, 1(.1ikikikiiiiijijijijjkikikijijtiijlcadadclalcacijnildlanibni,ja兰州交通大学数理与软件工程学院改进的cholesky分解算法。输出：；解；解解),.,2, 1()3()1,.,1()2(),.,2()1 (.3111111nixnixldyxdyxydxlniylbybyblyainikkkiiiinnntikkikiibx兰州交通大学数理与软件工程学院例题分解做解：对系数矩阵算法解方程组分解试用改进的例doolitteaxxxcholeskey6353212211

18、142 .2 .3321兰州交通大学数理与软件工程学院例题tldla11125. 025. 0111.7541125. 025. 01175. 11.751141125. 025. 011125. 075. 175. 125. 01143125. 075. 175. 125. 01143225. 02225. 0114321221114兰州交通大学数理与软件工程学院例题tybyyyyyyyl)3 ,47,5(3,75.1,5635110.25125.01321321即得得由兰州交通大学数理与软件工程学院例题tttxyxyxxxxxxdld)3 , 2 , 1 (1, 2, 33125.1111

19、25.025.01)3 , 1,45(12332111所以方程的解：得得，由而兰州交通大学数理与软件工程学院 a=ldlt分解，既适合于解对称正定方程组，也适合求解a为对称，而各阶顺序主子式不为零的方程组 而对a=llt只适合于对称正定方程组兰州交通大学数理与软件工程学院 追赶法nnnnnijnnijabcabcabcaaajaa11122211, 01|i |)(即有，对一切设三对角矩阵兰州交通大学数理与软件工程学院追赶法),.,3 , 2(1111,111111221132nicpaqqbpaqqcqcqcqpppaludoolittleaiiiiiiinnnn其中则有分解满足如果兰州交通

20、大学数理与软件工程学院追赶法),.,2(1111),.,(1113213213221niypfyfyffffyyyypppfffulaiiiinnntnfyxfyfx解得，故有其中等价于求则求兰州交通大学数理与软件工程学院追赶法组的追赶法。以上称为解三对角方程解得再由)1,.,1(1121121112211niqxcyxqyxyyyyxxxxqcqcqcqiiiiinnnnnnnnnn兰州交通大学数理与软件工程学院例题32320151361420125133142012512131123)3(3)3(aaczk，兰州交通大学数理与软件工程学院例题120351461120351461021153

21、1643) 1 (3)2(13aazz所以，由与第三列交换第一列与第三列交换第二列兰州交通大学数理与软件工程学院3.5平方根法 在应用数学中，线性方程组大多数的系数矩阵为对称正定这一性质，因此利用对称正定矩阵的三角分解式求解对称正定方程组的一种有效方法，且分解过程无需选主元，有良好的数值稳定性。兰州交通大学数理与软件工程学院平方根法 a对称：at=a a正定：a的各阶顺序主子式均大于零。即),.2 , 1(0.1111nkaaaaakkkkk兰州交通大学数理与软件工程学院平方根法 由doolittle分解，a有唯一分解。，也就是所以，有即tttttttttllaulullululululual

22、u)(a兰州交通大学数理与软件工程学院平方根法 定理3.2.4 设a为对称正定矩阵，则存在唯一分解a=ldlt，其中l为单位下三角阵，d=diag(d1,d2,dn)且di0(i=1,n)兰州交通大学数理与软件工程学院平方根法 证明：nddduulluadoolittle21111,a令非奇异的上三角阵。为为单位下三角阵，其中分解为分解可唯一是对称正定，由因为兰州交通大学数理与软件工程学院平方根法均大于零即。得由；得；由得故有的顺序主子式均大于零是正定的，则又因为nnnndddddddddddda,.,00.;0000a21212212111兰州交通大学数理与软件工程学院平方根法。所以为单位上

23、三角阵。为对角阵其中故lduauddudddddddun,1.1*.*1*.*12211211兰州交通大学数理与软件工程学院平方根法 推论：设a为对称正定矩阵，则存在唯一分解 其中l为具有主对角元素为正数的下三角矩阵。，所以故有对称，即又因为ttttttldlauladlulduaa)(tlla 兰州交通大学数理与软件工程学院 证明0,.,0, 0)(4 . 2 . 3),.,(2121212121ntttndddlllldldldladdddiagd的主对角元素为其中则由定理令兰州交通大学数理与软件工程学院平方根法332322131211333231222111333231232221131

24、211212221113?.,llllllllllllaaaaaaaaanllllllllllaaijnnnnt为例。以如何求令则对称正定设兰州交通大学数理与软件工程学院平方根法。，得由；，得时：由。；同理得，得由；，得时：由2221313232223221313222122222222212211313111212111212111112111121lllalllllalalllaklallalllaallak兰州交通大学数理与软件工程学院平方根法njnjilllallalnlallllakjjjkjkikijijjkjkjjjjii,.,2 , 1,.,1/ )()(,3112111221

25、23333323323223133有阶行列式推广到，得时：由兰州交通大学数理与软件工程学院平方根法 cholesky分解法缺点及优点 优点：可以减少存储单元。 缺点：存在开方运算，可能会出现根号下负数。ttllayxlblybaxcholesky其中分解法解线性方程组用兰州交通大学数理与软件工程学院改进平方根法 改进的平方根法分解a=ldltnnnnnnnntnnnnnndlddldlddldldlddlllllldlladdddlllllll.1.111)(1.11133322322211311211112132312121121323121由兰州交通大学数理与软件工程学院改进平方根法112

26、1111211,.,2, 1)1,.,2, 1(/)(),.,2, 1()1,.,2, 1(jkkikiiijjkjkkikijijjkikikiijijjkjkkikijnidladijdldlalniddlaijdlldlaji由此可得有逐行相乘，并注意到兰州交通大学数理与软件工程学院改进平方根法)1,.,2, 1,.,3 ,2(,1111ijnilcaddcllcacdcldlcikikikiiijijijjkjkikijijjijijjijij，成所以可将上述公式改写，则可令为减少计算量兰州交通大学数理与软件工程学院tnnntdydydyyddddddllacholeskyyxbybx

27、),.,(111221112111故即等价于求分解法解线性方程组用兰州交通大学数理与软件工程学院改进的平方根法；做对做对分解，输入1111)2(1,.,2, 1)1(,.,3,2.2);,.2, 1(),.,2, 1(.1ikikikiiiiijijijijjkikikijijtiijlcadadclalcacijnildlanibni,ja兰州交通大学数理与软件工程学院改进平方根法。输出：；解；解解),.,2, 1()3()1,.,1()2(),.,2()1 (.3111111nixnixldyxdyxydxlniylbybyblyainikkkiiiinnntikkikiibx兰州交通大学

28、数理与软件工程学院例题分解做解：对系数矩阵算法解方程组分解试用改进的例doolitteaxxxcholeskey6353212211142 .2 .3321兰州交通大学数理与软件工程学院例题tldla11125. 025. 0111.7541125. 025. 01175. 11.751141125. 025. 011125. 075. 175. 125. 01143125. 075. 175. 125. 01143225. 02225. 0114321221114兰州交通大学数理与软件工程学院例题tybyyyyyyyl)3 ,47,5(3,75.1,5635110.25125.0132132

29、1即得得由兰州交通大学数理与软件工程学院例题tttxyxyxxxxxxdld)3 , 2 , 1 (1, 2, 33125.111125.025.01)3 , 1,45(12332111所以方程的解：得得，由而兰州交通大学数理与软件工程学院 a=ldlt分解，既适合于解对称正定方程组，也适合求解a为对称，而各阶顺序主子式不为零的方程组 而对a=llt只适合于对称正定方程组兰州交通大学数理与软件工程学院2.6范数与误差估计 用直接方法解n阶线性方程组ax=b，由于原始数据a、b的误差及计算过程中的舍入误差，一般得不到方程的精确解 ，往往得到 它的近似解x，为了讨论解的精度，即误差向量x- ，的大

30、小，也为了讨论用迭代法解线性方程组的收敛性问题，需要引入向量及矩阵的范数。 xx兰州交通大学数理与软件工程学院向量的范数 定义3.1 设是n维向量空间，如果 ，实值函数x满足条件 (1) 正定性：x0，当且仅当x=0时，x； (2) 齐次性：r,x=|x； (3) 三角不等式：x+yx+y， 则称x为 上的向量范数(或向量的模)。 nrnryx ,nr兰州交通大学数理与软件工程学院 在数值计算中，常用的向量范数有三种。设 ，规定 ntnrxxxx),(21ininiiniixxxxxx12/112211max)3()(2)2( 1 ) 1 (范数向量的范数向量的范数向量的兰州交通大学数理与软件

31、工程学院 性质兰州交通大学数理与软件工程学院兰州交通大学数理与软件工程学院 证明：据式(3.25)，只要证明对“”范数结论成立即可。又据定义3.2知：0lim0maxlim), 2 , 1(0limlim)()(1)()(xxxxnixxxxkkikinikikikkk兰州交通大学数理与软件工程学院矩阵的范数兰州交通大学数理与软件工程学院 设 常用的矩阵范数：(1)矩阵的列范数： (2)矩阵的行范数：(3)矩阵的欧氏范数：(4)矩阵的谱范数： nnnniiraa)(niijnjaa111maxnjijniaa11max ninjijeaa1212)(maxmax2,a兰州交通大学数理与软件工程

32、学院 例3.6 已知 ，求a的常用范数。 解： 1312a52 , 5max1amax3,44a2551313121132aat01152aaet)22115(218643. 3)22115(21max2a兰州交通大学数理与软件工程学院兰州交通大学数理与软件工程学院定的。是可以控制的，或是稳时，函数值的误差这表明当时有当若记1, 1)()()()(1, 1|,)()(|,)(|*rrrrrccxefexefeccxfxfxcxfc兰州交通大学数理与软件工程学院为病态。称当为良态；称当。和相对意义下的条件数在绝对意义下为一般分别称)(1)(1)(,xfcxfcxfccr兰州交通大学数理与软件工程

33、学院例题在正根附近是病态的即正根为解得由解在正根附近的性态。讨论函数例)(1201|12| )100(|100100,1010)(10100)(2 .2 .110021*xfxfxxxxfxxxfx兰州交通大学数理与软件工程学院。变化，函数值变化极大也就是自变量发生微小则取则如：取09.20)9 .99()(, 9 .99200)99()(,99*1*1*1*1fxfxfxfx兰州交通大学数理与软件工程学院多元函数误差估计)()()()(),.,(),.,()(),.,(),.,(),.,(*1*1*1*21*2*121*2*1*21iniiniiiniiiinntntnnxexffexexfxxxfxxxfxxxffexxxxxxxxxxxfy因此绝对误差界为其绝对误差为代替用对于多元函数兰州交通大学数理与软件工程学院3.7迭代法 解线性方程组的直接法，如gauss消去法、矩阵的三角分解等，适用于阶数不高的线性方程组。而在实际应用中，常会遇到一类阶数很高，非零元素很少的所谓高阶稀疏方程组(零元素成片分布，数量上绝对占优)。对这类方程组用迭代法求解，可以充分利用稀疏矩阵的特性减少计算工作量，节省存贮量。兰州交通大学数理与软件工程学院迭代法所要解决的几个主要问题是： (1) 构造一种迭代格式，把所给方程组ax=b化成同解的方程组x=bx+d