追赶法解三对角方程组概要

《数值分析》课程设计追赶法解三对角方程组院（系）名称信息工程学院专业班级10普本信计学号100111014学生姓名刘银朋指导教师张荣艳2013年05月31日数值分析课程设计评阅书题目追赶法解三对角方程组学生姓名刘银朋学号100111014指导教师评语及成绩指导教师签名：年月日答辩评语及成绩答辩教师签名：年月日教研室意见总成绩：教研室主任签名：年月日课程设计任务书2012—2013学年第二学期专业班级：10普本信息与计算科学学号：100111014姓名：刘银朋课程设计名称：数值分析Ⅰ、Ⅱ设计题目：追赶法解三对角方程组完成期限：自2013年05月21日至2013年05月31日共10天设计依据、要求及主要内容：一、设计目的理解追赶法,掌握追赶法的算法设计以及关于追赶法的分析和综合应用,能够较熟练的应用Matlab软件编写求解追赶法的程序和应用Matlab软件数据库软件.二、设计内容（1）认真挑选有代表性的三对角方程组.（2）认真梳理解三对角方程组的解题思路.（3）比较追赶法和高斯消去法的计算精度.三、设计要求1．先用Matlab数据库中的相应的函数对选定的方程,求出具有一定精度的解.2．然后使用所用的方法编写Matlab程序求解.3.对于使用多个方程解同意问题的,在界面上要设计成菜单的形式.计划答辩时间：2013年06月5日工作任务鱼工作量要求：查阅文献资料不少于3篇,课程设计报告1篇不少于3000字.指导教师（签字）：教研室主任（签字）：批准日期：2013年05月20日课程设计说明书（论文）第I页追赶法解三对角方程组摘要本文主要通过运用追赶法来求解三对角方程组的问题.追赶法是用来求解三对角方程组的专用方法,对于三对角方程组,追赶法比Gauss消去法的计算量要小的多,本文主要介绍了追赶法的原理,并用Matlab编写求解程序,以实现对三对角方程组的求解,进一步解决实际中的问题.并且根据所得出的结果分析追赶法算法和高斯消去的法的计算精度.关键词：追赶法,三对角方程组,追赶法的Matlab程序课程设计说明书（论文）第II页目录1.前言.................................................................................................................................................12.解题思想和方法....................................................................................................................................12.1追赶法解题思想.......................................................................................................................12.2追赶法解题原理........................................................................................................................43.对追赶法的MATLAB求解...............................................................................................................43.1实验程序......................................................................................................................................43.2应用举例.....................................................................................................................................54.与高斯消去法的精度比较.................................................................................................................5课程设计总结.............................................................................................................................................8参考文献......................................................................................................................................................8课程设计说明书（论文）第1页1.前言当今很多科学与工程计算问题大都可以化为线性方程组的形式,所以有效的求解线性方程组在科学和工程计算中是非常重要的.虽然线性代数方程的求解方法和数值计算软件包均很成熟,但随着并行计算机的发展,问题的求解速度和解题规模都大大提高,因而使数值计算方法和响应的数学软件包都产生了变化,相应的线性方程组的有效并行求解也引起了人们的普遍关注.追赶法是用来求解三对角方程组的专用方法,生活中很多实际问题,都归结为求解线性方程组.例如解常微分方程边值问题,解热传导方程以及船体数学放样中建立三次样条函数等,都会要求就解系数矩阵成三对角线性的方程组.而解三对角方程组的最简单方法是追赶法,公式简单,计算量小,所占用的存储单元少,所以在小机器上也能求解.追赶大事用来求解三对角方程组的专用方法,对于三对角方程组,追赶法比Gauss消去法的计算量要小得多.应用追赶法求解三对角线性方程,追赶法仍然保持LU分解特性,它是一种特殊的LU分解.充分利用了系数矩阵的特点,而且使之分解更简单,得到对三对角线性方程组的快速解法.本文讨论使用追赶法解线性方程组.介绍追赶法的理论,求解线性方程组的追赶法的实现以及追赶法的应用.2.解题思想和方法三对角矩阵是一种具有特殊意义的带状矩阵.用差分法求解二阶常微分方程边值问题时,最后常规解为求解具有三对角系数矩阵的线性方程组.对三对角矩阵实行Doolittle（或Crout）分解,便得到求解三对角方程组的最有效方法---追赶法.设矩阵A非奇异,A有Crout分解A=LU,其中Ｌ为下三角矩阵,Ｕ为单位上三角矩阵,可先依次求出L,U中的元素后,令Ux=y,先求解下三角方程组Ly=f得出y,再求解上三角方程组Ux=y,事实上求解三对角方程组的2追赶法将矩阵三角分解的计算与求解两个三角方程组的计算放在一起,使算法更为紧凑.本文主要介绍追赶法的原理,以及编写Matlab程序实现在计算机上的应用并分析他们的计算精度,比较解三对角方程组的最优解的问题.2.1追赶法解题思想在实际问题中,经常遇到以下形式的方程组课程设计说明书（论文）第2页nnnnnnnnnnnnkkkkkkkdxbxadxcxbxadxcxbxadxcxbxadxcxb111112111232221212111（2.11）这种方程组的系数矩阵A为三对角矩阵,即nnnnnkkkbacbacbacbacbA11122211以下针对这种方程组的特点提供一种简便有效的算法—追赶法.追赶法实际上是高斯消去法的一种简化形式,它同样分消元与回代两个过程.先将（2.11）第一个方程中x1的系数化为1112111bdxbcx111111bdybcr（2.12）有1211yxrx注意到剩下的方程中,实际上只有第二个方程中含有变量x1,因此消元手续可以简化.利用（2.12）可将第二个方程化为2312yxrx,这样一步一步地顺序加工（2.11）的每个方程,设第k–1个方程已经变成111kkkkyxrx（2.13）再利用（2.13）从第k个方程中消去xk-1,得：kkkkkkkkkaydxcxarb111)(同除kkkarb1,得nkarbaydxarbcxkkkkkkkkkkkk,,3,21111课程设计说明书（论文）第3页记kkkkkkkkkkkkarbaydyarbcr111则有kkkkyxrx1这样做n–1步以后,便得到：111nnnnyxrx将上式与（2.11）中第11个方程联立,即可解出xn=yn,这里nnnnnnnarbaydy11于是,通过消元过程,所给方程组（2.11）可归结为以下更为简单的形式：nnkkkkyxyxrxyxrx11211（2.14）这种方程组称作二对角型方程组,其系数矩阵中的非零元素集中分步在主对角线和一条次主对角线上11111121nkrrrr对加工得到的方程组（2.14）自下而上逐步回代,即可依次求出xn,xn-1,…,x1,计算公式为：1,,2,11nnkxryxyxkkkknn（2.15）上述算法就是追赶法,它的消元过程与回代过程分别称作“追”过程与“赶”过程.综合追与赶的过程,得如下计算公式：nkarbaydyarbcrbdybcrkkkkkkkkkkkk,,3,2111111111（2.16）课程设计说明书（论文）第4页1,,2,11nnkxryxyxkkkknn（2.17）2.2追赶法解题原理(1)计算i的递推公式111/cb,/(),2,3,,1iiiiicbain.(2)解Ly=f111/yfb,1()/(),2,3,,;iiiiiiiyfaybain(3)解Ux=y11,,1,2,2,1nniiiixyxyxinn.我们将计算系数121n及12nyyy的过程称为追的过程.将计算方程组的解11nnxxx的过程称为追赶的过程.3.对追赶法的MATLAB求解3.1实验程序functionx=chase(a,b,c,f)%定义函数chasen=length(b);ifn-1==length(a)fori=n-1:-1:1a(i+1)=a(i);endend%将a设置为n维向量c(1)=c(1)/b(1);f(1)=f(1)/b(1);fori=2:n-1b(i)=b(i)-a(i)*f(i-1)/b(i);c(i)=c(i)/b(i);f(i)=(f(i)-a(i)*f(i-1))/b(i);课程设计说明书（论文）第5页endf(n)=(f(n)-a(n)*f(n-1))/(b(n)-a(n)*c(n-1));fori=n-1:-1:1f(i)=f(i)-c(i)*f(i+1);endx=f;3.2应用举例例1用追赶法解三对角方程组设270329045A567f求解线性方程组Ax=F解：（1）在Matlab中编写一个名为chase.m的M文件,依次输入数据如下；A=[270;329;045];a=[34];b=[225];c=[79];f=[