数值计算方法 第3章 线性方程组的解法课件

1、第3章 线性方程组的解法,1,PPT学习交流,3.1 问题综述,在自然科学与社会科学的研究中，常常需要求解线性代数方程组，这些方程组的系数矩阵大致分为两种：一种是低阶稠密矩阵（例如：阶数大约为小于等于150），另一种是大型稀疏矩阵（即矩阵阶数高且零元素较多）。,在计算机上求解线性代数方程组 Ax=b 的常用的数值解法： 1、直接法：就是经过有限次算术运算，可求得方程组精确解的方法（若计算过程中没有舍入误差）。但实际计算中由于舍入误差的存在和影响，这种方法也只能求得线性方程组的近似解。 这类方法是解低阶稠密矩阵及大型带状方程组的有效方法。,2,PPT学习交流,2、迭代法：就是用某种极限过程去逐步

2、逼近线性方程组精确解的方法，迭代法具有需要计算机的存贮单元较少，程序设计简单，原始系数矩阵在计算机中始终不变等优点，但存在收敛性和收敛速度等问题。 迭代法是解大型稀疏矩阵方程组的重要方法。,注:直接法求解n元线性代数方程组所需乘法次数 1、Cramer（克莱姆）法则：(n+1)！，当n=10时，(n+1)!=39916800次 2、Gauss消去法： 当n=10时，约为430次,3,PPT学习交流,3.2 线性方程组的直接解法,n元线性方程组,简记为,设A非奇异，则方程组有唯一解。,方程组的矩阵形式,4,PPT学习交流,Gauss消去法,高斯消去法步骤： (1) 首先将增广阵 A, b 化为上

3、三角阵； (2) 用三角方程组，回代求解 。,Gauss消去法是一个古老的求解线性代数方程组的方法（早在公元前250年我国就掌握了解三元一次联立方程组的方法）。但由于它改进、变形得到的主元素消去法、三角分解法仍然是目前计算机上常用的有效方法。,5,PPT学习交流,用一个简单的例子说明消去法的基本思想。,6,PPT学习交流,解 (1) 化上三角方程组, , , ,7,PPT学习交流, ,(2)回代过程. 得到下同解方程组后,如下处理,从下向上逐步求解,把x3的值代入求x2,用x3, x2的值求x1,8,PPT学习交流,对应的增广矩阵的变化,(-2)r1 + r3r3,r2 + r3 r3,9,P

4、PT学习交流,1.基本思想,将原方程组逐次消去未知元， 变为与之同解的上三角方程组， 再回代求解 。,用矩阵语言叙述，上述过程是使用初等行变换把增广阵约化为上三角阵，使用上三角方程组，回代求解 。,10,PPT学习交流,2.算法构造,根据下面的上三角方程组,逐次回代求解 xk,22,n-1,n-1,11,PPT学习交流,定义：在使用高斯消去法的过程中，仅对方程组做倍加变换，就形成了顺序高斯消去法。,顺序高斯消去法求解n 元线性方程组的乘除运算总次数为：,顺序高斯消去法计算过程中出现的 称为主元素. 出现 ，消元过程就进行不下去了。,12,PPT学习交流,定理: 顺序高斯消去法的前 n -1 个

5、主元素 均不为零的充要条件是方程组的系数矩阵A的前n -1个顺序主子式,13,PPT学习交流,顺序Gauss消去法计算过程中的 akk(k) 称为主元素，在第k步消元时要用它作除数,则可能会出现以下几种情况,1、若出现 akk(k) 0，消元过程就不能进行下去。,2、akk(k) 0 ，消去过程能够进行，但若|akk(k)| 过小，也会造成舍入误差积累很大导致计算解的精度下降。,顺序高斯消去法的数值稳定性是没有保证的!,14,PPT学习交流,顺序主元素消去法可能计算失败之例,例：单精度解方程组,用顺序主元素消去法计算：,8个,小主元 /* Small pivot element */可能导致计

6、算失败。,15,PPT学习交流,例： 在四位十进制的限制下，试用顺序Gauss消去法求解如下方程组,此方程组具有四位有效数字的精确解为,x117.46，x245.76，x35.546,16,PPT学习交流,解 用顺序Gauss消去法求解，消元过程如下,17,PPT学习交流,经回代求解得 x35.546，x2100.0，x1104.0,和此方程组的精确解相比,x35.546 ，x245.76， x117.46,有较大的误差。,对于此例，由于顺序Gauss消去法中的主元素绝对值非常小，使消元乘数绝对值非常大，计算过程中出现大数吃掉小数现象，产生较大的舍入误差，最终导致计算解 x1104.0 和 x

7、2100.0 已完全失真。,为避免这种现象发生，可以对原方程组作等价变换，再利用顺序Gauss消去法求解。,18,PPT学习交流,写出原方程组的增广矩阵：,针对第一列找出绝对值最大的元素，进行等价变换：,19,PPT学习交流,求得方程的解为：x35.546，x245.76，x117.46,精确解为： x35.546 ，x245.76， x117.46,由此可见，第二种Gauss消去法的精度明显高于顺序Gauss消去法，我们称它为列主元Gauss消去法。,列主元Gauss消去法与顺序Gauss消去法的不同之处在于：,后者是按自然顺序取主元素进行消元,前者在每步消元之前先选取主元素然后再进行消元,

8、20,PPT学习交流,3.列主元高斯消去法,定义 使用高斯消去法的过程中，在第 k 次消元前，先对第 k 个增广阵 A(k), b(k) 做交换二行的变换，把 中绝对值最大的元素换到 (k, k) 位置，再消元。此方法叫列主元素高斯消去法。,1.消元过程 对于k =1,2,n -1执行 (1)选行号ik，使 (2)交换第 k 行与第 ik 行。,21,PPT学习交流,(3)对于 i = k +1,k +2,n 计算,2.回代过程,22,PPT学习交流,评论：列主元素消去法，所需条件较少，仅仅要求方程组的系数矩阵 A 非奇异。 而且，对一般的方程组，它还具有良好的数值稳定性，其计算量与顺序消去法

9、的计算量相当。,23,PPT学习交流,3.3 矩阵的直接分解法,从3.2中讨论可知，顺序Gauss消去法的消元过程是将增广矩阵A，bA（1），b（1）逐步化为矩阵A（n），b（n）。,可见，在顺序Gauss消去法的过程中，系数矩阵AA（1）经过一系列单位下三角矩阵的左乘运算化为上三角矩阵A（n），即,1.矩阵的三角分解法,24,PPT学习交流,这时,令,容易验证,25,PPT学习交流,从顺序Gauss消去法的矩阵运算表示式可知，系数矩阵A可分解为一个单位下三角矩阵L和一个上三角矩阵U的乘积，即,其中,26,PPT学习交流,定义 A = LU 叫做 A 的三角分解。 L，U 是下、上三角阵. 若

10、 L 是单位下三角矩阵， U 是上三角矩阵，则 A =LU 叫 A 的Doolittle 分解； 若 L 是下三角矩阵，U 是单位上三角矩阵， A =LU 叫 A 的 Crout 分解。,如果方程组 Ax =b 的系数阵 A 能分解为 A =LU, 其中，L 是下三角矩阵，U 是上三角矩阵.,这时解方程组 Ax=b， 可化为求解两个三角方程组 Ly =b, Ux =y . 先由 Ly =b 解出向量 y，再由 Ux =y 解出向量 x， 则 x 是原方程组 Ax=b 的解向量。,三角分解用处,27,PPT学习交流,对于,由,解得,Ly =b,28,PPT学习交流,对于,由,求得,Ux =y,2

11、9,PPT学习交流,可以看出对于方程组：,只要对系数矩阵作了三角分解：,由这个简单的计算过程可知，系数矩阵的三角分解很关键。,通过如下两组公式很容易求解：,Ax =b,A =LU,30,PPT学习交流,以Doolittle（杜利特尔）分解为例,在顺序Gauss消去法的过程中，若每步消元的主元素 akk(k)0，则矩阵A 可分解。而 akk(k) 0 的充要条件是A 的各阶顺序主子式不为零。,单位下三角阵,上三角阵, 矩阵 ARnn 的 Doolittle 分解,31,PPT学习交流,例： 利用Doolittle三角分解法分解矩阵,解：,1,2,3,4,1,1,1,2,6,12,3,7,6,24

12、,6,24,矩阵的三角分解,32,PPT学习交流,如果我们要求解方程组,则由,得到,33,PPT学习交流,由,解得,再由,求得方程组的解：,34,PPT学习交流,解：设,比较两边系数得:,例 用矩阵的杜利脱尔（Doolittle）分解解方程组,35,PPT学习交流,练习1：利用Doolittle三角分解方法解线性方程,解: 进行三角分解ALU，对增广矩阵A,b作三角分解:,1 2 3 -2,-3,2,2,-3,-1,3,3,17,36,PPT学习交流,得到,1 2 3 -2,-3,2,2,-3,-1,3,3,17,这时，相应的方程组为：,37,PPT学习交流,练习2：利用Doolittle三角

13、分解方法解线性方程组,解：对增广矩阵进行三角分解,1 2 3 -4 -2,-3,2,4,2,-3,1,3,3,3,2,2,-4,-1,17,-16,38,PPT学习交流,1 2 3 -4 -2,-3,2,4,2,-3,1,3,3,3,2,2,-4,-1,17,-16,解得,等价方程组通过分解式容易写出为：,39,PPT学习交流,练习： 用矩阵的杜利脱尔（Doolittle）分解 A=LU 解方程组：,答案：,40,PPT学习交流,2.列主元三角分解法,与列主元高斯消去法相对应的是列主元三角分解法。,选主元 D-分解的实施方法 采取与列主元类似的方法，在 D -分解中也选主元素。设使用 D-分解

14、公式 已进行了 k -1 步，第 k -1 次分解矩阵为,41,PPT学习交流,(1)进行第 k 步分解， 先寻找主元素，计算中间量,42,PPT学习交流,(2) 再按公式进行第 k 步的D-分解运算。,满足 的 就是第 k 步的主元素，以 的值作为 。为此，交换矩阵 A(k-1) 的第 k 行与第 ik 行。此时：,43,PPT学习交流,例：用选主元的杜利脱尔（Doolittle）分解解方程组,解：对增广矩阵进行变换，有,44,PPT学习交流,45,PPT学习交流,等价的三角方程组为：,回代求解，得,46,PPT学习交流,3.4 特殊线性方程组解法,1.追赶法,追赶法是专门用于求解三对角方程

15、组的。这类方程组经常出现于用差分方法或有限元方法求解二阶常微分方程边值问题、热传导问题及三次样条函数插值等问题，三对角方程组Axb的系数矩阵具有如下形式：,47,PPT学习交流,并且满足,条件(i)保证方程组不能降阶，条件(ii)保证三角分解可做到底。,在此条件下，可对A进行三角分解，设,A=,48,PPT学习交流,根据矩阵乘法及矩阵相等的定义，有：,则根据该组公式可以对三对角矩阵进行三角分解，对于三对角方程组Axb，设A的三角分解为ALU，则原方程组等价于,Lyb，Uxy,由Lyb求y；再由Uxy求x。,注 追赶法的存贮与计算量都很小，乘除运算总次数为 5n-4。,49,PPT学习交流,练习

16、 试用“追赶法”求解线性代数方程组：,50,PPT学习交流,2.改进的平方根法,改进的平方根法一般用于求解对称线性方程组。,因为A对称，则有：,推导得到：,51,PPT学习交流,3.6 线性方程组的迭代解法,1.问题的提出,1直接方法的缺陷(以Gauss消去法为代表)：,对于低中阶数（n100）的线性方程组十分有效，但n很大时，特别是由某些微分方程数值解所提出来的线性方程组，由于舍入误差的积累以及计算机的存贮困难，直接方法却无能为力。,2解决方法：（利用迭代方法）,迭代方法：把线性方程组的数值求解问题化为一个迭代序列来实现。,52,PPT学习交流,具体做法,(2) 取任意初始向量 x(0) 构

17、成迭代序列:,由于迭代方法能避免系数矩阵中零元的存贮与计算，特别适用于解系数矩阵阶数很高而非零元极少（即大型稀疏）的线性方程组。,53,PPT学习交流,迭代格式：,定义：,迭代矩阵：,迭代过程收敛：,若序列x(k)极限存在，称此迭代过程收敛，否则称为发散。,3. 需要讨论的问题：,怎样建立迭代格式；迭代过程是否收敛，误差分析；如何加快收敛速度等等。,迭代法计算精度可控，特别适用于求解系数为大型的方程组。,54,PPT学习交流,2.雅可比迭代法,迭代格式：,缩写为：,按此格式迭代求解的方法称为雅可比迭代法,简称J法。,55,PPT学习交流,写成矩阵形式：,L,U,D,分裂 A = D+ L+U,

18、拆分A为三个部分。,56,PPT学习交流,Jacobi 迭代矩阵,那么，原方程组与下面的迭代方程组同解：,D,L,U 的具体形式,57,PPT学习交流,J,58,PPT学习交流,J,59,PPT学习交流,例： 用雅可比迭代法解线性方程组,解 生成雅可比迭代格式：,从此表可以看出，迭代序列收敛于x*，若取x(12)作为近似解，则误差不超过 10-5,60,PPT学习交流,3.高斯-赛德尔迭代法, ,矩阵形式：,Gauss-Seidel 迭代阵，简记为G,61,PPT学习交流,G-S迭代,Jacobi迭代、G-S迭代计算式：,62,PPT学习交流,解,原方程等价于,63,PPT学习交流,建立Jacobi迭代格式如下,建立Gauss-Seidel迭代格式如下,64,PPT学习交流,4.逐次超松弛迭代法,SOR是GS迭代法的一种加速方法，是解大型稀疏矩阵方程组的有效方法之一。它具