第3章_解线性方程组的直接方法

1、数值计算方法2022-3-271第第3 3章章 解线性代数方程组的直接法解线性代数方程组的直接法nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111本章介绍求解n阶线性代数方程组（31）数值计算方法2022-3-272的的直接法直接法，并研究舍入误差对解的影响。，并研究舍入误差对解的影响。 这里假定系数行列式不为零，由克莱姆法则知，这里假定系数行列式不为零，由克莱姆法则知，方程组的解方程组的解存在且唯一存在且唯一。 所谓所谓直接法直接法，就是不计舍入误差时，通过，就是不计舍入误差时，通过有限有限次次算术运算能求得算术运算能求得准确解准确解的方法

2、。的方法。 克莱姆法则法就是一种直接法。只是方程组阶数克莱姆法则法就是一种直接法。只是方程组阶数较高时它的运算量太大，实际无法使用。较高时它的运算量太大，实际无法使用。 本章介绍计算机上常用、有效的直接法本章介绍计算机上常用、有效的直接法高斯高斯消去法与三角分解法消去法与三角分解法。数值计算方法2022-3-273 线性方程组（线性方程组（3-1）常简写成）常简写成矩阵矩阵形式形式Ax=b1112112122221212nnnnnnnnaaaxaaaxAxaaaxbbbb其中，数值计算方法2022-3-2743.1 高斯消去法高斯消去法3.1.1 高斯消去法的基本步骤高斯消去法的基本步骤 高斯

3、（高斯（Gauss）消去法其实就是一种消去）消去法其实就是一种消去法法(消元法消元法)，只是步骤规范，便于编写计算，只是步骤规范，便于编写计算机程序。机程序。 中国东汉初年诞生的中国东汉初年诞生的九章算术九章算术，记载了求解线性代数组的消去法，比国外早记载了求解线性代数组的消去法，比国外早 1500年。年。数值计算方法2022-3-275例如：例如：要解方程组要解方程组31187435132321321321xxxxxxxxx其步骤如下：将第一个方程乘其步骤如下：将第一个方程乘-5，-7，分别加于第二、，分别加于第二、第三方程，消去未知量第三方程，消去未知量x1，得同解方程组，得同解方程组10

4、10691891323232321xxxxxxx数值计算方法2022-3-276将所得方程组的第二方程乘将所得方程组的第二方程乘 ，加到第三方程，加到第三方程，消去未知量消去未知量x2，得同解方程组，得同解方程组32429189132332321xxxxxx这是这是上三角形方程组上三角形方程组。 由第三方程解得由第三方程解得x3=-2，将，将x3代入第二方程可代入第二方程可解得解得x2=5，再将，再将x3、x2代入第一方程解得代入第一方程解得x1=-3。数值计算方法2022-3-277 一般高斯消去法包括一般高斯消去法包括两个过程两个过程：先把方程组：先把方程组化为同解的上三角形方程组，再按相

5、反顺序求化为同解的上三角形方程组，再按相反顺序求解上三角形方程组。前者称解上三角形方程组。前者称消去消去或或消元消元过程，过程，后者称后者称回代回代过程。过程。 消去过程实际上是对消去过程实际上是对增广矩阵增广矩阵作作行初等变换行初等变换。 如上例可表示为如上例可表示为bAA数值计算方法2022-3-278 10911061893213411117315321125rr137rr 49121839211332rr数值计算方法2022-3-279对一般的对一般的n阶线性方程组，消去过程分阶线性方程组，消去过程分n-1步步：第第1步步 消去消去a11 下方元素，下方元素，第第2步步 消去消去 下方

6、元下方元素，第第n-1步步 消去消去 下方元素。下方元素。 第第k步将第步将第k行的适当倍数加于其后各行，行的适当倍数加于其后各行，也可说是从也可说是从k+1n行减去第行减去第k行的适当倍数，行的适当倍数， 使它们的第使它们的第k列元素变为零，而其他列元素减列元素变为零，而其他列元素减去第去第k行对应列元素的倍数。行对应列元素的倍数。(1)(1)2222a a(n-2)(n-2)n-1, n-1n-1, n-1a a数值计算方法2022-3-271011121k1, k+11n111121k1, k+11n1(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)222k2, k+12n2

7、222k2, k+12n2n-1n-1n-1n-1(k-1)(k-1)(k-1)(k-1)(k-1)(k-1)(k-1)(k-1)kkk, k+1knkkkk, k+1knk(n-1)(n-1)(n-1)(n-1)nnnnnnaa.aa.abaa.aa.aba.aa.aba.aa.ab.A,b=A,b=aa. abaa. ab.abab 经高斯消去法进行经高斯消去法进行n-1步消元后得到上步消元后得到上三角形方程组为：三角形方程组为：数值计算方法2022-3-2711 如把增广矩阵变换前后都在计算机上用如把增广矩阵变换前后都在计算机上用同一数组同一数组A存储，则消去过程可写为：存储，则消去过程

8、可写为：A 对对k=1n-1（步步）做）做 对对i= k+1n（行行）做）做 令令 （“适当倍数适当倍数”） 对对j= k+1n+1（列列）令）令/ikikkklaaijijik kjaal a数值计算方法2022-3-2712回代过程是解同解的回代过程是解同解的上三角形上三角形方程组方程组nnnnnnnnnnnnnnnnnnnbxabxaxabxaxaxabxaxaxaxa1, 111, 12211, 222211111212111,数值计算方法2022-3-2713注意：注意：此处此处增广矩阵不是增广矩阵不是原始原始增广矩阵，而增广矩阵，而是是变换后变换后的增广矩阵，的增广矩阵，b是变换后

9、增广矩阵是变换后增广矩阵的第的第n+1列。回代过程可写为：列。回代过程可写为： 令令 对对k = n 1 1(行行)令令nnnnabx/kknkjjkjkkaxabx/ )(1数值计算方法2022-3-27143.1.2 高斯消去法的运算量高斯消去法的运算量 高斯消去法比起克莱姆法则和约当消去高斯消去法比起克莱姆法则和约当消去法，主要长处就是运算量较少。法，主要长处就是运算量较少。 用克莱姆法则求解用克莱姆法则求解n阶线性方程组，需计阶线性方程组，需计算算n+1 个行列式；每个行列式是个行列式；每个行列式是n!个乘积之和，个乘积之和，而每个乘积是而每个乘积是n个元素相乘，因此共需乘法次个元素相

10、乘，因此共需乘法次数数(n+1)n!(n-1)+n=(n+1)!(n-1)+n数值计算方法2022-3-2715当当n=20时时(n+1)!(n+1)9.70731020。 要完成这么多次乘法，在每秒做一亿次乘要完成这么多次乘法，在每秒做一亿次乘法运算的计算机上，也需法运算的计算机上，也需30.8万年。因此克莱万年。因此克莱姆法则在实际计算中不适用。姆法则在实际计算中不适用。 高斯消去法消去过程分高斯消去法消去过程分n-1步，第步，第k步变换步变换n-k行：对这些行先求倍数，再从行：对这些行先求倍数，再从k+1n行的行的n+1-k个元素减去第个元素减去第k行对应列的倍数；因此，行对应列的倍数；

11、因此，共需乘、除次数：共需乘、除次数：数值计算方法2022-3-2716112316523 1)1)(nknnnknknN) 1(2212nnnN 回代过程求回代过程求xn需需1次除法，求次除法，求xn-1需需1次乘次乘法、法、1次除法，次除法，求，求x1需需n 1次乘法次乘法1次除次除法，因此共需乘除次数法，因此共需乘除次数两过程共需乘除次数两过程共需乘除次数332321nnnNNN数值计算方法2022-3-2717当当n=20时，时，N=3060，显然比克莱姆法则少得多。，显然比克莱姆法则少得多。 线性代数教材讲授线性方程组解法时，往线性代数教材讲授线性方程组解法时，往往提倡用行初等变换把

12、增广矩阵化为最简形。往提倡用行初等变换把增广矩阵化为最简形。如上例方程组，多用如下变换： 10911061893213411117315321125rr137rr 数值计算方法2022-3-2718 变换结束后增广矩阵最后一列就是解，不变换结束后增广矩阵最后一列就是解，不需回代。这种解法称为需回代。这种解法称为约当消去法约当消去法。 它容易学习掌握，也容易编写计算机程序。它容易学习掌握，也容易编写计算机程序。其计算过程可写为：其计算过程可写为： 2151314212111132312321262rrrrrrrr23r)9(2r数值计算方法2022-3-2719 对对k=1n(步步)做做 对对j

13、= k+1n (行行)令令 对对I=1n但但ik(行行)做（做（“适当倍数适当倍数”） 对对j= k+1n+1(列列)令令kjikijijaaaakkkjkjaaa/不过这种解法需要乘除次数不过这种解法需要乘除次数nknnnknnknN123322)1)(1()1(数值计算方法2022-3-2720137rr 比高斯消去法多比高斯消去法多 相当于相当于 ),(6133nnNN 高斯消去法约一半的运算量。因此高斯消去法约一半的运算量。因此除非方程组除非方程组的阶数的阶数n n较小，计算机上不用约当消去法较小，计算机上不用约当消去法。 一般算法乘除次数与加减次数相差不多，一般算法乘除次数与加减次数

14、相差不多，而且计算机上乘除运算比加减运算费时间，而且计算机上乘除运算比加减运算费时间，所以通常只比较所以通常只比较乘除次数乘除次数。数值计算方法2022-3-27213.1.3 3.1.3 选主元技术选主元技术 高斯消去法消去过程中，第高斯消去法消去过程中，第k步求步求n-k个倍个倍数数 aik/akk 用到的除数用到的除数akk ，称为，称为主元主元。 它若为它若为零零或或接近于零接近于零，计算机将，计算机将“溢出溢出”而停止计算，或产生较大误差。而停止计算，或产生较大误差。232121021215xxxx例如方程组例如方程组数值计算方法2022-3-2722准确到九位小数的解是准确到九位小

15、数的解是x1=0.250 001 875，x2=0.499 998 749。若在若在4位计算机上按高斯消去法求解，则有位计算机上按高斯消去法求解，则有555102510210412102321210152rr回代解得回代解得 =0.5， =0，显然，显然严重失真严重失真。2x1x数值计算方法2022-3-2723造成这种结果的原因，就是造成这种结果的原因，就是小主元小主元的出现。的出现。 用它作除数产生大商数，数乘大数变大数，用它作除数产生大商数，数乘大数变大数，大数吃小数产生舍入误差大数吃小数产生舍入误差（如（如34105=-399 997-1060.400 0），），从而从而 有误差。有误

16、差。2x代回第一个方程时，代回第一个方程时，因为因为10-5x1+2x2=1，10-5 +2 =1 两式相减得两式相减得1x2x10-5(x1 )+2(x2 )=0，1x2x数值计算方法2022-3-2724可见可见 | x1 |=200 000| x2 |2x1x表明表明 的误差被放大的误差被放大200 000倍，倍， 自然失真。自然失真。2x1x 为了避免出现小主元，可在第为了避免出现小主元，可在第k步的第步的第k列列的元素的元素 中选主元，即中选主元，即nkkkkkaaa, 1 在其中找出绝对值最大的元素在其中找出绝对值最大的元素 ，然后交换，然后交换第第k和第和第p行，继续进行消去过程

17、。行，继续进行消去过程。pka 交换行相当于改变方程顺序，不会影响原交换行相当于改变方程顺序，不会影响原方程组的解。这种消去法称为方程组的解。这种消去法称为列主元消去法列主元消去法。数值计算方法2022-3-2725把它应用于上例，有把它应用于上例，有 12232121023223212101522121055rrrr回代得解回代得解 =0.5, =0.25，接近真解。，接近真解。2x1x 也可在第也可在第k行元素行元素akk，ak,k+1，akn中选中选绝对值最大的元素绝对值最大的元素akq，交换，交换k、p行和行和k、p列，列，然后继续消去过程。然后继续消去过程。这两种消去法分别称这两种消

18、去法分别称行主元法行主元法与与全主元法全主元法。数值计算方法2022-3-2726 不过交换两列相当于改变未知量顺序，所不过交换两列相当于改变未知量顺序，所以需用一数组，专门记录未知量顺序及其变化，以需用一数组，专门记录未知量顺序及其变化，并在最后调整解的顺序，使解中并在最后调整解的顺序，使解中n个数与未知个数与未知量正确对应。量正确对应。 假定用数组假定用数组L表求未知量的顺序，则全主表求未知量的顺序，则全主元法的计算步骤可归纳如下：元法的计算步骤可归纳如下：数值计算方法2022-3-2727 对对j=1n令令Lj j（记未知量原始顺序）（记未知量原始顺序） 对对k=1n-1做（以下为消去过

19、程）做（以下为消去过程） 求求 当当pk时交换的时交换的k，p行行 当当 k p时交换及时交换及L的的k，p列列 对对i= k+1n做做 令令c aik/akk 对对i= k+1n+1令令aij aij-cakj pqijpqijk i nk i nk j nk j namax|a |amax|a |(消元)(选全主元选全主元)数值计算方法2022-3-2728 令an，n+1 an，n+1/ann 对i=n 1 1令ai, n+1 对i= 1 n 令P L；xp ai, n+1nijiinjijniaaaa11,1,)/(回代) 三种主元消去法选取绝对值相对最大的元素三种主元消去法选取绝对值

20、相对最大的元素作主元，保证了倍数作主元，保证了倍数c的绝对值不超过的绝对值不超过1，也有利，也有利于控制误差的传播，所以稳定性较好。三种主元于控制误差的传播，所以稳定性较好。三种主元法中全元法稳定性最好，但全主元法中全元法稳定性最好，但全主元法最费时间，法最费时间，数值计算方法2022-3-2729 有些方程组的系数数矩阵特殊，如对称有些方程组的系数数矩阵特殊，如对称正定或对角占优，即满足条件正定或对角占优，即满足条件njjijiiaa11|， i=1,2,n可以保证主元就在对角线上，当然不需选主元。可以保证主元就在对角线上，当然不需选主元。 程序最复杂。通常情况下稳定性彼此相差不大，程序最复

21、杂。通常情况下稳定性彼此相差不大，所以一般情况都只用列主元消去法。所以一般情况都只用列主元消去法。数值计算方法2022-3-2730复习题复习题1、何谓高斯消去法？它与一般消去法有何不、何谓高斯消去法？它与一般消去法有何不同？怎样计算行列式？同？怎样计算行列式？2、计算机上为什么不用克莱姆法与约当消去、计算机上为什么不用克莱姆法与约当消去法？法？3、何谓主元消去法？有何优点？、何谓主元消去法？有何优点？数值计算方法2022-3-2731应用应用Gauss列主元消去法解列主元消去法解n阶线性方程阶线性方程组组Ax=b，其中，其中A=aijnn，b=a1,n+1,.,an,n+1T输入输入 方程组

22、的阶数方程组的阶数n；增广矩阵；增广矩阵A,b。输出输出 方程组的解方程组的解x1,.,xn或系数矩阵奇异的信息。或系数矩阵奇异的信息。算法算法3.13.1.2 Gauss3.1.2 Gauss选列主元消去法选列主元消去法数值计算方法2022-3-2732STEP1 对对k=1,2,.,n-1(步步)做做STEP2-5 STEP3 若若 ，则输出，则输出(A is singular)；停机；停机 k ki , ki , ka= 0a= 0STEP4则kkkkkkjkji , ji , jkkjkji , ji , j若若i i k,tk,t a ,aa ,a a,aa,a t tj= k,k+

23、1,.,n+1(列j= k,k+1,.,n+1(列) )STEP5 对对i=k+1,.,n(行行)做做STEP6-7STEP6 求乘子求乘子aiklik=aik/akkSTEP7 对对j=k+1,.,n+1(列列)消元消元 aijaij-aikakj k ki , kiki , kikk i nk i na= max aa= max aSTEP2 选列主元：求选列主元：求ik使使数值计算方法2022-3-2733STEP8 若若ann=0,则输出则输出(A is singular);停机。停机。 否则，否则， xnan,n+1/annSTEP9 对对k=n-1,.,1(行行)n nkk, n+

24、1kjjkkkk, n+1kjjkkj=k+1j=k+1x =(a-a x )/ax =(a-a x )/aSTEP10 输出输出(x1,x2,.,xn),停机停机.数值计算方法2022-3-27343.1.3 Gauss3.1.3 Gauss按比例选列主元消去法按比例选列主元消去法例例 将方程组将方程组12316913821.127812.87343114xxx 改为方程组改为方程组4444144442316*109*101*1038*102*101.127*108*1012.873*1043114xxx 应用应用Gauss列主元消去法，进行第一步消列主元消去法，进行第一步消元以后增广矩阵是

25、元以后增广矩阵是: 数值计算方法2022-3-2735444416*109*101*1038*10020812508123005.250.754.5 由此可见，第二步的主行是第二行，消元由此可见，第二步的主行是第二行，消元过程结束后，由回代过程得到的计算解与例过程结束后，由回代过程得到的计算解与例2中中应用基本应用基本Gauss消去法得到的计算解相同。消去法得到的计算解相同。 该例说明，该例说明，Gauss列主元消去法也会使计列主元消去法也会使计算结果产生较大的误差。算结果产生较大的误差。 数值计算方法2022-3-2736 后面的方程组是由前面的方程组的头两个后面的方程组是由前面的方程组的头

26、两个方程乘方程乘104得到的。得到的。 在消元过程第在消元过程第k步，若第步，若第k列的第列的第k至第至第n个个元素中元素中某个元素某个元素与其所在行的与其所在行的“大小大小”之比为之比为最大者，就选它作为主元，这种选主元的方法最大者，就选它作为主元，这种选主元的方法似乎是合理的，经过这样修改的选列主元消去似乎是合理的，经过这样修改的选列主元消去法称为法称为按比例选列主元消去法。按比例选列主元消去法。 数值计算方法2022-3-2737 Gauss按比例选列主元消去法就是在消元按比例选列主元消去法就是在消元过程第一步之前，对过程第一步之前，对i=1,2.,n，计算方程组的，计算方程组的系数矩阵

27、的第系数矩阵的第i行的大小行的大小,即找出每行元素绝对即找出每行元素绝对值的最大者：值的最大者：1maxiijj nsa 在第在第k步，找出最小的步，找出最小的r(rk)，使，使,rkikriaakinss 则第则第r行就是按比例最大的行，选作主行。行就是按比例最大的行，选作主行。 对换增广矩阵的第对换增广矩阵的第k行与第行与第r行。行。数值计算方法2022-3-2738输入输入 方程组的阶数方程组的阶数n；增广矩阵；增广矩阵A,b。输出输出 方程组的解方程组的解x1,.,xn或系数矩阵奇异的信息。或系数矩阵奇异的信息。算法算法3.2 应用应用Gauss按比例选列主元消去法解按比例选列主元消去

28、法解n阶阶线性方程组线性方程组Ax=b，其中，其中A=aijnn，b=a1,n+1,.,an,n+1T数值计算方法2022-3-2739若若si=0，则输出，则输出(A is singular)；停机。；停机。STEP1 对对i=1,2,.,n(行行)1maxiijj nsa STEP2 对对k=1,2,.,n-1(步步)做做STEP3-7 STEP3 选主元选主元:求求r，使，使 maxrkikk i nriaass STEP4 若若ark=0，则输出则输出(A is singular)；停机。停机。STEP5 若若rk，则，则qsk, sksr, srq。STEP6 对对j=k,.,n+1

29、(列列) ,takj, akjarj ,arjt。(对换增广矩阵的第对换增广矩阵的第k行与第行与第r行行)数值计算方法2022-3-2740STEP7 对对i=k+1,.,n(行行)做做STEP8-9STEP8 求乘子求乘子aiklik=aik/akkSTEP9 对对j=k+1,.,n+1(列列)消元消元 aijaij-aikakj STEP10 若若ann=0,则输出则输出(A is singular);停机。停机。 否则，否则， xnan,n+1/annSTEP11 对对k=n-1,.,1(行行)n nkk, n+1kjjkkkk, n+1kjjkkj=k+1j=k+1x =(a-a x

30、)/ax =(a-a x )/aSTEP10 输出输出(x1,x2,.,xn)，停机。，停机。数值计算方法2022-3-2741例例3 应用应用Gauss按比例按比例列主元消去法解方程组列主元消去法解方程组12312133403210410 xxx1213,3403210410A b解：1232410sss112131123131,245aaasss2122,34031213210410srr1第 行为主行，s1234210sss数值计算方法2022-3-2742312121213131111112,33aaalalaa 求乘子，消元得123322233340312481234210sss22

31、222323323111,231015aass32322233,123334034812s rr2第3行为主行，s1234102sss323232221,11aala 求乘子，消元得2223371143111111340348123201xxx 回代解得数值计算方法2022-3-2743 算法算法3.2中，若不进行增广矩阵的行交换，中，若不进行增广矩阵的行交换，则可引进一个向量则可引进一个向量P=p1,p2,pnT来来记录行交记录行交换换。P的分量最初为的分量最初为pi=i，i=1,2,n，即，即P=1,2,nT。 若在消元过程的第若在消元过程的第k步需要交换增广矩阵的步需要交换增广矩阵的第第

32、k行与第行与第r行，则交换行，则交换P的第的第k与第与第r个分量。消个分量。消元过程结束时，向量元过程结束时，向量P便给出消元过程中便给出消元过程中一组主一组主行的指示行的指示。 数值计算方法2022-3-2744 这样，最后的这样，最后的 p1指示原始增广矩阵在第一步指示原始增广矩阵在第一步被选为主行的行，被选为主行的行，p2指示第二步被选为主行的行，指示第二步被选为主行的行，等等依此类推。等等依此类推。 在消元过程中，对增广矩阵进行行交换的在消元过程中，对增广矩阵进行行交换的目的是把系数矩阵化为一个上三角阵。由此可目的是把系数矩阵化为一个上三角阵。由此可知，最后一个方程仅含知，最后一个方程

33、仅含xn和和xn-1等等。等等。 但是但是P的最后元素也给出这种信息：第的最后元素也给出这种信息：第pn个个方程仅含方程仅含xn,第第pn-1个方程含个方程含xn和和xn-1等等。等等。 数值计算方法2022-3-2745例例4：解方程组：解方程组12312133403210410 xxx解：解：1213,3403210410A b321P312123,1,1,1131,245ppppppaaasss2122ppp是主行，1042321pppsss102431210410230433121321pppsssP322311,1,11211,131,133,1,1,ppppppaaaaaaaa 求

34、乘子数值计算方法2022-3-27461511,311024312P8430432133223212,2,322323231 pppppppsasasss消元得323,3ppp是主行1323231233,212,2,222233412213403 P310114812ppppppsasaaas 2104132P84304332132232111411711131 pppsss消元得数值计算方法2022-3-27473332222111111411137,313113,33333222,2323,33,221,1284*2030*24*013ppppppppppppbbxxaabaxba xxx

35、aabaxaxxxa 回代解得132P84030430032211141170乘子换为数值计算方法2022-3-2748 由于消元过程中保存了元素由于消元过程中保存了元素lij,因此可在消元因此可在消元结束后对方程组的右端向量结束后对方程组的右端向量b进行变换。进行变换。 算法算法3.33.3 应用应用Gauss按比例选列主元消去法按比例选列主元消去法(不做矩不做矩阵行交换阵行交换)解解n阶线性方程组阶线性方程组Ax=b，其中，其中A=aijnn，b=a1,n+1,.,an,n+1T输入输入 方程组的阶数方程组的阶数n；增广矩阵；增广矩阵A,b。输出输出 方程组的解方程组的解x1,.,xn或系

36、数矩阵奇异的信息。或系数矩阵奇异的信息。数值计算方法2022-3-2749Step1 11,2,., ;maxijj nina i对求出每行的“大小”：s0,is 若则输出(A is singular);停机(1,2,., ) )TipiPPn给向量 赋初值 Step2 对对k=1,2,n-1做做step3-6. Step3 按比例选列主元按比例选列主元:求求r,使使 ,maxirrip kp kk i nppaass Step4 若若 ,则输出则输出(A is singular);停机。停机。,0rp kaStep5 若若kr, 则则tpk; pkpr; prtStep6 对对i=k+1,n

37、做做step7-8 数值计算方法2022-3-2750Step7 求乘子求乘子 ,iikp kp kpkaaaStep8 ,kjjkpjaiiippp对j=k+1,.,n(列),消元：aaaStep9 11ppbbStep10 112,3,.,ijiiippppjinba对(行)， bbStep11 若若 ,则输出则输出(A is singular);停机。停机。 否则，否则，,0npna,nnpnpnbxaStep12 ,11,.,2,1()/iiinpipjjp ij iinxbaxa ，Step13 输出输出(x1,x2,xn);停机。停机。 数值计算方法2022-3-27513.1.4

38、 Gauss-Jordan消去法消去法 解线性方程组解线性方程组(1.1)的的Gauss-Jordan消去法消去法就是无回代过程的就是无回代过程的Gauss消去法。消去法。 无回代过程无回代过程,即在消元过程的每一步将即在消元过程的每一步将主列主列中除主元以外的其余元素均消为零。中除主元以外的其余元素均消为零。 在实际计算中在实际计算中,第第k步消元之前不将主元交换步消元之前不将主元交换到（到（k,k）位置上，可以根据每一步选取的主元）位置上，可以根据每一步选取的主元所在位置找出方程组的解。所在位置找出方程组的解。 数值计算方法2022-3-2752Gauss消去法的计算公式：消去法的计算公式

39、： (1)(1)( )( )(1)(1)/()0,1,., ,1()1,., ()kkikikkkkikkkkijijikkjlaaaaal ajkn nkikn乘子列其中 =1,2,.n-1(步)；行(0),1,2,., ;1,2,., ,1ijijaain jn n规定：数值计算方法2022-3-2753Gauss-Jordan消去法的计算公式：消去法的计算公式： (1)(1)( )( )(1)(1),( )(1),(0/,1,2,. ,()01,2,. ,1,2,., ()1,2,. ,(),1,., ,1(),., ,1()kkkkkikikkkkkikkkkkkijijikijkki

40、jijijmaain iiain iiknin iiaam ajkn naajkn na乘子，步行列列其中),1,2,., ;1,2,., ,1ija in jn n( )( ),1,/,1,2,.,kknkkinikxaakn方程组的解为：数值计算方法2022-3-2754算法算法3.43.4 应用应用Gauss-Jordan列主元消去法解列主元消去法解n阶线形阶线形方程组方程组Ax=b,其中其中A=aijnn, b=a1,n+1,an,n+1T 输入输入 方程组的阶数方程组的阶数n；增广矩阵；增广矩阵A,b。输出输出 方程组的解方程组的解x1,.,xn或系数矩阵奇异的信息。或系数矩阵奇异的

41、信息。数值计算方法2022-3-2755Step4 对对i=1,n,iik(行行)做做 Step5-6 Step5 求乘子求乘子 ,/kikikikikamaaStep6 对对j=k+1,n+1(列列) ,kijijikijaaa aStep7 对对k=1,2,n求解求解 ,1,/kkkinikxaaStep8 输出（输出（x1,x2,xn）;停机。停机。Step1 对对k=1,2,n(步步)做做step2-4 Step2 选列主元：求选列主元：求ik,使使 11,1,.,.maxkkikikini iiaaStep3 若若 ,则输出则输出(A is singular);停机停机,0kika数

42、值计算方法2022-3-27563.1.5 3.1.5 矩阵方程的解法矩阵方程的解法 应用应用Gauss顺序消去法解矩阵方程顺序消去法解矩阵方程 AX=B其中其中A=aijnn，B=bijnm ， X=xijnm 数值计算方法2022-3-2757(1)(1)( )( )(1)(1)( )(1)(1)/()0,1,., (),1,2,.,1,., ()kkikikkkkikkkkijijikkjkkkijijikkjlaaaaal ajknbbl ajmkikn乘子列其中 =1,2,.n-1(步)；行(0)(0)( ,1,2,., );(1,2,., ;1,2,.,)ijijijijaa i

43、jnbbin jm规定：数值计算方法2022-3-2758由回代过程得方程由回代过程得方程AX=B解解X的计算公式为的计算公式为 (1)(1)(1)1()/,1,.,2,1;1,2,.,niiiijijikkjiik ixbaxain njm 其中 将逐步计算得到的将逐步计算得到的 存放到存放到aij的位置上，的位置上， 存放到存放到bij的位置上，最后的解的位置上，最后的解xij还可存放到还可存放到bij的的位置上。位置上。 ( )kija( )kijb数值计算方法2022-3-27593.1.6 Gauss消去法的矩阵表示形式消去法的矩阵表示形式 应用应用Gauss基本消去法（假设没有进行

44、行交基本消去法（假设没有进行行交换）解线形方程组换）解线形方程组AX=B (1)(1)1111,A bAbLA bAxL b 第一步消元后-11即L211111n111/2,.,.1iillaainl-11其中L，数值计算方法2022-3-2760(2)(2)1(1)(1)11221111221,AbLAbL LA bLAxL L b 第二步消元后-11即L2(1)(1)322222111/3,.,.1iinllaainl-12其中L，数值计算方法2022-3-2761(1)(1)1(2)(2)11111211111112121(1)(1)(1)11(1)11112121,.,.kkkkkkk

45、kkkkkkkAbLAbLL LA bLLAxLL L bAxbALLAbLL L b 第k-1步消元后-11-11=即L或写成其中L，( )( )1(1)(1)1111121111111112121( )( )( )111( )111112121,.,.kkkkkkkkkkkkkkkkkkkAbLAbL LL LA bL LLAxL LL L bAxbAL LLAbL LL L b 第k步消元后-11-11=即L或写成其中L，数值计算方法2022-3-2762(1)(1)1,11.1/1,.,1.1ikkkikkkkkn klaaiknll-1k其中L，(1)(1)1(2)(2)111112

46、11111112121(1)(1)(1)11(1)11112121,.,.(*).nnnnnnnnnnnnnnAbLAbLL LA bLLAxLL L bAxbALLAbLL L b 第n-1步消元后-11-11=即L或写成其中L，数值计算方法2022-3-2763 A(n-1)是一个上三角阵。回代过程是解上三是一个上三角阵。回代过程是解上三角形方程组角形方程组(*)。 矩阵矩阵 称为称为Gauss变换矩阵或消元矩阵变换矩阵或消元矩阵 。1kL可以把它写成：可以把它写成： 1TkkkLIl e其中其中I为为n阶单位阵阶单位阵 ,0.010.0Tke k1,0.0.Tkkknklll数值计算方法

47、2022-3-2764 特别地，若令特别地，若令x=x1,x2,xn, lik=xi/xk, i=k+1,n,则有则有11,.,0,.,0TkkL xxx这就是说，这就是说， 把把x 的后的后n-k个分量都消为零。个分量都消为零。1kL由于由于 ,因此有因此有 0Tk ke l TTkkkkIl eIl eI从而从而数值计算方法2022-3-2765k+1,knk11.11.1TkkkLIl ell其次，当其次，当ij时，由于时，由于 TTTTiji ijji ijjijL LIleIl eIlel eLLI数值计算方法2022-3-2766则有则有11211.(2)nniiLL LLLnI2

48、1313212,1111.1nnn nllllll2111(1)3132(1)1122(2)(1),112(1)(2)11221,1111.1nn nnnnnnaaaaaaaaaaaaL是一个单位下三角阵。是一个单位下三角阵。数值计算方法2022-3-2767(1)1112.nnALLA-11L因为因为记记A(n-1)=U，则有，则有 1112.nLLAU-11L因此因此121.nAL LL ULU 矩阵矩阵A被分解成一个单位下三角阵和一个上被分解成一个单位下三角阵和一个上三角阵的乘积。三角阵的乘积。 为使为使Gauss基本消去法能进行到底基本消去法能进行到底, 假定了主假定了主元全不为零，在

49、什么情况下这些主元全不为零元全不为零，在什么情况下这些主元全不为零? 数值计算方法2022-3-2768定理定理 在在Gauss消去法中消去法中,主元主元 全不为全不为零的充要条件是矩阵零的充要条件是矩阵A的顺序主子矩阵的顺序主子矩阵(1)(1)1122,.,kkkaaa111212122211121112212212.,.,.nnknnnnaaaaaaaaAaAAaaaaa都是非奇异都是非奇异,此处此处kn.数值计算方法2022-3-27693.2 直接三角分解法直接三角分解法3.2.1 矩阵三角分解矩阵三角分解 在在n阶矩阵阶矩阵A的顺序主子矩阵的顺序主子矩阵Ak(k=1,2,n-1)均非

50、奇异的假定下，均非奇异的假定下，Gauss消去法的消去法的消元过程消元过程能能进行到底。进行到底。 即可以把矩阵即可以把矩阵A分解成分解成 A=LU 其中其中L是一个是一个单位单位下三角阵，下三角阵，U是一个上三角阵。是一个上三角阵。数值计算方法2022-3-2770定义 若方阵若方阵A可以分解成一个下三角阵可以分解成一个下三角阵L和一个和一个上三角阵上三角阵U的乘积，即的乘积，即 A=LU (2.1) 则称这种分解为方阵则称这种分解为方阵A的一种的一种三角分解三角分解或或LU分解分解. 特别地特别地 若若L为单位下三角阵时，则称它为为单位下三角阵时，则称它为Doolittle分解；分解； 若

51、若U为单位上三角阵时，则称它为为单位上三角阵时，则称它为Crout分解。分解。 数值计算方法2022-3-2771 由上节知，若由上节知，若n阶方阵阶方阵A的顺序主子矩阵的顺序主子矩阵A1, A2,An-1均非奇异，则均非奇异，则Guass消去法的消元过程消去法的消元过程可以作出可以作出A的的Doolittle分解分解A=LU 。 矩阵三角分解唯一性矩阵三角分解唯一性 对任一非异对角阵对任一非异对角阵D，有，有 A=(LD)(D-1U)=LU 这也是这也是A 的一种三角分解。的一种三角分解。 这说明矩阵的三角分解并不唯一。这说明矩阵的三角分解并不唯一。 数值计算方法2022-3-2772 为了

52、讨论矩阵为了讨论矩阵A的三角分解的唯一性问题，的三角分解的唯一性问题，将将A分解成分解成A=LDR （2.2） 其中其中L、R分别为分别为单位单位下、上三角阵，下、上三角阵，D为一为一个对角阵。个对角阵。 称这种分解为矩阵称这种分解为矩阵A的一种的一种LDR分解分解。 定理定理1 1 n阶矩阵阶矩阵A有唯一的有唯一的LDR的充要条件是的充要条件是A的的顺序主子矩阵顺序主子矩阵A1,A2,An-1均非奇异。均非奇异。由此知道由此知道,在定理条件下在定理条件下, Doolittle分解、分解、Crout分解都是唯一的分解都是唯一的.数值计算方法2022-3-2773 如果对线性方程组如果对线性方程

53、组Ax=b的系数矩阵的系数矩阵A作出作出LU分解分解(由由A确定确定L和和U)， 那么该方程组可写成那么该方程组可写成 LUx=b 于是，解方程组（于是，解方程组（2.1）便等价于解下面的两个）便等价于解下面的两个方程组：方程组：Ly=b Ux=y 这就是解线性方程组的这就是解线性方程组的直接三角分解法直接三角分解法。 上述下、上三角形方程组，极容易求解。上述下、上三角形方程组，极容易求解。数值计算方法2022-3-2774 Gauss消去法的消元过程是将消去法的消元过程是将A的三角分解的三角分解和解方程组和解方程组Ly=b同时进行（注意同时进行（注意L是单位下三角是单位下三角阵，即作阵，即作

54、Doolittle分解），其回代过程是解方程分解），其回代过程是解方程组组Ux=y。 直接三角分解法是从矩阵直接三角分解法是从矩阵A的元素直接由关的元素直接由关系式系式A=LU确定确定L和和U的元素，不必像的元素，不必像Gauss消去消去法那样计算那些中间结果。法那样计算那些中间结果。数值计算方法2022-3-27753.2.2 Doolittle分解法分解法 LU 分解的紧凑格式分解的紧凑格式 求解线性代数方程组的三角分解法，起求解线性代数方程组的三角分解法，起源于高斯消去法的矩阵形式。源于高斯消去法的矩阵形式。反复计算反复计算,很浪费哦很浪费哦 数值计算方法2022-3-2776通过比较法

55、直接导出通过比较法直接导出L L和和U U的计算公式。的计算公式。思思路路 nnnnnnnnuuullaaaa.1.11.1111211111 ),min(1jikjkkiul jia数值计算方法2022-3-2777先计算先计算U的元素，后计算的元素，后计算L的元素：的元素：lU的第的第1行：行：11111111101 00,0nrrrual uu1211111 00,0jnjjrrjjruual uu11 ,1,2,., .jjuajn数值计算方法2022-3-2778112121212111121211101 00,00/;nrrrual ull ulaulL的第1列：11111,111

56、1101 00,0niirrii iirual ulll u1111/,2,3,., .iilauin数值计算方法2022-3-2779l再计算再计算U的第的第2行元素；行元素；l再再计算计算L的第的第2列元素；列元素；l数值计算方法2022-3-27801111 ( ,0) (1)nkkjkrrjkrrjkrrrkkrrjkkkjkkral ul urkll ul ul当时l计算计算U的第的第k行元素：行元素：,1,.,kkk kk nuuu11( ,0)nkkjkrrjkrrjkrrral ul urkl当时11 , ,1,.,kkjkjkrrjrual ujk kn数值计算方法2022-

57、3-2781l计算计算L的第的第k列元素：列元素：1,.,1,2,.,1:kkn kllkn1111 ( ,0) nkkikirrkirrkirrkikkkrkrrral ul ul ul urk u11 /, 1,2,., kikikirrkkkrlal uuikkn数值计算方法2022-3-2782利用上述计算公式便可逐步求出利用上述计算公式便可逐步求出U U与与L L的各元素的各元素1111),3 ,2(ikkikiiniylbybyl求解求解 Ly=b , 即计算即计算:数值计算方法2022-3-2783)1 ,2, 1(1niuxuyxuyxiinikkikiinnnnl求解求解 U

58、x=y , 即计算：即计算：数值计算方法2022-3-2784lLU分解的运算量：分解的运算量：321().3nO n计算计算U的第的第2行行n-1个元素个元素:(n-1)1（1项乘积）项乘积） 第第3行行n-2个元素个元素:(n-2)2（2项乘积）项乘积） 第第n行行1个元素个元素: 1(n-1)（n-1项乘积）项乘积）1132 (1) 1 (2) 2.2 (2) 1 (1)11 ()( 1)(1) (21)261 ();6nknnnnk nknnnnnnO n 数值计算方法2022-3-27853/3n 用直接三角分解法解用直接三角分解法解Ax=b大约需要大约需要 次乘除法。次乘除法。 )

59、, 2 , 1(0nkukk 显然显然, 当当 时时,解解Ax=b直直接三角分解法计算才能完成。接三角分解法计算才能完成。数值计算方法2022-3-2786 因此可采用与列主元消去法类似的方法，因此可采用与列主元消去法类似的方法，对矩阵进行行交换，则再实现矩阵的三角分解。对矩阵进行行交换，则再实现矩阵的三角分解。 设设A A为非奇异矩阵为非奇异矩阵, , 当当 时计算将中时计算将中断或者当断或者当 绝对值很小时，按分解公式计算绝对值很小时，按分解公式计算可能引起舍入误差的积累。可能引起舍入误差的积累。0kkukku数值计算方法2022-3-2787可见 L和和U中的三角零元素都不存储，就是中的

60、三角零元素都不存储，就是L的对的对角元素也因为都是角元素也因为都是1没有必要再记录在程序中，没有必要再记录在程序中，这样只用一个这样只用一个n阶方阵就可以把阶方阵就可以把L和和U贮存起来。贮存起来。 即：下三角（包括对角元即：下三角（包括对角元) )存储存储L L各元素各元素, ,而而上三角存储上三角存储U U的元素。的元素。 在计算机程序中常用这种方法解线性方程组。在计算机程序中常用这种方法解线性方程组。优点：节约存储空间。优点：节约存储空间。l矩阵分解的紧凑格式矩阵分解的紧凑格式数值计算方法2022-3-2788 再考察递推公式会发现再考察递推公式会发现A中任一元素中任一元素aij只在只在