第五章线性方程组求解的直接法

1、科学计算与数学建模科学计算与数学建模中南大学数学科学与计算技术学院中南大学数学科学与计算技术学院第五章第五章 小行星轨道方程计算问题小行星轨道方程计算问题 线性方程组求解的直接法线性方程组求解的直接法小行星轨道方程问题小行星轨道方程问题 5.1线性方程组直接解法概述线性方程组直接解法概述5.2直接解法直接解法5.3小行星轨道方程问题的模型求解小行星轨道方程问题的模型求解5.45.1.1 5.1.1 问题的引入问题的引入v 一天文学家要确定一颗小行星绕太阳运行的轨道，他在轨道平面内一天文学家要确定一颗小行星绕太阳运行的轨道，他在轨道平面内建立以太阳为原点的直角坐标系，其单位为天文测量单位，在建立

2、以太阳为原点的直角坐标系，其单位为天文测量单位，在5 5个个不同的时间对小行星作了不同的时间对小行星作了5 5次观察，测得轨道上的次观察，测得轨道上的5 5个点的坐标数据个点的坐标数据如下表：如下表： 表表 5.1.1 5.1.1 轨道上的轨道上的5 5个点的坐标数据个点的坐标数据 试确立小行星的轨道方程，并画出小行星的运动轨线图形。试确立小行星的轨道方程，并画出小行星的运动轨线图形。123455.7646.2866.7597.1687.4080.6481.2021.8232.5263.360 xy 5.15.1 小行星轨道方程问题小行星轨道方程问题 5.1.2 5.1.2 模型的分析模型的分

3、析 v 由开普勒第一定律知，小行星轨道为一椭圆，设椭圆的一般方程由开普勒第一定律知，小行星轨道为一椭圆，设椭圆的一般方程为：为： ，需要确定系数，需要确定系数 利用已知的数据，不妨设利用已知的数据，不妨设 欲确定系数欲确定系数 等价于求解一个线性方程组：等价于求解一个线性方程组： 可写成矩阵的形式：可写成矩阵的形式： 22123452221 0axa xy a ya xa y ,1,2,3,4,5;iai 1,2,3,4,5;iixyi ia221 12 1 13 14 15 1221 22 22324 252221 32 33334 353221 42 44344 454221 52 553

4、54 5552221 02221 02221 02221 02221 0axa x ya ya xa yaxa x ya ya xa yaxa x ya ya xa yaxa x ya ya xa yaxa x ya ya xa y AXb v其中，其中， ，2211 11112222 22222233 33332244 44442255 5555222222222222222xxyyxyxxyyxyAxxyyxyxxyyxyxxyyxy12345aaXaaa 11111b ， 5.1.3 5.1.3 模型的假设模型的假设 v 假设：假设： (1)(1)小行星轨道方程满足开普勒第一定律；小行星

5、轨道方程满足开普勒第一定律； (2)(2)以上所测得数据真实有效。以上所测得数据真实有效。 5.1.3 5.1.3 模型的模型的建立建立 v 该问题的模型为：该问题的模型为： 可见，解答上述问题就是对线性方程进行求解可见，解答上述问题就是对线性方程进行求解。 1234533.22377.47010.419911.52801.296039.513815.11151.444812.57202.404045.684124.64333.323313.51803.646051.380236.21276.380714.33605.052054.878549.781811.289614.81606.7200

6、aaaaa 11111 5.2 5.2 线性方程组直接解法概述线性方程组直接解法概述v 直接法：直接法：利用一系列递推公式计算有限步，能直接得到方程组的精利用一系列递推公式计算有限步，能直接得到方程组的精确解。当然，实际计算结果仍有误差，譬如舍入误差。舍入误差的积累确解。当然，实际计算结果仍有误差，譬如舍入误差。舍入误差的积累有时甚至会严重影响解的精度有时甚至会严重影响解的精度v 求解线性方程组最基本的一种直接法是求解线性方程组最基本的一种直接法是消去法消去法。这是一个众所周知。这是一个众所周知的古老方法，但用在现代电子计算机上仍然十分有效。消去法的基本思的古老方法，但用在现代电子计算机上仍然

7、十分有效。消去法的基本思想是，通过将一个方程乘或除以某个常数，以及将两个方程思想是，通想是，通过将一个方程乘或除以某个常数，以及将两个方程思想是，通过将一个方程乘或除以某个常数，以及将两个方程相加减这两种手续，过将一个方程乘或除以某个常数，以及将两个方程相加减这两种手续，逐步减少方程中的变元的数目，最终使每个方程仅含一个变元，从而得逐步减少方程中的变元的数目，最终使每个方程仅含一个变元，从而得出所求的解。其中出所求的解。其中高斯消去法高斯消去法是广泛应用的方法，其求解过程分为消元是广泛应用的方法，其求解过程分为消元过程和回代过程两个环节。消元过程将所给的方程组加工成上三角方程过程和回代过程两个

8、环节。消元过程将所给的方程组加工成上三角方程组。所归结的方程组再通过回代过程得出它的解。高斯消去法由于添加组。所归结的方程组再通过回代过程得出它的解。高斯消去法由于添加了回代的过程，算法结构稍复杂，但这种算法的改进明显减少了计算量。了回代的过程，算法结构稍复杂，但这种算法的改进明显减少了计算量。v 直接法比较适用于中小型方程组。对高阶方程组，即使系数矩阵是直接法比较适用于中小型方程组。对高阶方程组，即使系数矩阵是稀疏的，但在运算中很难保持稀疏性，因而有存储量大，程序复杂等不稀疏的，但在运算中很难保持稀疏性，因而有存储量大，程序复杂等不足。足。 5.3.1 5.3.1 高斯消去法高斯消去法v 消

9、去法是一个古老的求解线性方程组的方法。由它改进得消去法是一个古老的求解线性方程组的方法。由它改进得选主元法选主元法是目前计算机上常用的有效的求解低阶稠密矩阵线性方程组是目前计算机上常用的有效的求解低阶稠密矩阵线性方程组的方法。的方法。例例 5.3.1 5.3.1 用用 消去法解方程组消去法解方程组GaussGauss1231231232221(5.3.1)1324 (5.3.2)2539 (5.3.3)2xxxxxxxxx5.35.3 直接解法直接解法v解：第解：第 1 1 步，步， 加到加到 ， 加到加到 ，得等价方程组：得等价方程组： 第第 2 2 步，步， 加到加到 得等价的方程组：得等

10、价的方程组：35.3.12 （） （）（ 5.3.2）15.3.1()2 (5.3.3)123232322211(5.3.4)282(5.3.5)xxxxxxx 25.3.4（ 5.3.5）12323322211100(5.3.6)xxxxxx 第第 3 3 步，回代法求解步，回代法求解 即可求得该方程组的解为：即可求得该方程组的解为： 用矩阵法描述的约化过程即为：用矩阵法描述的约化过程即为：v 这种求解过程称为具有回代的这种求解过程称为具有回代的高斯消去法高斯消去法。v 此例可见此例可见GaussGauss消去法的基本思想是：用矩阵消去法的基本思想是：用矩阵A A的初等行变换将系数矩的初等行

11、变换将系数矩阵化为具有简单形式的矩阵（如上三角阵，单位矩阵等），而三角形方阵化为具有简单形式的矩阵（如上三角阵，单位矩阵等），而三角形方程组是很容易回代求解的。程组是很容易回代求解的。（5.3.6）32110,1,.2xxx 122133(1)3()21()222212 2 2101 11,3 2 41/202821 3 95/2rrrrrrAb 233(2)22 22101 110 0 10 0rrr 一般的，设有个未知数的线性方程组为：一般的，设有个未知数的线性方程组为： 11 11221121 1222221 122(5.3.7)nnnnnnnnnna xa xa xba xa xa x

12、ba xa xa xb 设设 则则 化为：化为： 为方便，为方便， 则消去法为：则消去法为： 第第1 1步：步： 计算计算 用用 乘乘 的第的第一方程加到第一方程加到第 个方程中去个方程中去 （即实行行的初等变换）（即实行行的初等变换） ，消去第消去第2 2个到第个到第n n个方程中的未知数个方程中的未知数 得得与与 等价方程组：等价方程组：1212)( , ,)( , ,)TTij n nnnAaXx xxbb bb（，5.3.7AXb ，(1)(1)()ijn nA Aa，111a0（），(1)11(1)11m(2,3,4),iiaina1 im5.3.7i2,3,)in（。11(2,3,

13、)iiR m RR in1,x5.3.7(1)(1)(1)(1)12(,)det0TnbbbbbA，(1)(1)(1)(1)111121(2)(2)(2)22222(2)(2)(2)2innnnnnnxaaabxaabxaab(5.3.8) 记为：记为： 其中其中 式中元素式中元素 为进一步需要计算的元为进一步需要计算的元素，公式为：素，公式为：(2)(2)AXb（5.3.8）(2)ija(2)(1)(1)(2)(1)(1)1 11 1( ,2,3),2,3,ijijijiiiaam ai jnbbm bin，v第第 ， 步，继续上述过程消元。设第步，继续上述过程消元。设第 步到第步到第 步计

14、步计算已完成，得到与原方程组等价的方程组：算已完成，得到与原方程组等价的方程组： 记为记为 ，下面进行第，下面进行第 步消元法：步消元法：k1,2,1kn11k(1)(1)(1)(1)1112111(2)(2)(2)222223( )( )( )( )( )( )nnkkkkkknknkkknknnnaaabxaabxxaabxaab (5.3.9)()( )KkAXbkv 设设 ，计算乘数，计算乘数 v 用用 中第中第 个方程加到第个方程加到第 个方程个方程 消去消去 中第中第 个方程个方程 的未知数的未知数 得到与原方程组等价的方程组：得到与原方程组等价的方程组： ()0kkka( )(

15、)(1,)kikkikkkamkkna ，ikm（ 5.3.9）ki1)ikn （， ，（ 5.3.9）i1)i kn （，kx(1)(1)(1)11121(1)1(2 )(2 )1222(2 )22()()(),1()(1)(1)1,11,(1)1(1),1(1)(1),nnkkkkkk kknkkkkkkknkkkn kkknn nnaaaxbaaxbaaabaabaxab(5.3.10)v 记为记为 其中其中 中元素计算公式为：中元素计算公式为： 最后，重复上述过程，即最后，重复上述过程，即 且设且设 共完成共完成 步消元计算，得到与步消元计算，得到与 等价的三角形方程组。等价的三角形方

16、程组。( 1)( 1)kkAX b(1)(1,kkAb）(1)( )( )(1)( )( )(1)(1)( )( ,1,)(1.)kkkijijikkjkkkiiik kkkkkaam ai jknbbm biknAAkbbk （ ）与前 行元素相同，与前 个元素相同(5.3.11)1,2,31;kn( )0(1 ,2,1 )kkkakn，1n（ 5.3.7）(1)(1)(1)(1)1111211(2)(2)(2)22222( )( )nnnnnnnnxaaabxaabxab(5.3.12) 再用回代法求解再用回代法求解 的解，计算公式为：的解，计算公式为： 元素元素 称为称为约化的主元素约化

17、的主元素。将。将 化为化为 的过程称的过程称为为消元过程消元过程。 由消元过程和回代过程求解线性方程组的方法称为由消元过程和回代过程求解线性方程组的方法称为Gauss Gauss 消去法消去法。 的求解过程的求解过程 称为称为回代过程回代过程。5.3.12（）( )( )( )( )1( )(),(1,2,1)nnnnnniiiijjj iiiiibxaba xxinna (5.3.13)( )kkka（5.3.7）（5.3.12）（ 5.3.12）5.3.13（）v 定理（定理（GaussGauss消去法）消去法）设设 若约化的主元素若约化的主元素 则可通过则可通过GaussGauss消去法

18、（不进行两行的初等变换消去法（不进行两行的初等变换两行交换位置）将方程两行交换位置）将方程组化为等价的三角形方程组组化为等价的三角形方程组 。消元和求解的计算公式为：。消元和求解的计算公式为： 1 1、消元计算、消元计算 2 2、回代计算、回代计算,n nAXb A R。( )0,1,2kkkakn（ 5.3.12）( )( )(1)( )( )(1)( )( )(1,)( ,1,)(1,)kikkikkkkkkijijikkjkkkiiikkamiknaaam ai jknbbm bikn,1,21kn( )( )( )( )1( )(),(1,2,1)nnnnnniiiijjj iiiii

19、bxaba xxinna 5.3.2 5.3.2 矩阵的三角分解矩阵的三角分解v 下面用矩阵理论进一步来分析下面用矩阵理论进一步来分析 Gauss Gauss消去法，设约化主元素消去法，设约化主元素 由于对由于对 实行的初等变换相当于用初等矩阵左乘实行的初等变换相当于用初等矩阵左乘于是，于是， 消去法第消去法第1 1步：步： , , 则有：则有：v v 其中：其中：v （ 为初等三角矩阵）为初等三角矩阵） (1)(1)(2)(2)A XbA Xb(1)(2)(1)(2)11L AALbb211110010001nmLm( )0(1,21)kkkakn，AAGauss1Lv Gauss消去法第消

20、去法第k步消元过程：步消元过程： v 则有则有v 其中：其中： ( )( )(1)(1),kkkkA XbAXb1,11111kkkn kkLmm第 列( )(1)( )(1),kkkkkkL AALbb(5.3.14)1,2,1kn利用递推公式则有：利用递推公式则有：由由 得得 : 11,11111kkkn kkLmm第 列(1)( )(1)( )122 1122 1,nnnnnnL LLLAAUL LLLbb(5.3.15)111121)nL LLULUA=(5.3.16)(5.3.15)v 其中其中v L L为由乘数构成的下三角阵为由乘数构成的下三角阵,U,U为上三角矩阵，为上三角矩阵，

21、 表明，表明，用矩阵理论来分析用矩阵理论来分析GaussGauss消去法，得到一个重要结果，即消去法，得到一个重要结果，即在在 条件下条件下GaussGauss消去法实质上是消去法实质上是A A将分将分解成两个三角矩阵的解成两个三角矩阵的(1)(1)(1)1112121(2)(2)2223132( )12111,1nnnnnnnaaamaaLmmUamm (5.3.16)( )0,(1,2)kkkakn.ALUv 显然，可由显然，可由GaussGauss消去法及行列式性质可知，如果消去法及行列式性质可知，如果 v 则有则有 其中其中 为顺序主为顺序主子式子式v 反之，可用归纳法证明：如果反之，

22、可用归纳法证明：如果A A的顺序主子式的顺序主子式 满足：满足：v 则则 ( )0(1,2)iiiaik，(1)(1)(2)( )1111122det)0,det( )0(2,3)iiiiAaAa aaik（iAdet()0(1,2,3)iAik ，( )0iiia 。1111111,iiiiiaaAaAaa（ ）v 定理定理 5.3.2 5.3.2 （矩阵的三角分解）（矩阵的三角分解）设设 ，如果，如果 的顺的顺序主子式有序主子式有 ，则，则 可分解为一个单位下三角可分解为一个单位下三角矩阵与一个上三角矩阵的乘积，即矩阵与一个上三角矩阵的乘积，即 且分解是唯一的且分解是唯一的。n nARAd

23、et( )0(1,n-1)iAi AALU，v 证明证明 现仅就现仅就 来证明唯一性，存在性上面已证。来证明唯一性，存在性上面已证。假若假若 且对且对 非奇异时考虑，非奇异时考虑， 为单位下三为单位下三角阵，角阵， 为上三角阵，由假设知为上三角阵，由假设知 存在（因为存在（因为 可逆可逆 故故 可逆），从而由可逆），从而由 有有 ，上式右端，上式右端为上三角阵，左边为单位下三角阵，因此左右两端应为单位矩阵。故为上三角阵，左边为单位下三角阵，因此左右两端应为单位矩阵。故 即分解是唯一的。即分解是唯一的。v 称矩阵的三角分解称矩阵的三角分解 （杜利特尔）分解。（杜利特尔）分解。det( ) 0(1

24、,1)iAin11ALULU（5.3.17）A1,L L1,U U11U1det0,AL1 1A LU，1U（5.3.17）11,LL UUALUDoolittle为1111L LUU 其中其中v 在以上定理条件下，同样可有下面的三角分解：在以上定理条件下，同样可有下面的三角分解： ，其中，其中L L为为下三角矩阵，下三角矩阵，U U为单位上三角矩阵，称之为为单位上三角矩阵，称之为CroutCrout（克劳特）分解（克劳特）分解。11121212221211,1nnnnnnuuuluuLUlluALUv 如前例中系数矩阵如前例中系数矩阵A A的分解为：的分解为： 现设现设 ，若如分解，若如分解

25、 ，则，则 而求解这两个三角形方程组是很容易的。而求解这两个三角形方程组是很容易的。122222233241112139101212ALUAXbALU(1)AXbLUXbLYb (2)UXYXv 定理定理 5.3.3 5.3.3 v 设设A A为为n n阶非奇异矩阵，则用阶非奇异矩阵，则用GaussGauss消去法解消去法解 所需要的乘所需要的乘除法次数及加减法的次数分别为：除法次数及加减法的次数分别为：AXb33231333(2)(1)(25)/63nnnMDnnASn nn（）5.3.35.3.3 Gauss Gauss消去法的计算量消去法的计算量v 但如果用但如果用 （克莱姆）法则解（克

26、莱姆）法则解 ，就需要计算，就需要计算 个个n n阶阶行列式，若行列式用子式展开，总共需要行列式，若行列式用子式展开，总共需要 次乘法，如次乘法，如 时时 消去法需要消去法需要430430乘除法，而克莱姆法则却需要乘除法，而克莱姆法则却需要3991680039916800次乘次乘法，由此可见，法，由此可见， 法则方程组的工作量太大，不便于使用。如果法则方程组的工作量太大，不便于使用。如果计算是在每秒作计算是在每秒作 次乘除法计算机上进的，那么用次乘除法计算机上进的，那么用 消去法解消去法解2020阶方程组约需阶方程组约需0.030.03秒即可完成，而用秒即可完成，而用 法则大约需法则大约需 小

27、时才能完成（大约相当于小时才能完成（大约相当于 年）可见，年）可见， 法则完全不适于在法则完全不适于在计算机上求解高维方程组。计算机上求解高维方程组。GramerAXbn1(n1)!10n 510Gauss111.3 10710GramerGaussGramerGramerv 用用GaussGauss消去法解消去法解 时，设时，设A A非奇异，但可能出非奇异，但可能出现现 ，这时必须进行行交换的这时必须进行行交换的GaussGauss消去法，但在实消去法，但在实际计算中即使际计算中即使 ，但其绝对值很小时，用但其绝对值很小时，用 作除数，作除数，会导致中间结果矩阵会导致中间结果矩阵 的元素数量

28、级严重增长和舍入误的元素数量级严重增长和舍入误差的扩散，使最后结果不可靠。差的扩散，使最后结果不可靠。例例5.3.25.3.2 设有方程组设有方程组bAX kA12120.000112xxxx5.3.4 Gauss主元素消去法主元素消去法 0kkka 0kkka kkkav解解 方程组得解方程组得解v方法一：用方法一：用Gauss消去法求解。消去法求解。（用具有舍入的（用具有舍入的3位浮点数进行运算）位浮点数进行运算） 回代得解回代得解 ， ，与精确解比较，这结，与精确解比较，这结果很差。果很差。*(0.99989999,1.00010001)X 0.000100 1 1,11 2Ab2110

29、000m 0.000100110100001000021.00 x 10.00 x v方法二：用具有行交换的方法二：用具有行交换的Gauss消去法（避免小消去法（避免小主元）主元） 回代得解：回代得解：v这个解对于具有舍入的这个解对于具有舍入的3位浮点数进行计算，是位浮点数进行计算，是一个很好的结果。一个很好的结果。v方法一计算失败的原因，是用了一个绝对值很小方法一计算失败的原因，是用了一个绝对值很小的数作除数，乘数很大，引起约化中间结果数量的数作除数，乘数很大，引起约化中间结果数量误差很严重增长，再舍入就使得计算结果不可靠误差很严重增长，再舍入就使得计算结果不可靠了。了。12211 2112

30、,0.0001000.000100 1 10 1.001.00Ab rrm 211.00,1.00 xxv这个例子告诉我们，在采用高斯消去法解方程组这个例子告诉我们，在采用高斯消去法解方程组时，小主元可能导致计算失败，故在消去法中应时，小主元可能导致计算失败，故在消去法中应避免采用绝对值很小的主元素。避免采用绝对值很小的主元素。 v对一般矩阵方程组，需要引进主元的技巧，即在对一般矩阵方程组，需要引进主元的技巧，即在高斯消去法的每一步应该选取系数矩阵或消元后高斯消去法的每一步应该选取系数矩阵或消元后的低阶矩阵中的绝对值最大的元素作为主元素，的低阶矩阵中的绝对值最大的元素作为主元素，保持乘数保持乘

31、数 以便减少计算过程中的舍入误以便减少计算过程中的舍入误差对计算解的影响。差对计算解的影响。ikm1v 这个例子还告诉我们，对同一个数值问题，这个例子还告诉我们，对同一个数值问题，用不同的计算方法，得到的精度大不一样，一个用不同的计算方法，得到的精度大不一样，一个计算方法，如果用此方法的计算过程中舍入误差计算方法，如果用此方法的计算过程中舍入误差得到控制，对计算结果影响较小，称此方法为数得到控制，对计算结果影响较小，称此方法为数值稳定的；否则，如果用此计算方法的计算过程值稳定的；否则，如果用此计算方法的计算过程中舍入误差增长迅速，计算结果受舍入误差影响中舍入误差增长迅速，计算结果受舍入误差影响

32、较大，称此方法为数值不稳定。因此，我们解数较大，称此方法为数值不稳定。因此，我们解数值问题时，应选择和使用数值稳定的计算方法，值问题时，应选择和使用数值稳定的计算方法，否则，如果使用数值不稳定的计算方法去解数值否则，如果使用数值不稳定的计算方法去解数值计算问题，就可能导致计算失败。计算问题，就可能导致计算失败。v 设有线性方程组，其中为非奇异矩阵。方程组得增广矩阵为设有线性方程组，其中为非奇异矩阵。方程组得增广矩阵为 第第 步步 ：首先在：首先在 中选主元素，即选择中选主元素，即选择 使使 ，再交换再交换 的第一行与第的第一行与第 行元素，交换行元素，交换 的第一列与第的第一列与第 列元素列元

33、素（相当于交换未知数（相当于交换未知数 与与 ），将），将 调到调到 位置（交换后的增广矩位置（交换后的增广矩阵为阵为 ，其元素仍记为，其元素仍记为 ，然后进行消元法计算。，然后进行消元法计算。 5.3.5 完全主元素消去法完全主元素消去法1 111121121222212.nni jnnnnnaaabaaabaAbaaab，11k （）A11ij， ，1 1110maxi nj ni jijaa A b（，）1iA1j1x1jx1 1i ja11（， ）A b，ijiab，v 第第 步：继续上述过程，设已完成第步：继续上述过程，设已完成第 步到第步到第 步计算，步计算， 约化约化为下述形式（

34、为简单起见，仍记为下述形式（为简单起见，仍记 元素为元素为 元素为元素为 ）：）：域 v 于是第于是第 步计算：对于步计算：对于 按下述步骤从按下述步骤从 计算到计算到k11kAb，kA（ ）kijab（），ib,A b1112112222nnkkknknknnnaaabaabaabaab第第 步主元区域步主元区域kkk=12n-1 ， ， ， 1 3 （1）选主元素：选择）选主元素：选择 使使 （2）如果）如果 ，则交换，则交换 第第 行与第行与第 行元素，行元素，如果如果 ，则交换，则交换 的第的第 列与第列与第 列元素。列元素。 （3）消元计算）消元计算,kkij,0maxkkk i n

35、k j nijijaa kik,A bkkikjkAkkj,(1,., )ikikkkamikna ijaibijaikkjm a(,1,., )i j kn ibik kmb(1 ,., )i kn （4）回代求解。经过上面的过程，即从第）回代求解。经过上面的过程，即从第 步到第步到第 步完成选主元，交换两行，交换两列，消元计算，步完成选主元，交换两行，交换两列，消元计算，原方程组约化为：原方程组约化为：其中其中 为未知数为未知数 调换后的顺序。回代调换后的顺序。回代求解：求解：1n-1111211122222nnnnnnaaaybaaybayb 12.ny yy，1(),(1,.,2 ,1

36、)nnnnniijjjiiiibyabayyina 12.nxxx， 5.3.6 列主元消去法列主元消去法v 完全主元素消去法完全主元素消去法是解低阶稠密矩阵方程组的有效是解低阶稠密矩阵方程组的有效方法，但完全主元素方法在选主元时要花费一定的时间。方法，但完全主元素方法在选主元时要花费一定的时间。现介绍一种在实际计算中常用的部分选主元，（即列主现介绍一种在实际计算中常用的部分选主元，（即列主元）消去法。元）消去法。列主元消去法列主元消去法，即是每次选主元时，仅依，即是每次选主元时，仅依次按列选取绝对值最大的元素作为主元素，且仅交换两次按列选取绝对值最大的元素作为主元素，且仅交换两行，再进行消元

37、计算。行，再进行消元计算。 设列主元消去法已经完成第设列主元消去法已经完成第 步到第步到第 步的按列选步的按列选主元，交换两行，消元计算得到与原方程组等价的方程主元，交换两行，消元计算得到与原方程组等价的方程组：组： 1k-1v ( )kA(1)(1)(1)11121(2)(2)222( )( )( )( )nnkkkkknkknknnaaaaaaaaa(1 )1( 2 )2()()kkkknbbbbb第第 步选主元区域步选主元区域kv第第 步计算如下：对于步计算如下：对于 , 按下述步骤按下述步骤从从 计算到计算到 按列主元，即确定按列主元，即确定 使使 如果如果 ，则，则 为非奇异，停止计

38、算。为非奇异，停止计算。 如果如果 ，则交换，则交换 第第 行第行第 行元素行元素 消元计算：消元计算：kk=12n-1 ， ， ， 1 4 1ki,0maxkikikk i naa 2 3 4,0ki kaAkik,A bkikikaijaib,(1,. )ikikkkma ai kn ijaibikm*kja( ,1,. )i jkn ikm*kb(1,. )ikn （5）回代计算：回代计算： 计算解计算解 在常数项内在常数项内 得到得到例例 5.3.3 用列主元消去法求解方程组用列主元消去法求解方程组解解 精确解为（舍入值）：精确解为（舍入值）：nnnniijjiij ib / aba

39、b/ anibb = +1(1,.2,1)in 12, .nx xx nb1231231230.7290.810.90.68670.83381.3311.211.11.000 xxxxxxxxx*(0.2245,0.2841,0.3279)Tx 0.7290 0.8100 0.9000 0.6867,1.0001.0001.0000.83381.3311.2101.1001.000Ab132131(,0.7513,0.5477)rr mm回代计算得到计算解：回代计算得到计算解： 本例是具有舍入的位浮点数进行运算，所得的计算解还是比较准本例是具有舍入的位浮点数进行运算，所得的计算解还是比较准确的

40、。确的。 下面是完全主元素消去法框图（图下面是完全主元素消去法框图（图 ） 32321.3311.2101.1001.00000.090900.17360.0825000.14730.29750.1390,0.61711.3311.2101.1001.00000.14730.29750.1390000.010000.003280rrm0.2246,0.2812,0.3280Tx 5.3.1输入输入 选主元素选主元素 否否是是否否交换行交换行输出输出 否否交换列且交换列且消元计算消元计算回代回代（当 ）调整求解调整求解输入计算解输入计算解nb cA， ZII1 ,2,nI ,maxk i nkj

41、 nik jkaija ,ik jka0ck=12n-1 ， ， ，0cdet0A0nna1,.2,1nnnniiijjiibbabba xainki kkjk( )( )kIZ KIZ j1,.(1,. )ikikikkkijijikkjiiikkamaaaam abbm biknjkn1knstop 1,2.x i in1 2 .ixIZ Gbin（），stop图图5.3.1 完全主元素消去法框图完全主元素消去法框图v 用完全主元素消元法解用完全主元素消元法解 ，可用一整型数组，可用一整型数组 开始开始记录未知数记录未知数 次序，即次序，即 ，最后记录，最后记录调整后未知数的足标。系数阵调

42、整后未知数的足标。系数阵 存在二维数组存在二维数组 内，常数项内，常数项 存在存在 内，解存在数组内，解存在数组 内。内。v 例例 5.3.4 若在计算过程中，只取若在计算过程中，只取3位有效数字，试用列位有效数字，试用列主元素法求解：主元素法求解：AX b IZ n12.nxxx， ， 12.IZ nn ，AA nn，b b nnX1231231230.501.103.106.005.3.182.004.500.360.025.3.195.000.966.500.965.3.20 xxxxxxxxxv 解解 第一步，选第一步，选 为主列元，将为主列元，将 对调位置，对调位置， v 第二步，选

43、第二步，选 为列主元，不需换行，为列主元，不需换行， 5.005.3.185.3.201231231235.000.966.500.965.3.182.004.500.360.025.3.190.501.103.106.005.3.20 xxxxxxxxx21312.000.500.40,0.105.005.00mm*2123*31235.3.19m5.3.184.122.240.3645.3.19 5.3 20m5.3.181.002.455.905.3.20 xxxx。4.12321.000.2434.12m *325.3.20m5.3.19*32.995.995.3.20 x v 由由

44、回代求解得：回代求解得： 与原方与原方程组准确解程组准确解 比较，可知，本题用比较，可知，本题用3位有效数位有效数字计算的列元素法是相当精确的。大量实践表明：列主元法为解线字计算的列元素法是相当精确的。大量实践表明：列主元法为解线性方程组的精确方法。性方程组的精确方法。v 下面用矩阵运算来描述列主元素法下面用矩阵运算来描述列主元素法v 记记 是初等排列阵（由交换单位矩阵是初等排列阵（由交换单位矩阵 的第的第 行与行与 行所得）。行所得）。则列主元素法为：则列主元素法为：v 其中其中 的元素满足的元素满足 ，由，由 得：得： *5.3.18 5.3.195.3.203212.001.002.60

45、 xxx，1232.601.002.00 xxx，,kk iIIkki11(1)(2)(1)(2)1 1,1 1,( )(1)( )(1),5.3.21,kkiikkkkkk ikk iL IAAL IbbL IAAL IbbkLikm1 k 12n-1 ， ， ，5.3.21121( )11,22,1 1,nnnniiiLIL IL IAAU 简记为：简记为： ，其中，其中 。 下面考察下面考察 时的时的 其中，其中， 则由排列阵性质（左乘矩阵是对矩阵进行行变化。）则由排列阵性质（左乘矩阵是对矩阵进行行变化。）( )nPA U Pbb，12111,2 2,1 1,nnniiiP L ILIL

46、I4nP。32133322332143 3,2 2,1 1,3323321233213 2 1(5.3.22)iiiiiiiiiiiiU ALI LI LI AL ILIIIL IIIIIALLLPA （），322333321132123232333321iiiiiiiiiLIILIILILILLP III，v 已知已知 为单位下三角阵，其元素绝对值为单位下三角阵，其元素绝对值 ，记，记 。由由 得：得： 。其中。其中 为排列阵，为排列阵， 为单位下三角阵，为单位下三角阵， 为上三角阵。为上三角阵。v 这表明，对这表明，对 应用列主元素法相当于对应用列主元素法相当于对 先进行一系列行变先进行一

47、系列行变换后对换后对 再应用再应用 消去法。再实际计算中我们只能在计消去法。再实际计算中我们只能在计算过程中，做关于行的变换。有结论：算过程中，做关于行的变换。有结论：v 定理定理5.3.4 （列主元素三角分解定理）（列主元素三角分解定理）v 若若 为非奇异性矩阵，则存在排列矩阵为非奇异性矩阵，则存在排列矩阵 使使 。其中。其中 为单为单位下三角阵，位下三角阵， 为上三角阵。为上三角阵。v 存放在存放在 的下三角部分，的下三角部分， 存放在存放在 的上三角部分。由整数的上三角部分。由整数型数组记录可知型数组记录可知 的情况。的情况。(1,2,3)kL k 11321LL L L （5.3.22

48、）PALUPLUbAX A|bbPAXPaussGAPPA=LULULAUAP 5.3.7 Gauss-Jordan 消去法消去法v 消去法总是消去对角线下方的元素。现考虑一种消去法总是消去对角线下方的元素。现考虑一种修正，即消去对角线下方和上方的元素。这即为修正，即消去对角线下方和上方的元素。这即为 消去法。消去法。 设用设用 消去法已完成消去法已完成 步，于是步，于是 化为等价方程化为等价方程组组 其中：其中： GaussGauss Jordan G JG Jk-1Ax b kkA xb 1,1,11,1,1|11|knkkkkknk kk nkn kn nnaabaaAbaabaabv

49、在第在第 步计算时，考虑对上述矩阵的第步计算时，考虑对上述矩阵的第 行上、下都进行消元计算行上、下都进行消元计算 1、按列选主元素，即定义按列选主元素，即定义 使使 2、换行（当换行（当ikk）。交换）。交换A,b第第k行与第行与第ik行元素。行元素。 3、计算乘数计算乘数 ( 可存可存放在放在 的单元中的单元中) （ ） 4、消元计算计算主元素消元计算计算主元素 kk1,2,knki,maxkikikkinaa /1,1/ikikkkkkkkma aini k ma 1ikmikaikm1,11,ijikkjijiikkiam aa in jkn ikbm bb inik （ 且）（ 且）v

50、 5、计算主元素计算主元素 上述过程全部执行完后有：上述过程全部执行完后有： 这表明这表明 用方法将用方法将 约化为单位矩阵，计算解就在常数项位置约化为单位矩阵，计算解就在常数项位置得到，因此用不着回代求解。用得到，因此用不着回代求解。用 方法接方程组的计算量大约需方法接方程组的计算量大约需要要 次乘除法，要比次乘除法，要比 消去法大些。但用消去法大些。但用 方法求一个矩方法求一个矩阵的逆矩阵还是比较合适的。阵的逆矩阵还是比较合适的。 ,1kjkkkjkkkka majk knb mb（ ）1(1 )(1 )211,1kknbbA bAbb G JAGJ3/2nGaussG Jv 定理定理 （

51、G-J法求逆矩阵）法求逆矩阵） 设设 的逆矩阵的逆矩阵 ，即求，即求 阶阶矩阵矩阵 ，使，使 其中其中 为单位矩阵，将为单位矩阵，将 按列写按列写成成 ， 为列向量，为列向量， 为单位列向量。为单位列向量。于是求解于是求解 ，等价于求解，等价于求解 个方程个方程组：组： ，所以我们可以用，所以我们可以用 法求法求解解 。v 例例 5.3.5 对对 求求 。A1AnXnA X InIX1212, , , , ,nnnXx xx Ie eeixienAXIn1,2,iiAxe inG JnAXI1826 49104 345A 1Av 解解 1821 0 06 49100 1 034 3450 0

52、11821 0 0( 1)16491001 04 34500 1AIr 18 21 0 06120 1 26 1 040 2 34 0 113rrrr 10184980821012610( 2)00182123rrrr 故：故： 100952818( 1)330101032( 2)32001821( 18)31rrrrrr 95281811032821A 5.3.8 直接三角分解直接三角分解v 为求解为求解 将将 进行进行 分解。即分解。即 将原问题转将原问题转化为求解两个三角形方程组化为求解两个三角形方程组 求求 求求 。 v 不选主元的三角分解法不选主元的三角分解法v 设设 且有且有 其中

53、其中 为单位下三角阵，为单位下三角阵， 上三角上三角阵。即阵。即 AXbAL U、A LU，1 Lyb（ ）(2)Uxyyx Adet0AA LULU111212122231321231111nnnnnnnuuuluuAllulll（5.3.23）v 下面说明：下面说明： 的元素可由的元素可由 步直接计算出来，其中第步直接计算出来，其中第 步定出步定出 的第的第 行和行和 的第的第 列元素。列元素。v 由由 有：有： 得得 的第的第1行元素行元素 得得 的第的第1列元素到第列元素到第 列元素。由列元素。由 利用矩阵乘法有：利用矩阵乘法有： 故故 L U、nrUrLr5.3.23（）11(1,2

54、, ) 5.3.24iiauinU11111 111(2,3, , ) 5.3.25iauiiial ulinL1r 5.3.23111(0)nrrirkkirkkirirkkkal ul uurkl时11,1,rririrkkikual uir rn(5.3.26) 又由又由 有：有： 故：故： 因此可得因此可得 的第的第 行和第行和第 列的全部元素。列的全部元素。5.3.23111nririkkrikkrirrrkkal ul ul u11(,1,)ririkkrkrral uuirlir rnUrr(5.3.27)LULybUxy、 确定后，求解和的计算公式为：11111(5.3.28)

55、(2,3, )(1,2,1)(5.3.29)nnnniikkkiiiiiiikkkyunyuxuiybybl yinxxinn 直接分解法约需直接分解法约需 乘除法，和乘除法，和 消去法计算量基本相当。对消去法计算量基本相当。对计算计算 和式，可采用双精度累加以提高精度。和式，可采用双精度累加以提高精度。v （B）选主元的三角分解法）选主元的三角分解法 在直接三角分解中，如果在直接三角分解中，如果 计算将要中断，或者当计算将要中断，或者当 绝绝对值很小时，按分解公式计算可能引起舍入误差的积累。但当对值很小时，按分解公式计算可能引起舍入误差的积累。但当 为为非奇异时，可通过交换非奇异时，可通过交

56、换 的行实现矩阵的行实现矩阵 的的 分解。因此可采用分解。因此可采用与列主之消去法类似的方法将直接三角分解法修改为部分选主之的与列主之消去法类似的方法将直接三角分解法修改为部分选主之的三角分解法。三角分解法。 设已完成第设已完成第 步分解，这时有：步分解，这时有： 33nGauss0rru rruAAPALU1r 11121212223132331,11,112,1nnrrrnr rrrrnnnn rnrnnuuuluulluuuAlaalllaav 第第 步分解需要到步分解需要到 两式，为避免两式，为避免 中中 用小的数用小的数 作除数，先引进量：作除数，先引进量： 由由 及及 定义，易见定

57、义，易见 则由则由 有：有： 若若 ，则我们可以用，则我们可以用 作为作为 交换交换 的第的第 行与行与 行（但我们将交换后的新元素仍记为行（但我们将交换后的新元素仍记为 及及 ）于）于是有是有 。控制了误差传播，再进行第。控制了误差传播，再进行第 步步分解。分解。 对一般的非奇异矩阵对一般的非奇异矩阵 求逆的方法：求逆的方法： 则：则：r（ 5.3.26） （ 5.3.27）（5.3.27）rrurru11(,1 , , )riirik krkS al ui rrn ，（ 5.3.26）iSrrruS（ 5.3.27）(1,)irSSirlirnmaxriir i nSSriSrruArri

58、ijlija1(1, )irlirn rAPA LU111AU L P 5.3.9 平方根法平方根法v 利用对称正定矩阵的三角分解而得到的求利用对称正定矩阵的三角分解而得到的求解对称正定方程组的一种有效方法解对称正定方程组的一种有效方法平方根平方根法法 设设 为对称阵，即为对称阵，即 ，且，且 的所有顺序主子式均的所有顺序主子式均非零，则知非零，则知 可以唯一分解为：可以唯一分解为： 为利用为利用 的非奇异性，将的非奇异性，将 再分解为：再分解为：ATAAAAALUUU11211111,1,111220111nnnnnuuuuuunnuuUDUu 为对角矩阵，为对角矩阵， 为单位上三角阵，则：

59、为单位上三角阵，则： 又又 ，由分解的唯一性即得：，由分解的唯一性即得： 代入上代入上面面 中得：中得： 。 定理定理 5.3.6 （对称阵的三角分解）设（对称阵的三角分解）设 为为 阶对称阵，阶对称阵，且且 的所有顺序主子式均非零。则的所有顺序主子式均非零。则 可唯一分解可唯一分解为：为： 。其中。其中 为单位下三角阵，为单位下三角阵， 为对角阵。为对角阵。 当当 为对称正定矩阵时，则为对称正定矩阵时，则 的所有顺序主子的所有顺序主子式式 ，而，而 设设 ，则，则 于是于是：D0U0A LU LDU（ 5.3.30）0TTTAAUDL（）0TUL（ 5.3.30）TALDLAnAATA LD

60、LLDAA0iD TA LDL。12(,),nDdiag d dd1110,0(2,3, )iiDDidDdin从而：从而： 其中其中 为下三角阵。为下三角阵。12nddDd111/21/222nnddddD Ddd1/21/21/21/21 1)(TTTTALDLLD D LLDLDLL（）1/21LLDv 定理定理 5.3.7 （对称正定矩阵的（对称正定矩阵的 分解）分解） 若若 为为 阶对称正定矩阵，则存在一个实的非奇异阶对称正定矩阵，则存在一个实的非奇异下三角矩阵下三角矩阵 ，使，使 。当限定。当限定 的对角元素为正时，的对角元素为正时，这种分解是唯一的。这种分解是唯一的。 下面来考虑