Chapt-4 线性代数方程组的数值解法.ppt

第四章线性代数方程组的数值解法,4.1概述线性代数方程组(SystemofLinearAlgebraEquations)的求解是数值计算方法中的一个重要课题。现代工程技术或科研过程中所遇到的一些实际问题，常常直接或间接地归结为求解一个线性代数方程组。例如有分支水流的流速分布、建筑结构中的设计计算和应力分析、仪器分析中的质谱分析、光谱分析、色谱分析、电力系统中的电网分析等等；另外有些数值计算方法本身也是以线性代数方程组的数值解、有限元法和边界元等等，其中间过程或者最后都会导致求解线性代数方程组。这些线性代数方程组的解法是十分必要的，有着十分重要的意义。,4.1概述,本章介绍求解n阶线性代数方程组的一般形式是：或简写成矩阵形式：其中A称为方程组(4.1)式的系数矩阵；B称为方程组的右端列向量；x称谓方程组解的列向量。它们分别为,(4.1),(4.2),4.1概述,求解线性代数方程组的数值计算方法很多，大致可分为两大类：消去（元）法和迭代法。消去法是直接从方程组的系数矩阵入手，经过有限步运算求出方程组的精确解（假如没有舍入误差的话）。迭代法则是将求方程组的问题化为构造一组递推计算结构，从一组近似解出发，用这组递推结构逐步算出精度更高的近似解。上述这两类算法各有其优点和缺点，消去法的计算量小，但程序复杂；迭代法计算量大，精度不高，但程序结构简单。本章将主要介绍求解线性代数方程组的简单高斯消去法和三角分解法，迭代法将在以后相关章节中介绍。,4.2高斯消去法,4.2.1高斯消去法的基本步骤我们以三元线性代数方程组为例，叙述简单高斯消去法（以下简称为消去法）的基本步骤，这各方法是理解其它方法的基础，消去法分为消元和回代两个过程。例4-1：消去过程实际上是对增广矩阵作行初等变换。上例可表示为,4.2高斯消去法,这是上三角方程组，它极容易求解：由第三个方程得，代入第二个方程得，再代入第一方程。此一过程称为回代过程。从上述消元过程可以看出，三元议程组要经过两次消元（因为不用消）才能把增广矩阵化为拟上三角矩阵。对于一般的n元线性代数方程组，经经过(n-1)次消元才能把相应的增广矩阵变换为拟上三角矩阵。n元线性代数方程组的增广矩阵的一般形式如(4.3)式。,4.2高斯消去法,以下是消元步骤（共分n-1部）：第一步(k=1)：从第一列中消去第2n行中x1的系数，即消去a11下方元素；第二步(k=2)：从第一列中消去第3n行中x2的系数，即消去a22下方元素；,(4.3),4.2高斯消去法,第j步(k=j)：从第j列中消去第j+1n行中xj的系数；即消去ajj下方元素;第n-1步(k=n-1)：从第n-1列中消去第n行中xn-1的系数；即消去an-1n-1下方元素因此，高斯消元步骤的计算通式可写为：,(4.4),4.2高斯消去法,经过n-1步消元后，增广矩阵(4.3)式变为：,(4.5),4.2高斯消去法,高斯回代过程的通用递推计算公式可写为：,(4.6),4.2高斯消去法,4.2.2高斯消去法的计算量分析我们从(4-4)式可以看出，高斯消去法消去过程共分n-1步，第k步变换n-k行：对这些行先乘系数，再从n+1-k元素减去第k行相对应列的元素；因此共需乘、除次数为回代过程求xn需1次除法，求xn-1需1次乘法、1次除法，求x1需n-1次乘法、1次除法，因此共需乘除次数两过程共需要乘除次数为。当n=20时，N=3060.,4.2高斯消去法,4.2.2高斯消去法的程序框图与通用程序,START,INPUTN,A(),B,CALLelimination,CALLback,OUTPUTX(N),END,4.2高斯消去法,10OPEN(8,或在kn行、kn列选绝对值最大的元素apq，交换k、p行和k、p列，然后继续进行消去过程。这两种消去法为行主元消去法和全主元消去法。本节讨论应用广泛且易于在计算机上实现的列主元素消去法。列主元素消去法的计算步骤可归纳如下：选主元素；把主元素所在的行与第k行互换；消元；回代,4.2高斯消去法,其中、两步与简单高斯消去法中的消元与回代过程完全一样，也就是说，列主元消去法是在简单消去法的基础上引入选列主远过程，这个过程并不影响获得正确结果。列主元高斯消去法的程序框图与通用程序为了简单和说明问题，将上面的和两步单独用一个子程序。因此，列主元高斯消去法的程序框图只需在简单高斯消去法的流程图中增加一个选列主元子程序gaussp，具体如下：,4.2高斯消去法,SUBROUTINEgaussp,k=1,n-1,a(p,j)=t,i=k+1,n,c=abs(a(i,k);p=i,endi,t=a(k,j);a(k,j)=a(p,j),endj,ENDSUBROUTINEgaussp,c=abs(a(k,k);p=k,Ifabs(a(i,K)c?,Y,N,j=1,n+1,endk,4.2高斯消去法,10SUBROUTINEgaussp(a,b,n)20DIMENSIONa(n,n+1),b(n)30C生成增广矩阵40DOi=1,n50a(i,n+1)=b(i)60ENDDO70C选主元开始80DOk=1,n-190c=abs(a(k,k);p=k100DOi=k+1,n110IF(abs(a(i,k)c)THEN120c=a(i,k);p=i130ENDIF140Cp,k行交换开始,150DOj=1,n+1160t=a(k,j);a(k,j)=a(p,j)170a(p,j)=t180ENDDO190ENDDO200ENDSUBROUTINEgaussp,4.2高斯消去法,4.2.4高斯-约当法前面所讲的是如何将一个线性方程组的系数矩阵改变为一个上三角矩阵，然后回代求解。本节所讲的是如何将系数矩阵改变为一个对角矩阵，即，除对角线元素外，其他元素均为零,4.2高斯消去法,列主元高斯-约旦消元过程的递推计算通式结构为：高斯-约旦消去法消元过程的计算量比高斯消去法有所增加（约为1.3倍），但是总的计算量增加并不大，另一方面，这一方法的程序结构简单，所以在实际中得到了广泛的应用。高斯-约旦消去法的程序框图与通用程序自行设计。,改进后,(4.8),(4.7),4.3三角分解法,线性方程组的另一直接解法是三角形分解法，即方程组（4-2）的系数矩阵A分解成两个形式简单的三角形矩阵L和U的乘积：A=LU。从而求解Ax=b的问题转化为三角形方程组Lx=yUy=b其中,(4.9),(4.10),4.3三角分解法,比较等式左边和右边乘积矩阵LU的第r行主角元右边（含主角元）的对应元素，得再比较等式两边第r列主角元以下（不含主角元）的对应元素，得当r=1时，有,(4.11),(4.12),(4.13),(4.14),4.3三角分解法,假定已求出U的第1至第n-1行和L的第1至第n-1列，由（4-11）式计算出U的第r行元素和由（4-12）式计算出L的第r列元素（4-13）式至（4-16）式所表示的矩阵分解称Doolittle分解。类似地，若U为单位上三角矩阵，而L为下三角矩阵，则有,(4.15),(4.16),(4.17),4.3三角分解法,规定。称上述分解为Crout分解。实现了系数矩阵A的Doolittle或Crout分解后，方程组Ax=b可以分解成为Ly=b和Ux=b这两个三角矩阵来进行求解。设U为上三角矩阵，而L为单位下三角矩阵，并且，根据公式（4-4）和（4-6）得与Doolittle分解相对应的方程组解为,(4.18),(4.19),4.3三角分解法,类似地，与Crout分解相应的求解公式,(4.20),(4.21),4.3三角分解法,无论Doolittle分解还是Crout分解，其运算量均小于高斯消去法。为保证它们能顺利、稳定进行，也可选列主元。用Crout分解法求解方程组Ax=b的步骤如下：用（4-17）式求lir;确定最大列主元；用（4-18）式求uir,进行分解；回代。通用公式为,(4.22),(4.23),4.3追赶法,求解三对角占优方程组若作Crout分解，则有,4.3追赶法,比较Crout解，易知回代得。,(4.24),(4.25),4.3追赶法,按照以上公式求解Ax=b的方法就叫做追赶法，其中ui、li和yi称追，回代称赶，乘除法运算量仅为5n-4，远比一般方程组的高斯消去法或三角分解法的运算量少。不用选主元，就可保证顺利、稳定进行计算。,4.4舍入误差对解的影响,本节研究线性代数方程组解的误差。衡量数的误差用绝对值。方程组的解是向量，衡量其误差，自然也会想到绝对值的概念。4.4.1向量与矩阵范数众所周知，数x的绝对值x是x的函数:x=(x),具有以下三性质：（1）（2）对任意实数（3）推广到向量，具有如下类似性质的函数：。该函数成为向量x的范数或模或长度，它也应该具有以下性质：（1）非负性（2）齐次性：对任意实数（3）三角不等式：,4.4舍入误差对解的影响,几何上三角不等式表示：在以向量x、y及其和x-y构成的三角形中，一边之长不超过另两边边长之和，即从而表示以x、y和x-y为边的三角形中，一边之长不小于另两边边长之差。常用向量范数有3种，即：分别称为1范数、2范数和无穷大范数。不难验证它们具有性质（1）和（2）。对于性,4.4舍入误差对解的影响,性质（3），这里已2范数为例，给出证明，以供参考。最后不等式称Cauchy不等式。注意对任意实数,4.4舍入误差对解的影响,由二次式的判别式，便可推出Cauchy不等式，因而2范数的性质（3）得证。对于n阶方阵，具有如下4种性质的函数称为矩阵范数。（1）（2）对任意实数（3）（4）容易验证矩阵函数具有上述4种性质，因而，它是一种范数，称为矩阵的F范数。常用矩阵范数是如下三种范数：,4.4舍入误差对解的影响,其中表示矩阵的谱半径，即特征值绝对值的最大值。三种范数分别称为1范数或列范数，无穷大范数或行范数，2范数或谱范数。可以证明，矩阵的这三种范数还具有以下3种性质：（满足性质（1）的矩阵范数成为相容范数）（1）（2）单位矩阵I的范数（3）时可逆且,(4.26),4.4舍入误差对解的影响,例4-3设则,4.4舍入误差对解的影响,它的三个根为4.4.1误差分析设线性方程组Ax=b中，A为非奇异矩阵，x为方程组的精确解。假定b有误差b,则解为x+x,即,4.4舍入误差对解的影响,即两边取范数又因由（4-30）和（4-31）式，得另外，若矩阵A有误差A，则解为x+x，即,(4.27),(4.28),(4.29),(4.30),(4.31),(4.32),(4.33),4.4舍入误差对解的影响,即有虽然A为非奇异，但不能保证A+A也为非奇异，为保证A+A为非奇异，需对A作些限制。因为由（4-26）式，若，则存在，因此（4.35)式变为由（4-34）和（4-35）式，得两边取范数,(4.34),(4.35),(4.36),(4.37),(4.38),4.4舍入误差对解的影响,设，则得从（4-32）和（4-39）式可以看出，如果线性方程组Ax=b中，A或的微小变化，都将引起方程解x为倍，若这个倍数巨大，则方程组定义为“病态方程组”，矩阵A为“病态矩阵”，否则定义为“病态方程