数值分析－线性代数方程组的直接解法.pptx

《数值分析－线性代数方程组的直接解法.pptx》由会员分享，可在线阅读，更多相关《数值分析－线性代数方程组的直接解法.pptx（108页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、3.1引言引言 在工程技术、自然科学和社会科学中，经常在工程技术、自然科学和社会科学中，经常遇到的许多问题最终都可归结为解线性方程组，遇到的许多问题最终都可归结为解线性方程组，如电学中网络问题、用最小二乘法求实验数据的如电学中网络问题、用最小二乘法求实验数据的曲线拟合问题，工程中的三次样条函数的插值问曲线拟合问题，工程中的三次样条函数的插值问题，经济运行中的投入产出问题以及大地测量、题，经济运行中的投入产出问题以及大地测量、机械与建筑结构的设计计算问题等等，都归结为机械与建筑结构的设计计算问题等等，都归结为求解线性方程组或非线性方程组的数学问题。因求解线性方程组或非线性方程组的数学问题。因此线

2、性方程组的求解对于实际问题是极其重要的。此线性方程组的求解对于实际问题是极其重要的。第第3 3章章解线性方程组的直接方法解线性方程组的直接方法第1页/共108页引例引例:设有电源及一些电阻组成的简单电路，求各环设有电源及一些电阻组成的简单电路，求各环路电流。路电流。AR1R2R3R4R5R6E2E1E3BCDEFGHI1I2I3解解:设设I1,I2,I3为图示为图示的环路电流的环路电流,对每一个对每一个环路环路,利用利用克希霍夫定克希霍夫定律律在任何一个在任何一个闭合回路中闭合回路中,各电动势的代数和等于各电阻上电压降各电动势的代数和等于各电阻上电压降的代数和的代数和第2页/共108页AR1R

3、2R3R4R5R6E2E1E3BCDEFGHI1I2I3对环路对环路ABEF：UAB+UBE+UEF=E1R1IAB+R4IBE+R5IEF=E1再用环路电流代替支路电流，即再用环路电流代替支路电流，即IAB=I1，IBE=I1-I2，IEF=I1-I3利用欧姆利用欧姆定律定律式式为为第3页/共108页AR1R2R3R4R5R6E2E1E3BCDEFGHI1I2I3将将式代入式代入,即得环路电流即得环路电流I1,I2,I3所满足的代数方程所满足的代数方程(R1+R4+R5)I1-R4I2R5I3=E1同理同理,对环路对环路BCDE及环路及环路FDGH可得方程：可得方程：-R4+（R2+R4+R

4、6)I2-R6I3=E2-R5I1-R6I2+(R2+R4+R6)I3=E3第4页/共108页或写为矩阵形式即得到环路电流或写为矩阵形式即得到环路电流I1,I2,I3所满足所满足的线性方程组：的线性方程组：(R1+R4+R5)-R4-R5I1E1-R4(R2+R4+R6)-R6I2=E2-R5-R6(R3+R5+R6)I3E3解上述线性方程组，即求得环路电流解上述线性方程组，即求得环路电流I I1 1,I,I2 2,I,I3 3 在工程实际问题中产生的线性方程组，其系数在工程实际问题中产生的线性方程组，其系数矩阵大致有两种：一种是低阶稠密矩阵（这种矩阵矩阵大致有两种：一种是低阶稠密矩阵（这种矩

5、阵元素都存储在计算机的存储器中元素都存储在计算机的存储器中););另一类是大型稀另一类是大型稀疏矩阵疏矩阵(此类矩阵阶数高此类矩阵阶数高,零元素较多零元素较多,压缩存储）。压缩存储）。第5页/共108页第第3章章解线性方程组的直接法解线性方程组的直接法 常见的线性方程组是方程个数和未知量个常见的线性方程组是方程个数和未知量个数相同的数相同的n阶线性方程组，一般形式为阶线性方程组，一般形式为简记为简记为Ax=b，其中，其中(3.1)一般一般b0,当系数矩阵当系数矩阵A非奇异非奇异(即即detA0)时，方程组（时，方程组（3.1）有惟一解。）有惟一解。第6页/共108页线性方程组的数值解法一般有两

6、类：线性方程组的数值解法一般有两类：1.直接法：就是经过有限步算术运算，可求得直接法：就是经过有限步算术运算，可求得方程组精确解的方法（若计算过程中没有舍方程组精确解的方法（若计算过程中没有舍入误差），如克莱姆法则就是一种直接法，入误差），如克莱姆法则就是一种直接法，直接法中具有代表性的算法是高斯直接法中具有代表性的算法是高斯(Gauss)消去法。消去法。2.迭代法迭代法:(第四章介绍）就是用某种极限过第四章介绍）就是用某种极限过程去逐步逼近线性方程组的精确解的方法。程去逐步逼近线性方程组的精确解的方法。也就是也就是从解的某个近似值出发，通过构造一从解的某个近似值出发，通过构造一个无穷序列去逼

7、近精确解的方法。个无穷序列去逼近精确解的方法。(一般有一般有限步内得不到精确解限步内得不到精确解)第7页/共108页3.2解线性方程组的直接法（高斯消去法）解线性方程组的直接法（高斯消去法）高斯消去法的基本思想高斯消去法的基本思想先用一个简单实例来说明先用一个简单实例来说明Gauss法的基本思想法的基本思想例例3.1 3.1 解线性方程组解线性方程组 解解:该方程组的求解过程实际上是将中学学过的消该方程组的求解过程实际上是将中学学过的消元法标准化元法标准化,将一个方程乘或除以某个常数将一个方程乘或除以某个常数,然后将然后将两个方程相加减两个方程相加减,逐步减少方程中的未知数逐步减少方程中的未知

8、数,最终使最终使每个方程只含有一个未知数每个方程只含有一个未知数,从而得出所求的解。从而得出所求的解。整个过程分为消元和回代两个部分。整个过程分为消元和回代两个部分。第8页/共108页（1）消元过程）消元过程第第1步步:将方程将方程乘上乘上(-2)加到方程加到方程上去上去,将将方程方程乘上乘上 加到方程加到方程上去上去,这样就消去这样就消去了第了第2、3个方程的个方程的 项项,于是就得到等价方程于是就得到等价方程组组第9页/共108页第第2步：将方程步：将方程乘上乘上 加到方程加到方程上去，上去，这样就消去了第这样就消去了第3个方程的个方程的 项，于是就得到项，于是就得到等价方程组等价方程组这

9、样，消元过程就是把原方程组化为上三角这样，消元过程就是把原方程组化为上三角形方程组，其系数矩阵是上三角矩阵。形方程组，其系数矩阵是上三角矩阵。（2）回代过程）回代过程回代过程是将上述三角形方程组自下而上求回代过程是将上述三角形方程组自下而上求解，从而求得原方程组的解：解，从而求得原方程组的解：第10页/共108页前述的消元过程相当于对原方程组前述的消元过程相当于对原方程组 的增广矩阵进行下列变换的增广矩阵进行下列变换(表示增广矩阵的第表示增广矩阵的第 行）行）同样可得到与原方程同样可得到与原方程组等价的方程组组等价的方程组第11页/共108页 由此看出由此看出,高斯消去法解方程组基本思想是设法

10、高斯消去法解方程组基本思想是设法消去方程组的系数矩阵消去方程组的系数矩阵A的主对角线下的元素的主对角线下的元素,而将而将Ax=b化为等价的上三角形方程组化为等价的上三角形方程组,然后再通过回代然后再通过回代过程便可获得方程组的解。换一种说法就是用矩阵过程便可获得方程组的解。换一种说法就是用矩阵行的初等变换将原方程组系数矩阵化为上三角形矩行的初等变换将原方程组系数矩阵化为上三角形矩阵阵,而以上三角形矩阵为系数的方程组的求解比较简而以上三角形矩阵为系数的方程组的求解比较简单单,可以从最后一个方程开始可以从最后一个方程开始,依次向前代入求出未依次向前代入求出未知变量知变量 这种求解上三角方程组的方这

11、种求解上三角方程组的方法称为法称为回代回代,通过一个方程乘或除以某个常数通过一个方程乘或除以某个常数,以及以及将两个方程相加减将两个方程相加减,逐步减少方程中的变元数逐步减少方程中的变元数,最终最终将方程组化成上三角方程组将方程组化成上三角方程组,一般将这一过程称为一般将这一过程称为消消元元,然后再回代求解。然后再回代求解。通常把按照先消元通常把按照先消元,后回代两个步骤求解线性后回代两个步骤求解线性方程组的方法称为方程组的方法称为高斯高斯（Gauss）消去法。消去法。第12页/共108页高斯消去法算法构造高斯消去法算法构造 我们知道我们知道,线性方程组线性方程组(3.1)用矩阵形式表示用矩阵

12、形式表示为为 (3.3)解线性方程组（解线性方程组（3.1）的高斯（）的高斯（Gauss）消去法的消元）消去法的消元过程就是对过程就是对(3.3)的增广矩阵进行行初等变换。将例的增广矩阵进行行初等变换。将例3.1中解三阶线性方程组的消去法推广到一般的中解三阶线性方程组的消去法推广到一般的 阶线性方程组并记阶线性方程组并记则高斯消去法的算法构造归纳为：则高斯消去法的算法构造归纳为：第13页/共108页 消元过程消元过程,高斯消去法的消元过程由高斯消去法的消元过程由n-1步组成：步组成：第第1 1步步 设设 ,把把(3.3)(3.3)中的第一列中元素中的第一列中元素 消为零消为零,令令 用用 乘以

13、第乘以第1 1个方程后加到第个方程后加到第 个方程上去个方程上去,消去消去第第2 2n n个方程的未知数个方程的未知数 ,得到得到 即即其中其中 第14页/共108页第第k步步（k=2,3,n-1）继续上述消元过程，设）继续上述消元过程，设第第k-1次消元已经完成，得到与原方程组等价的次消元已经完成，得到与原方程组等价的方程组方程组记为记为 其中其中第15页/共108页只要只要 ,消元过程就可以进行下去消元过程就可以进行下去,直到直到经过经过n-1n-1次消元之后，消元过程结束，得到与次消元之后，消元过程结束，得到与原方程组等价的上三角形方程组原方程组等价的上三角形方程组,记为记为或者写成或者

14、写成 第16页/共108页即即(3.7)（2）回代过程）回代过程就是对上三角方程组（就是对上三角方程组（3.7）自下而上逐步回代解方）自下而上逐步回代解方程组计算，即程组计算，即第17页/共108页（3 3）高斯消去法的计算步骤：）高斯消去法的计算步骤：消元过程消元过程;设设 计算计算 回代过程回代过程 第18页/共108页(4)(4)高斯消去法流程图高斯消去法流程图，见，见P P4242(5)(5)GaussGauss消去法计算量消去法计算量 消元计算消元计算:aij(k+1)=aij(k)-mikakj(k)(i,j=k+1,k+2,n)第一第一步计算乘数步计算乘数mik,mik=ai1/

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

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

17、变换得到的上三角形方程组的顺序主子式经变换得到的上三角形方程组的顺序主子式 所以能实现高斯消去法求解所以能实现高斯消去法求解 （m=1,2,m=1,2,，n n）第22页/共108页定义定义3.1 3.1 设矩阵设矩阵 每一行对角元素的每一行对角元素的绝对值都大于同行其他元素绝对值之和绝对值都大于同行其他元素绝对值之和 则称则称A A为严格对角占优矩阵。为严格对角占优矩阵。定理定理3.2 3.2 若方程组若方程组 的系数矩阵的系数矩阵A为严为严格对角占优，则用高斯消去法求解时，格对角占优，则用高斯消去法求解时，全全不不为零。第23页/共108页证证:先考察消元过程的第先考察消元过程的第1 1步

18、步,因因A为严格对角占为严格对角占 优优,故故 故故 ,又根据高斯消又根据高斯消 去公式得去公式得 于是于是 再利用方程组的对角占优性再利用方程组的对角占优性,由上式可进一步得由上式可进一步得 又由又由 得得 故有故有 当当A A为严格对角占优时为严格对角占优时,余下的子阵仍是余下的子阵仍是对角占优的，从而又有对角占优的，从而又有 。依次类推全不为。依次类推全不为零。零。定理证毕。定理证毕。第24页/共108页 一般线性方程组使用高斯消去法求解时，一般线性方程组使用高斯消去法求解时，在消元过程中可能会出现在消元过程中可能会出现 的情况，这的情况，这时消去法将无法进行；即使时消去法将无法进行；即

19、使 ，但它的，但它的绝对值很小时，用其作除数，会导致其他元素绝对值很小时，用其作除数，会导致其他元素数量级的严重增长和舍入误差的扩散，将严重数量级的严重增长和舍入误差的扩散，将严重影响计算结果的精度。实际计算时必须避免这影响计算结果的精度。实际计算时必须避免这类情况的发生。主元素消去法就可弥补这一缺类情况的发生。主元素消去法就可弥补这一缺陷。陷。第25页/共108页交换原则：通过方程或变量次序的交交换原则：通过方程或变量次序的交换，使在对角线位置上获得绝对值尽换，使在对角线位置上获得绝对值尽可能大的系数作为可能大的系数作为akk(k)，称这样的，称这样的akk(k)为为主元素主元素，并称使用主

20、元素的消，并称使用主元素的消元法元法为主元素法为主元素法根据主元素选取范围分为：列主元素根据主元素选取范围分为：列主元素法、行主元素法、全主元素法法、行主元素法、全主元素法记笔记高斯主元素消去法高斯主元素消去法第26页/共108页主元素法的意义主元素法的意义例例3.2用高斯消去法求下列方程组的解用高斯消去法求下列方程组的解 解：解：确定乘数确定乘数，再计算系数，再计算系数假设计算在假设计算在4 4位浮点十进值的计算机上求解位浮点十进值的计算机上求解,则有则有这时方程组的实际形式是这时方程组的实际形式是 由此回代解出由此回代解出 ,但这个解不满足原但这个解不满足原方程组方程组,解是错误的。这是因

21、为所用的除数太小解是错误的。这是因为所用的除数太小使得上式在消元过程中使得上式在消元过程中“吃掉吃掉”了下式，解决了下式，解决这个问题的方法之一就是采用列选主元高斯消这个问题的方法之一就是采用列选主元高斯消元法。即按列选绝对值大的系数作为主元素，元法。即按列选绝对值大的系数作为主元素，则将方程组中的两个方程相交换，原方程组变则将方程组中的两个方程相交换，原方程组变为为得到消元后的方程组得到消元后的方程组 第27页/共108页这时这时 因而方程组的实际形式是因而方程组的实际形式是 由此回代解出由此回代解出 ,这个结果是正确的这个结果是正确的 可见用高斯消去法解方程组时可见用高斯消去法解方程组时,

22、小主元可小主元可能导致计算失败能导致计算失败,因为用绝对值很小的数作除因为用绝对值很小的数作除数数,乘数很大乘数很大,引起约化中间结果数量级严重增引起约化中间结果数量级严重增长长,再舍入就使得计算结果不可靠了再舍入就使得计算结果不可靠了,故避免采故避免采用绝对值很小的主元素。以便减少计算过程中用绝对值很小的主元素。以便减少计算过程中舍入误差对计算解的影响。舍入误差对计算解的影响。第28页/共108页全主元素消去法全主元素消去法是通过方程或变量次序的交换，使在对是通过方程或变量次序的交换，使在对角线位置上获得绝对值尽可能大的系数作为角线位置上获得绝对值尽可能大的系数作为 称这样的称这样的 为主元

23、素。尽管它的算法更稳为主元素。尽管它的算法更稳定，但计算量较大，实际应用中大多数使用列定，但计算量较大，实际应用中大多数使用列主元素消去法即可满足需要。主元素消去法即可满足需要。第29页/共108页 全主元素法全主元素法全主元素法全主元素法不是按列选主元素，而是在全体待选系数中选取，则得不是按列选主元素，而是在全体待选系数中选取，则得全主元素法。全主元素法。例例3.3 用用全主元素法解下列线组全主元素法解下列线组10 x1-19x2-2x3=3(1)-20 x1+40 x2+x3=4(2)x1+4x2+5x3=5(3)n解：选择所有系数中绝对值最大的解：选择所有系数中绝对值最大的40作为作为主

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

25、2=-1.525/4.9=-0.31122，(10)-m32(9)消去消去x2得得1.43366x1=6.33161(11)记笔记第31页/共108页保留有主元素的方程保留有主元素的方程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第32页/共108页列主元素法列主元素法列主元素法就是在待消元的所在列中选取主元，经方程的行交换，置主元素于对列主元素法就是在待消元的所在列中选取主元，经方程的行交换，置主元素于对角线位置后进行消元的方法。角线位置后进行消

26、元的方法。例例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=4(4)10 x1-19x2-2x3=3(5)x1+4x2+5x3=5(6)计算计算m21=10/-20=-0.5m31=1/-20=-0.05第33页/共108页(5)-m21(4),(6)-m31(4)得得 x21.5x3=5(7)6x2+5.05x3=5.2(8)选选6为主元素为主元素6x2+5.05x3=5.2(9

27、)x21.5x3=5(10)计算计算m32=1/6=0.16667，(10)-m32(9)得得-2.34168x3=4.13332(11)记笔记第34页/共108页保留有主元素的方程保留有主元素的方程-20 x1+40 x2+x3=4(4)6x2+5.05x3=5.2(9)-2.34168x3=4.13332(11)进行回代进行回代x3=-1.76511x2=2.35230 x1=4.41634记笔记 列选主元素的计算方法与高斯消去法完全一样列选主元素的计算方法与高斯消去法完全一样,不同的是在每步消元之前要按列选出主元不同的是在每步消元之前要按列选出主元第35页/共108页例例3.5 3.5

28、用矩阵的初等行变换求解解方程组用矩阵的初等行变换求解解方程组 解解:用矩阵的初等行变换求解用矩阵的初等行变换求解,对增广矩阵对增广矩阵 (下面带下划线元素为主元素下面带下划线元素为主元素)第36页/共108页第37页/共108页高斯高斯-约当（约当（Jordan）消去法）消去法 高斯消去法有消元和回代两个过程，消去高斯消去法有消元和回代两个过程，消去的是对角线下方的元素。当对消元过程稍加改的是对角线下方的元素。当对消元过程稍加改变便可使方程组变便可使方程组 化为对角阵化为对角阵（3.83.8）这时求解就不需要回代了这时求解就不需要回代了,这种将主元素化为这种将主元素化为1,1,并用主元将其所在

29、列的冗余元素全都消为并用主元将其所在列的冗余元素全都消为0,0,即即消去对角线上方与下方的元素消去对角线上方与下方的元素,这种方法称为这种方法称为高斯高斯-约当消去法约当消去法,这时等号右端即为方程组的解这时等号右端即为方程组的解第38页/共108页例例3.6 3.6 用高斯用高斯-约当约当(Jordan)(Jordan)消去法求方程组的解消去法求方程组的解 解解 方程组相应的增广矩阵方程组相应的增广矩阵 列选主元列选主元故得故得 第39页/共108页定理定理3.4 3.4 设设A A为非奇异矩阵，方程组为非奇异矩阵，方程组AX=I的的增广矩阵为增广矩阵为 C=A A I I ，如果对，如果对

30、C应用高斯应用高斯-约当消去法化为约当消去法化为 I I B B，则，则 =B。例例3.7 3.7 用高斯用高斯-约当（约当（JordanJordan）消去法）消去法求 的逆矩阵的逆矩阵 第40页/共108页解解 C=A A I I =第41页/共108页3.3矩阵三角分解法矩阵三角分解法 矩阵三角分解法是高斯消去法解线性方程组的一矩阵三角分解法是高斯消去法解线性方程组的一种变形解法种变形解法矩阵三角分解原理矩阵三角分解原理 应用高斯消去法解应用高斯消去法解n阶线性方程组阶线性方程组Ax=b,经过经过n步消元之后步消元之后,得出一个等价的上三角型方程组得出一个等价的上三角型方程组A(n)x=b

31、(n),对上三角形方程组用逐步回代就可以求对上三角形方程组用逐步回代就可以求出解来。上述过程可通过矩阵分解来实现。出解来。上述过程可通过矩阵分解来实现。将非奇异阵将非奇异阵A分解成一个下三角阵分解成一个下三角阵L和一个上三和一个上三角阵角阵U的乘积的乘积A=LU称为对称为对矩阵矩阵A A的三角分解，又称的三角分解，又称LU分解分解第42页/共108页其中其中第43页/共108页方程组方程组Ax=b的系数矩阵的系数矩阵A经过顺序消元逐步经过顺序消元逐步化为上三角型化为上三角型A(n),相当于用一系列初等变换左相当于用一系列初等变换左乘乘A的结果。事实上，第的结果。事实上，第1列消元将列消元将A(

32、1)=A化为化为A(2)，若令：，若令：则根据距阵左乘有则根据距阵左乘有L1A(1)=A(2)第44页/共108页第第2列消元将列消元将A(2)化为化为A(3)，若令：，若令：经计算可知经计算可知L2A(2)=A(3),依此类推依此类推,一般有一般有LkA(k)=A(k+1)第45页/共108页mi1=a(1)i1/a(1)11i=2,3,n于是矩阵于是矩阵经过消元化为上三角阵经过消元化为上三角阵的过程可表示为的过程可表示为上述矩阵上述矩阵 是一类初等矩阵是一类初等矩阵,它们都是单位下三角阵，且其逆矩阵也是单位它们都是单位下三角阵，且其逆矩阵也是单位下三角阵下三角阵,只需将只需将 改为改为 ,

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

34、列式由行列式的性质知，方程组系数矩阵的性质知，方程组系数矩阵A A的前的前n-1n-1个顺序主子个顺序主子矩阵矩阵 非奇异，即顺序主子式非奇异，即顺序主子式不等于零，即不等于零，即第48页/共108页其中其中 （A A的主子阵）的主子阵）反之反之,可用归纳法证明可用归纳法证明,如果如果A A的顺序主子式的顺序主子式 则则 于是得到下述定理：于是得到下述定理：第49页/共108页定理定理3.5 3.5 设设 。如果。如果A顺序各阶主子式顺序各阶主子式,则则A可惟一地分解成可惟一地分解成 一个单位下三角阵一个单位下三角阵L和一个非奇异的上三角阵和一个非奇异的上三角阵U的乘积。的乘积。证：由于证：由

35、于A A各阶主子式不为零各阶主子式不为零,则消元过程能则消元过程能进行到底进行到底,前面已证明将方程组的系数矩阵前面已证明将方程组的系数矩阵A A用初等变换的方法分解成两个三角矩阵的乘用初等变换的方法分解成两个三角矩阵的乘积积A=LUA=LU的过程。的过程。现仅证明分解的惟一性。现仅证明分解的惟一性。设设A A有两种有两种LULU分解分解 其中其中 为单位下三角阵，为单位下三角阵，为上三角阵为上三角阵 A A的行列式的行列式 均为非奇异矩阵均为非奇异矩阵,有有上式两边左边同乘上式两边左边同乘 ，右边同乘，右边同乘 得得上式左边为单位下三角阵上式左边为单位下三角阵,右边为上三角阵右边为上三角阵,

36、故应为单故应为单位阵位阵,即即 惟一性得证。惟一性得证。第50页/共108页非奇异矩阵不一定都有非奇异矩阵不一定都有LULU分解把分解把A分解分解,例例:显然显然A A非奇异非奇异,若若A A有有LULU分解分解,则则 比较两边元素得比较两边元素得b=0,ab=1,b=0,ab=1,显然矛盾显然矛盾 故该非奇异矩阵故该非奇异矩阵A A不存在不存在LULU分解分解,所以并所以并非非奇异矩阵都有非非奇异矩阵都有LULU分解分解.原因是原因是A A的顺序主子式的顺序主子式=0.=0.尽管尽管A A是非奇异是非奇异矩阵矩阵,不符合定理要求不符合定理要求.第51页/共108页 把把A分解成一个单位下三角

37、阵分解成一个单位下三角阵L和一个上和一个上三角阵三角阵U的乘积称为的乘积称为杜利特尔杜利特尔（Doolittle）分解分解。其中其中 第52页/共108页用三角分解法解方程组用三角分解法解方程组求求解线性方程组解线性方程组Ax=b时时,先对非奇异矩阵先对非奇异矩阵A进行进行LU分解使分解使A=LU，那么方程组就化为，那么方程组就化为LUx=b从从而而使使问问题题转转化化为为求求解解两两个个简简单单的的的的三三角角方方程组程组Ly=b求解求解yUx=y求解求解x这这就就是是求求解解线线性性方方程程组组的的三三角角分分解解法法的的基基本本思思想想。下下面面只只介介绍绍杜杜利利特特尔尔（Doolit

38、tle）分分解法。解法。设设A=LU为为第53页/共108页若把若把A分解成一个下三角阵分解成一个下三角阵L和一个单位上和一个单位上三角阵三角阵U的乘积称为的乘积称为克克洛特分解洛特分解Crout）其中其中 第54页/共108页由矩阵乘法规则由矩阵乘法规则由此可得由此可得U的第的第1行元素和行元素和L的第的第1列元素列元素第55页/共108页 再再确确定定U的的第第k行行元元素素与与L的的第第k列列元元素素,对对于于k=2,3,n计算：计算：计算计算U的第的第k行元素行元素（j=k,k+1,j=k,k+1,n,n）计算计算L L的第的第k k列元素列元素 （i=k,k+1,i=k,k+1,n,

39、n）第56页/共108页利用上述计算公式便可逐步求出利用上述计算公式便可逐步求出U与与L的各元素的各元素求解求解 Ly=b,Ly=b,即计算即计算:求解求解 Ux=y,Ux=y,即计算：即计算：第57页/共108页显显然然,当当时时,解解Ax=b直直接接三三角角分分解解法法计计算算才才能能完完成成。设设A为为非非奇奇异异矩矩阵阵,当当时时计计算算将将中中断断或或者者当当绝绝对对值值很很小小时时，按按分分解解公公式式计计算算可可能能引引起起舍舍入入误误差差的的积积累累，因因此此可可采采用用与与列列主主元元消消去去法法类类似似的的方方法法，对对矩矩阵阵进进行行行行交交换，则再实现矩阵的三角分解。换

40、，则再实现矩阵的三角分解。用直接三角分解法解用直接三角分解法解Ax=b大约需要大约需要 次乘除法。次乘除法。第58页/共108页例例3.8用三角分解法解方程组用三角分解法解方程组 求解求解Ly=b得得y=2，2，1T 求解求解Ux=y得得x=-1，0，1T所以方程组的解为所以方程组的解为第59页/共108页3.4平方根法平方根法 工程实际计算中工程实际计算中,线性方程组的系数矩阵线性方程组的系数矩阵常常具有对称正定性，其各阶顺序主子式及常常具有对称正定性，其各阶顺序主子式及全部特征值均大于全部特征值均大于0。矩阵的这一特性使它的。矩阵的这一特性使它的三角分解也有更简单的形式，从而导出一些三角分

41、解也有更简单的形式，从而导出一些特殊的解法特殊的解法,如平方根法与改进的平方根法。如平方根法与改进的平方根法。定理定理3.6 3.6 设设A A是正定矩阵，则存在惟一的是正定矩阵，则存在惟一的对角元素均为正数的下三角阵对角元素均为正数的下三角阵L L，使，使A=LLA=LLT T证：因证：因A A是正定矩阵是正定矩阵,A,A的顺序主子式的顺序主子式 i i0,i=1,2,0,i=1,2,n,n 因此存在惟一的分解因此存在惟一的分解 A=LU A=LU 第60页/共108页L是单位下三角阵是单位下三角阵,U是上三角阵是上三角阵,将将U再分解再分解 其中其中D为对角阵为对角阵,U0为单位上三角阵，

42、于是为单位上三角阵，于是A=LU=LDU0又又A=AT=U0TDLT由分解惟一性由分解惟一性,即得即得U0T=LA=LDLT第61页/共108页记记又因为又因为det(Ak)0,(k=1,2,n),故故于是对角阵于是对角阵D还可分解还可分解其中其中 为下三角阵为下三角阵,令令L=LL=L1 1，定理得证。，定理得证。第62页/共108页将将A=LLT展开，写成展开，写成按矩阵乘法展开，可逐行求出分解矩阵按矩阵乘法展开，可逐行求出分解矩阵L L的元素，计的元素，计算公式是对于算公式是对于i=1,2,i=1,2,n,n j=i+1,i+2,n 这一方法称为这一方法称为平方根法平方根法,又称又称乔累

43、斯基乔累斯基(Cholesky)分分解解,它所需要的乘除次数约它所需要的乘除次数约 为数量级为数量级,比比LU分解分解节省近一般的工作量。节省近一般的工作量。第63页/共108页例例3.9 3.9 平方根法求解方程组平方根法求解方程组 解解:因方程组系数矩阵对称正定因方程组系数矩阵对称正定,设设A=,A=,即：即：由由Ly=bLy=b解得解得 由由 解得解得 由此例可以看出，平方根法解正定方程组的缺由此例可以看出，平方根法解正定方程组的缺点是需要进行开方运算。为避免开方运算，我们改点是需要进行开方运算。为避免开方运算，我们改用单位三角阵作为分解阵，即把对称正定矩阵用单位三角阵作为分解阵，即把对

44、称正定矩阵A分分解成解成的形式，其中的形式，其中 第64页/共108页为对角阵，而为对角阵，而 是单位下三角阵是单位下三角阵,这里分这里分解公式为解公式为 第65页/共108页据此可逐行计算据此可逐行计算 运用这种矩阵分解方法运用这种矩阵分解方法,方程组方程组Ax=bAx=b即即可归结为求解两个上三角方程组可归结为求解两个上三角方程组 和和其计算公式分别为其计算公式分别为 和和 求解方程组的上述算法称为改进的平方根法。这种求解方程组的上述算法称为改进的平方根法。这种方法总的计算量约为方法总的计算量约为 ，即仅为高斯消去法计，即仅为高斯消去法计算量的一半。算量的一半。第66页/共108页3.5追

45、赶法追赶法在数值计算中在数值计算中,有一种系数矩阵是三对角方程组有一种系数矩阵是三对角方程组简记为简记为Ax=f,AAx=f,A满足条件满足条件 （1 1）（2 2）（3 3）第67页/共108页第68页/共108页 用归纳法可以证明，满足上述条件的三对角线用归纳法可以证明，满足上述条件的三对角线性方程组的系数矩阵性方程组的系数矩阵A非奇异，所以可以利用矩阵非奇异，所以可以利用矩阵的直接三角分解法来推导解三对角线性方程组的计的直接三角分解法来推导解三对角线性方程组的计算公式，用克洛特分解法，将算公式，用克洛特分解法，将A分解成两个三角阵分解成两个三角阵的乘积，设的乘积，设A=LU 按乘法展开按

46、乘法展开 则可计算则可计算 可依次计算可依次计算 当，当，由上式可惟由上式可惟一确定一确定L和和U。第69页/共108页=y1y2y3f1f2fny1y2ynx1x2xn第70页/共108页例例3.9用追赶法求解三对角方程组用追赶法求解三对角方程组 解解 由由Ly=f 解出解出y又由又由Ux=y解出解出x第71页/共108页开始开始输入数据输入数据c1/b1r1d1/b1y12ibiri-1aiqci/qri(diyi-1ai)/qyii0,使得对任意使得对任意恒有恒有（证（证:略）略）第81页/共108页定理定理3.9 其中其中为向量中的任一种范数。为向量中的任一种范数。证证由于由于 而对于

47、而对于上的任一种上的任一种范数范数,由定理由定理3.7知存在常数知存在常数C1，C2，使，使于是可得于是可得从而定理得证。从而定理得证。第82页/共108页定义定义3.5（矩阵的范数）如果矩阵（矩阵的范数）如果矩阵 的某的某个个非负的实值函数非负的实值函数 ，满足，满足则称则称 是是 上的一个矩阵范数上的一个矩阵范数(或模或模)第83页/共108页矩阵范数的性质可由向量范数定义直接验证矩阵范数的性质可由向量范数定义直接验证。(1)设设A0,x0,使使Ax0,根据向量范数的性根据向量范数的性 质质 Ax 0,所以所以0 x0,使使 Ax=0,则则=0当当A=0时时,第84页/共108页矩阵范数的

48、性质可由向量范数定义直接验证矩阵范数的性质可由向量范数定义直接验证(2)根据向量范数的性质根据向量范数的性质第85页/共108页矩阵范数的性质可由向量范数定义直接验证矩阵范数的性质可由向量范数定义直接验证(3)第86页/共108页矩阵范数定义的另一种方法是矩阵范数定义的另一种方法是这是由于这是由于同样，矩阵范数和向量范数密切相关，向量范数同样，矩阵范数和向量范数密切相关，向量范数有相应的矩阵范数，即有相应的矩阵范数，即第87页/共108页第88页/共108页定义定义3.7（矩阵的谱半径）设（矩阵的谱半径）设的特征的特征值为值为,称称为为A的的谱半径。谱半径。例例 3.12 3.12 计算方阵计

49、算方阵 的三种常用范数的三种常用范数 第89页/共108页例例3.12 3.12 计算方阵计算方阵 的三种范数的三种范数 解解 先计算先计算所以所以 ,从而从而第90页/共108页定理定理3.11设设A为为n阶方阵阶方阵,则对任意矩阵范数则对任意矩阵范数都有都有证证:设设为为A的特征值，的特征值，x是是对应于的特征向对应于的特征向量量,则则x=Ax。两端取范数并依据其性质。两端取范数并依据其性质得得由于由于x0，故，故 ，所以，所以第91页/共108页3.7误差分析误差分析方程组的性态方程组的性态在建立方程组时，其系数往往含有误差在建立方程组时，其系数往往含有误差（如观测误差或计算误差），就是

50、说，所要（如观测误差或计算误差），就是说，所要求解的运算是有扰动的方程组，因此需要研求解的运算是有扰动的方程组，因此需要研究扰动对解的影响。究扰动对解的影响。第92页/共108页例例3.13考察方程组考察方程组 和和上上述述两两个个方方程程组组尽尽管管只只是是右右端端项项有有微微小小扰扰动动,但解大不相同但解大不相同,第第1个方程组的解是个方程组的解是第第2个方程组的解是个方程组的解是。这类方程组。这类方程组称为病态的。称为病态的。第93页/共108页定义定义3.8A或或b的微小变化的微小变化(又称扰动或摄动又称扰动或摄动)引起方程组引起方程组Ax=b解的巨大变化，则称方程组解的巨大变化，则称