分析02-线性方程组直接解法.ppt

《分析02-线性方程组直接解法.ppt》由会员分享，可在线阅读，更多相关《分析02-线性方程组直接解法.ppt（96页珍藏版）》请在金锄头文库上搜索。

1、WY第二第二 章章线性方程组线性方程组直接解法直接解法2-1第二章 线性方程组直接解法WY第二章第二章目录目录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

2、 GaussGauss消去法的矩阵形式消去法的矩阵形式消去法的矩阵形式消去法的矩阵形式 3.2 3.2 矩阵的三角分解矩阵的三角分解矩阵的三角分解矩阵的三角分解 3.3 3.3 直接三角分解法直接三角分解法直接三角分解法直接三角分解法4. 4. 平方根法与改进的平方根法平方根法与改进的平方根法平方根法与改进的平方根法平方根法与改进的平方根法5. 5. 矩阵求逆矩阵求逆矩阵求逆矩阵求逆6.方程组的性态和条件数方程组的性态和条件数2第二章 线性方程组直接解法WY线性方程组的概念线性方程组的概念 在科学研究和工程技术中所提出的计算问题中，线性在科学研究和工程技术中所提出的计算问题中，线性在科学研究和

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

4、组问题，因此，线性方程组的解法，都包含了解线性方程组问题，因此，线性方程组的解法在数值计算中占有较重要的地位。在数值计算中占有较重要的地位。在数值计算中占有较重要的地位。在数值计算中占有较重要的地位。 设设设设n n阶线性方程组：阶线性方程组：阶线性方程组：阶线性方程组： 其矩阵形式为：其矩阵形式为：其矩阵形式为：其矩阵形式为：Ax=b (2-2)其中：其中：其中：其中：3第二章 线性方程组直接解法WY 求解求解Ax = b，曾经学曾经学过高斯（过高斯（Gauss）消元法消元法，克莱姆（克莱姆（Cramer）法则法则，矩阵变换法矩阵变换法等，但已远等，但已远远满足不了实际运算的需要，主要体现两

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

6、det(A) 0，则该方程组有唯一解。则该方程组有唯一解。4第二章 线性方程组直接解法WY线性方程组的数值解法线性方程组的数值解法解线性方程组的数值方法大致分为两类：解线性方程组的数值方法大致分为两类：解线性方程组的数值方法大致分为两类：解线性方程组的数值方法大致分为两类： 请注意：请注意：请注意：请注意：由于在计算中某些数据实际上只能用有限位小由于在计算中某些数据实际上只能用有限位小由于在计算中某些数据实际上只能用有限位小由于在计算中某些数据实际上只能用有限位小 数，即不可避免地存在着舍入误差的影响，因数，即不可避免地存在着舍入误差的影响，因数，即不可避免地存在着舍入误差的影响，因数，即不可

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

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

9、一般不能在有限步内得到准确解。种算法逐步将其准确化，一般不能在有限步内得到准确解。 这一章介绍计算机上常用的直接法，它们都是以这一章介绍计算机上常用的直接法，它们都是以这一章介绍计算机上常用的直接法，它们都是以这一章介绍计算机上常用的直接法，它们都是以GaussGauss消元法为基本方法，即先将线性方程组化为等价的三角形消元法为基本方法，即先将线性方程组化为等价的三角形消元法为基本方法，即先将线性方程组化为等价的三角形消元法为基本方法，即先将线性方程组化为等价的三角形方程组，然后求解。方程组，然后求解。方程组，然后求解。方程组，然后求解。5第二章 线性方程组直接解法WY1 Gauss消元法消元

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

11、s消元法的基本思想是：先逐次消去变量，将消元法的基本思想是：先逐次消去变量，将消元法的基本思想是：先逐次消去变量，将消元法的基本思想是：先逐次消去变量，将方程组化成同解的上三角形方程组，此过程称为方程组化成同解的上三角形方程组，此过程称为方程组化成同解的上三角形方程组，此过程称为方程组化成同解的上三角形方程组，此过程称为消元过消元过消元过消元过程程程程。然后按方程相反顺序求解上三角形方程组，得到原。然后按方程相反顺序求解上三角形方程组，得到原。然后按方程相反顺序求解上三角形方程组，得到原。然后按方程相反顺序求解上三角形方程组，得到原方程组的解，此过程称为方程组的解，此过程称为方程组的解，此过程

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

13、元公式和回代求解公式，从而得到求解组的消元公式和回代求解公式，从而得到求解组的消元公式和回代求解公式，从而得到求解n n阶线性方阶线性方阶线性方阶线性方程组的能顺利在计算机上实现的行之有效的算法。程组的能顺利在计算机上实现的行之有效的算法。程组的能顺利在计算机上实现的行之有效的算法。程组的能顺利在计算机上实现的行之有效的算法。 7第二章 线性方程组直接解法WYGauss消元法的基本步骤消元法的基本步骤1（4 4阶）阶）阶）阶） 为能更清楚地得到算法，下面以为能更清楚地得到算法，下面以为能更清楚地得到算法，下面以为能更清楚地得到算法，下面以4 4阶线性方程组为例总结阶线性方程组为例总结阶线性方程

14、组为例总结阶线性方程组为例总结求解步骤，并且很容易地可推广至一般的求解步骤，并且很容易地可推广至一般的求解步骤，并且很容易地可推广至一般的求解步骤，并且很容易地可推广至一般的n n阶线性方程组。阶线性方程组。阶线性方程组。阶线性方程组。8第二章 线性方程组直接解法WY 可以检查，分别以可以检查，分别以可以检查，分别以可以检查，分别以 l li i1 1乘第一个方程加到第乘第一个方程加到第乘第一个方程加到第乘第一个方程加到第i i个方程上个方程上个方程上个方程上可以完成第一次消元，得同解方程组：可以完成第一次消元，得同解方程组：可以完成第一次消元，得同解方程组：可以完成第一次消元，得同解方程组：

15、变化以后的方变化以后的方变化以后的方变化以后的方程组系数及右程组系数及右程组系数及右程组系数及右边的常数项可边的常数项可边的常数项可边的常数项可总结出如下的总结出如下的总结出如下的总结出如下的计算公式：计算公式：计算公式：计算公式： 完成第一次消元之后的完成第一次消元之后的完成第一次消元之后的完成第一次消元之后的方程组记为：方程组记为：方程组记为：方程组记为： A(2) x = b (2) Gauss消元法的基本步骤消元法的基本步骤2（4 4阶）阶）阶）阶）9第二章 线性方程组直接解法WYGauss消元法的基本步骤消元法的基本步骤3（4 4阶）阶）阶）阶） 以方程组中第以方程组中第以方程组中第

16、以方程组中第i i个方程减去第二个方程乘个方程减去第二个方程乘个方程减去第二个方程乘个方程减去第二个方程乘l li i2 2 ( (i i = 3,4)= 3,4)，完完完完成第二次消元。成第二次消元。成第二次消元。成第二次消元。 上标为上标为上标为上标为3 3的系数的系数的系数的系数和右端项可由和右端项可由和右端项可由和右端项可由下面公式计算：下面公式计算：下面公式计算：下面公式计算：10第二章 线性方程组直接解法WYGauss消元法的基本步骤消元法的基本步骤4（4 4阶）阶）阶）阶）第三步第三步第三步第三步：消元消元消元消元（4 4阶方程组需进行阶方程组需进行阶方程组需进行阶方程组需进行3

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

18、回代求解过程求解过程求解过程求解过程很容易推广到一般的很容易推广到一般的很容易推广到一般的很容易推广到一般的n n阶线阶线阶线阶线性方程组。性方程组。性方程组。性方程组。 经过上述消元步骤，经过上述消元步骤，经过上述消元步骤，经过上述消元步骤，得到同解的上三角形得到同解的上三角形得到同解的上三角形得到同解的上三角形方程组：方程组：方程组：方程组：A (4) x = b(4) 11第二章 线性方程组直接解法WYGauss消元法的消元过程消元法的消元过程1、2（n n阶）阶）阶）阶）一般地，设一般地，设一般地，设一般地，设 n n阶方程组：阶方程组：阶方程组：阶方程组：消元过程为：消元过程为：消元

19、过程为：消元过程为： 将上方程组中第将上方程组中第将上方程组中第将上方程组中第i i个方程减去第个方程减去第个方程减去第个方程减去第2 2个方程乘以个方程乘以个方程乘以个方程乘以l li i2 2 ( (i i=3,=3,n n) )，完成完成完成完成第二步第二步第二步第二步消元。消元。消元。消元。 12第二章 线性方程组直接解法WYGauss消元法的消元过程消元法的消元过程3（n n阶）阶）阶）阶）第第第第k k 步步步步：设第：设第：设第：设第k k 1 1步消元后得原方程组的同解方程组为：步消元后得原方程组的同解方程组为：步消元后得原方程组的同解方程组为：步消元后得原方程组的同解方程组为

20、： 第第第第k k步消元后同步消元后同步消元后同步消元后同解方程组中上标解方程组中上标解方程组中上标解方程组中上标为为为为k k+1+1的元素的的元素的的元素的的元素的计算公式见下屏计算公式见下屏计算公式见下屏计算公式见下屏13第二章 线性方程组直接解法WY照此消元下去，完成照此消元下去，完成n 1次次消元后，可将原方程组化成消元后，可将原方程组化成同解的上三角形方程组如下：同解的上三角形方程组如下： Gauss消元法的消元过程消元法的消元过程3（n n阶）阶）阶）阶）14第二章 线性方程组直接解法WYGauss消元法的回代过程消元法的回代过程（n n阶）阶）阶）阶）回代过程回代过程：逐步回代

21、求得原方程组的解逐步回代求得原方程组的解 15第二章 线性方程组直接解法WYGauss消元法的计算量消元法的计算量 由于在计算机中作乘除运算量所需时间远大于作加减由于在计算机中作乘除运算量所需时间远大于作加减由于在计算机中作乘除运算量所需时间远大于作加减由于在计算机中作乘除运算量所需时间远大于作加减运算所需时间，故只考虑作乘除运算量。运算所需时间，故只考虑作乘除运算量。运算所需时间，故只考虑作乘除运算量。运算所需时间，故只考虑作乘除运算量。 由消元法步骤知，第由消元法步骤知，第由消元法步骤知，第由消元法步骤知，第k k次消元需作次消元需作次消元需作次消元需作n n k k次除法，作次除法，作次

22、除法，作次除法，作( (n n k k)( )(n n k k + 1)+ 1)次乘法，故消元过程中乘除法运算量为：次乘法，故消元过程中乘除法运算量为：次乘法，故消元过程中乘除法运算量为：次乘法，故消元过程中乘除法运算量为： 所以所以所以所以GaussGauss 消去法的消去法的消去法的消去法的乘除法乘除法乘除法乘除法总运算量总运算量总运算量总运算量为：为：为：为： 16第二章 线性方程组直接解法WYGauss法与法与Cramer法则的计算量比较法则的计算量比较 GaussGauss 消元法的乘消元法的乘消元法的乘消元法的乘除法总运算量为除法总运算量为除法总运算量为除法总运算量为： 与我们曾经

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

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

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

26、果。甚至导出错误的结果。甚至导出错误的结果。 GaussGauss消元法简单易行。消元法简单易行。消元法简单易行。消元法简单易行。17第二章 线性方程组直接解法WY2 主元素法主元素法 2.1 引入主元素的必要性引入主元素的必要性 对线性方程组对线性方程组AX = b，若其系数行列式若其系数行列式 det(A) 0，则该方程组有唯一则该方程组有唯一 解，但是这一条件解，但是这一条件 不能保证所有主元素都不等于零，只要某一主元不能保证所有主元素都不等于零，只要某一主元素等于零，就不能用素等于零，就不能用Gauss消元法求解该方程组，消元法求解该方程组，即使所有主元素不等于零，但即使所有主元素不等

27、于零，但 某一主元素的绝对某一主元素的绝对值很小时，值很小时，Gauss消元法也是不适用的。如下例：消元法也是不适用的。如下例： 例例218第二章 线性方程组直接解法WY例例2（续（续1） 解：解：为减小误差，计算过程中保留为减小误差，计算过程中保留3位有效数字。位有效数字。 按按Gauss消元法步骤：消元法步骤： 第一次消元后得同解方程组：第一次消元后得同解方程组：第一次消元后得同解方程组：第一次消元后得同解方程组： 第二次消元后得同解方程组第二次消元后得同解方程组第二次消元后得同解方程组第二次消元后得同解方程组 回代得解，回代得解，x3 = 2.02，x2 = 2.40，x1 = 5.80

28、。 容易验证，方程组（容易验证，方程组（3-8）的准确解为：）的准确解为： x1 = 2.60， x2 = 1.00，x3 = 2.0。显然两种结果相差很大。显然两种结果相差很大。19第二章 线性方程组直接解法WY 若在解方程组前，先交换方程的次序，若在解方程组前，先交换方程的次序，如将（如将（2-8）交换一行与二行改写成如下所示：）交换一行与二行改写成如下所示： 再用再用Gauss消元法，顺序消元后得同解方程组：消元法，顺序消元后得同解方程组：回代得解：回代得解：x3 = 2.00，x2 = 1.00，x1 = 2.60 与准确解相同。与准确解相同。 例例2（续（续2）20第二章 线性方程组

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

30、果。 为了在计算过程中，抑制舍入误差的增长，为了在计算过程中，抑制舍入误差的增长， 应尽量避免小主元的出现。如例应尽量避免小主元的出现。如例2的第二种解法的第二种解法, 通过交换方程次序，选取绝对值大的元素作主元通过交换方程次序，选取绝对值大的元素作主元 基于这种思想而导出主元素法。基于这种思想而导出主元素法。 21第二章 线性方程组直接解法WY2.2 列主元素法列主元素法 为简便起见，对方为简便起见，对方 程组（程组（2-1），用），用 其增其增 广矩阵：广矩阵： 表示，并直接在增广表示，并直接在增广矩阵上进行运算。矩阵上进行运算。 列主元素法的具体步骤如下：列主元素法的具体步骤如下： 22

31、第二章 线性方程组直接解法WY列主元素法列主元素法如此经过如此经过如此经过如此经过n n 1 1步，增广矩阵（步，增广矩阵（步，增广矩阵（步，增广矩阵（2-92-9）被化成上三角形，然）被化成上三角形，然）被化成上三角形，然）被化成上三角形，然后由回代过程求解。后由回代过程求解。后由回代过程求解。后由回代过程求解。 在上述过程中，在上述过程中，在上述过程中，在上述过程中，主元是按列选取的，故称为主元是按列选取的，故称为主元是按列选取的，故称为主元是按列选取的，故称为列主元法列主元法列主元法列主元法。例例例例2 2中的第二种解法就是按列主元法进行的。中的第二种解法就是按列主元法进行的。中的第二种

32、解法就是按列主元法进行的。中的第二种解法就是按列主元法进行的。 23第二章 线性方程组直接解法WY2.3 全主元素法全主元素法 经过经过n k次消元后，得到与方程组（次消元后，得到与方程组（2-1）同解的）同解的上三角形方程组，再由回代过程求解。上三角形方程组，再由回代过程求解。 24第二章 线性方程组直接解法WY主元素法举例主元素法举例例例6计算过程保留三位小数。 此例的计算结果表明，全主元素法的精度优于列此例的计算结果表明，全主元素法的精度优于列此例的计算结果表明，全主元素法的精度优于列此例的计算结果表明，全主元素法的精度优于列主元法，这是由于全主元法是在全体元素中选主元，主元法，这是由于

33、全主元法是在全体元素中选主元，主元法，这是由于全主元法是在全体元素中选主元，主元法，这是由于全主元法是在全体元素中选主元，故它对控制舍入误差十分有效。但是全主元法在计算故它对控制舍入误差十分有效。但是全主元法在计算故它对控制舍入误差十分有效。但是全主元法在计算故它对控制舍入误差十分有效。但是全主元法在计算过程中，需同时作行与列的互换，因而程序比较复杂过程中，需同时作行与列的互换，因而程序比较复杂过程中，需同时作行与列的互换，因而程序比较复杂过程中，需同时作行与列的互换，因而程序比较复杂, ,计算时间较长。列主元法的精度虽稍低于全主元法，计算时间较长。列主元法的精度虽稍低于全主元法，计算时间较长

34、。列主元法的精度虽稍低于全主元法，计算时间较长。列主元法的精度虽稍低于全主元法，但其计算简单，工作量大为减少，且计算经验与理论但其计算简单，工作量大为减少，且计算经验与理论但其计算简单，工作量大为减少，且计算经验与理论但其计算简单，工作量大为减少，且计算经验与理论分析均表明，它与全主元法同样具有良好的数值稳定分析均表明，它与全主元法同样具有良好的数值稳定分析均表明，它与全主元法同样具有良好的数值稳定分析均表明，它与全主元法同样具有良好的数值稳定性，故列主元法是求解中小型稠密线性方程组的最好性，故列主元法是求解中小型稠密线性方程组的最好性，故列主元法是求解中小型稠密线性方程组的最好性，故列主元法

35、是求解中小型稠密线性方程组的最好方法之一。方法之一。方法之一。方法之一。 方法之一。方法之一。方法之一。方法之一。 25第二章 线性方程组直接解法WY2.4 解三对角方程组的追赶法解三对角方程组的追赶法 在很多问题中，需要解如下形式的三对角方程组：在很多问题中，需要解如下形式的三对角方程组：在很多问题中，需要解如下形式的三对角方程组：在很多问题中，需要解如下形式的三对角方程组： 三对角方程组的系数矩阵为三对角阵，对于这种特殊三对角方程组的系数矩阵为三对角阵，对于这种特殊三对角方程组的系数矩阵为三对角阵，对于这种特殊三对角方程组的系数矩阵为三对角阵，对于这种特殊而又简单的方程组，用前面介绍的方法

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

37、的算法追赶法追赶法追赶法追赶法。 26第二章 线性方程组直接解法WY追赶法的解题步骤追赶法的解题步骤 首先首先首先首先进行顺序消元，进行顺序消元，进行顺序消元，进行顺序消元，且每步将主元系数且每步将主元系数且每步将主元系数且每步将主元系数化为化为化为化为1 1，将方程组化为：，将方程组化为：，将方程组化为：，将方程组化为：其中系数按下式计算其中系数按下式计算其中系数按下式计算其中系数按下式计算 ：然后然后然后然后回代回代回代回代求解，得：求解，得：求解，得：求解，得： 上述追赶法能进行到底上述追赶法能进行到底上述追赶法能进行到底上述追赶法能进行到底 。27第二章 线性方程组直接解法WY追赶法举

38、例追赶法举例用追赶法解下用追赶法解下用追赶法解下用追赶法解下列三对角方程组：列三对角方程组：列三对角方程组：列三对角方程组： 例例4解：解：解：解： 首先首先首先首先将方程组化为（将方程组化为（将方程组化为（将方程组化为（先追先追先追先追）：）：）：）： 然后然后回代（赶）求解：回代（赶）求解： x5 = 0，x4 = 30/7， x3 = 6/7，x2 = 12/7， x1 = 0 可以看出，追赶法本质上还可以看出，追赶法本质上还可以看出，追赶法本质上还可以看出，追赶法本质上还是顺序消元法，但由于计算过程是顺序消元法，但由于计算过程是顺序消元法，但由于计算过程是顺序消元法，但由于计算过程中只

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

40、程组的非常好的方法。法是求解三对角方程组的非常好的方法。法是求解三对角方程组的非常好的方法。法是求解三对角方程组的非常好的方法。 28第二章 线性方程组直接解法WY3 矩阵分解法矩阵分解法 如果用矩阵形式表示，如果用矩阵形式表示，如果用矩阵形式表示，如果用矩阵形式表示，GaussGauss消元法的消元过程是对消元法的消元过程是对消元法的消元过程是对消元法的消元过程是对方程组（方程组（方程组（方程组（2-12-1）的增广矩阵（）的增广矩阵（）的增广矩阵（）的增广矩阵（A A、b b）进行一系列的初等行进行一系列的初等行进行一系列的初等行进行一系列的初等行变换，将系数矩阵变换，将系数矩阵变换，将系

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

42、ssGauss消元法的消元法的消元法的消元法的 第一次消元第一次消元第一次消元第一次消元相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵：29第二章 线性方程组直接解法WY第二次消元第二次消元第二次消元第二次消元相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵： 第第第第k k次消元次消元次消元次消元相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵：相当于用初等矩阵： Gauss消元法的矩阵形式消元法的矩阵形式30第二章 线性方程组直接解法WY经过经过经过经过n n 1 1步消元后得到：步消元后得到：步消元后得到：步消元后得到： 因为因为因为因为

43、L Lk k ( (k k = 1,2, = 1,2, n n 1)1)均为非奇异阵，故它们均为非奇异阵，故它们均为非奇异阵，故它们均为非奇异阵，故它们的逆矩阵存在。的逆矩阵存在。的逆矩阵存在。的逆矩阵存在。容易求出：容易求出：容易求出：容易求出： 这说明：这说明：这说明：这说明：在在在在 的条件下，消元过程的条件下，消元过程的条件下，消元过程的条件下，消元过程实际上是把系数矩阵实际上是把系数矩阵实际上是把系数矩阵实际上是把系数矩阵A A分解成单位下三角阵与上三角矩阵分解成单位下三角阵与上三角矩阵分解成单位下三角阵与上三角矩阵分解成单位下三角阵与上三角矩阵的乘积的过程。的乘积的过程。的乘积的过

44、程。的乘积的过程。 Gauss消元法的矩阵形式（续）消元法的矩阵形式（续）31第二章 线性方程组直接解法WY杜利特尔（杜利特尔（Doolittle）分解分解LULU分解分解分解分解 事实上，只要事实上，只要事实上，只要事实上，只要A A非奇异，由上述结论，它一定可以分非奇异，由上述结论，它一定可以分非奇异，由上述结论，它一定可以分非奇异，由上述结论，它一定可以分解成两个三角形矩阵的乘积，即：解成两个三角形矩阵的乘积，即：解成两个三角形矩阵的乘积，即：解成两个三角形矩阵的乘积，即：A=A=L LU U 。 上述分解称为上述分解称为上述分解称为上述分解称为杜利特尔（杜利特尔（杜利特尔（杜利特尔（D

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

46、方程组回代过程则是求解另一个三角形方程组U Ux x = = y y，因此，因此，因此，因此，解线性方程组问题可转化为矩阵的三角分解问题。解线性方程组问题可转化为矩阵的三角分解问题。解线性方程组问题可转化为矩阵的三角分解问题。解线性方程组问题可转化为矩阵的三角分解问题。 其中：其中：其中：其中：L L为单位下三角矩阵，为单位下三角矩阵，为单位下三角矩阵，为单位下三角矩阵，U U为上三角矩阵：为上三角矩阵：为上三角矩阵：为上三角矩阵：32第二章 线性方程组直接解法WY3.2 矩阵的三角分解矩阵的三角分解 正如正如正如正如GaussGauss消元法要在一定条件下才能进行到底一样，消元法要在一定条件

47、下才能进行到底一样，消元法要在一定条件下才能进行到底一样，消元法要在一定条件下才能进行到底一样，矩阵矩阵矩阵矩阵A A也必须满足一定条件才能进行三角分解。也必须满足一定条件才能进行三角分解。也必须满足一定条件才能进行三角分解。也必须满足一定条件才能进行三角分解。 设设设设A A为为为为n n阶方阵，若阶方阵，若阶方阵，若阶方阵，若A A的顺序主子式的顺序主子式的顺序主子式的顺序主子式A Ai i( (i i = 1,2,= 1,2,n n 1) 1)均不为零均不为零均不为零均不为零, ,则矩阵则矩阵则矩阵则矩阵A A存在唯一的存在唯一的存在唯一的存在唯一的DoolittleDoolittle分

48、解。分解。分解。分解。 定理定理2.1存在性证明存在性证明存在性证明存在性证明唯一性证明唯一性证明唯一性证明唯一性证明下面讨论如何对下面讨论如何对下面讨论如何对下面讨论如何对A A进行进行进行进行LULU分解分解分解分解： （1 1行行行行1 1列列列列） 由于两个矩阵相等就是它们的对应元素都相等，因此由于两个矩阵相等就是它们的对应元素都相等，因此由于两个矩阵相等就是它们的对应元素都相等，因此由于两个矩阵相等就是它们的对应元素都相等，因此通过比较通过比较通过比较通过比较A A与与与与LULU的对应元素，即可得到直接计算的对应元素，即可得到直接计算的对应元素，即可得到直接计算的对应元素，即可得到

49、直接计算L L、U U的的的的元素的公式：元素的公式：元素的公式：元素的公式：A A= =LU LU 即：即：即：即： 紧接下屏：紧接下屏：紧接下屏：紧接下屏：33第二章 线性方程组直接解法WY对对A进行进行LU分解分解ALU由矩阵乘法规则及比较（由矩阵乘法规则及比较（由矩阵乘法规则及比较（由矩阵乘法规则及比较（2-112-11）两端的元素，得：）两端的元素，得：）两端的元素，得：）两端的元素，得：即可由（即可由（即可由（即可由（2-122-12）求出）求出）求出）求出U U的第一行，的第一行，的第一行，的第一行，L L的第一列。的第一列。的第一列。的第一列。 下面讨论一般情况，即：下面讨论一

50、般情况，即：下面讨论一般情况，即：下面讨论一般情况，即：U U的第的第的第的第i i 行，行，行，行，L L的第的第的第的第j j列：列：列：列：34第二章 线性方程组直接解法WY一般情况下，可由：一般情况下，可由：一般情况下，可由：一般情况下，可由：对对A进行进行LU分解分解 （r r 行行行行r r 列）列）列）列）计算过程应按计算过程应按计算过程应按计算过程应按U U第第第第1 1行、行、行、行、L L第第第第1 1列列列列（第（第（第（第1 1框），框），框），框），U U第第第第2 2行、行、行、行、L L第第第第2 2列列列列（第（第（第（第2 2框），框），框），框），的顺序的顺

51、序的顺序的顺序 具体分解步具体分解步具体分解步具体分解步骤见下屏：骤见下屏：骤见下屏：骤见下屏： 得到计算得到计算得到计算得到计算u uij ij和和和和 l lij ij 的公式：的公式：的公式：的公式： 35第二章 线性方程组直接解法WY对对A进行进行LU分解的具体步骤分解的具体步骤1. 计算计算U的第的第1行，行，L的第的第1列，亦称为计算列，亦称为计算 第第1框；框； 2. 计算计算U的第的第r 行，行，L的第的第r 列（列（r =2,n），）， 即第即第r 框框 ：36第二章 线性方程组直接解法WY矩阵矩阵A的的LU分解举例分解举例解：解：解：解：按分解公式（按分解公式（按分解公式（

52、按分解公式（2-132-13），），），），一框一框分解，每框计算时先行后列一框一框分解，每框计算时先行后列一框一框分解，每框计算时先行后列一框一框分解，每框计算时先行后列 ：所以：所以：所以：所以：例例例例5 5 37第二章 线性方程组直接解法WY三角分解的紧凑格式三角分解的紧凑格式 根据式（根据式（2-13）的特点，矩阵的三角分解可按）的特点，矩阵的三角分解可按以下格式及顺序进行。这种格式既便于记忆，又便以下格式及顺序进行。这种格式既便于记忆，又便于计算，称为于计算，称为紧凑格式紧凑格式。见下表。见下表2-1： 表表表表2-12-1( (a a1111) )u u1111( (a a121

53、2) )u 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 a

54、3 3n n) )u u3 3n n 38第二章 线性方程组直接解法WY（1）计算顺序计算顺序：将：将aij ，uij ，lij 按表按表2-1列好，计算列好，计算 时时按框从外到内进行按框从外到内进行， 每一框中每一框中先算行先算行。从。从 左向右依次计算左向右依次计算 uij ；再算列，自上而下求再算列，自上而下求 lij ；三角分解的紧凑格式三角分解的紧凑格式 （2）计算方法计算方法：按行计算按行计算时，需将所求元时，需将所求元 uij 的的 对应元对应元aij 逐次减去逐次减去 uij 所所在行左面各框的元在行左面各框的元 素素 lij 乘以乘以 uij 所在列上面各框相应的元所在列上

55、面各框相应的元 uij 。 按按列计算列计算 lij 时，在时，在作上述运算后还需除以作上述运算后还需除以 lij 所在框的对角元所在框的对角元 lij 。 说明：说明：39第二章 线性方程组直接解法WY三角分解的紧凑格式举例三角分解的紧凑格式举例例例例例4 4中矩阵中矩阵中矩阵中矩阵A A的三角分解按紧凑格式计算，结果见下表的三角分解按紧凑格式计算，结果见下表的三角分解按紧凑格式计算，结果见下表的三角分解按紧凑格式计算，结果见下表2-22-2：由表由表可得：可得：（2 2）2 2（2 2）2 2（3 3）3 3（7 7）7 7 2 2 2=32=3（7 7）7 7 2 2 3=13=1（4

56、4）（）（）（）（4 4 （ 1 1） 2 2）/3=2/3=2（5 5）5 5 2 2 1 1 （ 1 1） 3=63=6表表表表2-22-240第二章 线性方程组直接解法WY3.3 直接三角分解法直接三角分解法 若线性方程组若线性方程组若线性方程组若线性方程组Ax Ax = = b b的系数矩阵的系数矩阵的系数矩阵的系数矩阵A A完成三角分解，完成三角分解，完成三角分解，完成三角分解，A A = = LULU，那么解那么解那么解那么解方程组方程组方程组方程组Ax Ax = = b b等价于求解两个三角等价于求解两个三角等价于求解两个三角等价于求解两个三角形方程组形方程组形方程组形方程组Ly

57、 Ly = = b b，UxUx = = y y，即由：即由：即由：即由： 再再再再由：由：由：由：可解得：可解得：可解得：可解得：41第二章 线性方程组直接解法WY直接三角分解法（续）直接三角分解法（续） 容易看出，式（容易看出，式（容易看出，式（容易看出，式（2-142-14）与式（）与式（）与式（）与式（2-132-13）的运算规律相同，）的运算规律相同，）的运算规律相同，）的运算规律相同， 或者由：或者由：或者由：或者由： 可知，若将可知，若将可知，若将可知，若将b b作作作作A A的最后一列处理，在将的最后一列处理，在将的最后一列处理，在将的最后一列处理，在将A A化为上三化为上三化

58、为上三化为上三角阵的同时，也将角阵的同时，也将角阵的同时，也将角阵的同时，也将b b化作了化作了化作了化作了y y，故在利用三角分解求解方程故在利用三角分解求解方程故在利用三角分解求解方程故在利用三角分解求解方程组组组组AxAx = = b b时，只需将右端向量时，只需将右端向量时，只需将右端向量时，只需将右端向量b b列在表列在表列在表列在表2-12-1的最后一列，按的最后一列，按的最后一列，按的最后一列，按u uij ij的计算方法即可求出的计算方法即可求出的计算方法即可求出的计算方法即可求出y yk k（或在式（或在式（或在式（或在式（2-132-13）中求）中求）中求）中求u uij

59、ij时，增时，增时，增时，增加一列，加一列，加一列，加一列，j j算到算到算到算到n n+1+1）下表下表下表下表2-32-3是求解线性方程是求解线性方程是求解线性方程是求解线性方程Ax Ax = = b b的紧凑的紧凑的紧凑的紧凑格式，其计算顺序与计算方法与三角分解相同。格式，其计算顺序与计算方法与三角分解相同。格式，其计算顺序与计算方法与三角分解相同。格式，其计算顺序与计算方法与三角分解相同。按表按表按表按表2-32-3计算后，再按式（计算后，再按式（计算后，再按式（计算后，再按式（2-152-15）即可求出方程组的解。）即可求出方程组的解。）即可求出方程组的解。）即可求出方程组的解。42

60、第二章 线性方程组直接解法WY紧凑格式解线性方程组紧凑格式解线性方程组举例举例例例6解解 ：按表按表按表按表2-32-3计算：计算：计算：计算：( (a a1111) )u u1111( (a a1212) )u u1212( (a a1313) )u u1313( (a a1 1n n) )u u1 1n n( (b b1 1) )y y1 1( (a a2121) )l l2121( (a a2222) )u u2222( (a a2323) )u u2323( (a a2 2n n) )u u2 2n n( (b b2 2) )y y2 2( (a a3131) )l l3131( (a

61、 a3232) )l l3232( (a a3333) )u u3333( (a a3 3n n) )u u3 3n n( (b b3 3) )y y3 3( (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( (b bn n) )y yn n(3) 3(3) 3(2) 2(2) 2(5) 5(5) 5(6) 6(6) 6(-1) -1/3(-1) -1/3(1) 1/3(1) 1/3表表表表2-32-343第二章 线性方程组直接解法WY所以：所以：紧凑格式解线性

62、方程组紧凑格式解线性方程组举例（续）举例（续）44第二章 线性方程组直接解法WY三角分解法三角分解法的几点说明的几点说明1 1、用三角分解法求线性方程的乘除法运算量也是、用三角分解法求线性方程的乘除法运算量也是、用三角分解法求线性方程的乘除法运算量也是、用三角分解法求线性方程的乘除法运算量也是n n3 3/3 /3 数量级。由于在求出数量级。由于在求出数量级。由于在求出数量级。由于在求出u uij ij, , l lij ij和和和和y yi i后，后，后，后，a aij ij和和和和b bi i无需保留，无需保留，无需保留，无需保留， 故上机计算时，可把故上机计算时，可把故上机计算时，可把故

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

64、的推导及例中可以看出，系数矩阵的、从三角分解法的推导及例中可以看出，系数矩阵的、从三角分解法的推导及例中可以看出，系数矩阵的 三三三三 角分解与右端项无关。因角分解与右端项无关。因角分解与右端项无关。因角分解与右端项无关。因 而在计算多个系数矩阵而在计算多个系数矩阵而在计算多个系数矩阵而在计算多个系数矩阵 为为为为A A而右端不同的线性方程组系时，用三角分解法更而右端不同的线性方程组系时，用三角分解法更而右端不同的线性方程组系时，用三角分解法更而右端不同的线性方程组系时，用三角分解法更 为为为为 简便（如可用于求逆矩阵）。简便（如可用于求逆矩阵）。简便（如可用于求逆矩阵）。简便（如可用于求逆矩

65、阵）。45第二章 线性方程组直接解法WY三角分解法三角分解法的几点说明（续）的几点说明（续）6 6、分解法的优点除上述分解法的优点除上述分解法的优点除上述分解法的优点除上述2 2、3 3外，还有：外，还有：外，还有：外，还有： a a. . 可求解可求解可求解可求解A A2 2z z = = b b, ,因为算因为算因为算因为算A A2 2计算量大，可用计算量大，可用计算量大，可用计算量大，可用 b b. . 可根据可根据可根据可根据A A的形状设计算法，当的形状设计算法，当的形状设计算法，当的形状设计算法，当A A为大型稀疏，且非零为大型稀疏，且非零为大型稀疏，且非零为大型稀疏，且非零元素有

66、规律如带状，三对角等，作分解时能充分利用元素有规律如带状，三对角等，作分解时能充分利用元素有规律如带状，三对角等，作分解时能充分利用元素有规律如带状，三对角等，作分解时能充分利用A A的的的的特点，特点，特点，特点，L L，U U能保持能保持能保持能保持A A的原状，即的原状，即的原状，即的原状，即L L与与与与A A的下三角相同，的下三角相同，的下三角相同，的下三角相同，U U与与与与A A的上三角形状相同。的上三角形状相同。的上三角形状相同。的上三角形状相同。 4 4、三角分解法一般也可采用选主元的技术，以使算法更、三角分解法一般也可采用选主元的技术，以使算法更、三角分解法一般也可采用选主

67、元的技术，以使算法更、三角分解法一般也可采用选主元的技术，以使算法更 具数值稳定性。具数值稳定性。具数值稳定性。具数值稳定性。5 5、也可以把矩阵、也可以把矩阵、也可以把矩阵、也可以把矩阵A A分解成一个下三角矩阵与一个单位上三分解成一个下三角矩阵与一个单位上三分解成一个下三角矩阵与一个单位上三分解成一个下三角矩阵与一个单位上三 角矩阵的乘积，矩阵的角矩阵的乘积，矩阵的角矩阵的乘积，矩阵的角矩阵的乘积，矩阵的 这种分解称为克劳特（这种分解称为克劳特（这种分解称为克劳特（这种分解称为克劳特（CroutCrout） 分解。分解。分解。分解。46第二章 线性方程组直接解法WY4 平方根法与改进的平方

68、根法平方根法与改进的平方根法 对称正定矩阵概念：对称正定矩阵概念： 工程实际问题的计算中，线性方程组的系数矩阵常工程实际问题的计算中，线性方程组的系数矩阵常工程实际问题的计算中，线性方程组的系数矩阵常工程实际问题的计算中，线性方程组的系数矩阵常常具有对称正定性，即其各阶顺序主子式及全部特征值均常具有对称正定性，即其各阶顺序主子式及全部特征值均常具有对称正定性，即其各阶顺序主子式及全部特征值均常具有对称正定性，即其各阶顺序主子式及全部特征值均大于零。矩阵的这一特性使它的三角分解也有更简单的形大于零。矩阵的这一特性使它的三角分解也有更简单的形大于零。矩阵的这一特性使它的三角分解也有更简单的形大于零

69、。矩阵的这一特性使它的三角分解也有更简单的形式，从而导出一些特殊的解法。式，从而导出一些特殊的解法。式，从而导出一些特殊的解法。式，从而导出一些特殊的解法。 5 5. . A A的所有顺序主子式均为正数，的所有顺序主子式均为正数，的所有顺序主子式均为正数，的所有顺序主子式均为正数，即即即即detdet( (A Ak k)0, )0, k k = 1,2, = 1,2,n n) ) 。 4 4. . A A的所有特征值的所有特征值的所有特征值的所有特征值00； 3. 3. A A的对角线元素的对角线元素的对角线元素的对角线元素a aii ii0(0(i i = 1,2, = 1,2,n n) )

70、； 2 2. . A A是非奇异阵，且是非奇异阵，且是非奇异阵，且是非奇异阵，且A A 1 1也是对称正定阵；也是对称正定阵；也是对称正定阵；也是对称正定阵； 1 1. . A A的所有顺序主子矩阵的所有顺序主子矩阵的所有顺序主子矩阵的所有顺序主子矩阵A Ak k( (k k=1,2,=1,2,n n) )也是对称正定阵；也是对称正定阵；也是对称正定阵；也是对称正定阵； 若若若若A A为对称正定矩阵，为对称正定矩阵，为对称正定矩阵，为对称正定矩阵，则则则则：47第二章 线性方程组直接解法WY4.1 平方根法平方根法 定理定理定理定理 2.22.2若若A是对称正定矩阵，则存在唯一的单位下三是对称

71、正定矩阵，则存在唯一的单位下三角矩阵角矩阵L和对角阵：和对角阵： 证明：证明： 首先首先A可直接作可直接作LU分解，记为分解，记为A = LU1 ，其中：其中：48第二章 线性方程组直接解法WY定理定理 2.2（续）（续）其中其中其中其中U U0 0是单位上三角阵，则由是单位上三角阵，则由是单位上三角阵，则由是单位上三角阵，则由A A的对称性可得：的对称性可得：的对称性可得：的对称性可得： 再由唯一性得再由唯一性得再由唯一性得再由唯一性得U U0 0 = = L LT T，所以所以所以所以A A = = LDLLDLT T，并且这种分解并且这种分解并且这种分解并且这种分解是唯一的，又由于是唯一

72、的，又由于是唯一的，又由于是唯一的，又由于U U1 1的对角线元素的对角线元素的对角线元素的对角线元素U Ukkkk就是就是就是就是GaussGauss消元法的消元法的消元法的消元法的主元素：主元素：主元素：主元素： 由于由于LD1/2是下三角阵，因此有推论：是下三角阵，因此有推论：49第二章 线性方程组直接解法WYCholeskg分解分解1 推推论论 若若若若A A是对称正定矩阵，则存在唯一的主对角线元素是对称正定矩阵，则存在唯一的主对角线元素是对称正定矩阵，则存在唯一的主对角线元素是对称正定矩阵，则存在唯一的主对角线元素都为正的下三角阵都为正的下三角阵都为正的下三角阵都为正的下三角阵L L

73、，使得：使得：使得：使得： A=LLA=LLT T矩阵的这种分解称为矩阵的这种分解称为矩阵的这种分解称为矩阵的这种分解称为CholeskgCholeskg分解分解分解分解。用比较法可以导出用比较法可以导出用比较法可以导出用比较法可以导出L L的计算公式。设：的计算公式。设：的计算公式。设：的计算公式。设： 比较比较比较比较A A与与与与LLLLT T的相应元素，的相应元素，的相应元素，的相应元素，即由即由即由即由A A = = LLLLT T可得：可得：可得：可得：计算顺序计算顺序按列进行按列进行。 因此：因此：50第二章 线性方程组直接解法WYCholeskg分解分解2当完成矩阵当完成矩阵当

74、完成矩阵当完成矩阵A A的的的的CholeskyCholesky分解后，分解后，分解后，分解后，求解方求解方求解方求解方 程组程组程组程组AXAX = = b b就转化求：就转化求：就转化求：就转化求： 求解对称求解对称求解对称求解对称正定线性方正定线性方正定线性方正定线性方程组的方法程组的方法程组的方法程组的方法称为称为称为称为平方根平方根平方根平方根法法法法，也称为，也称为，也称为，也称为CholeskyCholesky分分分分解法解法解法解法，这种，这种，这种，这种方法无需选方法无需选方法无需选方法无需选主元，计算过程也是稳定的。由于主元，计算过程也是稳定的。由于主元，计算过程也是稳定的

75、。由于主元，计算过程也是稳定的。由于A A的对称性的对称性的对称性的对称性，平方根法平方根法平方根法平方根法的乘除运算量为的乘除运算量为的乘除运算量为的乘除运算量为n n3 3/6/6数量级，约为直接分解法的一半。上数量级，约为直接分解法的一半。上数量级，约为直接分解法的一半。上数量级，约为直接分解法的一半。上机计算时，所需存贮单元也少，只要存贮机计算时，所需存贮单元也少，只要存贮机计算时，所需存贮单元也少，只要存贮机计算时，所需存贮单元也少，只要存贮A A的下三角部分的下三角部分的下三角部分的下三角部分和右端项和右端项和右端项和右端项b b，计算中计算中计算中计算中L L存放于存放于存放于存

76、放于A A的存贮单元，的存贮单元，的存贮单元，的存贮单元，y y , , x x存放在存放在存放在存放在b b的存贮单元。的存贮单元。的存贮单元。的存贮单元。平方根法平方根法平方根法平方根法的的的的不足不足不足不足之处在于需作之处在于需作之处在于需作之处在于需作n n次开方运算。次开方运算。次开方运算。次开方运算。它们的解分别为：它们的解分别为：它们的解分别为：它们的解分别为：51第二章 线性方程组直接解法WY平方根法举例平方根法举例 用平方根法解用平方根法解用平方根法解用平方根法解对称正定方程组：对称正定方程组：对称正定方程组：对称正定方程组： 例例7解解解解 ：先分解系数矩阵：先分解系数矩

77、阵：先分解系数矩阵：先分解系数矩阵A A，只对只对只对只对A A的下三角部分运算即可，的下三角部分运算即可，的下三角部分运算即可，的下三角部分运算即可，所以只存放所以只存放所以只存放所以只存放A A的下三角部分：的下三角部分：的下三角部分：的下三角部分：52第二章 线性方程组直接解法WY4.2 改进的平方根法改进的平方根法 由定理由定理由定理由定理2.22.2，对称正定矩，对称正定矩，对称正定矩，对称正定矩阵阵阵阵A A又可以作如下分解又可以作如下分解又可以作如下分解又可以作如下分解 ：其中，其中，其中，其中，L L是单位下三角阵，是单位下三角阵，是单位下三角阵，是单位下三角阵，D D是对角阵

78、，是对角阵，是对角阵，是对角阵，U U = = DLDLT T。由于由于由于由于U U = = DLDLT T，即：即：即：即： 比较两边的比较两边的比较两边的比较两边的对应元素可得对应元素可得对应元素可得对应元素可得 ：首先由紧凑格式首先由紧凑格式首先由紧凑格式首先由紧凑格式的三角分解可得：的三角分解可得：的三角分解可得：的三角分解可得：53第二章 线性方程组直接解法WY改进的平方根法说明改进的平方根法说明 基于上述基于上述基于上述基于上述LDLLDLT T分解的方法称为改进的平方根法，其乘分解的方法称为改进的平方根法，其乘分解的方法称为改进的平方根法，其乘分解的方法称为改进的平方根法，其乘

79、除运算量与除运算量与除运算量与除运算量与CholeskyCholesky分解相当，且避免了开方运算。计算分解相当，且避免了开方运算。计算分解相当，且避免了开方运算。计算分解相当，且避免了开方运算。计算顺序按先行后列逐层分解计算；顺序按先行后列逐层分解计算；顺序按先行后列逐层分解计算；顺序按先行后列逐层分解计算； 对称正定阵对称正定阵对称正定阵对称正定阵A A完成完成完成完成A A = = ADLADLT T= = LULU分解后，求解方程组：分解后，求解方程组：分解后，求解方程组：分解后，求解方程组：AxAx = = b b，就转化为求解就转化为求解就转化为求解就转化为求解 ： 并且由于求并且

80、由于求并且由于求并且由于求y y和求和求和求和求U U的最后一列的算法完全相同，所以的最后一列的算法完全相同，所以的最后一列的算法完全相同，所以的最后一列的算法完全相同，所以可将可将可将可将y y视为视为视为视为U U的最后一列进行计算。的最后一列进行计算。的最后一列进行计算。的最后一列进行计算。 按上述算法，当按上述算法，当按上述算法，当按上述算法，当A A为对称正定阵时，单位下三角阵为对称正定阵时，单位下三角阵为对称正定阵时，单位下三角阵为对称正定阵时，单位下三角阵L L的的的的元素不必按紧凑格式方法去求解，而只需在求得元素不必按紧凑格式方法去求解，而只需在求得元素不必按紧凑格式方法去求解

81、，而只需在求得元素不必按紧凑格式方法去求解，而只需在求得U U的第的第的第的第k k行元素后，以它们去除以行元素后，以它们去除以行元素后，以它们去除以行元素后，以它们去除以u ukkkk即得相应的即得相应的即得相应的即得相应的L L的第的第的第的第k k列元素，列元素，列元素，列元素，这样就大大减少了计算量。这样就大大减少了计算量。这样就大大减少了计算量。这样就大大减少了计算量。54第二章 线性方程组直接解法WY改进的平方根法举例改进的平方根法举例 用改进的平方用改进的平方用改进的平方用改进的平方根法求解方程组：根法求解方程组：根法求解方程组：根法求解方程组：例例8解：解：解：解：对增广矩阵（

82、对增广矩阵（对增广矩阵（对增广矩阵（A A b b）逐层分解可得：逐层分解可得：逐层分解可得：逐层分解可得：则则则则UxUx = = y y为：为：为：为： 改进平方根法由于对矩阵改进平方根法由于对矩阵改进平方根法由于对矩阵改进平方根法由于对矩阵A A无正定要求（只要无正定要求（只要无正定要求（只要无正定要求（只要u ukkkk 0 0 ），），），），( (k k = 1,2, = 1,2,n n) )即可，而正定要求即可，而正定要求即可，而正定要求即可，而正定要求u ukkkk 0 ( 0 (k k = 1,2, = 1,2,n n) )，因因因因此是求解对称方程组常用的方法。此是求解对称

83、方程组常用的方法。此是求解对称方程组常用的方法。此是求解对称方程组常用的方法。 55第二章 线性方程组直接解法WY5 Gauss-Jordan消元法求矩阵的逆消元法求矩阵的逆 Gauss消元法有许多变形，列主元素法是其中之消元法有许多变形，列主元素法是其中之一，在列主元法的基础上还可对算法进行如下的一，在列主元法的基础上还可对算法进行如下的修改：在消元过程中选主元后，先将主元化为修改：在消元过程中选主元后，先将主元化为1，然后将主元所在列上，下方各元素均化为然后将主元所在列上，下方各元素均化为0，这样，这样消元的结果使系数矩阵化为了单位阵，无需回代消元的结果使系数矩阵化为了单位阵，无需回代就得

84、到了原方程之解，这种无回代过程的列主元就得到了原方程之解，这种无回代过程的列主元素法称为素法称为Gauss-Jordan消元法消元法。 Gauss-Jordan消元法消元法比顺序消去法计算量大一比顺序消去法计算量大一点，实践中使用不多，但用它求逆阵却十分方便。点，实践中使用不多，但用它求逆阵却十分方便。因为消元过程实质上就是对系数矩阵因为消元过程实质上就是对系数矩阵A实行初等变实行初等变换，将换，将A化为单位阵，相当于对化为单位阵，相当于对A左乘了一系列的左乘了一系列的初等变换阵初等变换阵M1，M2，Mn-1，Mn，使：使：紧接下屏紧接下屏紧接下屏紧接下屏56第二章 线性方程组直接解法WYGa

85、uss-Jordan消元法求矩阵的逆（续消元法求矩阵的逆（续1） 这表明同样的一组初等变换在将这表明同样的一组初等变换在将A化为化为I 的同时的同时，可将，可将I 化为化为A 1，即有：即有： 因此，以因此，以Gauss-Jordan消元法消元法求求A的逆阵，就是的逆阵，就是要找到要找到Mi (i=1,2,n)，以它们逐个左乘以它们逐个左乘(A,I ),逐列将逐列将A的对角线上的元素化为的对角线上的元素化为1，而其余元素化，而其余元素化为为0，最终将，最终将A化为单位阵，则化为单位阵，则I化为化为A的逆阵的逆阵A 1 。57第二章 线性方程组直接解法WYGauss-Jordan消元法求矩阵的逆

86、（续消元法求矩阵的逆（续2）设增广阵为：设增广阵为：58第二章 线性方程组直接解法WY 这里这里这里这里a aij ij(1)(1)= =a a1 1j j，上述上述上述上述a aij ij(2)(2)的计算与的计算与的计算与的计算与GaussGauss消元法基本上消元法基本上消元法基本上消元法基本上相相相相同，仅仅由于同，仅仅由于同，仅仅由于同，仅仅由于mm1111与与与与GaussGauss消消消消元法中的乘数元法中的乘数元法中的乘数元法中的乘数l l1111不相同引起第不相同引起第不相同引起第不相同引起第一行元素一行元素一行元素一行元素a a1 1j j(2)(2)与与与与a aij i

87、j(2)(2)计算不相同，假若把增广阵中计算不相同，假若把增广阵中计算不相同，假若把增广阵中计算不相同，假若把增广阵中I I的各的各的各的各列列列列视为视为视为视为A A的第的第的第的第n n+1+1列，第列，第列，第列，第n n +2+2列，列，列，列，那么上述计算公式中的，那么上述计算公式中的，那么上述计算公式中的，那么上述计算公式中的第二个下标可扩充到第二个下标可扩充到第二个下标可扩充到第二个下标可扩充到2 2n n。Gauss-Jordan消元法求矩阵的逆（续消元法求矩阵的逆（续3）59第二章 线性方程组直接解法WYGauss-Jordan消元法求逆阵消元法求逆阵(续续4)60第二章

88、线性方程组直接解法WYGauss-Jordan消元法求逆阵消元法求逆阵(续续5)61第二章 线性方程组直接解法WY设经过设经过k 1步后得到步后得到 ：Gauss-Jordan消元法求逆阵消元法求逆阵(续续6)1 162第二章 线性方程组直接解法WYGauss-Jordan消元法求逆阵消元法求逆阵(续续7)其中：其中：其中：其中：63第二章 线性方程组直接解法WYGauss-Jordan消元法求逆阵消元法求逆阵(续续8)完成完成完成完成n n步消元后，步消元后，步消元后，步消元后，A A 1 1放在原放在原放在原放在原A A的位置。的位置。的位置。的位置。 64第二章 线性方程组直接解法WYG

89、auss-Jordan法求逆阵的具体步骤法求逆阵的具体步骤 按上述紧缩存贮原则，可节省存贮单元，同时按上述紧缩存贮原则，可节省存贮单元，同时还使得整个计算更简单了。可总结求逆步骤如下：还使得整个计算更简单了。可总结求逆步骤如下： 上述上述1，2是求第是求第k列元素，构成列元素，构成Mk（即求主列）即求主列） 65第二章 线性方程组直接解法WY（计算其他元素，但少（计算其他元素，但少k列，列，k行）行） 用上述用上述Gauss-Jordan法法求逆阵，计算量约求逆阵，计算量约为为n3，是是Gauss消元法消元法的的3倍，为保证方法稳倍，为保证方法稳定性，还可选定性，还可选列主元列主元，若仍按上述

90、紧缩存贮，若仍按上述紧缩存贮原则，则最后需原则，则最后需按行交换的相反次序作列交按行交换的相反次序作列交换才能得到换才能得到A 1。 Gauss-Jordan法求逆阵的具体法求逆阵的具体步骤（续）步骤（续） 66第二章 线性方程组直接解法WYGauss-Jordan法求逆阵举例法求逆阵举例例例例例9 9 解解解解： 按紧缩存贮方式，逐次计算结果与存贮如下：按紧缩存贮方式，逐次计算结果与存贮如下：按紧缩存贮方式，逐次计算结果与存贮如下：按紧缩存贮方式，逐次计算结果与存贮如下：第一步第一步第一步第一步：k k = 1 = 1，在第一列中选在第一列中选在第一列中选在第一列中选主元，交换主元，交换主元

91、，交换主元，交换1 1，2 2行，得：行，得：行，得：行，得：第二步：第二步：第二步：第二步： k k = 2 = 2在第二列对角元下选主元，交换在第二列对角元下选主元，交换在第二列对角元下选主元，交换在第二列对角元下选主元，交换2 2，3 3行由行由行由行由1 1，2 2先计算第先计算第先计算第先计算第2 2列，由列，由列，由列，由3 3计算其他元素（除计算其他元素（除计算其他元素（除计算其他元素（除2 2列列列列2 2行外）而由行外）而由行外）而由行外）而由4 4计算剩计算剩计算剩计算剩下的第下的第下的第下的第2 2行的元素（这里行的元素（这里行的元素（这里行的元素（这里k k=2=2的第

92、的第的第的第2 2列第行称为主列，主行）列第行称为主列，主行）列第行称为主列，主行）列第行称为主列，主行） 第三步：第三步：第三步：第三步：k k = 3 = 3以以以以a a3333=1/6=1/6为主元，消元后得为主元，消元后得为主元，消元后得为主元，消元后得：交交交交换换换换2 2、3 3列列列列最后：最后：最后：最后：按行交换的相反次序进行列交换：先交换按行交换的相反次序进行列交换：先交换按行交换的相反次序进行列交换：先交换按行交换的相反次序进行列交换：先交换2 2，3 3列，再列，再列，再列，再 交换交换交换交换1 1，2 2列得列得列得列得A A 1 1。 交换交换交换交换1 1，

93、2 2列列列列67第二章 线性方程组直接解法WY6 方程组的性态与条件数方程组的性态与条件数 无论用哪种方法求解线性方程组，无论用哪种方法求解线性方程组，一般情况下都会产生误差，本节讨论线一般情况下都会产生误差，本节讨论线性方程组解的误差。性方程组解的误差。 方程组的解为一组数，称为解向量，方程组的解为一组数，称为解向量，近似解向量与准确解向量之差称为误差近似解向量与准确解向量之差称为误差向量，为了估计误差向量的大小，首先向量，为了估计误差向量的大小，首先需引入衡量向量与矩阵大小的度量需引入衡量向量与矩阵大小的度量范数范数。 68第二章 线性方程组直接解法WY6.1 向量与矩阵的范数向量与矩阵

94、的范数 这三个性质刻画了向量长度的基本特征，并可以用其将平这三个性质刻画了向量长度的基本特征，并可以用其将平这三个性质刻画了向量长度的基本特征，并可以用其将平这三个性质刻画了向量长度的基本特征，并可以用其将平面向量长度的概念推广到一般面向量长度的概念推广到一般面向量长度的概念推广到一般面向量长度的概念推广到一般n n维向量，于是有如下定义：维向量，于是有如下定义：维向量，于是有如下定义：维向量，于是有如下定义： 定义定义定义定义1 1下屏将给出范数的种类：下屏将给出范数的种类：下屏将给出范数的种类：下屏将给出范数的种类：69第二章 线性方程组直接解法WY常用的向量范数常用的向量范数 容易证明它

95、们都满足上述三条性质。可以看出，容易证明它们都满足上述三条性质。可以看出，容易证明它们都满足上述三条性质。可以看出，容易证明它们都满足上述三条性质。可以看出，2 2范范范范数是平面向量长度计算公式在形式上的推广，也是线性代数是平面向量长度计算公式在形式上的推广，也是线性代数是平面向量长度计算公式在形式上的推广，也是线性代数是平面向量长度计算公式在形式上的推广，也是线性代数中的内积定义。此处引入多种范数来刻画向量的大小，数中的内积定义。此处引入多种范数来刻画向量的大小，数中的内积定义。此处引入多种范数来刻画向量的大小，数中的内积定义。此处引入多种范数来刻画向量的大小，是为了在不同情况下用不同的范

96、数研究问题。是为了在不同情况下用不同的范数研究问题。是为了在不同情况下用不同的范数研究问题。是为了在不同情况下用不同的范数研究问题。向量范数的证明：（只对第三条）向量范数的证明：（只对第三条）向量范数的证明：（只对第三条）向量范数的证明：（只对第三条） 对对对对 范数范数范数范数：前面：前面：前面：前面2 2条显然，对第三条，由于对任意实数条显然，对第三条，由于对任意实数条显然，对第三条，由于对任意实数条显然，对第三条，由于对任意实数x x, , y y，绝对值不等式：绝对值不等式：绝对值不等式：绝对值不等式：| |x x+ +y| y|x|+|y|x|+|y| 成立，因而有成立，因而有成立，

97、因而有成立，因而有: :分别称为向量分别称为向量x的的2范数，范数，1范数，无穷范数范数，无穷范数。70第二章 线性方程组直接解法WY对对2范数范数利用实数的柯西不等式利用实数的柯西不等式： 于是，有：于是，有：常用的向量范数（续）常用的向量范数（续）71第二章 线性方程组直接解法WYRn中范数的等价性中范数的等价性 例如可证明如下例如可证明如下例如可证明如下例如可证明如下等价性等价性等价性等价性： 所以，所以，所以，所以，2 2范范范范数与数与数与数与 范数范数范数范数是等价的。是等价的。是等价的。是等价的。不难证明：不难证明：不难证明：不难证明：亦即亦即1范数与范数与 范数是等价的范数是等

98、价的 。事实上事实上事实上事实上: : Rn 中任意中任意两种范数两种范数都是等价都是等价的的。 72第二章 线性方程组直接解法WY向量的误差向量的误差 有了向量范数，就可以用它来表示方程组有了向量范数，就可以用它来表示方程组解向量的误差，设解向量的误差，设x是方程组是方程组Ax = b的准确解向的准确解向量，量， 是近似解向量，则是近似解向量，则: 显然，范数不同，其误差值是不一样的。显然，范数不同，其误差值是不一样的。 分别称为分别称为 的关于的关于P范数的绝对误差与相范数的绝对误差与相对误差。对误差。73第二章 线性方程组直接解法WY矩阵范数矩阵范数 定义定义2对任意对任意对任意对任意n

99、 n阶方阵阶方阵阶方阵阶方阵A A = ( = (a aij ij) )n n n n，若对应一个非负实若对应一个非负实若对应一个非负实若对应一个非负实数数数数| |A A| |，满足：满足：满足：满足： 则称则称|A|为矩阵为矩阵A的的范数范数。 与向量范数定义比较，前三条性质只是向量范与向量范数定义比较，前三条性质只是向量范数定义的推广，而第四条性质则是矩阵乘法性质数定义的推广，而第四条性质则是矩阵乘法性质的要求，它使矩阵范数在数值计算中使用更方便。的要求，它使矩阵范数在数值计算中使用更方便。 74第二章 线性方程组直接解法WY常用的矩阵范数常用的矩阵范数常用的矩阵范数有：常用的矩阵范数有

100、：常用的矩阵范数有：常用的矩阵范数有： 它们分别叫做它们分别叫做它们分别叫做它们分别叫做矩阵的矩阵的矩阵的矩阵的 范数范数范数范数，1 1范数范数范数范数，2 2范数范数范数范数，F F范数范数范数范数，矩阵矩阵矩阵矩阵E E范数范数范数范数是向量是向量是向量是向量2 2范数范数范数范数的推广，的推广，的推广，的推广，矩阵矩阵矩阵矩阵 范数范数范数范数，1 1范数计算范数计算范数计算范数计算容易容易容易容易，而，而，而，而矩阵矩阵矩阵矩阵2 2范数与范数与范数与范数与A AT TA A的特征值有关的特征值有关的特征值有关的特征值有关，所以又称为，所以又称为，所以又称为，所以又称为谱谱谱谱范数范

101、数范数范数，它的，它的，它的，它的计算较困难计算较困难计算较困难计算较困难，但因为它有一些好的性质，所，但因为它有一些好的性质，所，但因为它有一些好的性质，所，但因为它有一些好的性质，所以也是以也是以也是以也是常用常用常用常用的范数。的范数。的范数。的范数。 75第二章 线性方程组直接解法WY常用的矩阵范数（续）常用的矩阵范数（续）可以证明，这些范数都满足定义可以证明，这些范数都满足定义2。以以以以| |A A| | 为例，前为例，前为例，前为例，前2 2条性质显然成立，而对：条性质显然成立，而对：条性质显然成立，而对：条性质显然成立，而对：76第二章 线性方程组直接解法WY最大行最大行和和矩

102、阵范数的证明矩阵范数的证明77第二章 线性方程组直接解法WY最大行最大行和和矩阵范数的证明（续）矩阵范数的证明（续）78第二章 线性方程组直接解法WY范数的相容性范数的相容性 在误差估计中，由于矩阵与向量会同时用到，我们总在误差估计中，由于矩阵与向量会同时用到，我们总在误差估计中，由于矩阵与向量会同时用到，我们总在误差估计中，由于矩阵与向量会同时用到，我们总希望有上面的不等式成立，希望有上面的不等式成立，希望有上面的不等式成立，希望有上面的不等式成立， 但对任意的向量范数与矩阵范但对任意的向量范数与矩阵范但对任意的向量范数与矩阵范但对任意的向量范数与矩阵范数却未必如此，因而数却未必如此，因而数

103、却未必如此，因而数却未必如此，因而特别地把满足此不等式的范数称为特别地把满足此不等式的范数称为特别地把满足此不等式的范数称为特别地把满足此不等式的范数称为相相相相容的容的容的容的，可以证明，上述常用的范数是相容的，即有：，可以证明，上述常用的范数是相容的，即有：，可以证明，上述常用的范数是相容的，即有：，可以证明，上述常用的范数是相容的，即有： 在使用范数时，应选用相容的矩阵范数与向量范数。在使用范数时，应选用相容的矩阵范数与向量范数。在使用范数时，应选用相容的矩阵范数与向量范数。在使用范数时，应选用相容的矩阵范数与向量范数。 分别称为分别称为分别称为分别称为 的关于的关于的关于的关于P P范

104、数的范数的范数的范数的绝对误差与相对误差。绝对误差与相对误差。绝对误差与相对误差。绝对误差与相对误差。 有了矩阵范数，就可以用它描述矩阵的误差，设有了矩阵范数，就可以用它描述矩阵的误差，设有了矩阵范数，就可以用它描述矩阵的误差，设有了矩阵范数，就可以用它描述矩阵的误差，设 是是是是A A的的的的近似矩阵，近似矩阵，近似矩阵，近似矩阵， 称为称为称为称为 的的的的残差阵残差阵，则：，则：，则：，则：79第二章 线性方程组直接解法WY求范数举例求范数举例例例1080第二章 线性方程组直接解法WY6.2 舍入误差的影响及算法的稳定性舍入误差的影响及算法的稳定性 前面曾介绍了多种解线性方程组的方法，前

105、面曾介绍了多种解线性方程组的方法，由于计算机字长的限制，无论哪种方法，求由于计算机字长的限制，无论哪种方法，求解的每一步几乎都可能引入新的舍入误差，解的每一步几乎都可能引入新的舍入误差，这些误差随着计算的推进而向前传播。这些误差随着计算的推进而向前传播。 算法不同误差的累积情况不一样，舍入算法不同误差的累积情况不一样，舍入误差对解的影响不大的算法称为误差对解的影响不大的算法称为数值稳定的数值稳定的算法算法。 可以证明：可以证明：主元素法、约当消去法、主元素法、约当消去法、Cholesky分解法和追赶法都是数值稳定的算分解法和追赶法都是数值稳定的算法。法。 81第二章 线性方程组直接解法WY 可

106、以看出，后两个方程组与第一个方程组相可以看出，后两个方程组与第一个方程组相比，系数矩阵或右端向量仅有比，系数矩阵或右端向量仅有0.0005以下的误差，以下的误差，但准确解却相差很大。但准确解却相差很大。 6.3 方程组的性态和条件数方程组的性态和条件数 数值稳定的算法是否一定能求得精度比较高数值稳定的算法是否一定能求得精度比较高的解呢？回答是不一定，解的精度还与方程组本的解呢？回答是不一定，解的精度还与方程组本身的性态有关，下面来考察几个例：身的性态有关，下面来考察几个例： 例例1182第二章 线性方程组直接解法WY方程组的性态和条件数（续方程组的性态和条件数（续1）例例12若其系数，常数项改

107、用三位有效数字的小数表示，若其系数，常数项改用三位有效数字的小数表示，则方程组为则方程组为 ：83第二章 线性方程组直接解法WY右端项右端项b产生产生0.1%的变化的变化引起解的变化引起解的变化最大变化最大变化184%。初始数据的误差（相对）初始数据的误差（相对）0.3% = 0.003，而解的相对误差却超过，而解的相对误差却超过50%。 例例13方程组的性态和条件数（续方程组的性态和条件数（续2）84第二章 线性方程组直接解法WY方程组的性态讨论方程组的性态讨论 病态、良态病态、良态 在许多实际问题中，线性方程组的系数矩阵和在许多实际问题中，线性方程组的系数矩阵和右端项的元素大多为前面计算的

108、结果，因此上述右端项的元素大多为前面计算的结果，因此上述例中的微小误差是避免不了。而对上述例中的方例中的微小误差是避免不了。而对上述例中的方程组，无论用多么稳定的算法求解，计算中产生程组，无论用多么稳定的算法求解，计算中产生的微小误差就使解面目全非，所以这些方程组的的微小误差就使解面目全非，所以这些方程组的性态是很差的。性态是很差的。 当方程组当方程组Ax = b的系数矩阵与右端向量的系数矩阵与右端向量b的微的微小变动（小扰动）而引起解严重失真时，称此方小变动（小扰动）而引起解严重失真时，称此方程组为病态方程组，其系数矩阵程组为病态方程组，其系数矩阵A称为病态矩阵，称为病态矩阵，否则称为良态方

109、程组，否则称为良态方程组，A称为良态矩阵，为了定量称为良态矩阵，为了定量刻画方程组刻画方程组“病态病态”的程度，下面对方程组的程度，下面对方程组Ax = b在在系数矩阵系数矩阵A及右端项及右端项b有扰动的几种情形进行讨论。有扰动的几种情形进行讨论。85第二章 线性方程组直接解法WY 此不等式表明，当右端项有扰动时，解的相对误差不此不等式表明，当右端项有扰动时，解的相对误差不此不等式表明，当右端项有扰动时，解的相对误差不此不等式表明，当右端项有扰动时，解的相对误差不超过超过超过超过b b的相对误差的的相对误差的的相对误差的的相对误差的 倍。倍。倍。倍。 首先考察右端项首先考察右端项b的扰动对解的

110、影响，设的扰动对解的影响，设b有扰有扰动动 b，A为准确为准确,记引起解记引起解x的扰动为的扰动为 x, 即：即：方程组的性态讨论方程组的性态讨论 病态、良态（续）病态、良态（续）86第二章 线性方程组直接解法WY方程组的性态讨论（续方程组的性态讨论（续2） 当当b为精确的而为精确的而A有微小扰动有微小扰动 A时，在时，在 A充分小充分小时也同样可推得：时也同样可推得： 紧接下屏讨论：紧接下屏讨论：87第二章 线性方程组直接解法WY方程组的性态讨论（续方程组的性态讨论（续3）88第二章 线性方程组直接解法WY方程组的性态讨论续（方程组的性态讨论续（3） 而当而当而当而当A A, ,b b同时有

111、微小扰动同时有微小扰动同时有微小扰动同时有微小扰动 A A， b b时，则可进一步导出更时，则可进一步导出更时，则可进一步导出更时，则可进一步导出更一般的误差估计式：一般的误差估计式：一般的误差估计式：一般的误差估计式：注意到：注意到：89第二章 线性方程组直接解法WY在在 b充分小时，充分小时，此式右端实际上此式右端实际上即为：即为：方程组的性态讨论续（方程组的性态讨论续（4）90第二章 线性方程组直接解法WY矩阵的条件数矩阵的条件数 在三种情况下得到的这三个不等式反映了解的相对误在三种情况下得到的这三个不等式反映了解的相对误在三种情况下得到的这三个不等式反映了解的相对误在三种情况下得到的这

112、三个不等式反映了解的相对误差与差与差与差与A A及及及及b b的相对误差的关系；数的相对误差的关系；数的相对误差的关系；数的相对误差的关系；数| |A|AA|A-1-1| |越小，解的相对越小，解的相对越小，解的相对越小，解的相对误差也越小；反之数误差也越小；反之数误差也越小；反之数误差也越小；反之数| |A|AA|A-1-1| |越大，解的相对误差也越大，越大，解的相对误差也越大，越大，解的相对误差也越大，越大，解的相对误差也越大，实际上这个数反映了解对方程组原始数据的敏感程度，揭实际上这个数反映了解对方程组原始数据的敏感程度，揭实际上这个数反映了解对方程组原始数据的敏感程度，揭实际上这个数

113、反映了解对方程组原始数据的敏感程度，揭示了矩阵示了矩阵示了矩阵示了矩阵A A和方程组本身的性态，称之为方程组或矩阵和方程组本身的性态，称之为方程组或矩阵和方程组本身的性态，称之为方程组或矩阵和方程组本身的性态，称之为方程组或矩阵A A的的的的条件数条件数，记作：记作：记作：记作： condcond( (A A) )越大，越大，越大，越大，A A的病态程度越严重。至于的病态程度越严重。至于的病态程度越严重。至于的病态程度越严重。至于condcond( (A A) )多大才多大才多大才多大才算病态，这是一个算病态，这是一个算病态，这是一个算病态，这是一个相对概念相对概念相对概念相对概念，没有一个严

114、格的数量界限。，没有一个严格的数量界限。，没有一个严格的数量界限。，没有一个严格的数量界限。 91第二章 线性方程组直接解法WY判断病态矩阵的几点参考判断病态矩阵的几点参考 求条件数要计算逆阵的范数，很不方便，如下求条件数要计算逆阵的范数，很不方便，如下一些现象可作为判断病态矩阵的参考。一些现象可作为判断病态矩阵的参考。（1 1）在用主元消去法时消元过程出现小主元（如例）在用主元消去法时消元过程出现小主元（如例）在用主元消去法时消元过程出现小主元（如例）在用主元消去法时消元过程出现小主元（如例1212）（2 2）矩阵）矩阵）矩阵）矩阵A A中元素间数量级相差很大；中元素间数量级相差很大；中元素

115、间数量级相差很大；中元素间数量级相差很大；（3 3）A A的行列式的行列式的行列式的行列式detdet( (A A) )满足（行列式值相对很大）满足（行列式值相对很大）满足（行列式值相对很大）满足（行列式值相对很大） ：（4 4）矩阵的某些行（或列）近似相关（如例）矩阵的某些行（或列）近似相关（如例）矩阵的某些行（或列）近似相关（如例）矩阵的某些行（或列）近似相关（如例1111）。）。）。）。 92第二章 线性方程组直接解法WY利用条件数判断矩阵的性态举例利用条件数判断矩阵的性态举例A A的条件数很大，所以方程组是病态的。的条件数很大，所以方程组是病态的。的条件数很大，所以方程组是病态的。的条

116、件数很大，所以方程组是病态的。的特例，它是典型的的特例，它是典型的的特例，它是典型的的特例，它是典型的“ “病态病态病态病态” ”阵，阵，阵，阵，n n越大，越大，越大，越大，“ “病态病态病态病态” ”越严越严越严越严重，重，重，重，如如如如n n=6=6时，时，时，时，condcond( (A A)=2910)=29106 6，对严重对严重对严重对严重“ “病态病态病态病态” ”的方程组，的方程组，的方程组，的方程组，即即即即使用主元素法求解也难以保证数值稳定性。使用主元素法求解也难以保证数值稳定性。使用主元素法求解也难以保证数值稳定性。使用主元素法求解也难以保证数值稳定性。 93第二章

117、线性方程组直接解法WY第二章第二章结结 束束2-94第二章 线性方程组直接解法WY定理定理3.1存在性证明存在性证明当当当当i i = 1 = 1，因为因为因为因为A A1 1 = = a a11 11 0 0由由由由3.13.1的讨论，存在矩阵：的讨论，存在矩阵：的讨论，存在矩阵：的讨论，存在矩阵： 假定结论对假定结论对假定结论对假定结论对j j = = k k 1 1成立，即：成立，即：成立，即：成立，即：按归纳法原理，存在初等矩阵按归纳法原理，存在初等矩阵按归纳法原理，存在初等矩阵按归纳法原理，存在初等矩阵L L1 1,L Ln n 1 1, ,使得使得使得使得 ：唯一性证明唯一性证明唯一性证明唯一性证明返回返回返回返回95第二章 线性方程组直接解法WY定理定理3.1唯一性证明唯一性证明返返返返 回回回回对于唯一性，假定对于唯一性，假定A有两种有两种Dolittle分解：分解： 由于单位下（上）三角阵的逆仍是单位下三由于单位下（上）三角阵的逆仍是单位下三角阵，而角阵，而 为上三角阵，它们不可能相等，为上三角阵，它们不可能相等，若要相等，必定有：若要相等，必定有： 96第二章 线性方程组直接解法