线性方程组直接解法.ppt

《线性方程组直接解法.ppt》由会员分享，可在线阅读，更多相关《线性方程组直接解法.ppt（53页珍藏版）》请在金锄头文库上搜索。

1、第三 章线性方程组线性方程组直接解法直接解法第三章第三章 线性方程组直接解法线性方程组直接解法返回前进第三章目录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.

2、1 GaussGauss消去法的矩阵形式消去法的矩阵形式消去法的矩阵形式消去法的矩阵形式 3.2 3.2 矩阵的三角分解矩阵的三角分解矩阵的三角分解矩阵的三角分解 3.3 3.3 直接三角分解法直接三角分解法直接三角分解法直接三角分解法4. 4. 平方根法与改进的平方根法平方根法与改进的平方根法平方根法与改进的平方根法平方根法与改进的平方根法5. 5. 矩阵求逆矩阵求逆矩阵求逆矩阵求逆6.方程组的性态和条件数方程组的性态和条件数第三章第三章 线性方程组直接解法线性方程组直接解法返回前进 设设设设n n阶线性方程组：阶线性方程组：阶线性方程组：阶线性方程组： 其矩阵形式为：其矩阵形式为：其矩阵形

3、式为：其矩阵形式为：Ax=b (2-2)其中：其中：其中：其中：在科学研究和工程技术中所提出的计算问题中，线性在科学研究和工程技术中所提出的计算问题中，线性在科学研究和工程技术中所提出的计算问题中，线性在科学研究和工程技术中所提出的计算问题中，线性方程组的求解问题是基本的，常见的，很多问题如插值函方程组的求解问题是基本的，常见的，很多问题如插值函方程组的求解问题是基本的，常见的，很多问题如插值函方程组的求解问题是基本的，常见的，很多问题如插值函数，最小二乘数据拟合，构造求解微分方程的差分格式等数，最小二乘数据拟合，构造求解微分方程的差分格式等数，最小二乘数据拟合，构造求解微分方程的差分格式等数

4、，最小二乘数据拟合，构造求解微分方程的差分格式等，都包含了解线性方程组问题，因此，线性方程组的解法，都包含了解线性方程组问题，因此，线性方程组的解法，都包含了解线性方程组问题，因此，线性方程组的解法，都包含了解线性方程组问题，因此，线性方程组的解法在数值计算中占有较重要的地位。在数值计算中占有较重要的地位。在数值计算中占有较重要的地位。在数值计算中占有较重要的地位。 第三章第三章 线性方程组直接解法线性方程组直接解法返回前进 求解求解Ax = b，曾经学过高斯（曾经学过高斯（Gauss）消元法，消元法，克莱姆（克莱姆（Cramer）法则，矩阵变换法等，但已远法则，矩阵变换法等，但已远远满足不了

5、实际运算的需要，主要体现两个方面：远满足不了实际运算的需要，主要体现两个方面：一是运算的快速和准确，其次是方程组的个数增大一是运算的快速和准确，其次是方程组的个数增大时的计算问题。如何建立能在计算机上可以实现的时的计算问题。如何建立能在计算机上可以实现的有效而实用的解法，具有极其重要的意义，我们也有效而实用的解法，具有极其重要的意义，我们也曾指出过，曾指出过，Cramer法则在理论上是绝对正确的，法则在理论上是绝对正确的，但当但当n较大时，在实际计算中却不能用。较大时，在实际计算中却不能用。 如果线性方程组如果线性方程组Ax = b的系数行列式不为零，的系数行列式不为零，即即det(A) 0，

6、则该方程组有唯一解。则该方程组有唯一解。第三章第三章 线性方程组直接解法线性方程组直接解法返回前进线性方程组的数值解法解线性方程组的数值方法大致分为两类：解线性方程组的数值方法大致分为两类：解线性方程组的数值方法大致分为两类：解线性方程组的数值方法大致分为两类： 请注意：由于在计算中某些数据实际上只能用有限位小请注意：由于在计算中某些数据实际上只能用有限位小请注意：由于在计算中某些数据实际上只能用有限位小请注意：由于在计算中某些数据实际上只能用有限位小 数，即不可避免地存在着舍入误差的影响，因数，即不可避免地存在着舍入误差的影响，因数，即不可避免地存在着舍入误差的影响，因数，即不可避免地存在着

7、舍入误差的影响，因 而即使是准确解法，也只能求到近似解。而即使是准确解法，也只能求到近似解。而即使是准确解法，也只能求到近似解。而即使是准确解法，也只能求到近似解。 直接法在求解中小型线性方程组（直接法在求解中小型线性方程组（直接法在求解中小型线性方程组（直接法在求解中小型线性方程组（ 100100个），特别是个），特别是个），特别是个），特别是系数矩阵为稠密型时，是常用的、非常好的方法。系数矩阵为稠密型时，是常用的、非常好的方法。系数矩阵为稠密型时，是常用的、非常好的方法。系数矩阵为稠密型时，是常用的、非常好的方法。 1.直接法：指假设计算过程中不产生含入误差，经过有直接法：指假设计算过程中

8、不产生含入误差，经过有直接法：指假设计算过程中不产生含入误差，经过有直接法：指假设计算过程中不产生含入误差，经过有 限步四则运算可求得方程组准确解的方法。限步四则运算可求得方程组准确解的方法。限步四则运算可求得方程组准确解的方法。限步四则运算可求得方程组准确解的方法。2. 2. 迭代法：从给定的方程组的一个近似值出发，构造某迭代法：从给定的方程组的一个近似值出发，构造某迭代法：从给定的方程组的一个近似值出发，构造某迭代法：从给定的方程组的一个近似值出发，构造某种算法逐步将其准确化，一般不能在有限步内得到准确解。种算法逐步将其准确化，一般不能在有限步内得到准确解。种算法逐步将其准确化，一般不能在

9、有限步内得到准确解。种算法逐步将其准确化，一般不能在有限步内得到准确解。 这一章介绍计算机上常用的直接法，它们都是以这一章介绍计算机上常用的直接法，它们都是以这一章介绍计算机上常用的直接法，它们都是以这一章介绍计算机上常用的直接法，它们都是以GaussGauss消元法为基本方法，即先将线性方程组化为等价的三角形消元法为基本方法，即先将线性方程组化为等价的三角形消元法为基本方法，即先将线性方程组化为等价的三角形消元法为基本方法，即先将线性方程组化为等价的三角形方程组，然后求解。方程组，然后求解。方程组，然后求解。方程组，然后求解。第三章第三章 线性方程组直接解法线性方程组直接解法返回前进1Gau

10、ss消元法GaussGauss消元法是最基本的一种方法，下例说明其消元法是最基本的一种方法，下例说明其消元法是最基本的一种方法，下例说明其消元法是最基本的一种方法，下例说明其基本思想基本思想基本思想基本思想: : 例例1解线性方程组：解线性方程组：解线性方程组：解线性方程组： 解：消去解：消去x1，进行第一次消元：首先找乘数，以进行第一次消元：首先找乘数，以-12乘第一个方程加到第二个方程，以乘第一个方程加到第二个方程，以18乘第一个乘第一个方程加到第三个方程上可得同解方程组：方程加到第三个方程上可得同解方程组： 第三章第三章 线性方程组直接解法线性方程组直接解法返回前进例1（续） 上述上述上

11、述上述GaussGauss消元法的基本思想是：先逐次消去变量，将消元法的基本思想是：先逐次消去变量，将消元法的基本思想是：先逐次消去变量，将消元法的基本思想是：先逐次消去变量，将方程组化成同解的上三角形方程组，此过程称为消元过方程组化成同解的上三角形方程组，此过程称为消元过方程组化成同解的上三角形方程组，此过程称为消元过方程组化成同解的上三角形方程组，此过程称为消元过程。然后按方程相反顺序求解上三角形方程组，得到原程。然后按方程相反顺序求解上三角形方程组，得到原程。然后按方程相反顺序求解上三角形方程组，得到原程。然后按方程相反顺序求解上三角形方程组，得到原方程组的解，此过程称为回代过程。方程组

12、的解，此过程称为回代过程。方程组的解，此过程称为回代过程。方程组的解，此过程称为回代过程。再消再消一次元得：一次元得： 二次消元后将方程化为二次消元后将方程化为二次消元后将方程化为二次消元后将方程化为倒三角形式，然后进行倒三角形式，然后进行倒三角形式，然后进行倒三角形式，然后进行回代容易解出：回代容易解出：回代容易解出：回代容易解出： x3 = 3, x2 = 2, x1 = 1。 我们的目的，是要总结归纳出一般情况下的我们的目的，是要总结归纳出一般情况下的我们的目的，是要总结归纳出一般情况下的我们的目的，是要总结归纳出一般情况下的n n阶线性方程阶线性方程阶线性方程阶线性方程组的消元公式和回

13、代求解公式，从而得到求解组的消元公式和回代求解公式，从而得到求解组的消元公式和回代求解公式，从而得到求解组的消元公式和回代求解公式，从而得到求解n n阶线性方阶线性方阶线性方阶线性方程组的能顺利在计算机上实现的行之有效的算法。程组的能顺利在计算机上实现的行之有效的算法。程组的能顺利在计算机上实现的行之有效的算法。程组的能顺利在计算机上实现的行之有效的算法。 第三章第三章 线性方程组直接解法线性方程组直接解法返回前进 为能更清楚地得到算法，下面以为能更清楚地得到算法，下面以为能更清楚地得到算法，下面以为能更清楚地得到算法，下面以4 4阶线性方程组为例总结阶线性方程组为例总结阶线性方程组为例总结阶

14、线性方程组为例总结求解步骤，并且很容易地可推广至一般的求解步骤，并且很容易地可推广至一般的求解步骤，并且很容易地可推广至一般的求解步骤，并且很容易地可推广至一般的n n阶线性方程组。阶线性方程组。阶线性方程组。阶线性方程组。第三章第三章 线性方程组直接解法线性方程组直接解法返回前进 可以检查，分别以可以检查，分别以可以检查，分别以可以检查，分别以 l li i1 1乘第一个方程加到第乘第一个方程加到第乘第一个方程加到第乘第一个方程加到第i i个方程上个方程上个方程上个方程上可以完成第一次消元，得同解方程组：可以完成第一次消元，得同解方程组：可以完成第一次消元，得同解方程组：可以完成第一次消元，

15、得同解方程组：变化以后的方变化以后的方变化以后的方变化以后的方程组系数及右程组系数及右程组系数及右程组系数及右边的常数项可边的常数项可边的常数项可边的常数项可总结出如下的总结出如下的总结出如下的总结出如下的计算公式：计算公式：计算公式：计算公式： 完成第一次消元之后的完成第一次消元之后的完成第一次消元之后的完成第一次消元之后的方程组记为：方程组记为：方程组记为：方程组记为： A(2) x = b (2) 第三章第三章 线性方程组直接解法线性方程组直接解法返回前进Gauss消元法的基本步骤3（4阶） 以方程组中第以方程组中第以方程组中第以方程组中第i i个方程减去第二个方程乘个方程减去第二个方程

16、乘个方程减去第二个方程乘个方程减去第二个方程乘l li i2 2 ( (i i = 3,4)= 3,4)，完完完完成第二次消元。成第二次消元。成第二次消元。成第二次消元。 上标为上标为上标为上标为3 3的系数的系数的系数的系数和右端项可由和右端项可由和右端项可由和右端项可由下面公式计算：下面公式计算：下面公式计算：下面公式计算：第三章第三章 线性方程组直接解法线性方程组直接解法返回前进第三步第三步第三步第三步：消元（：消元（：消元（：消元（4 4阶方程组需进行阶方程组需进行阶方程组需进行阶方程组需进行3 3次消元）次消元）次消元）次消元） 将上述将上述将上述将上述 A A (3) (3) X

17、X = = b b(3) (3) 中最后一个方程中的中最后一个方程中的中最后一个方程中的中最后一个方程中的x x3 3消为零消为零消为零消为零： 然后可回代求解：由于然后可回代求解：由于然后可回代求解：由于然后可回代求解：由于A A(4)(4)为上三角形，所以可为上三角形，所以可为上三角形，所以可为上三角形，所以可按变量的逆序逐步回代求按变量的逆序逐步回代求按变量的逆序逐步回代求按变量的逆序逐步回代求原方程组的解：原方程组的解：原方程组的解：原方程组的解： 上述上述上述上述 消元、回代求解过程消元、回代求解过程消元、回代求解过程消元、回代求解过程很容易推广到一般的很容易推广到一般的很容易推广到

18、一般的很容易推广到一般的n n阶线阶线阶线阶线性方程组。性方程组。性方程组。性方程组。 经过上述消元步骤，经过上述消元步骤，经过上述消元步骤，经过上述消元步骤，得到同解的上三角形得到同解的上三角形得到同解的上三角形得到同解的上三角形方程组：方程组：方程组：方程组：A (4) x = b(4) 第三章第三章 线性方程组直接解法线性方程组直接解法返回前进Gauss消元法的消元过程1、2（n阶）一般地，设一般地，设一般地，设一般地，设 n n阶方程组：阶方程组：阶方程组：阶方程组：消元过程为：消元过程为：消元过程为：消元过程为： 将上方程组中第将上方程组中第将上方程组中第将上方程组中第i i个方程减

19、去第个方程减去第个方程减去第个方程减去第2 2个方程乘以个方程乘以个方程乘以个方程乘以l li i2 2 ( (i i=3,=3,n n) )，完成完成完成完成第二步消元。第二步消元。第二步消元。第二步消元。 第三章第三章 线性方程组直接解法线性方程组直接解法返回前进第第第第k k 步：设第步：设第步：设第步：设第k k 1 1步消元后得原方程组的同解方程组为：步消元后得原方程组的同解方程组为：步消元后得原方程组的同解方程组为：步消元后得原方程组的同解方程组为： 第第第第k k步消元后同步消元后同步消元后同步消元后同解方程组中上标解方程组中上标解方程组中上标解方程组中上标为为为为k k+1+1

20、的元素的的元素的的元素的的元素的计算公式见下屏计算公式见下屏计算公式见下屏计算公式见下屏第三章第三章 线性方程组直接解法线性方程组直接解法返回前进照此消元下去，完成照此消元下去，完成n 1次次消元后，可将原方程组化成消元后，可将原方程组化成同解的上三角形方程组如下：同解的上三角形方程组如下： 第三章第三章 线性方程组直接解法线性方程组直接解法返回前进Gauss消元法的回代过程（n阶）回代过程回代过程：逐步回代求得原方程组的解逐步回代求得原方程组的解 第三章第三章 线性方程组直接解法线性方程组直接解法返回前进Gauss消元法的计算量 由于在计算机中作乘除运算量所需时间远大于作加减由于在计算机中作

21、乘除运算量所需时间远大于作加减由于在计算机中作乘除运算量所需时间远大于作加减由于在计算机中作乘除运算量所需时间远大于作加减运算所需时间，故只考虑作乘除运算量。运算所需时间，故只考虑作乘除运算量。运算所需时间，故只考虑作乘除运算量。运算所需时间，故只考虑作乘除运算量。 由消元法步骤知，第由消元法步骤知，第由消元法步骤知，第由消元法步骤知，第k k次消元需作次消元需作次消元需作次消元需作n n k k次除法，作次除法，作次除法，作次除法，作( (n n k k)( )(n n k k + 1)+ 1)次乘法，故消元过程中乘除法运算量为：次乘法，故消元过程中乘除法运算量为：次乘法，故消元过程中乘除法

22、运算量为：次乘法，故消元过程中乘除法运算量为： 所以所以所以所以GaussGauss 消去法的消去法的消去法的消去法的乘除法总运算量为：乘除法总运算量为：乘除法总运算量为：乘除法总运算量为： 第三章第三章 线性方程组直接解法线性方程组直接解法返回前进Gauss法与Cramer法则的计算量比较 GaussGauss 消元法的乘消元法的乘消元法的乘消元法的乘除法总运算量为除法总运算量为除法总运算量为除法总运算量为： 与我们曾经介绍的与我们曾经介绍的与我们曾经介绍的与我们曾经介绍的CramerCramer法则的乘除法总运算量法则的乘除法总运算量法则的乘除法总运算量法则的乘除法总运算量 ( (n n2

23、 2 1)1)n n!+!+n n 相比，由下表可知：当阶数越高时，相比，由下表可知：当阶数越高时，相比，由下表可知：当阶数越高时，相比，由下表可知：当阶数越高时，GaussGauss消消消消元法所需乘除法次数比元法所需乘除法次数比元法所需乘除法次数比元法所需乘除法次数比CramerCramer法则要少得多：法则要少得多：法则要少得多：法则要少得多： 方程组阶数方程组阶数方程组阶数方程组阶数3 3101020205050GaussGauss消元法运算量消元法运算量消元法运算量消元法运算量1717430430306030604415044150CramerCramer法则运算量法则运算量法则运算

24、量法则运算量51513592512103592512109.7109.71020207.6107.6106767Gauss Gauss 消元法的优缺点：消元法的优缺点：消元法的优缺点：消元法的优缺点： 但其计算过程中，要求但其计算过程中，要求但其计算过程中，要求但其计算过程中，要求a akkkk( (k k) )（称为主元素）均不为零，称为主元素）均不为零，称为主元素）均不为零，称为主元素）均不为零，因而适用范围小，只适用于从因而适用范围小，只适用于从因而适用范围小，只适用于从因而适用范围小，只适用于从1 1到到到到n n 1 1阶顺序主子式均不阶顺序主子式均不阶顺序主子式均不阶顺序主子式均不

25、为零的矩阵为零的矩阵为零的矩阵为零的矩阵A A，计算实践还表明，计算实践还表明，计算实践还表明，计算实践还表明，GaussGauss消元法的数值稳消元法的数值稳消元法的数值稳消元法的数值稳定性差，当出现小主元素时，会严重影响计算结果的精度，定性差，当出现小主元素时，会严重影响计算结果的精度，定性差，当出现小主元素时，会严重影响计算结果的精度，定性差，当出现小主元素时，会严重影响计算结果的精度，甚至导出错误的结果。甚至导出错误的结果。甚至导出错误的结果。甚至导出错误的结果。 GaussGauss消元法简单易行。消元法简单易行。消元法简单易行。消元法简单易行。第三章第三章 线性方程组直接解法线性方

26、程组直接解法返回前进2主元素法 2.1 引入主元素的必要性引入主元素的必要性 对线性方程组对线性方程组AX = b，若其系数行列式若其系数行列式 det(A) 0，则该方程组有唯一则该方程组有唯一 解，但是这一条件解，但是这一条件 不能保证所有主元素都不等于零，只要某一主元不能保证所有主元素都不等于零，只要某一主元素等于零，就不能用素等于零，就不能用Gauss消元法求解该方程组，消元法求解该方程组，即使所有主元素不等于零，但即使所有主元素不等于零，但 某一主元素的绝对某一主元素的绝对值很小时，值很小时，Gauss消元法也是不适用的。如下例：消元法也是不适用的。如下例： 例例2第三章第三章 线性

27、方程组直接解法线性方程组直接解法返回前进例2（续1） 解：为减小误差，计算过程中保留解：为减小误差，计算过程中保留3位有效数字。位有效数字。 按按Gauss消元法步骤：消元法步骤： 第一次消元后得同解方程组：第一次消元后得同解方程组：第一次消元后得同解方程组：第一次消元后得同解方程组： 第二次消元后得同解方程组第二次消元后得同解方程组第二次消元后得同解方程组第二次消元后得同解方程组 回代得解，回代得解，x3 = 2.02，x2 = 2.40，x1 = 5.80。 容易验证，方程组（容易验证，方程组（3-8）的准确解为：）的准确解为： x1 = 2.60， x2 = 1.00，x3 = 2.0。

28、显然两种结果相差很大。显然两种结果相差很大。第三章第三章 线性方程组直接解法线性方程组直接解法返回前进 若在解方程组前，先交换方程的次序，若在解方程组前，先交换方程的次序，如将（如将（2-8）交换一行与三行改写成如下所示：）交换一行与三行改写成如下所示： 再用再用Gauss消元法，顺序消元后得同解方程组：消元法，顺序消元后得同解方程组：回代得解：回代得解：x3 = 2.00，x2 = 1.00，x1 = 2.60 与准确解相同。与准确解相同。 例2（续2）第三章第三章 线性方程组直接解法线性方程组直接解法返回前进例2两种解法的误差分析 在例在例2中，对中，对(2-8)的方程进行顺序消元时，的方

29、程进行顺序消元时， 主元主元a(1)11=0.50，a(2)22=0.100都比较小，以它们作都比较小，以它们作 除数就增长了舍入误差除数就增长了舍入误差,而导致计算结果不准确。而导致计算结果不准确。 产生上述现象的原因在于舍入误差，当产生上述现象的原因在于舍入误差，当|a(k)kk| 很小时，进行第很小时，进行第k次消元，要用次消元，要用|a(k)kk|作除数，这作除数，这 样就可能增大舍入误差造成溢出停机，或者导致样就可能增大舍入误差造成溢出停机，或者导致 错误的结果。错误的结果。 为了在计算过程中，抑制舍入误差的增长，为了在计算过程中，抑制舍入误差的增长， 应尽量避免小主元的出现。如例应

30、尽量避免小主元的出现。如例2的第二种解法的第二种解法, 通过交换方程次序，选取绝对值大的元素作主元通过交换方程次序，选取绝对值大的元素作主元 基于这种思想而导出主元素法。基于这种思想而导出主元素法。 第三章第三章 线性方程组直接解法线性方程组直接解法返回前进2.2列主元素法 为简便起见，对方为简便起见，对方 程组（程组（2-1），用），用 其增其增 广矩阵：广矩阵： 表示，并直接在增广表示，并直接在增广矩阵上进行运算。矩阵上进行运算。 列主元素法的具体步骤如下：列主元素法的具体步骤如下： 第三章第三章 线性方程组直接解法线性方程组直接解法返回前进列主元素法如此经过如此经过如此经过如此经过n n

31、 1 1步，增广矩阵（步，增广矩阵（步，增广矩阵（步，增广矩阵（2-92-9）被化成上三角形，然）被化成上三角形，然）被化成上三角形，然）被化成上三角形，然后由回代过程求解。后由回代过程求解。后由回代过程求解。后由回代过程求解。 在上述过程中，主元是按列选取的，故称为在上述过程中，主元是按列选取的，故称为在上述过程中，主元是按列选取的，故称为在上述过程中，主元是按列选取的，故称为列主元法列主元法列主元法列主元法。例例例例2 2中的第二种解法就是按列主元法进行的。中的第二种解法就是按列主元法进行的。中的第二种解法就是按列主元法进行的。中的第二种解法就是按列主元法进行的。 第三章第三章 线性方程组

32、直接解法线性方程组直接解法返回前进2.3全主元素法经过经过n k次消元后，得到与方程组（次消元后，得到与方程组（2-1）同解的）同解的上三角形方程组，再由回代过程求解。上三角形方程组，再由回代过程求解。 第三章第三章 线性方程组直接解法线性方程组直接解法返回前进例例6计算过程保留三位小数。 此例的计算结果表明，全主元素法的精度优于列此例的计算结果表明，全主元素法的精度优于列此例的计算结果表明，全主元素法的精度优于列此例的计算结果表明，全主元素法的精度优于列主元法，这是由于全主元法是在全体元素中选主元，主元法，这是由于全主元法是在全体元素中选主元，主元法，这是由于全主元法是在全体元素中选主元，主

33、元法，这是由于全主元法是在全体元素中选主元，故它对控制舍入误差十分有效。但是全主元法在计算故它对控制舍入误差十分有效。但是全主元法在计算故它对控制舍入误差十分有效。但是全主元法在计算故它对控制舍入误差十分有效。但是全主元法在计算过程中，需同时作行与列的互换，因而程序比较复杂过程中，需同时作行与列的互换，因而程序比较复杂过程中，需同时作行与列的互换，因而程序比较复杂过程中，需同时作行与列的互换，因而程序比较复杂, ,计算时间较长。列主元法的精度虽稍低于全主元法，计算时间较长。列主元法的精度虽稍低于全主元法，计算时间较长。列主元法的精度虽稍低于全主元法，计算时间较长。列主元法的精度虽稍低于全主元法

34、，但其计算简单，工作量大为减少，且计算经验与理论但其计算简单，工作量大为减少，且计算经验与理论但其计算简单，工作量大为减少，且计算经验与理论但其计算简单，工作量大为减少，且计算经验与理论分析均表明，它与全主元法同样具有良好的数值稳定分析均表明，它与全主元法同样具有良好的数值稳定分析均表明，它与全主元法同样具有良好的数值稳定分析均表明，它与全主元法同样具有良好的数值稳定性，故列主元法是求解中小型稠密线性方程组的最好性，故列主元法是求解中小型稠密线性方程组的最好性，故列主元法是求解中小型稠密线性方程组的最好性，故列主元法是求解中小型稠密线性方程组的最好方法之一。方法之一。方法之一。方法之一。 方法

35、之一。方法之一。方法之一。方法之一。 第三章第三章 线性方程组直接解法线性方程组直接解法返回前进2.4解三对角方程组的追赶法在很多问题中，需要解如下形式的三对角方程组：在很多问题中，需要解如下形式的三对角方程组：在很多问题中，需要解如下形式的三对角方程组：在很多问题中，需要解如下形式的三对角方程组： 三对角方程组的系数矩阵为三对角阵，对于这种特殊三对角方程组的系数矩阵为三对角阵，对于这种特殊三对角方程组的系数矩阵为三对角阵，对于这种特殊三对角方程组的系数矩阵为三对角阵，对于这种特殊而又简单的方程组，用前面介绍的方法求解由于有大量而又简单的方程组，用前面介绍的方法求解由于有大量而又简单的方程组，

36、用前面介绍的方法求解由于有大量而又简单的方程组，用前面介绍的方法求解由于有大量的零元素既占内存又浪费计算时间，显然很不经济。充的零元素既占内存又浪费计算时间，显然很不经济。充的零元素既占内存又浪费计算时间，显然很不经济。充的零元素既占内存又浪费计算时间，显然很不经济。充分注意到三对角方程组的特点，根据顺序消元的思想导分注意到三对角方程组的特点，根据顺序消元的思想导分注意到三对角方程组的特点，根据顺序消元的思想导分注意到三对角方程组的特点，根据顺序消元的思想导出一个简便的算法出一个简便的算法出一个简便的算法出一个简便的算法追赶法。追赶法。追赶法。追赶法。 第三章第三章 线性方程组直接解法线性方程

37、组直接解法返回前进 首先进行顺序消元，首先进行顺序消元，首先进行顺序消元，首先进行顺序消元，且每步将主元系数且每步将主元系数且每步将主元系数且每步将主元系数化为化为化为化为1 1，将方程组化为：，将方程组化为：，将方程组化为：，将方程组化为：其中系数按下式计算其中系数按下式计算其中系数按下式计算其中系数按下式计算 ：然后回代然后回代然后回代然后回代求解，得：求解，得：求解，得：求解，得： 上述追赶法能进行到底上述追赶法能进行到底上述追赶法能进行到底上述追赶法能进行到底 。第三章第三章 线性方程组直接解法线性方程组直接解法返回前进追赶法举例用追赶法解下用追赶法解下用追赶法解下用追赶法解下列三对角

38、方程组：列三对角方程组：列三对角方程组：列三对角方程组： 例例4解：解：解：解： 首先将方程组化为（先追）：首先将方程组化为（先追）：首先将方程组化为（先追）：首先将方程组化为（先追）： 然后回代（赶）求解：然后回代（赶）求解： x5 = 0，x4 = 30/7， x3 = 6/7，x2 = 12/7， x1 = 0 可以看出，追赶法本质上还可以看出，追赶法本质上还可以看出，追赶法本质上还可以看出，追赶法本质上还是顺序消元法，但由于计算过程是顺序消元法，但由于计算过程是顺序消元法，但由于计算过程是顺序消元法，但由于计算过程中只涉及系数矩阵的非零元，因此大大节约了计算机内存中只涉及系数矩阵的非零

39、元，因此大大节约了计算机内存中只涉及系数矩阵的非零元，因此大大节约了计算机内存中只涉及系数矩阵的非零元，因此大大节约了计算机内存与计算量，按乘除法次数进行比较，与计算量，按乘除法次数进行比较，与计算量，按乘除法次数进行比较，与计算量，按乘除法次数进行比较，GaussGauss消元法约为消元法约为消元法约为消元法约为n n3 3/3/3，全主元法为全主元法为全主元法为全主元法为n n3 3/2/2，而追赶法仅为而追赶法仅为而追赶法仅为而追赶法仅为5 5n n-3-3次，可见追赶次，可见追赶次，可见追赶次，可见追赶法是求解三对角方程组的非常好的方法。法是求解三对角方程组的非常好的方法。法是求解三对

40、角方程组的非常好的方法。法是求解三对角方程组的非常好的方法。 第三章第三章 线性方程组直接解法线性方程组直接解法返回前进3矩阵分解法 如果用矩阵形式表示，如果用矩阵形式表示，如果用矩阵形式表示，如果用矩阵形式表示，GaussGauss消元法的消元过程是对消元法的消元过程是对消元法的消元过程是对消元法的消元过程是对方程组（方程组（方程组（方程组（2-12-1）的增广矩阵（）的增广矩阵（）的增广矩阵（）的增广矩阵（A A、b b）进行一系列的初等行进行一系列的初等行进行一系列的初等行进行一系列的初等行变换，将系数矩阵变换，将系数矩阵变换，将系数矩阵变换，将系数矩阵A A化成上三角矩阵的过程，也等价

41、于用化成上三角矩阵的过程，也等价于用化成上三角矩阵的过程，也等价于用化成上三角矩阵的过程，也等价于用一串初等变换阵去左乘增广矩阵，因此，消元过程可以通一串初等变换阵去左乘增广矩阵，因此，消元过程可以通一串初等变换阵去左乘增广矩阵，因此，消元过程可以通一串初等变换阵去左乘增广矩阵，因此，消元过程可以通过矩阵运算来实现。过矩阵运算来实现。过矩阵运算来实现。过矩阵运算来实现。紧接下屏：紧接下屏：紧接下屏：紧接下屏：3.1 GaussGauss消元法的矩阵形式消元法的矩阵形式消元法的矩阵形式消元法的矩阵形式 事实上，事实上，事实上，事实上，GaussGauss消元法的消元法的消元法的消元法的 第一次消

42、元第一次消元第一次消元第一次消元相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵：第三章第三章 线性方程组直接解法线性方程组直接解法返回前进第二次消元第二次消元第二次消元第二次消元相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵： 第第第第k k次消元次消元次消元次消元相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵： Gauss消元法的矩阵形式第三章第三章 线性方程组直接解法线性方程组直接解法返回前进经过经过经过经过n n 1 1步消元后得到：步消元后得到：步消元后得到：步消元后得到： 因为因为因为因为L Lk k ( (k

43、k = 1,2, = 1,2, n n 1)1)均为非奇异阵，故它们均为非奇异阵，故它们均为非奇异阵，故它们均为非奇异阵，故它们的逆矩阵存在。容易求出：的逆矩阵存在。容易求出：的逆矩阵存在。容易求出：的逆矩阵存在。容易求出： 这说明：在这说明：在这说明：在这说明：在 的条件下，消元过程的条件下，消元过程的条件下，消元过程的条件下，消元过程实际上是把系数矩阵实际上是把系数矩阵实际上是把系数矩阵实际上是把系数矩阵A A分解成单位下三角阵与上三角矩阵分解成单位下三角阵与上三角矩阵分解成单位下三角阵与上三角矩阵分解成单位下三角阵与上三角矩阵的乘积的过程。的乘积的过程。的乘积的过程。的乘积的过程。 Ga

44、uss消元法的矩阵形式（续）第三章第三章 线性方程组直接解法线性方程组直接解法返回前进杜利特尔（Doolittle）分解LU分解 事实上，只要事实上，只要事实上，只要事实上，只要A A满足一定条件，由上述结论，它一定满足一定条件，由上述结论，它一定满足一定条件，由上述结论，它一定满足一定条件，由上述结论，它一定可以分解成两个三角形矩阵的乘积，即：可以分解成两个三角形矩阵的乘积，即：可以分解成两个三角形矩阵的乘积，即：可以分解成两个三角形矩阵的乘积，即：A=LU A=LU 。 上述分解称为杜利特尔（上述分解称为杜利特尔（上述分解称为杜利特尔（上述分解称为杜利特尔（DoolittleDoolitt

45、le）分解，也称为分解，也称为分解，也称为分解，也称为LULU分解，分解，分解，分解，当系数矩阵完成三角分解后，对于求解方程组：当系数矩阵完成三角分解后，对于求解方程组：当系数矩阵完成三角分解后，对于求解方程组：当系数矩阵完成三角分解后，对于求解方程组：AxAx = = b b。 消元过程相当于分解消元过程相当于分解消元过程相当于分解消元过程相当于分解A A = = LULU及求解三角形方程组及求解三角形方程组及求解三角形方程组及求解三角形方程组LyLy = = b b，回代过程则是求解另一个三角形方程组回代过程则是求解另一个三角形方程组回代过程则是求解另一个三角形方程组回代过程则是求解另一个

46、三角形方程组UxUx = = y y，因此，因此，因此，因此，解线性方程组问题可转化为矩阵的三角分解问题。解线性方程组问题可转化为矩阵的三角分解问题。解线性方程组问题可转化为矩阵的三角分解问题。解线性方程组问题可转化为矩阵的三角分解问题。 其中：其中：其中：其中：L L为单位下三角矩阵，为单位下三角矩阵，为单位下三角矩阵，为单位下三角矩阵，U U为上三角矩阵：为上三角矩阵：为上三角矩阵：为上三角矩阵：第三章第三章 线性方程组直接解法线性方程组直接解法返回前进3.2矩阵的三角分解 正如正如正如正如GaussGauss消元法要在一定条件下才能进行到底一样，消元法要在一定条件下才能进行到底一样，消元

47、法要在一定条件下才能进行到底一样，消元法要在一定条件下才能进行到底一样，矩阵矩阵矩阵矩阵A A也必须满足一定条件才能进行三角分解。也必须满足一定条件才能进行三角分解。也必须满足一定条件才能进行三角分解。也必须满足一定条件才能进行三角分解。 设设设设A A为为为为n n阶方阵，若阶方阵，若阶方阵，若阶方阵，若A A的顺序主子式的顺序主子式的顺序主子式的顺序主子式A Ai i( (i i = 1,2,= 1,2,n n ) )均不为零均不为零均不为零均不为零, ,则矩阵则矩阵则矩阵则矩阵A A存在唯一的存在唯一的存在唯一的存在唯一的DoolittleDoolittle分解。分解。分解。分解。 定理

48、定理2.1下面讨论如何对下面讨论如何对下面讨论如何对下面讨论如何对A A进行进行进行进行LULU分解分解分解分解： （1 1行行行行1 1列列列列） 由于两个矩阵相等就是它们的对应元素都相等，因此由于两个矩阵相等就是它们的对应元素都相等，因此由于两个矩阵相等就是它们的对应元素都相等，因此由于两个矩阵相等就是它们的对应元素都相等，因此通过比较通过比较通过比较通过比较A A与与与与LULU的对应元素，即可得到直接计算的对应元素，即可得到直接计算的对应元素，即可得到直接计算的对应元素，即可得到直接计算L L、U U的的的的元素的公式：元素的公式：元素的公式：元素的公式：A A= =LU LU 即：即

49、：即：即： 紧接下屏：紧接下屏：紧接下屏：紧接下屏：第三章第三章 线性方程组直接解法线性方程组直接解法返回前进对A进行LU分解ALU由矩阵乘法规则及比较（由矩阵乘法规则及比较（由矩阵乘法规则及比较（由矩阵乘法规则及比较（2-112-11）两端的元素，得：）两端的元素，得：）两端的元素，得：）两端的元素，得：即可由（即可由（即可由（即可由（2-122-12）求出）求出）求出）求出U U的第一行，的第一行，的第一行，的第一行，L L的第一列。的第一列。的第一列。的第一列。 下面讨论一般情况，即：下面讨论一般情况，即：下面讨论一般情况，即：下面讨论一般情况，即：U U的第的第的第的第i i 行，行，

50、行，行，L L的第的第的第的第j j列：列：列：列：第三章第三章 线性方程组直接解法线性方程组直接解法返回前进一般情况下，可由：一般情况下，可由：一般情况下，可由：一般情况下，可由：对A进行LU分解（r 行r 列）计算过程应按计算过程应按计算过程应按计算过程应按U U第第第第1 1行、行、行、行、L L第第第第1 1列列列列（第（第（第（第1 1框），框），框），框），U U第第第第2 2行、行、行、行、L L第第第第2 2列列列列（第（第（第（第2 2框），框），框），框），的顺序的顺序的顺序的顺序 具体分解步具体分解步具体分解步具体分解步骤见下屏：骤见下屏：骤见下屏：骤见下屏： 得到计算得

51、到计算得到计算得到计算u uij ij和和和和 l lij ij 的公式：的公式：的公式：的公式： 第三章第三章 线性方程组直接解法线性方程组直接解法返回前进对A进行LU分解的具体步骤1. 计算计算U的第的第1行，行，L的第的第1列，亦称为计算列，亦称为计算 第第1框；框； 2. 计算计算U的第的第r 行，行，L的第的第r 列（列（r =2,n），）， 即第即第r 框框 ：第三章第三章 线性方程组直接解法线性方程组直接解法返回前进矩阵A的LU分解举例解：按分解公式（解：按分解公式（解：按分解公式（解：按分解公式（2-132-13），），），），一框一框分解，每框计算时先行后列一框一框分解，每框

52、计算时先行后列一框一框分解，每框计算时先行后列一框一框分解，每框计算时先行后列 ：所以：所以：所以：所以：例例例例5 5 第三章第三章 线性方程组直接解法线性方程组直接解法返回前进3.3直接三角分解法 若线性方程组若线性方程组若线性方程组若线性方程组Ax Ax = = b b的系数矩阵的系数矩阵的系数矩阵的系数矩阵A A完成三角分解，完成三角分解，完成三角分解，完成三角分解，A A = = LULU，那么解那么解那么解那么解方程组方程组方程组方程组Ax Ax = = b b等价于求解两个三角等价于求解两个三角等价于求解两个三角等价于求解两个三角形方程组形方程组形方程组形方程组Ly Ly = =

53、 b b，UxUx = = y y，即由：即由：即由：即由： 再再再再由：由：由：由：可解得：可解得：可解得：可解得：第三章第三章 线性方程组直接解法线性方程组直接解法返回前进直接三角分解法（续） 容易看出，式（容易看出，式（容易看出，式（容易看出，式（2-142-14）与式（）与式（）与式（）与式（2-132-13）的运算规律相同，）的运算规律相同，）的运算规律相同，）的运算规律相同， 或者由：或者由：或者由：或者由：第三章第三章 线性方程组直接解法线性方程组直接解法返回前进解线性方程组举例例例6解解 ：按表：按表：按表：按表2-32-3计算：计算：计算：计算：第三章第三章 线性方程组直接解

54、法线性方程组直接解法返回前进第三章第三章 线性方程组直接解法线性方程组直接解法返回前进三角分解法的几点说明1 1、用三角分解法求线性方程的乘除法运算量也是、用三角分解法求线性方程的乘除法运算量也是、用三角分解法求线性方程的乘除法运算量也是、用三角分解法求线性方程的乘除法运算量也是n n3 3/3 /3 数量级。由于在求出数量级。由于在求出数量级。由于在求出数量级。由于在求出u uij ij, , l lij ij和和和和y yi i后，后，后，后，a aij ij和和和和b bi i无需保留，无需保留，无需保留，无需保留， 故上机计算时，可把故上机计算时，可把故上机计算时，可把故上机计算时，可

55、把L L，U U和和和和y y存在存在存在存在A A，b b所占的单元，所占的单元，所占的单元，所占的单元， 回代时回代时回代时回代时x x取代取代取代取代y y，整个计算过程中不需要增加新的存整个计算过程中不需要增加新的存整个计算过程中不需要增加新的存整个计算过程中不需要增加新的存 贮贮贮贮单元。单元。单元。单元。3 3、完成、完成、完成、完成A=LUA=LU分解后可以较容易地求出行列式分解后可以较容易地求出行列式分解后可以较容易地求出行列式分解后可以较容易地求出行列式| |A A| |的值：的值：的值：的值： 2 2、从三角分解法的推导及例中可以看出，系数矩阵的、从三角分解法的推导及例中可

56、以看出，系数矩阵的、从三角分解法的推导及例中可以看出，系数矩阵的、从三角分解法的推导及例中可以看出，系数矩阵的 三三三三 角分解与右端项无关。因角分解与右端项无关。因角分解与右端项无关。因角分解与右端项无关。因 而在计算多个系数矩阵而在计算多个系数矩阵而在计算多个系数矩阵而在计算多个系数矩阵 为为为为A A而右端不同的线性方程组系时，用三角分解法更而右端不同的线性方程组系时，用三角分解法更而右端不同的线性方程组系时，用三角分解法更而右端不同的线性方程组系时，用三角分解法更 为为为为 简便（如可用于求逆矩阵）。简便（如可用于求逆矩阵）。简便（如可用于求逆矩阵）。简便（如可用于求逆矩阵）。第三章第

57、三章 线性方程组直接解法线性方程组直接解法返回前进三角分解法的几点说明（续）6 6、分解法的优点除上述分解法的优点除上述分解法的优点除上述分解法的优点除上述2 2、3 3外，还有：外，还有：外，还有：外，还有： a a. . 可求解可求解可求解可求解A A2 2z z = = b b, ,因为算因为算因为算因为算A A2 2计算量大，可用计算量大，可用计算量大，可用计算量大，可用 b b. . 可根据可根据可根据可根据A A的形状设计算法，当的形状设计算法，当的形状设计算法，当的形状设计算法，当A A为大型稀疏，且非零为大型稀疏，且非零为大型稀疏，且非零为大型稀疏，且非零元素有规律如带状，三对

58、角等，作分解时能充分利用元素有规律如带状，三对角等，作分解时能充分利用元素有规律如带状，三对角等，作分解时能充分利用元素有规律如带状，三对角等，作分解时能充分利用A A的的的的特点，特点，特点，特点，L L，U U能保持能保持能保持能保持A A的原状，即的原状，即的原状，即的原状，即L L与与与与A A的下三角相同，的下三角相同，的下三角相同，的下三角相同，U U与与与与A A的上三角形状相同。的上三角形状相同。的上三角形状相同。的上三角形状相同。 4 4、三角分解法一般也可采用选主元的技术，以使算法更、三角分解法一般也可采用选主元的技术，以使算法更、三角分解法一般也可采用选主元的技术，以使算

59、法更、三角分解法一般也可采用选主元的技术，以使算法更 具数值稳定性。具数值稳定性。具数值稳定性。具数值稳定性。5 5、也可以把矩阵、也可以把矩阵、也可以把矩阵、也可以把矩阵A A分解成一个下三角矩阵与一个单位上三分解成一个下三角矩阵与一个单位上三分解成一个下三角矩阵与一个单位上三分解成一个下三角矩阵与一个单位上三 角矩阵的乘积，矩阵的角矩阵的乘积，矩阵的角矩阵的乘积，矩阵的角矩阵的乘积，矩阵的 这种分解称为克劳特（这种分解称为克劳特（这种分解称为克劳特（这种分解称为克劳特（CroutCrout） 分解。分解。分解。分解。第三章第三章 线性方程组直接解法线性方程组直接解法返回前进解线性方程组举例

60、例：下述矩阵能否分解为例：下述矩阵能否分解为例：下述矩阵能否分解为例：下述矩阵能否分解为LULU（其中（其中（其中（其中L L为单位下三角阵，为单位下三角阵，为单位下三角阵，为单位下三角阵，U U为为为为上三角阵）？若能分解，那么分解是否惟一？上三角阵）？若能分解，那么分解是否惟一？上三角阵）？若能分解，那么分解是否惟一？上三角阵）？若能分解，那么分解是否惟一？第三章第三章 线性方程组直接解法线性方程组直接解法返回前进4平方根法与改进的平方根法对称正定矩阵概念：对称正定矩阵概念： 工程实际问题的计算中，线性方程组的系数矩阵常工程实际问题的计算中，线性方程组的系数矩阵常工程实际问题的计算中，线性

61、方程组的系数矩阵常工程实际问题的计算中，线性方程组的系数矩阵常常具有对称正定性，即其各阶顺序主子式及全部特征值均常具有对称正定性，即其各阶顺序主子式及全部特征值均常具有对称正定性，即其各阶顺序主子式及全部特征值均常具有对称正定性，即其各阶顺序主子式及全部特征值均大于零。矩阵的这一特性使它的三角分解也有更简单的形大于零。矩阵的这一特性使它的三角分解也有更简单的形大于零。矩阵的这一特性使它的三角分解也有更简单的形大于零。矩阵的这一特性使它的三角分解也有更简单的形式，从而导出一些特殊的解法。式，从而导出一些特殊的解法。式，从而导出一些特殊的解法。式，从而导出一些特殊的解法。 5. 5. A A的所有

62、顺序主子式均为正数，的所有顺序主子式均为正数，的所有顺序主子式均为正数，的所有顺序主子式均为正数，即即即即detdet( (A Ak k)0, )0, k k = 1,2, = 1,2,n n) ) 。 4. 4. A A的所有特征值的所有特征值的所有特征值的所有特征值00； 3. 3. A A的对角线元素的对角线元素的对角线元素的对角线元素a aii ii0(0(i i = 1,2, = 1,2,n n) )； 2. 2. A A是非奇异阵，且是非奇异阵，且是非奇异阵，且是非奇异阵，且A A 1 1也是对称正定阵；也是对称正定阵；也是对称正定阵；也是对称正定阵； 1. 1. A A的所有顺序

63、主子矩阵的所有顺序主子矩阵的所有顺序主子矩阵的所有顺序主子矩阵A Ak k( (k k=1,2,=1,2,n n) )也是对称正定阵；也是对称正定阵；也是对称正定阵；也是对称正定阵； 若若若若A A为对称正定矩阵，则：为对称正定矩阵，则：为对称正定矩阵，则：为对称正定矩阵，则：第三章第三章 线性方程组直接解法线性方程组直接解法返回前进4.1平方根法定理定理定理定理 2.22.2若若A是对称正定矩阵，则存在唯一的单位下三是对称正定矩阵，则存在唯一的单位下三角矩阵角矩阵L和对角阵：和对角阵： 证明：证明： 首先首先A可直接作可直接作LU分解，记为分解，记为A =LU1 ，其中：其中：第三章第三章

64、线性方程组直接解法线性方程组直接解法返回前进定理2.2（续）其中其中其中其中U U0 0是单位上三角阵，则由是单位上三角阵，则由是单位上三角阵，则由是单位上三角阵，则由A A的对称性可得：的对称性可得：的对称性可得：的对称性可得： 再由唯一性得再由唯一性得再由唯一性得再由唯一性得U U0 0 = = L LT T，所以所以所以所以A A = = LDLLDLT T，并且这种分解并且这种分解并且这种分解并且这种分解是唯一的，又由于是唯一的，又由于是唯一的，又由于是唯一的，又由于U U1 1的对角线元素的对角线元素的对角线元素的对角线元素U Ukkkk就是就是就是就是GaussGauss消元法的消

65、元法的消元法的消元法的主元素：主元素：主元素：主元素： 由于由于LD1/2是下三角阵，因此有推论：是下三角阵，因此有推论：第三章第三章 线性方程组直接解法线性方程组直接解法返回前进Choleskg分解1推推论论 若若若若A A是对称正定矩阵，则存在唯一的主对角线元素是对称正定矩阵，则存在唯一的主对角线元素是对称正定矩阵，则存在唯一的主对角线元素是对称正定矩阵，则存在唯一的主对角线元素都为正的下三角阵都为正的下三角阵都为正的下三角阵都为正的下三角阵L L，使得：使得：使得：使得： A=LLA=LLT T矩阵的这种分解称为矩阵的这种分解称为矩阵的这种分解称为矩阵的这种分解称为CholeskgCho

66、leskg分解。分解。分解。分解。用比较法可以导出用比较法可以导出用比较法可以导出用比较法可以导出L L的计算公式。设：的计算公式。设：的计算公式。设：的计算公式。设： 比较比较比较比较A A与与与与LLLLT T的相应元素，的相应元素，的相应元素，的相应元素，即由即由即由即由A A = = LLLLT T可得：可得：可得：可得：计算顺序计算顺序按列进行按列进行。 因此：因此：第三章第三章 线性方程组直接解法线性方程组直接解法返回前进Choleskg分解2当完成矩阵当完成矩阵当完成矩阵当完成矩阵A A的的的的CholeskyCholesky分解后，分解后，分解后，分解后，求解方求解方求解方求解

67、方 程组程组程组程组AXAX = = b b就转化求：就转化求：就转化求：就转化求： 求解对称求解对称求解对称求解对称正定线性方正定线性方正定线性方正定线性方程组的方法程组的方法程组的方法程组的方法称为平方根称为平方根称为平方根称为平方根法，也称为法，也称为法，也称为法，也称为CholeskyCholesky分分分分解法，这种解法，这种解法，这种解法，这种方法无需选方法无需选方法无需选方法无需选主元，计算过程也是稳定的。由于主元，计算过程也是稳定的。由于主元，计算过程也是稳定的。由于主元，计算过程也是稳定的。由于A A的对称性，平方根法的对称性，平方根法的对称性，平方根法的对称性，平方根法的乘

68、除运算量为的乘除运算量为的乘除运算量为的乘除运算量为n n3 3/6/6数量级，约为直接分解法的一半。上数量级，约为直接分解法的一半。上数量级，约为直接分解法的一半。上数量级，约为直接分解法的一半。上机计算时，所需存贮单元也少，只要存贮机计算时，所需存贮单元也少，只要存贮机计算时，所需存贮单元也少，只要存贮机计算时，所需存贮单元也少，只要存贮A A的下三角部分的下三角部分的下三角部分的下三角部分和右端项和右端项和右端项和右端项b b，计算中计算中计算中计算中L L存放于存放于存放于存放于A A的存贮单元，的存贮单元，的存贮单元，的存贮单元，y y , , x x存放在存放在存放在存放在b b的

69、存贮单元。平方根法的不足之处在于需作的存贮单元。平方根法的不足之处在于需作的存贮单元。平方根法的不足之处在于需作的存贮单元。平方根法的不足之处在于需作n n次开方运算。次开方运算。次开方运算。次开方运算。它们的解分别为：它们的解分别为：它们的解分别为：它们的解分别为：第三章第三章 线性方程组直接解法线性方程组直接解法返回前进平方根法举例 用平方根法解用平方根法解用平方根法解用平方根法解对称正定方程组：对称正定方程组：对称正定方程组：对称正定方程组： 例例7解解解解 ：先分解系数矩阵：先分解系数矩阵：先分解系数矩阵：先分解系数矩阵A A，只对只对只对只对A A的下三角部分运算即可，的下三角部分运

70、算即可，的下三角部分运算即可，的下三角部分运算即可，所以只存放所以只存放所以只存放所以只存放A A的下三角部分：的下三角部分：的下三角部分：的下三角部分：第三章第三章 线性方程组直接解法线性方程组直接解法返回前进4.2改进的平方根法由定理由定理由定理由定理2.22.2，对称正定矩，对称正定矩，对称正定矩，对称正定矩阵阵阵阵A A又可以作如下分解又可以作如下分解又可以作如下分解又可以作如下分解 ：其中，其中，其中，其中，L L是单位下三角阵，是单位下三角阵，是单位下三角阵，是单位下三角阵，D D是对角阵，是对角阵，是对角阵，是对角阵，U U = = DLDLT T。由于由于由于由于U U = =

71、 DLDLT T，即：即：即：即： 比较两边的比较两边的比较两边的比较两边的对应元素可得对应元素可得对应元素可得对应元素可得 ：的三角分解可得：的三角分解可得：的三角分解可得：的三角分解可得：第三章第三章 线性方程组直接解法线性方程组直接解法返回前进改进的平方根法说明 基于上述基于上述基于上述基于上述LDLLDLT T分解的方法称为改进的平方根法，其乘分解的方法称为改进的平方根法，其乘分解的方法称为改进的平方根法，其乘分解的方法称为改进的平方根法，其乘除运算量与除运算量与除运算量与除运算量与CholeskyCholesky分解相当，且避免了开方运算。计算分解相当，且避免了开方运算。计算分解相当

72、，且避免了开方运算。计算分解相当，且避免了开方运算。计算顺序按先行后列逐层分解计算；顺序按先行后列逐层分解计算；顺序按先行后列逐层分解计算；顺序按先行后列逐层分解计算； 对称正定阵对称正定阵对称正定阵对称正定阵A A完成完成完成完成A A = L = LDLDLT T= = LULU分解后，求解方程组：分解后，求解方程组：分解后，求解方程组：分解后，求解方程组：AxAx = = b b，就转化为求解就转化为求解就转化为求解就转化为求解 ： 并且由于求并且由于求并且由于求并且由于求y y和求和求和求和求U U的最后一列的算法完全相同，所以的最后一列的算法完全相同，所以的最后一列的算法完全相同，所

73、以的最后一列的算法完全相同，所以可将可将可将可将y y视为视为视为视为U U的最后一列进行计算。的最后一列进行计算。的最后一列进行计算。的最后一列进行计算。 按上述算法，当按上述算法，当按上述算法，当按上述算法，当A A为对称正定阵时，单位下三角阵为对称正定阵时，单位下三角阵为对称正定阵时，单位下三角阵为对称正定阵时，单位下三角阵L L的的的的元素不必按紧凑格式方法去求解，而只需在求得元素不必按紧凑格式方法去求解，而只需在求得元素不必按紧凑格式方法去求解，而只需在求得元素不必按紧凑格式方法去求解，而只需在求得U U的第的第的第的第k k行元素后，以它们去除以行元素后，以它们去除以行元素后，以它

74、们去除以行元素后，以它们去除以u ukkkk即得相应的即得相应的即得相应的即得相应的L L的第的第的第的第k k列元素，列元素，列元素，列元素，这样就大大减少了计算量。这样就大大减少了计算量。这样就大大减少了计算量。这样就大大减少了计算量。第三章第三章 线性方程组直接解法线性方程组直接解法返回前进改进的平方根法举例 用改进的平方用改进的平方用改进的平方用改进的平方根法求解方程组：根法求解方程组：根法求解方程组：根法求解方程组：例例8 改进平方根法由于对矩阵改进平方根法由于对矩阵改进平方根法由于对矩阵改进平方根法由于对矩阵A A无正定要求（只要无正定要求（只要无正定要求（只要无正定要求（只要u ukkkk 0 0 ），），），），( (k k = 1,2, = 1,2,n n) )即可，而正定要求即可，而正定要求即可，而正定要求即可，而正定要求u ukkkk 0 ( 0 (k k = 1,2, = 1,2,n n) )，因因因因此是求解对称方程组常用的方法。此是求解对称方程组常用的方法。此是求解对称方程组常用的方法。此是求解对称方程组常用的方法。