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

劉 揚(yáng) 高 飛

（武漢理工大學(xué)理學(xué)院 武漢 430070）

0 引 言

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

1 局部消元法

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

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

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

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

到這里，停止消元過程.式（4）所對(duì)應(yīng)的幾何Stencil如圖1所示，它示出一個(gè)十三點(diǎn)差分格式，其局部截?cái)嗾`差與五點(diǎn)中心差分格式一樣為O（h2）.

圖1 13點(diǎn)差分格式的Stencil

2 混合多項(xiàng)式加速算法

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

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

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

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

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

上式右端項(xiàng)當(dāng)N→∞時(shí)趨于零，故算法收斂性得證.

將式（7）寫成矩陣形式

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

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

步驟3 計(jì)算

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

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

3 數(shù)值實(shí)驗(yàn)

為了驗(yàn)證新迭代算法的有效性，考慮一個(gè)模型方程如下

式（10）的解為

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

表1 迭代時(shí)間比較 s

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

4 結(jié) 論

本文利用局部消元法構(gòu)造了求解一類橢圓型方程的十三點(diǎn)差分格式，并結(jié)合五點(diǎn)差分格式建立了一個(gè)Jacobi型迭代算法.然后根據(jù)Chebyshev多項(xiàng)式加速方法構(gòu)造了一個(gè)混合半迭代算法.新算法在第一層上仍然使用經(jīng)典的Jacobi迭代，而在內(nèi)層上使用多項(xiàng)式加速方法.數(shù)值實(shí)驗(yàn)表明，新算法比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.