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

第3章 线性方程组的解法,3.1 问题综述,在自然科学与社会科学的研究中，常常需要求解线性代数方程组，这些方程组的系数矩阵大致分为两种：一种是低阶稠密矩阵（例如：阶数大约为小于等于150），另一种是大型稀疏矩阵（即矩阵阶数高且零元素较多）。,在计算机上求解线性代数方程组 Ax=b 的常用的数值解法：1、直接法：就是经过有限次算术运算，可求得方程组精确解的方法（若计算过程中没有舍入误差）。但实际计算中由于舍入误差的存在和影响，这种方法也只能求得线性方程组的近似解。这类方法是解低阶稠密矩阵及大型带状方程组的有效方法。,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消去法是一个古老的求解线性代数方程组的方法（早在公元前250年我国就掌握了解三元一次联立方程组的方法）。但由于它改进、变形得到的主元素消去法、三角分解法仍然是目前计算机上常用的有效方法。,用一个简单的例子说明消去法的基本思想。,解(1)化上三角方程组,(2)回代过程.得到下同解方程组后,如下处理,从下向上逐步求解,把x3的值代入求x2,用x3,x2的值求x1,对应的增广矩阵的变化,(-2)r1+r3r3,r2+r3 r3,1.基本思想,将原方程组逐次消去未知元，变为与之同解的上三角方程组，再回代求解。,用矩阵语言叙述，上述过程是使用初等行变换把增广阵约化为上三角阵，使用上三角方程组，回代求解。,2.算法构造,根据下面的上三角方程组,逐次回代求解 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)|过小，也会造成舍入误差积累很大导致计算解的精度下降。,顺序高斯消去法的数值稳定性是没有保证的!,顺序主元素消去法可能计算失败之例,例：单精度解方程组,用顺序主元素消去法计算：,8个,小主元/*Small pivot element*/可能导致计算失败。,例：在四位十进制的限制下，试用顺序Gauss消去法求解如下方程组,此方程组具有四位有效数字的精确解为,x117.46，x245.76，x35.546,解 用顺序Gauss消去法求解，消元过程如下,经回代求解得 x35.546，x2100.0，x1104.0,和此方程组的精确解相比,x35.546，x245.76，x117.46,有较大的误差。,对于此例，由于顺序Gauss消去法中的主元素绝对值非常小，使消元乘数绝对值非常大，计算过程中出现大数吃掉小数现象，产生较大的舍入误差，最终导致计算解 x1104.0 和 x2100.0 已完全失真。,为避免这种现象发生，可以对原方程组作等价变换，再利用顺序Gauss消去法求解。,写出原方程组的增广矩阵：,针对第一列找出绝对值最大的元素，进行等价变换：,求得方程的解为：x35.546，x245.76，x117.46,精确解为：x35.546，x245.76，x117.46,由此可见，第二种Gauss消去法的精度明显高于顺序Gauss消去法，我们称它为列主元Gauss消去法。,列主元Gauss消去法与顺序Gauss消去法的不同之处在于：,后者是按自然顺序取主元素进行消元,前者在每步消元之前先选取主元素然后再进行消元,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 非奇异。而且，对一般的方程组，它还具有良好的数值稳定性，其计算量与顺序消去法的计算量相当。,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 分解；若 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（杜利特尔）分解为例,在顺序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，对增广矩阵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.列主元三角分解法,与列主元高斯消去法相对应的是列主元三角分解法。,选主元 D-分解的实施方法 采取与列主元类似的方法，在 D-分解中也选主元素。设使用 D-分解公式 已进行了 k-1 步，第 k-1 次分解矩阵为,(1)进行第 k 步分解，先寻找主元素，计算中间量,(2)再按公式进行第 k 步的D-分解运算。,满足 的 就是第 k 步的主元素，以 的值作为。为此，交换矩阵 A(k-1)的第 k 行与第 ik 行。此时：,例：用选主元的杜利脱尔（Doolittle）分解解方程组,解：对增广矩阵进行变换，有,等价的三角方程组为：,回代求解，得,3.4 特殊线性方程组解法,1.追赶法,追赶法是专门用于求解三对角方程组的。这类方程组经常出现于用差分方法或有限元方法求解二阶常微分方程边值问题、热传导问题及三次样条函数插值等问题，三对角方程组Axb的系数矩阵具有如下形式：,并且满足,条件(i)保证方程组不能降阶，条件(ii)保证三角分解可做到底。,在此条件下，可对A进行三角分解，设,A=,根据矩阵乘法及矩阵相等的定义，有：,则根据该组公式可以对三对角矩阵进行三角分解，对于三对角方程组Axb，设A的三角分解为ALU，则原方程组等价于,Lyb，Uxy,由Lyb求y；再由Uxy求x。,注 追赶法的存贮与计算量都很小，乘除运算总次数为 5n-4。,练习 试用“追赶法”求解线性代数方程组：,2.改进的平方根法,改进的平方根法一般用于求解对称线性方程组。,因为A对称，则有：,推导得到：,3.6 线性方程组的迭代解法,1.问题的提出,1直接方法的缺陷(以Gauss消去法为代表)：,对于低中阶数（n100）的线性方程组十分有效，但n很大时，特别是由某些微分方程数值解所提出来的线性方程组，由于舍入误差的积累以及计算机的存贮困难，直接方法却无能为力。,2解决方法：（利用迭代方法）,迭代方法：把线性方程组的数值求解问题化为一个迭代序列来实现。,具体做法,(2)取任意初始向量 x(0)构成迭代序列:,由于迭代方法能避免系数矩阵中零元的存贮与计算，特别适用于解系数矩阵阶数很高而非零元极少（即大型稀疏）的线性方程组。,迭代格式：,定义：,迭代矩阵：,迭代过程收敛：,若序列x(k)极限存在，称此迭代过程收敛，否则称为发散。,3.需要讨论的问题：,怎样建立迭代格式；迭代过程是否收敛，误差分析；如何加快收敛速度等等。,迭代法计算精度可控，特别适用于求解系数为大型的方程组。,2.雅可比迭代法,迭代格式：,缩写为：,按此格式迭代求解的方法称为雅可比迭代法,简称J法。,写成矩阵形式：,L,U,D,分裂 A=D+L+U,拆分A为三个部分。,Jacobi 迭代矩阵,那么，原方程组与下面的迭代方程组同解：,D,L,U 的具体形式,J,J,例：用雅可比迭代法解线性方程组,解 生成雅可比迭代格式：,从此表可以看出，迭代序列收敛于x*，若取x(12)作为近似解，则误差不超过 10-5,3.高斯-赛德尔迭代法,矩阵形式：,Gauss-Seidel 迭代阵，简记为G,G-S迭代,Jacobi迭代、G-S迭代计算式：,解,原方程等价于,建立Jacobi迭代格式如下,建立Gauss-Seidel迭代格式如下,4.逐次超松弛迭代法,SOR是GS迭代法的一种加速方法，是解大型稀疏矩阵方程组的有效方法之一。它具有计算公式简单、程序设计容易、占用计算机内存较少等优点，但需要选择好的加速因子（最佳松驰因子）。首先用GS法定义辅助量：,加入松弛因子：,注：显然，当=1，SOR方法即为GS迭代法。SOR方法每迭代一次主要运算量是计算一次矩阵与向量的乘法。当 1时，称为超松驰法；当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迭代法收敛。,谢谢大家！,