第三章线性方程组直接解法精选PPT.ppt

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

1、第三章线性方程组直接解法第1页，本讲稿共53页第三章目录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.方程组的性态和条件数方程组的性态和条件数第2页，本讲稿共53页 设设设设n n阶线性方程组：阶线性方程组：阶线性方程组：阶线性方程组：其矩阵形式为：其矩阵形式为：其矩阵形式为：其矩阵形式为：Ax=b (2-2)其中：其中：其中：其中：在科学研究和工程技术中所提出的计算问题中，线性在科

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

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

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

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

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

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

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

10、，下例说明其消元法是最基本的一种方法，下例说明其基本思想基本思想基本思想基本思想:例例1解线性方程组：解线性方程组：解线性方程组：解线性方程组：解：消去解：消去x1 1，进行第一次消元：首先找乘数，以，进行第一次消元：首先找乘数，以-12乘第一个方程加到第二个方程，以乘第一个方程加到第二个方程，以18乘第一个方程乘第一个方程加到第三个方程上可得同解方程组：加到第三个方程上可得同解方程组：第6页，本讲稿共53页例1（续）上述上述上述上述GaussGauss消元法的基本思想是：先逐次消去变量，将消元法的基本思想是：先逐次消去变量，将消元法的基本思想是：先逐次消去变量，将消元法的基本思想是：先逐次消

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

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

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

14、。第8页，本讲稿共53页 可以检查，分别以可以检查，分别以可以检查，分别以可以检查，分别以 l li i1 1乘第一个方程加到第乘第一个方程加到第乘第一个方程加到第乘第一个方程加到第i i个方程上个方程上个方程上个方程上可以完成第一次消元，得同解方程组：可以完成第一次消元，得同解方程组：可以完成第一次消元，得同解方程组：可以完成第一次消元，得同解方程组：变化以后的方变化以后的方变化以后的方变化以后的方程组系数及右程组系数及右程组系数及右程组系数及右边的常数项可边的常数项可边的常数项可边的常数项可总结出如下的总结出如下的总结出如下的总结出如下的计算公式：计算公式：计算公式：计算公式：完成第一次消

15、元之后的完成第一次消元之后的完成第一次消元之后的完成第一次消元之后的方程组记为：方程组记为：方程组记为：方程组记为：A(2)x=b(2)第9页，本讲稿共53页Gauss消元法的基本步骤3（4阶）以方程组中第以方程组中第以方程组中第以方程组中第i i个方程减去第二个方程乘个方程减去第二个方程乘个方程减去第二个方程乘个方程减去第二个方程乘l li i2 2(i i=3,4)=3,4)，完，完，完，完成第二次消元。成第二次消元。成第二次消元。成第二次消元。上标为上标为上标为上标为3 3的系数的系数的系数的系数和右端项可由和右端项可由和右端项可由和右端项可由下面公式计算：下面公式计算：下面公式计算：下

16、面公式计算：第10页，本讲稿共53页第三步第三步第三步第三步：消元（：消元（：消元（：消元（4 4阶方程组需进行阶方程组需进行阶方程组需进行阶方程组需进行3 3次消元）次消元）次消元）次消元）将上述将上述将上述将上述 A A (3)(3)X X=b b(3)(3)中最后一个方程中的中最后一个方程中的中最后一个方程中的中最后一个方程中的x x3 3消为零消为零消为零消为零：然后可回代求解：由于然后可回代求解：由于然后可回代求解：由于然后可回代求解：由于A A(4)(4)为上三角形，所以可为上三角形，所以可为上三角形，所以可为上三角形，所以可按变量的逆序逐步回代求按变量的逆序逐步回代求按变量的逆序

17、逐步回代求按变量的逆序逐步回代求原方程组的解：原方程组的解：原方程组的解：原方程组的解：上述上述上述上述 消元、回代求解过程消元、回代求解过程消元、回代求解过程消元、回代求解过程很容易推广到一般的很容易推广到一般的很容易推广到一般的很容易推广到一般的n n阶线阶线阶线阶线性方程组。性方程组。性方程组。性方程组。经过上述消元步骤，经过上述消元步骤，经过上述消元步骤，经过上述消元步骤，得到同解的上三角形得到同解的上三角形得到同解的上三角形得到同解的上三角形方程组：方程组：方程组：方程组：A(4)(4)x x=b(4)第11页，本讲稿共53页Gauss消元法的消元过程1、2（n阶）一般地，设一般地，

18、设一般地，设一般地，设 n n阶方程组：阶方程组：阶方程组：阶方程组：消元过程为：消元过程为：消元过程为：消元过程为：将上方程组中第将上方程组中第将上方程组中第将上方程组中第i i个方程减去第个方程减去第个方程减去第个方程减去第2 2个方程乘以个方程乘以个方程乘以个方程乘以l li i2 2(i i=3,=3,n n)，完成，完成，完成，完成第二步消元。第二步消元。第二步消元。第二步消元。第12页，本讲稿共53页第第第第k k 步：设第步：设第步：设第步：设第k k 1 1步消元后得原方程组的同解方程组为：步消元后得原方程组的同解方程组为：步消元后得原方程组的同解方程组为：步消元后得原方程组的

19、同解方程组为：第第第第k k步消元后同步消元后同步消元后同步消元后同解方程组中上标解方程组中上标解方程组中上标解方程组中上标为为为为k k+1+1的元素的的元素的的元素的的元素的计算公式见下屏计算公式见下屏计算公式见下屏计算公式见下屏第13页，本讲稿共53页照此消元下去，完成照此消元下去，完成照此消元下去，完成照此消元下去，完成n 1次次消元后，可将原方程组化成消元后，可将原方程组化成消元后，可将原方程组化成消元后，可将原方程组化成同解的上三角形方程组如下：同解的上三角形方程组如下：同解的上三角形方程组如下：同解的上三角形方程组如下：第14页，本讲稿共53页Gauss消元法的回代过程（n阶）回

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

21、法，作次除法，作(n n k k)()(n n k k+1)+1)次乘法，故消元过程中乘除法运算量为：次乘法，故消元过程中乘除法运算量为：次乘法，故消元过程中乘除法运算量为：次乘法，故消元过程中乘除法运算量为：所以所以所以所以GaussGauss 消去法的消去法的消去法的消去法的乘除法总运算量为：乘除法总运算量为：乘除法总运算量为：乘除法总运算量为：第16页，本讲稿共53页Gauss法与Cramer法则的计算量比较 Gauss Gauss 消元法的乘消元法的乘消元法的乘消元法的乘除法总运算量为除法总运算量为除法总运算量为除法总运算量为：与我们曾经介绍的与我们曾经介绍的与我们曾经介绍的与我们曾经

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

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

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

25、sGauss消元法简单易行。消元法简单易行。消元法简单易行。消元法简单易行。第17页，本讲稿共53页2主元素法 2.1 引入主元素的必要性引入主元素的必要性 对线性方程组对线性方程组AX=b b，若其系数行列式，若其系数行列式 det(A)0，则该方程组有唯一，则该方程组有唯一 解，但是这一条件解，但是这一条件 不能保证所有主元素都不等于零，只要某一主元不能保证所有主元素都不等于零，只要某一主元素等于零，就不能用素等于零，就不能用Gauss消元法求解该方程组，消元法求解该方程组，消元法求解该方程组，消元法求解该方程组，即使所有主元素不等于零，但即使所有主元素不等于零，但 某一主元素的绝对某一主

26、元素的绝对值很小时，值很小时，Gauss消元法也是不适用的。如下例：消元法也是不适用的。如下例：消元法也是不适用的。如下例：消元法也是不适用的。如下例：例例2第18页，本讲稿共53页例2（续1）解：为减小误差，计算过程中保留解：为减小误差，计算过程中保留3位有效数字。位有效数字。按按Gauss消元法步骤：消元法步骤：第一次消元后得同解方程组：第一次消元后得同解方程组：第一次消元后得同解方程组：第一次消元后得同解方程组：第二次消元后得同解方程组第二次消元后得同解方程组第二次消元后得同解方程组第二次消元后得同解方程组 回代得解，回代得解，x3 3=2.02，x2=2.40，x x1 1=5.805

27、.80。容易验证，方程组（容易验证，方程组（3-8）的准确解为：）的准确解为：x1 1=2.60，x2=1.00，x3=2.0。显然两种结果相差很大。显然两种结果相差很大。显然两种结果相差很大。显然两种结果相差很大。第19页，本讲稿共53页 若在解方程组前，先交换方程的次序，若在解方程组前，先交换方程的次序，如将（如将（2-8）交换一行与三行改写成如下所示：）交换一行与三行改写成如下所示：再用再用再用再用GaussGauss消元法，顺序消元后得同解方程组：消元法，顺序消元后得同解方程组：回代得解：回代得解：x x3 3=2.00，x2 2=1.00，x1 1=2.60 2.60 与准确解相同。

28、与准确解相同。例2（续2）第20页，本讲稿共53页例2两种解法的误差分析 在例在例2中，对中，对(2-8)的方程进行顺序消元时，的方程进行顺序消元时，主元主元a a(1)11=0.50，a(2)22=0.100都比较小，以它们作都比较小，以它们作 除数就增长了舍入误差除数就增长了舍入误差,而导致计算结果不准确。而导致计算结果不准确。产生上述现象的原因在于舍入误差，当产生上述现象的原因在于舍入误差，当|a(k)kk|很小时，进行第很小时，进行第很小时，进行第很小时，进行第k次消元，要用次消元，要用|a(k k)kk|作除数，这作除数，这 样就可能增大舍入误差造成溢出停机，或者导致样就可能增大舍入

29、误差造成溢出停机，或者导致 错误的结果。错误的结果。为了在计算过程中，抑制舍入误差的增长，为了在计算过程中，抑制舍入误差的增长，应尽量避免小主元的出现。如例应尽量避免小主元的出现。如例2的第二种解法的第二种解法,通过交换方程次序，选取绝对值大的元素作主元通过交换方程次序，选取绝对值大的元素作主元 基于这种思想而导出主元素法。基于这种思想而导出主元素法。第21页，本讲稿共53页2.2列主元素法 为简便起见，对方为简便起见，对方 程组（程组（2-1），用），用 其增其增 广矩阵：广矩阵：表示，并直接在增广表示，并直接在增广表示，并直接在增广表示，并直接在增广矩阵上进行运算。矩阵上进行运算。矩阵上进

30、行运算。矩阵上进行运算。列主元素法的具体步骤如下：列主元素法的具体步骤如下：第22页，本讲稿共53页列主元素法如此经过如此经过如此经过如此经过n n 1 1步，增广矩阵（步，增广矩阵（步，增广矩阵（步，增广矩阵（2-92-9）被化成上三角形，然）被化成上三角形，然）被化成上三角形，然）被化成上三角形，然后由回代过程求解。后由回代过程求解。后由回代过程求解。后由回代过程求解。在上述过程中，主元是按列选取的，故称为在上述过程中，主元是按列选取的，故称为在上述过程中，主元是按列选取的，故称为在上述过程中，主元是按列选取的，故称为列主元法列主元法列主元法列主元法。例例例例2 2中的第二种解法就是按列主

31、元法进行的。中的第二种解法就是按列主元法进行的。中的第二种解法就是按列主元法进行的。中的第二种解法就是按列主元法进行的。第23页，本讲稿共53页2.3全主元素法经过经过n k k次消元后，得到与方程组（次消元后，得到与方程组（次消元后，得到与方程组（次消元后，得到与方程组（2-12-1）同解的上三角）同解的上三角）同解的上三角）同解的上三角形方程组，再由回代过程求解。形方程组，再由回代过程求解。形方程组，再由回代过程求解。形方程组，再由回代过程求解。第24页，本讲稿共53页例例例例6 6计算过程保留三位小数。此例的计算结果表明，全主元素法的精度优于列此例的计算结果表明，全主元素法的精度优于列此

32、例的计算结果表明，全主元素法的精度优于列此例的计算结果表明，全主元素法的精度优于列主元法，这是由于全主元法是在全体元素中选主元，主元法，这是由于全主元法是在全体元素中选主元，主元法，这是由于全主元法是在全体元素中选主元，主元法，这是由于全主元法是在全体元素中选主元，故它对控制舍入误差十分有效。但是全主元法在计算故它对控制舍入误差十分有效。但是全主元法在计算故它对控制舍入误差十分有效。但是全主元法在计算故它对控制舍入误差十分有效。但是全主元法在计算过程中，需同时作行与列的互换，因而程序比较复杂过程中，需同时作行与列的互换，因而程序比较复杂过程中，需同时作行与列的互换，因而程序比较复杂过程中，需同

33、时作行与列的互换，因而程序比较复杂,计算时间较长。列主元法的精度虽稍低于全主元法，计算时间较长。列主元法的精度虽稍低于全主元法，计算时间较长。列主元法的精度虽稍低于全主元法，计算时间较长。列主元法的精度虽稍低于全主元法，但其计算简单，工作量大为减少，且计算经验与理论但其计算简单，工作量大为减少，且计算经验与理论但其计算简单，工作量大为减少，且计算经验与理论但其计算简单，工作量大为减少，且计算经验与理论分析均表明，它与全主元法同样具有良好的数值稳定分析均表明，它与全主元法同样具有良好的数值稳定分析均表明，它与全主元法同样具有良好的数值稳定分析均表明，它与全主元法同样具有良好的数值稳定性，故列主元

34、法是求解中小型稠密线性方程组的最好性，故列主元法是求解中小型稠密线性方程组的最好性，故列主元法是求解中小型稠密线性方程组的最好性，故列主元法是求解中小型稠密线性方程组的最好方法之一。方法之一。方法之一。方法之一。方法之一。方法之一。方法之一。方法之一。第25页，本讲稿共53页2.4解三对角方程组的追赶法在很多问题中，需要解如下形式的三对角方程组：在很多问题中，需要解如下形式的三对角方程组：在很多问题中，需要解如下形式的三对角方程组：在很多问题中，需要解如下形式的三对角方程组：三对角方程组的系数矩阵为三对角阵，对于这种特殊三对角方程组的系数矩阵为三对角阵，对于这种特殊三对角方程组的系数矩阵为三对

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

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

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

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

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

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

41、aussGauss消元法的消元法的消元法的消元法的 第一次消元第一次消元第一次消元第一次消元相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵：第29页，本讲稿共53页第二次消元第二次消元第二次消元第二次消元相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵：第第第第k k次消元次消元次消元次消元相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵：Gauss消元法的矩阵形式第30页，本讲稿共53页经过经过经过经过n n 1 1步消元后得到：步消元后得到：步消元后得到：步消元后得到：因为因为因为因为L Lk k(k k=1,2,=1,2

42、,n n 1)1)均为非奇异阵，故它们均为非奇异阵，故它们均为非奇异阵，故它们均为非奇异阵，故它们的逆矩阵存在。容易求出：的逆矩阵存在。容易求出：的逆矩阵存在。容易求出：的逆矩阵存在。容易求出：这说明：在这说明：在这说明：在这说明：在 的条件下，消元过程的条件下，消元过程的条件下，消元过程的条件下，消元过程实际上是把系数矩阵实际上是把系数矩阵实际上是把系数矩阵实际上是把系数矩阵A A分解成单位下三角阵与上三角矩阵分解成单位下三角阵与上三角矩阵分解成单位下三角阵与上三角矩阵分解成单位下三角阵与上三角矩阵的乘积的过程。的乘积的过程。的乘积的过程。的乘积的过程。Gauss消元法的矩阵形式（续）第31

43、页，本讲稿共53页杜利特尔（Doolittle）分解LU分解 事实上，只要事实上，只要事实上，只要事实上，只要A A满足一定条件，由上述结论，它一定满足一定条件，由上述结论，它一定满足一定条件，由上述结论，它一定满足一定条件，由上述结论，它一定可以分解成两个三角形矩阵的乘积，即：可以分解成两个三角形矩阵的乘积，即：可以分解成两个三角形矩阵的乘积，即：可以分解成两个三角形矩阵的乘积，即：A=LU A=LU 。上述分解称为杜利特尔（上述分解称为杜利特尔（上述分解称为杜利特尔（上述分解称为杜利特尔（DoolittleDoolittle）分解，也称为）分解，也称为）分解，也称为）分解，也称为LULU分

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

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

46、。也必须满足一定条件才能进行三角分解。也必须满足一定条件才能进行三角分解。也必须满足一定条件才能进行三角分解。设设设设A A为为为为n n阶方阵，若阶方阵，若阶方阵，若阶方阵，若A A的顺序主子式的顺序主子式的顺序主子式的顺序主子式A Ai i(i i=1,2,=1,2,n n)均不为零均不为零均不为零均不为零,则矩阵则矩阵则矩阵则矩阵A A存在唯一的存在唯一的存在唯一的存在唯一的DoolittleDoolittle分解。分解。分解。分解。定理定理定理定理2.12.1下面讨论如何对下面讨论如何对下面讨论如何对下面讨论如何对A A进行进行进行进行LULU分解分解分解分解：（1 1行行行行1 1列

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

48、乘法规则及比较（由矩阵乘法规则及比较（2-112-11）两端的元素，得：）两端的元素，得：）两端的元素，得：）两端的元素，得：即可由（即可由（即可由（即可由（2-122-12）求出）求出）求出）求出U U的第一行，的第一行，的第一行，的第一行，L L的第一列。的第一列。的第一列。的第一列。下面讨论一般情况，即：下面讨论一般情况，即：下面讨论一般情况，即：下面讨论一般情况，即：U U的第的第的第的第i i 行，行，行，行，L L的第的第的第的第j j列：列：列：列：第34页，本讲稿共53页一般情况下，可由：一般情况下，可由：一般情况下，可由：一般情况下，可由：对A进行LU分解（r 行r 列）计算

49、过程应按计算过程应按计算过程应按计算过程应按U U第第第第1 1行、行、行、行、L L第第第第1 1列列列列（第（第（第（第1 1框），框），框），框），U U第第第第2 2行、行、行、行、L L第第第第2 2列列列列（第（第（第（第2 2框），框），框），框），的顺序的顺序的顺序的顺序 具体分解步具体分解步具体分解步具体分解步骤见下屏：骤见下屏：骤见下屏：骤见下屏：得到计算得到计算得到计算得到计算u uij ij和和和和 l lij ij 的公式：的公式：的公式：的公式：第35页，本讲稿共53页对A进行LU分解的具体步骤1.计算计算U的第的第的第的第1 1行，行，行，行，L L的第的第1列，

50、亦称为计算列，亦称为计算 第第1框；框；2.计算计算U的第的第的第的第r 行，行，行，行，L的第的第的第的第r 列（列（r r=2,n n），），），），即第即第即第即第r 框框框框 ：第36页，本讲稿共53页矩阵A的LU分解举例解：按分解公式（解：按分解公式（解：按分解公式（解：按分解公式（2-132-13），），），），一框一框分解，每框计算时先行后列一框一框分解，每框计算时先行后列一框一框分解，每框计算时先行后列一框一框分解，每框计算时先行后列 ：所以：所以：所以：所以：例例例例5 5 第37页，本讲稿共53页3.3直接三角分解法 若线性方程组若线性方程组若线性方程组若线性方程组Ax A