追赶法解三对角方程组

1、数值分析课程设计追赶法解三对角方程组院（系）名称 信息工程学院 专 业 班 级 10普本信计 学 号 100111014 学 生 姓 名 刘银朋 指 导 教 师 张荣艳 2013 年 05 月 31日数值分析 课程设计评阅书题目追赶法解三对角方程组学生姓名刘银朋学号100111014指导教师评语及成绩指导教师签名： 年 月 日答辩评语及成绩答辩教师签名： 年 月 日教研室意见 总成绩： 教研室主任签名：年 月 日课程设计任务书20122013学年第二学期专业班级： 10普本信息与计算科学 学号： 100111014 姓名： 刘银朋 课程设计名称： 数值分析、 设计题目： 追赶法解三对角方程组

2、完成期限：自 2013 年 05月 21 日至2013年05 月31日共 10天设计依据、要求及主要内容：一、设计目的 理解追赶法,掌握追赶法的算法设计以及关于追赶法的分析和综合应用,能够较熟练的应用Matlab软件编写求解追赶法的程序和应用Matlab软件数据库软件. 二、设计内容 （1）认真挑选有代表性的三对角方程组. （2）认真梳理解三对角方程组的解题思路. （3）比较追赶法和高斯消去法的计算精度. 三、设计要求 1先用Matlab数据库中的相应的函数对选定的方程,求出具有一定精度的解. 2然后使用所用的方法编写Matlab程序求解. 3.对于使用多个方程解同意问题的,在界面上要设计成菜

3、单的形式. 计划答辩时间：2013年 06 月 5 日工作任务鱼工作量要求：查阅文献资料不少于3篇,课程设计报告1篇不少于3000字.指导教师（签字）： 教研室主任（签字）： 批准日期： 2013 年 05 月 20 日 课程设计说明书（论文） 第 II页追赶法解三对角方程组摘 要本文主要通过运用追赶法来求解三对角方程组的问题.追赶法是用来求解三对角方程组的专用方法,对于三对角方程组,追赶法比Gauss消去法的计算量要小的多,本文主要介绍了追赶法的原理,并用Matlab编写求解程序,以实现对三对角方程组的求解,进一步解决实际中的问题.并且根据所得出的结果分析追赶法算法和高斯消去的法的计算精度.

4、关键词：追赶法,三对角方程组,追赶法的Matlab程序目 录1.前 言12.解题思想和方法12.1 追赶法解题思想12.2追赶法解题原理43.对追赶法的MATLAB求解43.1实验程序43.2 应用举例54.与高斯消去法的精度比较6课程设计总结8参考文献8 课程设计说明书（论文） 第 8 页1. 前 言当今很多科学与工程计算问题大都可以化为线性方程组的形式,所以有效的求解线性方程组在科学和工程计算中是非常重要的.虽然线性代数方程的求解方法和数值计算软件包均很成熟,但随着并行计算机的发展,问题的求解速度和解题规模都大大提高,因而使数值计算方法和响应的数学软件包都产生了变化,相应的线性方程组的有效

5、并行求解也引起了人们的普遍关注.追赶法是用来求解三对角方程组的专用方法,生活中很多实际问题,都归结为求解线性方程组.例如解常微分方程边值问题,解热传导方程以及船体数学放样中建立三次样条函数等,都会要求就解系数矩阵成三对角线性的方程组.而解三对角方程组的最简单方法是追赶法,公式简单,计算量小,所占用的存储单元少,所以在小机器上也能求解.追赶大事用来求解三对角方程组的专用方法,对于三对角方程组,追赶法比Gauss消去法的计算量要小得多.应用追赶法求解三对角线性方程,追赶法仍然保持LU分解特性,它是一种特殊的LU分解.充分利用了系数矩阵的特点,而且使之分解更简单,得到对三对角线性方程组的快速解法.

6、本文讨论使用追赶法解线性方程组.介绍追赶法的理论,求解线性方程组的追赶法的实现以及追赶法的应用.2.解题思想和方法三对角矩阵是一种具有特殊意义的带状矩阵.用差分法求解二阶常微分方程边值问题时,最后常规解为求解具有三对角系数矩阵的线性方程组.对三对角矩阵实行Doolittle（或Crout）分解,便得到求解三对角方程组的最有效方法-追赶法.设矩阵A非奇异,A有Crout分解A=LU,其中为下三角矩阵,为单位上三角矩阵,可先依次求出L,U中的元素后,令Ux=y,先求解下三角方程组Ly=f得出y,再求解上三角方程组Ux=y,事实上求解三对角方程组的2追赶法将矩阵三角分解的计算与求解两个三角方程组的计

7、算放在一起,使算法更为紧凑.本文主要介绍追赶法的原理,以及编写Matlab程序实现在计算机上的应用并分析他们的计算精度,比较解三对角方程组的最优解的问题.2.1 追赶法解题思想在实际问题中,经常遇到以下形式的方程组 （2.11）这种方程组的系数矩阵A为三对角矩阵,即以下针对这种方程组的特点提供一种简便有效的算法追赶法.追赶法实际上是高斯消去法的一种简化形式,它同样分消元与回代两个过程.先将（2.11）第一个方程中x1的系数化为1 （2.12）有注意到剩下的方程中,实际上只有第二个方程中含有变量x1,因此消元手续可以简化.利用（2.12）可将第二个方程化为,这样一步一步地顺序加工（2.11）的每

8、个方程,设第k 1个方程已经变成 （2.13）再利用（2.13）从第k个方程中消去xk-1,得：同除,得记则有 这样做n 1步以后,便得到：将上式与（2.11）中第11个方程联立,即可解出xn = yn ,这里于是,通过消元过程,所给方程组（2.11）可归结为以下更为简单的形式： （2.14）这种方程组称作二对角型方程组,其系数矩阵中的非零元素集中分步在主对角线和一条次主对角线上对加工得到的方程组（2.14）自下而上逐步回代,即可依次求出xn,xn-1,x1,计算公式为： （2.15）上述算法就是追赶法,它的消元过程与回代过程分别称作“追”过程与“赶”过程.综合追与赶的过程,得如下计算公式：（

9、2.16） （2.17）2.2追赶法解题原理(1) 计算的递推公式,.(2) 解Ly=f, (3) 解Ux=y. 我们将计算系数及的过程称为追的过程.将计算方程组的解的过程称为追赶的过程.3.对追赶法的MATLAB求解3.1实验程序function x=chase(a,b,c,f)%定义函数chasen=length(b);if n-1=length(a)for i=n-1:-1:1a(i+1)=a(i);endend%将a设置为n维向量c(1)=c(1)/b(1);f(1)=f(1)/b(1);for i=2:n-1b(i)=b(i)-a(i)*f(i-1)/b(i);c(i)=c(i)/b

10、(i);f(i)=(f(i)-a(i)*f(i-1)/b(i);endf(n)=(f(n)-a(n)*f(n-1)/(b(n)-a(n)*c(n-1);for i=n-1:-1:1f(i)=f(i)-c(i)*f(i+1);endx=f;3.2 应用举例 例1 用追赶法解三对角方程组设 求解线性方程组Ax=F解：（1）在Matlab中编写一个名为chase.m的M文件,依次输入数据如下；>> A=2 7 0;3 2 9;0 4 5;>> a=3 4;>> b=2 2 5;>>c=7 9;>> f=5 6 7;>> x=ch

11、ase (a,b,c,f)x= -3.0140 1.5754 0.1397得到输出结果x= -3.0140 1.5754 0.1397即为原线性方程组的解.结果验证：>>A*xans=5.0000 6.0000 7.0000得到ans=f即结果正确4. 与高斯消去法的精度比较事实上,追赶法的求解过程就是将系数矩阵分解两个简单的二对角线矩阵,从而归结为求解两个简单三角形方程组的过程. 高斯消去法是求解线性方程组的最基本方法之一.Gauss消去法是针对一般的线性方程组,与线性代数中的初等变换解线性方程组方法类似.追赶法只是针对系数矩阵为三对角阵的方程组,因此是一种特殊的方程组.此方法效

12、率较高,不过不适用于一般的线性方程组.下面对追赶法与高斯消去法计算量进行比较.例2 编写高斯消去法解线性方程组的Matlab程序,并求解下面的线性方程组解：编程如下function RA,RB,n,X=gaus(A,b) B=A b; n=length(b);RA=rank(A); RB=rank(B);zhica=RB-RA; if zhica>0, disp('请注意：因为RA=RB,所以此方程组无解.') return end if RA=RB if RA=n disp('请注意：因为RA=RB=n,所以此方程组有唯一解.') X=zeros(n,1

13、); C=zeros(1,n+1); for p= 1:n-1 for k=p+1:n m= B(k,p)/ B(p,p); B(k,p:n+1)= B(k,p:n+1)-m* B(p,p:n+1); end end b=B(1:n,n+1);A=B(1:n,1:n); X(n)=b(n)/A(n,n); for q=n-1:-1:1 X(q)=(b(q)-sum(A(q,q+1:n)*X(q+1:n)/A(q,q); end else disp('请注意：因为RA=RB<n,所以此方程组有无穷多解.') end end用Matlab调用程序：在Matlab中编写一个名为

14、gauss.m的M文件,依次输入数据如下:A=5,2,1;2,8,-3;1,-3,-6;b=8;21;1; RA,RB,n,X=gauss（A,b) 运行结果RA =3 RB =3 n = 3X =1 2 -1 ans = 1.0000 2.0000 -1.0000综上所述,追赶法的原理和高斯消去法相同,但考虑到方程组的特点,计算时会把大量零元素撇开,从而大大节省计算量.追赶法实际上就是把高斯消去法用到求解三对角方程组上的结果.这时由于A特别简单,因此使得求解的计算公式非常简单,而且计算量仅为2(n-1)+(n-1)+1+2(n-1)=5n-4次乘除法,而另外解一个方程组Ax=f仅增加3n-2

15、次乘除运算,易见追赶法的计算量是比较小的.课程设计总结 首先,这次的课程设计让我把以前学习到的非线性方程的求解知识得到巩固和进一步的提高,对已有知识有了更进一步的理解和认识同时也发现了自身有许多的不足之处.再者,在这次课程设计中碰到了很多的问题,自己通过上网,查阅了相关的书籍以及和我组其他的成员讨论的方式来解决的.另外编写程序是我的一大弱项,在以前做实验时总是按照老师给出的程序不加思考的敲进去,得出来结果就行,但在做这次课程设计时,需要自己真正的去理解和编程通过这次课程设计,我从中学会了很多,也发现自己真的还有很多不足以及很多东西需要去学习所以在以后的生活学习中要不断的扩大自己的视野,多学习一些与专业有关的知识,不能只满足于课本上的知识所以在完成本专业的基础上,要不断涉猎,完善自我,希望自己在以后的课程中会得到更好的