拋物問題的顯-隱有限差分區(qū)域分解并行算法.pdf

1、數(shù)學物理及工程問題，如油氣藏的勘探與開發(fā)、航天飛行器的設計、大型水利設施的建筑、空氣動力學、天體物理學等等，無不歸結為求解高維的大型偏微分方程模型問題.這些問題往往是高維的，計算規(guī)模大而且計算區(qū)域形態(tài)不規(guī)則，給計算帶來很大的困難.與此同時，我們對計算精度的要求越來越高，而單機計算的速度已遠遠不能滿足實際的需求.隨著大規(guī)?？茖W計算的需要和并行計算環(huán)境的發(fā)展成熟，區(qū)域分解方法已成為數(shù)值求解偏微分方程最有效的方法之一。 簡而言之，區(qū)域

2、分解方法就是把計算的區(qū)域分裂成若干子區(qū)域，子區(qū)域的形狀盡可能的規(guī)則.從而原問題的求解轉化成在各個子區(qū)域上分別解決問題.區(qū)域分解算法具有很多其他方法無以比擬的優(yōu)越性:首先，它把大型的問題轉化為若干小型問題，縮小計算的規(guī)模；其次，它各子區(qū)域上的計算是并行的，縮短計算的時間；再次，它允許在不同的子域上選用不同的數(shù)學模型，以便整體模型更適合于工程物理的實際情況；然后，它允許使用局部擬一致網(wǎng)格。無需用整體擬一致網(wǎng)格，甚至各子上可以采用不同的離散方

3、法進行計算；最后，若子區(qū)域的形狀足夠規(guī)則，可使得其上或者已有熟知通用的快速算法，或者已有解這類規(guī)則問題的高效軟件備用.當然，區(qū)域分解方法還有其他的優(yōu)點，但以縮小規(guī)模及并行計算尤為根本。 用區(qū)域分解法來求偏微分方程數(shù)值解已有大量研究[35，47，48，50，51，52].他們把這種方法應用于求解橢圓問題[59，60]、對稱正定線性系統(tǒng)[61]以及拋物問題[31-34，44]等.同時，區(qū)域分解方法也是構建預條件子的有效方法之一[41

4、].區(qū)域分解算法的主要困難在于，如何定義內邊界點的值和在子區(qū)域上選取合理的計算解去近似.于是，區(qū)域分解方法劃分為兩類:重疊型區(qū)域分解法和非重疊型區(qū)域分解法.子區(qū)域的選擇主要考慮區(qū)域形狀的可計算性以及問題的物理背景.尤其是后者，特別適用于在不同物理子區(qū)域上有不同控制方程的復合問題.非重疊型區(qū)域分解方法。比重疊型區(qū)域分解方法實現(xiàn)起來比較直觀易用，但它的理論分析往往比較困難。 重疊型區(qū)域分解法的原始思想來源于經(jīng)典的Schwarz交替法

5、.近年來建立在Schwarz交替法基礎上的區(qū)域分解法在理論分析和實際應用中取得令人注目的發(fā)展.從橢圓方程到拋物方程，從加性或乘性Schwarz算法發(fā)展到并行或串行子區(qū)域校正算法，從混合元到特征差分[12-16，36]，此類算法已成為一種行之有效的迭代方法.然而，由于其子區(qū)域的部分重疊性，也在一定程度上使得并行計算有所牽制。非重疊型區(qū)域分解法將計算區(qū)域分解成若干個獨立的不同子區(qū)域，具有高度并行、更適合模型要求和網(wǎng)格剖分靈活等優(yōu)點.對于此方

6、法，內邊界上的預處理方法是必須要考慮的.顯-隱格式區(qū)域分解方法就是以顯格式計算出相鄰子區(qū)域相交內邊界的近似值的一種方法.顯-隱格式區(qū)域分解方法綜合了二者的優(yōu)點，借助前一層數(shù)值解的信息，用顯格式給出在這一層的子問題的未知內邊界條件，把一個整體區(qū)域上的問題化為若干個子區(qū)域上的子問題，在每個子區(qū)域上用隱式方法求解，從而實現(xiàn)了并行.由計算角度而言，就是把一個整體的大型方程組分解為若干個小型方程組，實現(xiàn)了并行.由于給出子區(qū)域間內邊界條件的方法利用

7、了上一層數(shù)值解的信息，具有顯性性質，導致了算法需要一個穩(wěn)定性條件，但這個穩(wěn)定性條件沒有顯式方法那么嚴格。 關于各類區(qū)域分解方法，前人也做了很多研究:X.C.Cai[59，60，61]等給出了關于多種橢圓方程的基于重疊不匹配網(wǎng)格的重疊mortar有限元、有限差分方法的理論分析.C.N.Dawson，Q.Du和T.F.Dupont[31-34，44]等提出了多種顯-隱區(qū)域分解的有限差分及有限元算法，給出了相應的誤差估計.然而只是基于

8、熱傳導方程提出的，且對高維問題的分析只討論了內邊界上一個方向的顯式情形.張寶琳[25，27，30]等將Saul'yev的非對稱差分格式應用于一對內邊界點，或將具有較高穩(wěn)定性的顯格式置于內邊界點重寫了Dawson的區(qū)域分解方法，但并沒有提高整體精度.李長峰[1，2，3]研究了關于熱傳導方程、拋物方程的基于Dawson思想的區(qū)域分解有限差分算法，得到了類似的結論。 在導師芮洪興教授的精心指導下，本文作者在前人工作的基礎上，對區(qū)域分解

9、方法做了部分研究工作.結合杜強教授的在內邊界應用多步顯格式的算法，我們將迎風格式、高精度格式或不匹配網(wǎng)格應用到非重疊顯-隱有限差分區(qū)域分解算法，對變系數(shù)熱傳導問題或一般拋物問題給出了最大模誤差分析，并通過數(shù)值實驗得到的數(shù)值結果驗證了算法的有效性.這種算法在內邊界處，不僅采用大步長的空間步長，而且將每一個時間層分為若干子層，用較小的時間步長進行若干次顯格式計算，在得到內邊界點的近似值后，用隱格式在各個子區(qū)域上并行計算求出內點的值.此算法不

10、僅擴大了原來顯格式的穩(wěn)定性條件，而且有較好的并行性.全文共分四章。 第一章:由于關于此類算法大部分討論的是常系數(shù)的問題，我們給出關于變系數(shù)熱傳導方程的顯-隱有限差分區(qū)域分解算法.大體的做法是在內邊界點以較小的時間步長￣Δt和較大的空間步長￣h進行J次顯格式計算.然后，再用隱格式在各個子區(qū)域并行計算，得到的整體精度為O(Δt+h2+J￣h3).同時，這種算法較古典顯格式的穩(wěn)定性至少放寬了Jd2倍，計算格式也很簡單，易于并行程序的實

11、現(xiàn)。 第一章內容安排如下:關于一、二維的算法和誤差估計將分別在1.2和1.3節(jié)給出.首先，在1.2.1節(jié)給出了一維變系數(shù)熱傳導問題的模型，然后在1.2.2-1.2.4節(jié)討論了一致剖分網(wǎng)格情形，時空不同剖分情形和多個子區(qū)域的情形.在1.3.1節(jié)給出了二維變系數(shù)熱傳導問題的模型之后，關于2個子區(qū)域和4個子區(qū)域的二維區(qū)域分解方法分別在1.3.2和1.3.3節(jié)討論.最后，在1.4節(jié)我們用數(shù)值算例驗證了我們的結論.本章部分結果已經(jīng)在《山東

12、大學學報》(理學版)上發(fā)表。 第二章:我們給出穩(wěn)定性條件寬松的高精度有限差分區(qū)域分解方法.關于一維拋物問題，我們把區(qū)域劃分為一些互不相交的多個等距剖分的子區(qū)域.我們在內邊界點采用高精度的顯式差分格式，而且在內邊界點取小的時間步長￣Δt和大的空間步長￣h計算.在得到內邊界處的近似值后，再在內點采用高精度的緊交替方向隱式差分格式并行計算.這種有限差分區(qū)域分解方法得到了較好的收斂精度O(Δt2+h4+Jq￣h5)，而且該算法的計算格式

13、也很簡單，易于編程實現(xiàn).對于高維拋物問題，我們同樣地在內邊界點采用一族高精度的兩層顯式差分格式，在內點用緊交替方向隱格式進行計算.在這些格式采用的基礎上，我們首先把穩(wěn)定性條件的界較古典顯格式擴大了Jd2倍，其次，在內邊界點的格式是關于x和y方向都是顯式的，然后，在內點的隱格式是可以再并行的，且其中的系數(shù)矩陣是三對角陣，可以提高并行效率.最后，也是最重要的是，這種區(qū)域分解算法的整體精度為D(△t2+￣hΔt+J￣h3)，而且當選取特殊的d

14、和網(wǎng)格比￣r后，精度可以達到O(△t2+h4+Jh5)。 第二章:內容是這樣安排的:首先，在2.2節(jié)，我們不但介紹了關于一維拋物問題的一些預備知識，還在之后的各個小節(jié)分析了算法、誤差估計和并行效率.然后，關于二、三維的區(qū)域分解算法和誤差分析我們將分別在2.3和2.4節(jié)中給出.最后，在2.5節(jié)我們用一些數(shù)值算例驗證了算法的穩(wěn)定性和數(shù)值精度.本章部分結果已經(jīng)在《International Journal of Computer Ma

15、thematics》上發(fā)表。 第三章:討論的是不匹配網(wǎng)格的有限差分區(qū)域分解方法.不匹配的區(qū)域分解方法在子區(qū)域采取了不同的剖分，所以在內邊界處有一些不匹配的點.在這一章，我們將修正的Saul'yev非對稱格式和古典隱格式相結合，得到一種在內邊界使用的簡單的新顯格式，然后就給出非重疊不匹配有限差分區(qū)域分解算法.這種算法在二維情形的大多數(shù)內邊界點是關于x和y方向都是顯格式的，而且，它的穩(wěn)定性條件為r≤1，這比古典顯格式的穩(wěn)定性條件在一

16、維情形下擴展了2D2倍，在二維時擴展了4D2倍.當計算出內邊界點的值后，就只剩下求解兩個互不相關的、可并行計算的隱式差分問題.另外，這個區(qū)域分解算法的精度為O(Δt+h21+h21+H3)，計算格式也很簡單，易于并行程序的實現(xiàn).關于一、二維問題的區(qū)域分解算法和數(shù)值解的收斂性結果分別在3.2節(jié)和3.3節(jié)給出.最后，在3.4節(jié)我們用一些數(shù)值算例驗證了算法的穩(wěn)定性和數(shù)值精度。第四章，我們不但將多層顯一隱差分區(qū)域分解算法由第一章的熱傳導方程擴展

17、到一般拋物方程，而且介紹了三類區(qū)域分解的迎風差分算法.關于一維拋物問題，我們首先在4.2節(jié)給出一維一般拋物方程的模型和預備知識，并在4.3節(jié)給出了關于此模型的有限差分區(qū)域分解算法.其次，我們在4.4節(jié)給出了三類迎風差分算法，包括一階迎風差分算法(UDA)、內邊界二階迎風差分算法(IMUDA)和二階迎風差分算法(MUDA).一階迎風差分算法是在內邊界點和內點上分別采用顯、隱的一階迎風差分格式的算法，內邊界二階迎風算法是只在內邊界點處采用二