第三章线性方程组直接解法精选文档.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.1 GaussGauss消去法的矩阵形式消去法的矩阵形式消去法的矩

2、阵形式消去法的矩阵形式 3.2 3.2 矩阵的三角分解矩阵的三角分解矩阵的三角分解矩阵的三角分解 3.3 3.3 直接三角分解法直接三角分解法直接三角分解法直接三角分解法4.4.平方根法与改进的平方根法平方根法与改进的平方根法平方根法与改进的平方根法平方根法与改进的平方根法5.5.矩阵求逆矩阵求逆矩阵求逆矩阵求逆6.方程组的性态和条件数方程组的性态和条件数本讲稿第二页，共五十三页 设设设设n n阶线性方程组：阶线性方程组：阶线性方程组：阶线性方程组：其矩阵形式为：其矩阵形式为：其矩阵形式为：其矩阵形式为：Ax=b (2-2)其中：其中：其中：其中：在科学研究和工程技术中所提出的计算问题中，线性

3、在科学研究和工程技术中所提出的计算问题中，线性在科学研究和工程技术中所提出的计算问题中，线性在科学研究和工程技术中所提出的计算问题中，线性方程组的求解问题是基本的，常见的，很多问题如插值函方程组的求解问题是基本的，常见的，很多问题如插值函方程组的求解问题是基本的，常见的，很多问题如插值函方程组的求解问题是基本的，常见的，很多问题如插值函数，最小二乘数据拟合，构造求解微分方程的差分格式等数，最小二乘数据拟合，构造求解微分方程的差分格式等数，最小二乘数据拟合，构造求解微分方程的差分格式等数，最小二乘数据拟合，构造求解微分方程的差分格式等，都包含了解线性方程组问题，因此，线性方程组的解法，都包含了解

4、线性方程组问题，因此，线性方程组的解法，都包含了解线性方程组问题，因此，线性方程组的解法，都包含了解线性方程组问题，因此，线性方程组的解法在数值计算中占有较重要的地位。在数值计算中占有较重要的地位。在数值计算中占有较重要的地位。在数值计算中占有较重要的地位。本讲稿第三页，共五十三页 求解求解Ax=b，曾经学过高斯（，曾经学过高斯（Gauss）消元法，克莱）消元法，克莱姆（姆（Cramer）法则，矩阵变换法等，但已远）法则，矩阵变换法等，但已远远满足不了实际运算的需要，主要体现两个方面：一远满足不了实际运算的需要，主要体现两个方面：一是运算的快速和准确，其次是方程组的个数增大时的是运算的快速和准

5、确，其次是方程组的个数增大时的计算问题。如何建立能在计算机上可以实现的有效而计算问题。如何建立能在计算机上可以实现的有效而实用的解法，具有极其重要的意义，我们也曾指出过，实用的解法，具有极其重要的意义，我们也曾指出过，Cramer法则在理论上是绝对正确的，但当法则在理论上是绝对正确的，但当n较大时，较大时，在实际计算中却不能用。在实际计算中却不能用。如果线性方程组如果线性方程组Ax=b的系数行列式不为零，即的系数行列式不为零，即det(A)0，则该方程组有唯一解。，则该方程组有唯一解。本讲稿第四页，共五十三页线性方程组的数值解法解线性方程组的数值方法大致分为两类：解线性方程组的数值方法大致分为

6、两类：解线性方程组的数值方法大致分为两类：解线性方程组的数值方法大致分为两类：请注意：由于在计算中某些数据实际上只能用有限位小请注意：由于在计算中某些数据实际上只能用有限位小请注意：由于在计算中某些数据实际上只能用有限位小请注意：由于在计算中某些数据实际上只能用有限位小 数，即不可避免地存在着舍入误差的影响，因数，即不可避免地存在着舍入误差的影响，因数，即不可避免地存在着舍入误差的影响，因数，即不可避免地存在着舍入误差的影响，因 而即使是准确解法，也只能求到近似解。而即使是准确解法，也只能求到近似解。而即使是准确解法，也只能求到近似解。而即使是准确解法，也只能求到近似解。直接法在求解中小型线性

7、方程组（直接法在求解中小型线性方程组（直接法在求解中小型线性方程组（直接法在求解中小型线性方程组（100100个），特别是系数矩阵个），特别是系数矩阵个），特别是系数矩阵个），特别是系数矩阵为稠密型时，是常用的、非常好的方法。为稠密型时，是常用的、非常好的方法。为稠密型时，是常用的、非常好的方法。为稠密型时，是常用的、非常好的方法。1.1.直接法：指假设计算过程中不产生含入误差，经过有直接法：指假设计算过程中不产生含入误差，经过有直接法：指假设计算过程中不产生含入误差，经过有直接法：指假设计算过程中不产生含入误差，经过有 限步四则运算可求得方程组准确解的方法。限步四则运算可求得方程组准确解的方

8、法。限步四则运算可求得方程组准确解的方法。限步四则运算可求得方程组准确解的方法。2.2.迭代法：从给定的方程组的一个近似值出发，构造某种算法逐迭代法：从给定的方程组的一个近似值出发，构造某种算法逐迭代法：从给定的方程组的一个近似值出发，构造某种算法逐迭代法：从给定的方程组的一个近似值出发，构造某种算法逐步将其准确化，一般不能在有限步内得到准确解。步将其准确化，一般不能在有限步内得到准确解。步将其准确化，一般不能在有限步内得到准确解。步将其准确化，一般不能在有限步内得到准确解。这一章介绍计算机上常用的直接法，它们都是以这一章介绍计算机上常用的直接法，它们都是以这一章介绍计算机上常用的直接法，它们

9、都是以这一章介绍计算机上常用的直接法，它们都是以GaussGauss消元法为消元法为消元法为消元法为基本方法，即先将线性方程组化为等价的三角形方程组，然后求解。基本方法，即先将线性方程组化为等价的三角形方程组，然后求解。基本方法，即先将线性方程组化为等价的三角形方程组，然后求解。基本方法，即先将线性方程组化为等价的三角形方程组，然后求解。本讲稿第五页，共五十三页1Gauss消元法GaussGauss消元法是最基本的一种方法，下例说明其消元法是最基本的一种方法，下例说明其消元法是最基本的一种方法，下例说明其消元法是最基本的一种方法，下例说明其基本思想基本思想基本思想基本思想:例例1解线性方程组：

10、解线性方程组：解线性方程组：解线性方程组：解：消去解：消去x1，进行第一次消元：首先找乘数，以，进行第一次消元：首先找乘数，以-12乘第一个方程加到第二个方程，以乘第一个方程加到第二个方程，以18乘第一个方程乘第一个方程加到第三个方程上可得同解方程组：加到第三个方程上可得同解方程组：本讲稿第六页，共五十三页例1（续）上述上述上述上述GaussGauss消元法的基本思想是：先逐次消去变量，将方程组化消元法的基本思想是：先逐次消去变量，将方程组化消元法的基本思想是：先逐次消去变量，将方程组化消元法的基本思想是：先逐次消去变量，将方程组化成同解的上三角形方程组，此过程称为消元过成同解的上三角形方程组

11、，此过程称为消元过成同解的上三角形方程组，此过程称为消元过成同解的上三角形方程组，此过程称为消元过程。然后按方程相反顺序求解上三角形方程组，得到原程。然后按方程相反顺序求解上三角形方程组，得到原程。然后按方程相反顺序求解上三角形方程组，得到原程。然后按方程相反顺序求解上三角形方程组，得到原方程组的解，此过程称为回代过程。方程组的解，此过程称为回代过程。方程组的解，此过程称为回代过程。方程组的解，此过程称为回代过程。再消一次元得：再消一次元得：二次消元后将方程化为二次消元后将方程化为二次消元后将方程化为二次消元后将方程化为倒三角形式，然后进行倒三角形式，然后进行倒三角形式，然后进行倒三角形式，然

12、后进行回代容易解出：回代容易解出：回代容易解出：回代容易解出：x3=3,x2=2,x1=1。我们的目的，是要总结归纳出一般情况下的我们的目的，是要总结归纳出一般情况下的我们的目的，是要总结归纳出一般情况下的我们的目的，是要总结归纳出一般情况下的n n阶线性方程阶线性方程阶线性方程阶线性方程组的消元公式和回代求解公式，从而得到求解组的消元公式和回代求解公式，从而得到求解组的消元公式和回代求解公式，从而得到求解组的消元公式和回代求解公式，从而得到求解n n阶线性方阶线性方阶线性方阶线性方程组的能顺利在计算机上实现的行之有效的算法。程组的能顺利在计算机上实现的行之有效的算法。程组的能顺利在计算机上实

13、现的行之有效的算法。程组的能顺利在计算机上实现的行之有效的算法。本讲稿第七页，共五十三页 为能更清楚地得到算法，下面以为能更清楚地得到算法，下面以为能更清楚地得到算法，下面以为能更清楚地得到算法，下面以4 4阶线性方程组为例总结求解步阶线性方程组为例总结求解步阶线性方程组为例总结求解步阶线性方程组为例总结求解步骤，并且很容易地可推广至一般的骤，并且很容易地可推广至一般的骤，并且很容易地可推广至一般的骤，并且很容易地可推广至一般的n n阶线性方程组。阶线性方程组。阶线性方程组。阶线性方程组。本讲稿第八页，共五十三页 可以检查，分别以可以检查，分别以可以检查，分别以可以检查，分别以 l li i1

14、 1乘第一个方程加到第乘第一个方程加到第乘第一个方程加到第乘第一个方程加到第i i个方程上可以完个方程上可以完个方程上可以完个方程上可以完成第一次消元，得同解方程组：成第一次消元，得同解方程组：成第一次消元，得同解方程组：成第一次消元，得同解方程组：变化以后的方程变化以后的方程变化以后的方程变化以后的方程组系数及右边的组系数及右边的组系数及右边的组系数及右边的常数项可总结出常数项可总结出常数项可总结出常数项可总结出如下的计算公式：如下的计算公式：如下的计算公式：如下的计算公式：完成第一次消元之后的完成第一次消元之后的方程组记为：方程组记为：A(2)x=b(2)本讲稿第九页，共五十三页Gauss

15、消元法的基本步骤3（4阶）以方程组中第以方程组中第以方程组中第以方程组中第i i个方程减去第二个方程乘个方程减去第二个方程乘个方程减去第二个方程乘个方程减去第二个方程乘l li i2 2(i i=3,4)=3,4)，完，完，完，完成第二次消元。成第二次消元。成第二次消元。成第二次消元。上标为上标为上标为上标为3 3的系数的系数的系数的系数和右端项可由和右端项可由和右端项可由和右端项可由下面公式计算：下面公式计算：下面公式计算：下面公式计算：本讲稿第十页，共五十三页第三步第三步第三步第三步：消元（：消元（：消元（：消元（4 4阶方程组需进行阶方程组需进行阶方程组需进行阶方程组需进行3 3次消元）

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

17、代求解过程很容易推广到一般的很容易推广到一般的很容易推广到一般的很容易推广到一般的n n阶线阶线阶线阶线性方程组。性方程组。性方程组。性方程组。经过上述消元步骤，经过上述消元步骤，经过上述消元步骤，经过上述消元步骤，得到同解的上三角形方得到同解的上三角形方得到同解的上三角形方得到同解的上三角形方程组：程组：程组：程组：A(4)x=b(4)本讲稿第十一页，共五十三页Gauss消元法的消元过程1、2（n阶）一般地，设一般地，设一般地，设一般地，设 n n阶方程组：阶方程组：阶方程组：阶方程组：消元过程为：消元过程为：消元过程为：消元过程为：将上方程组中第将上方程组中第i个方程减去第个方程减去第2个

18、方程乘以个方程乘以li2(i=3,n)，完成，完成第二步消元。第二步消元。本讲稿第十二页，共五十三页第第k 步：设第步：设第k 1步消元后得原方程组的同解方程组为：步消元后得原方程组的同解方程组为：第第第第k k步消元后同步消元后同步消元后同步消元后同解方程组中上标解方程组中上标解方程组中上标解方程组中上标为为为为k k+1+1的元素的的元素的的元素的的元素的计算公式见下屏计算公式见下屏计算公式见下屏计算公式见下屏本讲稿第十三页，共五十三页照此消元下去，完成照此消元下去，完成n 1次次消元后，可将原方程组化成消元后，可将原方程组化成同解的上三角形方程组如下：同解的上三角形方程组如下：本讲稿第十

19、四页，共五十三页Gauss消元法的回代过程（n阶）回代过程回代过程：逐步回代求得原方程组的解逐步回代求得原方程组的解 本讲稿第十五页，共五十三页Gauss消元法的计算量 由于在计算机中作乘除运算量所需时间远大于作加减运算所需由于在计算机中作乘除运算量所需时间远大于作加减运算所需由于在计算机中作乘除运算量所需时间远大于作加减运算所需由于在计算机中作乘除运算量所需时间远大于作加减运算所需时间，故只考虑作乘除运算量。时间，故只考虑作乘除运算量。时间，故只考虑作乘除运算量。时间，故只考虑作乘除运算量。由消元法步骤知，第由消元法步骤知，第由消元法步骤知，第由消元法步骤知，第k k次消元需作次消元需作次消

20、元需作次消元需作n n k k次除法，作次除法，作次除法，作次除法，作(n n k k)()(n n k k+1)+1)次乘法，故消元过程中乘除法运算量为：次乘法，故消元过程中乘除法运算量为：次乘法，故消元过程中乘除法运算量为：次乘法，故消元过程中乘除法运算量为：所以所以所以所以GaussGauss 消去法的消去法的消去法的消去法的乘除法总运算量为：乘除法总运算量为：乘除法总运算量为：乘除法总运算量为：本讲稿第十六页，共五十三页Gauss法与Cramer法则的计算量比较 Gauss Gauss 消元法的乘消元法的乘消元法的乘消元法的乘除法总运算量为除法总运算量为除法总运算量为除法总运算量为：与

21、我们曾经介绍的与我们曾经介绍的与我们曾经介绍的与我们曾经介绍的CramerCramer法则的乘除法总运算量法则的乘除法总运算量法则的乘除法总运算量法则的乘除法总运算量 (n n2 2 1)1)n n!+!+n n 相比，由下表可知：当阶数越高时，相比，由下表可知：当阶数越高时，相比，由下表可知：当阶数越高时，相比，由下表可知：当阶数越高时，GaussGauss消消消消元法所需乘除法次数比元法所需乘除法次数比元法所需乘除法次数比元法所需乘除法次数比CramerCramer法则要少得多：法则要少得多：法则要少得多：法则要少得多：方程组阶数方程组阶数方程组阶数方程组阶数3 3101020205050

22、GaussGauss消元法运算量消元法运算量消元法运算量消元法运算量1717430430306030604415044150CramerCramer法则运算量法则运算量法则运算量法则运算量51513592512103592512109.7109.71020207.6107.6106767Gauss Gauss 消元法的优缺点：消元法的优缺点：消元法的优缺点：消元法的优缺点：但其计算过程中，要求但其计算过程中，要求但其计算过程中，要求但其计算过程中，要求a akkkk(k k)（称为主元素）均不为零，因（称为主元素）均不为零，因（称为主元素）均不为零，因（称为主元素）均不为零，因而适用范围小，只

23、适用于从而适用范围小，只适用于从而适用范围小，只适用于从而适用范围小，只适用于从1 1到到到到n n 1 1阶顺序主子式均不为零的阶顺序主子式均不为零的阶顺序主子式均不为零的阶顺序主子式均不为零的矩阵矩阵矩阵矩阵A A，计算实践还表明，计算实践还表明，计算实践还表明，计算实践还表明，GaussGauss消元法的数值稳定性差，当出消元法的数值稳定性差，当出消元法的数值稳定性差，当出消元法的数值稳定性差，当出现小主元素时，会严重影响计算结果的精度，甚至导出错误的结果。现小主元素时，会严重影响计算结果的精度，甚至导出错误的结果。现小主元素时，会严重影响计算结果的精度，甚至导出错误的结果。现小主元素时

24、，会严重影响计算结果的精度，甚至导出错误的结果。GaussGauss消元法简单易行。消元法简单易行。消元法简单易行。消元法简单易行。本讲稿第十七页，共五十三页2主元素法 2.1 引入主元素的必要性引入主元素的必要性 对线性方程组对线性方程组AX=b，若其系数行列式，若其系数行列式 det(A)0，则该方程组有唯一，则该方程组有唯一 解，但是这一条件解，但是这一条件 不能保证所有主元素都不等于零，只要某一主元不能保证所有主元素都不等于零，只要某一主元素等于零，就不能用素等于零，就不能用Gauss消元法求解该方程组，消元法求解该方程组，即使所有主元素不等于零，但即使所有主元素不等于零，但 某一主元

25、素的绝对某一主元素的绝对值很小时，值很小时，Gauss消元法也是不适用的。如下例：消元法也是不适用的。如下例：例例2本讲稿第十八页，共五十三页例2（续1）解：为减小误差，计算过程中保留解：为减小误差，计算过程中保留3位有效数字。位有效数字。按按Gauss消元法步骤：消元法步骤：第一次消元后得同解方程组：第一次消元后得同解方程组：第一次消元后得同解方程组：第一次消元后得同解方程组：第二次消元后得同解方程组第二次消元后得同解方程组第二次消元后得同解方程组第二次消元后得同解方程组 回代得解，回代得解，x3=2.02，x2=2.40，x1=5.80。容易验证，方程组（容易验证，方程组（3-8）的准确解

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

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

28、2的第二种解法的第二种解法,通过交换方程次序，选取绝对值大的元素作主元通过交换方程次序，选取绝对值大的元素作主元 基于这种思想而导出主元素法。基于这种思想而导出主元素法。本讲稿第二十一页，共五十三页2.2列主元素法 为简便起见，对方为简便起见，对方 程组（程组（2-1），用），用 其增其增 广矩阵：广矩阵：表示，并直接在增广表示，并直接在增广矩阵上进行运算。矩阵上进行运算。列主元素法的具体步骤如下：列主元素法的具体步骤如下：本讲稿第二十二页，共五十三页列主元素法如此经过如此经过如此经过如此经过n n 1 1步，增广矩阵（步，增广矩阵（步，增广矩阵（步，增广矩阵（2-92-9）被化成上三角形，然

29、后由）被化成上三角形，然后由）被化成上三角形，然后由）被化成上三角形，然后由回代过程求解。回代过程求解。回代过程求解。回代过程求解。在上述过程中，主元是按列选取的，故称为在上述过程中，主元是按列选取的，故称为在上述过程中，主元是按列选取的，故称为在上述过程中，主元是按列选取的，故称为列主元法列主元法列主元法列主元法。例。例。例。例2 2中的第二种解法就是按列主元法进行的。中的第二种解法就是按列主元法进行的。中的第二种解法就是按列主元法进行的。中的第二种解法就是按列主元法进行的。本讲稿第二十三页，共五十三页2.3全主元素法经过经过n k次消元后，得到与方程组（次消元后，得到与方程组（2-1）同解

30、的上三角）同解的上三角形方程组，再由回代过程求解。形方程组，再由回代过程求解。本讲稿第二十四页，共五十三页例例6计算过程保留三位小数。此例的计算结果表明，全主元素法的精度优于列此例的计算结果表明，全主元素法的精度优于列主元法，这是由于全主元法是在全体元素中选主元，主元法，这是由于全主元法是在全体元素中选主元，故它对控制舍入误差十分有效。但是全主元法在计算故它对控制舍入误差十分有效。但是全主元法在计算过程中，需同时作行与列的互换，因而程序比较复杂过程中，需同时作行与列的互换，因而程序比较复杂,计算时间较长。列主元法的精度虽稍低于全主元法，计算时间较长。列主元法的精度虽稍低于全主元法，但其计算简单

31、，工作量大为减少，且计算经验与理论但其计算简单，工作量大为减少，且计算经验与理论分析均表明，它与全主元法同样具有良好的数值稳定分析均表明，它与全主元法同样具有良好的数值稳定性，故列主元法是求解中小型稠密线性方程组的最好性，故列主元法是求解中小型稠密线性方程组的最好方法之一。方法之一。方法之一。方法之一。本讲稿第二十五页，共五十三页2.4解三对角方程组的追赶法在很多问题中，需要解如下形式的三对角方程组：在很多问题中，需要解如下形式的三对角方程组：在很多问题中，需要解如下形式的三对角方程组：在很多问题中，需要解如下形式的三对角方程组：三对角方程组的系数矩阵为三对角阵，对于这种特殊而又简三对角方程组

32、的系数矩阵为三对角阵，对于这种特殊而又简三对角方程组的系数矩阵为三对角阵，对于这种特殊而又简三对角方程组的系数矩阵为三对角阵，对于这种特殊而又简单的方程组，用前面介绍的方法求解由于有大量的零元素既占单的方程组，用前面介绍的方法求解由于有大量的零元素既占单的方程组，用前面介绍的方法求解由于有大量的零元素既占单的方程组，用前面介绍的方法求解由于有大量的零元素既占内存又浪费计算时间，显然很不经济。充分注意到三对角方程内存又浪费计算时间，显然很不经济。充分注意到三对角方程内存又浪费计算时间，显然很不经济。充分注意到三对角方程内存又浪费计算时间，显然很不经济。充分注意到三对角方程组的特点，根据顺序消元的

33、思想导出一个简便的算法组的特点，根据顺序消元的思想导出一个简便的算法组的特点，根据顺序消元的思想导出一个简便的算法组的特点，根据顺序消元的思想导出一个简便的算法追赶追赶追赶追赶法。法。法。法。本讲稿第二十六页，共五十三页 首先进行顺序消元，首先进行顺序消元，首先进行顺序消元，首先进行顺序消元，且每步将主元系数且每步将主元系数且每步将主元系数且每步将主元系数化为化为化为化为1 1，将方程组化为：，将方程组化为：，将方程组化为：，将方程组化为：其中系数按下式计算其中系数按下式计算其中系数按下式计算其中系数按下式计算 ：然后回代然后回代然后回代然后回代求解，得：求解，得：求解，得：求解，得：上述追赶

34、法能进行到底上述追赶法能进行到底上述追赶法能进行到底上述追赶法能进行到底 。本讲稿第二十七页，共五十三页追赶法举例用追赶法解下用追赶法解下用追赶法解下用追赶法解下列三对角方程组：列三对角方程组：列三对角方程组：列三对角方程组：例例4解：解：解：解：首先将方程组化为（先追）：首先将方程组化为（先追）：首先将方程组化为（先追）：首先将方程组化为（先追）：然后回代（赶）求解：然后回代（赶）求解：x5=0，x4=30/7，x3=6/7，x2=12/7，x1=0 可以看出，追赶法本质上还可以看出，追赶法本质上还可以看出，追赶法本质上还可以看出，追赶法本质上还是顺序消元法，但由于计算过程是顺序消元法，但由

35、于计算过程是顺序消元法，但由于计算过程是顺序消元法，但由于计算过程中只涉及系数矩阵的非零元，因此大大节约了计算机内存与计算量，中只涉及系数矩阵的非零元，因此大大节约了计算机内存与计算量，中只涉及系数矩阵的非零元，因此大大节约了计算机内存与计算量，中只涉及系数矩阵的非零元，因此大大节约了计算机内存与计算量，按乘除法次数进行比较，按乘除法次数进行比较，按乘除法次数进行比较，按乘除法次数进行比较，GaussGauss消元法约为消元法约为消元法约为消元法约为n n3 3/3/3，全主元法为，全主元法为，全主元法为，全主元法为n n3 3/2/2，而追赶法仅为，而追赶法仅为，而追赶法仅为，而追赶法仅为5

36、 5n n-3-3次，可见追赶法是求解三对角方程组的次，可见追赶法是求解三对角方程组的次，可见追赶法是求解三对角方程组的次，可见追赶法是求解三对角方程组的非常好的方法。非常好的方法。非常好的方法。非常好的方法。本讲稿第二十八页，共五十三页3矩阵分解法 如果用矩阵形式表示，如果用矩阵形式表示，如果用矩阵形式表示，如果用矩阵形式表示，GaussGauss消元法的消元过程是对方程组消元法的消元过程是对方程组消元法的消元过程是对方程组消元法的消元过程是对方程组（2-12-1）的增广矩阵（）的增广矩阵（）的增广矩阵（）的增广矩阵（A A、b b）进行一系列的初等行变换，将系）进行一系列的初等行变换，将系

37、）进行一系列的初等行变换，将系）进行一系列的初等行变换，将系数矩阵数矩阵数矩阵数矩阵A A化成上三角矩阵的过程，也等价于用一串初等变换阵去左化成上三角矩阵的过程，也等价于用一串初等变换阵去左化成上三角矩阵的过程，也等价于用一串初等变换阵去左化成上三角矩阵的过程，也等价于用一串初等变换阵去左乘增广矩阵，因此，消元过程可以通过矩阵运算来实现。乘增广矩阵，因此，消元过程可以通过矩阵运算来实现。乘增广矩阵，因此，消元过程可以通过矩阵运算来实现。乘增广矩阵，因此，消元过程可以通过矩阵运算来实现。紧接下屏：紧接下屏：紧接下屏：紧接下屏：3.1 GaussGauss消元法的矩阵形式消元法的矩阵形式消元法的矩

38、阵形式消元法的矩阵形式 事实上，事实上，事实上，事实上，GaussGauss消元法的消元法的消元法的消元法的 第一次消元第一次消元第一次消元第一次消元相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵：本讲稿第二十九页，共五十三页第二次消元第二次消元第二次消元第二次消元相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵：第第第第k k次消元次消元次消元次消元相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵：Gauss消元法的矩阵形式本讲稿第三十页，共五十三页经过经过经过经过n n 1 1步消元后得到：步消元后得到：步消元后得到：步消

39、元后得到：因为因为因为因为L Lk k(k k=1,2,=1,2,n n 1)1)均为非奇异阵，故它们均为非奇异阵，故它们均为非奇异阵，故它们均为非奇异阵，故它们的逆矩阵存在。容易求出：的逆矩阵存在。容易求出：的逆矩阵存在。容易求出：的逆矩阵存在。容易求出：这说明：在这说明：在 的条件下，消元过程的条件下，消元过程实际上是把系数矩阵实际上是把系数矩阵A分解成单位下三角阵与上三角矩阵分解成单位下三角阵与上三角矩阵的乘积的过程。的乘积的过程。Gauss消元法的矩阵形式（续）本讲稿第三十一页，共五十三页杜利特尔（Doolittle）分解LU分解 事实上，只要事实上，只要事实上，只要事实上，只要A A

40、满足一定条件，由上述结论，它一定可以分满足一定条件，由上述结论，它一定可以分满足一定条件，由上述结论，它一定可以分满足一定条件，由上述结论，它一定可以分解成两个三角形矩阵的乘积，即：解成两个三角形矩阵的乘积，即：解成两个三角形矩阵的乘积，即：解成两个三角形矩阵的乘积，即：A=LU A=LU 。上述分解称为杜利特尔（上述分解称为杜利特尔（上述分解称为杜利特尔（上述分解称为杜利特尔（DoolittleDoolittle）分解，也称为）分解，也称为）分解，也称为）分解，也称为LULU分解，当分解，当分解，当分解，当系数矩阵完成三角分解后，对于求解方程组：系数矩阵完成三角分解后，对于求解方程组：系数矩

41、阵完成三角分解后，对于求解方程组：系数矩阵完成三角分解后，对于求解方程组：AxAx=b b。消元过程相当于分解消元过程相当于分解消元过程相当于分解消元过程相当于分解A A=LULU及求解三角形方程组及求解三角形方程组及求解三角形方程组及求解三角形方程组LyLy=b b，回，回，回，回代过程则是求解另一个三角形方程组代过程则是求解另一个三角形方程组代过程则是求解另一个三角形方程组代过程则是求解另一个三角形方程组UxUx=y y，因此，解线性方，因此，解线性方，因此，解线性方，因此，解线性方程组问题可转化为矩阵的三角分解问题。程组问题可转化为矩阵的三角分解问题。程组问题可转化为矩阵的三角分解问题。

42、程组问题可转化为矩阵的三角分解问题。其中：其中：其中：其中：L L为单位下三角矩阵，为单位下三角矩阵，为单位下三角矩阵，为单位下三角矩阵，U U为上三角矩阵：为上三角矩阵：为上三角矩阵：为上三角矩阵：本讲稿第三十二页，共五十三页3.2矩阵的三角分解 正如正如正如正如GaussGauss消元法要在一定条件下才能进行到底一样，矩阵消元法要在一定条件下才能进行到底一样，矩阵消元法要在一定条件下才能进行到底一样，矩阵消元法要在一定条件下才能进行到底一样，矩阵A A也必须满足一定条件才能进行三角分解。也必须满足一定条件才能进行三角分解。也必须满足一定条件才能进行三角分解。也必须满足一定条件才能进行三角分

43、解。设设设设A A为为为为n n阶方阵，若阶方阵，若阶方阵，若阶方阵，若A A的顺序主子式的顺序主子式的顺序主子式的顺序主子式A Ai i(i i=1,2,=1,2,n n)均不为零均不为零均不为零均不为零,则矩阵则矩阵则矩阵则矩阵A A存在唯一的存在唯一的存在唯一的存在唯一的DoolittleDoolittle分分分分解。解。解。解。定理定理2.1下面讨论如何对下面讨论如何对下面讨论如何对下面讨论如何对A A进行进行进行进行LULU分解分解分解分解：（1 1行行行行1 1列列列列）由于两个矩阵相等就是它们的对应元素都相等，因此通过由于两个矩阵相等就是它们的对应元素都相等，因此通过由于两个矩阵

44、相等就是它们的对应元素都相等，因此通过由于两个矩阵相等就是它们的对应元素都相等，因此通过比较比较比较比较A A与与与与LULU的对应元素，即可得到直接计算的对应元素，即可得到直接计算的对应元素，即可得到直接计算的对应元素，即可得到直接计算L L、U U的元素的公式：的元素的公式：的元素的公式：的元素的公式：A A=LU LU 即：即：即：即：紧接下屏：紧接下屏：紧接下屏：紧接下屏：本讲稿第三十三页，共五十三页对A进行LU分解ALU由矩阵乘法规则及比较（由矩阵乘法规则及比较（由矩阵乘法规则及比较（由矩阵乘法规则及比较（2-112-11）两端的元素，得：）两端的元素，得：）两端的元素，得：）两端的

45、元素，得：即可由（即可由（即可由（即可由（2-122-12）求出）求出）求出）求出U U的第一行，的第一行，的第一行，的第一行，L L的第一列。的第一列。的第一列。的第一列。下面讨论一般情况，即：下面讨论一般情况，即：下面讨论一般情况，即：下面讨论一般情况，即：U U的第的第的第的第i i 行，行，行，行，L L的第的第的第的第j j列：列：列：列：本讲稿第三十四页，共五十三页一般情况下，可由：一般情况下，可由：一般情况下，可由：一般情况下，可由：对A进行LU分解（r 行r 列）计算过程应按计算过程应按计算过程应按计算过程应按U U第第第第1 1行、行、行、行、L L第第第第1 1列列列列（第

46、（第（第（第1 1框），框），框），框），U U第第第第2 2行、行、行、行、L L第第第第2 2列（第列（第列（第列（第2 2框），框），框），框），的顺序的顺序的顺序的顺序 具体分解步具体分解步具体分解步具体分解步骤见下屏：骤见下屏：骤见下屏：骤见下屏：得到计算得到计算得到计算得到计算u uij ij和和和和 l lij ij 的公式：的公式：的公式：的公式：本讲稿第三十五页，共五十三页对A进行LU分解的具体步骤1.计算计算U的第的第1行，行，L的第的第1列，亦称为计算列，亦称为计算 第第1框；框；2.计算计算U的第的第r 行，行，L的第的第r 列（列（r=2,n），），即第即第r 框框：

47、本讲稿第三十六页，共五十三页矩阵A的LU分解举例解：按分解公式（解：按分解公式（解：按分解公式（解：按分解公式（2-132-13），），），），一框一框分解，每框计算时先行后列一框一框分解，每框计算时先行后列一框一框分解，每框计算时先行后列一框一框分解，每框计算时先行后列 ：所以：所以：所以：所以：例例例例5 5 本讲稿第三十七页，共五十三页3.3直接三角分解法 若线性方程组若线性方程组若线性方程组若线性方程组Ax Ax=b b的系数矩阵的系数矩阵的系数矩阵的系数矩阵A A完成三角分解，完成三角分解，完成三角分解，完成三角分解，A A=LULU，那么解方，那么解方，那么解方，那么解方程组程组程

48、组程组Ax Ax=b b等价于求解两个三角形方等价于求解两个三角形方等价于求解两个三角形方等价于求解两个三角形方程组程组程组程组Ly Ly=b b，UxUx=y y，即由：，即由：，即由：，即由：再由：再由：再由：再由：可解得：可解得：可解得：可解得：本讲稿第三十八页，共五十三页直接三角分解法（续）容易看出，式（容易看出，式（容易看出，式（容易看出，式（2-142-14）与式（）与式（）与式（）与式（2-132-13）的运算规律相同，）的运算规律相同，）的运算规律相同，）的运算规律相同，或者由：或者由：或者由：或者由：本讲稿第三十九页，共五十三页解线性方程组举例例例6解解：按表：按表：按表：按

49、表2-32-3计算：计算：计算：计算：本讲稿第四十页，共五十三页本讲稿第四十一页，共五十三页三角分解法的几点说明1 1、用三角分解法求线性方程的乘除法运算量也是、用三角分解法求线性方程的乘除法运算量也是、用三角分解法求线性方程的乘除法运算量也是、用三角分解法求线性方程的乘除法运算量也是n n3 3/3/3 数量级。由于在求出数量级。由于在求出数量级。由于在求出数量级。由于在求出u uij ij,l lij ij和和和和y yi i后，后，后，后，a aij ij和和和和b bi i无需保留，无需保留，无需保留，无需保留，故上机计算时，可把故上机计算时，可把故上机计算时，可把故上机计算时，可把L

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