线性方程组直接解法省公共课一等奖全国赛课获奖课件.pptx

第三 章线性方程组线性方程组直接解法直接解法第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消去法矩阵形式消去法矩阵形式消去法矩阵形式消去法矩阵形式 3.2 3.2 矩阵三角分解矩阵三角分解矩阵三角分解矩阵三角分解 3.3 3.3 直接三角分解法直接三角分解法直接三角分解法直接三角分解法4.4.平方根法与改进平方根法平方根法与改进平方根法平方根法与改进平方根法平方根法与改进平方根法5.5.矩阵求逆矩阵求逆矩阵求逆矩阵求逆6.方程组性态和条件数方程组性态和条件数第2页第三章第三章 线性方程组直接解法线性方程组直接解法返回前进 设设设设n n阶线性方程组：阶线性方程组：阶线性方程组：阶线性方程组：其矩阵形式为：其矩阵形式为：其矩阵形式为：其矩阵形式为：Ax=b (2-2)其中：其中：其中：其中：在科学研究和工程技术中所提出计算问题中，线性在科学研究和工程技术中所提出计算问题中，线性在科学研究和工程技术中所提出计算问题中，线性在科学研究和工程技术中所提出计算问题中，线性方程组求解问题是基本，常见，很多问题如插值函方程组求解问题是基本，常见，很多问题如插值函方程组求解问题是基本，常见，很多问题如插值函方程组求解问题是基本，常见，很多问题如插值函数，最小二乘数据拟合，结构求解微分方程差分格式等数，最小二乘数据拟合，结构求解微分方程差分格式等数，最小二乘数据拟合，结构求解微分方程差分格式等数，最小二乘数据拟合，结构求解微分方程差分格式等，都包含了解线性方程组问题，所以，线性方程组解法，都包含了解线性方程组问题，所以，线性方程组解法，都包含了解线性方程组问题，所以，线性方程组解法，都包含了解线性方程组问题，所以，线性方程组解法在数值计算中占有较主要地位。在数值计算中占有较主要地位。在数值计算中占有较主要地位。在数值计算中占有较主要地位。第3页第三章第三章 线性方程组直接解法线性方程组直接解法返回前进 求解求解Ax=b，曾经学过高斯（，曾经学过高斯（Gauss）消元法，）消元法，克莱姆（克莱姆（Cramer）法则，矩阵变换法等，但已远）法则，矩阵变换法等，但已远远满足不了实际运算需要，主要表达两个方面：一远满足不了实际运算需要，主要表达两个方面：一是运算快速和准确，其次是方程组个数增大时计算是运算快速和准确，其次是方程组个数增大时计算问题。怎样建立能在计算机上能够实现有效而实用问题。怎样建立能在计算机上能够实现有效而实用解法，含有极其主要意义，我们也曾指出过，解法，含有极其主要意义，我们也曾指出过，Cramer法则在理论上是绝对正确，但当法则在理论上是绝对正确，但当n较大时，较大时，在实际计算中却不能用。在实际计算中却不能用。假如线性方程组假如线性方程组Ax=b系数行列式不为零，即系数行列式不为零，即det(A)0，则该方程组有唯一解。，则该方程组有唯一解。第4页第三章第三章 线性方程组直接解法线性方程组直接解法返回前进线性方程组数值解法解线性方程组数值方法大致分为两类：解线性方程组数值方法大致分为两类：解线性方程组数值方法大致分为两类：解线性方程组数值方法大致分为两类：请注意：因为在计算中一些数据实际上只能用有限位小请注意：因为在计算中一些数据实际上只能用有限位小请注意：因为在计算中一些数据实际上只能用有限位小请注意：因为在计算中一些数据实际上只能用有限位小 数，即不可防止地存在着舍入误差影响，因数，即不可防止地存在着舍入误差影响，因数，即不可防止地存在着舍入误差影响，因数，即不可防止地存在着舍入误差影响，因 而即使是准确解法，也只能求到近似解。而即使是准确解法，也只能求到近似解。而即使是准确解法，也只能求到近似解。而即使是准确解法，也只能求到近似解。直接法在求解中小型线性方程组（直接法在求解中小型线性方程组（直接法在求解中小型线性方程组（直接法在求解中小型线性方程组（100100个），尤其是个），尤其是个），尤其是个），尤其是系数矩阵为稠密型时，是惯用、非常好方法。系数矩阵为稠密型时，是惯用、非常好方法。系数矩阵为稠密型时，是惯用、非常好方法。系数矩阵为稠密型时，是惯用、非常好方法。1.直接法：指假设计算过程中不产生含入误差，经过有直接法：指假设计算过程中不产生含入误差，经过有直接法：指假设计算过程中不产生含入误差，经过有直接法：指假设计算过程中不产生含入误差，经过有 限步四则运算可求得方程组准确解方法。限步四则运算可求得方程组准确解方法。限步四则运算可求得方程组准确解方法。限步四则运算可求得方程组准确解方法。2.2.迭代法：从给定方程组一个近似值出发，结构某种算迭代法：从给定方程组一个近似值出发，结构某种算迭代法：从给定方程组一个近似值出发，结构某种算迭代法：从给定方程组一个近似值出发，结构某种算法逐步将其准确化，普通不能在有限步内得到准确解。法逐步将其准确化，普通不能在有限步内得到准确解。法逐步将其准确化，普通不能在有限步内得到准确解。法逐步将其准确化，普通不能在有限步内得到准确解。这一章介绍计算机上惯用直接法，它们都是以这一章介绍计算机上惯用直接法，它们都是以这一章介绍计算机上惯用直接法，它们都是以这一章介绍计算机上惯用直接法，它们都是以GaussGauss消消消消元法为基本方法，即先将线性方程组化为等价三角形方程元法为基本方法，即先将线性方程组化为等价三角形方程元法为基本方法，即先将线性方程组化为等价三角形方程元法为基本方法，即先将线性方程组化为等价三角形方程组，然后求解。组，然后求解。组，然后求解。组，然后求解。第5页第三章第三章 线性方程组直接解法线性方程组直接解法返回前进1Gauss消元法GaussGauss消元法是最基本一个方法，下例说明其消元法是最基本一个方法，下例说明其消元法是最基本一个方法，下例说明其消元法是最基本一个方法，下例说明其基本思想基本思想基本思想基本思想:例例1解线性方程组：解线性方程组：解线性方程组：解线性方程组：解：消去解：消去x1，进行第一次消元：首先找乘数，以，进行第一次消元：首先找乘数，以-12乘第一个方程加到第二个方程，以乘第一个方程加到第二个方程，以18乘第一个乘第一个方程加到第三个方程上可得同解方程组：方程加到第三个方程上可得同解方程组：第6页第三章第三章 线性方程组直接解法线性方程组直接解法返回前进例1（续）上述上述上述上述GaussGauss消元法基本思想是：先逐次消去变量，将方消元法基本思想是：先逐次消去变量，将方消元法基本思想是：先逐次消去变量，将方消元法基本思想是：先逐次消去变量，将方程组化成同解上三角形方程组，此过程称为消元过程组化成同解上三角形方程组，此过程称为消元过程组化成同解上三角形方程组，此过程称为消元过程组化成同解上三角形方程组，此过程称为消元过程。然后按方程相反次序求解上三角形方程组，得到原程。然后按方程相反次序求解上三角形方程组，得到原程。然后按方程相反次序求解上三角形方程组，得到原程。然后按方程相反次序求解上三角形方程组，得到原方程组解，此过程称为回代过程。方程组解，此过程称为回代过程。方程组解，此过程称为回代过程。方程组解，此过程称为回代过程。再消一次元得：再消一次元得：二次消元后将方程化为二次消元后将方程化为二次消元后将方程化为二次消元后将方程化为倒三角形式，然后进行倒三角形式，然后进行倒三角形式，然后进行倒三角形式，然后进行回代轻易解出：回代轻易解出：回代轻易解出：回代轻易解出：x3=3,x2=2,x1=1。我们目标，是要总结归纳出普通情况下我们目标，是要总结归纳出普通情况下我们目标，是要总结归纳出普通情况下我们目标，是要总结归纳出普通情况下n n阶线性方程阶线性方程阶线性方程阶线性方程组消元公式和回代求解公式，从而得到求解组消元公式和回代求解公式，从而得到求解组消元公式和回代求解公式，从而得到求解组消元公式和回代求解公式，从而得到求解n n阶线性方阶线性方阶线性方阶线性方程组能顺利在计算机上实现行之有效算法。程组能顺利在计算机上实现行之有效算法。程组能顺利在计算机上实现行之有效算法。程组能顺利在计算机上实现行之有效算法。第7页第三章第三章 线性方程组直接解法线性方程组直接解法返回前进 为能更清楚地得到算法，下面以为能更清楚地得到算法，下面以为能更清楚地得到算法，下面以为能更清楚地得到算法，下面以4 4阶线性方程组为例总结阶线性方程组为例总结阶线性方程组为例总结阶线性方程组为例总结求解步骤，而且很轻易地可推广至普通求解步骤，而且很轻易地可推广至普通求解步骤，而且很轻易地可推广至普通求解步骤，而且很轻易地可推广至普通n n阶线性方程组。阶线性方程组。阶线性方程组。阶线性方程组。第8页第三章第三章 线性方程组直接解法线性方程组直接解法返回前进 能够检验，分别以能够检验，分别以能够检验，分别以能够检验，分别以 l li i1 1乘第一个方程加到第乘第一个方程加到第乘第一个方程加到第乘第一个方程加到第i i个方程上个方程上个方程上个方程上能够完成第一次消元，得同解方程组：能够完成第一次消元，得同解方程组：能够完成第一次消元，得同解方程组：能够完成第一次消元，得同解方程组：改变以后方程改变以后方程改变以后方程改变以后方程组系数及右边组系数及右边组系数及右边组系数及右边常数项可总结常数项可总结常数项可总结常数项可总结出以下计算公出以下计算公出以下计算公出以下计算公式：式：式：式：完成第一次消元之后完成第一次消元之后完成第一次消元之后完成第一次消元之后方程组记为：方程组记为：方程组记为：方程组记为：A(2)x=b(2)第9页第三章第三章 线性方程组直接解法线性方程组直接解法返回前进Gauss消元法基本步骤3（4阶）以方程组中第以方程组中第以方程组中第以方程组中第i i个方程减去第二个方程乘个方程减去第二个方程乘个方程减去第二个方程乘个方程减去第二个方程乘l li i2 2(i i=3,4)=3,4)，完，完，完，完成第二次消元。成第二次消元。成第二次消元。成第二次消元。上标为上标为上标为上标为3 3系数系数系数系数和右端项可由和右端项可由和右端项可由和右端项可由下面公式计算：下面公式计算：下面公式计算：下面公式计算：第10页第三章第三章 线性方程组直接解法线性方程组直接解法返回前进第三步第三步第三步第三步：消元（：消元（：消元（：消元（4 4阶方程组需进行阶方程组需进行阶方程组需进行阶方程组需进行3 3次消元）次消元）次消元）次消元）将上述将上述将上述将上述 A A (3)(3)X X=b b(3)(3)中最终一个方程中中最终一个方程中中最终一个方程中中最终一个方程中x x3 3消为零消为零消为零消为零：然后可回代求解：因为然后可回代求解：因为然后可回代求解：因为然后可回代求解：因为A A(4)(4)为上三角形，所以可为上三角形，所以可为上三角形，所以可为上三角形，所以可按变量逆序逐步回代求原按变量逆序逐步回代求原按变量逆序逐步回代求原按变量逆序逐步回代求原方程组解：方程组解：方程组解：方程组解：上述上述上述上述 消元、回代求解过程消元、回代求解过程消元、回代求解过程消元、回代求解过程很轻易推广到普通很轻易推广到普通很轻易推广到普通很轻易推广到普通n n阶线阶线阶线阶线性方程组。性方程组。性方程组。性方程组。经过上述消元步骤，经过上述消元步骤，经过上述消元步骤，经过上述消元步骤，得到同解上三角形方得到同解上三角形方得到同解上三角形方得到同解上三角形方程组：程组：程组：程组：A(4)x=b(4)第11页第三章第三章 线性方程组直接解法线性方程组直接解法返回前进Gauss消元法消元过程1、2（n阶）普通地，设普通地，设普通地，设普通地，设 n n阶方程组：阶方程组：阶方程组：阶方程组：消元过程为：消元过程为：消元过程为：消元过程为：将上方程组中第将上方程组中第将上方程组中第将上方程组中第i i个方程减去第个方程减去第个方程减去第个方程减去第2 2个方程乘以个方程乘以个方程乘以个方程乘以l li i2 2(i i=3,=3,n n)，完成，完成，完成，完成第二步消元。第二步消元。第二步消元。第二步消元。第12页第三章第三章 线性方程组直接解法线性方程组直接解法返回前进第第第第k k 步：设第步：设第步：设第步：设第k k 1 1步消元后得原方程组同解方程组为：步消元后得原方程组同解方程组为：步消元后得原方程组同解方程组为：步消元后得原方程组同解方程组为：第第第第k k步消元后同步消元后同步消元后同步消元后同解方程组中上标解方程组中上标解方程组中上标解方程组中上标为为为为k k+1+1元素元素元素元素计算公式见下屏计算公式见下屏计算公式见下屏计算公式见下屏第13页第三章第三章 线性方程组直接解法线性方程组直接解法返回前进照此消元下去，完成照此消元下去，完成n 1次次消元后，可将原方程组化成消元后，可将原方程组化成同解上三角形方程组以下：同解上三角形方程组以下：第14页第三章第三章 线性方程组直接解法线性方程组直接解法返回前进Gauss消元法回代过程（n阶）回代过程回代过程：逐步回代求得原方程组解逐步回代求得原方程组解 第15页第三章第三章 线性方程组直接解法线性方程组直接解法返回前进Gauss消元法计算量 因为在计算机中作乘除运算量所需时间远大于作加减因为在计算机中作乘除运算量所需时间远大于作加减因为在计算机中作乘除运算量所需时间远大于作加减因为在计算机中作乘除运算量所需时间远大于作加减运算所需时间，故只考虑作乘除运算量。运算所需时间，故只考虑作乘除运算量。运算所需时间，故只考虑作乘除运算量。运算所需时间，故只考虑作乘除运算量。由消元法步骤知，第由消元法步骤知，第由消元法步骤知，第由消元法步骤知，第k k次消元需作次消元需作次消元需作次消元需作n n k k次除法，作次除法，作次除法，作次除法，作(n n k k)()(n n k k+1)+1)次乘法，故消元过程中乘除法运算量为：次乘法，故消元过程中乘除法运算量为：次乘法，故消元过程中乘除法运算量为：次乘法，故消元过程中乘除法运算量为：所以所以所以所以GaussGauss 消去法消去法消去法消去法乘除法总运算量为：乘除法总运算量为：乘除法总运算量为：乘除法总运算量为：第16页第三章第三章 线性方程组直接解法线性方程组直接解法返回前进Gauss法与Cramer法则计算量比较 Gauss Gauss 消元法乘消元法乘消元法乘消元法乘除法总运算量为除法总运算量为除法总运算量为除法总运算量为：与我们曾经介绍与我们曾经介绍与我们曾经介绍与我们曾经介绍CramerCramer法则乘除法总运算量法则乘除法总运算量法则乘除法总运算量法则乘除法总运算量 (n n2 2 1)1)n n!+!+n n 相比，由下表可知：当阶数越高时，相比，由下表可知：当阶数越高时，相比，由下表可知：当阶数越高时，相比，由下表可知：当阶数越高时，GaussGauss消消消消元法所需乘除法次数比元法所需乘除法次数比元法所需乘除法次数比元法所需乘除法次数比CramerCramer法则要少得多：法则要少得多：法则要少得多：法则要少得多：方程组阶数方程组阶数方程组阶数方程组阶数3 3101020205050GaussGauss消元法运算量消元法运算量消元法运算量消元法运算量1717430430306030604415044150CramerCramer法则运算量法则运算量法则运算量法则运算量51513592512103592512109.7109.71020207.6107.6106767Gauss Gauss 消元法优缺点：消元法优缺点：消元法优缺点：消元法优缺点：但其计算过程中，要求但其计算过程中，要求但其计算过程中，要求但其计算过程中，要求a akkkk(k k)（称为主元素）均不为零，（称为主元素）均不为零，（称为主元素）均不为零，（称为主元素）均不为零，因而适用范围小，只适合用于从因而适用范围小，只适合用于从因而适用范围小，只适合用于从因而适用范围小，只适合用于从1 1到到到到n n 1 1阶次序主子式均阶次序主子式均阶次序主子式均阶次序主子式均不为零矩阵不为零矩阵不为零矩阵不为零矩阵A A，计算实践还表明，计算实践还表明，计算实践还表明，计算实践还表明，GaussGauss消元法数值稳定消元法数值稳定消元法数值稳定消元法数值稳定性差，当出现小主元素时，会严重影响计算结果精度，甚性差，当出现小主元素时，会严重影响计算结果精度，甚性差，当出现小主元素时，会严重影响计算结果精度，甚性差，当出现小主元素时，会严重影响计算结果精度，甚至导犯错误结果。至导犯错误结果。至导犯错误结果。至导犯错误结果。GaussGauss消元法简单易行。消元法简单易行。消元法简单易行。消元法简单易行。第17页第三章第三章 线性方程组直接解法线性方程组直接解法返回前进2主元素法 2.1 引入主元素必要性引入主元素必要性 对线性方程组对线性方程组AX=b，若其系数行列式，若其系数行列式 det(A)0，则该方程组有唯一，则该方程组有唯一 解，不过这一条件解，不过这一条件 不能确保全部主元素都不等于零，只要某一主元不能确保全部主元素都不等于零，只要某一主元素等于零，就不能用素等于零，就不能用Gauss消元法求解该方程组，消元法求解该方程组，即使全部主元素不等于零，但即使全部主元素不等于零，但 某一主元素绝对某一主元素绝对值很小时，值很小时，Gauss消元法也是不适用。以下例：消元法也是不适用。以下例：例例2第18页第三章第三章 线性方程组直接解法线性方程组直接解法返回前进例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页第三章第三章 线性方程组直接解法线性方程组直接解法返回前进 若在解方程组前，先交换方程次序，若在解方程组前，先交换方程次序，如将（如将（2-8）交换一行与二行改写成以下所表示：）交换一行与二行改写成以下所表示：再用再用Gauss消元法，次序消元后得同解方程组：消元法，次序消元后得同解方程组：回代得解：回代得解：x3=2.00，x2=1.00，x1=2.60 与准确解相同。与准确解相同。例2（续2）第20页第三章第三章 线性方程组直接解法线性方程组直接解法返回前进例2两种解法误差分析 在例在例2中，对中，对(2-8)方程进行次序消元时，方程进行次序消元时，主元主元a(1)11=0.50，a(2)22=0.100都比较小，以它们作都比较小，以它们作 除数就增加了舍入误差除数就增加了舍入误差,而造成计算结果不准确。而造成计算结果不准确。产生上述现象原因在于舍入误差，当产生上述现象原因在于舍入误差，当|a(k)kk|很小时，进行第很小时，进行第k次消元，要用次消元，要用|a(k)kk|作除数，这作除数，这 样就可能增大舍入误差造成溢出停机，或者造成样就可能增大舍入误差造成溢出停机，或者造成 错误结果。错误结果。为了在计算过程中，抑制舍入误差增加，为了在计算过程中，抑制舍入误差增加，应尽可能防止小主元出现。如例应尽可能防止小主元出现。如例2第二种解法第二种解法,经过交换方程次序，选取绝对值大元素作主元经过交换方程次序，选取绝对值大元素作主元 基于这种思想而导出主元素法。基于这种思想而导出主元素法。第21页第三章第三章 线性方程组直接解法线性方程组直接解法返回前进2.2列主元素法 为简便起见，对方为简便起见，对方 程组（程组（2-1），用），用 其增其增 广矩阵：广矩阵：表示，并直接在增广表示，并直接在增广矩阵上进行运算。矩阵上进行运算。列主元素法详细步骤以下：列主元素法详细步骤以下：第22页第三章第三章 线性方程组直接解法线性方程组直接解法返回前进列主元素法如此经过如此经过如此经过如此经过n n 1 1步，增广矩阵（步，增广矩阵（步，增广矩阵（步，增广矩阵（2-92-9）被化成上三角形，然）被化成上三角形，然）被化成上三角形，然）被化成上三角形，然后由回代过程求解。后由回代过程求解。后由回代过程求解。后由回代过程求解。在上述过程中，主元是按列选取，故称为在上述过程中，主元是按列选取，故称为在上述过程中，主元是按列选取，故称为在上述过程中，主元是按列选取，故称为列主元法列主元法列主元法列主元法。例例例例2 2中第二种解法就是按列主元法进行。中第二种解法就是按列主元法进行。中第二种解法就是按列主元法进行。中第二种解法就是按列主元法进行。第23页第三章第三章 线性方程组直接解法线性方程组直接解法返回前进2.3全主元素法经过经过n k次消元后，得到与方程组（次消元后，得到与方程组（2-1）同解上）同解上三角形方程组，再由回代过程求解。三角形方程组，再由回代过程求解。第24页第三章第三章 线性方程组直接解法线性方程组直接解法返回前进例例6计算过程保留三位小数。此例计算结果表明，全主元素法精度优于列此例计算结果表明，全主元素法精度优于列此例计算结果表明，全主元素法精度优于列此例计算结果表明，全主元素法精度优于列主元法，这是因为全主元法是在全体元素中选主元，主元法，这是因为全主元法是在全体元素中选主元，主元法，这是因为全主元法是在全体元素中选主元，主元法，这是因为全主元法是在全体元素中选主元，故它对控制舍入误差十分有效。不过全主元法在计算故它对控制舍入误差十分有效。不过全主元法在计算故它对控制舍入误差十分有效。不过全主元法在计算故它对控制舍入误差十分有效。不过全主元法在计算过程中，需同时作行与列交换，因而程序比较复杂过程中，需同时作行与列交换，因而程序比较复杂过程中，需同时作行与列交换，因而程序比较复杂过程中，需同时作行与列交换，因而程序比较复杂,计算时间较长。列主元法精度虽稍低于全主元法，计算时间较长。列主元法精度虽稍低于全主元法，计算时间较长。列主元法精度虽稍低于全主元法，计算时间较长。列主元法精度虽稍低于全主元法，但其计算简单，工作量大为降低，且计算经验与理论但其计算简单，工作量大为降低，且计算经验与理论但其计算简单，工作量大为降低，且计算经验与理论但其计算简单，工作量大为降低，且计算经验与理论分析均表明，它与全主元法一样含有良好数值稳定分析均表明，它与全主元法一样含有良好数值稳定分析均表明，它与全主元法一样含有良好数值稳定分析均表明，它与全主元法一样含有良好数值稳定性，故列主元法是求解中小型稠密线性方程组最好性，故列主元法是求解中小型稠密线性方程组最好性，故列主元法是求解中小型稠密线性方程组最好性，故列主元法是求解中小型稠密线性方程组最好方法之一。方法之一。方法之一。方法之一。方法之一。方法之一。方法之一。方法之一。第25页第三章第三章 线性方程组直接解法线性方程组直接解法返回前进2.4解三对角方程组追赶法在很多问题中，需要解以下形式三对角方程组：在很多问题中，需要解以下形式三对角方程组：在很多问题中，需要解以下形式三对角方程组：在很多问题中，需要解以下形式三对角方程组：三对角方程组系数矩阵为三对角阵，对于这种特殊而三对角方程组系数矩阵为三对角阵，对于这种特殊而三对角方程组系数矩阵为三对角阵，对于这种特殊而三对角方程组系数矩阵为三对角阵，对于这种特殊而又简单方程组，用前面介绍方法求解因为有大量零元素又简单方程组，用前面介绍方法求解因为有大量零元素又简单方程组，用前面介绍方法求解因为有大量零元素又简单方程组，用前面介绍方法求解因为有大量零元素既占内存又浪费计算时间，显然很不经济。充分注意到既占内存又浪费计算时间，显然很不经济。充分注意到既占内存又浪费计算时间，显然很不经济。充分注意到既占内存又浪费计算时间，显然很不经济。充分注意到三对角方程组特点，依据次序消元思想导出一个简便算三对角方程组特点，依据次序消元思想导出一个简便算三对角方程组特点，依据次序消元思想导出一个简便算三对角方程组特点，依据次序消元思想导出一个简便算法法法法追赶法。追赶法。追赶法。追赶法。第26页第三章第三章 线性方程组直接解法线性方程组直接解法返回前进 首先进行次序消元，首先进行次序消元，首先进行次序消元，首先进行次序消元，且每步将主元系数且每步将主元系数且每步将主元系数且每步将主元系数化为化为化为化为1 1，将方程组化为：，将方程组化为：，将方程组化为：，将方程组化为：其中系数按下式计算其中系数按下式计算其中系数按下式计算其中系数按下式计算 ：然后回代然后回代然后回代然后回代求解，得：求解，得：求解，得：求解，得：上述追赶法能进行到底上述追赶法能进行到底上述追赶法能进行到底上述追赶法能进行到底 。第27页第三章第三章 线性方程组直接解法线性方程组直接解法返回前进追赶法举例用追赶法解下用追赶法解下用追赶法解下用追赶法解下列三对角方程组：列三对角方程组：列三对角方程组：列三对角方程组：例例4解：解：解：解：首先将方程组化为（先追）：首先将方程组化为（先追）：首先将方程组化为（先追）：首先将方程组化为（先追）：然后回代（赶）求解：然后回代（赶）求解：x5=0，x4=30/7，x3=6/7，x2=12/7，x1=0 能够看出，追赶法本质上还能够看出，追赶法本质上还能够看出，追赶法本质上还能够看出，追赶法本质上还是次序消元法，但因为计算过程是次序消元法，但因为计算过程是次序消元法，但因为计算过程是次序消元法，但因为计算过程中只包括系数矩阵非零元，所以大大节约了计算机内存与中只包括系数矩阵非零元，所以大大节约了计算机内存与中只包括系数矩阵非零元，所以大大节约了计算机内存与中只包括系数矩阵非零元，所以大大节约了计算机内存与计算量，按乘除法次数进行比较，计算量，按乘除法次数进行比较，计算量，按乘除法次数进行比较，计算量，按乘除法次数进行比较，GaussGauss消元法约为消元法约为消元法约为消元法约为n n3 3/3/3，全主元法为，全主元法为，全主元法为，全主元法为n n3 3/2/2，而追赶法仅为，而追赶法仅为，而追赶法仅为，而追赶法仅为5 5n n-3-3次，可见追赶法是次，可见追赶法是次，可见追赶法是次，可见追赶法是求解三对角方程组非常好方法。求解三对角方程组非常好方法。求解三对角方程组非常好方法。求解三对角方程组非常好方法。第28页第三章第三章 线性方程组直接解法线性方程组直接解法返回前进3矩阵分解法 假如用矩阵形式表示，假如用矩阵形式表示，假如用矩阵形式表示，假如用矩阵形式表示，GaussGauss消元法消元过程是对方消元法消元过程是对方消元法消元过程是对方消元法消元过程是对方程组（程组（程组（程组（2-12-1）增广矩阵（）增广矩阵（）增广矩阵（）增广矩阵（A A、b b）进行一系列初等行变换，）进行一系列初等行变换，）进行一系列初等行变换，）进行一系列初等行变换，将系数矩阵将系数矩阵将系数矩阵将系数矩阵A A化成上三角矩阵过程，也等价于用一串初等化成上三角矩阵过程，也等价于用一串初等化成上三角矩阵过程，也等价于用一串初等化成上三角矩阵过程，也等价于用一串初等变换阵去左乘增广矩阵，所以，消元过程能够经过矩阵运变换阵去左乘增广矩阵，所以，消元过程能够经过矩阵运变换阵去左乘增广矩阵，所以，消元过程能够经过矩阵运变换阵去左乘增广矩阵，所以，消元过程能够经过矩阵运算来实现。算来实现。算来实现。算来实现。紧接下屏：紧接下屏：紧接下屏：紧接下屏：3.1 GaussGauss消元法矩阵形式消元法矩阵形式消元法矩阵形式消元法矩阵形式 实际上，实际上，实际上，实际上，GaussGauss消元法消元法消元法消元法 第一次消元第一次消元第一次消元第一次消元相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵：第29页第三章第三章 线性方程组直接解法线性方程组直接解法返回前进第二次消元第二次消元第二次消元第二次消元相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵：第第第第k k次消元次消元次消元次消元相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵：Gauss消元法矩阵形式第30页第三章第三章 线性方程组直接解法线性方程组直接解法返回前进经过经过经过经过n n 1 1步消元后得到：步消元后得到：步消元后得到：步消元后得到：因为因为因为因为L Lk k(k k=1,2,=1,2,n n 1)1)均为非奇异阵，故它们均为非奇异阵，故它们均为非奇异阵，故它们均为非奇异阵，故它们逆矩阵存在。轻易求出：逆矩阵存在。轻易求出：逆矩阵存在。轻易求出：逆矩阵存在。轻易求出：这说明：在这说明：在这说明：在这说明：在 条件下，消元过程实条件下，消元过程实条件下，消元过程实条件下，消元过程实际上是把系数矩阵际上是把系数矩阵际上是把系数矩阵际上是把系数矩阵A A分解成单位下三角阵与上三角矩阵乘分解成单位下三角阵与上三角矩阵乘分解成单位下三角阵与上三角矩阵乘分解成单位下三角阵与上三角矩阵乘积过程。积过程。积过程。积过程。Gauss消元法矩阵形式（续）第31页第三章第三章 线性方程组直接解法线性方程组直接解法返回前进杜利特尔（Doolittle）分解LU分解 实际上，只要实际上，只要实际上，只要实际上，只要A A满足一定条件，由上述结论，它一定满足一定条件，由上述结论，它一定满足一定条件，由上述结论，它一定满足一定条件，由上述结论，它一定能够分解成两个三角形矩阵乘积，即：能够分解成两个三角形矩阵乘积，即：能够分解成两个三角形矩阵乘积，即：能够分解成两个三角形矩阵乘积，即：A=LU A=LU 。上述分解称为杜利特尔（上述分解称为杜利特尔（上述分解称为杜利特尔（上述分解称为杜利特尔（DoolittleDoolittle）分解，也称为）分解，也称为）分解，也称为）分解，也称为LULU分解，分解，分解，分解，当系数矩阵完成三角分解后，对于求解方程组：当系数矩阵完成三角分解后，对于求解方程组：当系数矩阵完成三角分解后，对于求解方程组：当系数矩阵完成三角分解后，对于求解方程组：AxAx=b b。消元过程相当于分解消元过程相当于分解消元过程相当于分解消元过程相当于分解A A=LULU及求解三角形方程组及求解三角形方程组及求解三角形方程组及求解三角形方程组LyLy=b b，回代过程则是求解另一个三角形方程组，回代过程则是求解另一个三角形方程组，回代过程则是求解另一个三角形方程组，回代过程则是求解另一个三角形方程组UxUx=y y，所以，所以，所以，所以，解线性方程组问题可转化为矩阵三角分解问题。解线性方程组问题可转化为矩阵三角分解问题。解线性方程组问题可转化为矩阵三角分解问题。解线性方程组问题可转化为矩阵三角分解问题。其中：其中：其中：其中：L L为单位下三角矩阵，为单位下三角矩阵，为单位下三角矩阵，为单位下三角矩阵，U U为上三角矩阵：为上三角矩阵：为上三角矩阵：为上三角矩阵：第32页第三章第三章 线性方程组直接解法线性方程组直接解法返回前进3.2矩阵三角分解 正如正如正如正如GaussGauss消元法要在一定条件下才能进行到底一样，消元法要在一定条件下才能进行到底一样，消元法要在一定条件下才能进行到底一样，消元法要在一定条件下才能进行到底一样，矩阵矩阵矩阵矩阵A A也必须满足一定条件才能进行三角分解。也必须满足一定条件才能进行三角分解。也必须满足一定条件才能进行三角分解。也必须满足一定条件才能进行三角分解。设设设设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列列列列）因为两个矩阵相等就是它们对应元素都相等，所以经因为两个矩阵相等就是它们对应元素都相等，所以经因为两个矩阵相等就是它们对应元素都相等，所以经因为两个矩阵相等就是它们对应元素都相等，所以经过比较过比较过比较过比较A A与与与与LULU对应元素，即可得到直接计算对应元素，即可得到直接计算对应元素，即可得到直接计算对应元素，即可得到直接计算L L、U U元素公元素公元素公元素公式：式：式：式：A A=LU LU 即：即：即：即：紧接下屏：紧接下屏：紧接下屏：紧接下屏：第33页第三章第三章 线性方程组直接解法线性方程组直接解法返回前进对A进行LU分解ALU由矩阵乘法规则及比较（由矩阵乘法规则及比较（由矩阵乘法规则及比较（由矩阵乘法规则及比较（2-112-11）两端元素，得：）两端元素，得：）两端元素，得：）两端元素，得：即可由（即可由（即可由（即可由（2-122-12）求出）求出）求出）求出U U第一行，第一行，第一行，第一行，L L第一列。第一列。第一列。第一列。下面讨论普通情况，即：下面讨论普通情况，即：下面讨论普通情况，即：下面讨论普通情况，即：U U第第第第i i 行，行，行，行，L L第第第第j j列：列：列：列：第34页第三章第三章 线性方程组直接解法线性方程组直接解法返回前进普通情况下，可由：普通情况下，可由：普通情况下，可由：普通情况下，可由：对A进行LU分解（r 行r 列）计算过程应按计算过程应按计算过程应按计算过程应按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页第三章第三章 线性方程组直接解法线性方程组直接解法返回前进对A进行LU分解详细步骤1.计算计算U第第1行，行，L第第1列，亦称为计算列，亦称为计算 第第1框；框；2.计算计算U第第r 行，行，L第第r 列（列（r=2,n），），即第即第r 框框：第36页第三章第三章 线性方程组直接解法线性方程组直接解法返回前进矩阵ALU分解举例解：按分解公式（解：按分解公式（解：按分解公式（解：按分解公式（2-132-13），），），），一框一框分解，每框计算时先行后列一框一框分解，每框计算时先行后列一框一框分解，每框计算时先行后列一框一框分解，每框计算时先行后列 ：所以：所以：所以：所以：例例例例5 5 第37页第三章第三章 线性方程组直接解法线性方程组直接解法返回前进3.3直接三角分解法 若线性方程组若线性方程组若线性方程组若线性方程组Ax Ax=b b系数矩阵系数矩阵系数矩阵系数矩阵A A完成三角分解，完成三角分解，完成三角分解，完成三角分解，A A=LULU，那么解，那么解，那么解，那么解方程组方程组方程组方程组Ax