线性方程组的直接法21

1、第1页第二章线性方程组的直接法在近代数学数值计算和工程应用中，求解线性方程组是重要的课题。例如，样条插值中形成的 K K 关系式，曲线拟合形成的法方程等，都落实到解一个盒元线性方程组，尤其是大型方程组的求解，即求线性方程组(2.12.1 )的未知量7；- 的数值。其中 aiai j j，bibi 为常数。上式可写成矩阵形式AxAx = = b b，即向量。当 detA=DOdetA=DO 时，由线性代数中的克莱姆法则，方程组 v v 上的解存在且惟一，且 有为系数矩阵匸的第：列元素以=代替的矩阵的行列式的值。克莱姆法则在建立线性方程组解的理论基础中功不可没，但是在实际计算中，我们难以承受它的计

2、算量。例如，解一个 100100 阶的线性方程组， 乘除法次数约为(101101 -100-100! 9999),即使以每秒 1 1* *的运算速度， 也需要近年的时间。在石油勘探、天气预报等问题中常常出现成百上千阶的方程组，也就产生了各种形式方程组数值解法的需求。研究大型方程组的解是目前计算数学中的一个重要方向和课题。解方程组的方法可归纳为直接解法和迭代解法。从理论上来说，直接法经过有限次四则运算，假定每一步运算过程中没有舍入误差，那么，最后得到方程组的解就是精确解。但是,这只是理想化的假定， 在计算过程中，完全杜绝舍入误差是不可能的，只能控制和约束由有限位算术运算带来的舍入误差的增长和危害

3、，这样直接法得到的解也不一定是绝对精确的。厲 E 九旳 +-+兀血=曾(2.1(2.1)口11如%f、坷函1农33泾*円】%叽(2.2(2.2)其中，-为系数矩阵,为解向量为常数第2页迭代法是将方程组的解看作某种极限过程的向量极限的值，像第 2 2 章中非线性方程求解一样，计算极限过程是用迭代过程完成的，只不过将迭代式中单变量 一十一一小换成向量而已。在用迭代算法时，我们不可能将极限过程算到底，只能将迭代进行有限多次，得到满足一定精度要求的方程组的近似解。在数值计算历史上，直接解法和迭代解法交替生辉。一种解法的兴旺与计算机的硬件环 境和问题规模是密切相关的。一般说来，对同等规模的线性方程组，直

4、接法对计算机的要求 高于迭代法。对于中等规模的线性方程组二丄.，由于直接法的准确性和可靠性高，一般都用直接法求解。对于高阶方程组和稀疏方程组（非零元素较少），一般用迭代法求解。消元法一、三角形方程组的解形如下面三种形式的线性方程组较容易求解。对角形方程组(2.3(2.3)设、八，对每一个方程， I I 厂厂显然，求解 n n 阶对角方程的运算量为-?o oF F 三角方程组第3页(2.4(2.4)按照方程组的顺序，从第一个方程至第 个方程，逐个解出第4页由方程_-，得-_1-1-。将心的值代入到第二个方程将H 亠.的值代入到第:个方程坳-包-以习3 -1,2,-j-i计算几需要：次乘法或除法运

5、算，一- -。因此，求解过程中的运算量为上三角方程组%磚（2.52.5）与计算下三角方程组的次序相反，从第卞个方程至第一个方程，逐个解出将?& 的值代入到第 1 1 个方程得解的通式计算几需要；一 + 次乘法或除法运算-。因此求解过程中的运算量为消元法的基本思想就是通过对方程组做初等变换，把一般形式的方程组化为等价的具有上述形式的易解方程组。由第斗个方程，。将入的值代入到第- 个方程第5页高斯消元法与列主元消元法高斯消元法高斯消元法是我们熟悉的古老、简单而有效的解方程组的方法。下面是中学阶段解二元 方程组（高斯消元法）的步骤:(2.6(2.6)(2.7(2.7)方程（2.62.6）乘以

6、一 3 3 加到第（2.72.7）个方程中得羽.人代入（2.62.6）得石 2 2。其方法相当于对方程组的增广矩阵做行的初等变换:亠已是上三角矩阵，而为原方程组的等价方程组，已化成易解的方程组形式。再用回代方法求解，得到:x2= 1, = 2这就是高斯消元法解方程组的消元和回代过程。一般地，可对线性方程组（2.12.1 ）施行以下一系列变换；（1 1）对换某两个方程的次序；（2 2）对其中某个方程的两边同乘一个不为零的数；（3 3）把某一个方程两边同乘一个常数后加到另一个方程的两边。 记变换后的方程组为：+知可十+芯耳=、a21Jcl叫 Mu+*耳召=暫內+ -+耳后=叽(2.82.8)第6页

7、显然方程组(2.12.1)与(2.82.8)是等价方程组，或者说它们有相同的解。分别记方程组(2.12.1)与(2.82.8)的增广矩阵为：(1)(1)对换某两行元素;(2)(2)中的某行乘一个不为零的数；(3)(3)把 CV)CV) 的某一行乘一个常数后加到另一行。高斯消元法就是通过以上(3 3)的变换，把化为等价的上三角形式。F F 面我们以=丄为例演示消元过程。设方程组:111十直匕工2 *- 13-3斗= 口也汕五+如乜十住妇玛十釐魚兀ib2勺込1+气丹5内*知珥弋 盘和可+422*直护+盘卵天斗=3頁其增广矩阵为:(1(1)若 1 -，则将第一行乘以； 加到第二行上；将第一乘以可以看

8、出,1:按一系列初等换后得到的(2.9(2.9)加到第三行上；将第一行乘以4- 1-加到第四行上得到第7页frl0aaL00J=hg17132220-)空0)壮udr凸dtB240)站弭aa& MB230站43aa a a第8页v 已是上三角矩阵，于是得到了与原方程等价的易解形式的方程组:2口工1十122十+如心=尊+吆妝4朗十囲比=阳(2.132.13)再对方程组(2.132.13)依次回代解出丁“门-厂匸。从式(2.122.12)可以得到系数矩阵 二的行列式的值为的对角元素的乘积。即这也正是在计算机上计算方阵 二的行列式的常规方法。要将上述解方程步骤推广到 打阶方程组，只需将对控制

9、量“4 4 的操作改成对控制量卞的操作即可。其中:将第二行乘以一上-加到第四行上， 得到f11a13巧40护%00务00%其中：(2.11(2.11)柑鼻n n(3(3)若；则将第三行乘以加到第四行上，得到(2.12(2.12)(2(2)若 则将第二行乘以第9页吆元方程组高斯消元法的步骤如下:对于A - -J JI I 约定 I I 气有忙学“-（盘叽肿）/ms卫+1“ 妒=铲-储-严尸址 t” 1 s “经过以上消元，我们已得到与：等价的方程组一.一 -，其中工已是一个上三角矩阵。为简单起见，仍记二的元素为-5二匚口 -叭料一I,-*-,!(2.15(2.15)即已得到原方程组的解。咼斯消兀

10、法算法在算法中略去了变量，矩阵和向量的定义部分。在消元过程中，将 素的位置上。1 1输入：方程组阶数n n,方程组系数矩阵 A A 和常数向量 bobo FORFOR i:=k+1i:=k+1 TOTO n n/假定，亠FORFOR j:=k+1j:=k+1 TOTO n nai: = SI / ENDFORJENDFORJ / ENDFORIENDFORI / ENDFORKENDFORKJ J 仍放在厂元2 2. FORFOR k:=1k:=1 TOTO n-1n-1/消元过程第10页 s:=bis:=biFORFOR j:=i+1j:=i+1 TOTO n n DODO4 4输出方程组的

11、解 - o o高斯消元法的运算量整个消元过程即式（2.142.14）的乘法和除法的运算量为回代过程即式（2.152.15 ）的乘除运算量为故高斯消元法的运算量为(2.16(2.16)高斯消元法的可行性在上面的消元法中，未知量是按照在方程组中的自然顺序消去的，也叫顺序消元法。H n在消元过程中假定对然元素，消元步骤才能顺利进行，由于顺序消元不改变上的主子式值，故高斯消元法可行的充分必要条件为1 1 的各阶主子式不为零。但是，实际上只要-1方程组就有解。故高斯消元法本身具有局限性。痕 T另一方面，即使高斯消元法可行，如果弘 很小，在运算中用它作为除法的分母ii 乜二、会导致其它元素数量级的严重增长

12、和舍入误差的扩散。这是高 斯消元法的另一缺陷。0 0003+3.0000X2=2.00011.0000+1 0000 xa= 1.00003 3. FORFOR i:=ni:=n TO1TO1/回代求解(2.17(2.17)(2.18(2.18)例 2.1 方程组1第11页1 2_ = _的精确解为：3 33 3。在高斯消兀法计算中取 5 5 位有效数字。解：方程（2.172.17） X X （- 1 1） /0.0003+/0.0003+ 方程（2.182.18）得：，代入方程（2.172.17）得11 - - 。由此得到的解完全失真，如果交换两个 方程的顺序，得到等价方程组经高斯消元后有由

13、此可看到，在有些情况下，调换方程组的次序对方程组的解是有影响的，对消元法中抑制舍入误差的增长是有效的。如果不调换方程组的次序，取6 6 位有效数字计算方程组的解，得到取 9 9 位有效数字计算方程组的解，得到由此可见有效数字在数值计算中的作用。列主元消元法如果在一列中选取按模最大的元素，将其调到主干方程位置再做消元，则称为列主元消元法。调换方程组的次序是为了使运算中做分母量的绝对值尽量地大，减少舍入误差的影响。用列主元方法可以克服高斯消元法的额外限制，只要方程组有解，列主元消元法就能畅通无阻地顺利求解，同时又提高了解的精确度。maxkl=ki更具体地，第一步在第一列元素中选出绝对值最大的元素，

14、交换第一行和第吨行的所有元素，再做化简为零的操作。的元素 E 製上丨，对疋行和陀行交换后，再做消元操作，这就是列主元消元法的操作步骤。0-1） 0-1）由于 ：儿】，可证”中至少有一个元素不为零，从理论上保证了列主元消元法的可行性。列主元消元法与高斯消元法相比，只增加了选列主元和交换两个方程组（即两行元素）的过程。列主元消元法算法对于每个r-在做消元前，选出中绝对值最大第12页1 1 输入：方程组阶数 人，方程组系数矩阵和常数向量项二。/ ENDFORKENDFORK4 4.输出方程组的解如果对于第：步，从：行至行和从此列至咋列中选取按模最大的诬血，对第氏行和第肚行交换，对第比列和第 v v

15、列交换，这就是全主元消元法。在k k 列和第 v v 列交换时，还要记录下 v v 的序号，以便恢 复未知量 x xk k和 xvxv 的位置。3.1.3 高斯若尔当(Gauss Jordan )消元法高斯消元法将系数矩阵化为上三角矩阵，再进行回代求解；高斯一若尔当消元法是将系数矩阵化为对角矩阵，再进行求解，即对高斯消元法或列主元消元法得到的等价增广矩阵：用第 4 4 行乘加到第 3 3 行上，用第 4 4 行乘加到第 2 2 行上，用第 4 4行乘 N N *4*4 加到第 1 1 行上，得到用第 3 3 行乘加到第 2 2 行上，用第 3 3 行乘 f 加到第 1 1 行上，再用第 2 2

16、行乘加到第 1 1 行上，得到2 2. FORFOR k:=lk:=l TOn-1TOn-1选主元的消元过程FOB. v:=kTOn/交换第*行和第朋行/ ENDFORIENDFORI3 3. FORFOR i:=ni:=n TOTO 1 1/回代求解/选择工：工：Ml第13页知 00 0 垃 m0 疵 0 0 貂0 0 增。希/00 舞昭2.192.19）系数矩阵元素为 一，常数项元素为 】。那么用初等变换化系数矩阵为对角矩阵的方法称为高斯一若尔当消元法。从形式上看对角矩阵（2.152.15）比上三角矩阵（2.112.11 ）更为简单，易于计算匚，但是将上三角矩阵（2.112.11）化为对角

17、矩阵（2.152.15 ）的工作量略大于上三角矩阵回代的工作量。高斯一若尔当消元法求逆矩阵设二为非奇异矩阵，方程组；的增广矩阵为 I I 。如果对：应用高斯- -若尔当消元法化为（打门，则= = T TO OX2 435例 2.22.2 用高斯- -若尔当消元法求V V-12210o56001245(10T245C10解：3501123101-3r宀-332-10解得:(2.19)为方便起见，仍记式（5可的逆矩阵川 O O第14页2 直接三角分解法仍以=为例，在高斯消元法中，从对方程组进行初等变换的角度观察方程组系数矩阵的演变过程。第一次消元步骤将方程组（2.92.9）化为方程组（2.102.

18、10），相当于用了三个初等矩阵左乘 止和记- 1：-，容易验证，第15页由丁 4、_ 丁得到t t -其中将方程组（2.102.10）化为方程组（2.112.11），相当于用了两个初等矩阵左乘上和丘。同理，将方程组（2.112.11）化为方程组（2.122.12），相当于用一个初等矩阵左乘丄和：。记Qs 小堪，有完成了消元过程，有亦有所有消元步骤表示为：w w左乘一系列下三角初等矩阵。容易验证，这些下三角矩阵的乘积亠仍为下三角矩阵，并有于是有或这里丁 仍为下三角矩阵，其对角元素为 1 1,称为单位下三角矩阵，而 二已是上三角矩阵。结果表明若消元过程可行， 可以将匸分解为单位下三角矩阵 二与上三

19、角矩阵丁的乘积。 由此派生出解方程组的直接分解法。由高斯消元法得到启发，对消元的过程相当于将 二分解为一个上三角矩阵和一个下三角矩阵的过程。如果直接分解 上得到和。这时方程匚一 I化为匸二=， 令-，由二1解出；再由一-，解出工。这就是直接分解法。= L,A = U，则有第16页将方阵二分解为上=二二，当二是单位下三角矩阵， L 是上三角矩阵时，称为多利特尔（DoclittleDoclittle ）分解；当丄是下三角矩阵，二是单位上三角矩阵时，称为库朗（CourantCourant）分解。分解的条件是若方阵上的各阶主子式不为零，则多利特尔分解或库朗分解是可行和惟一的。一、多利特尔分解多利特尔分

20、解步骤二可分解为A =-，其中-为单位下三角矩阵， 丁为上三角矩阵，即矩阵二和丁共有 J J 个未知元素，按照 P P 的行元素二的列元素的顺序，对每个 一列出式（2.162.16）两边对应的元素关系式，一个关系式解出一个 二或丁的元素。下面是计算二和丁的元素的步骤：（1 1）计算丁的第一行元素 心：；芯要计算则列出式（2.202.20）等号两边的第 1 1 行第 1 1 列元素的关系式:故=，二。一般地，由丁的第一行元素的关系式得到（2 2）计算上的第一列元素-1要计算 L L，则列出式（2.202.20）等号两边的第 2 2 行第 1 1 列元素的关系式: 故一一一一-一一。一般地，由二的

21、第 1 1 列元素的关系式 得到若亠二的各阶主子式不为零，第17页（3 3）计算丁的第 2 2 行元素（4 4）计算二的第 2 2 列元素若已算出丁的前行，匸的前-列的元素，则（5 5）计算丁的第行元素“ ;由的第：行元素的关系式：是上三角矩阵，列标行标。得到后1（2.212.21）（6 6）计算二的第 L L 列元素由二的第：列元素的关系式：T T 匚是下三角矩阵，二行标标：-行标。得到一直做到二的第列，T T 的第吃行为止。第18页十0（/）用匸-直接分解方法求解方程组所需要的计算量仍为，和用高斯消元法的计算量基本相同。可以看到在分解中 上的每个元素只在式（2.212.21 ）或（2.22

22、2.22）中做而且仅做一次贡献，如 果需要节省空间，可将丁以及二的元素直接放在矩阵 壬相应元素的位置上。用直接分解法解方程：，首先作出分解“二L令-1，解方程组。由 于二是单位下三角矩阵，容易得到!-1(2.23(2.23)再解方程组 L L ，其中对以进行二丁分解时，并不涉及常数项 勺。因此，若需要解具有相同系数的一系列线 性方程组时，使用直接分解法可以达到事半功倍的效果。多利特尔直接分解算法1 1 输入：方程组阶数，系数矩阵上和常数项卜。2F0Rk:=l TOn FORj：=kTOnIIII 计算的第行兀素(2.24(2.24)FORi-k+1FORi-k+1 TOTO n nII计算二的

23、第不列元素第19页 完成丄一分解第20页3F0Ri:=lT0n/解方程组4 4 匸口.： =1=1 匚二:-/解方程组一 5 5 输出方程组的解一 一例 3.23.2 用多利特尔分解求解方程组：r21I I1 110(wll132=1应苗23解：1122110对:：1 1，有 对丄】，有 对= 2,有 解丄，即 解-、，即二、追赶法很多科学计算问题中，常常所要求解的方程组为三对角方程组也/其中(3.25)(3.25)(3.29)(3.29)第21页由些可见将二分解为及丁，只需计算 |及 公式为：两组数，然后解；，计算再解则得并且满足条件:称心为对角占优的三对角线矩阵。其特征是非零元素仅分布在对

24、角线及对角线两侧的 位置。在样条插值函数的-订关系式中就出现过这类矩阵。事实上，许多连续问题经离散化 后得到的线性方程组，其系数矩阵就是三对角或五对角形式的对角矩阵。利用矩阵直接分解法，求解具有三对角线系数矩阵的线性方程组十分简单而有效。上分解为下三角矩阵-，及单位上三角矩阵 丁的乘积。即豆=二&，其中利用矩阵乘法公式，比较“丄二两边元素，可得到于是有61A = 7 -1/(2.26(2.26)现将1q %1L =的 吗1p-%、叭%1(3.27)(3.27)(3.31)(3.31)第22页整个求解过程是先由(3.28)(3.28)及(3.29)(3.29)求，及门，这时 一 ： 是追

25、”的过程，再由(3.24)(3.24)求出-：,这时IT是往回赶，故求解方程组(3.25)(3.25)的整个过程称为追赶法。对称正定矩阵也是很多物理问题产生的一类矩阵，正定矩阵的各阶主子式大于零。可以证明，若二正定，则存在下三角矩阵 二，使，直接分解-的分解方法， 称为平方根法。由于在平方根法中含有计算平方根的步骤，因此很少采用平方根法的分解形式。对于对称矩阵，常用的是- 丄二二 分解。( (提出矩阵的对角元素) )由二对称正定，可得 J由的对称性和分解的惟一性可证营旳一号舛我总一1(3.30)(3.30)平方根法对二作多利特尔分解二二，即(3.31)(3.31)第23页1-是对角元素为 1 1 的单位下三角矩阵。(2.34(2.34)第24页对矩阵二作