改進的Semi-Lagrangian算法及其應用.pdf

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

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

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

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

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

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

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

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

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

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

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