第三章线性方程组直接解法PPT讲稿.ppt

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

1、第三章线性方程组直接解法第1页，共53页，编辑于2022年，星期二第三章目录1.1.Gauus 消元法消元法消元法消元法2.主元素法主元素法 2.1 引入主元素法的必要性引入主元素法的必要性 2.2 列主元素法列主元素法 2.3 全主元素法全主元素法 2.4 2.4 解三对角方程组的追赶法解三对角方程组的追赶法解三对角方程组的追赶法解三对角方程组的追赶法3.矩阵分解法矩阵分解法 3.1 3.1 Gauss消去法的矩阵形式消去法的矩阵形式 3.2 矩阵的三角分解矩阵的三角分解 3.3 3.3 直接三角分解法直接三角分解法直接三角分解法直接三角分解法4.4.平方根法与改进的平方根法平方根法与改进的

2、平方根法平方根法与改进的平方根法平方根法与改进的平方根法5.5.矩阵求逆矩阵求逆矩阵求逆矩阵求逆6.方程组的性态和条件数方程组的性态和条件数第2页，共53页，编辑于2022年，星期二 设设设设n n阶线性方程组：阶线性方程组：阶线性方程组：阶线性方程组：其矩阵形式为：其矩阵形式为：Ax=b (2-2)其中：其中：其中：其中：在科学研究和工程技术中所提出的计算问题中，线性在科学研究和工程技术中所提出的计算问题中，线性在科学研究和工程技术中所提出的计算问题中，线性在科学研究和工程技术中所提出的计算问题中，线性方程组的求解问题是基本的，常见的，很多问题如插值函方程组的求解问题是基本的，常见的，很多问

3、题如插值函数，最小二乘数据拟合，构造求解微分方程的差分格式等数，最小二乘数据拟合，构造求解微分方程的差分格式等，都包含了解线性方程组问题，因此，线性方程组的解法，都包含了解线性方程组问题，因此，线性方程组的解法，都包含了解线性方程组问题，因此，线性方程组的解法，都包含了解线性方程组问题，因此，线性方程组的解法在数值计算中占有较重要的地位。在数值计算中占有较重要的地位。第3页，共53页，编辑于2022年，星期二 求解求解Ax=b，曾经学过高斯（，曾经学过高斯（Gauss）消元法，克莱）消元法，克莱姆（姆（Cramer）法则，矩阵变换法等，但已远）法则，矩阵变换法等，但已远远满足不了实际运算的需要

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

5、则该方程组有唯一解。第4页，共53页，编辑于2022年，星期二线性方程组的数值解法解线性方程组的数值方法大致分为两类：解线性方程组的数值方法大致分为两类：请注意：由于在计算中某些数据实际上只能用有限位小请注意：由于在计算中某些数据实际上只能用有限位小请注意：由于在计算中某些数据实际上只能用有限位小请注意：由于在计算中某些数据实际上只能用有限位小 数，即不可避免地存在着舍入误差的影响，因数，即不可避免地存在着舍入误差的影响，因数，即不可避免地存在着舍入误差的影响，因数，即不可避免地存在着舍入误差的影响，因 而即使是准确解法，也只能求到近似解。而即使是准确解法，也只能求到近似解。直接法在求解中小型

6、线性方程组（直接法在求解中小型线性方程组（100个），特别是系个），特别是系数矩阵为稠密型时，是常用的、非常好的方法。数矩阵为稠密型时，是常用的、非常好的方法。1.直接法：指假设计算过程中不产生含入误差，经过有直接法：指假设计算过程中不产生含入误差，经过有 限步四则运算可求得方程组准确解的方法。限步四则运算可求得方程组准确解的方法。2.2.迭代法：从给定的方程组的一个近似值出发，构造某种算法迭代法：从给定的方程组的一个近似值出发，构造某种算法迭代法：从给定的方程组的一个近似值出发，构造某种算法迭代法：从给定的方程组的一个近似值出发，构造某种算法逐步将其准确化，一般不能在有限步内得到准确解。逐步

7、将其准确化，一般不能在有限步内得到准确解。逐步将其准确化，一般不能在有限步内得到准确解。逐步将其准确化，一般不能在有限步内得到准确解。这一章介绍计算机上常用的直接法，它们都是以这一章介绍计算机上常用的直接法，它们都是以Gauss消消元法为基本方法，即先将线性方程组化为等价的三角形方程元法为基本方法，即先将线性方程组化为等价的三角形方程组，然后求解。组，然后求解。第5页，共53页，编辑于2022年，星期二1Gauss消元法Gauss消元法是最基本的一种方法，下例说明其消元法是最基本的一种方法，下例说明其基本思想基本思想基本思想基本思想:例例1解线性方程组：解线性方程组：解线性方程组：解线性方程组

8、：解：消去解：消去x1，进行第一次消元：首先找乘数，以，进行第一次消元：首先找乘数，以-12乘第一个方程加到第二个方程，以乘第一个方程加到第二个方程，以18乘第一个方乘第一个方程加到第三个方程上可得同解方程组：程加到第三个方程上可得同解方程组：第6页，共53页，编辑于2022年，星期二例1（续）上述上述Gauss消元法的基本思想是：先逐次消去变量，将方程消元法的基本思想是：先逐次消去变量，将方程组化成同解的上三角形方程组，此过程称为消元过组化成同解的上三角形方程组，此过程称为消元过程。然后按方程相反顺序求解上三角形方程组，得到原程。然后按方程相反顺序求解上三角形方程组，得到原方程组的解，此过程

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

10、，从而得到求解组的消元公式和回代求解公式，从而得到求解组的消元公式和回代求解公式，从而得到求解n n阶线性方阶线性方阶线性方阶线性方程组的能顺利在计算机上实现的行之有效的算法。程组的能顺利在计算机上实现的行之有效的算法。第7页，共53页，编辑于2022年，星期二 为能更清楚地得到算法，下面以为能更清楚地得到算法，下面以4阶线性方程组为例总结求阶线性方程组为例总结求解步骤，并且很容易地可推广至一般的解步骤，并且很容易地可推广至一般的n n阶线性方程组。阶线性方程组。第8页，共53页，编辑于2022年，星期二 可以检查，分别以可以检查，分别以可以检查，分别以可以检查，分别以 li i1 1乘第一个

11、方程加到第乘第一个方程加到第乘第一个方程加到第乘第一个方程加到第i i个方程上可以完个方程上可以完成第一次消元，得同解方程组：成第一次消元，得同解方程组：变化以后的方程变化以后的方程组系数及右边的组系数及右边的常数项可总结出常数项可总结出如下的计算公式：如下的计算公式：完成第一次消元之后的完成第一次消元之后的方程组记为：方程组记为：A(2)x=b(2)第9页，共53页，编辑于2022年，星期二Gauss消元法的基本步骤3（4阶）以方程组中第以方程组中第以方程组中第以方程组中第i i个方程减去第二个方程乘个方程减去第二个方程乘li i2(i i=3,4)=3,4)，完，完，完，完成第二次消元。成

12、第二次消元。成第二次消元。成第二次消元。上标为上标为上标为上标为3 3的系数的系数的系数的系数和右端项可由和右端项可由下面公式计算：下面公式计算：第10页，共53页，编辑于2022年，星期二第三步第三步第三步第三步：消元（：消元（4阶方程组需进行阶方程组需进行3次消元）次消元）将上述将上述 A A(3)(3)X X=b(3)中最后一个方程中的中最后一个方程中的x x3消为零消为零消为零消为零：然后可回代求解：由于然后可回代求解：由于A A(4)为上三角形，所以可按变量的为上三角形，所以可按变量的为上三角形，所以可按变量的为上三角形，所以可按变量的逆序逐步回代求原方程组的解：逆序逐步回代求原方程

13、组的解：逆序逐步回代求原方程组的解：逆序逐步回代求原方程组的解：上述上述 消元、回代求解过程消元、回代求解过程很容易推广到一般的很容易推广到一般的很容易推广到一般的很容易推广到一般的n n阶线阶线性方程组。性方程组。经过上述消元步骤，经过上述消元步骤，经过上述消元步骤，经过上述消元步骤，得到同解的上三角形方得到同解的上三角形方得到同解的上三角形方得到同解的上三角形方程组：程组：程组：程组：A(4)x=b(4)第11页，共53页，编辑于2022年，星期二Gauss消元法的消元过程1、2（n阶）一般地，设一般地，设一般地，设一般地，设 n n阶方程组：阶方程组：阶方程组：阶方程组：消元过程为：消元

14、过程为：将上方程组中第将上方程组中第i个方程减去第个方程减去第2个方程乘以个方程乘以li2(i=3,n)，完成，完成第二步消元。第二步消元。第12页，共53页，编辑于2022年，星期二第第k 步：设第步：设第k 1步消元后得原方程组的同解方程组为：步消元后得原方程组的同解方程组为：第第k步消元后同步消元后同步消元后同步消元后同解方程组中上标解方程组中上标为为k+1的元素的的元素的计算公式见下屏计算公式见下屏第13页，共53页，编辑于2022年，星期二照此消元下去，完成照此消元下去，完成n 1次次消元后，可将原方程组化成消元后，可将原方程组化成同解的上三角形方程组如下：同解的上三角形方程组如下：

15、第14页，共53页，编辑于2022年，星期二Gauss消元法的回代过程（n阶）回代过程回代过程：逐步回代求得原方程组的解逐步回代求得原方程组的解 第15页，共53页，编辑于2022年，星期二Gauss消元法的计算量 由于在计算机中作乘除运算量所需时间远大于作加减运算由于在计算机中作乘除运算量所需时间远大于作加减运算所需时间，故只考虑作乘除运算量。所需时间，故只考虑作乘除运算量。由消元法步骤知，第由消元法步骤知，第由消元法步骤知，第由消元法步骤知，第k k次消元需作次消元需作n k k次除法，作次除法，作(n n k)(n n k+1)+1)次乘法，故消元过程中乘除法运算量为：次乘法，故消元过程

16、中乘除法运算量为：次乘法，故消元过程中乘除法运算量为：次乘法，故消元过程中乘除法运算量为：所以所以Gauss 消去法的消去法的乘除法总运算量为：乘除法总运算量为：乘除法总运算量为：乘除法总运算量为：第16页，共53页，编辑于2022年，星期二Gauss法与Cramer法则的计算量比较 Gauss Gauss 消元法的乘消元法的乘除法总运算量为除法总运算量为除法总运算量为除法总运算量为：与我们曾经介绍的与我们曾经介绍的CramerCramer法则的乘除法总运算量法则的乘除法总运算量 (n n2 2 1)n!+n 相比，由下表可知：当阶数越高时，相比，由下表可知：当阶数越高时，GaussGauss

17、消消消消元法所需乘除法次数比元法所需乘除法次数比Cramer法则要少得多：法则要少得多：法则要少得多：法则要少得多：方程组阶数方程组阶数方程组阶数方程组阶数3 3101020205050GaussGauss消元法运算量消元法运算量消元法运算量消元法运算量1717430430306030604415044150CramerCramer法则运算量法则运算量法则运算量法则运算量51513592512103592512109.7109.71020207.6107.6106767Gauss 消元法的优缺点：消元法的优缺点：但其计算过程中，要求但其计算过程中，要求a akk(k)（称为主元素）均不为零，因

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

19、单易行。第17页，共53页，编辑于2022年，星期二2主元素法 2.1 引入主元素的必要性引入主元素的必要性 对线性方程组对线性方程组AX=b，若其系数行列式，若其系数行列式 det(A)0，则该方程组有唯一，则该方程组有唯一 解，但是这一条件解，但是这一条件 不能保证所有主元素都不等于零，只要某一主元不能保证所有主元素都不等于零，只要某一主元素等于零，就不能用素等于零，就不能用Gauss消元法求解该方程组，消元法求解该方程组，即使所有主元素不等于零，但即使所有主元素不等于零，但 某一主元素的绝对某一主元素的绝对值很小时，值很小时，Gauss消元法也是不适用的。如下例：消元法也是不适用的。如下

20、例：例例2第18页，共53页，编辑于2022年，星期二例2（续1）解：为减小误差，计算过程中保留解：为减小误差，计算过程中保留3位有效数字。位有效数字。按按Gauss消元法步骤：消元法步骤：第一次消元后得同解方程组：第一次消元后得同解方程组：第一次消元后得同解方程组：第一次消元后得同解方程组：第二次消元后得同解方程组第二次消元后得同解方程组第二次消元后得同解方程组第二次消元后得同解方程组 回代得解，回代得解，x3=2.02，x2=2.40，x1=5.80。容易验证，方程组（容易验证，方程组（3-8）的准确解为：）的准确解为：x1=2.60，x2=1.00，x3=2.0。显然两种结果相差很大。显

21、然两种结果相差很大。第19页，共53页，编辑于2022年，星期二 若在解方程组前，先交换方程的次序，若在解方程组前，先交换方程的次序，如将（如将（2-8）交换一行与三行改写成如下所示：）交换一行与三行改写成如下所示：再用再用Gauss消元法，顺序消元后得同解方程组：消元法，顺序消元后得同解方程组：回代得解：回代得解：x3=2.00，x2=1.00，x1=2.60 与准确解相同。与准确解相同。例2（续2）第20页，共53页，编辑于2022年，星期二例2两种解法的误差分析 在例在例2中，对中，对(2-8)的方程进行顺序消元时，的方程进行顺序消元时，主元主元a(1)11=0.50，a(2)22=0.

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

23、对值大的元素作主元通过交换方程次序，选取绝对值大的元素作主元 基于这种思想而导出主元素法。基于这种思想而导出主元素法。第21页，共53页，编辑于2022年，星期二2.2列主元素法 为简便起见，对方为简便起见，对方 程组（程组（2-1），用），用 其增其增 广矩阵：广矩阵：表示，并直接在增广表示，并直接在增广矩阵上进行运算。矩阵上进行运算。列主元素法的具体步骤如下：列主元素法的具体步骤如下：第22页，共53页，编辑于2022年，星期二列主元素法如此经过如此经过如此经过如此经过n 1步，增广矩阵（步，增广矩阵（2-9）被化成上三角形，然后由）被化成上三角形，然后由回代过程求解。回代过程求解。在上述

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

25、的精度优于列主元法，这是由于全主元法是在全体元素中选主元，主元法，这是由于全主元法是在全体元素中选主元，故它对控制舍入误差十分有效。但是全主元法在计算故它对控制舍入误差十分有效。但是全主元法在计算过程中，需同时作行与列的互换，因而程序比较复杂过程中，需同时作行与列的互换，因而程序比较复杂,计算时间较长。列主元法的精度虽稍低于全主元法，计算时间较长。列主元法的精度虽稍低于全主元法，但其计算简单，工作量大为减少，且计算经验与理论但其计算简单，工作量大为减少，且计算经验与理论分析均表明，它与全主元法同样具有良好的数值稳定分析均表明，它与全主元法同样具有良好的数值稳定性，故列主元法是求解中小型稠密线性

26、方程组的最好性，故列主元法是求解中小型稠密线性方程组的最好方法之一。方法之一。方法之一。方法之一。第25页，共53页，编辑于2022年，星期二2.4解三对角方程组的追赶法在很多问题中，需要解如下形式的三对角方程组：在很多问题中，需要解如下形式的三对角方程组：在很多问题中，需要解如下形式的三对角方程组：在很多问题中，需要解如下形式的三对角方程组：三对角方程组的系数矩阵为三对角阵，对于这种特殊而又三对角方程组的系数矩阵为三对角阵，对于这种特殊而又三对角方程组的系数矩阵为三对角阵，对于这种特殊而又三对角方程组的系数矩阵为三对角阵，对于这种特殊而又简单的方程组，用前面介绍的方法求解由于有大量的零元素既

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

28、。第26页，共53页，编辑于2022年，星期二 首先进行顺序消元，首先进行顺序消元，首先进行顺序消元，首先进行顺序消元，且每步将主元系数且每步将主元系数且每步将主元系数且每步将主元系数化为化为化为化为1 1，将方程组化为：，将方程组化为：，将方程组化为：，将方程组化为：其中系数按下式计算其中系数按下式计算：然后回代然后回代然后回代然后回代求解，得：求解，得：求解，得：求解，得：上述追赶法能进行到底上述追赶法能进行到底上述追赶法能进行到底上述追赶法能进行到底 。第27页，共53页，编辑于2022年，星期二追赶法举例用追赶法解下用追赶法解下列三对角方程组：列三对角方程组：列三对角方程组：列三对角方

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

30、次数进行比较，量，按乘除法次数进行比较，量，按乘除法次数进行比较，Gauss消元法约为消元法约为n n3 3/3，全主元，全主元法为法为n n3/2/2，而追赶法仅为，而追赶法仅为，而追赶法仅为，而追赶法仅为5 5n-3次，可见追赶法是求解三对角方次，可见追赶法是求解三对角方程组的非常好的方法。程组的非常好的方法。第28页，共53页，编辑于2022年，星期二3矩阵分解法 如果用矩阵形式表示，如果用矩阵形式表示，GaussGauss消元法的消元过程是对方程消元法的消元过程是对方程消元法的消元过程是对方程消元法的消元过程是对方程组（组（组（组（2-12-1）的增广矩阵（）的增广矩阵（）的增广矩阵（

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

32、53页，编辑于2022年，星期二第二次消元第二次消元第二次消元第二次消元相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵：第第k k次消元次消元次消元次消元相当于用初等矩阵：相当于用初等矩阵：Gauss消元法的矩阵形式第30页，共53页，编辑于2022年，星期二经过经过经过经过n 1步消元后得到：步消元后得到：因为因为因为因为L Lk(k=1,2,n 1)均为非奇异阵，故它们均为非奇异阵，故它们的逆矩阵存在。容易求出：的逆矩阵存在。容易求出：的逆矩阵存在。容易求出：的逆矩阵存在。容易求出：这说明：在这说明：在 的条件下，消元过程的条件下，消元过程实际上是把系数矩阵实际上是

33、把系数矩阵A分解成单位下三角阵与上三角矩阵分解成单位下三角阵与上三角矩阵的乘积的过程。的乘积的过程。Gauss消元法的矩阵形式（续）第31页，共53页，编辑于2022年，星期二杜利特尔（Doolittle）分解LU分解 事实上，只要事实上，只要事实上，只要事实上，只要A A满足一定条件，由上述结论，它一定可以分解满足一定条件，由上述结论，它一定可以分解满足一定条件，由上述结论，它一定可以分解满足一定条件，由上述结论，它一定可以分解成两个三角形矩阵的乘积，即：成两个三角形矩阵的乘积，即：成两个三角形矩阵的乘积，即：成两个三角形矩阵的乘积，即：A=LU 。上述分解称为杜利特尔（上述分解称为杜利特尔

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

35、=y，因此，解线性方程，因此，解线性方程组问题可转化为矩阵的三角分解问题。组问题可转化为矩阵的三角分解问题。其中：其中：其中：其中：L L为单位下三角矩阵，为单位下三角矩阵，U为上三角矩阵：为上三角矩阵：第32页，共53页，编辑于2022年，星期二3.2矩阵的三角分解 正如正如正如正如GaussGauss消元法要在一定条件下才能进行到底一样，矩阵消元法要在一定条件下才能进行到底一样，矩阵消元法要在一定条件下才能进行到底一样，矩阵消元法要在一定条件下才能进行到底一样，矩阵A也必须满足一定条件才能进行三角分解。也必须满足一定条件才能进行三角分解。设设设设A为为为为n n阶方阵，若阶方阵，若阶方阵，

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

37、U LU 即：即：即：即：紧接下屏：紧接下屏：紧接下屏：紧接下屏：第33页，共53页，编辑于2022年，星期二对A进行LU分解ALU由矩阵乘法规则及比较（由矩阵乘法规则及比较（2-11）两端的元素，得：）两端的元素，得：即可由（即可由（即可由（即可由（2-122-12）求出）求出）求出）求出U U的第一行，的第一行，的第一行，的第一行，L的第一列。的第一列。下面讨论一般情况，即：下面讨论一般情况，即：下面讨论一般情况，即：下面讨论一般情况，即：U的第的第i i 行，行，L的第的第的第的第j j列：列：列：列：第34页，共53页，编辑于2022年，星期二一般情况下，可由：一般情况下，可由：对A进

38、行LU分解（r 行r 列）计算过程应按计算过程应按U U第第第第1 1行、行、行、行、L L第第第第1 1列列列列（第（第（第（第1 1框），框），框），框），U第第2行、行、L L第第第第2 2列（第列（第列（第列（第2 2框），框），框），框），的顺序的顺序的顺序的顺序 具体分解步骤具体分解步骤具体分解步骤具体分解步骤见下屏：见下屏：见下屏：见下屏：得到计算得到计算得到计算得到计算u uij ij和和和和 l lij 的公式：的公式：的公式：的公式：第35页，共53页，编辑于2022年，星期二对A进行LU分解的具体步骤1.计算计算U的第的第1行，行，L的第的第1列，亦称为计算列，亦称为计算

39、 第第1框；框；2.计算计算U的第的第r 行，行，L的第的第r 列（列（r=2,n），），即第即第r 框框：第36页，共53页，编辑于2022年，星期二矩阵A的LU分解举例解：按分解公式（解：按分解公式（2-13），），一框一框分解，每框计算时先行后列一框一框分解，每框计算时先行后列一框一框分解，每框计算时先行后列一框一框分解，每框计算时先行后列 ：所以：所以：例例5 第37页，共53页，编辑于2022年，星期二3.3直接三角分解法 若线性方程组若线性方程组Ax Ax=b b的系数矩阵的系数矩阵A完成三角分解，完成三角分解，A A=LU，那么解方，那么解方，那么解方，那么解方程组程组程组程组A

40、x=b b等价于求解两个三角形等价于求解两个三角形方程组方程组Ly Ly=b b，UxUx=y，即由：，即由：再由：再由：再由：再由：可解得：可解得：第38页，共53页，编辑于2022年，星期二直接三角分解法（续）容易看出，式（容易看出，式（2-14）与式（）与式（2-13）的运算规律相同，）的运算规律相同，或者由：或者由：或者由：或者由：第39页，共53页，编辑于2022年，星期二解线性方程组举例例例6解解：按表：按表：按表：按表2-32-3计算：计算：计算：计算：第40页，共53页，编辑于2022年，星期二第41页，共53页，编辑于2022年，星期二三角分解法的几点说明1 1、用三角分解法

41、求线性方程的乘除法运算量也是、用三角分解法求线性方程的乘除法运算量也是、用三角分解法求线性方程的乘除法运算量也是、用三角分解法求线性方程的乘除法运算量也是n n3/3 数量级。由于在求出数量级。由于在求出uij,lij和和和和y yi i后，后，后，后，aij和和和和bi i无需保留，无需保留，故上机计算时，可把故上机计算时，可把故上机计算时，可把故上机计算时，可把L L，U和和y存在存在存在存在A A，b所占的单元，所占的单元，回回代时代时x x取代取代取代取代y y，整个计算过程中不需要增加新的存，整个计算过程中不需要增加新的存，整个计算过程中不需要增加新的存，整个计算过程中不需要增加新的

42、存 贮单元。贮单元。贮单元。贮单元。3、完成、完成A=LUA=LU分解后可以较容易地求出行列式分解后可以较容易地求出行列式|A|的值：的值：的值：的值：2 2、从三角分解法的推导及例中可以看出，系数矩阵的、从三角分解法的推导及例中可以看出，系数矩阵的、从三角分解法的推导及例中可以看出，系数矩阵的、从三角分解法的推导及例中可以看出，系数矩阵的 三三三三 角分解与右端项无关。因角分解与右端项无关。因角分解与右端项无关。因角分解与右端项无关。因 而在计算多个系数矩阵而在计算多个系数矩阵而在计算多个系数矩阵而在计算多个系数矩阵 为为为为A A而右端不同的线性方程组系时，用三角分解法更而右端不同的线性方

43、程组系时，用三角分解法更 为为为为 简便（如可用于求逆矩阵）。简便（如可用于求逆矩阵）。简便（如可用于求逆矩阵）。简便（如可用于求逆矩阵）。第42页，共53页，编辑于2022年，星期二三角分解法的几点说明（续）6、分解法的优点除上述、分解法的优点除上述2、3外，还有：外，还有：a.可求解可求解可求解可求解A2z=b b,因为算因为算A A2 2计算量大，可用计算量大，可用 b b.可根据可根据A的形状设计算法，当的形状设计算法，当A为大型稀疏，且非零为大型稀疏，且非零为大型稀疏，且非零为大型稀疏，且非零元素有规律如带状，三对角等，作分解时能充分利用元素有规律如带状，三对角等，作分解时能充分利用

44、元素有规律如带状，三对角等，作分解时能充分利用元素有规律如带状，三对角等，作分解时能充分利用A A的的的的特点，特点，L，U U能保持能保持A A的原状，即的原状，即L与与与与A A的下三角相同，的下三角相同，U U与与与与A的上三角形状相同。的上三角形状相同。的上三角形状相同。的上三角形状相同。4 4、三角分解法一般也可采用选主元的技术，以使算法更、三角分解法一般也可采用选主元的技术，以使算法更、三角分解法一般也可采用选主元的技术，以使算法更、三角分解法一般也可采用选主元的技术，以使算法更 具数值稳定性。具数值稳定性。5 5、也可以把矩阵、也可以把矩阵、也可以把矩阵、也可以把矩阵A分解成一个

45、下三角矩阵与一个单位上三分解成一个下三角矩阵与一个单位上三分解成一个下三角矩阵与一个单位上三分解成一个下三角矩阵与一个单位上三 角矩角矩角矩角矩阵的乘积，矩阵的阵的乘积，矩阵的阵的乘积，矩阵的阵的乘积，矩阵的 这种分解称为克劳特（这种分解称为克劳特（这种分解称为克劳特（这种分解称为克劳特（Crout）分解。分解。分解。分解。第43页，共53页，编辑于2022年，星期二解线性方程组举例例：下述矩阵能否分解为例：下述矩阵能否分解为例：下述矩阵能否分解为例：下述矩阵能否分解为LULU（其中（其中（其中（其中L L为单位下三角阵，为单位下三角阵，为单位下三角阵，为单位下三角阵，U U为为为为上三角阵）

46、？若能分解，那么分解是否惟一？上三角阵）？若能分解，那么分解是否惟一？上三角阵）？若能分解，那么分解是否惟一？上三角阵）？若能分解，那么分解是否惟一？第44页，共53页，编辑于2022年，星期二4平方根法与改进的平方根法对称正定矩阵概念：对称正定矩阵概念：工程实际问题的计算中，线性方程组的系数矩阵常工程实际问题的计算中，线性方程组的系数矩阵常工程实际问题的计算中，线性方程组的系数矩阵常工程实际问题的计算中，线性方程组的系数矩阵常常具有对称正定性，即其各阶顺序主子式及全部特征值均常具有对称正定性，即其各阶顺序主子式及全部特征值均常具有对称正定性，即其各阶顺序主子式及全部特征值均常具有对称正定性，

47、即其各阶顺序主子式及全部特征值均大于零。矩阵的这一特性使它的三角分解也有更简单的形大于零。矩阵的这一特性使它的三角分解也有更简单的形式，从而导出一些特殊的解法。式，从而导出一些特殊的解法。5.A A的所有顺序主子式均为正数，的所有顺序主子式均为正数，的所有顺序主子式均为正数，的所有顺序主子式均为正数，即即即即det(A Ak k)0,)0,k=1,2,n)。4.A A的所有特征值的所有特征值的所有特征值的所有特征值00；3.A A的对角线元素的对角线元素的对角线元素的对角线元素a aii ii0(i i=1,2,n)；2.2.A A是非奇异阵，且是非奇异阵，且是非奇异阵，且是非奇异阵，且A 1

48、 1也是对称正定阵；也是对称正定阵；也是对称正定阵；也是对称正定阵；1.1.A A的所有顺序主子矩阵的所有顺序主子矩阵的所有顺序主子矩阵的所有顺序主子矩阵A Ak k(k k=1,2,n n)也是对称正定阵；也是对称正定阵；若若A为对称正定矩阵，则：为对称正定矩阵，则：为对称正定矩阵，则：为对称正定矩阵，则：第45页，共53页，编辑于2022年，星期二4.1平方根法定理定理 2.2若若A是对称正定矩阵，则存在唯一的单位下三是对称正定矩阵，则存在唯一的单位下三角矩阵角矩阵L和对角阵：和对角阵：证明：证明：首先首先A可直接作可直接作LU分解，记为分解，记为A=LU1 ，其中：其中：第46页，共53

49、页，编辑于2022年，星期二定理2.2（续）其中其中U U0 0是单位上三角阵，则由是单位上三角阵，则由A A的对称性可得：的对称性可得：再由唯一性得再由唯一性得U U0 0=L LT T，所以，所以A=LDLT T，并且这种分解是唯，并且这种分解是唯，并且这种分解是唯，并且这种分解是唯一的，又由于一的，又由于一的，又由于一的，又由于U U1的对角线元素的对角线元素的对角线元素的对角线元素U Ukkkk就是就是GaussGauss消元法的主元素：消元法的主元素：消元法的主元素：消元法的主元素：由于由于LD1/2是下三角阵，因此有推论：是下三角阵，因此有推论：第47页，共53页，编辑于2022年

50、，星期二Choleskg分解1推推论论 若若若若A A是对称正定矩阵，则存在唯一的主对角线元素都为正是对称正定矩阵，则存在唯一的主对角线元素都为正是对称正定矩阵，则存在唯一的主对角线元素都为正是对称正定矩阵，则存在唯一的主对角线元素都为正的下三角阵的下三角阵的下三角阵的下三角阵L，使得：，使得：A=LLT矩阵的这种分解称为矩阵的这种分解称为Choleskg分解。分解。用比较法可以导出用比较法可以导出用比较法可以导出用比较法可以导出L L的计算公式。设：的计算公式。设：的计算公式。设：的计算公式。设：比较比较比较比较A与与LLT的相应元素，的相应元素，的相应元素，的相应元素，即由即由A=LLT