追赶法解三对角程组.docx
《追赶法解三对角程组.docx》由会员分享，可在线阅读，更多相关《追赶法解三对角程组.docx（13页珍藏版）》请在冰点文库上搜索。
追赶法解三对角程组
《数值分析》课程设计
追赶法解三对角方程组
院（系）名称信息工程学院
专业班级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日
追赶法解三对角方程组
摘要
本文主要通过运用追赶法来求解三对角方程组的问题.追赶法是用来求解三对角方程组的专用方法,对于三对角方程组,追赶法比Gauss消去法的计算量要小的多,本文主要介绍了追赶法的原理,并用Matlab编写求解程序,以实现对三对角方程组的求解,进一步解决实际中的问题.并且根据所得出的结果分析追赶法算法和高斯消去的法的计算精度.
关键词：
追赶法,三对角方程组,追赶法的Matlab程序
1.前言1
2.解题思想和方法1
2.1追赶法解题思想1
2.2追赶法解题原理4
3.对追赶法的MATLAB求解4
3.1实验程序4
3.2应用举例5
4.与高斯消去法的精度比较6
课程设计总结8
参考文献8
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.11）
这种方程组的系数矩阵A为三对角矩阵,即
以下针对这种方程组的特点提供一种简便有效的算法—追赶法.追赶法实际上是高斯消去法的一种简化形式,它同样分消元与回代两个过程.
先将（2.11）第一个方程中x1的系数化为1
（2.12）
有
注意到剩下的方程中,实际上只有第二个方程中含有变量x1,因此消元手续可以简化.利用（2.12）可将第二个方程化为
这样一步一步地顺序加工（2.11）的每个方程,设第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）
上述算法就是追赶法,它的消元过程与回代过程分别称作“追”过程与“赶”过程.综合追与赶的过程,得如下计算公式：
（2.16）
（2.17）
2.2追赶法解题原理
（1）计算
的递推公式
.
（2）解Ly=f
（3）解Ux=y
.
我们将计算系数
及
的过程称为追的过程.将计算方程组的解
的过程称为追赶的过程.
3.对追赶法的MATLAB求解
3.1实验程序
functionx=chase（a,b,c,f）
%定义函数chase
n=length（b）;
ifn-1==length（a）
fori=n-1:
-1:
1
a（i+1）=a（i）;
end
end
%将a设置为n维向量
c
（1）=c
（1）/b
（1）;f
（1）=f
（1）/b
（1）;
fori=2:
n-1
b（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）;
end
f（n）=（f（n）-a（n）*f（n-1））/（b（n）-a（n）*c（n-1））;
fori=n-1:
-1:
1
f（i）=f（i）-c（i）*f（i+1）;
end
x=f;
3.2应用举例
例1用追赶法解三对角方程组
设
求解线性方程组Ax=F
解：
（1）在Matlab中编写一个名为chase.m的M文件,依次输入数据如下；
>>A=[270;329;045];
>>a=[34];
>>b=[225];
>>c=[79];
>>f=[567];
>>x=chase（a,b,c,f）
x=-3.01401.57540.1397
得到输出结果x=-3.01401.57540.1397即为原线性方程组的解.
结果验证：
>>A*x’
ans=5.0000
6.0000
7.0000
得到ans=f即结果正确
4.与高斯消去法的精度比较
事实上,追赶法的求解过程就是将系数矩阵分解两个简单的二对角线矩阵,从而归结为求解两个简单三角形方程组的过程.高斯消去法是求解线性方程组的最基本方法之一.Gauss消去法是针对一般的线性方程组,与线性代数中的初等变换解线性方程组方法类似.追赶法只是针对系数矩阵为三对角阵的方程组,因此是一种特殊的方程组.此方法效率较高,不过不适用于一般的线性方程组.下面对追赶法与高斯消去法计算量进行比较.
例2编写高斯消去法解线性方程组的Matlab程序,并求解下面的线性方程组
解：
编程如下
function[RA,RB,n,X]=gaus（A,b）
B=[Ab];
n=length（b）;RA=rank（A）;
RB=rank（B）;zhica=RB-RA;
ifzhica>0,
disp（'请注意：
因为RA~=RB,所以此方程组无解.'）
return
end
ifRA==RB
ifRA==n
disp（'请注意：
因为RA=RB=n,所以此方程组有唯一解.'）
X=zeros（n,1）;C=zeros（1,n+1）;
forp=1:
n-1
fork=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）;
forq=n-1:
-1:
1
X（q）=（b（q）-sum（A（q,q+1:
n）*X（q+1:
n）））/A（q,q）;
end
elsedisp（'请注意：
因为RA=RBend
end
用Matlab调用程序：
在Matlab中编写一个名为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=3
X=12-1
ans=1.0000
2.0000
-1.0000
综上所述,追赶法的原理和高斯消去法相同,但考虑到方程组的特点,计算时会把大量零元素撇开,从而大大节省计算量.追赶法实际上就是把高斯消去法用到求解三对角方程组上的结果.这时由于A特别简单,因此使得求解的计算公式非常简单,而且计算量仅为2（n-1）+（n-1）+[1+2（n-1）]=5n-4次乘除法,而另外解一个方程组Ax=f仅增加3n-2次乘除运算,易见追赶法的计算量是比较小的.
课程设计总结
首先,这次的课程设计让我把以前学习到的非线性方程的求解知识得到巩固和进一步的提高,对已有知识有了更进一步的理解和认识．同时也发现了自身有许多的不足之处.再者,在这次课程设计中碰到了很多的问题,自己通过上网,查阅了相关的书籍以及和我组其他的成员讨论的方式来解决的.另外编写程序是我的一大弱项,在以前做实验时总是按照老师给出的程序不加思考的敲进去,得出来结果就行,但在做这次课程设计时,需要自己真正的去理解和编程．
通过这次课程设计,我从中学会了很多,也发现自己真的还有很多不足以及很多东西需要去学习．所以在以后的生活学习中要不断的扩大自己的视野,多学习一些与专业有关的知识,不能只满足于课本上的知识．所以在完成本专业的基础上,要不断涉猎,完善自我,希望自己在以后的课程中会得到更好的锻练．总的来说这次课程设计还是有很多的收获的,并且特别感谢我们组的成员在做课程设计的过程中对我的帮助．
参考文献
[1]冯国忱,黄明游．数值分析（上册）[M]．北京：
高等教育出版社,2007．
[2]宋叶志,贾东志．MATLAB数值分析与应用[M]．北京：
机械工业出版社,2009．
[3]张德丰．MATLAB数值分析与应用[M]．北京：
国防工业出版社,2007．
[4]周煦,计算机数值方法及程序设计,机械工业出版社,2004.10.01.
[5]张静,杨文平,石傅强等,MATLAB程序设计与实例应用,中国铁道出版社,2003.
升级会员 