改進(jìn)的Semi-Lagrangian算法及其應(yīng)用.pdf

1、本文主要是研究如何設(shè)計(jì)有效的自適應(yīng)算法和并行算法，用以復(fù)興傳統(tǒng)的Semi—Lagrangian算法。首先我們重新分析了算法的收斂性，給出了相對(duì)簡(jiǎn)化的ε一致的先驗(yàn)誤差估計(jì)。然后針對(duì)對(duì)流問(wèn)題和Semi—Lagrangian算法的特點(diǎn)，我們給出了新型的時(shí)間誤差指示子，及其后驗(yàn)誤差估計(jì)?；谶@個(gè)新型的時(shí)間誤差指示子，我們還給出了在收斂階和正則性要求上都是最優(yōu)的時(shí)間上的先驗(yàn)誤差估計(jì)。在用有限元方法進(jìn)行空間離散后，我們給出了完全離散格式的后驗(yàn)誤差估

2、計(jì)，并設(shè)計(jì)了相應(yīng)的自適應(yīng)算法。再然后，我們對(duì)傳統(tǒng)的時(shí)間并行算法進(jìn)行了改進(jìn)，將其與時(shí)間自適應(yīng)算法相結(jié)合，設(shè)計(jì)了自適應(yīng)的時(shí)間并行算法。最后，我們運(yùn)用Semi—Lagrangian算法進(jìn)行非牛頓流體的數(shù)值模擬，給出了數(shù)值算法，算法相關(guān)實(shí)現(xiàn)的細(xì)節(jié)以及數(shù)值模擬結(jié)果。
　　 Semi—Lagrangian算法是在20世紀(jì)80年代初提出的([36，80])。該算法將時(shí)間導(dǎo)數(shù)項(xiàng)和對(duì)流項(xiàng)同時(shí)處理，并沿著特征線方向進(jìn)行時(shí)間離散。由于算法是基于Lag

3、rangian觀點(diǎn)，所以可以將方程對(duì)稱化，線性化。數(shù)值解在使用精確積分時(shí)是無(wú)條件穩(wěn)定的，因此允許使用較大的時(shí)間步長(zhǎng)。算法提出后，就被研究人員應(yīng)用到了不同的實(shí)際問(wèn)題上去，例如對(duì)流擴(kuò)散問(wèn)題[96，13，97]，不可壓縮流體仿真模擬[80，17，1，78，99]，甚至更為復(fù)雜的粘彈性流體仿真[77，78，62，41]等等。對(duì)于Semi—Lagrangian算法在L∞([0，T]；L2(Ω))范數(shù)意義下的先驗(yàn)誤差估計(jì)，數(shù)學(xué)家們首先得到形式如下的

4、最優(yōu)收斂階的結(jié)果[36，89，35](空間使用線性有限元離散)：
　　 ‖u(tn)—Unh‖L2(Rd)≤c(k+h2)，但是這里常數(shù)c和ε成反比。當(dāng)ε→0時(shí)，這個(gè)誤差估計(jì)就沒(méi)有意義了。因此，數(shù)學(xué)家們又給出了ε一致的誤差估計(jì)[11]：
　　 ‖u(tn)—Unk‖L2(Ω)≤c(k+min{h，h2/k})．但是上述誤差估計(jì)的證明比較冗長(zhǎng)，而且對(duì)解的正則性有額外的要求。因此，我們?cè)诘诙陆o出了一個(gè)簡(jiǎn)化的證明，得到了類似

5、的結(jié)果，并且對(duì)解的正則性并沒(méi)有額外的要求。這個(gè)ε一致但是收斂階次優(yōu)的先驗(yàn)誤差結(jié)果和數(shù)值實(shí)驗(yàn)的結(jié)果更為符合。
　　 在應(yīng)用中，研究人員也發(fā)現(xiàn)了Semi—Lagrangian算法的缺點(diǎn)[22，6，10，5]。這限制了Semi—Lagrangian算法的推廣和使用。由于有數(shù)值積分和插值的引入，算法會(huì)產(chǎn)生數(shù)值耗散，且在某些情況下，會(huì)變得不穩(wěn)定。而均勻網(wǎng)格的使用，并不適合對(duì)流占優(yōu)問(wèn)題的解往往具有激波，運(yùn)動(dòng)界面的特點(diǎn)。研究人員為了解決這些問(wèn)

6、題，設(shè)計(jì)了人工粘性法，高精度格式，移動(dòng)有限元，Streamline算法等方法。而自適應(yīng)算法也被數(shù)學(xué)家們很自然的引入到了Semi—Lagrangian算法中[33，26，49，24，25]。由于自適應(yīng)算法根據(jù)當(dāng)前數(shù)值解提供誤差信息，自適應(yīng)地改進(jìn)網(wǎng)格，所以顯示了其一定的有效性。但是，這些自適應(yīng)算法并沒(méi)有注意對(duì)流占優(yōu)問(wèn)題的特點(diǎn)，所使用的時(shí)間誤差指示子仍然直接借鑒了拋物型方程的結(jié)果，從而影響了自適應(yīng)算法的效率。我們注意到引入隨體導(dǎo)數(shù)后，對(duì)流擴(kuò)散

7、問(wèn)題沿著特征線滿足能量等式。根據(jù)這點(diǎn)，我們?cè)诘谌轮薪o出了一個(gè)新型的時(shí)間誤差指示子，以及其后驗(yàn)誤差估計(jì)。然后將其和傳統(tǒng)的殘量型空間誤差指示子結(jié)合，給出了完全離散格式的后驗(yàn)誤差估計(jì)和自適應(yīng)算法。另外，基于這個(gè)新型的時(shí)間誤差指示子，我們給出了一個(gè)在收斂階和正則性要求上都是最優(yōu)的時(shí)間的先驗(yàn)誤差估計(jì)，克服了傳統(tǒng)的分析技巧在時(shí)間上對(duì)正則性要求較高的不足。
　　 Semi—Lagrangian算法的另一個(gè)比較大的憂慮是計(jì)算量的問(wèn)題。由于和傳

8、統(tǒng)方法相比，Semi—Lagrangian算法在每一時(shí)間步要多進(jìn)行一次特征線的回溯和定位，會(huì)導(dǎo)致計(jì)算量的增加。另外，由于時(shí)間這個(gè)串行的物理量存在，也使得在數(shù)值計(jì)算時(shí)，花在時(shí)間步進(jìn)上的時(shí)間相當(dāng)可觀。對(duì)一些較為復(fù)雜的物理現(xiàn)象，甚至?xí)霈F(xiàn)在時(shí)間上根本算不動(dòng)的情況。因此，我們引入了時(shí)間并行算法——Parareal算法。該算法由Lions，Maday和Turinici[65]于2001首先提出。并在許多時(shí)間相關(guān)問(wèn)題上有了應(yīng)用[9，7，67，44，

9、31]。該算法是一種基于兩層時(shí)間網(wǎng)格的迭代算法，每一次迭代在時(shí)間粗網(wǎng)格上進(jìn)行預(yù)估，再在時(shí)間細(xì)網(wǎng)格上進(jìn)行并行的校正。從而達(dá)到時(shí)間并行的效果。在第四章中，我們從線性方程組迭代算法的角度，重新分析了Parareal算法，給出了新的收斂性估計(jì)。由于Semi—Lagrangian算法每一步求解的是一個(gè)拋物型方程，所以Parareal．算法可以較為直接的應(yīng)用到Semi—Lagrangian算法上來(lái)。但是考慮到對(duì)流占優(yōu)問(wèn)題解的特點(diǎn)，我們?cè)赑arare

10、al算法中引入了時(shí)間自適應(yīng)，針對(duì)兩層網(wǎng)格在算法中的不同作用，分別設(shè)計(jì)了具有針對(duì)性的自適應(yīng)算法。自適應(yīng)Parareal算法充分考慮了各個(gè)中央處理器上的負(fù)載平衡，優(yōu)化了并行的效果。而自適應(yīng)的引入，也使Parareal算法更適合實(shí)際問(wèn)題的求解，推廣了其應(yīng)用范圍。
　　 我們將Semi—Lagrangian算法應(yīng)用于非牛頓流體的數(shù)值模擬。非牛頓流體的數(shù)值模擬的困難是如何保持協(xié)調(diào)張量τA的正定性和Weissenberg數(shù)比較大時(shí)(Wi＞0

11、.7)算法的收斂性。協(xié)調(diào)張量的正定性是非牛頓流體模型穩(wěn)定的重要條件，如果一個(gè)數(shù)值算法不能保持這一性質(zhì)，就會(huì)導(dǎo)致數(shù)值算法不收斂，特別是Weissenberg數(shù)比較大時(shí)。而Semi—lagrangian算法可以比較自然的保持正定性[63，62]。第五章中，我們?cè)敿?xì)介紹了算法流程以及在進(jìn)行數(shù)值實(shí)驗(yàn)時(shí)的一些細(xì)節(jié)問(wèn)題。數(shù)值結(jié)果說(shuō)明了我們的算法的有效性，在Weissenberg數(shù)小于0.7時(shí)，我們得到了符合公認(rèn)值的結(jié)果。而在Weissenberg數(shù)