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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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