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

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

1、会计学1数值分析数值分析(fnx)线性代数方程组的直线性代数方程组的直接解法接解法第一页，共108页。引例引例:设有电源及一些电阻设有电源及一些电阻(dinz)组成的简单电路，组成的简单电路，求各环路电流。求各环路电流。AR1R2R3R4R5R6E2E1E3BCDEFGHI1I2I3解解:设设I1,I2,I3为图示的为图示的环路电流环路电流,对对每一个环路每一个环路,利用克希霍利用克希霍夫定律夫定律(dngl)在任何一个在任何一个闭合回路中闭合回路中,各电动势的代数和等于各电动势的代数和等于(dngy)各电阻上电压各电阻上电压降降的代数和的代数和第2页/共108页第二页，共108页。AR1R2

2、R3R4R5R6E2E1E3BCDEFGHI1I2I3对环路对环路(hun l)ABEF：UAB+UBE+UEF=E1 R1 IAB+R4 IBE+R5 IEF=E1 再用环路电流再用环路电流(dinli)代替支路电流代替支路电流(dinli)，即，即IAB=I1，IBE=I1-I2，IEF=I1-I3 利用利用(lyng)欧姆定律欧姆定律式为式为第3页/共108页第三页，共108页。AR1R2R3R4R5R6E2E1E3BCDEFGHI1I2I3将将式代入式代入,即得环路电流即得环路电流I1,I2,I3所满足所满足(mnz)的的代数方程代数方程 (R1+R4+R5)I1-R4I2 R5I3=

3、E1 同理同理,对环路对环路(hun l)BCDE及环路及环路(hun l)FDGH可得方可得方程：程：-R4+（R2+R4+R6)I2-R6I3=E2-R5I1-R6I2+(R2+R4+R6)I3=E3第4页/共108页第四页，共108页。或写为矩阵形式即得到环路或写为矩阵形式即得到环路(hun l)电流电流I1,I2,I3所满足的线性方程组：所满足的线性方程组：(R1+R4+R5)-R4 -R5 I1 E1 -R4 (R2+R4+R6)-R6 I2 =E2 -R5 -R6 (R3+R5+R6)I3 E3 解上述线性方程组，即求得环路电流解上述线性方程组，即求得环路电流I1,I2,I3I1,

4、I2,I3 在工程实际问题中产生的线性方程组，其系数矩阵在工程实际问题中产生的线性方程组，其系数矩阵大致大致(dzh)(dzh)有两种：一种是低阶稠密矩阵（这种矩阵元有两种：一种是低阶稠密矩阵（这种矩阵元素都存储在计算机的存储器中素都存储在计算机的存储器中););另一类是大型稀疏矩阵另一类是大型稀疏矩阵(此类矩阵阶数高此类矩阵阶数高,零元素较多零元素较多,压缩存储）。压缩存储）。第5页/共108页第五页，共108页。第第3章章 解线性方程组的直接解线性方程组的直接(zhji)法法 常见常见(chn jin)(chn jin)的线性方程组是方程个的线性方程组是方程个数和未知量个数相同的数和未知量

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

6、直接法中具有代表性的算法是高直接法，直接法中具有代表性的算法是高斯斯(Gauss)消去法。消去法。迭代法迭代法:(第四章介绍）就是用某种极限过程第四章介绍）就是用某种极限过程去逐步逼近线性方程组的精确解的方法。去逐步逼近线性方程组的精确解的方法。也就是从解的某个近似值出发，通过构造也就是从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。一个无穷序列去逼近精确解的方法。(一般一般有限步内得不到精确解有限步内得不到精确解)第7页/共108页第七页，共108页。3.2 解线性方程组的直接解线性方程组的直接(zhji)法（高斯消法（高斯消去法）去法）高斯消去法的基本思想高斯消去法的基本思想

7、先用一个简单先用一个简单(jindn)实例来说明实例来说明Gauss法的基法的基本思想本思想例例3.1 解线性方程组解线性方程组 解解:该方程组的求解过程实际上是将中学学过的消该方程组的求解过程实际上是将中学学过的消元法标准化元法标准化,将一个方程乘或除以某个常数将一个方程乘或除以某个常数,然后将两然后将两个个(lin)(lin)方程相加减方程相加减,逐步减少方程中的未知数逐步减少方程中的未知数,最终使每个方程只含有一个未知数最终使每个方程只含有一个未知数,从而得出所求的从而得出所求的解。整个过程分为消元和回代两个解。整个过程分为消元和回代两个(lin)(lin)部分。部分。第8页/共108页

8、第八页，共108页。（1）消元过程）消元过程第第1步步:将方程将方程乘上乘上(-2)加到方程加到方程 上去上去,将将方程方程 乘上乘上 加到方程加到方程 上去上去,这样就消去这样就消去了第了第2、3个方程的个方程的 项项,于是于是(ysh)就得到等就得到等价方程组价方程组 第9页/共108页第九页，共108页。第第2 2步：将方程步：将方程 乘上乘上 加到方程加到方程 上去上去(shng(shng q)q)，这样就消去了第，这样就消去了第3 3个方程的个方程的 项，于是就得到项，于是就得到等价方程组等价方程组 这样，消元过程就是把原方程组化为上三角这样，消元过程就是把原方程组化为上三角形方程组

9、，其系数形方程组，其系数(xsh)(xsh)矩阵是上三角矩矩阵是上三角矩阵。阵。（2）回代过程）回代过程(guchng)回回代代过过程程(guchng)是是将将上上述述三三角角形形方方程程组组自自下而上求解，从而求得原方程组的解：下而上求解，从而求得原方程组的解：第10页/共108页第十页，共108页。前述的消元过程前述的消元过程(guchng)(guchng)相当于对原方程相当于对原方程组组 的增广矩阵的增广矩阵(j zhn)(j zhn)进行下列变换进行下列变换(表示增广矩阵表示增广矩阵(j(j zhn)zhn)的第的第 行）行）同样可得到同样可得到(d do)与原方程与原方程组等价的方程

10、组组等价的方程组 第11页/共108页第十一页，共108页。由此看出由此看出,高斯消去法解方程组基本思想高斯消去法解方程组基本思想是设法消去方程组的系数矩阵是设法消去方程组的系数矩阵A A的主对角线下的主对角线下的元素的元素,而将而将Ax=bAx=b化为等价的上三角化为等价的上三角(snjio)(snjio)形方程组形方程组,然后再通过回代过程便然后再通过回代过程便可获得方程组的解。换一种说法就是用矩阵可获得方程组的解。换一种说法就是用矩阵行的初等变换将原方程组系数矩阵化为上三行的初等变换将原方程组系数矩阵化为上三角角(snjio)(snjio)形矩阵形矩阵,而以上三角而以上三角(snjio)

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

12、消元通常把按照先消元,后回代两个步骤求解线性后回代两个步骤求解线性方程组的方法称为方程组的方法称为(chn wi)(chn wi)高斯高斯（GaussGauss）消去法。）消去法。第12页/共108页第十二页，共108页。高斯高斯(o s)(o s)消去法算法构造消去法算法构造 我们知道我们知道,线性方程组线性方程组(3.1)(3.1)用矩阵形式表示用矩阵形式表示为为 (3.3)解线性方程组（解线性方程组（3.13.1）的高斯（）的高斯（GaussGauss）消去法的消元过程就）消去法的消元过程就是对是对(3.3)(3.3)的增广矩阵进行的增广矩阵进行(jnxng)(jnxng)行初等变换。将

13、例行初等变换。将例3.13.1中解三阶线性方程组的消去法推广到一般的中解三阶线性方程组的消去法推广到一般的 阶线性方程阶线性方程组并记组并记则高斯消去法的算法构造归纳为：则高斯消去法的算法构造归纳为：第13页/共108页第十三页，共108页。消元过程消元过程,高斯消去法的消元过程由高斯消去法的消元过程由n-1n-1步组成步组成(z(z chn)chn)：第第1 1步步 设设 ,把把(3.3)(3.3)中的第一列中元素中的第一列中元素 消为零消为零,令令 用用 乘以第乘以第1 1个方程个方程(fngchng)(fngchng)后加到第后加到第 个方程个方程(fngchng)(fngchng)上去

14、上去,消去消去第第2 2n n个方程个方程(fngchng)(fngchng)的未知数的未知数 ,得到得到 即即 其中其中(qz(qzhnghng)第14页/共108页第十四页，共108页。第第k k步步 （k=2,3,n-1k=2,3,n-1）继续上述）继续上述(shngsh)(shngsh)消消元过程，设第元过程，设第k-1k-1次消元已经完成，得到与原方程次消元已经完成，得到与原方程组等价的方程组组等价的方程组 记为记为 其中其中(qzhng)(qzhng)第15页/共108页第十五页，共108页。只要只要(zhyo),(zhyo),消元过程就可以进行下消元过程就可以进行下去去,直到经过

15、直到经过n-1n-1次消元之后，消元过程结束，次消元之后，消元过程结束，得到与原方程组等价的上三角形方程组得到与原方程组等价的上三角形方程组,记为记为 或者或者(huzh)(huzh)写写成成 第16页/共108页第十六页，共108页。即即(3.7)（2）回代过程）回代过程就就是是对对上上三三角角(snjio)方方程程组组（3.7）自自下下而而上上逐逐步步回回代解方程组计算，即代解方程组计算，即 第17页/共108页第十七页，共108页。（3 3）高斯消去法的计算）高斯消去法的计算(j sun)(j sun)步骤：步骤：消元过程消元过程;设设 计算计算(j(j sun)sun)回代过程回代过程

16、(guchng)(guchng)第18页/共108页第十八页，共108页。(4)(4)高斯高斯(o s)(o s)消去法流程图消去法流程图 ，见，见P42P42(5)Gauss(5)Gauss消去法计算量消去法计算量 消元计算消元计算(j sun):aij(k+1)=aij(k)-mik akj(k)(i,j=k+1,k+2,n)第一第一 步计算步计算(j sun)乘数乘数mik,mik=ai1/a11(i=2,3,n)需要需要n-1次除法运算次除法运算,计算计算(j sun)aij(2）(i,j=2,3,n)需要需要(n-1)2次乘法运算及次乘法运算及(n-1)2次加减法运次加减法运 算算,

17、第19页/共108页第十九页，共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乘除乘除(chngch)法次数：法次数：MD=n(n-1)(2n-1)/6+n(n-1)/2=1/3 n(n2-1)加减法次数：加减法次数：AS=n(n-1)(2n-1)/6第20页/共108页第二十页，共108页。高斯消去法的适用高斯消去法的适用(shyng)(shyng)条件条件 定理定理

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

19、(binhun)(binhun)得到的上三角形方程组的顺序主子式得到的上三角形方程组的顺序主子式 所以所以(suy)(suy)能实现高斯消去法求能实现高斯消去法求解解 （m=1,2,m=1,2,，n n）第22页/共108页第二十二页，共108页。定义定义3.1 3.1 设矩阵设矩阵 每一行对角元素每一行对角元素(yun s)(yun s)的绝对值都大于同行其他元素的绝对值都大于同行其他元素(yun(yun s)s)绝对值之和绝对值之和 则称则称A A为严格对角为严格对角(du jio)(du jio)占优矩占优矩阵。阵。定理定理3.2 3.2 若方程组若方程组 的系数矩阵的系数矩阵A A为严

20、为严格格(yng)(yng)对角占优，则用高斯消去法求解时，对角占优，则用高斯消去法求解时，全不为零。全不为零。第23页/共108页第二十三页，共108页。证证:先考察消元过程的第先考察消元过程的第1 1步步,因因A A为严格对角占为严格对角占 优优,故故 故故 ,又根据高斯消又根据高斯消 去公式去公式(gngsh)(gngsh)得得 于是于是 再利用再利用(lyng)(lyng)方程组的对角占优性方程组的对角占优性,由上式可进一步得由上式可进一步得 又由又由 得得 故有故有 当当A A为严格对角为严格对角(du jio)(du jio)占优时占优时,余下余下的子阵仍是对角的子阵仍是对角(du

21、 jio)(du jio)占优的，从而又有占优的，从而又有 。依次类推全不为零。依次类推全不为零。定理证毕。定理证毕。第24页/共108页第二十四页，共108页。一般线性方程组使用高斯消去法求解时，在消元一般线性方程组使用高斯消去法求解时，在消元过程中可能会出现过程中可能会出现 的情况，这时消去法将无的情况，这时消去法将无法进行；即使法进行；即使 ，但它的绝对值很小时，用其，但它的绝对值很小时，用其作除数，会导致其他元素数量级的严重增长和舍入误作除数，会导致其他元素数量级的严重增长和舍入误差的扩散，将严重影响计算结果的精度。实际计算时差的扩散，将严重影响计算结果的精度。实际计算时必须避免必须避

22、免(bmin)(bmin)这类情况的发生。主元素消去法就这类情况的发生。主元素消去法就可弥补这一缺陷。可弥补这一缺陷。第25页/共108页第二十五页，共108页。n n交换原则：通过方程或变量次序的交换，交换原则：通过方程或变量次序的交换，使在对角线位置上获得使在对角线位置上获得(hud)绝对值绝对值尽可能大的系数作为尽可能大的系数作为akk(k)，称这样的，称这样的akk(k)为主元素，并称使用主元素的为主元素，并称使用主元素的消元法为主元素法消元法为主元素法n n根据主元素选取范围分为：列主元素法、根据主元素选取范围分为：列主元素法、行主元素法、全主元素法行主元素法、全主元素法记笔记记笔记

23、高斯高斯高斯高斯(o s)(o s)(o s)(o s)主元素消去法主元素消去法主元素消去法主元素消去法第26页/共108页第二十六页，共108页。主元素主元素主元素主元素(yun s)(yun s)法的意义法的意义法的意义法的意义例例3.2 用高斯用高斯(o s)消去法求下列方程组消去法求下列方程组的解的解 解：解：确定确定(qudng)乘数乘数 ，再计算，再计算系数系数 假设计算在假设计算在4 4位浮点十进值的计算机上求解位浮点十进值的计算机上求解,则有则有 这时方程组的实际形式是这时方程组的实际形式是 由此回代解出由此回代解出 ,但这个解不满足原方但这个解不满足原方程组程组,解是错误的。

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

25、ji gu)是是正确的正确的 可见用高斯消去法解方程组时可见用高斯消去法解方程组时,小主元可能小主元可能(knng)(knng)导致计算失败导致计算失败,因为用绝对值很小的数作除因为用绝对值很小的数作除数数,乘数很大乘数很大,引起约化中间结果数量级严重增长引起约化中间结果数量级严重增长,再再舍入就使得计算结果不可靠了舍入就使得计算结果不可靠了,故避免采用绝对值很故避免采用绝对值很小的主元素。以便减少计算过程中舍入误差对计算小的主元素。以便减少计算过程中舍入误差对计算解的影响。解的影响。第28页/共108页第二十八页，共108页。全主元素消去法全主元素消去法 是通过方程或变量次序是通过方程或变量

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

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

28、.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为主元素为主元素(yun s)4.9 x3+3x1=4.6 (9)1.525 x3+0.5x1=4.9 (10)计算计算(j sun)m32=-1.525/4.9=-0.31122，(10)-m32(9)消去消去x2得得1.43366x1=6.33161 (11)记笔记记笔记第31页/共108页第三十一页，共108页。保留保留保留保留(b(b oli)oli)有主元素的方程有主元素的方程有主元素的方程有主元素的方程40 x2-20 x1+x

29、3 =4 (4)4.9x3+3x1=4.6 (9)1.43366x1=6.33161 (11)进行进行(jnxng)回代回代x1=4.41634 x3=-1.76511x2=2.35230第32页/共108页第三十二页，共108页。列主元素列主元素列主元素列主元素(yun s)(yun s)法法法法n n列主元素法就是在待消元的所在列主元素法就是在待消元的所在(suzi)列中选取主元，经方程列中选取主元，经方程的行交换，置主元素于对角线位的行交换，置主元素于对角线位置后进行消元的方法。置后进行消元的方法。n n例例3.4 用列主元素法解下列线性用列主元素法解下列线性方程组方程组 10 x1-1

30、9x2-2x3=3 (1)-20 x1+40 x2+x3=4 (2)x1+4x2+5x3=5 (3)n解：选择解：选择-20作为作为(zuwi)该列的主元素，该列的主元素，-20 x1+40 x2+x3=4 (4)10 x1-19x2-2x3=3 (5)x1+4x2+5x3=5 (6)计算计算m21=10/-20=-0.5 m31=1/-20=-0.05第33页/共108页第三十三页，共108页。(5)-m(5)-m21(4),(6)-m(4),(6)-m3131(4)得得得得 x2 1.5x3=5 (7)6x2+5.05x3=5.2 (8)选选6为主元素为主元素(yun s)6x2+5.05

31、x3=5.2 (9)x2 1.5x3=5 (10)计算计算(j sun)m32=1/6=0.16667，(10)-m32(9)得得-2.34168x3=4.13332 (11)记笔记记笔记第34页/共108页第三十四页，共108页。保留保留保留保留(b(b oli)oli)有主元素的方程有主元素的方程有主元素的方程有主元素的方程-20 x1+40 x2+x3 =4 (4)6x2+5.05x3 =5.2 (9)-2.34168x3=4.13332 (11)进行进行(jnxng)回代回代x3=-1.76511x2=2.35230 x1=4.41634记笔记记笔记 列选主元素的计算方法与高斯消去法完

32、全列选主元素的计算方法与高斯消去法完全(wnqun)(wnqun)一样一样,不同的是在每步消元之前要按列选不同的是在每步消元之前要按列选出主元出主元第35页/共108页第三十五页，共108页。例例3.5 3.5 用矩阵的初等用矩阵的初等(chdng)(chdng)行变换求解解方行变换求解解方程组程组 解解:用矩阵的初等行变换求解用矩阵的初等行变换求解(qi ji),(qi ji),对增广矩阵对增广矩阵 (下面带下划线元素为主元素下面带下划线元素为主元素)第36页/共108页第三十六页，共108页。第37页/共108页第三十七页，共108页。高斯高斯(o s)-(o s)-约当（约当（Jorda

33、nJordan）消去法）消去法 高斯消去法有消元和回代两个高斯消去法有消元和回代两个(lin)(lin)过过程，消去的是对角线下方的元素。当对消元过程稍程，消去的是对角线下方的元素。当对消元过程稍加改变便可使方程组加改变便可使方程组 化为对角阵化为对角阵 （3.83.8）这时求解就不需要回代了这时求解就不需要回代了,这种将主元素化为这种将主元素化为1,1,并用并用主元将其所在主元将其所在(suzi)(suzi)列的冗余元素全都消为列的冗余元素全都消为0,0,即消即消去对角线上方与下方的元素去对角线上方与下方的元素,这种方法称为这种方法称为高斯高斯-约当消去法约当消去法,这时等号右端即为方程组的

34、解这时等号右端即为方程组的解第38页/共108页第三十八页，共108页。例例3.6 3.6 用高斯用高斯(o s)-(o s)-约当约当(Jordan)(Jordan)消去法求方程组的解消去法求方程组的解 解解 方程组相应方程组相应(xingyng)(xingyng)的增的增广矩阵广矩阵 列选主元列选主元故得故得 第39页/共108页第三十九页，共108页。定理定理(dngl)3.4 (dngl)3.4 设设A A为非奇异矩阵，方程组为非奇异矩阵，方程组AX=AX=I I的增广矩阵为的增广矩阵为 C=C=A A I I，如果对，如果对C C应用高应用高斯斯-约当消去法化为约当消去法化为 I I

35、 B B，则，则 =B =B。例例3.7 3.7 用高斯用高斯-约当（约当（JordanJordan）消去法求）消去法求 的逆矩阵的逆矩阵(j(j zhn)zhn)第40页/共108页第四十页，共108页。解解 C=A A I I =第41页/共108页第四十一页，共108页。3.3 矩阵矩阵(j zhn)三角分解法三角分解法 矩阵三角分解法是高斯消去法解线性方程组矩阵三角分解法是高斯消去法解线性方程组的一种变形的一种变形(bin xng)(bin xng)解法解法 矩阵三角分解矩阵三角分解(fnji)(fnji)原理原理 应用高斯消去法解应用高斯消去法解n阶线性方程组阶线性方程组Ax=b,经

36、过经过n步消元步消元之后之后,得出一个等价的上三角型方程组得出一个等价的上三角型方程组A(n)x=b(n),对上三角形方程组用逐步回代就可以求出对上三角形方程组用逐步回代就可以求出解来。上述过程可通过矩阵分解来实现。解来。上述过程可通过矩阵分解来实现。将非奇异阵将非奇异阵A分解成一个下三角阵分解成一个下三角阵L和一个上三角阵和一个上三角阵U的乘积的乘积 A=LU 称为对称为对矩阵矩阵A A的三角分解，又称的三角分解，又称LU分解分解第42页/共108页第四十二页，共108页。其中其中(qzhng)第43页/共108页第四十三页，共108页。方程组方程组Ax=b的系数矩阵的系数矩阵A经过顺序消元

37、逐步经过顺序消元逐步(zhb)化为上三角型化为上三角型A(n),相当于用一系列初等变换左乘相当于用一系列初等变换左乘A的结果。事实上，第的结果。事实上，第1列消元将列消元将A(1)=A化为化为A(2)，若，若令：令：则根据则根据(gnj)距阵左乘有距阵左乘有L1A(1)=A(2)第44页/共108页第四十四页，共108页。第第2列消元将列消元将A(2)化为化为A(3)，若令：，若令：经计算可知经计算可知(k zh)L2A(2)=A(3),依此类推依此类推,一般有一般有LkA(k)=A(k+1)第45页/共108页第四十五页，共108页。mi1=a(1)i1/a(1)11 i=2,3,n于是矩阵

38、于是矩阵 经过消元化为上三角阵经过消元化为上三角阵 的过程可表示为的过程可表示为上述矩阵上述矩阵 是一类初等矩阵是一类初等矩阵,它它们们(t men)都都是是单单位位下下三三角角阵阵，且且其其逆逆矩矩阵阵也也是是单单位下三角阵位下三角阵,只需将只需将 改为改为 ,就得到就得到 。即。即 第46页/共108页第四十六页，共108页。于是于是(ysh)(ysh)有有 其中其中(qzhn(qzhng)g)第47页/共108页第四十七页，共108页。L L为由乘数构成的单位下三角阵，为由乘数构成的单位下三角阵，U U为上三角阵，为上三角阵，由此可见，在由此可见，在 的条件的条件(tiojin)(tio

39、jin)下，高斯消去法实质上是将方程组下，高斯消去法实质上是将方程组的系数矩阵的系数矩阵A A分解为两个三角矩阵的乘积分解为两个三角矩阵的乘积A=LUA=LU。这种把非奇异矩阵这种把非奇异矩阵A A分解成一个下三角矩阵分解成一个下三角矩阵L L和和一个上三角矩阵一个上三角矩阵U U的乘积称为矩阵的三角分解，的乘积称为矩阵的三角分解，又称又称LULU分解。分解。显然，如果显然，如果 ,由行列式由行列式的性质知，方程组系数矩阵的性质知，方程组系数矩阵A A的前的前n-1n-1个顺序主个顺序主子矩阵子矩阵 非奇异，即顺序主非奇异，即顺序主子式不等于零，即子式不等于零，即第48页/共108页第四十八页

40、，共108页。其中其中(qzh(qzhng)ng)（A A的主子的主子(zh(zh zi)zi)阵）阵）反之反之,可用归纳法证明可用归纳法证明(zhngmng),(zhngmng),如果如果A A的顺序主的顺序主子式子式 则则 于是得到下述定理：于是得到下述定理：第49页/共108页第四十九页，共108页。定理定理3.5 3.5 设设 。如果。如果A A顺序各阶主子顺序各阶主子(zh(zh zi)zi)式式,则则A A可惟一地分解成可惟一地分解成 一个单位下三角阵一个单位下三角阵L L和一个非奇异的上三角阵和一个非奇异的上三角阵U U的乘积。的乘积。证：由于证：由于A A各阶主子各阶主子(zh

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

42、边为上三角阵右边为上三角阵,故应为单位阵故应为单位阵,即即 惟一性得证。惟一性得证。第50页/共108页第五十页，共108页。非奇异非奇异(qy)(qy)矩阵不一定都有矩阵不一定都有LULU分解把分解把A A分解分解,例例:显然显然A A非奇异非奇异(qy),(qy),若若A A有有LULU分解分解,则则 比较两边元素得比较两边元素得b=0,ab=1,b=0,ab=1,显然矛盾显然矛盾 故该非奇异矩阵故该非奇异矩阵A A不存在不存在LULU分解分解,所以并非所以并非非奇异矩阵都有非奇异矩阵都有LULU分解分解.原因原因(yunyn)(yunyn)是是A A的顺序主子式的顺序主子式=0.=0.尽

43、管尽管A A是非奇异矩阵是非奇异矩阵,不符合定理要求不符合定理要求.第51页/共108页第五十一页，共108页。把把A A分解成一个单位分解成一个单位(dnwi)(dnwi)下三角阵下三角阵L L和和一个上三角阵一个上三角阵U U的乘积称为杜利特尔的乘积称为杜利特尔（DoolittleDoolittle）分解。其中）分解。其中 第52页/共108页第五十二页，共108页。用三角分解法解方程组用三角分解法解方程组 求求解解线线性性方方程程组组Ax=b时时,先先对对非非奇奇异异矩矩阵阵A进进行行LU分分解解使使A=LU，那那么么方方程程组组就就化化为为 LU x=b从从而而使使问问题题转转化化为为

44、求求解解两两个个简简单单的的的的三三角角方方程组程组 L y=b 求解求解 y U x=y 求解求解 x这这就就是是(jish)求求解解线线性性方方程程组组的的三三角角分分解解法法 的的 基基 本本 思思 想想。下下 面面 只只 介介 绍绍 杜杜 利利 特特 尔尔（Doolittle）分解法。设）分解法。设A=LU为为第53页/共108页第五十三页，共108页。若把若把A A分解成一个下三角阵分解成一个下三角阵L L和一个单位上三角阵和一个单位上三角阵U U的乘积称为的乘积称为(chn wi)(chn wi)克洛特分解克洛特分解CroutCrout）其中其中 第54页/共108页第五十四页，共

45、108页。由矩阵乘法由矩阵乘法(chngf)规则规则 由此可得由此可得U的第的第1行元素行元素(yun s)和和L的第的第1列元素列元素(yun s)第55页/共108页第五十五页，共108页。再再确确定定U U的的第第k k行行元元素素与与L L的的第第k k列列元元素素,对对于于(duy)k=2,3,n(duy)k=2,3,n计算：计算：计算计算U U的第的第k k行元素行元素 （j=k,k+1,j=k,k+1,n,n）计算计算(j sun)L(j sun)L的第的第k k列列元素元素 （i=k,k+1,i=k,k+1,n,n）第56页/共108页第五十六页，共108页。利用上述计算公式便

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

47、再再实实现矩阵的三角分解。现矩阵的三角分解。用直接三角分解法解用直接三角分解法解Ax=b大约需要大约需要 次乘除法。次乘除法。第58页/共108页第五十八页，共108页。例例3.8 3.8 用三角用三角(snjio)(snjio)分解法解方程组分解法解方程组 求解求解(qi ji)Ly=b (qi ji)Ly=b 得得 y=y=2 2，2 2，1T 1T 求解求解(qi ji)Ux=y (qi ji)Ux=y 得得 x=-1 x=-1，0 0，1 T1 T所以方程组的解为所以方程组的解为 第59页/共108页第五十九页，共108页。3.4 平方根法平方根法 工程实际计算中工程实际计算中,线性方

48、程组的系数矩阵常常线性方程组的系数矩阵常常具有对称正定性，其各阶顺序主子式及全部特具有对称正定性，其各阶顺序主子式及全部特征值均大于征值均大于0。矩阵的这一特性使它的三角分解。矩阵的这一特性使它的三角分解也有更简单的形式，从而导出一些也有更简单的形式，从而导出一些(yxi)特殊特殊的解法的解法,如平方根法与改进的平方根法。如平方根法与改进的平方根法。定理定理3.6 设设A是正定矩阵，则存在惟一的对角是正定矩阵，则存在惟一的对角元素均为正数的下三角阵元素均为正数的下三角阵L，使，使A=LLT证：因证：因A是正定矩阵是正定矩阵,A的顺序主子式的顺序主子式 i0,i=1,2,n 因此存在惟一的分解因

49、此存在惟一的分解 A=LU 第60页/共108页第六十页，共108页。L是单位下三角是单位下三角(snjio)阵阵,U是上三角是上三角(snjio)阵阵,将将U再再分解分解 其中其中D为对角为对角(du jio)阵阵,U0为单位上三角阵为单位上三角阵，于是，于是 A=L U=L D U0 又又 A=AT=U0TD LT由分解惟一性由分解惟一性,即得即得 U0T=L A=L D LT 第61页/共108页第六十一页，共108页。记记 又因为又因为(yn wi)det(Ak)(yn wi)det(Ak)0,(k=1,2,n),0,(k=1,2,n),故故于是对角阵于是对角阵D D还可分解还可分解

50、其中其中 为下三角为下三角(snjio)(snjio)阵阵,令令L=L1L=L1，定理得，定理得证。证。第62页/共108页第六十二页，共108页。将将A=LLTA=LLT展开展开(zhn ki)(zhn ki)，写成，写成 按矩阵乘法展开，可逐行求出分解矩阵按矩阵乘法展开，可逐行求出分解矩阵L L的元素的元素(yun s)(yun s)，计算公式是对于，计算公式是对于i=1,2,n i=1,2,n j=i+1,i+2,n 这一方法称为平方根法这一方法称为平方根法,又称乔累斯基又称乔累斯基(Cholesky)(Cholesky)分分解解,它所需要的乘除次数约它所需要的乘除次数约 为数量级为数量