追趕法解三對角方程組

1、數(shù)值分析課程設(shè)計(jì)追趕法解三對角方程組院（系）名稱 信息工程學(xué)院 專 業(yè) 班 級 10普本信計(jì) 學(xué) 號 100111014 學(xué) 生 姓 名 劉銀朋 指 導(dǎo) 教 師 張榮艷 2013 年 05 月 31日數(shù)值分析 課程設(shè)計(jì)評閱書題目追趕法解三對角方程組學(xué)生姓名劉銀朋學(xué)號100111014指導(dǎo)教師評語及成績指導(dǎo)教師簽名： 年 月 日答辯評語及成績答辯教師簽名： 年 月 日教研室意見 總成績： 教研室主任簽名：年 月 日課程設(shè)計(jì)任務(wù)書20122013學(xué)年第二學(xué)期專業(yè)班級： 10普本信息與計(jì)算科學(xué) 學(xué)號： 100111014 姓名： 劉銀朋 課程設(shè)計(jì)名稱： 數(shù)值分析、 設(shè)計(jì)題目： 追趕法解三對角方程組

2、完成期限：自 2013 年 05月 21 日至2013年05 月31日共 10天設(shè)計(jì)依據(jù)、要求及主要內(nèi)容：一、設(shè)計(jì)目的 理解追趕法,掌握追趕法的算法設(shè)計(jì)以及關(guān)于追趕法的分析和綜合應(yīng)用,能夠較熟練的應(yīng)用Matlab軟件編寫求解追趕法的程序和應(yīng)用Matlab軟件數(shù)據(jù)庫軟件. 二、設(shè)計(jì)內(nèi)容 （1）認(rèn)真挑選有代表性的三對角方程組. （2）認(rèn)真梳理解三對角方程組的解題思路. （3）比較追趕法和高斯消去法的計(jì)算精度. 三、設(shè)計(jì)要求 1先用Matlab數(shù)據(jù)庫中的相應(yīng)的函數(shù)對選定的方程,求出具有一定精度的解. 2然后使用所用的方法編寫Matlab程序求解. 3.對于使用多個方程解同意問題的,在界面上要設(shè)計(jì)成菜

3、單的形式. 計(jì)劃答辯時(shí)間：2013年 06 月 5 日工作任務(wù)魚工作量要求：查閱文獻(xiàn)資料不少于3篇,課程設(shè)計(jì)報(bào)告1篇不少于3000字.指導(dǎo)教師（簽字）： 教研室主任（簽字）： 批準(zhǔn)日期： 2013 年 05 月 20 日追趕法解三對角方程組摘 要本文主要通過運(yùn)用追趕法來求解三對角方程組的問題.追趕法是用來求解三對角方程組的專用方法,對于三對角方程組,追趕法比Gauss消去法的計(jì)算量要小的多,本文主要介紹了追趕法的原理,并用Matlab編寫求解程序,以實(shí)現(xiàn)對三對角方程組的求解,進(jìn)一步解決實(shí)際中的問題.并且根據(jù)所得出的結(jié)果分析追趕法算法和高斯消去的法的計(jì)算精度.關(guān)鍵詞：追趕法,三對角方程組,追趕法

4、的Matlab程序目 錄1.前 言12.解題思想和方法12.1 追趕法解題思想12.2追趕法解題原理43.對追趕法的MATLAB求解43.1實(shí)驗(yàn)程序43.2 應(yīng)用舉例54.與高斯消去法的精度比較6課程設(shè)計(jì)總結(jié)8參考文獻(xiàn)81. 前 言當(dāng)今很多科學(xué)與工程計(jì)算問題大都可以化為線性方程組的形式,所以有效的求解線性方程組在科學(xué)和工程計(jì)算中是非常重要的.雖然線性代數(shù)方程的求解方法和數(shù)值計(jì)算軟件包均很成熟,但隨著并行計(jì)算機(jī)的發(fā)展,問題的求解速度和解題規(guī)模都大大提高,因而使數(shù)值計(jì)算方法和響應(yīng)的數(shù)學(xué)軟件包都產(chǎn)生了變化,相應(yīng)的線性方程組的有效并行求解也引起了人們的普遍關(guān)注.追趕法是用來求解三對角方程組的專用方法,

5、生活中很多實(shí)際問題,都?xì)w結(jié)為求解線性方程組.例如解常微分方程邊值問題,解熱傳導(dǎo)方程以及船體數(shù)學(xué)放樣中建立三次樣條函數(shù)等,都會要求就解系數(shù)矩陣成三對角線性的方程組.而解三對角方程組的最簡單方法是追趕法,公式簡單,計(jì)算量小,所占用的存儲單元少,所以在小機(jī)器上也能求解.追趕大事用來求解三對角方程組的專用方法,對于三對角方程組,追趕法比Gauss消去法的計(jì)算量要小得多.應(yīng)用追趕法求解三對角線性方程,追趕法仍然保持LU分解特性,它是一種特殊的LU分解.充分利用了系數(shù)矩陣的特點(diǎn),而且使之分解更簡單,得到對三對角線性方程組的快速解法. 本文討論使用追趕法解線性方程組.介紹追趕法的理論,求解線性方程組的追趕法

6、的實(shí)現(xiàn)以及追趕法的應(yīng)用.2.解題思想和方法三對角矩陣是一種具有特殊意義的帶狀矩陣.用差分法求解二階常微分方程邊值問題時(shí),最后常規(guī)解為求解具有三對角系數(shù)矩陣的線性方程組.對三對角矩陣實(shí)行Doolittle（或Crout）分解,便得到求解三對角方程組的最有效方法-追趕法.設(shè)矩陣A非奇異,A有Crout分解A=LU,其中為下三角矩陣,為單位上三角矩陣,可先依次求出L,U中的元素后,令Ux=y,先求解下三角方程組Ly=f得出y,再求解上三角方程組Ux=y,事實(shí)上求解三對角方程組的2追趕法將矩陣三角分解的計(jì)算與求解兩個三角方程組的計(jì)算放在一起,使算法更為緊湊.本文主要介紹追趕法的原理,以及編寫Matla

7、b程序?qū)崿F(xiàn)在計(jì)算機(jī)上的應(yīng)用并分析他們的計(jì)算精度,比較解三對角方程組的最優(yōu)解的問題.2.1 追趕法解題思想在實(shí)際問題中,經(jīng)常遇到以下形式的方程組 （2.11）這種方程組的系數(shù)矩陣A為三對角矩陣,即以下針對這種方程組的特點(diǎn)提供一種簡便有效的算法追趕法.追趕法實(shí)際上是高斯消去法的一種簡化形式,它同樣分消元與回代兩個過程.先將（2.11）第一個方程中x1的系數(shù)化為1 （2.12）有注意到剩下的方程中,實(shí)際上只有第二個方程中含有變量x1,因此消元手續(xù)可以簡化.利用（2.12）可將第二個方程化為,這樣一步一步地順序加工（2.11）的每個方程,設(shè)第k 1個方程已經(jīng)變成 （2.13）再利用（2.13）從第k個

8、方程中消去xk-1,得：同除,得記則有 這樣做n 1步以后,便得到：將上式與（2.11）中第11個方程聯(lián)立,即可解出xn = yn ,這里于是,通過消元過程,所給方程組（2.11）可歸結(jié)為以下更為簡單的形式： （2.14）這種方程組稱作二對角型方程組,其系數(shù)矩陣中的非零元素集中分步在主對角線和一條次主對角線上對加工得到的方程組（2.14）自下而上逐步回代,即可依次求出xn,xn-1,x1,計(jì)算公式為： （2.15）上述算法就是追趕法,它的消元過程與回代過程分別稱作“追”過程與“趕”過程.綜合追與趕的過程,得如下計(jì)算公式：（2.16） （2.17）2.2追趕法解題原理(1) 計(jì)算的遞推公式,.(

9、2) 解Ly=f, (3) 解Ux=y. 我們將計(jì)算系數(shù)及的過程稱為追的過程.將計(jì)算方程組的解的過程稱為追趕的過程.3.對追趕法的MATLAB求解3.1實(shí)驗(yàn)程序function x=chase(a,b,c,f)%定義函數(shù)chasen=length(b);if n-1=length(a)for i=n-1:-1:1a(i+1)=a(i);endend%將a設(shè)置為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(i);f(i)=(f(i)-a(i)*f(i-1)/b(i);endf

10、(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 應(yīng)用舉例 例1 用追趕法解三對角方程組設(shè) 求解線性方程組Ax=F解：（1）在Matlab中編寫一個名為chase.m的M文件,依次輸入數(shù)據(jù)如下； 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=chase (a,b,c,f)x= -3.0140 1.5754 0.1397得到輸出結(jié)果x= -3.0140 1.5754 0.1397即為原線性方程組的解.結(jié)果驗(yàn)證：A

11、*xans=5.0000 6.0000 7.0000得到ans=f即結(jié)果正確4. 與高斯消去法的精度比較事實(shí)上,追趕法的求解過程就是將系數(shù)矩陣分解兩個簡單的二對角線矩陣,從而歸結(jié)為求解兩個簡單三角形方程組的過程. 高斯消去法是求解線性方程組的最基本方法之一.Gauss消去法是針對一般的線性方程組,與線性代數(shù)中的初等變換解線性方程組方法類似.追趕法只是針對系數(shù)矩陣為三對角陣的方程組,因此是一種特殊的方程組.此方法效率較高,不過不適用于一般的線性方程組.下面對追趕法與高斯消去法計(jì)算量進(jìn)行比較.例2 編寫高斯消去法解線性方程組的Matlab程序,并求解下面的線性方程組解：編程如下function R

12、A,RB,n,X=gaus(A,b) B=A b; n=length(b);RA=rank(A); RB=rank(B);zhica=RB-RA; if zhica0, disp(請注意：因?yàn)镽A=RB,所以此方程組無解.) return end if RA=RB if RA=n disp(請注意：因?yàn)镽A=RB=n,所以此方程組有唯一解.) X=zeros(n,1); 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

13、,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(請注意：因?yàn)镽A=RBn,所以此方程組有無窮多解.) end end用Matlab調(diào)用程序：在Matlab中編寫一個名為gauss.m的M文件,依次輸入數(shù)據(jù)如下:A=5,2,1;2,8,-3;1,-3,-6;b=8;21;1; RA,RB,n,X=gauss（A,b) 運(yùn)行結(jié)果RA =3 RB =3 n = 3X =1 2 -1 ans = 1.0000 2.0000 -1.0

14、000綜上所述,追趕法的原理和高斯消去法相同,但考慮到方程組的特點(diǎn),計(jì)算時(shí)會把大量零元素撇開,從而大大節(jié)省計(jì)算量.追趕法實(shí)際上就是把高斯消去法用到求解三對角方程組上的結(jié)果.這時(shí)由于A特別簡單,因此使得求解的計(jì)算公式非常簡單,而且計(jì)算量僅為2(n-1)+(n-1)+1+2(n-1)=5n-4次乘除法,而另外解一個方程組Ax=f僅增加3n-2次乘除運(yùn)算,易見追趕法的計(jì)算量是比較小的.課程設(shè)計(jì)總結(jié) 首先,這次的課程設(shè)計(jì)讓我把以前學(xué)習(xí)到的非線性方程的求解知識得到鞏固和進(jìn)一步的提高,對已有知識有了更進(jìn)一步的理解和認(rèn)識同時(shí)也發(fā)現(xiàn)了自身有許多的不足之處.再者,在這次課程設(shè)計(jì)中碰到了很多的問題,自己通過上網(wǎng),查閱了相關(guān)的書籍以及和我組其他的成員討論的方式來解決的.另外編寫程序是我的一大弱項(xiàng),在以前做實(shí)驗(yàn)時(shí)總是按照老師給出的程序不加思考的敲進(jìn)去,得出來結(jié)果就行,但在做這次課程設(shè)計(jì)時(shí),需要自己真正的去理解和編程通過這次課程設(shè)計(jì),我從中學(xué)會了很多,也發(fā)現(xiàn)自己真的還有很多不足以及很多東西需要去學(xué)習(xí)所以在以后的生活學(xué)習(xí)中要不斷的擴(kuò)大自己的視野,多學(xué)習(xí)一些與專業(yè)有關(guān)的知識,不能只滿足于課本上的知識所以在完成本專業(yè)的基礎(chǔ)上,要不斷涉獵,完善自我,希望自己在以后的課程中會得到更好的鍛練總的來說這