數(shù)值計算學(xué)習(xí)報告

1、 高斯消元法研究與思考第一章高斯消元法描述1、高斯消元法的相關(guān)概念在自然科學(xué)研究和工程技術(shù)中有許多問題可歸結(jié)為求解線性代數(shù)方程組的問題,線性方程組求解是科學(xué)計算中最常遇到的問題。如在應(yīng)力分析、電路分析、分子結(jié)構(gòu)、測量學(xué)中都會遇到解線性方程組問題。在很多廣泛應(yīng)用的數(shù)學(xué)問題的數(shù)值方法中，如三次樣條、最小二乘法、微分方程邊值問題的差分法與有限元法也都涉及到求解線性方程組。直接法是在沒有舍入誤差的情況下，通過有限步四則運算來求的方程組精確解的方法。直接法基本方法是高斯消元法，其改進方法包括高斯列主元消去法，三角分解法，追趕法等的基本思想和原理。高斯消去法（Gauss Elimination Metho

2、d）是一種規(guī)則化的加減消元法?；舅枷胧峭ㄟ^逐次消元計算把需要求解的線性方程組轉(zhuǎn)化為上三角形方程組，即把線性方程組的系數(shù)矩陣轉(zhuǎn)化為上三角矩陣，從而使一般線性方程組的求解轉(zhuǎn)化為等價(同解)的上三角形方程組的求解。1.1 Gauss消去法的計算過程通過一系列的加減消元運算，也就是代數(shù)中的加減消去法，以使A對角線以下的元素化為零，將方程組化為上三角矩陣；然后，再逐一回代求解出x向量。現(xiàn)舉例說明如下： 1.1.1消元過程第一步：將(1)/3使x1的系數(shù)化為1,再將(2)、(3)式中x1的系數(shù)都化為零，即由(2)-2×(1)(1)得 由(3)-4×(1)(1)得 第二步：將(2)(1

3、)除以2/3，使x2系數(shù)化為1，得再將(3)(1)式中x2系數(shù)化為零，由(3)(1)-(-14/3)*(2)(2) ，得第三步：將(3)(2)除以18/3，使x3系數(shù)化為1，得經(jīng)消元后，得到如下三角代數(shù)方程組：1.1.2回代過程 由(3)(3)得 x3=1,將x3代入(2)(2)得x2=-2,將x2 、x3代入(1)(1)得x2=1,所以，本題解為x=1,2,-1T 1.1.3 用矩陣演示進行消元過程第一步： 先將方程寫成增廣矩陣的形式第二步：然后對矩陣進行初等行變換第三步：將增廣矩陣變換成上三角矩陣，主對角線全為1，左下三角矩陣全為0.即原方程組被等價轉(zhuǎn)化成為上三角方程組，然后，逐步回代得原

4、方程組的解即可。1.1.4高斯消元的公式綜合以上討論，不難看出，高斯消元法解方程組的公式為第一步，消元（1） 令 （2） 對k=1到n-1，若akk(k)0，進行 第二步，回代 若 2、高斯消元法的運算量由公式，可得出消去過程的第步共含有除法運算次，乘法和減法運算各次，所以消去過程共含有乘除法次數(shù)為含加減法次數(shù)為 而回代過程含乘除法次數(shù)為，加減法次數(shù)為，所以Gauss消去法總的乘除法次數(shù)為，加減法次數(shù)為2、 高斯消元法的相關(guān)問題1. 為什么說高斯消元法是中國古法？2. 哪種線性方程組可用平方根法求解？為什么說平方根法計算穩(wěn)定？3. 什么樣的線性方程組可用追趕法求解并能保證計算穩(wěn)定？4. 何為向

5、量范數(shù)？給出三種常用的向量范數(shù)。5. 何為矩陣范數(shù)?6.高斯消去法與LU分解有什么關(guān)系？用它們解線性方程組Ax=b有何不同？A要滿足什么條件？3、 高斯消元法的相關(guān)理論3.1.特征值和特征向量設(shè)A是一個n´n階實矩陣，若對于數(shù)l，存在非零向量x，使得Ax=lx成立。則稱l是A的特征值(Characteristic Value)，x為A的對應(yīng)于l的特征向量(Characteristic Vector)。3.2 向量和矩陣 用表示全部實矩陣的向量空間,表示全部復(fù)矩陣的向量空間.（稱為m行n列矩陣）.（稱為n維列向量） ,其中 為A的第列.同理 ,其中 為A的第行. 矩陣基本運算: (1)

6、矩陣加法 . (2)矩陣與標(biāo)量的乘法 . (3)矩陣與矩陣的乘法 . （4）單位矩陣 ,其中3.3 特殊矩陣設(shè),則有A為:(1)對角矩陣 如果當(dāng)時,;(2)三對角矩陣 如果當(dāng);(3)上三角矩陣 如果當(dāng);(4)對稱矩陣 如果;(5)正定矩陣 如果設(shè)A是n階實系數(shù)對稱矩陣, 如果對任何非零向量 都有,就稱A正定.四、高斯消元法國外研究進展十幾年來直接法在求解具有較大型稀疏矩陣方程組方面取得了較大進展。關(guān)于三對角線性方程組的直接求解已經(jīng)有大量并行算法, 其中Wang 的分裂法是最早針對實際硬件環(huán)境, 基于分治策略提出的并行算法。它不僅通信結(jié)構(gòu)簡單, 容易推廣到一般帶狀線性方程組的并行求解, 而且為相

7、繼出現(xiàn)的許多其它并行算法提供了可行的局部分解策略。近20 年來求解三對角方程組的并行算法都是基于分治策略, 即通過將三對角方程組分解成P 個小規(guī)模問題, 求解這P個小規(guī)模問題, 再將這些解結(jié)合起來得到原三對角方程組的解。一般求解三對角方程組的分治方法的計算過程可分為3個階段: 一是消去, 每臺處理機對子系統(tǒng)消元; 二是求解縮減系統(tǒng)( 需要通信) ; 三是回代, 將縮減系統(tǒng)的解回代到每個子系統(tǒng), 求出最終結(jié)果。具體可分為以下幾類:（一) 遞推耦合算法(Recurs ive Doubling)由Stone 于1975 年提出, 算法巧妙地把LU 分解方法的時序性很強的遞推計算轉(zhuǎn)化為遞推倍增并行計算

8、。D.J.Evans對此方法做了大量研究。P.Dubois 和G.Rodrigue 的研究表明Stone 算法是不穩(wěn)定的。（二) 循環(huán)約化方法(Cyclic Reduction)循環(huán)約化方法由Hockey 和G.Golub 在1965 年提出, 其基本思想是每次迭代將偶數(shù)編號方程中的奇變量消去, 只剩下偶變量, 問題轉(zhuǎn)變成求解僅由偶變量組成的規(guī)模減半的新三對角方程組。求解該新方程組, 得到所有的偶變量后, 再回代求解所有的奇變量。即約化和回代過程。由于其基本的算術(shù)操作可以向量化, 適合于向量機。此方法有大量學(xué)者進行研究,提出了許多改進的方法。例如, Heller 針對最后幾步的短向量操作提出了

9、不完全循環(huán)約化方法; R.Reulter 結(jié)合IBM3090VF向量機的特點提出了局部循環(huán)約化法; P.Amodio 針對分布式系統(tǒng)的特點改進了循環(huán)約化方法; 最近針對此方法又提出對三對角方程組進行更大約化步的交替迭代策略。（三) 基于矩陣乘分解算法將系數(shù)矩陣A 分解成A=FT, 方程Ax=b 化為Fy=b 和Tx=y兩個方程組的并行求解。這種算法又可以分為兩類:1.重疊分解。如Wang 的分裂法及其改進算法就屬于這一類。P.Amodio 在1993 年對這類算法進行了很好的總結(jié), 用本地LU、本地LUD 和本地循環(huán)約化法求解, 并在1995 年提出基于矩陣乘分解的并行QR 算法。H.Mich

10、ielse 和A.Van derVorst改變Wang 算法的消元次序, 提出了通信量減少的算法。李曉梅等將H.Michielse 和A.Van der Vorst 算法中的通信模式從單向串行改為雙向并行, 提出DPP 算法, 是目前最好的三對角方程組分布式算法之一。2000 年駱志剛等中依據(jù)DPP 算法, 利用計算與通信重疊技術(shù), 減少處理機空閑時間取得了更好的并行效果。此類算法要求解P- 1 階縮減系統(tǒng)。2.不重疊分解。例如Lawrie & Sameh 算法、Johsoon 算法、Baron 算法、Chawla 在1991 年提出的WZ 分解算法以及Mattor在1995

11、年提出的算法都屬于這一類。此類算法要求解2P-2 階縮減系統(tǒng)。( 四) 基于矩陣和分解算法將系數(shù)矩陣分解成A=A0+DA, 這類算法的共同特點是利用Sherman & Morrison 公式將和的逆化為子矩陣逆的和。按矩陣分解方法, 這種算法又可分為兩類:1.重疊分解。這類算法首先由Mehrmann 在1990 年提出,通過選擇好的分解在計算過程中保持原方程組系數(shù)矩陣的結(jié)構(gòu)特性, 具有好的數(shù)值穩(wěn)定性, 需要求解P- 1 階縮減系統(tǒng)。2.不重疊分解。Sun 等在1992 年提出的并行劃分LU 算法PPT 算法和并行對角占優(yōu)算法PDD 算法均屬于這一類。需要求解2P- 2 階縮減系

12、統(tǒng)。其中PDD 算法的通訊時間不隨處理機的變化而變化, 具有很好的可擴展性。X.H.Sun 和W.Zhang在2002 年提出了兩層混合并行方法PTH , 其基本思想是在PDD 中嵌入一個內(nèi)層三對角解法以形成一個兩層的并行, 基本算法是PDD, 三對角系統(tǒng)首先基于PDD 分解。PTH 算法也具有很好的可擴展性。5、 高斯消元法國內(nèi)研究現(xiàn)狀1、 并行求解三對角系統(tǒng)的直接解法李曉梅等將H.Michielse 和A.Van der Vorst 算法中的通信模式從單向串行改為雙向并行, 提出DPP 算法, 是目前最好的三對角方程組分布式算法之一。2000 年駱志剛等中依據(jù)DPP 算法, 利用計算與通信

13、重疊技術(shù), 減少處理機空閑時間取得了更好的并行效果。此類算法要求解P-1 階縮減系統(tǒng)。2、病態(tài)線性方程組解法研究病態(tài)線性方程組解法的研究是數(shù)值計算研究的一個重要課題.通過分析病態(tài)線性方程組的特點和成因的基礎(chǔ)上,對一些傳統(tǒng)的算法進行了改進,給出了加權(quán)迭代改善法和PSD-PCG法.其改進效果不僅在理論上得到了證明,且同時由幾個典型的數(shù)值試驗得到了驗證.3、解循環(huán)三對角線性方程組的追趕法循環(huán)三對角、循環(huán)Toeplitz三對角線性方程組的求解在科學(xué)與工程計算中有著廣泛的應(yīng)用. 運用矩陣分解給出此類方程組的直接解法; 通過分析其特性, 給出了達到機器精度的截斷算法, 其計算復(fù)雜度幾乎等同于求解一個三對角

14、線性方程組的計算復(fù)雜度. 數(shù)值實驗的結(jié)果與理論分析的結(jié)果十分吻合. 該算法還推廣到求解擬三對角線性方程組.4、基于矩陣分解的周期塊三對角線性方程組的并行直接解法提出了分布式環(huán)境下求解周期塊三對角線性方程組的一種并行算法該算法充分利用系 數(shù)矩陣結(jié)構(gòu)的特殊性，通過對系數(shù)矩陣進行適當(dāng)分解及近似處理，使算法只在相鄰處理機間通信2次，并從理論上給出了算法有效的一個充分條件最后，在HP rx2600集群上進行了數(shù)值試驗，結(jié)果表明，實算與理論是一致的，并行性也很好5、病態(tài)線性方程組的新解法：誤差轉(zhuǎn)移法提出了一種求解病態(tài)線性方程組的簡便有效的新算法，它的主要思想是將直接求解法中的計算誤差轉(zhuǎn)移到一個中間量上，從

15、而使得最終解獲得很好的精度，因此可極大地緩解一般算法條件預(yù)優(yōu)的困難以及病態(tài)方程組的求解難度。數(shù)值計算的結(jié)果表明，算法對極其病態(tài)的線性方程組也可獲得較好的精度和穩(wěn)定性。6、塊三對角線性方程組的并行直接解法提出了分布式環(huán)境下求解塊三對角線性方程組的一種并行算法,該算法充分利用系數(shù)矩陣結(jié)構(gòu)的特殊性,通過對系數(shù)矩陣進行適當(dāng)分解及近似處理,使算法只在相鄰處理機間通信兩次.并從理論上給出了算法有效的一個充分條件.最后,在HPrx2600集群上進行了數(shù)值實驗,結(jié)果表明,實算與理論是一致的,并行性也很好.第二章 算法研究一、高斯消元法方法有多少1. 高斯消元法及其改進法1、高斯消元法 高斯消元法，又稱高斯消去

16、法。是線性方程組直接解法的基本法。2、列主元Gauss消去法列主元素消去法是為控制舍入誤差而提出來的一種算法,在高斯消去法的消元過程中,若出現(xiàn)a=0,則消元無法進行,即使其不為0,但很小,把它作為除數(shù),就會導(dǎo)致其他元素量級的巨大增長和舍入誤差的擴散,最后使計算結(jié)果不可靠.使用列主元素消去法計算,基本上能控制舍入誤差的影響,并且選主元素比較方便。3、 直接三角分解法 回顧高斯消元法的實質(zhì),是經(jīng)過一系列的初等變換,將方陣A分解為下三角矩陣L與上三角矩陣U的乘積 A=LU,這里 , , .對系數(shù)矩陣一旦實現(xiàn)了這種三角分解(稱為LU分解),那么此方程組就可寫為等價形式于是,容易先解出y,再求出x.4、

17、三對角方程組的追趕法應(yīng)用有限元法解結(jié)構(gòu)力學(xué)問題時，最后歸結(jié)為求解線性方程組，系數(shù)矩陣大多具有正定性質(zhì)。所謂平方根法，就是利用對稱正定矩陣的三角分解而得到的求解對稱正定方程組的一種有效方法，目前在計算機上廣泛應(yīng)用平方根法解此類方程組。5、 改進的平方根法 在許多應(yīng)用中，欲求解的線性方程組的系數(shù)矩陣是對稱正定的.所謂平方根法，就是利用對稱正定矩陣的三角分解而得到的求解具有對稱正定矩陣的線性方程組的一中有效方法。2. 經(jīng)典的高斯消元法經(jīng)典的線性方程組的直接解法是高斯消去法，這是國際上的通用稱呼，以數(shù)學(xué)家高斯命名，大約在1800年，高斯（Gauss）提出了高斯消元法并用它解決了天體計算問題。但高斯消去

18、法實是中國古法，早在公元一世紀時我國東漢初年成書的九章算術(shù)中已具雛形，至遲在公元263年我國三國時代的數(shù)學(xué)家劉徽在注解九章算術(shù)時已經(jīng)完成，并經(jīng)我國歷朝歷代的數(shù)學(xué)家們沿用至今。目前，高斯消元法以及有它改進、變形得到的選主元素消去法、三角分解法仍然是常用的有效方法。二、高斯消元法及其改進法方法比較1. 高斯消元法的優(yōu)缺點分析1. 線性方程組的直接解法及其應(yīng)用的優(yōu)缺點分析(1) 高斯消去法優(yōu)點：可以預(yù)先估計工作量。數(shù)據(jù)空間為系數(shù)矩陣、解向量、與常數(shù)向量所占的存儲空間，而所需要的額外空間與數(shù)據(jù)無關(guān)。缺點：利用高斯消去法進行消元時，消元過程能進行到底的充分必要條件是系數(shù)矩陣A的各階順序主子式不為零。對于

19、良態(tài)問題，高斯消去法也可能給出很壞的結(jié)果，這說明高斯消去法的算法很不穩(wěn)定。事實上，一般的矩陣都是病態(tài)矩陣，采用高斯消去法一般也不能得到滿意的結(jié)果。(2) 列主元消去法優(yōu)點：優(yōu)點在于沒有增加求解過程的運算量，但大大減小誤差.缺點：經(jīng)過列選主元后，其計算過程還是不穩(wěn)定的，不適于求解大規(guī)模的線性方程組。(3) 直接三角分解法優(yōu)點：直接三角分解法的優(yōu)點在于它的精度比高斯消元法高。缺點：矩陣A可以進行三角分解是有條件的，它要求A為方陣且A的所有順序主子式均不等于零。(4) 平方根法 優(yōu)點：計算量為a3次乘除法，約為一般高斯消去法的一半。 數(shù)值穩(wěn)定。 存貯量少，可只存貯對角線以下元素。缺點：平方根法的缺點

20、是需要n個開方運算。(5) 追趕法優(yōu)點：追趕法的計算量是比較小的，追趕法計算公式中不會出現(xiàn)中間結(jié)果數(shù)量級的巨大增長和舍入誤差的嚴重累積。缺點： 不足之處是當(dāng)某個時，就不能進行2. 最好的方法是最好的方法是直接三角分解法。（1）由于在求出和后，和就無須保留了，故上機計算時，可把和錯誤！未找到引用源。,y存在所占的單元，回代時取代錯誤！未找到引用源。整個計算過程中不需要增加新的存儲單元。而且系數(shù)矩陣的三角分解與右端常數(shù)項無關(guān)，故在計算系數(shù)矩陣相同而右端項不同的一系列方程組時，用三角分解法更為簡便。（2）如果已經(jīng)實現(xiàn)了A=LU的分解計算，且L,U保存在A的相應(yīng)位置，則用直接三角分解 法解具有相同系數(shù)

21、的方程組是相當(dāng)方便的，每解一個方程組僅需要增加n2次運算。第三章 算法應(yīng)用1、 高斯消元法方法怎么用1. 一般程序設(shè)計高斯消去法的matlab程序方法高斯消去法求解方程組.根據(jù)高斯消去法,編制matlab程序如下首先建立一個M-file文件,保存在work中,文件名為magauss.mfunction x=magauss(A,b,flag)%用途:Gauss消去法解線性方程組Ax=b%格式:x=guass(A,b,flag),A為系數(shù)矩陣,b為右端項,若flag=0,則不顯示中間過程,%否則顯示中間過程,默認為0,x為解向量if nargin<3,flag=0;endn=length(b

22、);%消元for k=1:(n-1) m=A(k+1:n,k)/A(k,k); A(k+1:n,k+1:n)=A(k+1:n,k+1:n)-m*A(k,k+1:n); b(k+1:n)=b(k+1:n)-m*b(k); A(k+1:n,k)=zeros(n-k,1); if flag=0,Ab=A,b,endend%回代x=zeros(n,1);x(n)=b(n)/A(n,n)for k=n-1:-1:1 x(k)=(b(k)-A(k,k+1:n)*x(k+1:n)/A(k,k);end再在工作窗口輸入:>> A=1 1 1 1;1 2 2 2;1 2 3 3;1 2 3 4;b=

23、4 3 2 1'>> x=magauss(A,b);x'得計算結(jié)果x = 5 0 0 -1二、高斯消元法方法用哪好？1. 高斯消元法方法在你所學(xué)專業(yè)的應(yīng)用 工程中求解結(jié)構(gòu)受力后的變形 空氣動力學(xué)中計算機翼周圍的流場 利用滑動最小二乘插值函數(shù)加權(quán)殘值法求解結(jié)構(gòu)動力學(xué)方程 2. 高斯消元法方法在你了解的其他領(lǐng)域的應(yīng)用 氣象預(yù)報中計算大氣的流動 在結(jié)構(gòu)動力學(xué)的動力反應(yīng)數(shù)值分析方法中有常加速度法，此方法通過迭代法逐步逼近解析解。利用高斯消元法及其改進法解線性方程組解決一些如道路的交通流量，電網(wǎng)的電流流量，解析幾何等的實際問題。第四章 算法展望我們所學(xué)的計算方法有：1. 插值

24、法2. 擬合法3. LU法4. 迭代法5. 冪法和反冪法6. 歐拉法7. 龍貝格法在機械專業(yè)的應(yīng)用舉例：1.插值法插值法空間插值從廣義上講應(yīng)分為空間點插值和空間面插值。兩者之間有許多不同之處:定義不同。點插值是指已知某些點的值來估計未知點的值;面插值是指已知統(tǒng)計變量在某一分區(qū)系統(tǒng)的值求在同一研究區(qū)內(nèi)另一分區(qū)系統(tǒng)下的統(tǒng)計變量的值。作用的數(shù)據(jù)對象不同。點插值主要用于自然地理數(shù)據(jù),是某些點的值;而面插值主要用于社會經(jīng)濟統(tǒng)計數(shù)據(jù),是統(tǒng)計單元上的集合數(shù)據(jù),是某些面的值。插值方法不同。如前所述,點插值和面插值的方法有極大的不同。插值方法的理論基礎(chǔ)不同。其在機械中的應(yīng)用有：基于減小修正量和提高工作效率的考慮

25、，應(yīng)用插值法中的牛頓插值，提出了一種簡單、實用的凸輪工作廓線的修正設(shè)計方法，這種方法不必再去考慮原有解析方程的形式，只需通過對要進行修正的曲線附近的一些離散點的數(shù)據(jù)進行處理，就能對現(xiàn)有凸輪工作廓線進行修正，特別適合凸輪曲線在實際使用中的局部修正設(shè)計2。2. 擬合法 曲線擬合法在工程機械發(fā)動機故障診斷中的應(yīng)用3.LU法高斯消元的過程實際是把系數(shù)矩陣A分解成單位下三角矩陣和上三角矩陣的乘積的過程。只要A為非奇異，經(jīng)過一定的行交換后，它一定可以分解為兩個三角形矩陣的乘積。設(shè)A=LU，其中L為單位下三角矩陣，U為上三角矩陣。這種分解就是杜立特爾分解，即LU分解。經(jīng)典的高斯消元法是1810年提出的，它稍

26、作修改產(chǎn)生矩陣的LU分解，則是二十世紀四十年代提出的，當(dāng)A非奇異時只要對A做行置換，總可使PA=LU,其中P為行置換矩陣，利用它求解線性方程組相當(dāng)于列主元消去法，它的好處是具有相同系數(shù)矩陣A的不同向量b的線性方程組AX=b可節(jié)省工作量，當(dāng)矩陣A對稱正定時可用LL分解的平方根法或改進平方根法，它是計算穩(wěn)定的。4. 迭代法對于給定的線性方程組x=Bx+f，用公式x(k+1)=Bx*+f逐步帶入求近似解的方法稱為迭代法。線性方程組的基本迭代法包括雅克比迭代法、高斯-賽德爾迭代法、SOR迭代法、分塊迭代法和共軛梯度法，迭代法有存儲空間小，程序簡單等特點，是解大型稀疏線性方程組的有效解法，經(jīng)常出現(xiàn)在邊值

27、問題和偏微分方程數(shù)值中。這些系統(tǒng)方程未知數(shù)n可達上萬個。而系統(tǒng)矩陣A非零元素很少。迭代法中收斂性與收斂速度十分重要，實用中以收斂速度較快的SOR法應(yīng)用最廣，但選出最優(yōu)參數(shù)是很困難的。其在機械中應(yīng)用有迭代學(xué)習(xí)法在機械壓力機滑塊位置控制中的應(yīng)用5. 冪法和反冪法冪法是計算矩陣主特征值（矩陣按模最大的特征值）及應(yīng)對特征向量的迭代法，計算簡單，特別是用于大型稀疏矩陣情形，但收斂速度往往不能令人滿意，使用時可以結(jié)合反冪法及位移技巧等手段加速收斂。反冪法是計算海森伯格陣或三對角陣的對應(yīng)一個給定近似特征值的特征向量的有效方法之一。6. 歐拉法歐拉方法是最簡單、最古老的一種數(shù)值方法?；舅悸肥怯貌钌探茖?dǎo)數(shù)。其在機械中的應(yīng)用有基于牛頓歐拉法的4-UPS-RPS機械剛體動力學(xué)分析。 7. 龍貝格法龍貝格方法是目前計算機上求積的重要方法，針對積函數(shù)變化不均勻的自適應(yīng)方法也是以此為基礎(chǔ)給出的.第五章 學(xué)習(xí)思考 時間總是過得很快，轉(zhuǎn)眼間已經(jīng)接近學(xué)期末了，學(xué)習(xí)數(shù)值計算也已經(jīng)一個學(xué)期了。剛開始感覺還可以，知識接受起來比較容易，后來慢慢的感覺越來越難，上課時越聽越朦朧。雖然聽