1、多重網(wǎng)格算法綜述鄒靜文6摘要本文總結(jié)了多重網(wǎng)格算法的基礎(chǔ)理論，剖析了多重網(wǎng)格方式的一種并行模式和總結(jié)了已取得的功效和待擴充的領(lǐng)域。對多重網(wǎng)格方式的大體思想有一個較詳細的概述，比較分析了單一網(wǎng)格和多重網(wǎng)格的計算結(jié)果，并對多重網(wǎng)格的并行模式進行了探討和分析。關(guān)鍵詞多重網(wǎng)格算法，套迭代，粗網(wǎng)格校正，并行模式，交織多重網(wǎng)格，區(qū)域分解一、引言多重網(wǎng)格法(MultipleGridMethod),簡稱MG方式是最近幾年來求解偏微分方程邊值問題的快速方式之一，本文參考前人的文獻資料，并結(jié)合所學(xué)知識，總結(jié)多重網(wǎng)格法的基礎(chǔ)理論，包括多重網(wǎng)格的應(yīng)用原那么、具體實現(xiàn)步驟和計算結(jié)果的分析和比較。其計算結(jié)果說明：多重網(wǎng)格

2、方式具有收斂速度快的優(yōu)勢，當(dāng)多重網(wǎng)格方式所用層數(shù)越多，生效速度就越快；而且撞制粗、細網(wǎng)格層之間自適應(yīng)轉(zhuǎn)換的撞制參數(shù)在選取上有專門大的靈活性；能夠看出隨著剖分的加密，單一網(wǎng)格方式達到收斂所需的迭代次數(shù)顯著增加，而多重網(wǎng)格方式所需迭代次數(shù)大體上不隨網(wǎng)格的疏密和層數(shù)而轉(zhuǎn)變，這說明多重網(wǎng)格方式具有與網(wǎng)格參數(shù)無關(guān)的收斂性。二、多重網(wǎng)格方式的基礎(chǔ)理論多重網(wǎng)格方式的最初被提出是由于在網(wǎng)格方程迭代求解時，誤差的各個Fourier分量的衰減程度不同。熟悉到高頻振蕩誤差是局部行為，來源于周圍幾個網(wǎng)格點之間的彼此藕合，與邊界或距離較遠的網(wǎng)格點信息無關(guān)；而低頻滑膩誤差是全局行為，要緊來源于邊界信息。傳統(tǒng)的點或塊松弛都

3、是局部性較強的方式，因此它們能迅速抹平局部性的高頻振蕩誤差，但對全局性的低頻滑膩誤差卻衰減緩慢。事實上，通過初始幾回迭代后，誤差將呈現(xiàn)滑膩性。因此，適應(yīng)上稱能迅速抹平高頻振蕩誤差，使誤差趨于滑膩的松馳方式為有效滑膩方式，并用松馳因子來刻畫它們的滑膩效應(yīng)。多重網(wǎng)格方式思想的引入考慮在簡單區(qū)域上泊松方程的第一類邊值問題(狄立克雷邊值問題)：u(x.y)f(x,y),(x,y)u(x,y)0,(x,y)那個地址是一個單位正方形，是那個正方形的邊界如以下圖所示：u=0u=00u=0Q1£u=0在以步長為h的網(wǎng)格上h離散后，取得一個線性系統(tǒng)Lhuh九，其中Lh是一個稀疏矩陣。一樣采納經(jīng)典的迭代

4、法如Guass,seidel迭代、Jaccobi迭代、SOR迭代等，不難發(fā)覺如下一個事實：開始的幾回迭代近似解與真解之間的誤差衰減專門快，可是后來的迭代誤差去衰減很慢。而且系數(shù)矩陣Lh的條件數(shù)越高，達到必然精度所需要的迭代次數(shù)越多。通過對迭代進行傅立葉分析，咱們發(fā)覺處在高頻的誤差分量在迭代的進程中迅速衰減，而處在低頻的誤差分量確衰減的很慢。為了解決那個問題，多重網(wǎng)格方式應(yīng)運而生。通過局部松馳后誤差呈現(xiàn)滑膩性，現(xiàn)在誤差要緊來源于邊界。能夠假想二維NN網(wǎng)格上的點松馳方式，將邊界信息傳播到所有點至少需O(N)次迭代，因此收斂速度奇慢。不妨將網(wǎng)格方程的剩余部份(殘差)限制到粗網(wǎng)格上進行。在粗網(wǎng)格上精準

5、求解后，將所得解延拓到細網(wǎng)格上，與原先近似解組合，形成網(wǎng)格方程的近似解，稱這一進程為粗網(wǎng)格校正。在粗網(wǎng)格上，由于網(wǎng)格點少，邊界信息能較快地傳播到所有網(wǎng)格點，收斂速度將加速。一樣地，在粗網(wǎng)格上也存在高、低頻誤差，類似于細網(wǎng)格，進行幾回局部松弛排除高頻誤差后，能夠?qū)⒌皖l誤差再轉(zhuǎn)移到更高層網(wǎng)格。如此進行下去，直到最高層網(wǎng)格，那里未知量個數(shù)超級少，直接精準求解的工作量可忽略不計。然后從高層到低層依次將所得解返回、組合，在最細網(wǎng)格上最終形成一個近似解，這一遞歸性質(zhì)稱為套迭代技術(shù)。多重網(wǎng)格算法確實是如此將問題的求解散布在不同的層上，所有層彼此和諧地求解同一問題的。事實上，現(xiàn)在的粗網(wǎng)格校正確實是起到將邊界信

6、息迅速傳播到所有網(wǎng)格點的作用。細網(wǎng)格松弛、粗網(wǎng)格校正和套迭代技術(shù)是多重網(wǎng)格算法的三大支柱。細網(wǎng)格松弛負責(zé)排除高頻振蕩誤差，粗網(wǎng)格校正負責(zé)排除低頻滑膩誤差，套迭代技術(shù)負責(zé)通過限制和延拓算子連接所有層一起求解同一問題。可見多重網(wǎng)格算法的大體思想是:(1)一個問題能在不同規(guī)模的網(wǎng)格上求解；(2)細網(wǎng)格僅僅只需負責(zé)排除高頻誤差，而粗網(wǎng)格負責(zé)排除低頻誤差。多重網(wǎng)格方式的應(yīng)用原那么下面從算法對物理問題的離散格式、松弛方式、限制與延拓、網(wǎng)格粗化策略和套迭代技術(shù)的需求，別離論述應(yīng)用多重網(wǎng)格算法的大體準那么。離散格式離散格式必需是穩(wěn)固的。格式的數(shù)值穩(wěn)固性是一種局部行為，將致使解的局部高頻振蕩，使得松弛方式在細網(wǎng)

7、格上無法有效滑膩誤差，從而使多重網(wǎng)格算法的效率將很低，乃至發(fā)散。而離散解滑膩部份的穩(wěn)固性一樣僅僅依托于微分方程本身的穩(wěn)固性，與離散格式關(guān)系不大。固然，物理問題本身的穩(wěn)固性是一個大體前提。由于離散格式的穩(wěn)固性是局部行為，要求離散格式能將方程本身在一個或幾個網(wǎng)格步長上的所有振蕩較好地描述出來，以便于松弛方式有效地排除?？墒牵瑢o定的步長h,只判定格式是不是穩(wěn)固是不夠地，還應(yīng)該給出一個尺度來刻畫這種穩(wěn)固性的程度。h橢圓性確實是一個專門好的判別方式。具有h橢圓性的離散格式，都必然存在一種有效的松弛方式，排除所有高頻誤差。松弛方式總原那么是讓殘差從細網(wǎng)格限制到粗網(wǎng)格之前充分滑膩?；佇?yīng)的氣宇采納滑膩因

8、子，可通過局部模分析方式簡單地獲取。假設(shè)在每層網(wǎng)格上松弛次，那么可用預(yù)測多重網(wǎng)格算法的近似最優(yōu)收斂因子。松弛時要注意以下幾點：(1)每層網(wǎng)格上松弛次數(shù)不宜過量(一樣23次)，只需要排除高頻誤差，因為松弛到必然程度，低頻誤差將占主導(dǎo)地位，與高頻誤差彼此禍合，無助于限制之前殘差的滑膩。(2)最好具有數(shù)值穩(wěn)固性，幸免迭代進程中的高頻振蕩。(3)點松弛方式僅滑膩最強藕合方向的誤差，對存在次藕合方向的問題，如各向異性問題、奇異擾動問題，那么必需采取塊迭代方式，如線松弛、平面松弛，使位于同一塊的所有未知量被同時松弛或使強禍合方向的未知量被同時松弛。(4)滑膩因子不宜過小，一樣使得多重網(wǎng)格算法的收斂因子在左

9、右為最正確。GuassSeidel迭代是一個較好的選擇。(5)滑膩方式盡可能追求Robust性，使多重網(wǎng)格算法適應(yīng)多種類型的問題。限制與延拓要緊考慮算子的階，它們依托于原始方程中導(dǎo)數(shù)的階。設(shè)含有q個未知函數(shù)白q個微分方程。mj表示第j個未知函數(shù)在第i個方程中的最高導(dǎo)數(shù)的階。設(shè)這j個未知函數(shù)在限制和延拓進程中彼此獨立。令mj表示第j個未知函數(shù)的延拓階，m表示第i個方程殘差限制階。那么應(yīng)有以下關(guān)系式成立：(1)低頻調(diào)和空間中高頻通過粗網(wǎng)格校正振幅被放大1O(hmimjmij)倍。故為了i.j幸免由于粗網(wǎng)格校正引發(fā)高頻振蕩，應(yīng)有mmjmij,同時也能夠看出mimjmi,j1是沒必要要的。(2)細網(wǎng)格

10、限制時，每一個高頻對低頻振幅的奉獻為O(hmi%),故應(yīng)有mmj,對那些高、低頻彼此禍合的松弛方式，如Gauss一Seidel迭代，還應(yīng)有k(mij比)，其中O(rkj)為高頻誤差在第j個方程由于松弛所產(chǎn)生的對低頻的奉獻。(3)對完全多重網(wǎng)格算法(FMG),第j個未知函數(shù)從粗網(wǎng)格到細網(wǎng)格第一次延拓的階mj,必需知足mjplj,以保證細網(wǎng)格上第一次顯現(xiàn)的高頻誤差的階不小于微分方程的離散階p,其中l(wèi)j為第j個方程微分算子的階。網(wǎng)格粗化策略從程序設(shè)計的模塊化、易移植性動身，一樣采納標準網(wǎng)格粗化策略(步長在所有方向擴大一倍)。但為了維持點松弛，對特殊問題能夠采納半粗化策略，即僅粗化藕合方向網(wǎng)格，使之也

11、變成強藕合方向。粗網(wǎng)格上方程離散格式和迭代方式都能夠與細網(wǎng)格上的不同，對對稱正定算子，典型代表為Galerski近似。套迭代技術(shù)一樣采納V或W循環(huán)，W循環(huán)能維持收斂因子不隨網(wǎng)格的轉(zhuǎn)變而轉(zhuǎn)變，具有Robust性，但代價相對昂貴；當(dāng)網(wǎng)格層不多時，V循環(huán)具有一樣的性質(zhì)，但計算量小，因此更受歡迎。除此之外，還存在S循環(huán)、F循環(huán)，它們的性能介于V循環(huán)與W循環(huán)之間，視具體情形可別離采納。多重網(wǎng)格方式最簡單的橢圓型問題是Poisson方程uf,QRd()多重網(wǎng)格算法迭代的大體步驟：對式進行離散，取得的方程組Lu=f()其中，L是個通過離散所取得的系數(shù)矩陣。在網(wǎng)格步長為h(細網(wǎng)格)的網(wǎng)格點上，方程知足Lhuh

12、fh關(guān)于方程傳統(tǒng)的迭代方式是在確信的一種網(wǎng)格h上采納某種迭代解法，例如GaussSeidel迭代法、超松弛法(SOR)和它們改良的迭代技術(shù)，而多重網(wǎng)格方式采納不同品級的網(wǎng)格剖分。假定有一組網(wǎng)格0,1,.,i稱為網(wǎng)格序列k(k0,1,.,l),隨著k的增加,網(wǎng)格愈來愈細，這些網(wǎng)格都逼近同一區(qū)域，相應(yīng)的有網(wǎng)格步長序列hk,算子序列Lk。與傳統(tǒng)計算方式不同，多重網(wǎng)格方式采納一系列不同步長的網(wǎng)格層。因為場值的誤差在粗網(wǎng)格層上猛烈擺動，因此在粗網(wǎng)格層上對誤差進行迭代將加速收斂速度。誤差從細網(wǎng)格層到粗網(wǎng)格層的變換進程稱為限制，即將細網(wǎng)格層上與某一網(wǎng)格點相鄰的假設(shè)干個點的信息通過必然的權(quán)重濃縮到粗網(wǎng)格層的該

13、點。在粗網(wǎng)格層上對場值的誤差進行迭代后，必需將粗網(wǎng)格層上的誤差通過插值補充出細網(wǎng)格層上的函數(shù)值，這一插值進程稱為延拓。能夠看出，限制和延拓是互逆的。在每一層網(wǎng)格迭代前對場值的誤差進行限制，完成最粗一層網(wǎng)格迭代后對其進行延拓。多重網(wǎng)格法的一個重要方面確實是通過遞歸挪用二重網(wǎng)格方式來做近似。也確實是殘差方程不是通過直接方式求解，而是用幾回松弛磨光來磨掉高頻誤差，固然是伴隨向更粗一級網(wǎng)格上殘差限制，這確實是多重網(wǎng)格法的思想。如此多重網(wǎng)格方式的一系列問題將在不同網(wǎng)格大小的嵌套網(wǎng)格上取得解決。多重網(wǎng)格算法依照在每層上作校正循環(huán)的次數(shù)又能夠分為多重網(wǎng)格V一循環(huán)和多重網(wǎng)格W一循環(huán)算法。多重網(wǎng)格V一循環(huán)算法是

14、從最細網(wǎng)格一直到最粗網(wǎng)格，然后又返回到最細網(wǎng)格上的一種計算進程。若是一個V一循環(huán)算法是在每層上作二次校正循環(huán)，然后返回到下一級細網(wǎng)上，這確實是多重網(wǎng)格W一循環(huán)算法。計算結(jié)果和分析一一單一網(wǎng)格和多重網(wǎng)格的比較考慮以下的二維線性對流擴散方程的定解問題22uuuu”、b(),(x,y)(0,1)(0,1)(1)xyxyu(0,y)0,u(1,y)1誓*expb1u(x,0)exp(bx)1,u(x,1)2u(x,0).expb1選擇這必然解問題主若是可求得其精準解,以查驗所給出的混合有限分析多重網(wǎng)格法計算的有效性，求得此定解問題的精準解是u(x,y)exp(bx)expbexp(by)expb/取x

15、向和y向步長為h和k,將計算區(qū)域(0,1)(0,1)進行均勻剖分，在離散網(wǎng)格上成立方程(1)的混合有限分析格式Cn1n1n1n1ni,j1Ui,j1uijCi,j1ui,j1Ci1,jUi1,jCi1,jUi1,j(3)將計算區(qū)域均勻剖分為3333個結(jié)點，單一網(wǎng)格和多重網(wǎng)格中最細網(wǎng)格的步長hk。多重網(wǎng)格取4層，最粗網(wǎng)格步長為8h8k。計算中取方程(l)中b=12。在單一網(wǎng)格上求代數(shù)方程組(3)的收斂解。關(guān)于多重網(wǎng)格，因方程(l)是線性的，故在每層網(wǎng)格上的混合有限分析系數(shù)僅與該層步長有關(guān)。具體計算是在最細網(wǎng)格上完成一次迭代后，嵌入多重網(wǎng)格循環(huán)，咱們采納V循環(huán)。5收斂判據(jù)取10,關(guān)于多重網(wǎng)格收斂要

16、求最細網(wǎng)格上殘差范數(shù)Rc,RcR2(i,j)/NXY1/2，其中NXY(Imax1)(Jmax1),Imax和Jmax是最細網(wǎng)格上X和y方向的最大結(jié)點數(shù)；R(i,j)是最細網(wǎng)格結(jié)點(i,j)上的殘差。圖l是計算區(qū)域?qū)蔷€上的計算結(jié)果與精準解的比較.可見不管是單一網(wǎng)格仍是多重網(wǎng)格用混合有限分析法計算結(jié)果都是同精準解吻合的專門好。田J時用線上計算值圖2是迭代的收斂進程，也是殘差的衰減進程。圖中的工作單位等價于在最細網(wǎng)格上進行一次單獨的滑膩迭代所需的計算量。關(guān)于標準粗化系列，較粗網(wǎng)格上4次迭代相當(dāng)于相鄰細網(wǎng)上一次迭代。由圖能夠看出多重網(wǎng)格法的收斂速度比單一網(wǎng)格法快很多，所需工作單位少得多，計算證明了

17、多重網(wǎng)格法的優(yōu)越性.圖中A、B、C表示第一、二、三個多重網(wǎng)格循環(huán)cftl1-»1*11口口0102030405060圖2收斂曲線最細網(wǎng)格剖分17X1733X3365X65129X129網(wǎng)格層數(shù)3456最細網(wǎng)格步長最粗網(wǎng)格步長圖4給出了4種不同疏密剖分時，應(yīng)用單一網(wǎng)格方式和多重網(wǎng)格方式計算達到收斂解所需的工作單位。能夠看出隨著剖分的加密，單一網(wǎng)格方式達到收斂所需的迭代次數(shù)顯著增加，而多重網(wǎng)格方式所需迭代次數(shù)大體上不隨網(wǎng)格的疏密和層數(shù)而轉(zhuǎn)變。這說明多重網(wǎng)格方式具有與網(wǎng)格參數(shù)無關(guān)的收斂性。即收斂率是大體上相同的。圖5是4套多重網(wǎng)格的收斂曲線。能夠看出這些曲線的斜率，也確實是說，多重網(wǎng)格方式

18、的收斂率不受網(wǎng)格疏密的阻礙。圖4達到收斂孵所需1柞單傳圖5名址廂格收斂曲線三、多重網(wǎng)格方式的一種并行模式作為求解離散微分方程的一種迭代法，多重網(wǎng)格方式有效地利用了迭代進程的誤差校正特性和對高頻誤差分量的滑膩特性，改變了傳統(tǒng)的作法，作了變革性的構(gòu)造。其斂速與步長h無關(guān)，計算工作量為O（N）（N為離散格點數(shù)）?？傊嘀鼐W(wǎng)格法是一種高效率迭代法。在求解邊值問題的近似解方面，為了高效求解大型方程組的需要，人們嘗試并行處置。而區(qū)域分解法是并行計算最活躍的研究和應(yīng)用領(lǐng)域之一。其大體方式是把一個復(fù)雜區(qū)域（或系統(tǒng)），依照必然原那么（如物理特性、幾何形狀、離散方式、算法特點與處置器個數(shù)）分解成假設(shè)干子系統(tǒng)，要

19、緊采納高效快速迭代法求解原始問題?；谝陨暇壒剩岢隽艘环N并行的多重網(wǎng)格方式一一交織多重網(wǎng)格法。其對邊值問題的并行處置有別于通常的區(qū)域分解方式。通常的區(qū)域分解是將復(fù)雜區(qū)域分解成較小的子區(qū)域（重疊或不重疊）的和集。而交織多重網(wǎng)格法的思路是先將大區(qū)域離散劃分成網(wǎng)格，然后于網(wǎng)格中交織取點，分成假設(shè)干較粗的子網(wǎng)格，將這些子網(wǎng)格置于不同的處置器上，用通常的多重網(wǎng)格法計算其上邊值問題。最后，將這些不同處置器粗網(wǎng)格上的解組合成大區(qū)域的網(wǎng)格上的近似解。從數(shù)學(xué)上看，交織多重網(wǎng)格方式思路如下：設(shè)有邊值問題uf,在上六二（）ug,在上將劃分為步長h的細網(wǎng)格后，問題離散為求解方程組Lhuhfh然后，于LhUhfH（H

20、>h）設(shè)式的解析解為u*,方程組、的精準解為uh,uH。隨著h趨近于零，uh是趨近于u*。設(shè)用迭代法近似求解方程組及所得近似解為Uh及Uh。能夠看出，想用Uh組合成逼近Uh的近似解是沒有理論依據(jù)的?？墒牵煽紤]用Uh的組合作為較好的初始值，用適合的迭代法（包括多重網(wǎng)格方式）來求出知足精度要求的逼近uh的近似解。因此，利用交織多重網(wǎng)格法加速邊界值的信息傳遞以取得較好的初值，并結(jié)適合當(dāng)?shù)牡ㄇ蟮弥幸饩鹊慕平?。四、已取得的功效和待擴充的領(lǐng)域多重網(wǎng)格算法通過近30年的研究，在經(jīng)典應(yīng)用領(lǐng)域一線性和非線性、標量和非標量橢圓型間題取得了豐碩的功效，每一個未知量只需十多次算術(shù)運算便能在誤差許諾范圍

21、內(nèi)正確求解，具有內(nèi)在并行性，而且能適應(yīng)這些情形：自由邊界問題，狹小區(qū)域問題，各類類型的奇異與非持續(xù)性，局部網(wǎng)格細化，嚴峻非線性問題，區(qū)域中含有粗網(wǎng)格上不可見的小洞問題，高振蕩邊界問題等等。在彈性力學(xué)，網(wǎng)格生成技術(shù)方面也取得了一樣的效率。類似于橢圓型問題，從80年代開始，多重網(wǎng)格算法已深切到計算流體力學(xué)（CFD）,時刻相關(guān)間題、波動方程、積分方程等領(lǐng)域。對流體力學(xué)Euler方程、Stokes方程、Navier-Stokes方程、位勢方程中的大量定常與非定常問題，加入人工粘性，采納適當(dāng)?shù)碾x散格式（如迎風(fēng)格式，矢通量割裂格式，半離散格式）后，能以一樣的效率求解。在捐軀一至幾個數(shù)量級效率條件下，能夠成功求解含單族或多族特點線的高雷諾數(shù)不可緊縮流問題。多重網(wǎng)格算法在求解來自波動方程的高不適定問題時，成效超級不睬想，但如果是轉(zhuǎn)化為積分問題，那么成效要好得多。一樣，這種轉(zhuǎn)換也適合求解特點值或特點函數(shù)問題。對時刻相關(guān)拋物型問題，不但在求解隱式離散格式時與橢圓型算子具有一樣的效率，而且只要問題本身在時刻方向上滑膩，那么求解進程在時刻方向訪問細網(wǎng)格的次數(shù)很少，能迅速達到穩(wěn)固狀態(tài)。多重網(wǎng)格算法被推行到別