Poisson equation Analyses on the finite difference method by Gibou et al. for Journal of Computational Physics

Contents lists available atScienceDirect

Journal of Computational Physics

www.elsevier.com/locate/jcp

Analyses on the finite difference method by Gibou et al. for Poisson equation

Gangjoon Yoon

^a

, Chohong Min

^b

^,∗

aInstituteofMathematicalSciences,EwhaWomansUniversity,Seoul,120-750,RepublicofKorea bMathematicsDepartment,EwhaWomansUniversity,Seoul,120-750,RepublicofKorea

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

Articlehistory:

Received5June2014

Receivedinrevisedform11September 2014

Accepted12September2014 Availableonline22September2014

Keywords:

Poissonequation Finitedifferencemethod Preconditioning Convergenceanalysis

Gibouetal.in[4]introducedafinitedifferencemethodforsolvingthePoissonequationin irregulardomainswiththeDirichletboundarycondition.Contrarytoitsgreatimportance, its properties have not been mathematically analyzed, but have just been numerically observed.In thisarticle, we present two analysesfor the method. One proves that its solution issecond orderaccurate, and the other estimatesthe condition number ofits linearsystem.Accordingtoourestimation,theconditionnumberoftheunpreconditioned linearsystemisofsize O(1/(h·^hmin)),andeachofJacobi,SGS, and ILUpreconditioned systemsisofsizeO(h⁻²).Furthermore,ouranalysisshowsthattheconditionnumberof MILUisofsizeO(h⁻¹),themostsuccessfulone.

©^{2014ElsevierInc.}All rights reserved.

1. Introduction

TheShortley–Weller method[13] isabasicfinitedifferencemethodforsolvingthePoissonequation withtheDirichlet boundary condition. It is a simplesum ofthe central finitedifferences inthe Cartesian directions.Thoughimplemented in uniformgrid, the methodcan handlearbitrarily shaped domains. Its solution issecond order accurate to theanalytic solution.Usuallythegradientofasecondorderaccuratesolutionisonlyfirstorderaccurate,howeverthesolutionexhibits asupra-convergencebehavior.Itsgradientisalsosecondorderaccurate[10].

Thoughitsexcellenceinefficiencyandaccuracy,theShortley–Wellermethodconstitutesanon-symmetriclinearsystem.

Only in one dimension, the linear system can be castin a symmetric form [14]. Since the Laplacian is self-adjoint, the methodthat approximatestheoperator isexpectedtobesymmetric.Gibouetal.[4]introduceda simplemodificationof theShortley–Wellermethodthatresultsinasymmetriclinearsystem.Numericaltests[10]suggestthatthesolutionisstill secondorderaccurate.

ComparedtotheShortley–Wellermethod,themethodbyGibouetal.hasanadvantagetosolvesymmetriclinearsystem.

Thegain,however,turnsouttohavenotcomefree.Thesupra-convergenceoftheShortley–Wellermethodislostwiththe gain.Thesolutiongradientisonlyfirstorderaccurate.Bothmethodshavetheirownprosandconsasdescribedabove,anda choicebetweenthemdependsonthecharacteristicofthegivenproblem.Forexample,inapplicationtoincompressiblefluid flowsthesolutiongradientisaphysicalvariableandtheShortley–Wellermethodwouldbepreferred,andinapplicationto heatflowsthemethodbyGibouetal.wouldbedesired.

*

Correspondingauthor.

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

http://dx.doi.org/10.1016/j.jcp.2014.09.009 0021-9991/©^{2014ElsevierInc.}All rights reserved.

Fig. 1. Grid nodes inΩhare marked by◦and nodes inΓhby•. A grid node(xi,yj)∈ Ωhhas four neighboring nodes inΩh∪ Γh.

Contrarytotheirgreatimportance,theconvergencepropertiesoftheShortley–WellermethodandthemethodbyGibou etal. havejust beennumerically observed.The numerical tests, which are merely finite howevermany, are not enough toascertaintheproperties.ThoughtheShortley–Wellermethod[13]wasintroducedin1938,itisveryrecenttoseesome mathematicalanalysesonthegradientofitssolution.In2003,Lietal.[7,9]showedthesecondorderaccuracyinrectangular domains,andLietal.[8]the1

.

5 orderaccuracyinpolygonaldomains.In2014,wein[16]showedthesecondorderaccuracy ingeneraldomains.

AnimportantaspectofaPoissonsolveristhesizeoftheconditionnumberofitsassociatedlinearsystem.Alarge-sized condition number not onlydelays theconvergence to solve butalsodrops many significant digits inthe approximation.

The seminal work of Gustafsson [6] shows that only the modified incomplete-LU (MILU) preconditioner among many incomplete-LU (ILU)type preconditioners enhancesthe condition numberofthe standard finitedifference Poissonsolver with differentorder of magnitude. His work can deal onlywith rectangular domains. It is also very recent to see such estimationsinirregulardomains.Wein[15]arrivedatthesameconclusionfortheShortley–Wellermethod.OnlytheMILU enhancestheconditionnumberwithdifferentorderofgrowthwithrespecttogridstepsizeh.

In thisarticle, we introduce two analyses forthe method by Gibou etal. Oneproves that the solutionis second or- der accurate to the analytic solution. The other estimates the condition number of its linear systemwith and without preconditioners.The estimationshowsthat theunpreconditionedlinearsystemhasaverylarge conditionnumberofsize O

(

1

/(

h

·

^hmin

))

,whereh isthedefaultstepsize ofuniformgridandh_min istheminimumstepsize thatis usuallymuch smaller than h. We then show that Jacobi, symmetric Gauss–Seidel (SGS),and ILU preconditioners on the linear system reducetheconditionnumberfromO

(

1

/(

h

·

^hmin

))

to O

(

h⁻²

)

.Finally,weshowthat MILUpreconditionerexcels theothers bygainingO

(

h⁻¹

)

size.

2. Convergenceanalysis

Considerauniformgridh

Z

^{2withstepsizeh.Let}

Ω

_hbethesetofnodesofthegridbelongingto

Ω

,and

Γ

_h betheset ofintersectionpointsbetween

Γ

andgridlines.Agridnode

(

xi

,

yi

) ∈ Ω

hhasfourneighboringnodesin

Ω

h

∪ Γ

h,

(

xi±¹

,

yj

)

and

(

xi

,

yj±¹

)

in

Ω

h

∪Γ

h,asillustratedinFig. 1.Leth_i+1

2,jdenotethedistancefrom

(

xi

,

yj

)

toitsneighbor

(

xi+¹

,

yj

)

.Other distancesh_i−1

2,j

,

h_i,j+1 2

,

h_i,j−1

2 aresimilarlydefined.TheworkofGibouetal.[4]solvesthePoissonequationwithDirichlet boundarycondition

 −

u

=

f in

Ω

u

=

g on

Γ,

⁽¹⁾

bysolvingthediscreteequation

 −

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

.

⁽²⁾

HerethediscreteLaplacianoperator



hu

: Ω

h

→ R

^isdefinedas

−(

hu

)

_{i j}

:=



u_{i j}

−

^ui+1,j

h_i+1 2,j

+

^{ui j}

−

^ui−1,j

h_i−1 2,j



1 h

+



u_{i j}

−

^ui,j+1

h_i,j+1 2

+

^{ui j}

−

^ui,j−1

h_i,j−1 2



1

h

.

(3)

The equationsforeach node point

(

xi

,

yj

)

constitutea symmetriclinear systemwhosematrixis an M-matrix.It was numericallyobservedin[10]thatthenumericalsolutionissecondorderaccurateandthegradientofthesolutionisonly firstorderaccurate.

Inthissection,we analyzetheconsistencyandconvergenceaccuracyoftheGibouetal.method,whichshowsthatthe discretesolutionapproximatesthecontinuoussolutionwiththesecondorderaccuracy.Thoughtheconsistencyorderofthe discretizationrangesfromthezerotothesecond,itsconvergenceorderisthesecondordereverywhere.

Definition2.1.

Ω

_h^∗

⊂ Ω

hdenotesthesetofgridnodesadjacentto

Γ

_h,and

Ω

_h^◦

= Ω

h

\ Ω

_h^∗.

In Definition 2.1,we divides thenodes in

Ω

_h intotwo sets.Every node

(

xi

,

yj

) ∈ Ω

_h^{◦ hasthe four}neighboringpoints inside

Ω

h sothat h_i±1

2,j

=

^h_i,j±¹

2

=

^{h.Ontheother hand,if}

(

xi

,

yj

) ∈ Ω

_h^{∗,thenatleastoneofits four}neighboringpoints belongsto

Γ

h.

Lemma2.2(Consistencyerror).Forasmoothfunctionu

: Ω → R

^,

|

hu

− 

^u

| ≤



C1h²

,

in

Ω

_h^◦

C2

+

^C3h

,

in

Ω

_h^∗

,

⁽⁴⁾

whereC1

,

C2,andC3areconstantsindependentofh.

Proof. AsimpleTaylorseriesexpansiononu showstheconsistencyerror(4)withconstantsC1

,

C2,andC3dependentonly onu and

Ω

.

2

The discrete equation (2)for each

(

x_i

,

y_j

) ∈ Ω

h formsa symmetric linear systemwhose matrixis an M-matrix [12].

An importantpropertyofan M-matrixisthatitsinverseisnon-negativeineveryentry,fromwhichthediscretemaximum principlefollows.

Lemma2.3 (Discretemaximumprinciple). If

−

h

ν _≥

0,thentheminimumvalueof

ν

shouldbe achievedon

Γ

h.Similarly,if

−

h

ν ≤

^{0,thenthemaximumvalueof}

ν

shouldbeachievedon

Γ

h.Likewise,if

−

h

ν

1

≥ −

h

ν

2in

Ω

hand

ν

1

≥ ν

2on

Γ

h,then

ν

1

≥ ν

2on

Ω

h

∪ Γ

h.

Lemma2.4.Letw_hbethesolutionof

−

hw_h

=



_{0 in}

Ω

_h^◦

1 in

Ω

_h^{∗ and wh}

=

^{0 on}

Γ

h

.

Then0

≤

^wh

≤

^h2in

Ω

h.

Proof. Since

−

hwh

≥

^{0 in}

Ω

h and wh

=

^{0 on}

Γ

h, the maximum principle implies that wh

≥

^{0 in}

Ω

h. Furthermore, the maximum of wh is attainedat some point

(

xi^∗

,

yj^∗

) ∈ Ω

_h^{∗.Belonging to}

Ω

_h^∗,at least one of the four neighborhood points of

(

x_i∗

,

y_j∗

)

, say

(

x_i∗−1

,

y_j∗

)

, is a boundary point. Since all the terms in

−

hw_h

(

x_i∗

,

y_j∗

)

are non-negative and w_h

(

xi^∗−¹

,

yj^∗

) =

^0,wehave

w_h

(

x_i∗

,

y_j∗

)

hh_i∗−1

2,j^∗

≤ −

hw_h

(

x_i∗

,

y_j∗

) =

¹

,

or w_h

(

x_i∗

,

y_j∗

) ≤

^hh_i∗−¹₂,j^∗

≤

^h2

,

whichprovesthelemma.

2

Lemma2.5.Letv_hbethesolutionof

−

hv_h

=



_{1 in}

Ω

_h^◦

0 in

Ω

_h^{∗ and vh}

=

0 on

Γ

_h

.

Then0

≤

^vh

≤

^Cvin

Ω

_hforsufficientlysmallh,whereCvisindependentofh.

Proof. Since

−

hv_h

≥

^{0 in}

Ω

_h andv_h

=

^{0 on}

Γ

_h,themaximumprincipleimpliesthat v_h

≥

^{0 in}

Ω

_h.Considerananalytic solution v

: Ω → R

^satisfying

−

^v

=

^{2 in}

Ω

andv

=

^{0 on}

Γ

.Lemma 2.2impliesthatforsufficientlysmallh,wehave

−

h

(

v

−

^vh

) =

 −

hv

−

¹

≥

⁰

,

in

Ω

_h^◦

−

hv

≥ −

^C

,

in

Ω

_h^∗

,

withsomeconstant



C

>

0.Usingthediscretefunction wh giveninLemma 2.4,wehaveaninequality

−

h

(

v

−

^vh

+ 

^{C w}h

) ≥

^{0 in}

Ω

h

.

Sincev

−

^vh

+ 

^{C w}h

=

^{0 on}

Γ

h,wehavev

−

^vh

+ 

^{C w}h

≥

^{0.ThisinequalityandLemma 2.4implythat}

0

≤

^vh

≤

^v

+ 

^Ch2

.

TakingCv

=

^max

|

^v

| + 

^{C givestheestimate0}

≤

^vh

≤

^Cv forsomeconstantC independentofh.

2

Theorem2.6.Letu beacontinuoussolutiontotheproblem(1)andu_hadiscretesolutiontotheproblem(2).Thenwehave

|

^u

−

^uh

| =

^O



h²



in

Ω

h

.

Proof. UsingLemmas 2.4 and2.5,theconsistencylemmareads

|

hu

− 

^u

| ≤

^C1h²

(−

hv_h

) + (

^C2

+

^C3h

)(−

hw_h

).

Ontheotherhand,since



u

= 

hu_h

=

^{f in}

Ω

h,wehave

−

h



C₁h²v_h

+ (

^C2

+

^C3h

)

w_h

− (

^u

−

^uh

) 

≥

⁰

−

h



C₁h²v_h

+ (

^C2

+

^C3h

)

w_h

+ (

^u

−

^uh

) 

≥

⁰

.

Sincev_h

=

^wh

=

^u

−

^uh

=

^{0 on}

Γ

h,themaximumprincipleimpliesthat

|

^u

−

^uh

| ≤

^C1h²v_h

+ (

^C2

+

^C3h

)

w_h

≤

^C1C_vh²

+ (

^C2

+

^C3h

)

h²

=

^h2

(

C₁C_v

+

^C2

+

^C3h

),

whichshowstheconvergenceestimate

|

^u

−

^uh

| =

^O

(

h²

)

in

Ω

h.

2

3. Conditionnumberofthepreconditionedmatrices

Inthissection, weconsider theapplicationofbasicpreconditioningtechniques tothelinear systemthat isassociated withtheGibouetal.method.Beforeweproceedtothediscussionofthepreconditioners,weprovidetheestimationofthe conditionnumberofthelinearsystemassociatedwiththeGibouetal.method.

We mayassume that the domain

Ω

is a subset of

{(

^x

,

y

) R

²

:

⁰

≤

^x

≤

^a

,

0

≤

^y

≤

^b

}

^.Let

Ω

_h

:= {(

^ih

,

jh

) ∈ Ω :

¹

≤

ⁱ

≤

N

,

1

≤

^j

≤

^M

}

^withthelexicographicalorderon

Ω

h [3].LetK

:= |Ω

h

|

^andxk

:= (

ⁱkh

,

jkh

) ∈ Ω

h fork

=

¹

, . . . ,

K according totheorder.Throughoutthissection,let A betheK

×

^{K matrix}correspondingtothediscretePoissonequation(2),which issymmetricandpositivedefinite.Theentryar,sof A withxr

= (

ⁱrh

,

jrh

)

andxs

= (

ⁱsh

,

jsh

)

aregivenas

ar,s

=

⎧ ⎪

⎪ ⎪

⎪ ⎪

⎨

⎪ ⎪

⎪ ⎪

⎪ ⎩

−

_h¹2 if is

=

ⁱr

±

^{1 and j}r

=

^js

1 h

(

_h ¹

ir+¹₂,jr

+

_h ¹

ir−¹₂,jr

+

_h ¹

ir,jr+¹₂

+

_h ¹

ir,jr−¹₂

)

if s

=

^r

−

_h¹2 if i_s

=

ⁱrand j_s

=

^jr

±

¹

0 otherwise

(5)

whereh_i

r±¹2,jr andh_i

r,jr±¹2 aregivenas h_i

r+¹₂,j_r

=



h

,

if ir+¹

=

ir

+

1

|

ⁱrh

−

^xΓ

|,

^if

∃

^xΓ

= (

^xΓ

,

y_Γ

) ∈ Γ

such that irh

<

x_Γ

< (

ir

+

¹

)

h (6) andtheothersaregiveninthesamefashion.

Theorem3.1.Let

λ

beaneigenvalueofA,then0

<

C

≤ λ ≤

_h·h⁸_min ^forsomeC

>

0 independentofh andh_min

=

^min(ih,jh)∈Ωh

{

^h_i±¹

2,j

,

h_i,j±1

2

}

^.

Proof. Let

λ

beaneigenvalueof A.Then

λ

isapositiverealnumberbecause A issymmetricpositivedefinite.Inorderto findanupperboundof

λ

,weapplytheGerschgorinCircleTheorem.Since A isdiagonallydominant,theGerschgorinCircle Theoremimpliesthat

λ ≤

^ak,k

+

j=k

|

^ak,j

| ≤

^2ak,k

forsomek

=

¹

, . . . ,

K .From (5),we obtainthatak,k

≤

_h·h⁴_min ^forallk

=

¹

, . . . ,

K ,whichgivesanupperbound _h·h⁸

min for

λ

. Ontheotherhand,applyingthePerron–FrobeniusTheoremtotheM-matrix A⁻¹ showsthatthesmallesteigenvalue

λ

min of A issimpleandhasapositiveeigenvectoru

∈ R

^{K.Wemayassumemax}i=1,...,Ku_i

=

^{1.Regardingu asadiscretefunction} definedon

Ω

_h

∪ Γ

h withu

=

^{0 on}

Γ

_h,wecanseethatwiththehelpofw_h andvn giveninLemmas 2.4 and2.5,wehave

−

hu

= λ

minu

≤ λ

min

 −

h

(

v_h

+

^wh

) 

in

Ω

h

.

Andthemaximumprincipleimpliestheinequalityu

≤ λ

min

(

vh

+

^wh

)

in

Ω

h.ApplyingLemmas 2.4 and2.5,wefinallyobtain 1

=

^max

Ωh

u

≤ λ

minmax Ωh

(

v_h

+

^wh

) ≤ λ

min



C_v

+

^h2

 .

Since we may assume h

<

1, we conclude that

λ

min

≥

^C

>

0 for a constant C independent of h, which completes the proof.

2

Wehaveshownthattheconditionnumberofthematrix A stemmedfromthelinearsystem(2)isboundedby O

(

1

/(

h

·

h_min

))

.Table 1suggeststhattheboundistight.Sothesmallerh_minbecomes,theworsetheconditionnumberof A grows.

Indeed,thefollowingtheoremprovesthatthelowerandupperboundsaretight.

Theorem3.2.Let

λ

_minand

λ

maxbethesmallestandlargesteigenvaluesof A inmagnitude,respectively.Then

λ

_min

<

D forsome D

>

0 independentofh and

λ

max

>

_h·h¹

min.Thereforewehave

κ (

A

) =

^O

(

_h·h¹

min

)

. Proof. Atfirst,weshallshowthat

λ

max

>

_h·h¹

max.Let P

= (

^xi

,

yj

)

be thegridnode nearesttotheboundarysothathmin

=

min

{

^h_i±¹

2,j

,

h_i,j±1

2

}

^{.Thentakeavectore}P

∈ R

^{|Ωh|ofwhichtheelement}correspondingto P isoneandtheotherelements areallzero.TakingaRaleighquotient,wehave

λ

max

=

^max

0=v∈R^|Ωh|



^{A v}

,

v



^v

,

v

≥ 

^AeP

,

e_P



^eP

,

eP

=

¹

h



1

h_i−1 2,j

+

¹

h_i+1 2,j

+

¹

h_i,j−1 2

+

¹

h_i,j+1 2



>

¹ h

·

^hmin

.

In ordertoshow theestimate for

λ

min,wechoose arectangle R

⊂ Ω

^{whoseboundary isalignedwiththe gridlines.Let} R_h

=

^R

∩ Ω

h.Anyvector v

∈ R

^{|Rh| canbe extendedto} v

˜ ∈ R

^{|Ωh| bytakingzerovaluesoutsideR}h.Let B betheassociated matrixofthefive-pointfinitedifferencemethod.Then Av

˜ |

Rh

=

^{B v and A}v

˜ |

Ωh\^Rh

=

^{0,whichimplies}



^Av

˜ ,

v

˜ = 

^{B v}

,

v

^and

λ

min

=

^min

0=^u∈R^|Ωh|



Au

,

u



^u

,

u

≤

^min

0=^v∈R^|Rh|



Av

˜ ,

v

˜

˜

^v

,

^v

˜ =

^min

0=^v∈R^|Rh|



B v

,

v



^v

,

v

.

In [5],

λ

min

(

B

) =

^min0=^v∈R^{|Rh|B v},v

v,v isexactlygivenas4

(

^sin

2(^π_a^h)

h²

+

^sin2_h⁽2^πbh)

)

whichislessthan

π

²

(

_a¹2

+

_b¹2

)

,wherea

×

^b is thedimensionofthe rectangle.CombiningtheresultsofTheorem 3.1,wehave

κ (

A

) =

^O

(

_h·h¹

min

)

,whichcompletes the proof.

2

3.1. Jacobipreconditioning

Wedecompose A as A

=

^L

+

^D

+

^U

where L

,

D,andU

=

^{LT arethediagonal,thestrictlower}triangular,andtheuppertriangularpartsof A,respectively.The JacobipreconditioneristhediagonalmatrixD whosediagonalentriesarethesameasA.TheJacobipreconditioningonthe linearsystemresultsin D⁻¹Au

=

^D−1b.Thepreconditioningis,inotherwords,toscaleeachequationsothatits diagonal entrybecomesone.ApplyingtheJacobipreconditioningtoitslinearequation,theGibouetal.methodnowreads

u_{i j}

−

1 h_i+1 2,j 1

h_i+1 2,j

+

_h ¹

i−¹₂,j

+

_h ¹

i,j+¹₂

+

_h ¹

i,j−¹₂

u_i+1,j

−

1 hi−¹₂,j 1

hi+¹₂,j

+

_h ¹

i−¹₂,j

+

_h ¹

i,j+¹₂

+

_h ¹

i,j−¹₂

ui−¹,j

−

1 hi,j+¹₂ 1

hi+¹₂,j

+

_h ¹

i−¹₂,j

+

_h ¹

i,j+¹₂

+

_h ¹

i,j−¹₂

u_i,j+1

−

1 hi,j−¹₂ 1

hi+¹₂,j

+

_h ¹

i−¹₂,j

+

_h ¹

i,j+¹₂

+

_h ¹

i,j−¹₂

u_i,j−1

=

₁ ^hfi,j

hi+¹₂,j

+

_h ¹

i−¹₂,j

+

_h ¹

i,j+¹₂

+

_h ¹

i,j−¹₂

.

(7)

ItcanbeobservedfromEq.(7)thattheeigenvalueestimationfortheJacobi-preconditionedmatrixisalmostindependent ofhmin

=

^min(ih,jh)∈Ωh

{

^h_i±¹

2,j

,

h_i,j±1

2

}

^{,whilethatfortheoriginalmatrixisdependent.Thus,thepresenceofgridnodestoo}

neartheboundary isnot problematic intheJacobi-preconditionedmatrix.Precisely, leta gridnode

(

xi

,

yj

)

bevery near theboundarytotheleft.Asitgetsnearerandnearer,h_i−1

2,j

→

^{0 andthe}discretizationbecomes u_{i j}

−

⁰

·

^ui+¹,j

−

¹

·

^g

(

x_i−1

,

y_j

) −

⁰

·

^ui,j−¹

−

⁰

·

^ui,j+¹

=

⁰

·

^fi j

,

or u_{i j}

=

^g

(

x_i−1

,

y_j

).

Sothe equationmakes a diagonalblock splitfromthematrixandthe eigenvalueofthediagonalblock isone. Hence, thepresenceofgridnodesveryneartheboundaryactuallymakesratherabenigneffectonJacobi-preconditionedmatrix, contrarytoitsbadeffectontheoriginalmatrix.Now,weprovetheobservationasfollows.

Theorem3.3.Foranyeigenvalue

λ

oftheJacobi-preconditionedmatrix,wehave 0

<

^h

2

4Cv

+

_h^4h3

min

≤ λ ≤

²

.

(8)

Furthermore,ifh_min

≥

^{h3,thenwehave0}

<

Ch²

≤ λ ≤

^{2 forsomeconstantC}

=

^C

(Ω)

.

Proof. Let

λ

bean eigenvalueof D⁻¹A andu

∈ C

^{K its}corresponding eigenvector.SinceallthediagonalelementsofD are positive,let D¹² denotethe square rootmatrixof D. Thenwe can seethat D⁻¹Au

= λ

^{u ifandonly if D−12A D−12D12u}

= λ

D¹²u.Thus,thepositivedefinitenessofD⁻¹²A D⁻¹² verifiesthat

λ >

0 andu

∈ R

^{K.SinceD−1A isdiagonallydominantand}



K

j=¹

|

^a−_ii^1ai j

| ≤

^2,theGerschgorinCircleTheoremimplies

λ ≤

^2.

Ontheotherhand,wemayassumethatmaxi=¹,...,Kui

=

^{1.From(5),wehave} Au

= λ

^Du

≤

 λ

⁴

h²

,

in

Ω

_h^◦

λ

_hh⁴

min

,

in

Ω

_h^{∗ (9)}

Regardingu asadiscretefunctionon

Ω

hwithu

=

^{0 on}

Γ

h,wehave

−

hu

=

^{Au in}

Ω

h,andusingwhandvhinLemmas 2.4 and2.5,weobtain

−

hu

≤ λ

⁴

h²

(−

hv_h

) + λ

⁴

hh_min

(−

hw_h

)

in

Ω

h

= −

h

 λ

⁴

h²v_h

+ λ

⁴ hh_minw_h



in

Ω

_h

.

ApplyingthemaximumprincipleinLemma 2.3tothisinequalityaboveandusingLemmas 2.4 and2.5,weinducethat u

≤ λ

⁴

h²v_h

+ λ

⁴

hh_minw_h

≤ λ

h²



4C_v

+

^4h3 h_min

 .

Consequently,we obtainu

≤ λ

^h−2

(

4Cv

+

_h^4h_min³

)

in

Ω

h sothat 1

≤ λ

^h−2

(

4Cv

+

_h^4h_min³

)

becausemaxi=¹,...,Kui

=

^1.Combining

λ ≤

2,weobtainthebounds(8)for

λ

.Ifhmin

≥

h³,furthermore,then C⁻¹

:=

4Cv

+

_h^4h_min³

≤

4Cv

+

4.Inthiscase,

λ ≥

Ch², whichcompletestheproof.

2

Remark3.4.In[15],weshowedthatmostdomains withsmooth boundaryaswellasrectangulardomains satisfyhmin

=

O

(

h³

)

.Thedomain

Ω

iscalledtohavethegeneralintersectionpropertyifthecumulativedistributionfunction p

( ν )

defined by

p

( ν ) := (

x_i

,

y_j

) ∈ Ω

h

:

^dist



(

x_i

,

y_j

), Γ

_h



≤ ν 

(10)

isalmost linear,i.e., p

( ν ) =

^O

(

h⁻²

ν )

.Mostdomains havethegeneralintersection property(see Table 1 forexampleand [15]fordetails).Notethatwhenthecumulativedistributionfunctionp

( ν )

isalmostlinear,thenfor

α >

2,p

(

hα

) =

^O

(

hα⁻²

)

anditmeansh_min

≥

^{hα forsufficientlysmallh.}

Corollary3.5.Ifhmin

≥

^{h3,theconditionnumberoftheJacobi}preconditionedmatrixisboundedbyO

(

h⁻²

)

.

TheJacobicaseonTable 2showsthattheboundistight.WeobservethattheJacobi-preconditioningdiscretization(7) is preferredthan the original discretization(2) intwo senses.Its associated matrixhas much smallercondition number

(

O

(

h⁻²

))

thanthatoftheoriginalone

(

O

(

_h·h¹

min

))

,whichbecomes O

(

h⁻⁴

)

whenh_min

≥

^{h3.Thisisduetothefactthatthe} presenceofgridnodesvery neartheboundarymakesamaliciousone intheoriginal one.Also,theGerschgorincirclesof thematrix Aarewide spreadand, however,theJacobipreconditioning collocatesthe circlessharingthe samecenter.All theconcentrationofcirclesenhancestheconditionnumberofthematrix.