橢圓方程有限差分逼近的混合半迭代法＊

劉 揚 高 飛

（武漢理工大學理學院 武漢 430070）

0 引 言

現(xiàn)代科學技術工程中的大量數(shù)學模型都可以用微分方程來描述，求解微分方程的數(shù)值方法主要有：有限差分方法、有限元法以及有限體積法等.用有限差分法求解橢圓型方程，其差分格式的求解都歸結為一個線性代數(shù)方程組問題，原則上，數(shù)值代數(shù)中的方法都適用于求解這類代數(shù)方程組.但有限差分法所得到的差分格式的系數(shù)矩陣具有一些特殊的性質，如稀疏帶狀、主對角優(yōu)勢以及不可約性.因此針對這些特點，建立了更加有效的方法，如交替方向迭代法［1］、預處理共軛梯度法［2］以及多重網(wǎng)格法［3］等，這些方法都是迭代法.迭代法具有程序設計簡單，適合自動計算，同時還可以充分利用系數(shù)矩陣的稀疏性減少內(nèi)存存貯.因此，迭代法已經(jīng)成為求解線性方程組，尤其是求解具有大型稀疏系數(shù)矩陣的線性方程組的重要方法之一.半迭代法也稱Chebyshev多項式加速方法，是求解線性方程組的一個常用且比較有效的方法，它是迭代法的一種.與一般迭代法相比，半迭代法不僅可以提高求解線性方程組的收斂速度，而且可以使一些發(fā)散的迭代法收斂.關于半 迭 代 法，許 多 學 者 都 對 此 作 了 研 究［4－8］.Young在文獻［1］中，給出了線性方程組的迭代矩陣為對稱陣時，半迭代法的收斂性分析.本文利用局部消元法建立求解橢圓方程的十三點差分格式，將Chebyshev多項式加速方法應用于新差分格式，構造了一個混合半迭代法，用數(shù)值實驗驗證新算法的有效性.

1 局部消元法

考慮橢圓型方程第一邊值問題

式中：ui，j為式（1）的解u（x，y）在網(wǎng)格點（xi，yj）上的近似解，λ＝4＋ah2，fi，j＝f（xi，yj）.

在Ωh的每一個網(wǎng)格內(nèi)點（i，j）處都有一個聯(lián)系于式（2）的幾何Stencil.在網(wǎng)格點（i－1，j），（i＋1，j），（i，j－1），（i，j＋1）處，有另外4個差分方程

同樣的方法，消去上式中的ui－1，j－1，ui－1，j＋1，ui＋1，j－1，ui＋1，j＋1，可以得到一個更復雜的差分演化格式

到這里，停止消元過程.式（4）所對應的幾何Stencil如圖1所示，它示出一個十三點差分格式，其局部截斷誤差與五點中心差分格式一樣為O（h2）.

圖1 13點差分格式的Stencil

2 混合多項式加速算法

定義Ωh中網(wǎng)格點的集合Lp，稱為網(wǎng)格Ωh的層，p是層的標號，

式中：Mij為網(wǎng)格點（i，j）到邊界?Ω的最短歐氏距離.顯然，對于Lp（p＝2，3，...，n／2）中任意一點（i，j）都存在一個形如式（4）的差分演化形式，根據(jù)式（2）和式（4），可以構造一個Jacobi型迭代算法（JIA算法）如下.

注意到上面算法中在第一層和其他層使用不同的迭代格式.對于任意給定的初始值，Jacobi型算法式（6）和式（7）是收斂的，即當k→∞時.

利用邊界條件，計算｜ξ（k）i，j｜在每一層上可以得到的估計式，有

設內(nèi)點的總層數(shù)為r，則r＝n／2，由此得在所有的內(nèi)點上都有

上式右端項當N→∞時趨于零，故算法收斂性得證.

將式（7）寫成矩陣形式

由于JIA算法中第一層上的迭代公式與內(nèi)層不一致，因此根據(jù)Chebyshev多項式加速法構造一個混合半迭代法如下.

步驟1 輸入變量ε（誤差）的值；令k：＝1.

步驟3 計算

Else k：＝k＋1；goto步驟3.

注意到新算法中，第一層網(wǎng)格點的計算仍使用經(jīng)典的Jacobi迭代，而內(nèi)層網(wǎng)格點的計算使用多項式加速技術.之所以在第一層和內(nèi)層網(wǎng)格點上使用不同的迭代格式，主要原因有兩點：第一JIA算法中第一層和內(nèi)層使用了不同的迭代格式；第二在實際的數(shù)值計算中，外層的誤差比內(nèi)層收斂快.由于JIA算法的系數(shù)矩陣是對稱的，因此本文構造的混合迭代算法是收斂的.

3 數(shù)值實驗

為了驗證新迭代算法的有效性，考慮一個模型方程如下

式（10）的解為

取步長h＝1／100，比較Jacobi方法、JIA算法、Jacobi半迭代法、混合半迭代法在所有內(nèi)點上達到相同誤差精度所需要的時間，結果見表1.

表1 迭代時間比較 s

所有結果在IBM電腦，CPU頻率為1.6G的計算機上計算得到.數(shù)據(jù)結果表明：Chebyshev多項式加速方法能有效的加快迭代法的收斂速度，同時本文構造的混合半迭代法的收斂速度比Jacobi半迭代法約快一倍.

4 結 論

本文利用局部消元法構造了求解一類橢圓型方程的十三點差分格式，并結合五點差分格式建立了一個Jacobi型迭代算法.然后根據(jù)Chebyshev多項式加速方法構造了一個混合半迭代算法.新算法在第一層上仍然使用經(jīng)典的Jacobi迭代，而在內(nèi)層上使用多項式加速方法.數(shù)值實驗表明，新算法比Jacobi半迭代法收斂快.本文的算法和思想也可用于求解其他類型的偏微分方程.

［1］Young D M.Iterative solution of large linear system［M］.New York：Academic Press.，1971.

［2］Young D M.Iterative methods for solving partial differential equations of elliptic type［J］.Trans.Amer.Math.Soc 1954，76：92－111.

［3］Bramble J H.Multigrid methods［M］.Harlow：Longman Group UK Limited，1993.

［4］Climent J J，Neumann M，Sidi A.A semi－iterative method for real spectrum singular linear systems with an arbitrary index［J］.Comput.Appl.Math.，1997，87（1）：21－38.

［5］Eiermann M，Li X，Varga R S.On hybrid semi－iterative methods［J］.SIAM J.Numer.Anal.，1989（26）：152－168.

［6］Hadjidimos A，Stylianopoulos N S.Optimal semi－iterative methods for complex SOR with results from potential theory［J］.Numer.Math.，2006，103（4）：591－610.

［7］Rayes M O，Trevisan V，Wang P S.Factorization properties of chebyshev polynomials［J］.Comput.Math.Appl.，2005，50（8）：1 231－1 240.

［8］Belforte G，Gay P，Monegato G.Some new properties of chebyshev polynomials［J］.J.Compu.Appl.Math.，2000，117（2）：175－181.