高斯消去法的计算步骤课件.ppt

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

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

3、5R6E2E1E3BCDEFGHI1I2I3对环路对环路ABEF： UAB+ UBE+ UEF= E1 R1 IAB+ R4 IBE+ R5 IEF= E1 再用环路电流代替支路电流，即再用环路电流代替支路电流，即IAB=I1，IBE= I1- I2， IEF= I1- I3 利用欧姆利用欧姆定律定律式式为为 AR1R2R3R4R5R6E2E1E3BCDEFGHI1I2I3将将式代入式代入, 即得环路电流即得环路电流I1,I2,I3所满足的代数方程所满足的代数方程 (R1 + R4 + R5)I1 - R4I2 R5I3 = E1 同理同理, 对环路对环路BCDE及环路及环路FDGH可得方程：

4、可得方程： - R4 +（R2 + R4 + R6)I2-R6I3= E2 - R5I1 - R6I2+(R2 + R4 + R6)I3= E3 或写为矩阵形式即得到环路电流或写为矩阵形式即得到环路电流I1 ,I2 , I3所满足所满足的线性方程组：的线性方程组： (R1 + R4 + R5) -R4 - R5 I1 E1 -R4 (R2 + R4 + R6) - R6 I2 = E2 -R5 - R6 (R3 + R5 + R6) I3 E3 解上述线性方程组，即求得环路电流解上述线性方程组，即求得环路电流I I1 1 ,I,I2 2 , I, I3 3 在工程实际问题中产生的线性方程组，其

5、系数在工程实际问题中产生的线性方程组，其系数矩阵大致有两种：一种是低阶稠密矩阵（这种矩阵矩阵大致有两种：一种是低阶稠密矩阵（这种矩阵元素都存储在计算机的存储器中元素都存储在计算机的存储器中););另一类是大型稀另一类是大型稀疏矩阵疏矩阵( (此类矩阵阶数高此类矩阵阶数高, ,零元素较多零元素较多, ,压缩存储）。压缩存储）。 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa.22112222212111212111 nnnnnnnnbbbBxxxXaaaaaaaaaA.,.,.2121212222111211第第3章章 解线性方程组的直接法解线性方程组的直接法 常见的线性方程组是

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

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

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

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

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

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

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

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

14、构造归纳为：则高斯消去法的算法构造归纳为： nn),2, 1,(,)1()1(njibbaaiiijij 消元过程消元过程, ,高斯消去法的消元过程由高斯消去法的消元过程由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个方程的未知数个方程的未知数 , ,得到得到 即即 1 imi1x)2()2(b

15、xA)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(其中其中 第第k步步 （k=2,3,n-1）继续上述消元过程，设）继续上述消元过程，设第第k-1次消元已经完成，得到与原方程组等价的次消元已经完成，得到与原方程组等价的方程组方程组 knkknkknnknkkknkkknnbbbbxxxxaaaaaaaaa)()2(2) 1 (121)()()()()2(2)2(22) 1 (1) 1 (12) 1 (11nkjibmbba

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

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

18、()()1()()( 回代过程回代过程 1,2,1)(1)()()()(nniaxabxabxiiijnijiijiiinnnnnn(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/a11 (i=2,3,n) 需要需要n-1次除法运算次除法运算, 计算计算 aij(2）(i,j=2,3,n) 需要需要(n-1)2次乘法运算及次乘法运算

19、及(n-1)2次加减法运次加减法运 算算,第第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)/63.2.3 3.2.3 高斯消去法的适用条件高斯消去法的适用条件 定理定理3.1 3.1 方程组系数矩阵的顺序主子式全不方程组系数

20、矩阵的顺序主子式全不 为零则高斯消去法能实现方程组的为零则高斯消去法能实现方程组的 求解。求解。证明证明 上三角形方程组是从原方程组出发，通上三角形方程组是从原方程组出发，通过逐次进行过逐次进行“一行乘一数加到另一行一行乘一数加到另一行”而得出而得出的，该变换不改变系数矩阵顺序主子式的值。的，该变换不改变系数矩阵顺序主子式的值。 设方程组系数矩阵设方程组系数矩阵 ，其顺序主子式，其顺序主子式 nijaA)(01111mmmmmaaaaA（m =1,2,m =1,2,，n n） 经变换得到的上三角形方程组的顺序主子式经变换得到的上三角形方程组的顺序主子式 0)()2(22)1(11)()2(2)

21、2(22)1(1)1(12)1(11mmmmmmmmmaaaaaaaaaA所以能实现高斯消去法求解所以能实现高斯消去法求解 （m =1,2,m =1,2,，n n） 定义定义3.1 3.1 设矩阵设矩阵 每一行对角元素每一行对角元素的绝对值都大于同行其他元素绝对值之和的绝对值都大于同行其他元素绝对值之和 nijaA)(niaanijjijii,2, 1,1则称则称A A为严格对角占优矩阵。为严格对角占优矩阵。 定理定理3.2 3.2 若方程组若方程组 的系数矩阵的系数矩阵A为严为严格对角占优，则用高斯消去法求解时，格对角占优，则用高斯消去法求解时， 全全不不为零。为零。 bAx )(kkka证

22、证: :先考察消元过程的第先考察消元过程的第1 1步步, ,因因A为严格对角占为严格对角占 优优, ,故故 故故 , ,又根据高斯消又根据高斯消 去公式得去公式得 于是于是 njjaa2111011)1(11 aanjiaaaaajiijij,3 ,2,1111)2(nijjjinijjijnijjijaaaaa2111122)2()(12111111injjiinijjijaaaaaa再利用方程组的对角占优性再利用方程组的对角占优性, ,由上式可进一步得由上式可进一步得 111111111112)2()(aaaaaaaaaaaiiiiiiiiinijjij又由又由 njiaaaaajiiji

23、j, 3 ,2,1111)2(得得 11111111)2(aaaaaaaaaiiiiiiiiii故有故有 niaaiinijjij,3,2,)2(2)2(当当A A为严格对角占优时为严格对角占优时, , ,余下的子阵仍是余下的子阵仍是对角占优的，从而又有对角占优的，从而又有 。依次类推全不。依次类推全不为零。为零。 定理证毕。定理证毕。 011) 1 (11aa0)2(22a 一般线性方程组使用高斯消去法求解时，一般线性方程组使用高斯消去法求解时，在消元过程中可能会出现在消元过程中可能会出现 的情况，这的情况，这时消去法将无法进行；即使时消去法将无法进行；即使 ，但它的，但它的绝对值很小时，用

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

25、主元素的消元法为主元素为主元素法法 根据主元素选取范围分为：列主元素法、根据主元素选取范围分为：列主元素法、行主元素法、全主元素法行主元素法、全主元素法记笔记记笔记3.2.4 3.2.4 高斯主元素消去法高斯主元素消去法主元素法的意义主元素法的意义例例3.2 用高斯消去法求下列方程组的解用高斯消去法求下列方程组的解 211021215xxxx解：解： 确定乘数确定乘数 ，再计算系数，再计算系数 52110m5)2(25122122)2(22102101bamaa假设计算在假设计算在4 4位浮点十进值的计算机上求解位浮点十进值的计算机上求解, ,则有则有 5555555510101000002.

26、 010210101000001. 0101，这时方程组的实际形式是这时方程组的实际形式是 5252151010110 xxx由此回代解出由此回代解出 , ,但这个解不满足原但这个解不满足原方程组方程组, ,解是错误的。这是因为所用的除数太小解是错误的。这是因为所用的除数太小使得上式在消元过程中使得上式在消元过程中“吃掉吃掉”了下式，解决了下式，解决这个问题的方法之一就是采用列选主元高斯消这个问题的方法之一就是采用列选主元高斯消元法。即按列选绝对值大的系数作为主元素，元法。即按列选绝对值大的系数作为主元素，则将方程组中的两个方程相交换，原方程组变则将方程组中的两个方程相交换，原方程组变为为 1

27、, 021xx110221521xxxx得到消元后的方程组得到消元后的方程组 525211021)101 (2xxx这时这时 5555555510101000002. 010210101000001. 0101，因而方程组的实际形式是因而方程组的实际形式是 12221xxx由此回代解出由此回代解出 , ,这个结果是正确的这个结果是正确的 1, 121xx 可见用高斯消去法解方程组时可见用高斯消去法解方程组时, ,小主元可小主元可能导致计算失败能导致计算失败, ,因为用绝对值很小的数作除因为用绝对值很小的数作除数数, ,乘数很大乘数很大, ,引起约化中间结果数量级严重增引起约化中间结果数量级严重

28、增长长, ,再舍入就使得计算结果不可靠了再舍入就使得计算结果不可靠了, ,故避免采故避免采用绝对值很小的主元素。以便减少计算过程中用绝对值很小的主元素。以便减少计算过程中舍入误差对计算解的影响。舍入误差对计算解的影响。全主元素消去法全主元素消去法 是通过方程或变量次序的交换，使在对角是通过方程或变量次序的交换，使在对角线位置上获得绝对值尽可能大的系数作为线位置上获得绝对值尽可能大的系数作为 称这样的称这样的 为主元素。尽管它的算法更稳为主元素。尽管它的算法更稳定，但计算量较大，实际应用中大多数使用列定，但计算量较大，实际应用中大多数使用列主元素消去法即可满足需要。主元素消去法即可满足需要。 )

29、(kkka)(kkka不是按列选主元素，而是在全体不是按列选主元素，而是在全体待选系数中选取，则得待选系数中选取，则得全主元素法。全主元素法。 例例3.3 用用全主元素法解下列线组全主元素法解下列线组 10 x1 - 19x2 - 2x3=3 (1)-20 x1 +40 x2 + x3 =4 (2) x1 + 4x2 + 5x3=5 (3)n解：选择所有系数中绝对值最大的解：选择所有系数中绝对值最大的40作为作为主主元素，交换第一、二行和交换第一、二列使元素，交换第一、二行和交换第一、二列使该主元素位于对角线的第一个位置上，得该主元素位于对角线的第一个位置上，得40 x2 - 20 x1 +

30、x3 =4 (4)-19x2+10 x1 - 2x3=3 (5) 4x2+ x1 +5x3=5 (6)记笔记记笔记计算计算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.5x1=4.9 (10)计算计算m32=-1.525/4.9=-0.31122， (10)- m32(9)消去消去x2得得1.43366x1=6. 33161 (11)

31、记笔记记笔记保留有主元素的方程保留有主元素的方程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.352303.2.4.1 列主元素法列主元素法 列主元素法就是在待消元的所在列中选取主列主元素法就是在待消元的所在列中选取主元，经方程的行交换，置主元素于对角线位元，经方程的行交换，置主元素于对角线位置后进行消元的方法。置后进行消元的方法。 例例3.4 用用列主元素法解下列线性方程组列主元素法解下列线性方程组 10 x1 - 19x2 -

32、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.5 m31=1/-20=-0.05(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)计

33、算计算m32=1/6=0.16667， (10)- m32(9) 得得-2.34168x3=4.13332 (11)记笔记记笔记保留有主元素的方程保留有主元素的方程 -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记笔记记笔记 列选主元素的计算方法与高斯消去法完全一样列选主元素的计算方法与高斯消去法完全一样, ,不同的是在每步消元之前要按列选出主元不同的是在每步消元之前要按列选出主元例例3.5 3.5 用矩阵的初等行变换

34、求解解方程组用矩阵的初等行变换求解解方程组 754217743322321321321xxxxxxxxx 解解: : 用矩阵的初等行变换求解用矩阵的初等行变换求解, ,对增广矩阵对增广矩阵 ( (下面带下划线元素为主元素下面带下划线元素为主元素) ) 2 . 12 . 1005 . 65 . 85 . 7017745 . 25 . 05 . 105 . 65 . 85 . 7017745 . 65 . 85 . 705 . 25 . 05 . 101774754233221774754217743322232313121251_2121_) 1 (rrrrrrrrrrbAA3.2.5 3.2.

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

36、斯-约当消去法约当消去法,这时等号右端即为方程组的解这时等号右端即为方程组的解例例3.6 3.6 用高斯用高斯- -约当约当(Jordan)(Jordan)消去法求方程组的解消去法求方程组的解 120221321321321xxxxxxxxx解解 方程组相应的增广矩阵方程组相应的增广矩阵 111202211111111102211112列选主元列选主元5 . 15 . 05 . 105 . 05 . 15 . 205 . 05 . 05 . 012 . 14 . 0002 . 06 . 0104 . 08 . 0013100201020013, 2, 2321xxx故得故得 定理定理3.4 3

37、.4 设设A A为非奇异矩阵，方程组为非奇异矩阵，方程组AX = I的的增广矩阵为增广矩阵为 C = = A A I I ，如果对，如果对C应用高斯应用高斯- -约当消去法化为约当消去法化为 I I B B ，则，则 = =B。例例3.7 3.7 用高斯用高斯- -约当（约当（JordanJordan）消去法）消去法求求 1A563452231A的逆矩阵的逆矩阵 1A解解 C = = A A I I = = 1005630104520012311031300120100012311331000120100352011331000120102310011330122311A3.3 矩阵三角分解法

38、矩阵三角分解法 矩阵三角分解法是高斯消去法解线性方程组的一矩阵三角分解法是高斯消去法解线性方程组的一种变形解法种变形解法 3.3.1 3.3.1 矩阵三角分解原理矩阵三角分解原理 应用高斯消去法解应用高斯消去法解n阶线性方程组阶线性方程组Ax=b, 经过经过n步消元之后步消元之后, , 得出一个等价的上三角型方程组得出一个等价的上三角型方程组A(n) x=b(n), 对上三角形方程组用逐步回代就可以求对上三角形方程组用逐步回代就可以求出解来。上述过程可通过矩阵分解来实现。出解来。上述过程可通过矩阵分解来实现。 将非奇异阵将非奇异阵A分解成一个下三角阵分解成一个下三角阵L和一个上三和一个上三角阵

39、角阵U的乘积的乘积 A=LU 称为对称为对矩阵矩阵A A的三角分解，又称的三角分解，又称LU分解分解)() 3(3) 3(33) 2(2) 2(23) 2(22) 1 (1) 1 (13) 1 (12) 1 (1121323121,1111nnnnnnnnaaaaaaaaaaUmmmmmLLUaaaaaaaaaaaaaaaaAnnnnnnnn321333323122322211131211其中其中方程组方程组Ax=b的系数矩阵的系数矩阵A经过顺序消元逐步化经过顺序消元逐步化为上三角型为上三角型A(n),相当于用一系列初等变换左乘相当于用一系列初等变换左乘A的结果。事实上，第的结果。事实上，第1

40、列消元将列消元将A(1)=A化为化为A(2)，若令：，若令：10000100010001131211nmmmL), 3 , 2(,) 1 (11) 1 (11niaamii则根据距阵左乘有则根据距阵左乘有L1A(1)=A(2)第第2列消元将列消元将A(2)化为化为A(3)，若令：，若令：1000010001000012322nmmL), 4 , 3(,)2(22)2(22niaamii经计算可知经计算可知 L2A(2)=A(3),依此类推依此类推,一般有一般有LkA(k)=A(k+1)11111,1nkkkkmmLmi1= a(1) i1/ a(1) 11 i=2,3,n于是矩阵于是矩阵 经过

41、消元化为上三角阵经过消元化为上三角阵 的过程可表示为的过程可表示为上述矩阵上述矩阵 是一类初等矩阵是一类初等矩阵, ,它们都是单位下三角阵，且其逆矩阵也是单位它们都是单位下三角阵，且其逆矩阵也是单位下三角阵下三角阵, ,只需将只需将 改为改为 , ,就得到就得到 。即。即 ) 1 (AA)(nA)(1221nnnAALLLL) 1, 2 , 1(nkLkikm), 2, 1(nkkimik1kL11111, 11nkkkkmmL于是有于是有 LUULLLALLLAnnn)()(111211)(111211)() 3 (3) 3 (33) 2(2) 2(23) 2(22) 1 (1) 1 (13

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

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

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

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

46、,非奇异矩阵不一定都有非奇异矩阵不一定都有LULU分解把分解把A分解分解, ,例例: :0110A显然显然A A非奇异非奇异, ,若若A A有有LULU分解分解, ,则则cadabdbcdba01010110 比较两边元素得比较两边元素得b=0,ab=1, b=0,ab=1, 显然矛盾显然矛盾 故该非奇异矩阵故该非奇异矩阵A A不存在不存在LULU分解分解, ,所以并所以并非非奇异矩阵都有非非奇异矩阵都有LULU分解分解. . 原因是原因是A A的顺序主子式的顺序主子式=0.=0.尽管尽管A A是非奇异是非奇异矩阵矩阵, ,不符合定理要求不符合定理要求. . 把把A分解成一个单位下三角阵分解成

47、一个单位下三角阵L和一个上和一个上三角阵三角阵U的乘积称为的乘积称为杜利特尔（杜利特尔（Doolittle）分解分解。其中其中 nnnnnnuuuuuuUlllL222112112121,1113.3.2 用三角分解法解方程组用三角分解法解方程组 求求解线性方程组解线性方程组Ax=b时时,先对非奇异矩阵先对非奇异矩阵A进行进行LU分解使分解使A=LU，那么方程组就化为，那么方程组就化为 LU x=b从而使问题转化为求解两个简单的的三角方从而使问题转化为求解两个简单的的三角方程组程组 L y=b 求解求解 y U x=y 求解求解 x这就是求解线性方程组的三角分解法的基本这就是求解线性方程组的三

48、角分解法的基本思想。下面只介绍杜利特尔（思想。下面只介绍杜利特尔（Doolittle）分）分解法。解法。设设A=LU为为若把若把A分解成一个下三角阵分解成一个下三角阵L和一个单位上和一个单位上三角阵三角阵U的乘积称为的乘积称为克克洛特分解洛特分解Crout） 其中其中 111,211221222111nnnnnnuuuUllllllLnnnnnnnnnnnuuuuuulllaaaaaaaaa2221121121212122221111111111 由矩阵乘法规则由矩阵乘法规则niuaii, 2 , 111niulaii, 3 , 21111 由此可得由此可得U的第的第1行元素和行元素和L的第的

49、第1列元素列元素niauii, 2 , 111niualii,3 ,21111 再确定再确定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） nnnnnnnnnnnuuuuuulllaaaaaaaaa2221121121212122221111111111利用上述计算公式便可逐步求出利用上述计算公式便可逐步求出U与与

50、L的各元素的各元素求解求解 Ly=b , Ly=b , 即计算即计算: : 1111),3 ,2(ikkikiiniylbyby 求解求解 UxUx=y , =y , 即计算：即计算： )1 ,2, 1(1niuxuyxuyxiinikkikiinnnn 显然显然, 当当 时时, 解解Ax=b直接三角分解法计算才能完成。设直接三角分解法计算才能完成。设A为非奇异矩阵为非奇异矩阵, 当当 时计算将中断或者时计算将中断或者当当 绝对值很小时，按分解公式计算可绝对值很小时，按分解公式计算可能引起舍入误差的积累，因此可采用与列能引起舍入误差的积累，因此可采用与列主元消去法类似的方法，对矩阵进行行交主元