追趕法解三對(duì)角方程組

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

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

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

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

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

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

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

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

9、2.16） （2.17）2.2追趕法解題原理(1) 計(jì)算的遞推公式,.(2) 解Ly=f, (3) 解Ux=y. 我們將計(jì)算系數(shù)及的過(guò)程稱(chēng)為追的過(guò)程.將計(jì)算方程組的解的過(guò)程稱(chēng)為追趕的過(guò)程.3.對(duì)追趕法的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

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 應(yīng)用舉例 例1 用追趕法解三對(duì)角方程組設(shè) 求解線(xiàn)性方程組Ax=F解：（1）在Matlab中編寫(xiě)一個(gè)名為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

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

12、Matlab程序,并求解下面的線(xiàn)性方程組解：編程如下function RA,RB,n,X=gaus(A,b) B=A b; n=length(b);RA=rank(A); RB=rank(B);zhica=RB-RA; if zhica0, disp(請(qǐng)注意：因?yàn)镽A=RB,所以此方程組無(wú)解.) return end if RA=RB if RA=n disp(請(qǐng)注意：因?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

13、: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(請(qǐng)注意：因?yàn)镽A=RBn,所以此方程組有無(wú)窮多解.) end end用Matlab調(diào)用程序：在Matlab中編寫(xiě)一個(gè)名為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 =

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