数学与应用数学毕业论文-求方程的近似解方法及比较分析.doc

淮 北 师 范 大 学 2012届学士学位论文 求方程的近似解方法及比较分析学院、专业数学科学学院 数学与应用数学研 究 方 向 求方程的近似解 学 生 姓 名 学 号 指导教师姓名 指导教师职称 讲师 2012年 3 月 7 日题目：求方程的近似解方法及比较分析（淮北师范大学数学科学学院，淮北，235000）摘 要目前在许多实际应用领域,诸如航空、造船以及其它结构工程中,常遇到求解大型线性代数方程组的问题。本文根据线性代数方程组的雅可比迭代法、lu分解法及高斯列主元消去法三种解法进行了比较，用以方便在实际生活应用中更好的作出选择。在第二章中本文详细的介绍了线性代数方程组的三种解法的理论知识与证明过程。为了更加清晰的展现三种方法的不同点以及其各自的优越性，本文在第三章中给出了实例，通过实例的计算与程序的实现，再结合三种方法的优缺点进行了比较。 关键词：线性代数方程组、迭代法、lu分解法、高斯消去法、列主元消去法、不同点、比较the approximate solution method for equation and comparative analysisjian bin sun(school of mathematical science, huaibei normal univercity, huaibei, 235000)abstract at present in many practical applications fields, such as aerospace, shipbuilding and other structure engineering, often meet to solve large-scale linear algebra equations. this paper based on linear algebra equations jacobi iterative method, lu decomposition method and gaussian listed the primary elimination technique three method are compared, and easy to apply in real life in better to make a choice. in the second chapter of this paper introduces the linear algebra equations of three kinds of solution and the theoretical knowledge of that process. in order to more clear show three methods of differences and their respective superiority, the paper in the third chapter gives an example, through the examples of calculation and program implementation, combined with 3 kindsand the advantages and disadvantages of the methods are compared.key words ：linear algebra equations, iterative method, lu decomposition method, the gaussian elimination method, and all the primary elimination method, the differences, the comparison 目 录第一章、引 言.4 第二章、求解线性方程组的基本理论2.1、迭 代 法.62.2、直 角 三 角 形 分 解 法.7 2.3、高 斯 列 主 元 消 去 法.9第三章、三种算法求解方程组实例3.1迭代法.103.2 直接三角分解法.113.3 高斯列主元消去法.123.4 三种方法的优缺点比较.13参考文献.14致 谢.15第一章 引 言在自然科学、工程技术、经济和医学各领域中产生的许多实际问题都可以通过数学语言描述为数学问题，也就是说，由实际问题建立数学模型，然后应用各种数学方法和技巧来求解，最后把结果反馈到实际应用中去。例如电学中的网络问题，船体数学放样中建立三次样条函数问题，用最小二乘法求实验数据的曲线拟合问题，解非线性方程组的问题，用差分法或者有限元方法解常微方程。偏微分方程边值问题等都导致求解线性代数方程组，二这些方程组的系数矩阵大致分为两种，一种是低阶稠密矩阵（例如，阶数不超过150），本文的编写由以下几个特点：另一种是大型稀疏矩阵（即矩阵阶数高且零元素较多的）。本文主要是分析高斯列主元消去法、矩阵的lu分解法和简单迭代法理论上的异同，并用c语言程序通过具体实例进行了分析比较。1、对于难点问题从具体模型引入，淡化抽象的概念与定理，通俗易通；2、对于具体模型本文给出了多种解题的思想及方法；3、对问题进行简洁易懂的理论证明，突出了线性代数的理论和基本思想，使数学方法更加利于理解掌握。4、简要分析了算法的计算效果、稳定性、收敛效果、计算精度以及优劣性。第二章 求解线性方程组的基本理论2.1 迭代法迭代法的基本思想：是将线性方程组转化为便于迭代的等价方程组，对任选一组初始值xi（i=1,2n），按某种计算规则，不断地对所得到的值进行修正，最终获得满足精度要求的方程组的近似解。对于线性方程组ax=b 其中，a为非奇异矩阵。将a分裂为a=m-n，其中，m为非奇异矩阵，且要求线性代数方程组mx=d容易求解，一般选择为a的某一部分元素构成的矩阵，称m为a的分裂矩阵。于是，求解ax=b转化为求解mx=nx+b,由此可构造一个迭代法： x(0)(初始向量) ， x(k+1)=bx(k)+f (k=0,1,2) 其中，f=b/m,b=i-a/m为迭代法的迭代矩阵。选取m为a的对角元素组成的矩阵，即选取m=d，可得到解ax=b的雅克比迭代法：x(0)(初始向量),x(k+1)=bx(k)+f (k=0,1,2) bj为求解ax=b的雅克比迭代法的迭代矩阵。解雅克比迭代法的计算公式为： （k=0,1,2，:i=1,2,3,.n）雅克比方法是求对称矩阵的全部特征值以及相应的特征向量的一种方法，它是基于以下两个结论：1)任何实对称矩阵a可以通过正交相似变换成对角型，即存在正交矩阵q，使得 qtaq=diag(1,2,n) 其中i（i=1,2,n）是a的特征值，q中各列为相应的特征向量。2）在正交相似变换下，矩阵元素的平方和不变。即设a=(aij)n*n ，q为交矩阵，记b=qtaq=(bij)n*n,则i,j=1naij2=i,j=1nbij2雅克比方法的基本思想：是通过一次正交变换，将a中的一对非0的非对角线化成0，并且使得非对角元素的平方和减小。反复进行上述过程，使变换后的矩阵的非对角元素的平方和趋于0，从而使该矩阵近似为对角矩阵，得到全部特征值和特征向量。2.2 直接三角分解法 矩阵直接三角分解法：是高斯消去法的变形方法。高斯消去法有多种变形，有的是高斯消去法的改进，有的是用于某种特殊系数矩阵的化简。高斯消去法解线性方程组先消元，然后再回代。当用矩阵描述时，是对系数矩阵分解为一个上三角阵和一个下三角阵的乘积，即lu分解。因此，高斯消去法与矩阵的lu分解是一致的。将高斯消去法改写为紧凑形式，可以直接从矩阵a的元素得到计算l，u元素的递推公式，而不需要任何中间步骤，这就是所谓的直接三角分解法，一旦实现了矩阵a的lu分解，那么求解ax=b的问题就等价于求解两个三角形方程组：ly=b, 求xux=y, 求y 的问题，而这两个线性代数方程组只要回代，就可以求出其解。设a为非奇异矩阵，且有分解式a=lu，其中l为单位下三角矩阵，u为单位上三角矩阵，a=10 0l211 0 ln1 ln2 1 u11 u12u1n0 u22u2n 0 0 unn 第一步，用l的第一行分别乘以u的第j(j=1,2,n)列，比较两边可得a1j=u1j(j=1,2,n) 分别用l的第i(i=1,2,n)行乘u的第一列，比较可得ai1=li1u11(i=1,2,n) 即得 li1=ai1u11 (i=1,2,n) 这样就求出了l的第一列和u的第一行的所有元素。依次进行下去，一直到第k-1步，即已求出l的前k-1列和u的前k-1行的所有元素。第k步，用l的第k行分别乘u的第j(j=k,k+1,n)列，比较两边可得：akj=lk1u1j+lk,k-1uk-1,j+ukj (j=k,k+1,n) 分别用l的第i(i=k+1,n)行乘u的第k列，比较两边可得：aik=li1uik+li,k-1uk-1,k+likukk (i=k+1,n)总结上述讨论，得到用直接三角分解法求解ax=b的计算公式： u1j=a1j (j=1,2,n), li1=ai1u11 (i=2,3,n) ukj=akj-m=1k-1lkmumj (j=k,k+1,n) lik=aik-m=1k-1limumkukk (i=k+1,k+2,n)及求解ly=b,ux=y的计算公式：y1=b1yk=bk-j=1k-1lkjyj (k=2,3,n)， xn=ynunnxk=yk-j=k+1nukjxjukk (k=n-1,n-2,2,1)2.3 高斯列主元消去法 高斯顺序消去法的基本思想是：对线性代数方程组所对应的增广矩阵（a|b）进行一系列“把某一行的非零常数倍加到另一行上”的初等变换，使得（a|b）中a的对角线一下的元素全变为0，从而使原方程组等价的转化为容易求解的上三角形线性代数方程组，再通过回代得到上三角形线性代数方程组的解，即可求得原方程组的解。设线性方程组的增广矩阵为=a11 a12a1nb1a21 a22a2nb2 an1 an2 annbn首先，在第一列中选取绝对值最大的元素ai1(1)作为第一列的主元，即 |ai1(1)|=max1kn|ak1(1)|0 然后交换第一行与第i行，经一次消元计算得：a(1)=(ab)a(2)=(a2b2) ，此消去过程与高斯顺序消去法完全相同。 重复上述过程，设已完成第k-1步的选主元素，交换两行及消元过程后(ab)已约化为 a(k)=(akbk=a111 a121 a1k1 a1n1 b11 a222 a2k2 a2n2 b222 akk(k) akn(k) bk(k) ank(k) ann(k) bn(k) 第k步选主元素，在a(k)右下角方阵的第一列内选取绝对值最大的元素aik(k)作为这一列的主元,即 |aik(k)|=maxksn|ask|0 然后交换a(k)的第i行与第k行，再进行消元计算。如此重复，直到最后将原线性代数方程组化为 a111 a121a1n1 a222a2n2 ann(n) x1x2xn=b11b22bn(n) 回代求解得到 xn=bn(n)an(n)xk=bk(k)-i=k+1naki(k)xiakk(k) (k=n-1,2,1)列主元消去法除了每步需要按列选出主元，然后进行对换外，其消去过程与高斯顺序消去法是相同的。第三章 三种方法求解方程组实例线性代数方程组的应用十分广泛，在实际生活中遇到的一些问题通常可以用求解方程组的方法来解决。本章主要是通过实例介绍三种方法的应用以及其各种方法的优缺点比较。例：用三种方法求解方程组 2.0x1+1.0x4=0.02.0x1+2.0x2+3.0x3+2.0x4=-2.06.0x1+1.0x2-6.0x3-5.0x4=6.04.0x1-3.0x2+1.0x4=-7.0 的解。3.1 迭代法 解题步骤： 将方程组记为ax=b，其中 a=2.0 0.00.0 1.02.0 2.03.0 2.06.0 1.0-6.0 -5.04.0 -3.0 0.0 1.0 b=0.0-2.06.0-7.0 将原方程组改写为x1=-1.02.0x4x2=-12.02.0x1+3.0x3+2.0x4+2.0 x3=16.06.0x1+1.0x2-5.0x4-6.0 x4=-4.0x1+3.0x2-7.0 (1)也可写为 x=bx+f 其中 b= 0.0 0.0 0.0 -1.02.0 -1.0 0.0 -3.02.0 -1,0 1.0 1.06.0 -5.06.0 -1.0-4.0 3.0 0.0 0.0 f=0.0-1.0-1.0-7.0任取初始值x(0)=(0.0,0.0,0.0,0.0)t,代入（1）式右边，得到新的值： x(1)=(0.0,-1.0,-1.0,-7.0)t再将x(1)代入（1）式右边得到x(2)。反复利用这个计算程序，得到一个向量序列和一般的计算公式： x(k+1)=bx(k)+f 其中k表示迭代次数（k=1,2,）。 令x(k)=(x1k,x2(k),xn(k)t，由雅克比迭代公式x0 (初始向量）x(k+1)=bx(k)+f (k=0,1,2,)有： dx(k+1)=l+uxk+b x(k+1)=d-1l+uxk+d-1b 于是，根据雅克比迭代法的计算公式可求出方程组的解。3.2 直接三角分解法 解题步骤： 将方程组改写为2.0 0.0 0.0 1.02.0 2.0 3.0 2.0 6.0 1.0 -6.0 -5.04.0 -3.0 0.0 1.0 x1x2x3x4=0.0-2.06.0-7.0 设2.0 0.00.0 1.02.0 2.03.0 2.06.0 1.0-6.0 -5.04.0 -3.0 0.0 1.0=100 0l2110 0l31l321 0 l41 l42 l43 1u11u12u13 u140u22u23 u2400u33 u34 0 0 0 u44 第一步有：u11=2 .0 u12=0.0 u13=0.0 u14=1.0 l21=1.0 l31=3.0 l41=2.0 第二步有：u22=2.0 u23=3.0 u24=1.0 l32=0.5 l42=-1.5 第三步有：u33=-7.5 u34=-8.5 l43=-0.6 第四步有：u44=-4.6 于是有 l=1 0 0 01.0 1 0 03.0 0.5 1 0 2.0 -1.5 -0.6 1 u=2.00.00.0 1.002.03.0 1.000-7.5 -8.5 0 0 0 -4.6 由ly=b得y，由ux=y得x=(-3.5，0.0，-3.0，7.0)t3.3 高斯列主元消去法解题步骤：对线性方程组： ax=b ； 令增广矩阵为：a(1)=(a(1)b(1)=(ab)消元过程： 令li1=ai1(1)a11(1) ，把式的增广矩阵中的第1行的li1倍依次加到该增广矩阵的第i（i1）行，则第i(i1)行第j列位置的元素为： （i，j=2,3,4,n） (i=2,3,n)因此，式可转化为： a(2)=(a(2)b(2)= 依次做下去，一直做到第n-1步，即有 化为回代求解： xn=bn(n)ann(m)xk=bn(n)-j=k+1nakj(k)xjakk(m) （k=n-1，n-2，.,2,1）3.4 三种方法的优缺点比较迭代法具有循环的计算式，方法简单，程序实现方便，能充分利用系数的稀疏性，适宜解大型稀疏矩阵方程组。迭代法不存在误差累积问题。使用迭代法的关键问题是其收敛性与收敛速度，收敛性与迭代初值的选取无关。雅克比迭代法的收敛条件是：max xi=max1in|xik+1-xi(k)| 为精度要求高斯列主元消去法特点是每次在系数矩阵中依次按列在主对角线以下的元素中，选取绝对值最大的元素作为主元，将它调至主对角线上，然后用它去消去对角线以下的元素，最后变为同解的上三角形方程组求解。如果那一列的所有元素都为0，则说明该方程组解不唯一。高斯列主元消去法计算简单，工作量大为减少，且计算经验与理论分析均表明，它具有良好的数值稳定性，故列主元法是求解中小型稠密线性方程组的最好方法之一。 矩阵的三角分解法是高斯消去法紧凑格式的矩阵表示，它在解方程组的直接法中起着重要的作用。系数矩阵的lu分解与右端项无关。因而在计算多个系数矩阵为a而右端不同的线性方程组系是，用lu分解法更为简便。 lu分解法可以使用于任何矩阵，从使用范围来说lu分解法优点相当明