第5章 线性方程组的直接方法

1、2022-6-231第五章第五章 解线性方程组的直接法解线性方程组的直接法1. Gauss 消元法消元法2.2. 主元素法主元素法3.3. 矩阵矩阵三角分解法三角分解法4. 三对角矩阵分解及追赶法三对角矩阵分解及追赶法5. Cholesky 分分解法解法6.6. 条件数与扰动分析条件数与扰动分析2022-6-2325.1 引言引言 在工程技术、自然科学和社会科学中，经常在工程技术、自然科学和社会科学中，经常遇到的许多问题最终都可归结为解线性方程组，遇到的许多问题最终都可归结为解线性方程组，如电学中如电学中网络问题网络问题、用最小二乘法求实验数据的、用最小二乘法求实验数据的曲线曲线拟合问题，拟合

2、问题，工程中的三次工程中的三次样条插值问题样条插值问题，经，经济运行中的济运行中的投入产出问题投入产出问题以及大地测量、机械与以及大地测量、机械与建筑结构的建筑结构的设计计算设计计算问题等等，都归结为求解线问题等等，都归结为求解线性方程组或非线性方程组的数学问题。因此线性性方程组或非线性方程组的数学问题。因此线性方程组的求解对于实际问题极其重要。方程组的求解对于实际问题极其重要。 2022-6-233 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa.22112222212111212111 nnnnnnnnbbbbxxxXaaaaaaaaaA2121212222111211,简

3、记为简记为 Ax=b，其中，其中 ( 6.1 ) 常见常见的线性方程组是方程个数和未知量个数相同的线性方程组是方程个数和未知量个数相同的的n阶线性方程组，一般形式为阶线性方程组，一般形式为 2022-6-234线性方程组的数值解法一般有两类：线性方程组的数值解法一般有两类：1. 直接法：就是经过有限步算术运算（直接法：就是经过有限步算术运算（若计算过程若计算过程中不考虑舍入误差中不考虑舍入误差），），可求得方程组精确解的方可求得方程组精确解的方法法，如克莱姆法则就是一种直接法，直接法中具，如克莱姆法则就是一种直接法，直接法中具有代表性的算法有代表性的算法是高斯是高斯 (Gauss)消元法消元法

4、。2.2. 迭代法迭代法: : 就是用某种极限过程去逐步逼近线性方就是用某种极限过程去逐步逼近线性方程组的精确解的方法。也就是程组的精确解的方法。也就是从解的某个近似值从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方出发，通过构造一个无穷序列去逼近精确解的方法。法。( (一般有限步内得不到一般有限步内得不到精确解精确解) )2022-6-235 5.2 高斯消去法高斯消去法 5.2.1 高斯消去法的基本思想高斯消去法的基本思想先用一个简单实例来说明先用一个简单实例来说明Gauss法的基本思想法的基本思想12312312231425427xxxxxxxx例例5.1 5.1 解线性方程组

5、解线性方程组2022-6-2361232323231425 23 213 2xxxxxxx12312312231425427xxxxxxxx（1）消元过程）消元过程12,2 第第2步：将方程步：将方程 乘上乘上 加到方程加到方程 上去，这样就上去，这样就消去了第消去了第3个方程的个方程的 项，于是就得到等价方程组项，于是就得到等价方程组 852x2022-6-237 4218724132332321xxxxxx 这样这样，消元过程就是把原方程组化为上三角，消元过程就是把原方程组化为上三角形方程组，其系数矩阵是上三角矩阵。形方程组，其系数矩阵是上三角矩阵。 2022-6-238（2）回代过程）回

6、代过程回代过程是将上述三角形方程组自下而上求解，回代过程是将上述三角形方程组自下而上求解，从而求得原方程组的解：从而求得原方程组的解： 9,1,6123 xxx 4218724132332321xxxxxx 2022-6-239前述的消元过程相当于对原方程组前述的消元过程相当于对原方程组 741021524312321xxx的增广矩阵进行下的增广矩阵进行下列初等行变换列初等行变换 21323250214013121213)2()21(rrrr 42187002140131223)85(rr得得到与原方到与原方程组程组等等价的方程组价的方程组 702145241312bAA2022-6-2310

7、 由此看出由此看出, ,高斯消去法的基本思想是消去方程高斯消去法的基本思想是消去方程组系数矩阵组系数矩阵A的主对角线下的元素的主对角线下的元素, ,将将Ax=b化为等价化为等价的上三角形方程组的上三角形方程组, ,然后再通过回代过程便可获得方然后再通过回代过程便可获得方程组的解程组的解。 11,xxxnn 通常通常把按照先消元把按照先消元, ,后回代两个步骤求解线性后回代两个步骤求解线性方程组的方法称为方程组的方法称为高斯高斯（Gauss）消去法。消去法。换一种说法就是用初等行变换化方程组系数矩阵为换一种说法就是用初等行变换化方程组系数矩阵为上三角形矩阵上三角形矩阵, ,而以上三角形矩阵为系数

8、的方程组而以上三角形矩阵为系数的方程组的求解比较简单的求解比较简单, ,可以从最后一个方程开始可以从最后一个方程开始, ,依次向依次向前代入求出未知变量前代入求出未知变量 。2022-6-23115.2.2 高斯消元法高斯消元法算法构造算法构造 nnnnnnnnbbbxxxaaaaaaaaa2121212222111211( 6.3 ) 记记),2, 1,(,)1()1(njibbaaiiijij 则高斯消去法的算法构造归纳为：则高斯消去法的算法构造归纳为： 我们我们知道知道, ,线性方程组线性方程组( (6.1)用矩阵形式表示为用矩阵形式表示为 2022-6-2312 消元过程消元过程, ,

9、高斯消去法的消元过程由高斯消去法的消元过程由n-1步组成：步组成： 第第1 1步步 设设 , ,把把(6.3)(6.3)中的第一列中元素中的第一列中元素 消为零消为零, ,令令 0) 1 (11a)1(1)1(31)1(21,naaa), 3 , 2(,)1(11)1(11niaamii用用 乘以第乘以第1 1个方程后加到第个方程后加到第 个方程上去个方程上去, ,消去消去第第2 2n n个方程的未知数个方程的未知数 , ,得到得到 即即 1 imi1x)2()2(bxA)2()2(2)1(121)2()2(2)2(2)2(22)1(1)1(12)1(11nnnnnnnbbbxxxaaaaaa

10、anjibmbbamaaiiijiijij,3,2,)1(11)1()2()1(11)1()2(其中其中 2022-6-2313第第k步步 （k=2,3,n-1）继续上述消元过程，设）继续上述消元过程，设第第k-1次消元已经完成，得到与原方程组等价的次消元已经完成，得到与原方程组等价的方程组方程组 (1)(1)(1)(1)1111211(2)(2)(2)22222( )( )( )( )( )( )nnkkkkkkknkkkknnknnnxaaabxaabxaabxaab nkjibmbbamaakkikkikikkjikkijkij,1,)()()1()()()1(), 1()()(nkia

11、amkkkkikik记为记为 其中其中)()(kkbxA2022-6-2314只要只要 , ,消元过程就可以进行下去消元过程就可以进行下去, ,直到经过直到经过n-1n-1次消元之后，消元过程结束，得到与原方程组等价次消元之后，消元过程结束，得到与原方程组等价的上三角形方程组的上三角形方程组, ,记为记为 0)(kkka)()(nnbxA或者写成或者写成 (1)(1)(1)(1)1111211(2)(2)(2)22222( )( )nnnnnnnnxaaabxaabxab 2022-6-2315)()()2(2)2(22)2(22)1(1)1(12)1(121)1(11nnnnnnnnnnbx

12、abxaxabxaxaxa即即 ( (6.7) （2）回代过程）回代过程就是对上三角方程组（就是对上三角方程组（6.7）自下而上逐步回代解方）自下而上逐步回代解方程组计算，即程组计算，即 )1 ,2,1(,)(1)()()()( niaxabxabxiiijnijiijiiinnnnnn2022-6-2316（3 3）高斯消去法的计算步骤：）高斯消去法的计算步骤： 消元过程消元过程; ;设设 计算计算 1,2, 1,0)( nkakkk对nkkjibmbbamaaaamkkikkikikkjikkijkijkkkkikik,2,1,)()()1()()()1()()( 回代过程回代过程 1,2

13、,1)(1)()()()( nniaxabxabxiiijnijiijiiinnnnnn2022-6-2317(4) (4) 高斯消去法流程图高斯消去法流程图 ， (5)(5) GaussGauss消去法计算量消去法计算量 313n 消元计算消元计算: aij(k+1)= aij(k)- mik akj(k) (i,j=k+1,k+2, , n) 第一第一 步计算乘数步计算乘数mik, mik=ai1/a11 (i=2,3,n) 需要需要n-1次除法运算次除法运算, 计算计算 aij(2）(i,j=2,3,n) 需要需要(n-1)2次乘法运算及次乘法运算及(n-1)2次次加减法运算加减法运算,

14、2022-6-2318第第k 步步加减法次数加减法次数乘法次数乘法次数除法次数除法次数123n-1(n-1)2(n-2)2(n-3)21(n-1)2(n-2)2(n-3)21(n-1)(n-2)(n-3)1合计合计n(n-1)(2n-1)/6n(n-1)(2n-1)/6n(n-1)/2乘除法次数：乘除法次数：MD= n(n-1)(2n-1)/6+ n(n-1)/2=1/3 n(n2-1)加减法次数：加减法次数：AS= n(n-1)(2n-1)/62022-6-2319算法算法. ( )( )0,1,2,.kkkkaknAA若，覆盖，消去：对于nk, 2 , 1 . 1., 0 ) 1 (则停止

15、计算若kka(2) 1, ( ) /. ( ) 1, .ikikkkiiikkijijikkjiknimaabbmbiijknaama对于对于, 1 , . 2ni 回代：对于, ) 1 (iibx , , 1 )2(jijiixaxxnij对于./ ) 3(iiiiaxx 2022-6-2320乘除法运算工作量乘除法运算工作量. ), 1,( ,:,)( : ,:) 1(2) 1(nkjiknbknaknmkkikijik次乘法次乘法次除法步消元：第消元过程乘除法次数：回代过程乘除法次数：nnnnkknnkkn6522131131)(2112)(111(1)(1)21nnkn nk总的乘除法

16、运算次数：nnn312331非零判断次数最多为：11()(1)21nn kn nk行交换的元素个数为：11()(1)21nn kn nk1(1)2nkn nk21(1)(21)6nkn nnk2022-6-23215.2.3 5.2.3 高斯消去法的适用条件高斯消去法的适用条件 定理定理1 1 方程组系数矩阵的顺序主子式全不方程组系数矩阵的顺序主子式全不 为零则高斯消去法能实现方程组的为零则高斯消去法能实现方程组的 求解。求解。证明证明: 上三角形方程组是从原方程组出发，通过逐上三角形方程组是从原方程组出发，通过逐次进行次进行“一行乘一数加到另一行一行乘一数加到另一行”而得出的，该变而得出的，

17、该变换不改变系数矩阵顺序主子式的值。换不改变系数矩阵顺序主子式的值。2022-6-2322设方程组系数矩阵设方程组系数矩阵 ，其顺序主子式，其顺序主子式 nijaA)(01111mmmmmaaaaA（m =1,2,m =1,2,，n n） 经变换得到的上三角形方程组的顺序主子式经变换得到的上三角形方程组的顺序主子式 0)()2(22)1(11)()2(2)2(22)1(1)1(12)1(11mmmmmmmmmaaaaaaaaaA所以能实现高斯消去法求解所以能实现高斯消去法求解 （m =1,2,m =1,2,，n n） 2022-6-2323定义定义5.1 5.1 设矩阵设矩阵 每一行对角元素的

18、绝对每一行对角元素的绝对值都大于同行其他元素绝对值之和值都大于同行其他元素绝对值之和 nnijaA )(niaanijjijii,2,1,1 则称则称A A为严格对角占优矩阵。为严格对角占优矩阵。 nnnnnnaaaaaaaaaA2122221112112022-6-2324定理定理 5.1 5.1 若方程组若方程组 的系数矩阵的系数矩阵A为严格对为严格对角占优，则用高斯消去法求解时，角占优，则用高斯消去法求解时， 全不全不为零为零。 bAx )(kkka2022-6-2325证证: :先考察消元过程的第先考察消元过程的第1 1步步, ,因因A为严格对角占为严格对角占 优优, ,故故 故故 ,

19、 ,又根据高斯消又根据高斯消 去公式得去公式得 于是于是 njjaa2111011)1(11 aanjiaaaaajiijij,3 ,2,1111)2(nijjjinijjijnijjijaaaaa2111122)2()(12111111injjiinijjijaaaaaa再利用方程组的对角占优性再利用方程组的对角占优性, ,由上式可进一步得由上式可进一步得 111111111112)2()(aaaaaaaaaaaiiiiiiiiinijjij 又由又由 njiaaaaajiijij,3,2,1111)2( 得得 11111111)2(aaaaaaaaaiiiiiiiiii 故有故有 niaa

20、iinijjij,3,2,)2(2)2( 当当A A为严格对角占优时为严格对角占优时, , ,余下的子阵仍是余下的子阵仍是对角占优的，从而又有对角占优的，从而又有 。依次类推全不。依次类推全不为零。为零。 定理证毕。定理证毕。 011) 1 (11aa0)2(22a2022-6-2326 一般线性方程组使用高斯消去法求解时，在一般线性方程组使用高斯消去法求解时，在消元过程中可能会出现消元过程中可能会出现 的情况，这时消去的情况，这时消去法将无法进行；即使法将无法进行；即使 ，但它的绝对值很小，但它的绝对值很小时，用其作除数，会导致其他元素数量级的严重增时，用其作除数，会导致其他元素数量级的严重

21、增长和舍入误差的扩散，将严重影响计算结果的精度。长和舍入误差的扩散，将严重影响计算结果的精度。实际计算时必须避免这类情况实际计算时必须避免这类情况的发生的发生, ,选主元素选主元素消消去法去法就可弥补这一缺陷。就可弥补这一缺陷。 0)( kkka()0kkka 2022-6-2327主元素法的意义主元素法的意义00001. 1,99999. 012 xx例例3.2 用高斯消去法求下列方程组的解用高斯消去法求下列方程组的解 211021215xxxx假设计算在假设计算在4 4位浮点十进值的计算机上求解位浮点十进值的计算机上求解, ,则有则有 5555555510101000002. 010210

22、101000001. 0101 ， 5252151010110 xxx0, 112 xx得到消元后的方程组得到消元后的方程组的实际形式是的实际形式是 显然这不是方程组的解显然这不是方程组的解 )1(10)2(5 2022-6-2328由此回代解出由此回代解出 , ,但这个解不满足原方程组但这个解不满足原方程组, ,解是错误的。这是因为所用的除数太小使得上式在消解是错误的。这是因为所用的除数太小使得上式在消元过程中元过程中“吃掉吃掉”了下式，解决这个问题的方法之一了下式，解决这个问题的方法之一就是采用列选主元高斯消元法。即按列选绝对值大的就是采用列选主元高斯消元法。即按列选绝对值大的系数作为主元

23、素，则将方程组中的两个方程相交换，系数作为主元素，则将方程组中的两个方程相交换，原方程组变为原方程组变为 0, 112 xx得到消元后的方程组得到消元后的方程组 525211021)101 (2xxx110221521xxxx)1(10)2(5 2022-6-2329得到消元后的方程组得到消元后的方程组 125522(1 10 )1 2 10 xxx 110221521xxxx)1(10)2(5 这时这时 110210100000102111010100000101555555 ，即即 12221xxx00001. 1,99999. 012 xx由此回代解出由此回代解出 , ,这个结果这个结果

24、很接近方很接近方程组程组的解的解1,112 xx2022-6-2330 可见用高斯消去法解方程组时可见用高斯消去法解方程组时, ,小主元可能导致小主元可能导致计算失败计算失败, ,因为用绝对值很小的数作除数因为用绝对值很小的数作除数, ,乘数很大乘数很大, ,引起约化中间结果数量级严重增长引起约化中间结果数量级严重增长, ,再舍入就使得计再舍入就使得计算结果不可靠了算结果不可靠了, ,故避免采用绝对值很小的主元素。故避免采用绝对值很小的主元素。以便减少计算过程中舍入误差对计算解的影响。以便减少计算过程中舍入误差对计算解的影响。 解决的方法就是选主元减少解决的方法就是选主元减少计算过程中舍入误计

25、算过程中舍入误差对计算解的影响。差对计算解的影响。2022-6-2331交换原则：通过方程或变量次序的交换，使在交换原则：通过方程或变量次序的交换，使在对角线位置上获得绝对值尽可能大的系数作对角线位置上获得绝对值尽可能大的系数作为为akk(k)，称这样的，称这样的akk(k) 为为主元素主元素，并称使用，并称使用主元素的消元法主元素的消元法为主元素法为主元素法 根据主元素选取范围分为：根据主元素选取范围分为： 列主元素法、列主元素法、 行主元素法、行主元素法、 全主元素法全主元素法记笔记记笔记5.3 5.3 高斯主元素消去法高斯主元素消去法2022-6-23325.3.2 列主元素法列主元素法

26、 列列主元素法就是在待消元的所在列中选取主元，经方程主元素法就是在待消元的所在列中选取主元，经方程的行交换，置主元素于对角线位置后进行消元的方法。的行交换，置主元素于对角线位置后进行消元的方法。 55444020321910321321321xxxxxxxxx解：选择解：选择-20作为该列的作为该列的主元素主元素，(4)(5)(6)计算计算m21 =10/-20=-0.5,m31=1/-20=-0.05例例5.4 用用列主元素法解下列线性方程组列主元素法解下列线性方程组(1)(2)(3) 55432191044020321321321xxxxxxxxx2022-6-2333(5)- m21(4

27、), (6)- m31(4)得得 2 . 505. 5655 . 1340202222321xxxxxxx选选6为主元素为主元素计算计算m32=1/6=0.16667，(10)- m32(9) 得得记笔记记笔记(7) (8) 55 . 12 . 505. 56340203232321xxxxxxx 13332. 434168. 22 . 505. 5634020332321xxxxxx(9)(10)(11)2022-6-2334保留有主元素的方程保留有主元素的方程 -20 x1 +40 x2 + x3 =4 (4) 6x2 + 5.05x3 =5.2 (9) -2.34168x3=4.1333

28、2 (11)进行回代进行回代x3 =-1.76511x2=2.35230 x1=4.41634记笔记记笔记 列选主元素的计算方法与高斯消去法完全一样列选主元素的计算方法与高斯消去法完全一样, ,不同的是在每步消元之前要按列选出主元不同的是在每步消元之前要按列选出主元2022-6-2335例例5.5 5.5 用矩阵的初等行变换求解解方程组用矩阵的初等行变换求解解方程组 754217743322321321321xxxxxxxxx 解解: : 用矩阵的初等行变换求解用矩阵的初等行变换求解, ,对增广矩阵对增广矩阵 ( (带圆圈元素带圆圈元素为主元素为主元素) ) 2022-6-2336 2 . 1

29、2 . 1005 . 65 . 85 . 7017745 . 25 . 05 . 105 . 65 . 85 . 7017745 . 65 . 85 . 705 . 25 . 05 . 1017747542332217747542177433222323131212512121)1(rrrrrrrrrrbAA2022-6-2337全主元素消去法全主元素消去法 是通过方程或是通过方程或变量变量次序的交换，使在对角次序的交换，使在对角线位置上获得绝对值尽可能大的系数为线位置上获得绝对值尽可能大的系数为 ，称这样的称这样的 为主元素。尽管它的算法更稳为主元素。尽管它的算法更稳定，但计算量较大，实际应

30、用中大多数使用列定，但计算量较大，实际应用中大多数使用列主元素消去法即可满足需要。主元素消去法即可满足需要。 )(kkka)(kkka2022-6-2338不是按列选主元素，而是在全体不是按列选主元素，而是在全体待选系数中选取，则得待选系数中选取，则得全主元素法。全主元素法。例例5.3 用用全主元素法解下列线性方程组全主元素法解下列线性方程组 10 x1 - 19x2 - 2x3=3 (1)-20 x1 +40 x2 + x3 =4 (2) x1 + 4x2 + 5x3=5 (3)解：选择所有系数中绝对值最大的解：选择所有系数中绝对值最大的40作为作为主元素，主元素，交换第一、二行和交换第一、

31、二列使该主元素位于交换第一、二行和交换第一、二列使该主元素位于对角线的第一个位置上，得对角线的第一个位置上，得40 x2 - 20 x1 + x3 =4 (4)-19x2+10 x1 - 2x3=3 (5) 4x2+ x1 +5x3=5 (6)记笔记记笔记2022-6-2339计算计算m21=-19/40=0.475，m31=4/40=0.1(5)- m21(4), (6)- m31(4) 消去消去x2 得得 0.5x1 1.525 x3 =4.9 (7) 3x1 + 4.9 x3 =4.6 (8)选选4.9为主元素为主元素 4.9 x3 + 3x1=4.6 (9)1.525 x3 +0.5x

32、1=4.9 (10)计算计算m32=-1.525/4.9=-0.31122， (10)- m32(9)消去消去x2得得1.43366x1=6. 33161 (11)记笔记记笔记2022-6-2340保留有主元素的方程保留有主元素的方程40 x2 - 20 x1 + x3 =4 (4) 4.9x3 + 3x1=4.6 (9) 1.43366x1=6. 33161 (11)进行回代进行回代x1=4.41634 x3 =-1.76511x2=2.352302022-6-23415.4 矩阵三角分解法矩阵三角分解法 矩阵三角分解法是高斯法解方程组的一种变形解法矩阵三角分解法是高斯法解方程组的一种变形解

33、法 5.4.1 5.4.1 矩阵三角分解原理矩阵三角分解原理 应用高斯消去应用高斯消去法解法解 n 阶线性方程组阶线性方程组 Ax=b, 经经过过n步消元之后步消元之后, , 得出一个等价的上三角型方程组得出一个等价的上三角型方程组A(n) x=b(n), 对上三角形方程组用逐步回代就可以求对上三角形方程组用逐步回代就可以求出解来。上述过程可通过矩阵分解来实现。出解来。上述过程可通过矩阵分解来实现。 将非奇异阵将非奇异阵A分解成一个下三角阵分解成一个下三角阵L和一个上三和一个上三角阵角阵U的乘积的乘积 A=LU 称为对称为对矩阵矩阵A的三角分解，又称的三角分解，又称LU分解分解UL2022-6

34、-2342 把把A分解成一个单位下三角阵分解成一个单位下三角阵L和一个上三角和一个上三角阵阵U的乘积称为的乘积称为杜利特尔（杜利特尔（Doolittle）分解分解。其中其中 nnnnnnuuuuuuUlllL222112112121,111ALU 2022-6-2343若把若把A分解成一个下三角阵分解成一个下三角阵L和一个单位上三角和一个单位上三角阵阵U的乘积称为的乘积称为克克洛特洛特分解分解( (Crout) 其中其中 111,211221222111nnnnnnuuuUllllllL11121212221211,1nnnnnnuuuluuLUllu Doolittle 分解分解2022-6

35、-2344 任意矩阵任意矩阵A可分解成可分解成分解成一个分解成一个单位单位下三角阵下三角阵L、一个对角阵一个对角阵和一个单位上三角阵和一个单位上三角阵U的乘积的乘积 1111112112212121nnnnnuuudddlllA杜利特尔（杜利特尔（Doolittle）LUA 克洛克洛特分解特分解 (Crout) LUA L单位下三角阵单位下三角阵U单位上三角阵单位上三角阵2022-6-23455.4.2 用三角分解法解方程组用三角分解法解方程组 求求解线性方程组解线性方程组 Ax=b 时时,先对非奇异矩阵先对非奇异矩阵A进进行行LU分解分解(Doolittle)使使A=LU，那么方程组就化为，

36、那么方程组就化为,1112121 nnlllLbLYbLUXYUX ,令 nnnnbyylylbyylby22112212111bLUX nyyy21Y2022-6-2346XYUXY求解方程已知 , nnnnnnnnyxuyxuxuyxuxuxu2122211212111XbLYbLUXYUX ,令 nnnnuuuuuuU2221121111xxxnn 问题问题转化为求解两个简单转化为求解两个简单的上、下三角方程的上、下三角方程组组 这这就是求解线性方程组的三角分解法的就是求解线性方程组的三角分解法的基本基本思想，思想， 下面下面只介绍杜利特尔（只介绍杜利特尔（Doolittle）分）分解法

37、。解法。2022-6-2347 nnnnnnnnnnnnuuuuuulllaaaaaaaaa222112112121212222111211111 由矩阵乘法规则由矩阵乘法规则 nnnnnnnnnnnnnnnnnuulululululuulululululuuluululuuu111,1122212111132321312232123111312121221221112111211比比较较等等式式两两边边2022-6-2348nnnnnnnnnnnuuuuuulllaaaaaaaaa2221121121212122221111111111 由矩阵乘法规则由矩阵乘法规则niuaii, 2 , 1

38、11niulaii, 3 , 21111 由此可得由此可得U的第的第1行元素和行元素和L的第的第1列元素列元素niauii, 2 , 111niualii,3 ,211112022-6-2349 再确定再确定U的第的第k行元素与行元素与L的第的第k列元素列元素, ,对于对于k=2,3, ,n计算：计算： 计算计算U的第的第k行元素行元素 11krrjkrkjkjulau 计算计算L L的第的第k k列元素列元素 11kikirr krikk kalulu nnnnnnnnnnnuuuuuulllaaaaaaaaa2221121121212122221111111111(,1, )jk kn (

39、,1,)ik kn 2022-6-2350利用上述计算公式便可逐步求出利用上述计算公式便可逐步求出U与与L的各元素的各元素求解求解 Ly=b , Ly=b , 即计算即计算: : 1111),3,2(ikkikiiniylbyby 求解求解 Ux=y , Ux=y , 即计算：即计算： )1 ,2,1(1niuxuyxuyxiinikkikiinnnn2022-6-2351 显然显然, 当当 时时, 解解Ax=b直直接三角分解法计算才能完成。设接三角分解法计算才能完成。设A为非奇异矩阵为非奇异矩阵, 当当 时计算将中断或者当时计算将中断或者当 绝对值很小时，绝对值很小时，按分解公式计算可能引起

40、舍入误差的积累，因此按分解公式计算可能引起舍入误差的积累，因此可采用与列主元消去法类似的方法，对矩阵进行可采用与列主元消去法类似的方法，对矩阵进行行交换，则再实现矩阵的三角分解。行交换，则再实现矩阵的三角分解。 ), 2 , 1(0nkukk0kku kku33n用三角分解法求解用三角分解法求解Ax=b大约需要大约需要 次乘除法。次乘除法。 2022-6-2352例例6.8 用三角分解法解方程组用三角分解法解方程组 542631531321321xxx 332322131211323121111631531321uuuuuulll令 332332133122321231113123132122

41、12211121131211631531321uulululululuuluululuuu2022-6-2353例例6.8 用三角分解法解方程组用三角分解法解方程组 ,321131211 uuu121312212222 ulau231513212323 ulau11/)213(/)(2212313232 uulal121316233213313333 ululau 33233213312232123111312313212212211121131211631531321uulululululuuluululuuu113121 ll2022-6-2354例例6.8 用三角分解法解方程组用三角分解

42、法解方程组 542631531321321xxx121321111111ULbAx bLUx YUx 令令bLY 先先解解2022-6-2355例例6.8 用三角分解法解方程组用三角分解法解方程组 542121321111111X101123 xxx所以方程组的解为所以方程组的解为bLY 先先解解 542111111Y 542321211yyyyyy得得TTY)1 ,2,2( YUX 再再解解 122121321X 122232332321xxxxxx2022-6-23565.5 解三对角线方程组的追赶法解三对角线方程组的追赶法 nnnnnnnnnfffffxxxxxbacbacbacbacb

43、1321132111133322211 在一些实际问题中，例如解热传递方程，三次在一些实际问题中，例如解热传递方程，三次样条求系数都会遇到解对角占优的三对角方程组。样条求系数都会遇到解对角占优的三对角方程组。)1,3,2,0(32111 nicacbcabcbiinniii，简记为fAx 若若A A满足条件满足条件( (对角占优对角占优）2022-6-2357 用归纳法可以证明，满足上述条件的三对角线用归纳法可以证明，满足上述条件的三对角线性方程组的性方程组的系数矩阵系数矩阵A非奇异非奇异，所以可以利用矩阵，所以可以利用矩阵的三角分解法来推导解三对角线性方程组的计算公的三角分解法来推导解三对角

44、线性方程组的计算公式，用克洛特分解法，将式，用克洛特分解法，将A分解成两个三角阵的乘分解成两个三角阵的乘积，设积，设A=LU 11112122111122211nnnnnnnnuuulllbacbacbacb三对角矩阵三对角矩阵A可分解为两个两对角下、上三角矩阵的乘积可分解为两个两对角下、上三角矩阵的乘积2022-6-2358 nnnnnbacbacbacb11122211 111111211133221nnnnnuuulllll nnnnnnnnnnluulluulluull1111211222122111), 2(niaii .,iiul中的和只需求UL2022-6-2359 nnnnnb

45、acbacbacb11122211比较矩阵对应元素比较矩阵对应元素,11bl iiiiiiiuabllcu111/nnluulul12211则可计算得则可计算得 可依次计算可依次计算 nnnnnnnnnnluaaulluaaulluaaull11112112221221111, 1 ni111lcu ,11bl ,2222122 ulcluab 2221222lcuuabl2022-6-2360 nnnnnbacbacbacb11122211比较矩阵对应元素比较矩阵对应元素,11lb 可通过下面两式得到实际上iiul , nnnnnnnnnnluaaulluaaulluaaull1111211

46、222122111.,2/,1111nilcablbliiiii 1,2,1111 niluabulciiiiiii.1, 1 nicluiii,21nlll.121 nuuu2022-6-2361程：等价于解两个三角形方求解fAX )1(il由递推公式计算.,2;, 1 XYUXYfLY求求 从而得到求三对角方程组的追赶法公式：从而得到求三对角方程组的追赶法公式：fLY 解)2(., 3 , 2,1111nilyafylfyiiiii nilcablbliiiii,2/,1111 nnnnnnfffyyylalalalal212111332212022-6-2362程：等价于解两个三角形方求

47、解fAX .,2;, 1 XYUXYfLY求求 从而得到求三对角方程组的追赶法公式：从而得到求三对角方程组的追赶法公式：YUX 解)4(. 1 , 1,1 nixuyxyxiiiinnnnyyylll2121,11xxxnn 追赶 nnnyyyxxxuuu212112111111)3(iu由递推公式计算.1, 1 nicluiii2022-6-2363例例3.9 用追赶法求解三对角方程组用追赶法求解三对角方程组 501352242231124321xxxx解解 ,211 bl,2511222 lcabl65,54,21333222111 lculculcunilcablbliiiii,2/,1

48、111 iiilcu ,51222333 lcabl,31033444 lcabl2022-6-23641, 5 . 12321222111lyafylfy1,654344432333lyafylyafy0, 1433344xuyxyx2, 121113222xuyxxuyx由由Ly=f 解出解出y又由又由Ux=y解出解出x 50131651541211252512225124321xxxx2022-6-23655.6 解正定矩阵方程的平方根法解正定矩阵方程的平方根法 工程实际计算中工程实际计算中, ,线性方程组的系数矩阵线性方程组的系数矩阵A常常具常常具有有正定正定(对称对称)性，其各阶顺序

49、主子式及全部特征值均性，其各阶顺序主子式及全部特征值均大于大于0。矩阵的这一特性使它的三角分解也有更简单。矩阵的这一特性使它的三角分解也有更简单的形式，从而导出一些特殊的解法，如平方根法与改的形式，从而导出一些特殊的解法，如平方根法与改进的平方根法。进的平方根法。 乔累斯基乔累斯基(Cholesky)分解法分解法2022-6-2366证：因证：因A是正定矩阵是正定矩阵, , A的顺序主子式的顺序主子式 i i0, 0, 1i n 因此存在惟一的分解因此存在惟一的分解 A=LU 定理定理6 6 设设A是正定矩阵，则存在惟一的对角元素均为是正定矩阵，则存在惟一的对角元素均为正数的下三角阵正数的下三

50、角阵 L L，使，使A=LLT . .nnnnnnnnnnnuuuuuulllaaaaaaaaa22211211212121222211111111112022-6-2367L是单位下三角阵是单位下三角阵, U是上三角阵是上三角阵, 将将U再分解再分解 01, 1, 111111122211111DUuuuuuuuuunnnnnnn 其中其中D为对角阵为对角阵, U0为单位上三角阵，于是为单位上三角阵，于是 A = L U = L D U0 又又 A = AT = U0TD LT由分解惟一性由分解惟一性, 即得即得 U0T=L nnnnuuuuuu2221121100TAL DL2022-6-

51、23681122nnuuDu 记记 又因为又因为det(Ak)0,(k=1,2,n), 故故于是对角阵于是对角阵D还可分解还可分解 0,(1,2, )iiuin 2121221122112211DDuuuuuuuuuDnnnnnn 1111222211()()TTTTALDLLD D LLDLDL L 其中其中 为下三角阵为下三角阵, ,令令L=LL=L1 1，定理得证。，定理得证。 121LLD 2022-6-2369将将 A=LLT 展开展开，写成，写成 nnnnnnnnnnnnnllllllllllllaaaaaaaaa22212111212221112122221111111按矩阵乘法

52、展开，可逐行求出分解矩阵按矩阵乘法展开，可逐行求出分解矩阵L L的元素，计的元素，计算公式是对于算公式是对于i=1,2,n 21112)(ikikiiiilaliiikikjkjijilllal11j=i+1, i+2,n 这一方法称为这一方法称为平方根法平方根法,又称又称乔累斯基乔累斯基(Cholesky)分解分解,它所需要的乘除次数约它所需要的乘除次数约 为数量级为数量级, ,比比LU分解节分解节省近一般的工作量。省近一般的工作量。 36n2022-6-2370例例6.9 6.9 平方根法求解方程组平方根法求解方程组 7851102021211321xxx解解: : 因方程组系数矩阵对称正

53、定因方程组系数矩阵对称正定, ,设设A= ,A= ,即：即： TLL3332223121113332312221111102021211llllllllllll212, 111, 11131311121211111lallalal1122212222lal212102221313232lllal344112322313333llal322111L由由Ly=bLy=b解得解得 3, 3, 5321yyy由由 解得解得 yxLT1, 5, 2321xxx 由此例可以看出，平方根法解正定方程组的缺由此例可以看出，平方根法解正定方程组的缺点是需要进行开方运算。为避免开方运算，我们改点是需要进行开方运算

54、。为避免开方运算，我们改用单位三角阵作为分解阵，即把对称正定矩阵用单位三角阵作为分解阵，即把对称正定矩阵A分分解成解成 TLDLA 的形式，其中的形式，其中 2022-6-2371ndddD21为对角阵，而为对角阵，而 1111321323121nnnllllllL是单位下三角阵是单位下三角阵, ,这里分这里分解公式为解公式为 11211, 2 , 11, 2 , 1/)(ikikkiiijkjjkikkijijnildadijdlldal2022-6-2372据此可逐行计算据此可逐行计算 运用这种矩阵分解方法运用这种矩阵分解方法, ,方程组方程组Ax=bAx=b即即可归结为求解两个上三角方程

55、组可归结为求解两个上三角方程组 332312211dlldldbxDLLT)(bLy bDxLT1和和其计算公式分别为其计算公式分别为 11,2, 1ikkikiiniylby和和 nikkkiiiinnixldyx11 , 1,/求解方程组的上述算法称为求解方程组的上述算法称为改进的平方根法改进的平方根法。这种。这种方法总的计算量约为方法总的计算量约为 ，即仅为高斯消去法计，即仅为高斯消去法计算量的一半。算量的一半。 6/3n2022-6-2373 向量范数是用来度量向量长度的向量范数是用来度量向量长度的,它可以看它可以看作是解析几何中二、三维向量长度概念的推广。作是解析几何中二、三维向量长

56、度概念的推广。用用Rn表示表示n维实向量空间。维实向量空间。 为了研究线性方程组近似解的误差和迭代为了研究线性方程组近似解的误差和迭代法的收敛性法的收敛性, , 有必要对向量及矩阵的有必要对向量及矩阵的 “ “大小大小”引进某种度量引进某种度量-范数的概念。范数的概念。2022-6-2374记笔记记笔记定义定义5.2 对任一向量对任一向量X Rn, 按照一定规则确定一个实按照一定规则确定一个实数与它对应数与它对应, 该实数记为该实数记为|X|, 若若|X|满足下面三个满足下面三个性性质质:则称该实数则称该实数|X|X|为向量为向量X X的的范数范数(1) |X| 0；|X|=0当且仅当当且仅当

57、X=0；(2) 对任意实数对任意实数 ， | X|=| | |X|；(3) 对对任意向量任意向量Y Y R Rn n，|X+Y| X+Y| | |X|+|Y|X|+|Y|)( )( )( 三角不等式三角不等式齐次性齐次性正定性正定性2022-6-2375max,max121ininxxxxX 记笔记记笔记 2x niinxxxxX12112112222212 niinxxxxX2022-6-2376定理定理5.1 5.1 对对于任意于任意向量向量 x , ,有有 xxpplimpnipipxx11 即即 xnxxpp1当当 p， 证证:其中max1inixx pnipipxx11 ppinix

58、n11max ppinixx11max xxpplim11pn2022-6-2377 当不需要指明使用哪一种向量范数时，就用记号当不需要指明使用哪一种向量范数时，就用记号|.|泛指任何一种向量范数。泛指任何一种向量范数。 有了向量的范数就可以用它来衡量向量的大小和表示有了向量的范数就可以用它来衡量向量的大小和表示向量的误差。向量的误差。 设设x*为为Ax=b的精确解，的精确解，x为其近似解，则其绝对误差为其近似解，则其绝对误差可表示成可表示成|x-x* |，其相对误差可表示成，其相对误差可表示成的的特特例例范范数数上上述述范范数数都都是是pnipipxXp11)|(| 记笔记记笔记*xxx x

59、xx* 或或2022-6-2378:具具有有以以下下性性质质向向量量范范数数 x101 xxx时时，当当）（yxyxyyxyyxx )(:证证yxyxxx )3()2(2022-6-2379例例5.11 设设 , 计算计算 21,xxx 42101 ixx1解解:maxixx 2122)( ixx22 ,1,0 , 1max 62)1(012222 Tx)2 , 1, 0 , 1( 2022-6-2380定义定义5.4 ( 向量序列的极限向量序列的极限 ) 设设 为为 中中的的一向量序列，一向量序列， , 记记 。如果如果 (i =1,2, n)，则称则称 收收敛于向量敛于向量 ，记为，记为

60、)(kxnRnRx * Tknkkkxxxx)()(2)(1)(, Tnxxxx*2*1*, *)(limikikxx )(kx*x*)(limxxkk 定理定理 5.2（向量范数的等价性）（向量范数的等价性） 设设 为为 上任意两种向量范数上任意两种向量范数, 则存在常数则存在常数 C1, C20, 使得对任意使得对任意 恒有恒有qpxx,nRnRxpqpxCxxC21 （证（证: :略）略） 2022-6-2381定理定理5.3 其中其中 为向量中的任一种范数。为向量中的任一种范数。 0limlim*)(*)( xxxxkkkk证证由于由于对于对于 上的任一种上的任一种 范数范数, 由定理