分析02-线性方程组直接解法.ppt

《分析02-线性方程组直接解法.ppt》由会员分享，可在线阅读，更多相关《分析02-线性方程组直接解法.ppt（96页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、WY第二 章线性方程组直接解法2-1 第章 WY第二章目录1.1.GauusGauus 消元法消元法2.2.主元素法主元素法 2.1 2.1 引入主元素法的必要性引入主元素法的必要性 2.2 2.2 列主元素法列主元素法 2.3 2.3 全主元素法全主元素法 2.4 2.4 解三对角方程组的追赶法解三对角方程组的追赶法3.3.矩阵分解法矩阵分解法 3.1 3.1 GaussGauss消去法的矩阵形式消去法的矩阵形式 3.2 3.2 矩阵的三角分解矩阵的三角分解 3.3 3.3 直接三角分解法直接三角分解法4.4.平方根法与改进的平方根法平方根法与改进的平方根法5.5.矩阵求逆矩阵求逆6.方程组

2、的性态和条件数2 第章 WY线性方程组的概念 在科学研究和工程技术中所提出的计算问题中，线性在科学研究和工程技术中所提出的计算问题中，线性方程组的求解问题是基本的，常见的，很多问题如插值函方程组的求解问题是基本的，常见的，很多问题如插值函数，最小二乘数据拟合，构造求解微分方程的差分格式等数，最小二乘数据拟合，构造求解微分方程的差分格式等，都包含了解线性方程组问题，因此，线性方程组的解法，都包含了解线性方程组问题，因此，线性方程组的解法在数值计算中占有较重要的地位。在数值计算中占有较重要的地位。设设nn阶线性方程组：阶线性方程组：其矩阵形式为：其矩阵形式为：Ax=b(2-2)其中：其中：3 第章

3、 WY 求解Ax=b，曾经学过高斯（Gauss）消元法，克莱姆（Cramer）法则，矩阵变换法等，但已远远满足不了实际运算的需要，主要体现两个方面：一是运算的快速和准确，其次是方程组的个数增大时的计算问题。如何建立能在计算机上可以实现的有效而实用的解法，具有极其重要的意义，我们也曾指出过，Cramer 法则在理论上是绝对正确的，但当n 较大时，在实际计算中却不能用。线性方程组的概念（续）如果线性方程组Ax=b的系数行列式不为零，即det(A)0，则该方程组有唯一解。4 第章 WY线性方程组的数值解法解线性方程组的数值方法大致分为两类：解线性方程组的数值方法大致分为两类：请注意：请注意：由于在计

4、算中某些数据实际上只能用有限位小由于在计算中某些数据实际上只能用有限位小 数，即不可避免地存在着舍入误差的影响，因数，即不可避免地存在着舍入误差的影响，因 而即使是准确解法，也只能求到近似解。而即使是准确解法，也只能求到近似解。直接法在求解中小型线性方程组（直接法在求解中小型线性方程组（100100个），特别是个），特别是系数矩阵为稠密型时，是常用的、非常好的方法。系数矩阵为稠密型时，是常用的、非常好的方法。1.直接法：直接法：指假设计算过程中不产生含入误差，经过有指假设计算过程中不产生含入误差，经过有 限步四则运算可求得方程组准确解的方法。限步四则运算可求得方程组准确解的方法。2.2.迭代法

5、：迭代法：从给定的方程组的一个近似值出发，构造某从给定的方程组的一个近似值出发，构造某种算法逐步将其准确化，一般不能在有限步内得到准确解。种算法逐步将其准确化，一般不能在有限步内得到准确解。这一章介绍计算机上常用的直接法，它们都是以这一章介绍计算机上常用的直接法，它们都是以GaussGauss消元法为基本方法，即先将线性方程组化为等价的三角形消元法为基本方法，即先将线性方程组化为等价的三角形方程组，然后求解。方程组，然后求解。5 第章 WY1 Gauss 消元法 GaussGauss消元法是最基本的一种方法，下例说明其消元法是最基本的一种方法，下例说明其基本思想基本思想:例1解线性方程组：解线

6、性方程组：解：消去x1，进行第一次消元：首先找乘数，以-12 乘第一个方程加到第二个方程，以18乘第一个方程加到第三个方程上可得同解方程组：6 第章 WY例1（续）上述上述GaussGauss消元法的基本思想是：先逐次消去变量，将消元法的基本思想是：先逐次消去变量，将方程组化成同解的上三角形方程组，此过程称为方程组化成同解的上三角形方程组，此过程称为消元过消元过程程。然后按方程相反顺序求解上三角形方程组，得到原。然后按方程相反顺序求解上三角形方程组，得到原方程组的解，此过程称为方程组的解，此过程称为回代过程回代过程。再消一次元得：二次消元后将方程化为二次消元后将方程化为倒三角形式，然后进行倒三

7、角形式，然后进行回代容易解出：回代容易解出：x3=3,x2=2,x1=1。我们的目的，是要总结归纳出一般情况下的我们的目的，是要总结归纳出一般情况下的nn阶线性方程阶线性方程组的消元公式和回代求解公式，从而得到求解组的消元公式和回代求解公式，从而得到求解nn阶线性方阶线性方程组的能顺利在计算机上实现的行之有效的算法。程组的能顺利在计算机上实现的行之有效的算法。7 第章 WYGauss 消元法的基本步骤1（4 4 阶）阶）为能更清楚地得到算法，下面以为能更清楚地得到算法，下面以44阶线性方程组为例总结阶线性方程组为例总结求解步骤，并且很容易地可推广至一般的求解步骤，并且很容易地可推广至一般的nn

8、阶线性方程组。阶线性方程组。8 第章 WY 可以检查，分别以可以检查，分别以llii11乘第一个方程加到第乘第一个方程加到第ii个方程上个方程上可以完成第一次消元，得同解方程组：可以完成第一次消元，得同解方程组：变化以后的方变化以后的方程组系数及右程组系数及右边的常数项可边的常数项可总结出如下的总结出如下的计算公式：计算公式：完成第一次消元之后的完成第一次消元之后的方程组记为：方程组记为：A(2)x=b(2)Gauss 消元法的基本步骤2（4 4 阶）阶）9 第章 WYGauss 消元法的基本步骤3（4 4 阶）阶）以方程组中第以方程组中第ii个方程减去第二个方程乘个方程减去第二个方程乘lli

9、i2 2(i i=3,4)=3,4)，完，完成第二次消元。成第二次消元。上标为上标为33的系数的系数和右端项可由和右端项可由下面公式计算：下面公式计算：10 第章 WYGauss 消元法的基本步骤4（4 4 阶）阶）第三步第三步：消元消元（44阶方程组需进行阶方程组需进行33次消元次消元）将上述将上述 AA(3)(3)X X=bb(3)(3)中最后一个方程中的中最后一个方程中的xx33消为零消为零：然后可回代求解：然后可回代求解：由于由于AA(4)(4)为上三角形，所以可为上三角形，所以可按变量的逆序逐步回代求按变量的逆序逐步回代求原方程组的解：原方程组的解：上述上述 消元、回代消元、回代求解

10、过程求解过程很容易推广到一般的很容易推广到一般的nn阶线阶线性方程组。性方程组。经过上述消元步骤，经过上述消元步骤，得到同解的上三角形得到同解的上三角形方程组：方程组：A(4)x=b(4)11 第章 WYGauss 消元法的消元过程1、2（n n 阶）阶）一般地，设一般地，设 nn阶方程组：阶方程组：消元过程为：消元过程为：将上方程组中第将上方程组中第ii个方程减去第个方程减去第22个方程乘以个方程乘以llii22(ii=3,=3,nn)，完成，完成第二步第二步消元。消元。12 第章 WYGauss 消元法的消元过程3（n n 阶）阶）第第k k 步步：设第：设第kk11步消元后得原方程组的同

11、解方程组为：步消元后得原方程组的同解方程组为：第第kk步消元后同步消元后同解方程组中上标解方程组中上标为为kk+1+1的元素的的元素的计算公式见下屏计算公式见下屏13 第章 WY照此消元下去，完成n 1次消元后，可将原方程组化成同解的上三角形方程组如下：Gauss 消元法的消元过程3（n n 阶）阶）14 第章 WYGauss 消元法的回代过程（n n 阶）阶）回代过程：逐步回代求得原方程组的解 15 第章 WYGauss 消元法的计算量 由于在计算机中作乘除运算量所需时间远大于作加减由于在计算机中作乘除运算量所需时间远大于作加减运算所需时间，故只考虑作乘除运算量。运算所需时间，故只考虑作乘除

12、运算量。由消元法步骤知，第由消元法步骤知，第kk次消元需作次消元需作nnkk次除法，作次除法，作(nn kk)()(n n k k+1)+1)次乘法，故消元过程中乘除法运算量为：次乘法，故消元过程中乘除法运算量为：所以所以GaussGauss 消去法的消去法的乘除法乘除法总运算量总运算量为：为：16 第章 WYGauss 法与Cramer 法则的计算量比较 Gauss Gauss 消元法的乘消元法的乘除法总运算量为除法总运算量为：与我们曾经介绍的与我们曾经介绍的CramerCramer法则的乘除法总运算量法则的乘除法总运算量(nn221)1)nn!+!+n n 相比，由下表可知：相比，由下表可

13、知：当阶数越高时，当阶数越高时，GaussGauss消消元法所需乘除法次数比元法所需乘除法次数比CramerCramer法则要少得多法则要少得多：方程组阶数 方程组阶数 3 3 10 10 20 20 50 50Gauss Gauss 消元法运算量 消元法运算量17 17 430 430 3060 3060 44150 44150Cramer Cramer 法则运算量 法则运算量51 51359251210 3592512109.710 9.71020 207.610 7.61067 67Gauss Gauss 消元法的优缺点：消元法的优缺点：但但其计算过程中，要求其计算过程中，要求aakkk

14、k(kk)（称为主元素）均不为零，（称为主元素）均不为零，因而适用范围小，只适用于从因而适用范围小，只适用于从11到到nn 11阶顺序主子式均不阶顺序主子式均不为零的矩阵为零的矩阵AA，计算实践还表明，计算实践还表明，GaussGauss消元法的数值稳消元法的数值稳定性差，当出现小主元素时，会严重影响计算结果的精度，定性差，当出现小主元素时，会严重影响计算结果的精度，甚至导出错误的结果。甚至导出错误的结果。GaussGauss消元法简单易行。消元法简单易行。17 第章 WY2 主元素法 2.1 引入主元素的必要性 对线性方程组AX=b，若其系数行列式 det(A)0，则该方程组有唯一 解，但是

15、这一条件 不能保证所有主元素都不等于零，只要某一主元素等于零，就不能用Gauss 消元法求解该方程组，即使所有主元素不等于零，但 某一主元素的绝对值很小时，Gauss 消元法也是不适用的。如下例：例218 第章 WY例2（续1）解：为减小误差，计算过程中保留3位有效数字。按Gauss 消元法步骤：第一次消元后得同解方程组：第一次消元后得同解方程组：第二次消元后得同解方程组第二次消元后得同解方程组 回代得解，x3=2.02，x2=2.40，x1=5.80。容易验证，方程组（3-8）的准确解为：x1=2.60，x2=1.00，x3=2.0。显然两种结果相差很大。19 第章 WY 若在解方程组前，先

16、交换方程的次序，如将（2-8）交换一行与二行改写成如下所示：再用Gauss 消元法，顺序消元后得同解方程组：回代得解：x3=2.00，x2=1.00，x1=2.60 与准确解相同。例2（续2）20 第章 WY例2两种解法的误差分析 在例2中，对(2-8)的方程进行顺序消元时，主元a(1)11=0.50，a(2)22=0.100 都比较小，以它们作 除数就增长了舍入误差,而导致计算结果不准确。产生上述现象的原因在于舍入误差，当|a(k)kk|很小时，进行第k次消元，要用|a(k)kk|作除数，这 样就可能增大舍入误差造成溢出停机，或者导致 错误的结果。为了在计算过程中，抑制舍入误差的增长，应尽量

17、避免小主元的出现。如例2的第二种解法,通过交换方程次序，选取绝对值大的元素作主元 基于这种思想而导出主元素法。21 第章 WY2.2 列主元素法 为简便起见，对方 程组（2-1），用 其增 广矩阵：表示，并直接在增广矩阵上进行运算。列主元素法的具体步骤如下：22 第章 WY列主元素法如此经过如此经过nn11步，增广矩阵（步，增广矩阵（2-92-9）被化成上三角形，然）被化成上三角形，然后由回代过程求解。后由回代过程求解。在上述过程中，在上述过程中，主元是按列选取的，故称为主元是按列选取的，故称为列主元法列主元法。例例22中的第二种解法就是按列主元法进行的。中的第二种解法就是按列主元法进行的。2

18、3 第章 WY2.3 全主元素法 经过n k次消元后，得到与方程组（2-1）同解的上三角形方程组，再由回代过程求解。24 第章 WY主元素法举例例6计算过程保留三位小数。此例的计算结果表明，全主元素法的精度优于列此例的计算结果表明，全主元素法的精度优于列主元法，这是由于全主元法是在全体元素中选主元，主元法，这是由于全主元法是在全体元素中选主元，故它对控制舍入误差十分有效。但是全主元法在计算故它对控制舍入误差十分有效。但是全主元法在计算过程中，需同时作行与列的互换，因而程序比较复杂过程中，需同时作行与列的互换，因而程序比较复杂,计算时间较长。列主元法的精度虽稍低于全主元法，计算时间较长。列主元法

19、的精度虽稍低于全主元法，但其计算简单，工作量大为减少，且计算经验与理论但其计算简单，工作量大为减少，且计算经验与理论分析均表明，它与全主元法同样具有良好的数值稳定分析均表明，它与全主元法同样具有良好的数值稳定性，故列主元法是求解中小型稠密线性方程组的最好性，故列主元法是求解中小型稠密线性方程组的最好方法之一。方法之一。方法之一。方法之一。25 第章 WY2.4 解三对角方程组的追赶法 在很多问题中，需要解如下形式的三对角方程组：在很多问题中，需要解如下形式的三对角方程组：三对角方程组的系数矩阵为三对角阵，对于这种特殊三对角方程组的系数矩阵为三对角阵，对于这种特殊而又简单的方程组，用前面介绍的方

20、法求解由于有大量而又简单的方程组，用前面介绍的方法求解由于有大量的零元素既占内存又浪费计算时间，显然很不经济。充的零元素既占内存又浪费计算时间，显然很不经济。充分注意到三对角方程组的特点，根据顺序消元的思想导分注意到三对角方程组的特点，根据顺序消元的思想导出一个简便的算法出一个简便的算法追赶法追赶法。26 第章 WY追赶法的解题步骤 首先首先进行顺序消元，进行顺序消元，且每步将主元系数且每步将主元系数化为化为11，将方程组化为：，将方程组化为：其中系数按下式计算其中系数按下式计算：然后然后回代回代求解，得：求解，得：上述追赶法能进行到底上述追赶法能进行到底。27 第章 WY追赶法举例用追赶法解

21、下用追赶法解下列三对角方程组：列三对角方程组：例4解：解：首先首先将方程组化为（将方程组化为（先追先追）：）：然后回代（赶）求解：x5=0，x4=30/7，x3=6/7，x2=12/7，x1=0 可以看出，追赶法本质上还可以看出，追赶法本质上还是顺序消元法，但由于计算过程是顺序消元法，但由于计算过程中只涉及系数矩阵的非零元，因此大大节约了计算机内存中只涉及系数矩阵的非零元，因此大大节约了计算机内存与计算量，按乘除法次数进行比较，与计算量，按乘除法次数进行比较，GaussGauss消元法约为消元法约为nn33/3/3，全主元法为，全主元法为nn33/2/2，而追赶法仅为，而追赶法仅为55nn-3

22、-3次，可见追赶次，可见追赶法是求解三对角方程组的非常好的方法。法是求解三对角方程组的非常好的方法。28 第章 WY3 矩阵分解法 如果用矩阵形式表示，如果用矩阵形式表示，GaussGauss消元法的消元过程是对消元法的消元过程是对方程组（方程组（2-12-1）的增广矩阵（）的增广矩阵（AA、bb）进行一系列的初等行）进行一系列的初等行变换，将系数矩阵变换，将系数矩阵AA化成上三角矩阵的过程，也等价于用化成上三角矩阵的过程，也等价于用一串初等变换阵去左乘增广矩阵，因此，消元过程可以通一串初等变换阵去左乘增广矩阵，因此，消元过程可以通过矩阵运算来实现。过矩阵运算来实现。紧接下屏：紧接下屏：3.1

23、 GaussGauss消元法的矩阵形式消元法的矩阵形式 事实上，事实上，GaussGauss消元法的消元法的 第一次消元第一次消元相当于用初等矩阵：相当于用初等矩阵：29 第章 WY第二次消元第二次消元相当于用初等矩阵：相当于用初等矩阵：第第kk次消元次消元相当于用初等矩阵：相当于用初等矩阵：Gauss 消元法的矩阵形式30 第章 WY经过经过nn11步消元后得到：步消元后得到：因为因为LLkk(kk=1,2,=1,2,nn1)1)均为非奇异阵，故它们均为非奇异阵，故它们的逆矩阵存在。的逆矩阵存在。容易求出：容易求出：这说明：这说明：在在 的条件下，消元过程的条件下，消元过程实际上是把系数矩阵

24、实际上是把系数矩阵AA分解成单位下三角阵与上三角矩阵分解成单位下三角阵与上三角矩阵的乘积的过程。的乘积的过程。Gauss 消元法的矩阵形式（续）31 第章 WY杜利特尔（Doolittle）分解 LU LU 分解 分解 事实上，只要事实上，只要AA非奇异，由上述结论，它一定可以分非奇异，由上述结论，它一定可以分解成两个三角形矩阵的乘积，即：解成两个三角形矩阵的乘积，即：A=A=LLU U。上述分解称为上述分解称为杜利特尔（杜利特尔（DoolittleDoolittle）分解）分解，也称为，也称为LULU分解分解，当系数矩阵完成三角分解后，对于求解方程组：当系数矩阵完成三角分解后，对于求解方程组

25、：AxAx=bb。消元过程相当于分解消元过程相当于分解AA=LULU及求解三角形方程组及求解三角形方程组LLyy=bb，回代过程则是求解另一个三角形方程组，回代过程则是求解另一个三角形方程组UUxx=yy，因此，因此，解线性方程组问题可转化为矩阵的三角分解问题。解线性方程组问题可转化为矩阵的三角分解问题。其中：其中：LL为单位下三角矩阵，为单位下三角矩阵，UU为上三角矩阵：为上三角矩阵：32 第章 WY3.2 矩阵的三角分解 正如正如GaussGauss消元法要在一定条件下才能进行到底一样，消元法要在一定条件下才能进行到底一样，矩阵矩阵AA也必须满足一定条件才能进行三角分解。也必须满足一定条件

26、才能进行三角分解。设设AA为为nn阶方阵，若阶方阵，若AA的顺序主子式的顺序主子式AAii(i i=1,2,=1,2,n n 1)1)均不为零均不为零,则矩阵则矩阵AA存在唯一的存在唯一的DoolittleDoolittle分解。分解。定理2.1存在性证明 存在性证明唯一性证明 唯一性证明下面讨论如何对下面讨论如何对AA进行进行LULU分解分解：（11行行11列列）由于两个矩阵相等就是它们的对应元素都相等，因此由于两个矩阵相等就是它们的对应元素都相等，因此通过比较通过比较AA与与LULU的对应元素，即可得到直接计算的对应元素，即可得到直接计算LL、UU的的元素的公式：元素的公式：AA=LU L

27、U 即：即：紧接下屏：紧接下屏：33 第章 WY对A 进行LU 分解ALU由矩阵乘法规则及比较（由矩阵乘法规则及比较（2-112-11）两端的元素，得：）两端的元素，得：即可由（即可由（2-122-12）求出）求出UU的第一行，的第一行，LL的第一列。的第一列。下面讨论一般情况，即：下面讨论一般情况，即：UU的第的第i i 行，行，LL的第的第jj列：列：34 第章 WY一般情况下，可由：一般情况下，可由：对A 进行LU 分解（r r 行行r r 列）列）计算过程应按计算过程应按UU第第11行、行、LL第第11列列（第（第11框），框），UU第第22行、行、LL第第22列列（第（第22框），框

28、），的顺序的顺序 具体分解步具体分解步骤见下屏：骤见下屏：得到计算得到计算uuijij和和 llijij 的公式：的公式：35 第章 WY对A 进行LU 分解的具体步骤1.计算U 的第1行，L 的第1列，亦称为计算 第1框；2.计算U 的第r 行，L 的第r 列（r=2,n），即第r 框：36 第章 WY矩阵A 的LU 分解举例解：解：按分解公式（按分解公式（2-132-13），），一框一框分解，每框计算时先行后列一框一框分解，每框计算时先行后列：所以：所以：例例55 37 第章 WY三角分解的紧凑格式 根据式（2-13）的特点，矩阵的三角分解可按以下格式及顺序进行。这种格式既便于记忆，又便于

29、计算，称为紧凑格式。见下表2-1：表表2-12-1(aa1111)uu1111(aa1212)uu1212(aa1313)uu1313(aa11nn)uu11nn(aa2121)ll2121(aa2222)uu2222(aa2323)uu2323(aa22nn)uu22nn(aann11)llnn11(aann22)llnn22(aann33)llnn33(aannnn)uunnnn(aa3131)ll3131(aa3232)ll3232(aa3333)uu3333(aa33nn)uu33nn 38 第章 WY（1）计算顺序：将aij，uij，lij 按表2-1 列好，计算 时按框从外到内进行

30、，每一框中先算行。从 左向右依次计算 uij；再算列，自上而下求 lij；三角分解的紧凑格式（2）计算方法：按行计算时，需将所求元 uij 的 对应元aij 逐次减去 uij 所在行左面各框的元 素 lij 乘以 uij 所在列上面各框相应的元 uij。按列计算 lij 时，在作上述运算后还需除以 lij 所在框的对角元 lij。说明：39 第章 WY三角分解的紧凑格式举例例例44中矩阵中矩阵AA的三角分解按紧凑格式计算，结果见下表的三角分解按紧凑格式计算，结果见下表2-22-2：由表可得：（2 2）2 2（2 2）2 2（3 3）3 3（7 7）7 7 2 2 2=3 2=3（7 7）7 7

31、 2 2 3=1 3=1（4 4）（）（4 4（1 1）2 2）/3=2/3=2（5 5）5 5 2 2 1 1（1 1）3=6 3=6表表2-22-240 第章 WY3.3 直接三角分解法 若线性方程组若线性方程组Ax Ax=bb的系数矩阵的系数矩阵AA完成三角分解，完成三角分解，A A=LULU，那么解，那么解方程组方程组Ax Ax=bb等价于求解两个三角等价于求解两个三角形方程组形方程组Ly Ly=bb，UxUx=yy，即由：，即由：再由：再由：可解得：可解得：41 第章 WY直接三角分解法（续）容易看出，式（容易看出，式（2-142-14）与式（）与式（2-132-13）的运算规律相同

32、，）的运算规律相同，或者由：或者由：可知，若将可知，若将bb作作AA的最后一列处理，在将的最后一列处理，在将AA化为上三化为上三角阵的同时，也将角阵的同时，也将bb化作了化作了yy，故在利用三角分解求解方程，故在利用三角分解求解方程组组AxAx=bb时，只需将右端向量时，只需将右端向量bb列在表列在表2-12-1的最后一列，按的最后一列，按uuijij的计算方法即可求出的计算方法即可求出yykk（或在式（或在式（2-132-13）中求）中求uuijij时，增时，增加一列，加一列，jj算到算到nn+1+1）下表下表2-32-3是求解线性方程是求解线性方程Ax Ax=bb的紧凑的紧凑格式，其计算顺

33、序与计算方法与三角分解相同。格式，其计算顺序与计算方法与三角分解相同。按表按表2-32-3计算后，再按式（计算后，再按式（2-152-15）即可求出方程组的解。）即可求出方程组的解。42 第章 WY紧凑格式解线性方程组举例例6解：按表按表2-32-3计算：计算：(a a11 11)u u11 11(a a12 12)u u12 12(a a13 13)u u13 13(a a1 1n n)u u1 1n n(b b1 1)y y1 1(a a21 21)l l21 21(a a22 22)u u22 22(a a23 23)u u23 23(a a2 2n n)u u2 2n n(b b2 2

34、)y y2 2(a a31 31)l l31 31(a a32 32)l l32 32(a a33 33)u u33 33(a a3 3n n)u u3 3n n(b b3 3)y y3 3(a an n1 1)l ln n1 1(a an n2 2)l ln n2 2(a an n3 3)l ln n3 3(a ann nn)u unn nn(b bn n)y yn n(3)3(3)3(2)2(2)2(5)5(5)5(6)6(6)6(-1)-1/3(-1)-1/3(1)1/3(1)1/3表表2-32-343 第章 WY所以：紧凑格式解线性方程组举例（续）44 第章 WY三角分解法的几点说明1

35、1、用三角分解法求线性方程的乘除法运算量也是、用三角分解法求线性方程的乘除法运算量也是nn33/3/3 数量级。由于在求出数量级。由于在求出uuijij,llijij和和yyii后，后，aaijij和和bbii无需保留，无需保留，故上机计算时，可把故上机计算时，可把LL，UU和和yy存在存在AA，bb所占的单元，所占的单元，回代时回代时xx取代取代yy，整个计算过程中不需要增加新的存，整个计算过程中不需要增加新的存 贮单元。贮单元。33、完成、完成A=LUA=LU分解后可以较容易地求出行列式分解后可以较容易地求出行列式|AA|的值：的值：2 2、从三角分解法的推导及例中可以看出，系数矩阵的、从

36、三角分解法的推导及例中可以看出，系数矩阵的 三三 角分解与右端项无关。因角分解与右端项无关。因 而在计算多个系数矩阵而在计算多个系数矩阵 为为AA而右端不同的线性方程组系时，用三角分解法更而右端不同的线性方程组系时，用三角分解法更 为为 简便（如可用于求逆矩阵）。简便（如可用于求逆矩阵）。45 第章 WY三角分解法的几点说明（续）66、分解法的优点除上述、分解法的优点除上述22、33外，还有：外，还有：aa.可求解可求解AA22zz=bb,因为算因为算AA22计算量大，可用计算量大，可用 b b.可根据可根据AA的形状设计算法，当的形状设计算法，当AA为大型稀疏，且非零为大型稀疏，且非零元素有

37、规律如带状，三对角等，作分解时能充分利用元素有规律如带状，三对角等，作分解时能充分利用AA的的特点，特点，LL，UU能保持能保持AA的原状，即的原状，即LL与与AA的下三角相同，的下三角相同，UU与与AA的上三角形状相同。的上三角形状相同。44、三角分解法一般也可采用选主元的技术，以使算法更、三角分解法一般也可采用选主元的技术，以使算法更 具数值稳定性。具数值稳定性。55、也可以把矩阵、也可以把矩阵AA分解成一个下三角矩阵与一个单位上三分解成一个下三角矩阵与一个单位上三 角矩阵的乘积，矩阵的角矩阵的乘积，矩阵的 这种分解称为克劳特（这种分解称为克劳特（CroutCrout）分解。分解。46 第

38、章 WY4 平方根法与改进的平方根法 对称正定矩阵概念：工程实际问题的计算中，线性方程组的系数矩阵常工程实际问题的计算中，线性方程组的系数矩阵常常具有对称正定性，即其各阶顺序主子式及全部特征值均常具有对称正定性，即其各阶顺序主子式及全部特征值均大于零。矩阵的这一特性使它的三角分解也有更简单的形大于零。矩阵的这一特性使它的三角分解也有更简单的形式，从而导出一些特殊的解法。式，从而导出一些特殊的解法。5 5.AA的所有顺序主子式均为正数，的所有顺序主子式均为正数，即即detdet(AAkk)0,)0,kk=1,2,=1,2,nn)。4 4.AA的所有特征值的所有特征值00；3.3.AA的对角线元素

39、的对角线元素aaiiii0(0(ii=1,2,=1,2,nn)；22.AA是非奇异阵，且是非奇异阵，且AA11也是对称正定阵；也是对称正定阵；11.AA的所有顺序主子矩阵的所有顺序主子矩阵AAkk(kk=1,2,=1,2,nn)也是对称正定阵；也是对称正定阵；若若AA为对称正定矩阵，为对称正定矩阵，则则：47 第章 WY4.1 平方根法 定理定理 2.2 2.2若A 是对称正定矩阵，则存在唯一的单位下三角矩阵L 和对角阵：证明：首先A 可直接作LU 分解，记为A=LU1，其中：48 第章 WY定理 2.2（续）其中其中UU00是单位上三角阵，则由是单位上三角阵，则由AA的对称性可得：的对称性可

40、得：再由唯一性得再由唯一性得UU00=LLTT，所以，所以AA=LDLLDLTT，并且这种分解，并且这种分解是唯一的，又由于是唯一的，又由于UU11的对角线元素的对角线元素UUkkkk就是就是GaussGauss消元法的消元法的主元素：主元素：由于LD1/2是下三角阵，因此有推论：49 第章 WYCholeskg 分解1 推论 若若AA是对称正定矩阵，则存在唯一的主对角线元素是对称正定矩阵，则存在唯一的主对角线元素都为正的下三角阵都为正的下三角阵LL，使得：，使得：A=LLA=LLTT矩阵的这种分解称为矩阵的这种分解称为CholeskgCholeskg分解分解。用比较法可以导出用比较法可以导出

41、LL的计算公式。设：的计算公式。设：比较比较AA与与LLLLTT的相应元素，的相应元素，即由即由AA=LLLLTT可得：可得：计算顺序按列进行。因此：50 第章 WYCholeskg 分解2当完成矩阵当完成矩阵AA的的CholeskyCholesky分解后，分解后，求解方求解方 程组程组AXAX=bb就转化求：就转化求：求解对称求解对称正定线性方正定线性方程组的方法程组的方法称为称为平方根平方根法法，也称为，也称为CholeskyCholesky分分解法解法，这种，这种方法无需选方法无需选主元，计算过程也是稳定的。由于主元，计算过程也是稳定的。由于AA的对称性的对称性，平方根法平方根法的乘除运

42、算量为的乘除运算量为nn33/6/6数量级，约为直接分解法的一半。上数量级，约为直接分解法的一半。上机计算时，所需存贮单元也少，只要存贮机计算时，所需存贮单元也少，只要存贮AA的下三角部分的下三角部分和右端项和右端项bb，计算中，计算中LL存放于存放于AA的存贮单元，的存贮单元，y y,xx存放在存放在bb的存贮单元。的存贮单元。平方根法平方根法的的不足不足之处在于需作之处在于需作nn次开方运算。次开方运算。它们的解分别为：它们的解分别为：51 第章 WY平方根法举例 用平方根法解用平方根法解对称正定方程组：对称正定方程组：例7解解：先分解系数矩阵：先分解系数矩阵AA，只对，只对AA的下三角部

43、分运算即可，的下三角部分运算即可，所以只存放所以只存放AA的下三角部分：的下三角部分：52 第章 WY4.2 改进的平方根法 由定理由定理2.22.2，对称正定矩，对称正定矩阵阵AA又可以作如下分解又可以作如下分解：其中，其中，LL是单位下三角阵，是单位下三角阵，DD是对角阵，是对角阵，UU=DLDLTT。由于由于UU=DLDLTT，即：，即：比较两边的比较两边的对应元素可得对应元素可得：首先由紧凑格式首先由紧凑格式的三角分解可得：的三角分解可得：53 第章 WY改进的平方根法说明 基于上述基于上述LDLLDLTT分解的方法称为改进的平方根法，其乘分解的方法称为改进的平方根法，其乘除运算量与除

44、运算量与CholeskyCholesky分解相当，且避免了开方运算。计算分解相当，且避免了开方运算。计算顺序按先行后列逐层分解计算；顺序按先行后列逐层分解计算；对称正定阵对称正定阵AA完成完成AA=ADLADLTT=LULU分解后，求解方程组：分解后，求解方程组：AxAx=bb，就转化为求解，就转化为求解：并且由于求并且由于求yy和求和求UU的最后一列的算法完全相同，所以的最后一列的算法完全相同，所以可将可将yy视为视为UU的最后一列进行计算。的最后一列进行计算。按上述算法，当按上述算法，当AA为对称正定阵时，单位下三角阵为对称正定阵时，单位下三角阵LL的的元素不必按紧凑格式方法去求解，而只需

45、在求得元素不必按紧凑格式方法去求解，而只需在求得UU的第的第kk行元素后，以它们去除以行元素后，以它们去除以uukkkk即得相应的即得相应的LL的第的第kk列元素，列元素，这样就大大减少了计算量。这样就大大减少了计算量。54 第章 WY改进的平方根法举例 用改进的平方用改进的平方根法求解方程组：根法求解方程组：例8解：解：对增广矩阵（对增广矩阵（AA bb）逐层分解可得：逐层分解可得：则则UxUx=yy为：为：改进平方根法由于对矩阵改进平方根法由于对矩阵AA无正定要求（只要无正定要求（只要uukkkk 0 0），），(kk=1,2,=1,2,nn)即可，而正定要求即可，而正定要求uukkkk

46、0(0(kk=1,2,=1,2,nn)，因，因此是求解对称方程组常用的方法。此是求解对称方程组常用的方法。55 第章 WY5 Gauss-Jordan 消元法求矩阵的逆 Gauss 消元法有许多变形，列主元素法是其中之一，在列主元法的基础上还可对算法进行如下的修改：在消元过程中选主元后，先将主元化为1，然后将主元所在列上，下方各元素均化为0，这样消元的结果使系数矩阵化为了单位阵，无需回代就得到了原方程之解，这种无回代过程的列主元素法称为Gauss-Jordan 消元法。Gauss-Jordan 消元法比顺序消去法计算量大一点，实践中使用不多，但用它求逆阵却十分方便。因为消元过程实质上就是对系数

47、矩阵A 实行初等变换，将A 化为单位阵，相当于对A 左乘了一系列的初等变换阵M1，M2，Mn-1，Mn，使：紧接下屏紧接下屏56 第章 WYGauss-Jordan 消元法求矩阵的逆（续1）这表明同样的一组初等变换在将A 化为I 的同时，可将I 化为A1，即有：因此，以Gauss-Jordan 消元法求A 的逆阵，就是要找到Mi(i=1,2,n)，以它们逐个左乘(A,I),逐列将A 的对角线上的元素化为1，而其余元素化为0，最终将A 化为单位阵，则I 化为A 的逆阵A1。57 第章 WYGauss-Jordan 消元法求矩阵的逆（续2）设增广阵为：58 第章 WY 这里这里aaijij(1)(

48、1)=aa11jj，上述，上述aaijij(2)(2)的计算与的计算与GaussGauss消元法基本上消元法基本上相相同，仅仅由于同，仅仅由于mm1111与与GaussGauss消元法中的乘数消元法中的乘数ll1111不相同引起第不相同引起第一行元素一行元素aa11jj(2)(2)与与aaijij(2)(2)计算不相同，假若把增广阵中计算不相同，假若把增广阵中II的各的各列列视为视为AA的第的第nn+1+1列，第列，第n n+2+2列，列，那么上述计算公式中的，那么上述计算公式中的第二个下标可扩充到第二个下标可扩充到22nn。Gauss-Jordan 消元法求矩阵的逆（续3）59 第章 WYG

49、auss-Jordan 消元法求逆阵(续4)60 第章 WYGauss-Jordan 消元法求逆阵(续5)61 第章 WY设经过k 1步后得到：Gauss-Jordan 消元法求逆阵(续6)1 1 62 第章 WYGauss-Jordan 消元法求逆阵(续7)其中：其中：63 第章 WYGauss-Jordan 消元法求逆阵(续8)完成完成nn步消元后，步消元后，AA11放在原放在原AA的位置。的位置。64 第章 WYGauss-Jordan 法求逆阵的具体步骤 按上述紧缩存贮原则，可节省存贮单元，同时还使得整个计算更简单了。可总结求逆步骤如下：上述1，2是求第k列元素，构成Mk（即求主列）6

50、5 第章 WY（计算其他元素，但少k列，k行）用上述Gauss-Jordan 法求逆阵，计算量约为n3，是Gauss 消元法的3倍，为保证方法稳定性，还可选列主元，若仍按上述紧缩存贮原则，则最后需按行交换的相反次序作列交换才能得到A1。Gauss-Jordan 法求逆阵的具体步骤（续）66 第章 WYGauss-Jordan 法求逆阵举例例 例9 9 解 解：按紧缩存贮方式，逐次计算结果与存贮如下：按紧缩存贮方式，逐次计算结果与存贮如下：第一步 第一步：k k=1=1，在第一列中选 在第一列中选主元，交换 主元，交换1 1，2 2 行，得：行，得：第二步：第二步：k k=2=2 在第二列对角元