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

《数值计算方法课件第3章线性方程组的解法.ppt》由会员分享，可在线阅读，更多相关《数值计算方法课件第3章线性方程组的解法.ppt（77页珍藏版）》请在三一办公上搜索。

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

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

3、公元前250年我国就掌握了解三元一次联立方程组的方法）。但由于它改进、变形得到的主元素消去法、三角分解法仍然是目前计算机上常用的有效方法。,用一个简单的例子说明消去法的基本思想。,解(1)化上三角方程组,(2)回代过程.得到下同解方程组后,如下处理,从下向上逐步求解,把x3的值代入求x2,用x3,x2的值求x1,对应的增广矩阵的变化,(-2)r1+r3r3,r2+r3 r3,1.基本思想,将原方程组逐次消去未知元，变为与之同解的上三角方程组，再回代求解。,用矩阵语言叙述，上述过程是使用初等行变换把增广阵约化为上三角阵，使用上三角方程组，回代求解。,2.算法构造,根据下面的上三角方程组,逐次回代

4、求解 xk,22,n-1,n-1,定义：在使用高斯消去法的过程中，仅对方程组做倍加变换，就形成了顺序高斯消去法。,顺序高斯消去法求解n 元线性方程组的乘除运算总次数为：,顺序高斯消去法计算过程中出现的 称为主元素.出现，消元过程就进行不下去了。,定理:顺序高斯消去法的前 n-1 个主元素 均不为零的充要条件是方程组的系数矩阵A的前n-1个顺序主子式,顺序Gauss消去法计算过程中的 akk(k)称为主元素，在第k步消元时要用它作除数,则可能会出现以下几种情况,1、若出现 akk(k)0，消元过程就不能进行下去。,2、akk(k)0，消去过程能够进行，但若|akk(k)|过小，也会造成舍入误差积

5、累很大导致计算解的精度下降。,顺序高斯消去法的数值稳定性是没有保证的!,顺序主元素消去法可能计算失败之例,例：单精度解方程组,用顺序主元素消去法计算：,8个,小主元/*Small pivot element*/可能导致计算失败。,例：在四位十进制的限制下，试用顺序Gauss消去法求解如下方程组,此方程组具有四位有效数字的精确解为,x117.46，x245.76，x35.546,解 用顺序Gauss消去法求解，消元过程如下,经回代求解得 x35.546，x2100.0，x1104.0,和此方程组的精确解相比,x35.546，x245.76，x117.46,有较大的误差。,对于此例，由于顺序Gau

6、ss消去法中的主元素绝对值非常小，使消元乘数绝对值非常大，计算过程中出现大数吃掉小数现象，产生较大的舍入误差，最终导致计算解 x1104.0 和 x2100.0 已完全失真。,为避免这种现象发生，可以对原方程组作等价变换，再利用顺序Gauss消去法求解。,写出原方程组的增广矩阵：,针对第一列找出绝对值最大的元素，进行等价变换：,求得方程的解为：x35.546，x245.76，x117.46,精确解为：x35.546，x245.76，x117.46,由此可见，第二种Gauss消去法的精度明显高于顺序Gauss消去法，我们称它为列主元Gauss消去法。,列主元Gauss消去法与顺序Gauss消去法

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

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

9、 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 的解向量。,三角分解用处,对于,由,解得,Ly=b,对于,由,求得,Ux=y,可以看出对于方程组：,只要对系数矩阵作了三角分解：,由这个简单的计算过程可知，系数矩阵的三角分解很关键。,通过如下两组公式很容易求解：,Ax=b,A=LU,以Doolittle（杜利

10、特尔）分解为例,在顺序Gauss消去法的过程中，若每步消元的主元素 akk(k)0，则矩阵A 可分解。而 akk(k)0 的充要条件是A 的各阶顺序主子式不为零。,单位下三角阵,上三角阵,矩阵 ARnn 的 Doolittle 分解,例：利用Doolittle三角分解法分解矩阵,解：,1,2,3,4,1,1,1,2,6,12,3,7,6,24,6,24,矩阵的三角分解,如果我们要求解方程组,则由,得到,由,解得,再由,求得方程组的解：,解：设,比较两边系数得:,例 用矩阵的杜利脱尔（Doolittle）分解解方程组,练习1：利用Doolittle三角分解方法解线性方程,解:进行三角分解ALU，

11、对增广矩阵A,b作三角分解:,1 2 3-2,-3,2,2,-3,-1,3,3,17,得到,1 2 3-2,-3,2,2,-3,-1,3,3,17,这时，相应的方程组为：,练习2：利用Doolittle三角分解方法解线性方程组,解：对增广矩阵进行三角分解,1 2 3-4-2,-3,2,4,2,-3,1,3,3,3,2,2,-4,-1,17,-16,1 2 3-4-2,-3,2,4,2,-3,1,3,3,3,2,2,-4,-1,17,-16,解得,等价方程组通过分解式容易写出为：,练习：用矩阵的杜利脱尔（Doolittle）分解 A=LU 解方程组：,答案：,2.列主元三角分解法,与列主元高斯消

12、去法相对应的是列主元三角分解法。,选主元 D-分解的实施方法 采取与列主元类似的方法，在 D-分解中也选主元素。设使用 D-分解公式 已进行了 k-1 步，第 k-1 次分解矩阵为,(1)进行第 k 步分解，先寻找主元素，计算中间量,(2)再按公式进行第 k 步的D-分解运算。,满足 的 就是第 k 步的主元素，以 的值作为。为此，交换矩阵 A(k-1)的第 k 行与第 ik 行。此时：,例：用选主元的杜利脱尔（Doolittle）分解解方程组,解：对增广矩阵进行变换，有,等价的三角方程组为：,回代求解，得,3.4 特殊线性方程组解法,1.追赶法,追赶法是专门用于求解三对角方程组的。这类方程组

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

14、解对称线性方程组。,因为A对称，则有：,推导得到：,3.6 线性方程组的迭代解法,1.问题的提出,1直接方法的缺陷(以Gauss消去法为代表)：,对于低中阶数（n100）的线性方程组十分有效，但n很大时，特别是由某些微分方程数值解所提出来的线性方程组，由于舍入误差的积累以及计算机的存贮困难，直接方法却无能为力。,2解决方法：（利用迭代方法）,迭代方法：把线性方程组的数值求解问题化为一个迭代序列来实现。,具体做法,(2)取任意初始向量 x(0)构成迭代序列:,由于迭代方法能避免系数矩阵中零元的存贮与计算，特别适用于解系数矩阵阶数很高而非零元极少（即大型稀疏）的线性方程组。,迭代格式：,定义：,迭

15、代矩阵：,迭代过程收敛：,若序列x(k)极限存在，称此迭代过程收敛，否则称为发散。,3.需要讨论的问题：,怎样建立迭代格式；迭代过程是否收敛，误差分析；如何加快收敛速度等等。,迭代法计算精度可控，特别适用于求解系数为大型的方程组。,2.雅可比迭代法,迭代格式：,缩写为：,按此格式迭代求解的方法称为雅可比迭代法,简称J法。,写成矩阵形式：,L,U,D,分裂 A=D+L+U,拆分A为三个部分。,Jacobi 迭代矩阵,那么，原方程组与下面的迭代方程组同解：,D,L,U 的具体形式,J,J,例：用雅可比迭代法解线性方程组,解 生成雅可比迭代格式：,从此表可以看出，迭代序列收敛于x*，若取x(12)作

16、为近似解，则误差不超过 10-5,3.高斯-赛德尔迭代法,矩阵形式：,Gauss-Seidel 迭代阵，简记为G,G-S迭代,Jacobi迭代、G-S迭代计算式：,解,原方程等价于,建立Jacobi迭代格式如下,建立Gauss-Seidel迭代格式如下,4.逐次超松弛迭代法,SOR是GS迭代法的一种加速方法，是解大型稀疏矩阵方程组的有效方法之一。它具有计算公式简单、程序设计容易、占用计算机内存较少等优点，但需要选择好的加速因子（最佳松驰因子）。首先用GS法定义辅助量：,加入松弛因子：,注：显然，当=1，SOR方法即为GS迭代法。SOR方法每迭代一次主要运算量是计算一次矩阵与向量的乘法。当 1时

17、，称为超松驰法；当1时，称为低松驰法。,SOR迭代的矩阵形式：,fw,SOR 迭代矩阵,5.迭代法的收敛性,2.Gauss-Seidel方法收敛的条件,（充分条件）若A 为严格对角占优阵，则解 的Jacobi 和 Gauss-Seidel 迭代法均收敛。,3、其它判别条件,定理,定理,定理,（1）列出求解该方程组的Jacobi迭代格式，并判别是否收敛；（2）列出求解该方程组的Gauss-Seidel迭代格式，并判别是否收敛；（3）取x(0)=(0,0,0)T，求Gauss-Seidel迭代法的前两次迭代值x(1),x(2).,例：,考察系数矩阵A及2D-A,由于A及2D-A都正定，故Jacobi迭代法收敛。,考察系数矩阵A,由于A对称正定，故Gauss-Seidel迭代法收敛。,谢谢大家！,