ch线性代数方程组的直接解法PPT课件

1、Tel： 86613747E-mail： 授课授课: 68学分：学分：4第1页/共100页3.1 引言引言 在工程技术、自然科学和社会科学中，经常在工程技术、自然科学和社会科学中，经常遇到的许多问题最终都可归结为解线性方程组，遇到的许多问题最终都可归结为解线性方程组，如电学中网络问题、用最小二乘法求实验数据的如电学中网络问题、用最小二乘法求实验数据的曲线拟合问题，工程中的三次样条函数的插值问曲线拟合问题，工程中的三次样条函数的插值问题，经济运行中的投入产出问题以及大地测量、题，经济运行中的投入产出问题以及大地测量、机械与建筑结构的设计计算问题等等，都归结为机械与建筑结构的设计计算问题等等，都归

2、结为求解线性方程组或非线性方程组的数学问题。因求解线性方程组或非线性方程组的数学问题。因此线性方程组的求解对于实际问题是极其重要的。此线性方程组的求解对于实际问题是极其重要的。 第第3 3章章 解线性方程组的直接方法解线性方程组的直接方法 第2页/共100页 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa.22112222212111212111 nnnnnnnnbbbBxxxXaaaaaaaaaA.,.,.2121212222111211第第3章章 解线性方程组的直接法解线性方程组的直接法 常见的线性方程组是方程个数和未知量个常见的线性方程组是方程个数和未知量个数相同的数相同

3、的n阶线性方程组，一般形式为阶线性方程组，一般形式为 简记为简记为 Ax=b，其中，其中 ( 3.1 ) 一般一般b0, 当系数矩阵当系数矩阵A非奇异非奇异( (即即detA0) 时，方程组（）有惟一解。时，方程组（）有惟一解。 第3页/共100页线性方程组的数值解法一般有两类：线性方程组的数值解法一般有两类：1. 直接法：就是经过有限步算术运算，可求得直接法：就是经过有限步算术运算，可求得方程组精确解的方法（若计算过程中没有舍方程组精确解的方法（若计算过程中没有舍入误差），如克莱姆法则就是一种直接法，入误差），如克莱姆法则就是一种直接法，直接法中具有代表性的算法是高斯直接法中具有代表性的算法

4、是高斯(Gauss)消去法。消去法。2. 迭代法迭代法: ( 第四章介绍）就是用某种极限过第四章介绍）就是用某种极限过程去逐步逼近线性方程组的精确解的方法。程去逐步逼近线性方程组的精确解的方法。也就是也就是从解的某个近似值出发，通过构造一从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。个无穷序列去逼近精确解的方法。( (一般有一般有限步内得不到精确解限步内得不到精确解) )第4页/共100页 3.2 解线性方程组的直接法（高斯消去法）解线性方程组的直接法（高斯消去法） 3.2.1 高斯消去法的基本思想高斯消去法的基本思想先用一个简单实例来说明先用一个简单实例来说明Gauss法的基

5、本思想法的基本思想例例3.1 3.1 解线性方程组解线性方程组 72452413221321321xxxxxxxx解解: : 该方程组的求解过程实际上是将中学学过的消该方程组的求解过程实际上是将中学学过的消元法标准化元法标准化, ,将一个方程乘或除以某个常数将一个方程乘或除以某个常数, ,然后将然后将两个方程相加减两个方程相加减, ,逐步减少方程中的未知数逐步减少方程中的未知数, ,最终使最终使每个方程只含有一个未知数每个方程只含有一个未知数, ,从而得出所求的解。从而得出所求的解。整个过程分为消元和回代两个部分。整个过程分为消元和回代两个部分。 第5页/共100页（1）消元过程）消元过程第第

6、1步步: :将方程将方程乘上乘上( (-2)加到方程加到方程 上去上去, ,将将方程方程 乘上乘上 加到方程加到方程 上去上去, ,这样就消去这样就消去了第了第2、3个方程的个方程的 项项, ,于是就得到等价方程于是就得到等价方程组组 211x213232524132232321xxxxxx第6页/共100页第第2步：将方程步：将方程 乘上乘上 加到方程加到方程 上去，上去，这样就消去了第这样就消去了第3个方程的个方程的 项，于是就得项，于是就得到等价方程组到等价方程组 852x4218724132332321xxxxxx这样，消元过程就是把原方程组化为上三角这样，消元过程就是把原方程组化为上

7、三角形方程组，其系数矩阵是上三角矩阵。形方程组，其系数矩阵是上三角矩阵。 （2）回代过程）回代过程回代过程是将上述三角形方程组自下而上求回代过程是将上述三角形方程组自下而上求解，从而求得原方程组的解：解，从而求得原方程组的解： 6, 1,9321xxx第7页/共100页前述的消元过程相当于对原方程组前述的消元过程相当于对原方程组 741021524312321xxx的增广矩阵进行下列变换的增广矩阵进行下列变换( ( 表示增广矩阵的第表示增广矩阵的第 行）行） 702145241312bAA21323250214013121213)2()21(rrrr42187002140131223)85(r

8、r同样可得到与原方程同样可得到与原方程组等价的方程组组等价的方程组 iri第8页/共100页 由此看出由此看出, ,高斯消去法解方程组基本思想是设高斯消去法解方程组基本思想是设法消去方程组的系数矩阵法消去方程组的系数矩阵A的主对角线下的元素的主对角线下的元素, ,而而将将Ax=b化为等价的上三角形方程组化为等价的上三角形方程组, ,然后再通过回然后再通过回代过程便可获得方程组的解。换一种说法就是用矩代过程便可获得方程组的解。换一种说法就是用矩阵行的初等变换将原方程组系数矩阵化为上三角形阵行的初等变换将原方程组系数矩阵化为上三角形矩阵矩阵, ,而以上三角形矩阵为系数的方程组的求解比较而以上三角形

9、矩阵为系数的方程组的求解比较简单简单, ,可以从最后一个方程开始可以从最后一个方程开始, ,依次向前代入求出依次向前代入求出未知变量未知变量 这种求解上三角方程组的这种求解上三角方程组的方法称为方法称为回代回代, 通过一个方程乘或除以某个常数通过一个方程乘或除以某个常数, ,以以及将两个方程相加减及将两个方程相加减, ,逐步减少方程中的变元数逐步减少方程中的变元数, ,最最终将方程组化成上三角方程组终将方程组化成上三角方程组, ,一般将这一过程称为一般将这一过程称为消元消元,然后再回代求解。然后再回代求解。11,xxxnn通常把按照先消元通常把按照先消元, ,后回代两个步骤求解线性后回代两个步

10、骤求解线性方程组的方法称为方程组的方法称为高斯高斯（Gauss）消去法。消去法。第9页/共100页3.2.2 高斯消去法算法构造高斯消去法算法构造 我们知道我们知道, ,线性方程组线性方程组( (3.1)用矩阵形式表示为用矩阵形式表示为 nnnnnnnnbbbxxxaaaaaaaaa2121212222111211( 3.3 ) 解线性方程组（）的高斯（解线性方程组（）的高斯（Gauss）消去法的消元过）消去法的消元过程就是对程就是对( 3.3 )的增广矩阵进行行初等变换。将例中的增广矩阵进行行初等变换。将例中解三阶线性方程组的消去法推广到一般的解三阶线性方程组的消去法推广到一般的 阶线阶线性

11、方程组并记性方程组并记则高斯消去法的算法构造归纳为：则高斯消去法的算法构造归纳为： nn),2, 1,(,)1()1(njibbaaiiijij第10页/共100页 消元过程消元过程, ,斯消去法的消元过程由斯消去法的消元过程由n-1步组成：步组成： 第第1 1步步 设设 , ,把把(3.3)(3.3)中的第一列中元素中的第一列中元素 消为零消为零, ,令令 0) 1 (11a)1(1)1(31)1(21,naaa), 3 , 2(,)1(11)1(11niaamii用用 乘以第乘以第1 1个方程后加到第个方程后加到第 个方程上去个方程上去, ,消去消去第第2 2n n个方程的未知数个方程的未

12、知数 , ,得到得到 即即 1 imi1x)2()2(bxA)2()2(2)1(121)2()2(2)2(2)2(22)1(1)1(12)1(11nnnnnnnbbbxxxaaaaaaanjibmbbamaaiiijiijij,3,2,)1(11)1()2()1(11)1()2(其中其中 第11页/共100页第第k步步 （k=2,3,n-1）继续上述消元过程，设）继续上述消元过程，设第第k-1次消元已经完成，得到与原方程组等价的次消元已经完成，得到与原方程组等价的方程组方程组 knkknkknnknkkknkkknnbbbbxxxxaaaaaaaaa)()2(2) 1 (121)()()()(

13、)2(2)2(22) 1 (1) 1 (12) 1 (11nkjibmbbamaakkikkikikkjikkijkij,1,)()()1()()()1(), 1()()(nkiaamkkkkikik记为记为 其中其中)()(kkbxA第12页/共100页只要只要 , ,消元过程就可以进行下去消元过程就可以进行下去, ,直到直到经过经过n-1n-1次消元之后，消元过程结束，得到与次消元之后，消元过程结束，得到与原方程组等价的上三角形方程组原方程组等价的上三角形方程组, ,记为记为 0)(kkka)()(nnbxA或者写成或者写成 )()2(2) 1 (121)()2(2)2(22) 1 (1)

14、 1 (12) 1 (11nnnnnnnnbbbxxxaaaaaa第13页/共100页)()()2(2)2(22)2(22)1(1)1(12)1(121)1(11nnnnnnnnnnbxabxaxabxaxaxa即即 ( (3.7) （2）回代过程）回代过程就是对上三角方程组（）自下而上逐步回代解方程就是对上三角方程组（）自下而上逐步回代解方程组计算，即组计算，即 )1 ,2, 1(,)(1)()()()(niaxabxabxiiijnijiijiiinnnnnn第14页/共100页（3 3）高斯消去法的计算步骤：）高斯消去法的计算步骤： 消元过程消元过程; ;设设 计算计算 1,2, 1,0

15、)(nkakkk对nkkjibmbbamaaaamkkikkikikkjikkijkijkkkkikik,2,1,)()()1()()()1()()( 回代过程回代过程 1,2,1)(1)()()()(nniaxabxabxiiijnijiijiiinnnnnn第15页/共100页(4) (4) 高斯消去法流程图高斯消去法流程图 ，见，见P P4242(5)(5) GaussGauss消去法计算量消去法计算量 331n 消元计算消元计算: aij(k+1)= aij(k)- mik akj(k) (i,j=k+1,k+2, , n) 第一第一 步计算乘数步计算乘数mik, mik=ai1/a1

16、1 (i=2,3,n) 需要需要n-1次除法运算次除法运算, 计算计算 aij(2）(i,j=2,3,n) 需要需要(n-1)2次乘法运算及次乘法运算及(n-1)2次加减法运次加减法运 算算,第16页/共100页第第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)加减法次数：加减法次

17、数：AS= n(n-1)(2n-1)/6第17页/共100页3.2.3 3.2.3 高斯消去法的适用条件高斯消去法的适用条件 定理定理3.1 3.1 方程组系数矩阵的顺序主子式全不方程组系数矩阵的顺序主子式全不 为零则高斯消去法能实现方程组的为零则高斯消去法能实现方程组的 求解。求解。证明证明 上三角形方程组是从原方程组出发，通上三角形方程组是从原方程组出发，通过逐次进行过逐次进行“一行乘一数加到另一行一行乘一数加到另一行”而得出而得出的，该变换不改变系数矩阵顺序主子式的值。的，该变换不改变系数矩阵顺序主子式的值。 第18页/共100页设方程组系数矩阵设方程组系数矩阵 ，其顺序主子式，其顺序主

18、子式 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） 第19页/共100页定义定义3.1 3.1 设矩阵设矩阵 每一行对角元素每一行对角元素的绝对值都大于同行其他元素绝对值之和的绝对值都大于同行其他元素绝对值之和 nijaA)(niaanijjijii,2, 1,1则称则称A

19、A为严格对角占优矩阵。为严格对角占优矩阵。 定理定理3.2 3.2 若方程组若方程组 的系数矩阵的系数矩阵A为严为严格对角占优，则用高斯消去法求解时，格对角占优，则用高斯消去法求解时， 全全不不为零为零。 bAx )(kkka第20页/共100页证证: :先考察消元过程的第先考察消元过程的第1 1步步, ,因因A为严格对角占为严格对角占 优优, ,故故 故故 , ,又根据高斯消又根据高斯消 去公式得去公式得 于是于是 njjaa2111011)1(11 aanjiaaaaajiijij,3 ,2,1111)2(nijjjinijjijnijjijaaaaa2111122)2()(1211111

20、1injjiinijjijaaaaaa再利用方程组的对角占优性再利用方程组的对角占优性, ,由上式可进一步得由上式可进一步得 111111111112)2()(aaaaaaaaaaaiiiiiiiiinijjij又由又由 njiaaaaajiijij, 3 ,2,1111)2(得得 11111111)2(aaaaaaaaaiiiiiiiiii故有故有 niaaiinijjij,3,2,)2(2)2(当当A A为严格对角占优时为严格对角占优时, , ,余下的子阵仍是余下的子阵仍是对角占优的，从而又有对角占优的，从而又有 。依次类推全不。依次类推全不为零。为零。 定理证毕。定理证毕。 011) 1

21、 (11aa0)2(22a第21页/共100页 一般线性方程组使用高斯消去法求解时，一般线性方程组使用高斯消去法求解时，在消元过程中可能会出现在消元过程中可能会出现 的情况，这的情况，这时消去法将无法进行；即使时消去法将无法进行；即使 ，但它的，但它的绝对值很小时，用其作除数，会导致其他元素绝对值很小时，用其作除数，会导致其他元素数量级的严重增长和舍入误差的扩散，将严重数量级的严重增长和舍入误差的扩散，将严重影响计算结果的精度。实际计算时必须避免这影响计算结果的精度。实际计算时必须避免这类情况的发生。主元素消去法就可弥补这一缺类情况的发生。主元素消去法就可弥补这一缺陷。陷。 0)(kkka0)

22、(kkka第22页/共100页交换原则：通过方程或变量次序的交交换原则：通过方程或变量次序的交换，使在对角线位置上获得绝对值尽换，使在对角线位置上获得绝对值尽可能大的系数作为可能大的系数作为akk(k)，称这样的，称这样的akk(k) 为为主元素主元素，并称使用主元素的消，并称使用主元素的消元法元法为主元素法为主元素法根据主元素选取范围分为：列主元素根据主元素选取范围分为：列主元素法、行主元素法、全主元素法法、行主元素法、全主元素法记笔记记笔记3.2.4 3.2.4 高斯主元素消去法高斯主元素消去法第23页/共100页主元素法的意义主元素法的意义例例3.2 用高斯消去法求下列方程组的解用高斯消

23、去法求下列方程组的解 211021215xxxx解：解： 确定乘数确定乘数 ，再计算系数，再计算系数 52110m5)2(25122122)2(22102101bamaa假设计算在假设计算在4 4位浮点十进值的计算机上求解位浮点十进值的计算机上求解, ,则有则有 5555555510101000002. 010210101000001. 0101，这时方程组的实际形式是这时方程组的实际形式是 5252151010110 xxx由此回代解出由此回代解出 , ,但这个解不满足原但这个解不满足原方程组方程组, ,解是错误的。这是因为所用的除数太小解是错误的。这是因为所用的除数太小使得上式在消元过程中

24、使得上式在消元过程中“吃掉吃掉”了下式，解决了下式，解决这个问题的方法之一就是采用列选主元高斯消这个问题的方法之一就是采用列选主元高斯消元法。即按列选绝对值大的系数作为主元素，元法。即按列选绝对值大的系数作为主元素，则将方程组中的两个方程相交换，原方程组变则将方程组中的两个方程相交换，原方程组变为为 1, 021xx110221521xxxx得到消元后的方程组得到消元后的方程组 525211021)101 (2xxx第24页/共100页这时这时 5555555510101000002. 010210101000001. 0101，因而方程组的实际形式是因而方程组的实际形式是 12221xxx由

25、此回代解出由此回代解出 , ,这个结果是正确的这个结果是正确的 1, 121xx 可见用高斯消去法解方程组时可见用高斯消去法解方程组时, ,小主元可小主元可能导致计算失败能导致计算失败, ,因为用绝对值很小的数作除因为用绝对值很小的数作除数数, ,乘数很大乘数很大, ,引起约化中间结果数量级严重增引起约化中间结果数量级严重增长长, ,再舍入就使得计算结果不可靠了再舍入就使得计算结果不可靠了, ,故避免采故避免采用绝对值很小的主元素。以便减少计算过程中用绝对值很小的主元素。以便减少计算过程中舍入误差对计算解的影响。舍入误差对计算解的影响。第25页/共100页全主元素消去法全主元素消去法 是通过方

26、程或变量次序的交换，使在对角是通过方程或变量次序的交换，使在对角线位置上获得绝对值尽可能大的系数作为线位置上获得绝对值尽可能大的系数作为 ，称这样的称这样的 为主元素。尽管它的算法更稳为主元素。尽管它的算法更稳定，但计算量较大，实际应用中大多数使用列定，但计算量较大，实际应用中大多数使用列主元素消去法即可满足需要。主元素消去法即可满足需要。 )(kkka)(kkka第26页/共100页不是按列选主元素，而是在全体待选系数中选取，则得不是按列选主元素，而是在全体待选系数中选取，则得全主元素法。全主元素法。例例3.3 用用全主元素法解下列线组全主元素法解下列线组 10 x1 - 19x2 - 2x

27、3=3 (1)-20 x1 +40 x2 + x3 =4 (2) x1 + 4x2 + 5x3=5 (3)n解：选择所有系数中绝对值最大的解：选择所有系数中绝对值最大的40作为作为主主元素，交换第一、二行和交换第一、二列使元素，交换第一、二行和交换第一、二列使该主元素位于对角线的第一个位置上，得该主元素位于对角线的第一个位置上，得40 x2 - 20 x1 + x3 =4 (4)-19x2+10 x1 - 2x3=3 (5) 4x2+ x1 +5x3=5 (6)记笔记记笔记第27页/共100页计算计算m21=-19/40，m31=4/40(5)- m21(4), (6)- m31(4) 消去消

28、去x2 得得 0.5x1 1.525 x3 =4.9 (7) 3x1 + 4.9 x3 =4.6 (8)选为主元素选为主元素 4.9 x3 + 3x1=4.6 (9)1.525 x3 +0.5x1=4.9 (10)计算计算m32， (10)- m32(9)消去消去x2得得1=6. 33161 (11)记笔记记笔记第28页/共100页保留有主元素的方程保留有主元素的方程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.35230第29页/

29、共100页3.2.4.1 列主元素法列主元素法列主元素法就是在待消元的所在列中选取主元，经方程的行交换，置主元素于对列主元素法就是在待消元的所在列中选取主元，经方程的行交换，置主元素于对角线位置后进行消元的方法。角线位置后进行消元的方法。 例例3.4 用用列主元素法解下列线性方程组列主元素法解下列线性方程组 10 x1 - 19x2 - 2x3=3 (1)-20 x1 +40 x2 + x3 =4 (2) x1 + 4x2 + 5x3=5 (3)n解：选择解：选择-20作为该列的作为该列的主元素主元素，-20 x1 +40 x2 + x3 =3 (4) 10 x1 - 19x2 - 2x3=4

30、 (5) x1 + 4x2 + 5x3=5 (6)计算计算m21 =10/-20 m31=1/-20第30页/共100页(5)- m21(4), (6)- m31(4)得得 x2 1.5x3=5 (7)6x2 + 5.05x3=5.2 (8)选选6为主元素为主元素6x2 + 5.05x3=5.2 (9) x2 1.5x3=5 (10)计算计算m32=1/6， (10)- m32(9) 得得3=4.13332 (11)记笔记记笔记第31页/共100页保留有主元素的方程保留有主元素的方程 -20 x1 +40 x2 + x3 =4 (4) 6x2 + 5.05x3 =5.2 (9) -2.3416

31、8x3=4.13332 (11)进行回代进行回代x3 =-1.76511x2=2.35230 x1=4.41634记笔记记笔记 列选主元素的计算方法与高斯消去法完全一样列选主元素的计算方法与高斯消去法完全一样, ,不同的是在每步消元之前要按列选出主元不同的是在每步消元之前要按列选出主元第32页/共100页例例3.5 3.5 用矩阵的初等行变换求解解方程组用矩阵的初等行变换求解解方程组 754217743322321321321xxxxxxxxx 解解: : 用矩阵的初等行变换求解用矩阵的初等行变换求解, ,对增广矩阵对增广矩阵 ( (下面带下划线元素为主元素下面带下划线元素为主元素) ) 第3

32、3页/共100页 2 . 12 . 1005 . 65 . 85 . 7017745 . 25 . 05 . 105 . 65 . 85 . 7017745 . 65 . 85 . 705 . 25 . 05 . 101774754233221774754217743322232313121251_2121_) 1 (rrrrrrrrrrbAA第34页/共100页3.2.5 3.2.5 高斯高斯- -约当（约当（Jordan）消去法）消去法 高斯消去法有消元和回代两个过程，消去高斯消去法有消元和回代两个过程，消去的是对角线下方的元素。当对消元过程稍加改的是对角线下方的元素。当对消元过程稍加改变

33、便可使方程组变便可使方程组 化为对角阵化为对角阵 bAx )()(2)(121111nnnnnbbbxxx（）（） 这时求解就不需要回代了这时求解就不需要回代了, ,这种将主元素化为这种将主元素化为1,1,并用主元将其所在列的冗余元素全都消为并用主元将其所在列的冗余元素全都消为0,0,即即消去对角线上方与下方的元素消去对角线上方与下方的元素, ,这种方法称为这种方法称为高斯高斯-约当消去法约当消去法,这时等号右端即为方程组的解这时等号右端即为方程组的解第35页/共100页例例3.6 3.6 用高斯用高斯- -约当约当(Jordan)(Jordan)消去法求方程组的解消去法求方程组的解 1202

34、21321321321xxxxxxxxx解解 方程组相应的增广矩阵方程组相应的增广矩阵 111202211111111102211112列选主元列选主元5 . 15 . 05 . 105 . 05 . 15 . 205 . 05 . 05 . 012 . 14 . 0002 . 06 . 0104 . 08 . 0013100201020013, 2, 2321xxx故得故得 第36页/共100页定理定理3.4 3.4 设设A A为非奇异矩阵，方程组为非奇异矩阵，方程组AX = I的的增广矩阵为增广矩阵为 C = = A A I I ，如果对，如果对C应用高斯应用高斯- -约当消去法化为约当消

35、去法化为 I I B B ，则，则 = =B。例例3.7 3.7 用高斯用高斯- -约当（约当（JordanJordan）消去法）消去法求求 1A563452231A的逆矩阵的逆矩阵 1A第37页/共100页解解 C = = A A I I = = 1005630104520012311031300120100012311331000120100352011331000120102310011330122311A第38页/共100页3.3 矩阵三角分解法矩阵三角分解法 矩阵三角分解法是高斯消去法解线性方程组的一矩阵三角分解法是高斯消去法解线性方程组的一种变形解法种变形解法 3.3.1 3.3.

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

37、33) 2(2) 2(23) 2(22) 1 (1) 1 (13) 1 (12) 1 (1121323121,1111nnnnnnnnaaaaaaaaaaUmmmmmLLUaaaaaaaaaaaaaaaaAnnnnnnnn321333323122322211131211其中其中第40页/共100页方程组方程组Ax=b的系数矩阵的系数矩阵A经过顺序消元逐步化经过顺序消元逐步化为上三角型为上三角型A(n),相当于用一系列初等变换左乘相当于用一系列初等变换左乘A的结果。事实上，第的结果。事实上，第1列消元将列消元将A(1)=A化为化为A(2)，若令：，若令：10000100010001131211n

38、mmmL), 3 , 2(,) 1 (11) 1 (11niaamii则根据距阵左乘有则根据距阵左乘有L1A(1)=A(2)第41页/共100页第第2列消元将列消元将A(2)化为化为A(3)，若令：，若令：1000010001000012322nmmL), 4 , 3(,)2(22)2(22niaamii经计算可知经计算可知 L2A(2)=A(3),依此类推依此类推,一般有一般有LkA(k)=A(k+1)11111,1nkkkkmmL第42页/共100页mi1= a(1) i1/ a(1) 11 i=2,3,n于是矩阵于是矩阵 经过消元化为上三角阵经过消元化为上三角阵 的过程可表示为的过程可表

39、示为上述矩阵上述矩阵 是一类初等矩阵是一类初等矩阵, ,它们都是单位下三角阵，且其逆矩阵也是单位它们都是单位下三角阵，且其逆矩阵也是单位下三角阵下三角阵, ,只需将只需将 改为改为 , ,就得到就得到 。即。即 ) 1 (AA)(nA)(1221nnnAALLLL) 1, 2 , 1(nkLkikm), 2, 1(nkkimik1kL11111, 11nkkkkmmL第43页/共100页于是有于是有 LUULLLALLLAnnn)()(111211)(111211)() 3 (3) 3 (33) 2(2) 2(23) 2(22) 1 (1) 1 (13) 1 (12) 1 (112132312

40、1,1111nnnnnnnnaaaaaaaaaaUmmmmmL其中其中 第44页/共100页L L为由乘数构成的单位下三角阵，为由乘数构成的单位下三角阵，U U为上三角阵，为上三角阵，由此可见，在由此可见，在 的条件下，的条件下，高斯消去法实质上是将方程组的系数矩阵高斯消去法实质上是将方程组的系数矩阵A A分解分解为两个三角矩阵的乘积为两个三角矩阵的乘积A=LUA=LU。这种把非奇异矩阵。这种把非奇异矩阵A A分解成一个下三角矩阵分解成一个下三角矩阵L L和一个上三角矩阵和一个上三角矩阵U U的的乘积称为矩阵的三角分解，又称乘积称为矩阵的三角分解，又称LULU分解。分解。 显然，如果显然，如果

41、 , ,由行列式由行列式的性质知，方程组系数矩阵的性质知，方程组系数矩阵A A的前的前n-1n-1个顺序主子个顺序主子矩阵矩阵 非奇异，即顺序主子非奇异，即顺序主子式不等于零，即式不等于零，即) 1, 2 , 1(0)(nkakkk) 1, 2 , 1(0)(nkakkk)1, 2, 1(nkAk第45页/共100页0)det()1(111 aA), 3 , 2(0)det()()2(22)1(11kiaaaAiiii其中其中 iiiiiaaaaAaA1111111),(（A A的主子阵）的主子阵） 反之反之, ,可用归纳法证明可用归纳法证明, ,如果如果A A的顺序主子式的顺序主子式 ),

42、2 , 1(0)det()()2(22)1(11kiaaaAiiii则则 ), 2 , 1(0)(kiaiii于是得到下述定理：于是得到下述定理： 第46页/共100页定理定理3.5 3.5 设设 。如果。如果A顺序各阶主子式顺序各阶主子式, , , ,则则A可惟一地分解成可惟一地分解成 一个单位下三角阵一个单位下三角阵L和一个非奇异的上三角和一个非奇异的上三角阵阵U的乘积。的乘积。证：由于证：由于A A各阶主子式不为零各阶主子式不为零, ,则消元过程能则消元过程能进行到底进行到底, , 前面已证明将方程组的系数矩阵前面已证明将方程组的系数矩阵A A用初等变换的方法分解成两个三角矩阵的乘用初等

43、变换的方法分解成两个三角矩阵的乘积积A=LUA=LU的过程。的过程。 现仅证明分解的惟一性。现仅证明分解的惟一性。 设设A A有两种有两种LULU分解分解 nnRA) 1, 2 , 1(0)det(niAiULLUA其中其中 为单位下三角阵，为单位下三角阵， 为上三角阵为上三角阵 A A的行列式的行列式 均为非奇异矩阵均为非奇异矩阵, ,有有上式两边左边同乘上式两边左边同乘 ，右边同乘，右边同乘 得得上式左边为单位下三角阵上式左边为单位下三角阵, ,右边为上三角阵右边为上三角阵, ,故应为故应为单位阵单位阵, ,即即 惟一性得证。惟一性得证。 LL,UU ,ULULA, 0ULLU 1L1U1

44、1UULLUULL,第47页/共100页 把把A分解成一个单位上三角阵分解成一个单位上三角阵L和一个下和一个下三角阵三角阵U的乘积称为的乘积称为杜利特尔（杜利特尔（Doolittle）分解分解。其中其中 nnnnnnuuuuuuUlllL222112112121,111第48页/共100页若把若把A分解成一个下三角阵分解成一个下三角阵L和一个单位上和一个单位上三角阵三角阵U的乘积称为的乘积称为克克洛特分解洛特分解Crout） 其中其中 111,211221222111nnnnnnuuuUllllllL第49页/共100页3.3.2 用三角分解法解方程组用三角分解法解方程组 求求解线性方程组解线

45、性方程组Ax=b时时,先对非奇异矩阵先对非奇异矩阵A进行进行LU分解使分解使A=LU，那么方程组就化为，那么方程组就化为 LU x=b从而使问题转化为求解两个简单的的三角方从而使问题转化为求解两个简单的的三角方程组程组 L y=b 求解求解 y U x=y 求解求解 x这就是求解线性方程组的三角分解法的基本这就是求解线性方程组的三角分解法的基本思想。下面只介绍杜利特尔（思想。下面只介绍杜利特尔（Doolittle）分）分解法。解法。设设A=LU为为第50页/共100页nnnnnnnnnnnuuuuuulllaaaaaaaaa2221121121212122221111111111 由矩阵乘法规

46、则由矩阵乘法规则niuaii, 2 , 111niulaii, 3 , 21111 由此可得由此可得U的第的第1行元素和行元素和L的第的第1列元素列元素niauii, 2 , 111niualii,3 ,21111第51页/共100页 再确定再确定U的第的第k行元素与行元素与L的第的第k列元素列元素, ,对对于于k=2,3, ,n计算：计算： 计算计算U的第的第k行元素行元素 11krrjkrkjkjulau（j=k,k+1,j=k,k+1,n,n） 计算计算L L的第的第k k列元素列元素 kkkrrkirikikuulal11（i=k,k+1,i=k,k+1,n,n） nnnnnnnnnn

47、nuuuuuulllaaaaaaaaa2221121121212122221111111111第52页/共100页利用上述计算公式便可逐步求出利用上述计算公式便可逐步求出U与与L的各元素的各元素求解求解 Ly=b , Ly=b , 即计算即计算: : 1111),3 ,2(ikkikiiniylbyby 求解求解 Ux=y , Ux=y , 即计算：即计算： )1 ,2, 1(1niuxuyxuyxiinikkikiinnnn第53页/共100页 显然显然, 当当 时时, 解解Ax=b直接三角分解法计算才能完成。设直接三角分解法计算才能完成。设A为非奇异矩阵为非奇异矩阵, 当当 时计算将中断或

48、者时计算将中断或者当当 绝对值很小时，按分解公式计算可绝对值很小时，按分解公式计算可能引起舍入误差的积累，因此可采用与列能引起舍入误差的积累，因此可采用与列主元消去法类似的方法，对矩阵进行行交主元消去法类似的方法，对矩阵进行行交换，则再实现矩阵的三角分解。换，则再实现矩阵的三角分解。 用直接三角分解法解用直接三角分解法解Ax=b大约需要大约需要 次乘除法。次乘除法。 ), 2 , 1(0nkukk0kkukku3/3n第54页/共100页例例3.8 用三角分解法解方程组用三角分解法解方程组 542631531321321xxx332322131211323121111631531321uuuu

49、uulll113213121131211lluuu121312212222ulau231513212323ulau11/)213(/)(2212313232uulal121316233213313333ululau121321111111UL求解求解 Ly=b 得得 y= 2，2，1T 求解求解 Ux=y 得得 x= -1，0，1 T所以方程组的解为所以方程组的解为 101321xxx第55页/共100页3.4 平方根法平方根法 工程实际计算中工程实际计算中, ,线性方程组的系数矩阵线性方程组的系数矩阵常常具有对称正定性，其各阶顺序主子式及常常具有对称正定性，其各阶顺序主子式及全部特征值均大于

50、全部特征值均大于0。矩阵的这一特性使它的。矩阵的这一特性使它的三角分解也有更简单的形式，从而导出一些三角分解也有更简单的形式，从而导出一些特殊的解法，如平方根法与改进的平方根法。特殊的解法，如平方根法与改进的平方根法。 定理定理3.6 3.6 设设A A是正定矩阵，则存在惟一的是正定矩阵，则存在惟一的对角元素均为正数的下三角阵对角元素均为正数的下三角阵L L，使，使A=LLTA=LLT证：因证：因A A是正定矩阵是正定矩阵, A, A的顺序主子式的顺序主子式 i i0, i=1,2,0, i=1,2,n ,n 因此存在惟一的分解因此存在惟一的分解 A=LU A=LU 第56页/共100页L是单

51、位下三角阵是单位下三角阵, U是上三角阵是上三角阵, 将将U再分解再分解 01,1,111111122211111DUuuuuuuuuunnnnnnn其中其中D为对角阵为对角阵, U0为单位上三角阵，于是为单位上三角阵，于是 A = L U = L D U0 又又 A = AT = U0TD LT由分解惟一性由分解惟一性, 即得即得 U0T=L A=L D LT 第57页/共100页nnuuuD2211记记 又因为又因为det(Ak)0,(k=1,2,n), 故故于是对角阵于是对角阵D还可分解还可分解 ), 2 , 1( , 0niuii2121221122112211DDuuuuuuuuuD

52、nnnnnnTTTTLLLDLDLDLDLDLA1121212121)(其中其中 为下三角阵为下三角阵, ,令令L=LL=L1 1，定理得证。，定理得证。 211LDL 第58页/共100页将将A=LLT展开，写成展开，写成 nnnnnnnnnnnnnllllllllllllaaaaaaaaa22212111212221112122221111111按矩阵乘法展开，可逐行求出分解矩阵按矩阵乘法展开，可逐行求出分解矩阵L L的元素，计的元素，计算公式是对于算公式是对于i=1,2,i=1,2,n,n 21112)(ikikiiiilaliiikikjkjijilllal11j=i+1, i+2,n

53、 这一方法称为这一方法称为平方根法平方根法,又称又称乔累斯基乔累斯基(Cholesky)分分解解,它所需要的乘除次数约它所需要的乘除次数约 为数量级为数量级, ,比比LU分解分解节省近一般的工作量。节省近一般的工作量。 361n第59页/共100页例例3.9 3.9 平方根法求解方程组平方根法求解方程组 7851102021211321xxx解解: : 因方程组系数矩阵对称正定因方程组系数矩阵对称正定, ,设设A= ,A= ,即：即： TLL3332223121113332312221111102021211llllllllllll212, 111, 11131311121211111lall

54、alal1122212222lal212102221313232lllal344112322313333llal322111L由由Ly=bLy=b解得解得 3, 3, 5321yyy由由 解得解得 yxLT1, 5, 2321xxx 由此例可以看出，平方根法解正定方程组的缺由此例可以看出，平方根法解正定方程组的缺点是需要进行开方运算。为避免开方运算，我们改点是需要进行开方运算。为避免开方运算，我们改用单位三角阵作为分解阵，即把对称正定矩阵用单位三角阵作为分解阵，即把对称正定矩阵A分分解成解成 TLDLA 的形式，其中的形式，其中 第60页/共100页ndddD21为对角阵，而为对角阵，而 11

55、11321323121nnnllllllL是单位下三角阵是单位下三角阵, ,这里分这里分解公式为解公式为 11211, 2 , 11, 2 , 1/)(ikikkiiijkjjkikkijijnildadijdlldal第61页/共100页据此可逐行计算据此可逐行计算 运用这种矩阵分解方法运用这种矩阵分解方法, ,方程组方程组Ax=bAx=b即即可归结为求解两个上三角方程组可归结为求解两个上三角方程组 332312211dlldldbxDLLT)(bLy bDxLT1和和其计算公式分别为其计算公式分别为 11,2, 1ikkikiiniylby和和 nikkkiiiinnixldyx11 ,

56、1,/求解方程组的上述算法称为改进的平方根法。这种求解方程组的上述算法称为改进的平方根法。这种方法总的计算量约为方法总的计算量约为 ，即仅为高斯消去法计，即仅为高斯消去法计算量的一半。算量的一半。 6/3n第62页/共100页3.5 追赶法追赶法在数值计算中在数值计算中, ,有一种系数矩阵是三对角方程组有一种系数矩阵是三对角方程组 nnnnnnnnnfffffxxxxxbacbacbacbacb1321132111133322211简记为简记为Ax=f,AAx=f,A满足条件满足条件 （1 1）（2 2）（3 3）011 cb)1, 3 , 2, 0(nicacabiiiii0nnab第63页

57、/共100页 用归纳法可以证明，满足上述条件的三对角用归纳法可以证明，满足上述条件的三对角线性方程组的系数矩阵线性方程组的系数矩阵A非奇异，所以可以利用矩非奇异，所以可以利用矩阵的直接三角分解法来推导解三对角线性方程组阵的直接三角分解法来推导解三对角线性方程组的计算公式，用克洛特分解法，将的计算公式，用克洛特分解法，将A分解成两个三分解成两个三角阵的乘积，设角阵的乘积，设A=LU 11112122111122211nnnnnnnnuuulalalbacbacbacb按乘法展开按乘法展开 1,2, 111111niluabulclbiiiiiii1, 2 , 1/11111niuabllcubl

58、iiiiiiinnluulul12211则可计算则可计算 可依次计算可依次计算 当，当， 由上式可惟由上式可惟一确定一确定L和和U。 0il第64页/共100页例例3.9 用追赶法求解三对角方程组用追赶法求解三对角方程组 501352242231124321xxxx解解 21211111lcubl54252221222lcuuabl565123332333lcuuabl253444uabl16515412112525122251252242231121, 5 . 12321222111lyafylfy1,654344432333lyafylyafy0, 1433344xuyxyx2, 1211

59、13222xuyxxuyx由由Ly=f 解出解出y又由又由Ux=y解出解出x 第65页/共100页记笔记记笔记 为了研究线性方程组近似解的误差估计为了研究线性方程组近似解的误差估计和迭代法的收敛性和迭代法的收敛性, 有必要对向量及矩阵的有必要对向量及矩阵的“大小大小”引进某种度量引进某种度量-范数的概念。向量范范数的概念。向量范数是用来度量向量长度的数是用来度量向量长度的,它可以看成是二、它可以看成是二、三维解析几何中向量长度概念的推广。用三维解析几何中向量长度概念的推广。用Rn表示表示n维实向量空间。维实向量空间。第66页/共100页记笔记记笔记定义定义3.2 对任一向量对任一向量X Rn,

60、 按照一定规则确定一按照一定规则确定一个实个实数与它对应数与它对应, 该实数记为该实数记为|X|, 若若|X|满足下面满足下面三个三个性质性质:(1) |X| 0；|X|=0当且仅当当且仅当X=0；(2) 对任意实数对任意实数 ， | X|=| | |X|；(3) 对任意向量对任意向量Y Rn，|X+Y| |X|+|Y| 则称该实数则称该实数|X|为向量为向量X的的范数范数第67页/共100页记笔记记笔记|max|,.,|,max|)(.|.|X|12121122222121211ininniinniinxxxxXxxxxXxxxx2x第68页/共100页 当不需要指明使用哪一种向量范数时，就