《3线性方程组直接解法(1).ppt》由会员分享，可在线阅读，更多相关《3线性方程组直接解法(1).ppt（55页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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.6.方程组的性态和条件数方程组的性态和条件数方程组的性态和条件数方程组的性态和条件数线性方程组的概念 在科学研究和工程技术中所提出的计算问题中，线性在科学研究和工程技术中所提出的计算问题中，线性在科学研究和工程技术中所提出的计算问题中，线性在科学研究和工程技术中所提出的计算问
3、题中，线性方程组的求解问题是基本的，常见的，很多问题如插值函方程组的求解问题是基本的，常见的，很多问题如插值函方程组的求解问题是基本的，常见的，很多问题如插值函方程组的求解问题是基本的，常见的，很多问题如插值函数，最小二乘数据拟合，构造求解微分方程的差分格式等数，最小二乘数据拟合，构造求解微分方程的差分格式等数，最小二乘数据拟合，构造求解微分方程的差分格式等数，最小二乘数据拟合，构造求解微分方程的差分格式等，都包含了解线性方程组问题，因此，线性方程组的解法，都包含了解线性方程组问题，因此，线性方程组的解法，都包含了解线性方程组问题，因此，线性方程组的解法，都包含了解线性方程组问题，因此，线性方
4、程组的解法在数值计算中占有较重要的地位。在数值计算中占有较重要的地位。在数值计算中占有较重要的地位。在数值计算中占有较重要的地位。设设设设n n阶线性方程组：阶线性方程组：阶线性方程组：阶线性方程组：其矩阵形式为：其矩阵形式为：其矩阵形式为：其矩阵形式为：Ax=b (2-2)其中：其中：其中：其中：求解求解Ax=b，曾经学过曾经学过高斯（高斯（Gauss）消元法，消元法，克莱姆（克莱姆（Cramer）法则，矩阵变换法法则，矩阵变换法等，但已远等，但已远远满足不了实际运算的需要，主要体现远满足不了实际运算的需要，主要体现两个方面两个方面：一一是运算的快速和准确，是运算的快速和准确，其次其次是方程
5、组的个数增大是方程组的个数增大时的计算问题。如何建立能在计算机上可以实现的时的计算问题。如何建立能在计算机上可以实现的有效而实用的解法，具有极其重要的意义，我们也有效而实用的解法，具有极其重要的意义，我们也曾指出过，曾指出过，Cramer法则法则在理论上是绝对正确的，在理论上是绝对正确的，但当但当n较大时，在实际计算中却不能用。较大时，在实际计算中却不能用。线性方程组的概念（续）如果线性方程组如果线性方程组Ax=b的系数行列式不为零，的系数行列式不为零，即即det(A)0，则该方程组有唯一解。则该方程组有唯一解。线性方程组的数值解法解线性方程组的数值方法大致分为两类：解线性方程组的数值方法大致
6、分为两类：解线性方程组的数值方法大致分为两类：解线性方程组的数值方法大致分为两类：请注意：请注意：请注意：请注意：由于在计算中某些数据实际上只能用有限位由于在计算中某些数据实际上只能用有限位由于在计算中某些数据实际上只能用有限位由于在计算中某些数据实际上只能用有限位 小数，即不可避免地存在着舍入误差的影响，小数，即不可避免地存在着舍入误差的影响，小数，即不可避免地存在着舍入误差的影响，小数，即不可避免地存在着舍入误差的影响，因而即使是准确解法，也只能求到近似解。因而即使是准确解法，也只能求到近似解。因而即使是准确解法，也只能求到近似解。因而即使是准确解法，也只能求到近似解。1.直接法：直接法：
7、直接法：直接法：指假设计算过程中不产生含入误差，经过有指假设计算过程中不产生含入误差，经过有指假设计算过程中不产生含入误差，经过有指假设计算过程中不产生含入误差，经过有 限步四则运算可求得方程组准确解的方法。限步四则运算可求得方程组准确解的方法。限步四则运算可求得方程组准确解的方法。限步四则运算可求得方程组准确解的方法。2.2.迭代法：迭代法：迭代法：迭代法：从给定的方程组的一个近似值出发，构造某从给定的方程组的一个近似值出发，构造某从给定的方程组的一个近似值出发，构造某从给定的方程组的一个近似值出发，构造某种算法逐步将其准确化一般不能在有限步内得到准确解。种算法逐步将其准确化一般不能在有限步
8、内得到准确解。种算法逐步将其准确化一般不能在有限步内得到准确解。种算法逐步将其准确化一般不能在有限步内得到准确解。这一章介绍计算机上常用的直接法，它们都是以这一章介绍计算机上常用的直接法，它们都是以这一章介绍计算机上常用的直接法，它们都是以这一章介绍计算机上常用的直接法，它们都是以GaussGauss消元法为基本方法，即先将线性方程组化为等价的三角形消元法为基本方法，即先将线性方程组化为等价的三角形消元法为基本方法，即先将线性方程组化为等价的三角形消元法为基本方法，即先将线性方程组化为等价的三角形方程组，然后求解。方程组，然后求解。方程组，然后求解。方程组，然后求解。直接法在求解中小型线性方程
9、组（直接法在求解中小型线性方程组（直接法在求解中小型线性方程组（直接法在求解中小型线性方程组（100100个），个），个），个），特别是系数矩阵为稠密型时，是常用的、非常好的方法特别是系数矩阵为稠密型时，是常用的、非常好的方法特别是系数矩阵为稠密型时，是常用的、非常好的方法特别是系数矩阵为稠密型时，是常用的、非常好的方法1Gauss消元法GaussGauss消元法是最基本的一种方法，下例说明其消元法是最基本的一种方法，下例说明其消元法是最基本的一种方法，下例说明其消元法是最基本的一种方法，下例说明其基本思想基本思想基本思想基本思想:例例1解线性方程组：解线性方程组：解线性方程组：解线性方程组：
10、解：解：消去消去x1，进行第一次消元：首先找乘数，以进行第一次消元：首先找乘数，以-12乘第一个方程加到第二个方程，以乘第一个方程加到第二个方程，以18乘第一个乘第一个方程加到第三个方程上可得同解方程组方程加到第三个方程上可得同解方程组：例1（续）上述上述上述上述GaussGauss消元法的基本思想是：先逐次消去变量，将消元法的基本思想是：先逐次消去变量，将消元法的基本思想是：先逐次消去变量，将消元法的基本思想是：先逐次消去变量，将方程组化成同解的上三角形方程组，此过程称为方程组化成同解的上三角形方程组，此过程称为方程组化成同解的上三角形方程组，此过程称为方程组化成同解的上三角形方程组，此过程
11、称为消元过消元过消元过消元过程。程。程。程。然后按方程相反顺序求解上三角形方程组，得到原然后按方程相反顺序求解上三角形方程组，得到原然后按方程相反顺序求解上三角形方程组，得到原然后按方程相反顺序求解上三角形方程组，得到原方程组的解，此过程称为方程组的解，此过程称为方程组的解，此过程称为方程组的解，此过程称为回代过程。回代过程。回代过程。回代过程。再消一次元得：再消一次元得：二次消元后将方程化为二次消元后将方程化为二次消元后将方程化为二次消元后将方程化为倒三角形式，然后进行倒三角形式，然后进行倒三角形式，然后进行倒三角形式，然后进行回代容易解出：回代容易解出：回代容易解出：回代容易解出：x3=3
12、,x2=2,x1=1。我们的目的，是要总结归纳出一般情况下的我们的目的，是要总结归纳出一般情况下的我们的目的，是要总结归纳出一般情况下的我们的目的，是要总结归纳出一般情况下的n n阶线性方程阶线性方程阶线性方程阶线性方程组的消元公式和回代求解公式，从而得到求解组的消元公式和回代求解公式，从而得到求解组的消元公式和回代求解公式，从而得到求解组的消元公式和回代求解公式，从而得到求解n n阶线性方阶线性方阶线性方阶线性方程组的能顺利在计算机上实现的行之有效的算法。程组的能顺利在计算机上实现的行之有效的算法。程组的能顺利在计算机上实现的行之有效的算法。程组的能顺利在计算机上实现的行之有效的算法。Gau
13、ss消元法的基本步骤1（4阶）为能更清楚地得到算法，下面以为能更清楚地得到算法，下面以为能更清楚地得到算法，下面以为能更清楚地得到算法，下面以4 4阶线性方程组为例总结阶线性方程组为例总结阶线性方程组为例总结阶线性方程组为例总结求解步骤，并且很容易地可推广至一般的求解步骤，并且很容易地可推广至一般的求解步骤，并且很容易地可推广至一般的求解步骤，并且很容易地可推广至一般的n n阶线性方程组。阶线性方程组。阶线性方程组。阶线性方程组。可以检查，分别以可以检查，分别以可以检查，分别以可以检查，分别以 l li i1 1乘第一个方程加到第乘第一个方程加到第乘第一个方程加到第乘第一个方程加到第i i个方
14、程上个方程上个方程上个方程上可以完成第一次消元，得同解方程组：可以完成第一次消元，得同解方程组：可以完成第一次消元，得同解方程组：可以完成第一次消元，得同解方程组：变化以后的方变化以后的方变化以后的方变化以后的方程组系数及右程组系数及右程组系数及右程组系数及右边的常数项可边的常数项可边的常数项可边的常数项可总结出如下的总结出如下的总结出如下的总结出如下的计算公式：计算公式：计算公式：计算公式：完成第一次消元之后的完成第一次消元之后的完成第一次消元之后的完成第一次消元之后的方程组记为：方程组记为：方程组记为：方程组记为：A(2)x=b(2)Gauss消元法的基本步骤2（4阶）Gauss消元法的基
15、本步骤3（4阶）以方程组中第以方程组中第以方程组中第以方程组中第i i个方程减去第二个方程乘个方程减去第二个方程乘个方程减去第二个方程乘个方程减去第二个方程乘l li i2 2(i i=3,4)=3,4)，完完完完成第二次消元。成第二次消元。成第二次消元。成第二次消元。上标为上标为上标为上标为3 3的系数的系数的系数的系数和右端项可由和右端项可由和右端项可由和右端项可由下面公式计算：下面公式计算：下面公式计算：下面公式计算：Gauss消元法的基本步骤4（4阶）第三步第三步第三步第三步：消元（：消元（：消元（：消元（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 i个方程减去第个方程减去第个
18、方程减去第个方程减去第2 2个方程乘以个方程乘以个方程乘以个方程乘以l li i2 2 (i i=3,=3,n n)，完成完成完成完成第二步第二步第二步第二步消元。消元。消元。消元。Gauss消元法的消元过程3（n阶）第第第第k k 步步步步：设第：设第：设第：设第k k 1 1步消元后得原方程组的同解方程组为：步消元后得原方程组的同解方程组为：步消元后得原方程组的同解方程组为：步消元后得原方程组的同解方程组为：第第第第k k步消元后同步消元后同步消元后同步消元后同解方程组中上标解方程组中上标解方程组中上标解方程组中上标为为为为k k+1+1的元素的的元素的的元素的的元素的计算公式见下屏计算公
19、式见下屏计算公式见下屏计算公式见下屏Gauss消元法的消元过程3（n阶）照此消元下去，完成照此消元下去，完成n 1次次消元后，可将原方程组化成消元后，可将原方程组化成同解的上三角形方程组如下：同解的上三角形方程组如下：Gauss消元法的回代过程（n阶）回代过程回代过程：逐步回代求得原方程组的解逐步回代求得原方程组的解 Gauss消元法的计算量 由于在计算机中作乘除运算量所需时间远大于作加减由于在计算机中作乘除运算量所需时间远大于作加减由于在计算机中作乘除运算量所需时间远大于作加减由于在计算机中作乘除运算量所需时间远大于作加减运算所需时间，故只考虑作乘除运算量。运算所需时间，故只考虑作乘除运算量
20、。运算所需时间，故只考虑作乘除运算量。运算所需时间，故只考虑作乘除运算量。由消元法步骤知，第由消元法步骤知，第由消元法步骤知，第由消元法步骤知，第k k次消元需作次消元需作次消元需作次消元需作n n k k次除法，作次除法，作次除法，作次除法，作(n n k k)()(n n k k+1)+1)次乘法，故消元过程中乘除法运算量为：次乘法，故消元过程中乘除法运算量为：次乘法，故消元过程中乘除法运算量为：次乘法，故消元过程中乘除法运算量为：所以所以所以所以GaussGauss 消去法的消去法的消去法的消去法的乘除法乘除法乘除法乘除法总运算量总运算量总运算量总运算量为：为：为：为：Gauss法与Cr
21、amer法则的计算量比较 GaussGauss 消元法的乘消元法的乘消元法的乘消元法的乘除法总运算量为除法总运算量为除法总运算量为除法总运算量为：与我们曾经介绍的与我们曾经介绍的与我们曾经介绍的与我们曾经介绍的CramerCramer法则的乘除法总运算量法则的乘除法总运算量法则的乘除法总运算量法则的乘除法总运算量 (n n2 2 1)1)n n!+!+n n 相比，由下表可知：当阶数越高时，相比，由下表可知：当阶数越高时，相比，由下表可知：当阶数越高时，相比，由下表可知：当阶数越高时，GaussGauss消消消消元法所需乘除法次数比元法所需乘除法次数比元法所需乘除法次数比元法所需乘除法次数比C
22、ramerCramer法则要少得多：法则要少得多：法则要少得多：法则要少得多：方程组阶数方程组阶数方程组阶数方程组阶数3 3101020205050GaussGauss消元法运算量消元法运算量消元法运算量消元法运算量1717430430306030604415044150CramerCramer法则运算量法则运算量法则运算量法则运算量51513592512103592512109.7109.71020207.6107.6106767Gauss Gauss 消元法的优缺点：消元法的优缺点：消元法的优缺点：消元法的优缺点：但但但但其计算过程中，要求其计算过程中，要求其计算过程中，要求其计算过程中，
23、要求a akkkk(k k)（称为主元素）均不为零，称为主元素）均不为零，称为主元素）均不为零，称为主元素）均不为零，因而适用范围小，只适用于从因而适用范围小，只适用于从因而适用范围小，只适用于从因而适用范围小，只适用于从1 1到到到到n n 1 1阶顺序主子式均不阶顺序主子式均不阶顺序主子式均不阶顺序主子式均不为零的矩阵为零的矩阵为零的矩阵为零的矩阵A A，计算实践还表明，计算实践还表明，计算实践还表明，计算实践还表明，GaussGauss消元法的数值稳消元法的数值稳消元法的数值稳消元法的数值稳定性差，当出现小主元素时，会严重影响计算结果的精度，定性差，当出现小主元素时，会严重影响计算结果的
24、精度，定性差，当出现小主元素时，会严重影响计算结果的精度，定性差，当出现小主元素时，会严重影响计算结果的精度，甚至导出错误的结果。甚至导出错误的结果。甚至导出错误的结果。甚至导出错误的结果。GaussGauss消元法简单易行。消元法简单易行。消元法简单易行。消元法简单易行。2主元素法 2.1 引入主元素的必要性引入主元素的必要性 对线性方程组对线性方程组AX=b，若其系数行列式若其系数行列式 det(A)0，则该方程组有唯一则该方程组有唯一 解，但是这一条件解，但是这一条件 不能保证所有主元素都不等于零，只要某一主元不能保证所有主元素都不等于零，只要某一主元素等于零，就不能用素等于零，就不能用
25、Gauss消元法求解该方程组，消元法求解该方程组，即使所有主元素不等于零，但即使所有主元素不等于零，但 某一主元素的绝对某一主元素的绝对值很小时，值很小时，Gauss消元法也是不适用的。如下例消元法也是不适用的。如下例：例例2例2（续1）解：解：为减小误差，计算过程中保留为减小误差，计算过程中保留3位有效数字。位有效数字。按按Gauss消元法步骤：消元法步骤：第一次消元后得同解方程组：第一次消元后得同解方程组：第一次消元后得同解方程组：第一次消元后得同解方程组：第二次消元后得同解方程组第二次消元后得同解方程组第二次消元后得同解方程组第二次消元后得同解方程组 回代得解，回代得解，x3=2.02，
26、x2=2.40，x1=5.80。容易验证，方程组（容易验证，方程组（3-8）的准确解为：）的准确解为：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、，需同时作行与列的互换，因而程序比较复杂过程中，需同时作行与列的互换，因而程序比较复杂过程中，需同时作行与列的互换，因而程序比较复杂过程中，需同时作行与列的互换，因而程序比较复杂,计算时间较长。列主元法的精度虽稍低于全主元法，计算时间较长。列主元法的精度虽稍低于全主元法，计算时间较长。列主元法的精度虽稍低于全主元法，计算时间较长。列主元法的精度虽稍低于全主元法，但其计算简单，工作量大为减少，且计算经验与理论但其计算简单，工作量大为减少，且计算经验与理论但其计算简单，工作量大为减少，且计算经验与理论但其计算简单，工作量大为减少，且计算经验与理论分析均表明，它与全主元法同样具有良好的数值稳定分析均
32、表明，它与全主元法同样具有良好的数值稳定分析均表明，它与全主元法同样具有良好的数值稳定分析均表明，它与全主元法同样具有良好的数值稳定性，故列主元法是求解中小型稠密线性方程组的最好性，故列主元法是求解中小型稠密线性方程组的最好性，故列主元法是求解中小型稠密线性方程组的最好性，故列主元法是求解中小型稠密线性方程组的最好方法之一。方法之一。方法之一。方法之一。方法之一。方法之一。方法之一。方法之一。2.4解三对角方程组的追赶法 三对角方程组的系数矩阵为三对角阵，对于这种特殊三对角方程组的系数矩阵为三对角阵，对于这种特殊三对角方程组的系数矩阵为三对角阵，对于这种特殊三对角方程组的系数矩阵为三对角阵，对
33、于这种特殊而又简单的方程组，用前面介绍的方法求解由于有大量而又简单的方程组，用前面介绍的方法求解由于有大量而又简单的方程组，用前面介绍的方法求解由于有大量而又简单的方程组，用前面介绍的方法求解由于有大量的零元素既占内存又浪费计算时间，显然很不经济。充的零元素既占内存又浪费计算时间，显然很不经济。充的零元素既占内存又浪费计算时间，显然很不经济。充的零元素既占内存又浪费计算时间，显然很不经济。充分注意到三对角方程组的特点，根据顺序消元的思想导分注意到三对角方程组的特点，根据顺序消元的思想导分注意到三对角方程组的特点，根据顺序消元的思想导分注意到三对角方程组的特点，根据顺序消元的思想导出一个简便的算
34、法出一个简便的算法出一个简便的算法出一个简便的算法追赶法追赶法追赶法追赶法。在很多问题中，需要解如下形式的三对角方程组：在很多问题中，需要解如下形式的三对角方程组：在很多问题中，需要解如下形式的三对角方程组：在很多问题中，需要解如下形式的三对角方程组：追赶法的解题步骤 首先首先首先首先进行顺序消元，进行顺序消元，进行顺序消元，进行顺序消元，且每步将主元系数且每步将主元系数且每步将主元系数且每步将主元系数化为化为化为化为1 1，将方程组化为：，将方程组化为：，将方程组化为：，将方程组化为：其中系数按下式计算其中系数按下式计算其中系数按下式计算其中系数按下式计算 ：然后然后然后然后回代回代回代回代
35、求解，得求解，得求解，得求解，得：上述追赶法能进行到底上述追赶法能进行到底上述追赶法能进行到底上述追赶法能进行到底 。追赶法举例用追赶法解下用追赶法解下用追赶法解下用追赶法解下列三对角方程组：列三对角方程组：列三对角方程组：列三对角方程组：例例4解：解：解：解：首先将方程组化为首先将方程组化为首先将方程组化为首先将方程组化为（先追）（先追）（先追）（先追）：然后然后回代（赶）求解：回代（赶）求解：x5=0，x4=30/7，x3=6/7，x2=12/7，x1=0 可以看出，追赶法本质上还可以看出，追赶法本质上还可以看出，追赶法本质上还可以看出，追赶法本质上还是顺序消元法，但由于计算过程是顺序消元
36、法，但由于计算过程是顺序消元法，但由于计算过程是顺序消元法，但由于计算过程中只涉及系数矩阵的非零元，因此大大节约了计算机内存中只涉及系数矩阵的非零元，因此大大节约了计算机内存中只涉及系数矩阵的非零元，因此大大节约了计算机内存中只涉及系数矩阵的非零元，因此大大节约了计算机内存与计算量，按乘除法次数进行比较，与计算量，按乘除法次数进行比较，与计算量，按乘除法次数进行比较，与计算量，按乘除法次数进行比较，GaussGauss消元法消元法消元法消元法约为约为约为约为n n3 3/3/3，全主元法为全主元法为全主元法为全主元法为n n3 3/2/2，而而而而追赶法追赶法追赶法追赶法仅为仅为仅为仅为5 5
37、n n-3-3次，次，次，次，可见追赶可见追赶可见追赶可见追赶法是求解三对角方程组的非常好的方法。法是求解三对角方程组的非常好的方法。法是求解三对角方程组的非常好的方法。法是求解三对角方程组的非常好的方法。3矩阵分解法 如果用矩阵形式表示，如果用矩阵形式表示，如果用矩阵形式表示，如果用矩阵形式表示，GaussGauss消元法的消元过程是对消元法的消元过程是对消元法的消元过程是对消元法的消元过程是对方程组（方程组（方程组（方程组（2-12-1）的增广矩阵（）的增广矩阵（）的增广矩阵（）的增广矩阵（A A、b b）进行一系列的初等行进行一系列的初等行进行一系列的初等行进行一系列的初等行变换，将系数
38、矩阵变换，将系数矩阵变换，将系数矩阵变换，将系数矩阵A A化成上三角矩阵的过程，也等价于用化成上三角矩阵的过程，也等价于用化成上三角矩阵的过程，也等价于用化成上三角矩阵的过程，也等价于用一串初等变换阵去左乘增广矩阵，因此，消元过程可以通一串初等变换阵去左乘增广矩阵，因此，消元过程可以通一串初等变换阵去左乘增广矩阵，因此，消元过程可以通一串初等变换阵去左乘增广矩阵，因此，消元过程可以通过矩阵运算来实现。过矩阵运算来实现。过矩阵运算来实现。过矩阵运算来实现。紧接下屏：紧接下屏：紧接下屏：紧接下屏：3.1 GaussGauss消元法的矩阵形式消元法的矩阵形式消元法的矩阵形式消元法的矩阵形式 事实上，
39、事实上，事实上，事实上，GaussGauss消元法消元法消元法消元法的的的的 第一次消元第一次消元第一次消元第一次消元相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵：第二次消元第二次消元第二次消元第二次消元相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵：第第第第k k次消元次消元次消元次消元相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵：Gauss消元法的矩阵形式经过经过经过经过n n 1 1步消元后得到：步消元后得到：步消元后得到：步消元后得到：这说明：这说明：这说明：这说明：在在在在 的条件下，消元过程的条件下，消元过
40、程的条件下，消元过程的条件下，消元过程实际上是把系数矩阵实际上是把系数矩阵实际上是把系数矩阵实际上是把系数矩阵A A分解成单位下三角阵与上三角矩阵分解成单位下三角阵与上三角矩阵分解成单位下三角阵与上三角矩阵分解成单位下三角阵与上三角矩阵的乘积的过程。的乘积的过程。的乘积的过程。的乘积的过程。Gauss消元法的矩阵形式（续）因为因为因为因为L Lk k (k k=1,2,=1,2,n n 1)1)均为非奇异阵，故它们均为非奇异阵，故它们均为非奇异阵，故它们均为非奇异阵，故它们的逆矩阵存在。容易求出：的逆矩阵存在。容易求出：的逆矩阵存在。容易求出：的逆矩阵存在。容易求出：杜利特尔（Doolittl
41、e）分解LU分解 事实上，只要事实上，只要事实上，只要事实上，只要A A非奇异，由上述结论，它一定可以分非奇异，由上述结论，它一定可以分非奇异，由上述结论，它一定可以分非奇异，由上述结论，它一定可以分解成两个三角形矩阵的乘积，即：解成两个三角形矩阵的乘积，即：解成两个三角形矩阵的乘积，即：解成两个三角形矩阵的乘积，即：A A=L LU U 。消元过程相当于分解消元过程相当于分解消元过程相当于分解消元过程相当于分解A A=LULU及求解三角形方程组及求解三角形方程组及求解三角形方程组及求解三角形方程组LyLy=b b，回代过程则是求解另一个三角形方程组回代过程则是求解另一个三角形方程组回代过程则
42、是求解另一个三角形方程组回代过程则是求解另一个三角形方程组UxUx=y y，因此，因此，因此，因此，解线性方程组问题可转化为矩阵的三角分解问题。解线性方程组问题可转化为矩阵的三角分解问题。解线性方程组问题可转化为矩阵的三角分解问题。解线性方程组问题可转化为矩阵的三角分解问题。其中：其中：其中：其中：L L为单位下三角矩阵，为单位下三角矩阵，为单位下三角矩阵，为单位下三角矩阵，U U为上三角矩阵：为上三角矩阵：为上三角矩阵：为上三角矩阵：上述分解称为上述分解称为上述分解称为上述分解称为杜利特尔（杜利特尔（杜利特尔（杜利特尔（DoolittleDoolittle）分解分解分解分解，也称为也称为也称
43、为也称为LULU分解分解分解分解，当系数矩阵完成三角分解后，对于求解方程组：当系数矩阵完成三角分解后，对于求解方程组：当系数矩阵完成三角分解后，对于求解方程组：当系数矩阵完成三角分解后，对于求解方程组：AxAx=b b。3.2矩阵的三角分解 正如正如正如正如GaussGauss消元法要在一定条件下才能进行到底一样，消元法要在一定条件下才能进行到底一样，消元法要在一定条件下才能进行到底一样，消元法要在一定条件下才能进行到底一样，矩阵矩阵矩阵矩阵A A也必须满足一定条件才能进行三角分解。也必须满足一定条件才能进行三角分解。也必须满足一定条件才能进行三角分解。也必须满足一定条件才能进行三角分解。设设
44、设设A A为为为为n n阶方阵，若阶方阵，若阶方阵，若阶方阵，若A A的顺序主子式的顺序主子式的顺序主子式的顺序主子式A Ai i(i i=1,2,=1,2,n n 1)1)均不为零均不为零均不为零均不为零,则矩阵则矩阵则矩阵则矩阵A A存在唯一的存在唯一的存在唯一的存在唯一的DoolittleDoolittle分解分解分解分解。定理定理2.1存在性证明存在性证明存在性证明存在性证明唯一性证明唯一性证明唯一性证明唯一性证明下面讨论如何对下面讨论如何对下面讨论如何对下面讨论如何对A A进行进行进行进行LULU分解分解分解分解：（1 1行行行行1 1列列列列）由于两个矩阵相等就是它们的对应元素都相
45、等，因此由于两个矩阵相等就是它们的对应元素都相等，因此由于两个矩阵相等就是它们的对应元素都相等，因此由于两个矩阵相等就是它们的对应元素都相等，因此通过比较通过比较通过比较通过比较A A与与与与LULU的对应元素，即可得到直接计算的对应元素，即可得到直接计算的对应元素，即可得到直接计算的对应元素，即可得到直接计算L L、U U的的的的元素的公式：元素的公式：元素的公式：元素的公式：A A=LU LU 即：即：即：即：紧接下屏：紧接下屏：紧接下屏：紧接下屏：对A进行LU分解ALU由矩阵乘法规则及比较（由矩阵乘法规则及比较（由矩阵乘法规则及比较（由矩阵乘法规则及比较（2-112-11）两端的元素，得
46、：）两端的元素，得：）两端的元素，得：）两端的元素，得：即可由（即可由（即可由（即可由（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第第第
47、第1 1列列列列（第（第（第（第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 框框：矩阵A的LU分
48、解举例解：解：解：解：按分解公式（按分解公式（按分解公式（按分解公式（2-132-13），），），），一框一框分解，每框计算时先行后列一框一框分解，每框计算时先行后列一框一框分解，每框计算时先行后列一框一框分解，每框计算时先行后列 ：所以：所以：所以：所以：例例例例5 5 三角分解的紧凑格式 根据式（根据式（2-13）的特点，矩阵的三角分解可按）的特点，矩阵的三角分解可按以下格式及顺序进行。这种格式既便于记忆，又便以下格式及顺序进行。这种格式既便于记忆，又便于计算，称为于计算，称为紧凑格式紧凑格式。见下。见下表表2-1：表表表表2-12-1(a a1111)u u1111(a a1212)u
49、u1212(a a1313)u u1313(a a1 1n n)u u1 1n n (a a2121)l l2121(a a2222)u u2222(a a2323)u u2323(a a2 2n n)u u2 2n n (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 annnn)u unnnn (a a3131)l l3131(a a3232)l l3232(a a3333)u u3333(a a3 3n n)u u3 3n n （1）计算顺序计算顺序：将将aij，uij，lij 按表按表2-1列好，计算列好，计算
50、 时时按框从外到内进行，按框从外到内进行，每一框中每一框中先算行先算行。从从 左向右依次计算左向右依次计算 uij；再算列，自上而下求再算列，自上而下求 lij；三角分解的紧凑格式 （2）计算方法计算方法：按行按行计算计算时，需将所求元时，需将所求元 uij 的的 对应元对应元aij 逐次减去逐次减去 uij 所在行左面各框的元所在行左面各框的元 素素 lij 乘以乘以 uij 所在列上面各框相应的元所在列上面各框相应的元 uij。按列按列计算计算 lij 时，在作上述运算后还需除以时，在作上述运算后还需除以 lij 所在框的对角元所在框的对角元 lij 。说明：说明：三角分解的紧凑格式举例例