Poissonequation perturbation and Jacobi preconditioning for solving Comparison of eigenvalue ratios in artificial boundary Journal of Computational Physics

Contents lists available atScienceDirect

Journal of Computational Physics

www.elsevier.com/locate/jcp

Comparison of eigenvalue ratios in artificial boundary perturbation and Jacobi preconditioning for solving Poisson equation

Gangjoon Yoon

^a

, Chohong Min

^b,∗

aNationalInstituteforMathematicalSciences,Daejeon34047,RepublicofKorea bDepartmentofMathematics,EwhaWoman’sUniversity,Seoul03760,RepublicofKorea

a r t i c l e i n f o a b s t r a c t

Articlehistory:

Received8December2016

Receivedinrevisedform2August2017 Accepted5August2017

Availableonline10August2017

Keywords:

Shortley–Weller

Artificialboundaryperturbation Jacobipreconditioner Conditionnumber Poissonequation Finitedifferencemethod

TheShortley–WellermethodisastandardfinitedifferencemethodforsolvingthePoisson equationwithDirichletboundarycondition.Unlessthedomainisrectangular,themethod meets an inevitable problem that some of the neighboring nodes may be outsidethe domain. Inthiscase,anusual treatmentis toextrapolatethefunctionvaluesatoutside nodesbyquadraticpolynomial.Theextrapolationmaybecomeunstableinthesensethat someof theextrapolation coefficients increase rapidlywhen thegrid nodes are getting closer to the boundary. A practical remedy, whichwe call artificial perturbation,is to treat gridnodes verynear the boundary as boundarypoints. The aimof thispaper is torevealtheadverseeffectsoftheartificialperturbationonsolvingthelinearsystemand theconvergenceofthesolution.Weshowthatthematrixisnearlysymmetricsothatthe ratioofitsminimumandmaximumeigenvaluesisanimportantfactorinsolvingthelinear system.Ouranalysisshowsthattheartificialperturbationresultsinasmallenhancement oftheeigenvalueratiofromO(1/(h·^hmin)toO(h⁻³)and triggersanoscillatoryorderof convergence. Instead,we suggestusing JacobiorILU-typepreconditioneron thematrix withoutapplyingtheartificialperturbation.Accordingtoouranalysis,thepreconditioning not onlyreduces theeigenvalueratio from O(1/(h·^hmin)to O(h⁻²),butalsokeepsthe sharpsecondorderconvergence.

©^{2017ElsevierInc.Allrightsreserved.}

1. Introduction

Inthisarticle,weconsiderthestandardfinitedifferencemethodforsolvingthePoissonequation

−

^u

=

^{f inadomain}



⊂ R

^{nwithDirichletboundaryconditionu}

=

^{g on}∂.Lettheuniformgridofstepsizeh isdenotedby(h

Z)

^{n.Thediscrete} domainisthendefinedasthesetofgridnodesinsidethedomain,i.e.^h

:=  ∩ (

^h

Z)

^n.

Thestandard finitedifference methodisadimension-by-dimension applicationofthecentralfinite difference,andwe present mainly the caseof one dimension andreport anynominal differences inthe other dimensions, when required.

Unlessisrectangular,themethodmeetsaninevitableproblemthatsomeoftheneighboringnodesmaybeoutside.As

*

Correspondingauthor.

E-mailaddress:chohong@ewha.ac.kr(C. Min).

http://dx.doi.org/10.1016/j.jcp.2017.08.013 0021-9991/©^{2017ElsevierInc.Allrightsreserved.}

Fig. 1. u^h_i,j hasfourneighboringnodes.Theoneintherightisoutside,andtheghostvalueu^G_i+1,jisquadraticallyextrapolatedfrominsidevaluesu^h_i,j andu^h_i−1,jandtheboundaryvaluegI.

depictedinFig. 1,a neighboringnodeofthegridnodeisoutside.Thenodeoutside^hiscalledghostnode[10],andthe functionvalueattheghostnodeisextrapolatedbythequadraticpolynomialasfollows.

u_i^G_+1,j

:=

^uh_i−1,j¹

− θ

1

+ θ −

^2uh_i,j¹

− θ θ +

^gI

2

(

1

+ θ) θ .

Hereθ

·

^{h isthedistancebetweenthegridnodeandtheboundarytotheright.}

Applyingtheextrapolationtothesecond-ordercentraldifferencescheme,weobtainasecond-orderdiscretizationinthe x-direction

− (

^Dxxu

)

_{i j}

= −

^ui−1,j

−

^2ui,j

+

^uG_i+1,j

h²

=

²

θ

h

·

^hui,j

−

²

h

· (θ +

¹

)

hu_i−1,j

−

²

θ

h

· (θ +

¹

)

hg_I

.

⁽¹⁾

ThisdiscretizationiscalledtheShortleyandWellermethod[19]andthecorrespondingdiscreteLaplacianoperatorisgiven inequation (3)insection3.OnapplyinganiterativemethodtosolvethediscretePoissonequationwhichisrelatedtoan nonsymmetric matrix,itis notedin [17]that iftherelatedmatrixis nearlysymmetric,the residualnormisbounded by theratioofthemaximumandminimumeigenvaluesinabsolutevalue.Weshow inthisworkthatthematrixinducedby the Shortley–Weller methodis nearlysymmetric inthe sense thatthe dominantmajorityofthe entriesin A

= (

^ai,j) are symmetricabouttheir diagonals[23] andai j

=

^{0 iffa}ji

=

^{0 ([18]andreferencestherein).Inthisrespect,weestimate the} convergenceperformancebytheeigenvalueratioratherthantheratioofsingularvalues.

From the discretization (1),we see that theextrapolation mayproduce large errorifθ in the denominator gets very small.ThisresultsinalargeconditionnumberforthematrixassociatedwiththeShortley–Wellermethodasanestimation

|λ

max/λmin

| =

^O(1/ (h

·

^hmin)) shown in Theorem 3.1. Here hmin is the minimum distance from the nodes in  to the boundary ∂. To mitigate the singularity of the extrapolation, there are two treatments in practice: artificial boundary perturbationandpreconditioning.

The artificial boundary perturbationis to treat thegrid nodes nearthe boundary within a certain thresholdθ0

·

^{h as} boundarypointsandwetakeu^h_i,j

=

^gI [7,10,16].Thecommonchoiceofthethresholdisθ0

=

^{h.Wecallthepracticeasthe} artificialboundaryperturbationthroughoutthispaper.

This article isaimed atrevealing theprecise effects from the artificialperturbation. We review the known facts and estimate theratioofeigenvaluesfortheunperturbedlinearsysteminsection2.Insection4,wediscusstheeffectsonthe convergenceofthenumericalsolutionandtheeigenvalueratioofthelinearsystemfortheartificialperturbation.Inpractice, we take θ0

=

^{h forthe} perturbation value andwe reveal inTheorem 4.2 that the eigenvalueratio to thecorresponding treatment is shown to be O(h⁻³) so that the artificial perturbation is lesseffective than any preconditioning. Another treatment to mitigatethe dependence on the minimumgrid size and condition numbers as well is preconditioning the linearsystem.WeestimatetheeffectoftheJacobipreconditioninginsection5andwetesttheusualotherpreconditioners suchassymmetricGauss–Seidel(SGS),incompleteLU(ILU)andmodifiedILU(MILU)toseetheeffectofthepreconditioning.

We showthat theJacobipreconditioningisenough tocompletelyresolve theissueofthesingularityoftheextrapolation when θ is small, by proving that theJacobi preconditioner istotally free fromthe effect ofthe minimumdistance h_min andits conditionnumberisnolargerthan O(h⁻²).Consequently,we suggestthepreconditioningmethodratherthat the artificialboundaryperturbationinordertoimprovetheperformanceoftheiterativesolver.

Itisworthnotingthatitwasobservedformanysecondorder,self-adjoint,ellipticequationsthatthespectralcondition numbersofthediscreteoperatorgrowasO(h⁻²)asthemeshsizeh tendstozero(see[6]fordetails).Also,Dupont,Kendall andRachford[9]observedthateventhoughtheconvergenceratesoftheJacobi,SGS,andILUpreconditionedmatricesstill

behaveasO(h⁻²)withamuchsmallermultiplicativeconstant,theMILUpreconditionedmatrixdropstheorderto O(h⁻¹). TheMILUimprovement O(h⁻¹)fortherectangulardomainwas provedin[3,4,14,21]andwe alsoreferthereaderto[1,2, 5,12,15]forrelatedworksontheMILUpreconditioning.However,theMILUimprovementofO(h⁻¹)forgeneraldomainsis notprovedyetandweleavethestudyforafurtherwork.

2. ReviewofShortley–Wellermethod

Inthiswork, we focusboth onthe convergenceperformance ofthestandard finitedifference methodforthe Poisson equationandontheeffectofthetwomethodsimprovingtheperformance:artificialboundaryperturbationandprecondi- tioning. Inthisrespect,itissufficient tocomparethe performancesforthetwo dimensionalcase.Letusintroduce some discretizationsettingsofdomainforsolvingthePoissonproblem

 −

u

=

f in



u

=

g on

∂,

⁽²⁾

where

⊂ R

^{2 isan openandboundeddomainwithsmoothboundary} ∂.Consider auniformgridwithstepsize h,i.e.

h

Z

^2.By^h wedenotethesetofgrid nodesbelongingto ,and∂^h denotestheset ofintersectionpoints between∂

andgridlines,i.e.^h

=  ∩ 

h

Z

²



and∂^h

= ∂ ∩ {(

^h

Z × R) ∪ (R ×

^h

Z)}

^{.A gridnode} (x_i,y_i)

∈ 

^{h hasfour}neighboring nodesin^h

∪∂

^h,namely



x_i±1,y_j



and



x_i,y_j±1



in^h

∪∂

^h.Leth_i+¹

2,jdenotethedistancefrom



x_i,y_j



toitsneighbor



x_i+1,y_j



,andotherdistancesh_i−1 2,j,h_i,j±1

2 aredefinedinthesamefashion,seeFig. 1.

Byapplyingthe quadraticpolynomial extrapolationfortheghost values,its discrete Laplacian_hu^h

: 

^h

→ R

^foruh

:

^h

∪ ∂

^h

→ R

^readsas





_hu^h



i j

=



u^h_i+1,j

−

^uh_{i j} h_i+1

2,j

−

^u

h

i j

−

^uh_i−1,j h_i−1

2,j



2

h_i+1

2,j

+

^h_i−¹

2,j

+



u^h_i,j+1

−

^uh_{i j} h_i,j+1

2

−

^u

h

i j

−

^uh_i,j−1 h_i,j−1

2



2

h_i,j+1

2

+

^h_i,j−¹

2

.

(3)

Notethatwhenh_i+1

2,j<h,wesetxi+¹

=

^xi

+

^h_i+¹

2,jsothat(xi+¹,yj)

∈ ∂

^{h anduh}_i+1,j

=

^g(xi+¹,yj)inequation(3).

Throughoutthework, wedenote byu the solutiontothe Poissonequation(2) andby u^h thesolution ofthediscrete equation

 −

hu^h



x_i

,

y_j



=

^f



x_i

,

y_j



, 

x_i

,

y_j



∈ 

^h u^h



x_i

,

y_j



=

^g



x_i

,

y_j



, 

x_i

,

y_j



∈ ∂

^h

.

⁽⁴⁾

Now,weintroducesomelemmasonthediscretizationinageneralsetting.Fortheproofswereferto[22].

Lemma2.1(Monotoneproperty).Foranyv^h,w^h

: 

^h

∪ ∂

^h

→ R

^with

−

^hvh

≥ −

^{hwh in}^handv^h

≥

^whon∂^h,wehave v^h

≥

^whin^h

∪ ∂

^h.

Letusdefinethefunctionsp^h

: 

^h

∪ ∂

^h

→ R

^{asthesolutionof}

−

^hph

=

^{1 in}



^h

withboundarycondition p^h

=

^{0 on}∂^h.Thenwehavethefollowingestimationforp^h [22].

Lemma2.2.Letp(x)betheanalyticsolutionof

−

^p

=

^{1 in}withp

=

^{0 on}∂.LetCp

=

^Cp()betheconstantgivenby C_p

:=

^max

 ∂

p

∂

x_i

(

x

) ,

∂

³p

∂

x³_i

(

x

) ,

∂

⁴p

∂

x⁴_i

(

x

)

:

^x

∈  ∩ ∂,

ⁱ

=

¹

,

2

.

Ifh

≤

^min



1,_8C³_p



,thenforeach



x_i,y_j



∈ 

^h,wehave 0

≤

p^h_{i j}

≤

2Cp

·

dist



xi

,

yj

 , ∂

^h

 .

Therefore,thereisaconstantC>0 suchthatwehave



2

h_i+1 2,j

·

^h_i−¹

2,j

+

²

h_i,j+1 2

·

^h_i,j−¹

2



p^h_{i j}

≤

^{C 1} h² forall



x_i,y_j



∈ 

^h

3. Nearlysymmetricmatrix

Forasymmetriclinearsystem,ConjugateGradientmethodistheoptimalsolverintheKrylovspaceassociatedwiththe linear system. Its convergence speed isdetermined by the condition number. Thus preconditioningthe symmetric linear systemisfocusedonreducingtheconditionnumber.

For a nonsymmetriclinear system, GeneralMinimal RESidual(GMRES) methodis the optimalsolver tominimize the residualintheKrylovspace. Unlikethesymmetriccase,theconvergencespeedisnotalwaysdeterminedby thecondition number, theratioofthemaximumandminimumsingular values.Theconvergenceis guaranteedforgeneralnonsingular matrices,butthemeasureofconvergencespeeddependsoneachtypeofthematrix.Thetypesandcorrespondingestimates arelistedbelow.

For normal matrix

, 

rk

 ≤

minp∈πk



maxλ∈σ(A)

|

p

(λ)| 

.

For diagonalizable matrix

, 

^rk

 ≤

^minp∈πk



max_λ∈σ(A)

|

^p

(λ) | 

· κ (

X

) .

In general

, 

^rk

 =

^minp∈πk



^p

(

A

)

r₀

 .

Now letusconsiderthematrixA associatedwiththeShortley–Wellermethod,andcheckthetypetowhichitbelongs.

Fig. 2showsthatall ofitseigenvaluesarelocatednearthepositiverealaxisinthecomplexplane.Insidethedomain,the Shortley–Wellermethodequalstothestandardmethodwhoseassociatedmatrixissymmetric.Withsmallerstepsizeh,the numberofgridnodesinsidethedomaindominatesthenumberofgridnodesadjacenttoboundary.Fromthisreason,the matrixA canbethoughasasmallperturbationofitssymmetricpartbyitsnonsymmetricpart.

A

=

^A

+

^AT

2

+

^A

−

^AT 2

.

Fig. 3 confirms the dominance of thesymmetric part over the nonsymmetric part. In particular, thematrix A

= (

^ai j) is nearly-symmetricinthesensethatai j

=

^{0 iffa}ji

=

^{0 ([18]andreferencestherein)andthedominantmajorityoftheentries} inA aresymmetricabouttheirdiagonals[23].Sincethesymmetricparthasonlyrealeigenvaluesandisdiagonalizable,the perturbation argumentexplainstheobservedrealeigenvaluesofA andindicates thatthematrix A maybestill diagonal- izable. Thereforeitisreasonabletoapply theconvergenceestimatefordiagonalizablematricestoA.Accordingto[17],the estimatecanbesimplifiedwhentheeigenvaluesarelocatedonthelinesegment[λmin, λmax] onthepositiverealaxisas



^rk

 

^r0

 ≤ κ (

X

)

1

− λ

min

/λ

max

1

+ λ

min

/λ

_max



k

.

(5)

Here X isatransformationmatrixtomake X⁻¹A X diagonal,and

κ

(X)isits conditionnumber.When A isdiagonalizable, all ofitsILU-typepreconditionedmatricesarediagonalizable. Thuswe aimtoreducethe eigenvalueratio.Fig. 4 provides empiricalevidencesthatGMRESconvergesfasterwithsmallereigenvalueratiothatvalidatestheaboveestimate.

Now,letusestimatetheeigenvaluesofthematrixassociatedwiththediscretization,whichisdenotedbyA

Theorem3.1.LetλbeaneigenvalueofthematrixA associatedwiththediscretization,0<CA

≤ |λ| ≤

_h·h⁸_min ^{forsomeconstant} CA

=

^CA(),thatisindependentofgridsizeh.

Proof. Forsufficientlysmallh,wemayassumethatwhenever



x_i,y_j



∈ 

^{handoneofitsneighbors,letussay}



x_i−1,y_j



,is on∂,thenitsneighborintheoppositesidebelongstoinside,i.e.



x_i+1,y_j



∈ 

^h.Letλbeaneigenvalueofthematrix A associated withthediscretizationand v itscorresponding eigenvector,thatis,Av

= λ

^v.The Gerschgorincircletheorem impliesthat 0<

|λ| ≤

_h·h⁸_min^{.Since A is anM-matrix,the} Perron–FrobeniusTheorem [13]applying toA⁻¹ showsthat the minimumeigenvalueλm isapositiverealnumberandthereexistsaneigenvectorv

= (

^vP)_P∈h withvP>0 forall P

∈ 

^h corresponding to λm.We mayassume that v isdefinedon ^h

∪ ∂

^{h by a trivialextension.Let v}P0

=

^max

{

^vP

:

^P

∈ 

^h

}

^. ThenwecanseeAv

= (−

hv)andforthefunction p^hgiveninLemma 2.2,wehave

( −

hv

) = λ

mv

≤ λ

mv_P0

( −

hp^h

).

ApplyingLemmas 2.1 and 2.2showsthatthereexistsaconstantC0independentofh suchthat

v_P

≤

^C0

λ

mv_P0

∀

^P

∈ 

^h

.

Thisshowsthatλm

≥

^CAforsomeconstantCA,whichcompletestheproof.

2

Table 1showsthattheestimationofTheorem 3.1istight:fortheunperturbedmatrixA,

|λ

min(A)|

≈

^CAforsomeconstant CA and

|λ

max(A)

| ≈

⁸/hhmin.

Fig. 2. TheeigenvaluedistributionofA arenearlyreal.Thetoprowdepicttheeigenvaluesincomplexplaneforthecase= {(x,y)|x²+y²<1}and h=80³,andthebottomrowfor= {(^x,y,z)|^x2+^y2+^z2<1}^andh=20³.Theellipsesincludingtheeigenvalueshaveeccentricity1−².79×^10−10and 1−¹.70×^10−8,respectively,whichmeanthatalltheeigenvaluesarealmostreal.

4. Effectoftheperturbation

Letu^h be thenumerical solutionwithout perturbation,and ^u

˜

^{h be the numericalsolution with}perturbation. Whileit has been well known that



u^h

−

^u



L^∞

=

^O



h²



[19,22], the convergence order of the perturbed solution has been left

Fig. 3. Theratiobetweenthenumberofnonsymmetricentriesandthenumberofsymmetricentries.TheratiodecaysasfastasO(h),whichmeansthe dominanceofthesymmetricpartovernonsymmetricpart.= {(x,y)|x²+y²<1}.

Fig. 4. ThedecreaseoftheresidualnorminGMRES.Asestimatedin(5),GMRESconvergesfasterwithsmallereigenvalueratio.= {(^x,y)|^x2+^y2<1} andh=3/80..

Table 1

EigenvaluesoftheunperturbedmatrixoftheShortley–WellermethodinExample 4.1:theresultstightlyobeytheestimateofTheorem 3.1,0<CA≤ |λ| ≤

8 h·hmin.

grid Original (unperturbed) matrix

|λ^max| ^{ratio h}min ratio _hh⁸

min rate |λmin| ^ratio

20² 4.00×10² 5.03×10⁻² 5.30×10² 5.74

40² 2.17×10⁴ 54.3 1.53×10⁻³ 0.0304 3.49×10⁴ 65.8 5.77

80² 1.09×^{105 5.02 7}.03×^{10−4 0.459 1}.52×^{105 4.35 5.78 1.00}

160² 1.59×^{106 14.5 9}.15×^{10−5 0.130 2}.33×^{106 15.4 5.78 1.00}

320² 2.30×^{107 14.4 1}.31×^{10−5 0.143 3}.26×^{107 14.0 5.78 1.00}

unclear. Inthissection,we investigatetheconvergenceorderof

˜

u^h

−

^u



L^∞.Let∂ ˜^h bethegridnodesthatweretreated asboundarypointsbytheperturbation.Thenthedifference^u

˜

^h

−

^{uh satisfythediscreteharmonicequation,}

−

^h



˜

u^h

−

^uh



=

^{0 in}



^h

− ∂ ˜

^h

.

On ∂ ˜^h, the perturbed value ^u

˜

^h_i ^{is assigned by g}(xI)

=

^u(xI). It is known that the unperturbed numerical solution is third order accurate near the boundary [22], so that u^h_i

=

^u(x_i)

+

^O



h³



. Applying the mean-value theorem, we have

˜

u^h_i

−

^uh_i

=

^u(xI)

−

^u(xi)

−

^O



h³



=

^∂_∂^u_x(ξ ) θ0h

+

^O



h³



, for some ξ between xi and xI. Thus the boundary value of the discreteharmonicsolutionu

˜

^h

−

^{uh isgivenas}

˜

u^h

−

^uh

=



0 on

∂

^h

\ {

x

∈ ∂

^h

:

dist

(

x

, 

^h

) ≤ θ

h

}

∂u

∂x

(ξ ) θ

0h

+

^O



h³



on

∂ ˜

^h

.

Fig. 5. TheerrorplotofthenumericalsolutionsinExample 4.1.Theperturbationoccurssometimes(marked×)andsometimesnot(marked◦).Thelower bound(Ch²)andupperbound(C·h²+ ∇uL^∞(∂)h²)aredrawnaslines.

Thediscretemaximumprinciple[22]statesthatthediscreteharmonicsolutionshouldhaveitsmaximumorminimumon theboundary,thereforewehave

 ˜

^uh

−

^uh

 

L^∞

^h

≤ ∇

^u



L^∞(∂)

θ

0h

+

^O



h³



,

foran



-neighborhood∂ _of ∂andsufficientlysmallh withθ0h

≤ 

.Itiswell knownthattheunperturbednumerical solutionshowsaverycleansecond orderconvergencerate[8,22],



_u^h

−

^u



L^∞

^h



^C

·

^{h2.Using theabove inequalityand} thetriangleinequality,weobtaintheestimate:

 ˜

^uh

−

^u

 

L^∞

^h

≤

^C

·

^h2

+ ∇

^u



L^∞(∂)

θ

0h

+

^O



h³

 .

When θ0

=

^{h, note that the perturbed solution is still second order accurate, however, Fig. 5 shows that while the} unperturbedsolutionhasthecleansecond orderaccuracyash isvaried,thatoftheperturbedonewouldfluctuatearound thesecondorder.

Letusnowturn ourattentionto thestatistics thatshow how oftentheperturbation occurs. Theedge length ofeach gridcellish andtheboundary∂isacurveoffinitelength.Thereforethenumberofgridcellsintersectingtheboundary canbesaidtobeaboutO



h⁻¹



.Similarly,thenumberofgridedgesintersectingtheboundaryis O



h⁻¹



.Wemayassume that O



h⁻¹



numberofintersectionpointsarerandomlydistributedongridedgesoflengthh.Theintersectionpointsthat are within distance θ0h

=

^{h2 from the endsare classified as‘toonear’ points onwhich the} perturbation isapplied. The edgelengthh isdividedintoh⁻¹ numberofsubintervalsoflengthh².Whenthe O



h⁻¹



numberofintersectionpointsare randomlydistributedontheedgelengthh,thenumberofpointslyingontheendsubintervalsistherefore O(1).

Similarly as above, we deduct that if θ0 were taken larger as a constant such as .001, the number of perturbation pointswouldincreaseunboundedlyasO



h⁻¹



andifθ0takensmallerash²,theperturbationpointswouldnotappearfor sufficientlysmall h.

Example4.1.ConsiderthePoissonproblem

−

^u

=

^{0 in}

= 

(x,y)

|

^x2

+

^y2<1



withu

=

^y/



(x

+

²)²

+

^y2



.Theartificial boundaryperturbationwascarriedoutwithθ0

=

^{h.Fig. 5showstheerrorsofthe}unperturbedandperturbedsolutions.

Ourargumentin thissection indicates that thechoice θ0

=

^{h ismarginal sothat} perturbation points maysometimes appear andsometimes not. When perturbation points do appear, theconvergence order



u^h

−

^u



_L∞

^h would fluctuate betweenC

·

^{h2 andC}

·

^h2

+ ∇

^u



L^∞(∂)h²,whicharewellobservedinFig. 5.

Wehavediscussedhowmuchtheperturbationaffectstheconvergenceorderandhowoftenitoccurs.Thelinearsystem associatedwiththePoissonsolverhasanotoriouslylargecondition number



_hh⁸_min^{.Thethirdissueofourdiscussionisto} showthattheperturbationslightlydecreasestheconditionnumberasbelow.

Fig. 6. Theeigenvalueratiooftheperturbed(marked×^)andunperturbed(marked◦^{)linearsystemsin}Example 4.1.Theperturbedratioissmallerthan theunperturbedratioasexpectedinTheorem 4.2.Theratiosofbothdataarebetweenthesecondorder(dottedline)andthethirdorder(solidline).

Theorem4.2.LetλbeaneigenvalueofthematrixofthePoissonsolverwiththeperturbation,thenwehave

0

< ˜

C

≤ |λ| ≤

⁸

θ

0h²

≤

⁸ h

·

hmin forsomeconstantC

˜ = ˜

^C().

Proof. ThematrixobtainedinthisperturbationsettingisalsoanM-matrix.Inthiscase,wehavehmin

≥ θ

0

·

^{h andapplying} thesameargumentusedfortheproofofTheorem 3.1givestheaboveresult.

2

The above theoremshows that the eigenvalue ratioof the perturbed matrix is smallerthan that ofthe unperturbed matrix. Since θ0

=

^{h, the estimate indicates that the two eigenvalue ratios are bounded above by} _h⁸3/ ˜C

=

^O



h⁻³



and 8

hh_min/ ˜C

≥

^O



h⁻³



,respectively.Fig. 6verifies thetheorem:theperturbed ratioissmallerthantheunperturbedratioand theratiosofbothdataarebetweenthesecond orderandthethirdorder.Inthefollowingsection,however,weshowthat theJacobipreconditioningdropsdowntherationolargerthan O



h⁻²



.

5. EffectoftheJacobipreconditioning

For a linear system Ax

=

^{b, the Jacobi} preconditioner is the diagonal matrix D whose diagonal entries are the same asA.The JacobipreconditioningonthelinearsystemresultsinD⁻¹Ax

=

^D−1b.Thepreconditioningis,inother words,to scaleeachequation sothat itsdiagonalentrybecomesone.ApplyingtheJacobipreconditioningonitslinearequation,the standardfinitedifferencemethodnowreads

ui j

− 

^{hi−12jhi j−12hi j+12} h_i−1

2j

+

^h_i+¹

2j

 

h_i−1

2jh_i+1

2j

+

^h_{i j−}¹

2h_{i j+}1 2



ui+¹,j

− 

^{hi+12jhi j−12hi j+12} h_i−1

2j

+

h_i+1 2j

 

h_i−1

2jh_i+1

2j

+

h_{i j−}1 2h_{i j+}1

2



ui−¹,j

− 

^{hi j−12hi−12jhi+12j} h_{i j−}1

2

+

^h_{i j+}¹

2

 

h_i−1

2jh_i+1

2j

+

^h_{i j−}¹

2h_{i j+}1 2



^ui,j+¹

− 

^{hi j+12hi−12jhi+12j} h_{i j−}1

2

+

^h_{i j+}¹

2

 

h_i−1

2jh_i+1

2j

+

^h_{i j−}¹

2h_{i j+}1 2



u_i,j−1

=

^{fi j} 2

h_i−1 2jh_{i j+}1

2h_{i j−}1 2h_{i j+}1

2

h_i−1 2jh_i+1

2j

+

^h_{i j−}¹

2h_{i j+}1 2

.

Table 2

EigenvaluesofthepreconditionedmatricesinExample 4.1:theresultsofJacobitightlyobeystheestimateO h⁻²

<|λ|<O(1)ofTheorem 5.1,andthe otherresultsareatleastasgoodas|λmax/λmin|=O

h⁻² .

grid Jacobi preconditioned SGS preconditioned

|λmax| ^ratio |λmin| ^ratio |λmax| ^ratio |λmin| ^ratio

20² 1.96 3.56×^{10−2 1.00 1}.29×¹⁰⁻¹

40² 1.99 0.98 8.53×10⁻³ 0.24 1.00 0.98 3.33×10⁻² 0.26

80² 1.99 1.00 2.08×10⁻³ 0.24 0.999 1.00 8.28×10⁻³ 0.25

160² 1.99 1.00 5.14×^{10−4 0.25 0.999 1.00 2}.05×^{10−3 0.25}

320² 1.99 1.00 1.27×^{10−4 0.25 0.999 1.00 5}.11×^{10−4 0.25}

grid ILU preconditioned MILU preconditioned

|λmax| ratio |λmin| ratio |λmax| ratio |λmin| ratio

20² 1.18 2.08×^{10−1 3.28 0.999}

40² 1.20 0.98 5.60×^{10−2 0.26 6.64 2.02 1.00 1.00}

80² 1.20 1.00 1.40×^{10−2 0.25 13.4 2.02 1.00 1.00}

160² 1.20 1.00 3.50×10⁻³ 0.25 27.2 2.03 0.999 1.00

320² 1.20 1.00 8.72×10⁻⁴ 0.25 55.0 2.02 0.999 1.00

Inbrief,theJacobipreconditionerD⁻¹A actsonu as



D⁻¹Au



i j

=

^ui j

− α

_{i j}u_i−1,j

− β

i ju_i+1,j

− γ

_{i j}u_i,j1

− δ

i ju_i,j+1

withnonnegativeconstants

α

i j,βi j,

γ

i j,δi j satisfying0<

α

i j

+ β

i j

+ γ

i j

+ δ

i j

≤

^{1.ThismeansthattheJacobi}preconditioner eliminatescompletelytheadverseeffectofh_min.AlsoweshowinthefollowingthattheJacobipreconditioningreducesthe ratiomagnitudeto O



h⁻²



.

Theorem5.1.ForanyeigenvalueλoftheJacobi-preconditionedmatrixD⁻¹A,wehave0<C_J

·

^h2

≤ |λ| ≤

^{2 forsomeconstant} CJ

=

^CJ().

Proof. LetλbeaneigenvalueoftheJacobi-preconditionedmatrixD⁻¹A and v itscorrespondingeigenvector,thatis,Av

=

λDv. Sinceallthediagonalentries ofD arepositiveandA isan M-matrix,the Jacobi-preconditionedmatrixD⁻¹A is also an M-matrix. The Gerschgorincircletheorem for D⁻¹A shows

|λ| ≤

^{2, andit remains to show that}

|λ| ≥

^CJh² forsome constant C_J independent ofh. Wemayassume that λ

= λ

min is aminimum eigenvalue.Since D⁻¹A isan M-matrix,the Perron–FrobeniusTheoremappliedtoA⁻¹D showsthatthereexistsaneigenvectorv

= (

^vP)_P∈h withvP>0 forallP

∈ 

^h correspondingtoλ.Wemayassumethat v isdefinedon^h

∪ ∂

^{h byatrivialextensionassettingvaluesofv equalto0.}

LetaP0P0vP0

=

^max

{(

^Dv)P

:

^P

∈ 

^h

}

^{.ThenwecanseeAv}

= (−

hv)andforthefunction p^h giveninLemma 2.2,wehave

( −

hv

) = λ

minDv

≤ λ

minaP₀P₀vP₀

( −

hp^h

).

ApplyingCorollary 2.1andLemma 2.2givethatthereexistsaconstantC independentofh suchthat

v_P0

≤ λ

mina_P0P0v_P0p^h

(

P₀

) ≤

^C

h²

λ

minv_P0

.

Thisshowsthatλmin

≥

^CJ

·

^{h2 whereC}J

=

¹_C^{,whichcompletestheproof.}

2

NotethattheeigenvalueestimatefortheJacobi-preconditionedmatrixisindependentofh_min,whilethatfortheoriginal matrixisdependent.ThusthepresenceofgridnodestooneartheboundaryisnotproblematicintheJacobi-preconditioned matrix.

Remark. Theorem 3.6in[20]showstheILU-typepreconditionersareactuallyappliedontopoftheapplicationoftheJacobi preconditioner.HencewecanexpectthattheireffectsareatleastasgoodasJacobi;SeeTable 2.

6. Conclusion

The matrix derived from the standard finite difference method called as the Shortley–Weller method is sparse and non-symmetric, and nearly symmetric. Hence the ratio

|λ

max/λmin

|

^{, an accurate measure of eigenvalue} distribution, is a veryimportantfactorinsolvingitsassociatedlinearsystem.Weshowedtheestimation

|λ

max/λmin

| =

^O(1/ (h

·

^hmin))that isproved andverifiedthrough numericaltests.Furthermore,the testssuggestthat theestimate isoptimal. Thereforethe