A Cascadic Multigrid Algorithm for Semilinear Indefinite Elliptic Problems

Computing 64, 349±366 (2000)

A Cascadic Multigrid Algorithm for Semilinear Inde®nite Elliptic Problems V. V. Shaidurov, Krasnoyarsk, and G. Timmermann, Dresden Received February 1999, revised July 13, 1999 Abstract We propose a cascadic multigrid algorithm for a semilinear inde®nite elliptic problem. We use a standard ®nite element discretization with piecewise linear ®nite elements. The arising nonlinear equations are solved by a cascadic organization of Newton's method with frozen derivative on a sequence of nested grids. This gives a simple version of a multigrid method without projections on coarser grids. The cascadic multigrid algorithm starts on a comparatively coarse grid where the number of unknowns is small enough to obtain an approximate solution within suciently high precision without substantial computational e€ort. On each ®ner grid we perform exactly one Newton step taking the approximate solution from the coarsest grid as initial guess. The linear Newton systems are solved iteratively by a Jacobi-type iteration with special parameters using the approximate solution from the previous grid as initial guess. We prove that for a suciently ®ne initial grid and for a suciently good start approximation the algorithm yields an approximate solution within the discretization error on the ®nest grid and that the method has multigrid complexity with logarithmic multiplier. AMS Subject Classi®cations: 65N30, 65N55, 65F10. Key Words: Newton method, multigrid methods, cascadic multigrid algorithm, smoothing iteration.

1. Introduction During the last years a special kind of ``one-way multigrid'' method was developed which uses a sequence of successively ®ner grids without projection on coarser meshes. The general scheme of such a cascadic multigrid algorithm for approximating a problem F …u† ˆ 0;

u2V;

can be described as follows: Consider a sequence of ®nite-dimensional spaces V0  V1 


 Vl  V with associated discrete problems Fi …ui † ˆ 0;

ui 2 V i ;

i ˆ 0; . . . ; l:

Let Si denote some abstract iterative process for solving the discrete problem on level i. Then a cascadic multigrid algorithm reads

350

V. V. Shaidurov and G. Timmermann

Initialization: Determine u0 2 V0 as approximate solution of F0 …u0 † ˆ 0: Iteration:

for i ˆ 1; . . . ; l do ui :ˆ Si uiÿ1 :

According to [1] a cascadic multigrid algorithm is said to be optimal if the iteration error on the ®nest grid is of the same order as the discretization error kul ÿ ul k  ku ÿ ul k and if the computational complexity of the algorithm ± denoted by comp…algo† ± is proportional to the number of unknowns Nl on the ®nest grid comp…algo† ˆ O…Nl †: The ®rst cascadic multigrid algorithm was a cascadic conjugate gradient method, see [4], where the high speed of convergence was demonstrated computationally. In the following years optimality was proved for second order elliptic boundary value problems with smooth solutions, [10], and H 1‡a -regular problems [1, 2, 11]. Moreover, the convergence analysis was extended to a whole class of smoothing iterations, [2], and to problems with curvilinear boundary, [12]. In all papers cited the second order elliptic operator was linear, self-adjoint, and positive-de®nite. Recently, L. V. Gilyova and V. V. Shaidurov proposed a cascadic multigrid algorithm for a nonlinear elliptic Dirichlet problem, [6]. They use Newton's method with frozen derivative on a sequence of nested grids. The arising linear problems are solved by a special Jacobi-type iteration taking the approximate solution from the previous grid as initial guess. They proved optimality provided that the initial grid size is suciently small and the approximate solution on the coarsest grid is suciently accurate. It was shown by G. Timmermann that this optimality result is preserved if a full Newton method is used, [14]. All these methods lead to linear systems with positive-de®nite coecient matrices. In [7] L. V. Gilyova and V. V. Shaidurov presented an optimal cascadic multigrid algorithm for linear self-adjoint but inde®nite second order elliptic operators. In this paper we combine the results for nonlinear self-adjoint and linear inde®nite problems to obtain a cascadic multigrid algorithm for nonlinear inde®nite elliptic Dirichlet problems. Again we use Newton's method with frozen derivative on a sequence of nested grids for the solution of the discrete problem. As main result we prove that the algorithm is almost optimal with logarithmic multiplier provided that the initial grid size is suciently small and that the start approximation is suciently accurate. 2. Formulation of the Problem Let X  R2 be a convex polygonal domain with boundary @X. We study the problem Lu :ˆ ÿDu ‡ f …x; u† u

ˆ 0 in X; ˆ 0 on @X

…1†

Cascadic Multigrid Algorithm

351

  R† is nonlinear in the second argument. Moreover, we assume where f 2 C 0 …X that the partial derivatives @2 f ; @22 f exist and satisfy j@2 f …x; v†j  x

and

j@22 f …x; v†j  j

…2†

for all x 2 X; v 2 R with some constants x; j > 0. We use the usual notations for Sobolev spaces: L2 …X† is the real Hilbert space of measurable functions equipped with the scalar product Z hv; wi0;X :ˆ

X

vw dx

and the induced norm 1=2

kvk0;X :ˆ hv; vi0;X : Further, H k …X† is the Hilbert space of functions v 2 L2 …X† the generalized derivatives @ jaj v=@xa ; jaj  k; of which belong to L2 …X†. The norm in H k …X† is given by 0 11=2

X @ jaj v 2

A : kvkk;X :ˆ @

@xa 0;X jajk Finally, H01 …X†  H 1 …X† denotes the space of functions which belong to H 1 …X† and vanish on @X in the sense of traces on @X. The weak formulation of problem (1) consists in the following: Find a function u 2 H01 …X† such that Z L…u; v† :ˆ

X

…rurv ‡ f …x; u†v†dx ˆ 0

for all v 2 H01 …X†:

…3†

Assumption (2) implies that the form L…:; :† is Lipschitz continuous, i.e., jL…v; z† ÿ L…w; z†j  Lkv ÿ wk1;X kzk1;X

for all v; w; z 2 H01 …X†

…4†

with some constant L > 0. We assume that problem (1) has a regular solution u 2 H 2 …X† \ H01 …X†, that is the linearization of L in u de®ned by Lu v :ˆ ÿDv ‡ @2 f …x; u†v is an isomorphism from H01 …X† onto H ÿ1 …X†. Note that u solves the variational equation (3), too. The condition on the regularity of u implies that for any function g 2 L2 …X† the problem

352

V. V. Shaidurov and G. Timmermann

Lu v v

ˆ ˆ

g in X; 0 on @X

has a solution v 2 H 2 …X† \ H01 …X† which satis®es kvk2;X  ckgk0;X :  we de®ne the bilinear form Lz : H 1 …X†  H 1 …X† ! R For any function z 2 C 0 …X† 0 0 by Z …5† Lz …v; w† :ˆ …rvrw ‡ @2 f …x; z†vw†dx: X

Then the regularity of u implies that there exists a constant c > 0 such that inf

v2H01 …X†

sup

w2H01 …X†

Lu …v; w†  c: kvk1;X kwk1;X

…6†

3. Discretization For the discretization of problem (3) we use linear ®nite elements on a nested sequence of triangulations obtained by the following re®nement procedure. Given an initial triangulation T0 of the domain X the re®ned triangulation T1 is obtained by dividing each triangle T 2 T0 into four equal triangles by connecting the midpoints of the edges. Repeating this process of subdivision we get a nested sequence of triangulations …Ti †liˆ0 with mesh size parameter hi :ˆ maxT 2Ti diamT which satis®es hi ˆ hiÿ1 =2

for i ˆ 1; . . . ; l:

…7†

With each triangulation Ti we associate the linear ®nite element space  : vjT 2 P1 …T † Vi :ˆ fv 2 C…X†

for all T 2 Ti ; vj@X ˆ 0g

where P1 …T † denotes the set of linear functions over the triangle T . Since the triangulation is nested we have V0  V1 


 Vl  H01 …X†: The ®nite element approximation for problem (3) is de®ned as follows: Find a function ui 2 Vi such that Z L…ui ; vi † ˆ

X

…rui rvi ‡ f …x; ui †vi †dx ˆ 0

for all vi 2 Vi :

…8†

Cascadic Multigrid Algorithm

353

Lemma 1. Let assumption (2) be satis®ed and let u 2 H 2 …X† \ H01 …X† be a regular solution of problem (1) in the sense of (6). Then there exists a constant H0 > 0 such that for all hi  H0 the discrete problem (8) has a solution ui 2 Vi which satis®es ku ÿ ui k1;X  c inf ku ÿ vi k1;X vi 2Vi

where the constant c > 0 is independent of i. The proof is essentially based on the implicit function theorem. For a detailed discussion we refer to [3], cf. Theorem 7.1. When using linear ®nite elements over triangulations satisfying (7) the usual approximation property implies ku ÿ ui k1;X  chi kuk2;X

…9†

with a constant c > 0 independent of i. Next we provide a discretization error estimate in L2 -norm. Lemma 2. Let the assumptions of Lemma 1 be satis®ed. Then there exists a constant H1  H0 such that for hi  H1 the discretization error is given by ku ÿ ui k0;X  ch2i kuk2;X

…10†

where the constant c > 0 is independent of i. Proof: The proof uses a modi®cation of the method by Aubin and Nitsche applied to a special linear problem. Let hi  H0 be such that the discrete problem  ! R by (8) has a solution ui 2 Vi . Then we de®ne a function p : X 8 < @2 f …x; u† p…x† :ˆ f …x; u† ÿ f …x; ui † : u…x† ÿ ui …x†

if u…x† ˆ ui …x†, if u…x† 6ˆ ui …x†

and consider the auxiliary problem: Find w 2 H01 …X† such that Z b…w; v† :ˆ

X

…rwrv ‡ pwv†dx ˆ hu ÿ ui ; vi0;X

for all v 2 H01 …X†:

…11†

First, we show that this problem has a solution w 2 H 2 …X† \ H01 …X†. Using Taylor expansion p…x† can be written as p…x† ˆ @2 f …x; u† ÿ 12 @22 f …x; n†…u…x† ÿ ui …x†† where n ˆ n…x† lies between u ˆ u…x† and ui ˆ ui …x†. Hence, with (2) and the imbeddings H01 …X† ,! L2 …X†; H01 …X† ,! L4 …X†, and the discretization error estimate (9) we obtain

354

V. V. Shaidurov and G. Timmermann

Z b…w; v†  Lu …w; v† ÿ c

X

ju ÿ ui jjwjjvjdx

 Lu …w; v† ÿ cku ÿ ui k0;X kwkL4 …X† kvkL4 …X†  Lu …w; v† ÿ cku ÿ ui k1;X kwk1;X kvk1;X  Lu …w; v† ÿ chi kwk1;X kvk1;X :

…12†

If hi  H00 with H00 :ˆ minfH0 ; cc=2g then the inf-sup-condition (6) implies inf

w2H01 …X†

b…w; v†  c ÿ chi > 0: v2H 1 …X† kwk1;X kvk1;X sup 0

For these hi there exists a solution w 2 H01 …X† \ H 2 …X† to problem (11) such that kwk2;X  cku ÿ ui k0;X : Moreover, there exists a constant H1  H00 such that for all hi  H1 the corresponding discrete problem b…wi ; vi † ˆ hu ÿ ui ; vi i0;X

for all vi 2 Vi

has a solution wi which satis®es kw ÿ wi k1;X  chi kwk2;X  chi ku ÿ ui k0;X ;

…13†

see [9]. Setting v ˆ u ÿ ui in (11) we obtain ku ÿ ui k20;X ˆ L…u; w† ÿ L…ui ; w†: With L…u; wi † ˆ L…ui ; wi † ˆ 0, the Lipschitz continuity (4), and the discretization error estimates (9), (13) this leads to ku ÿ ui k20;X ˆ L…u; w ÿ wi † ÿ L…ui ; w ÿ wi †  Lku ÿ ui k1;X kw ÿ wi k1;X  ch2i kuk2;X ku ÿ ui k0;X : ( 4. Formulation of the Algorithm For the solution of the discrete problem (8) we use Newton's method with frozen derivative. We assume that u0 2 V0 is an approximate solution of (8) on the coarsest grid i ˆ 0 which is determined within suciently high precision. This solution u0 is used for linearization at all grids. On each level we perform exactly

Cascadic Multigrid Algorithm

355

one Newton step. As a result on level i we have to solve the following problem: Find zi 2 Vi such that Lu0 …zi ÿ uiÿ1 ; vi † ˆ ÿL…uiÿ1 ; vi † for all vi 2 Vi

…14†

where uiÿ1 is the approximate solution of (8) on level i ÿ 1. This equation can be rewritten as Lu0 …zi ; vi † ˆ hg…uiÿ1 †; vi i0;X

for all vi 2 Vi

with hg…uiÿ1 †; vi i0;X ˆ ÿL…uiÿ1 ; vi † ‡ Lu0 …uiÿ1 ; vi † Z ˆ …ÿf …x; uiÿ1 †vi ‡ @2 f …x; u0 †uiÿ1 vi †dx: X

Let Xi denote the set of inner vertices of the triangulation Ti which are numbered by 1 to Ni . With each node xj 2 Xi we associate the piecewise linear nodal basis  which equals 1 at xj and 0 at all other nodes xk 2 Xi . Using function uij 2 C 0 …X† P the usual isomorphism between functions vi …x† ˆ xj 2Xi v…xj †uij …x† 2 Vi and vectors vi 2 RNi with components vi …xj † this system is equivalent to the linear system L i zi ˆ f i

…15†

where the components of Li ˆ …lijk †jk 2 RNi Ni and fi ˆ …fji †j 2 RNi are given by lijk ˆ Lu0 …uik ; uij † fji

ˆ

for all j; k such that xj ; xk 2 Xi ;

hg…uiÿ1 †; uij i0;X

for all j such that xj 2 Xi :

Note that the matrix Li is symmetric but not necessarily positive-de®nite. The next lemma provides a result on the solvability of the Newton systems. Lemma 3. Let the assumptions of Lemma 1 be satis®ed. Let H1 > 0 be such that for hi  H1 the discrete problem (8) has a solution ui 2 Vi which satis®es the error estimates (9), (10). Then there exists a constant H2  H1 such that for hi  H2 and suciently good approximate solutions u0 the Newton system (15) has a unique solution zi 2 RNi . Proof: We show that the bilinear form Lu0 …:; :† satis®es a certain inf-sup-condition. In analogy to the proof of Lemma 2 we obtain Z Lu0 …v; w†  Lu …v; w† ÿ c

X

ju ÿ u0 jjwjjvjdx

 Lu …v; w† ÿ c0 ku ÿ u0 k1;X kvk1;X kwk1;X

356

V. V. Shaidurov and G. Timmermann

with some constant c0 > 0. Let u0 be a suciently good approximate solution and let h0  H2  H1 be suciently small such that ku ÿ u0 k1;X  ku ÿ u0 k1;X ‡ ku0 ÿ u0 k1;X  ch0 kuk2;X ‡ ku0 ÿ u0 k1;X 

c : 2c0

Then we obtain Lu0 …w; v† c  c ÿ c0 ku ÿ u0 k1;X  > 0 2 w2H01 …X† v2H 1 …X† kwk1;X kvk1;X inf

sup

…16†

0

which implies the solvability of the Newton systems.

(

The Newton systems are solved by a Jacobi-type iteration with special parameters. Therefore, we de®ne the diagonal matrix Di ˆ diag…dji †j 2 RNi Ni by dji :ˆ

X x measT 3 T 2T ;x 2T \X i

j

…17†

i

where x > 0 is the bound for @2 f , see (2). Obviously, the matrix Di is positivede®nite. Note that if Mi ˆ …mijk †jk is the usual mass matrix de®ned by mijk ˆ huik ; uij i0;X then Di can be interpreted as an approximation of the matrix xMi using a quadrature scheme. The matrix Di is used as a preconditioner. Let ki denote the upper bound for the maximal in modulus eigenvalue of Dÿ1 i Li given by ki ˆ max j

Ni 1X li : i dj kˆ1 jk

…18†

Let Ii : RNi ! RNi‡1 be the linear interpolation operator which corresponds to the identical imbedding Vi ,! Vi‡1 with respect to the isomorphism between Vi and RNi de®ned above. Then the Cascadic Multigrid Algorithm for Semilinear Inde®nite Problems (CASIP) reads as follows. Algorithm CASIP Initialization: Determine u0 as an approximate solution of (8) for i ˆ 0. Iteration: for i ˆ 1; . . . ; l do w0 ˆ Iiÿ1 uiÿ1 for k ˆ 0; . . . ; mi ÿ 1 do  ÿ2 p…2k‡1† : sk :ˆ ki cos 2…2m ‡1† i rk :ˆ fi ÿ Li wk : ÿ1 wk‡1 :ˆ wk ‡ sk Dÿ1 i Li Di rk

ui :ˆ wmi .

Cascadic Multigrid Algorithm

357

5. Error Analysis In this section we give a detailed error analysis for the cascadic multigrid  we de®ne the algorithm CASIP. We begin with some de®nitions. For z 2 C 0 …X† x 1 1 shifted bilinear form Lz : H0 …X†  H0 …X† ! R by Z …v; w† :ˆ …rvrw ‡ …@2 f …x; z† ‡ x†vw†dx: …19† Lx z X

This bilinear form induces an energy norm 1=2 jjjvjjjz;x :ˆ ‰Lx z …v; v†Š

…20†

which is uniformly equivalent to the H 1 -norm due to (2), i.e., there exist a constant c > 1 independent of z such that 1 c kvk1;X

 jjjvjjjz;x  ckvk1;X :

…21†

The error analysis is done using an equivalent discrete energy norm. Therefore, we introduce the scalar product hv; wiDi :ˆ vT Di w

for all v; w 2 RNi

and the corresponding vector norm 1=2

kvki :ˆ hv; viDi : By standard techniques, cf. [8], it can be shown that this norm is uniformly equivalent to the L2 -norm, i.e., there exists a constant c > 1 independent of i such that 1 c kvk0;X

 kvkDi  ckvk0;X

…22†

for all v 2 Vi and corresponding grid vectors v 2 RNi . Further, we de®ne the discrete energy norm jjjvjjji :ˆ ‰vT …Li ‡ Di †vŠ1=2

for all v 2 RNi :

It follows from (21) and (22) that this norm is uniformly equivalent to the H1 -norm, i.e., there exists a constant c > 1 independent of i such that 1 c kvk1;X

 jjjvjjji  ckvk1;X

for all v 2 Vi and corresponding grid vectors v 2 RNi . Finally, we de®ne the iteration error ei :ˆ jjjui ÿ ui jjji

for i ˆ 0; . . . ; l:

…23†

358

V. V. Shaidurov and G. Timmermann

The outline of the analysis is as follows: In Lemma 4 we show how the discrete norms k:ki and jjj:jjji on two successive levels i and i ‡ 1 are related. Then in Lemma 5 we prove some smoothing properties of the Jacobi-type iteration used in the cascadic algorithm CASIP. The Newton error jjjui ÿ zi jjji is estimated in Lemma 6. In Lemma 7 we provide a recursive estimate for the iteration error ei . In Theorem 8 we formulate the main results for the cascadic multigrid algorithm CASIP. Lemma 4. For any vector v 2 RNi we have kIi vki‡1  kvki

and

jjjIi vjjji‡1  jjjvjjji :

…24†

Proof: With the usual property Li ˆ ITi Li‡1 Ii for nested ®nite element spaces the second estimate is a consequence of the ®rst one. The proof of the ®rst estimate is essentially based on the special re®nement procedure which generates the family of triangulations fTi gliˆ0 . In particular, if xj ; xk are two neighbour vertices of Ti then the midpoint …xj ‡ xk †=2 is a vertex of Ti‡1 . Further, we use the property of piecewise linear functions v 2 Vi that   ‰v…xj † ‡ v…xk †Š2 v2 …xj † ‡ v2 …xk † 2 xj ‡ xk  : …25† ˆ v 2 4 2 Finally, each triangle T 2 Ti is divided into four equal triangles Ti;j so that measTi;j ˆ 14 measTi

for j ˆ 1; . . . ; 4:

…26†

Let the vertices of a triangle T 2 Ti be denoted by x1;T ; x2;T ; x3;T . Taking into account that  x X 2 v …x1;T † ‡ v2 …x2;T † ‡ v2 …x3;T † measT kvk2i ˆ hv; viDi ˆ 3 T 2T i

and using (25), (26) a careful calculation yields kIi vki‡1  kvki .

(

In the next lemma we prove some properties of the Jacobi-type iteration used in the cascadic algorithm CASIP. Preliminarily, we consider the polynomial q…x† ˆ

mY i ÿ1

…1 ÿ sk x2 †

kˆ0

with parameters sk as in algorithm CASIP. In [12] it is proved that this polynomial satis®es the estimates jq…x†j  1; jxq2 …x†j 

ki 2mi ‡ 1

…27† …28†

Cascadic Multigrid Algorithm

359

for all x 2 ‰ÿki ; ki Š, where ki is de®ned as in (18). Using standard arguments, cf. [8], it can be shown that ki  chÿ2 i :

…29†

Now we introduce the error propagation operator Qi;mi : RNi ! RNi which relates the initial and the ®nal iteration error according to zi ÿ ui ˆ Qi;mi …zi ÿ Iiÿ1 uiÿ1 †: Then the error propagation operator of the Jacobi-type iteration used in algorithm CASIP is given by the polynomial Qi;mi ˆ q…Dÿ1 i Li †. Lemma 5. The error propagation operator of the smoother used in algorithm CASIP satis®es the estimates   1 …30† jjjQi;mi vjjji  c 1 ‡ p kvk0;X hi m i jjjQi;mi vjjji  jjjvjjji

…31†

for all v 2 RNi . Proof: For the proof we consider the eigenvalue problem Li g ˆ lDi g. The theory of generalized eigenvalue problems implies that there exists an Di -orthogonal set i of eigenvectors fgj gNjˆ1 such that hgj ; gk iDi ˆ djk . Let v 2 RNi be an arbitrary vector with the expansion vˆ

Ni X jˆ1

v j gj :

…32†

Then the norms of v are given by kvk2i ˆ

Ni X jˆ1

v2j

jjjvjjj2i ˆ

and

Ni X jˆ1

…1 ‡ lj †v2j :

For the error propagation operator we obtain jjjQi;mi vjjj2i ˆ

Ni X jˆ1

…1 ‡ lj †q2 …lj †v2j :

With (28) we get jjjQi;mi vjjj2i 

Ni X …1 ‡ lj †v2j ˆ jjjvjjj2i : jˆ1

360

V. V. Shaidurov and G. Timmermann

On the other hand, (27) leads to jjjQi;mi vjjj2i 

 1‡

X   Ni ki ki v2j ˆ 1 ‡ kvk2i : 2mi ‡ 1 jˆ1 2mi ‡ 1

Using the inequality …a2 ‡ b2 †1=2  a ‡ b for a; b > 0, the norm equivalence (22), and estimate (29) we end up with p     1 ki jjjQi;mi vjjji  c 1 ‡ p kvk0;X  c 1 ‡ p kvk0;X : hi mi 2mi ‡ 1 In the following lemma we provide an estimate for the Newton error. Lemma 6. Let h0  H2 be suciently small and let u0 be such that (16) holds, i.e., the Newton systems have unique solutions zi . Then there exists a constant H3  H2 such that for all hi  H3 jjjui ÿ zi jjji  c1 jjjui ÿ Iiÿ1 uiÿ1 jjj2i ‡ c2 jjjui ÿ Iiÿ1 uiÿ1 jjji kui ÿ u0 k1;X :

…33†

Proof: The proof is straight-forward using standard techniques. We recall that the Newton system is given by Z X

…rzi rvi ‡ @2 f …x; u0 †zi vi †dx ˆ

Z X

…ÿf …x; uiÿ1 †vi ‡ @2 f …x; u0 †uiÿ1 vi †dx

for all vi 2 Vi . Subtracting this equation from the nonlinear system (8) Z X

…rui rvi ‡ f …x; ui †vi †dx ˆ 0

for all vi 2 Vi

we obtain Z …r…ui ÿ zi †rvi ‡ @2 f …x; u0 †…ui ÿ zi †vi †dx X Z
ÿÿ
f …x; uiÿ1 † ÿ f …x; ui † vi ‡ @2 f …x; u0 †…ui ÿ uiÿ1 †vi dx ˆ X

…34† for all vi 2 Vi :

Let us use the Taylor expansions f …uiÿ1 † ˆ f …ui † ‡ @2 f …x; ui †…uiÿ1 ÿ ui † ‡ 12 @22 f …x; n1 †…uiÿ1 ÿ ui †2 with n1 ˆ n1 …x† lying between uiÿ1 ˆ uiÿ1 …x† and ui ˆ ui …x† and @2 f …x; u0 † ˆ @2 f …x; ui † ‡ @22 f …x; n2 †…u0 ÿ ui †

Cascadic Multigrid Algorithm

361

with n2 ˆ n2 …x† lying between u0 ˆ u0 …x† and ui ˆ ui …x†. Then (34) can be written as Z 1 @22 f …x; n1 †…ui ÿ uiÿ1 †2 vi dx Lu0 …ui ÿ zi ; vi † ˆ 2 X Z @22 f …x; n2 †…u0 ÿ ui †…ui ÿ uiÿ1 †vi dx …35† ‡ X

Now we consider the auxiliary problem: Find w 2 H01 …X† such that Lu0 …v; w† ˆ hui ÿ zi ; vi0;X

for all v 2 H01 …X†:

Since hi  H2 and u0 are chosen such that (16) holds this problem has a solution w 2 H01 …X† \ H 2 …X† which satis®es the estimate kwk2;X  ckui ÿ zi k0;X :

…36†

Then there exists a constant H3  H2 such that for all hi  H3 the corresponding discrete problem Lu0 …vi ; wi † ˆ hui ÿ zi ; vi i0;X

for all vi 2 Vi

…37†

has a solution wi 2 Vi which satis®es kw ÿ wi k1;X  chi kwk2;X  chi kui ÿ zi k0;X ; cf. [9]. This implies kwi k0;X  kwk2;X ‡ kw ÿ wi k1;X  …1 ‡ chi †kwk2;X :

…38†

Setting vi ˆ wi in (35) and vi ˆ ui ÿ zi in (37) we obtain kui ÿ zi k20;X ˆ

1 2 ‡

Z X

Z

@22 f …x; n1 †…ui ÿ uiÿ1 †2 wi dx

X

@22 f …x; n2 †…u0 ÿ ui †…ui ÿ uiÿ1 †wi dx:

…39†

On the other hand, with vi ˆ ui ÿ zi in (35) and using (39) we get jjjui ÿ zi jjj2u ;x ˆ Lu0 …ui ÿ zi ; ui ÿ zi † ‡ xkui ÿ zi k20;X 0 Z ÿ
1 ˆ @22 f …x; n1 †…ui ÿ uiÿ1 †2 …ui ÿ zi † ‡ xwi dx 2 X Z
ÿ @22 f …x; n2 †…u0 ÿ ui †…ui ÿ uiÿ1 † …ui ÿ zi † ‡ xwi dx ‡ X

Now condition (2), the norm equivalence (21), and the Cauchy inequality lead to

362

V. V. Shaidurov and G. Timmermann

ÿ
kui ÿ zi k21;X  ckui ÿ uiÿ1 k2L4 …X† kui ÿ zi k0;X ‡ xkwi k0;X ÿ
‡ cku0 ÿ ui kL4 …X† kui ÿ uiÿ1 kL4 …X† kui ÿ zi k0;X ‡ xkwi k0;X : With (36) and (38) the term in the scopes can be estimated by kui ÿ zi k0;X ‡ xkwi k0;X  ckui ÿ zi k0;X  ckui ÿ zi k1;X : Finally, the imbedding H01 …X† ,! L4 …X† implies kui ÿ zi k1;X  c01 kui ÿ uiÿ1 k21;X ‡ c02 ku0 ÿ ui k1;X kui ÿ uiÿ1 k1;X : Taking into account the norm equivalence (23) we obtain (33) with appropriate constants c1 ; c2 > 0. ( In the next lemma we prove a recursive estimate for the iteration error ei . Lemma 7. Let e > 0 be some ®xed constant and assume that hi  H3 . Let u0 be such that (16) and the condition e0  eh0 kuk2;X

…40†

are satis®ed. Then the iteration error ei can be estimated by hi ei  c3 e2iÿ1 ‡ c4 h0 kuk2;X eiÿ1 ‡ c5 h0 hi kuk22;X ‡ c6 p kuk2;X ‡ eiÿ1 : mi

…41†

Proof: The error ei consists of two parts, namely one arising due to Newton's method and another caused by the iterative solution of the linear system (15): ei ˆ jjjui ÿ ui jjji  jjjui ÿ zi jjji ‡ jjjzi ÿ ui jjji :

…42†

First, we estimate the right-hand side of the Newton error estimate provided in Lemma 6. Using Lemma 4, the discretization error estimate (9), the norm equivalence (23), and hi ˆ hiÿ1 =2 we obtain jjjui ÿ Iiÿ1 uiÿ1 jjji  jjjui ÿ Iiÿ1 uiÿ1 jjji ‡ jjjIiÿ1 …uiÿ1 ÿ uiÿ1 †jjji  ckuiÿ1 ÿ ui k1;X ‡ jjjuiÿ1 ÿ uiÿ1 jjjiÿ1  chi kuk2;X ‡ eiÿ1 : Further, the discretization error estimate (9) and the condition (40) for e0 imply kui ÿ u0 k1;X  kui ÿ uk1;X ‡ ku ÿ u0 k1;X ‡ ku0 ÿ u0 k1;X  ch0 kuk2;X : After summarizing these estimates the Newton error satis®es

Cascadic Multigrid Algorithm

363

jjjui ÿ zi jjji  c1 …eiÿ1 ‡ chi kuk2;X †2 ‡ c2 …eiÿ1 ‡ chi kuk2;X †ch0 kuk2;X  c03 e2iÿ1 ‡ c04 h0 kuk2;X eiÿ1 ‡ c05 h0 hi kuk22;X with appropriate constants c0k > 0. The error caused by the iterative solution of the linear systems is bounded by jjjzi ÿ ui jjji ˆ jjjQi;mi …zi ÿ Iiÿ1 uiÿ1 †jjji  jjjQi;mi …zi ÿ ui †jjji

‡ jjjQi;mi …ui ÿ Iiÿ1 uiÿ1 †jjji ‡ jjjQi;mi Iiÿ1 …uiÿ1 ÿ uiÿ1 †jjji :

With the results of Lemma 5 we obtain   1  jjjzi ÿ ui jjji  jjjzi ÿ ui jjji ‡ c 1 ‡ p kui ÿ uiÿ1 k0;X ‡ jjjIiÿ1 …uiÿ1 ÿ uiÿ1 †jjji : hi m i The ®rst term is again the Newton error which can be estimated as above. For the second term we use (10). Applying Lemma 4 to the last term yields hi jjjzi ÿ ui jjji  jjjzi ÿ ui jjji ‡ eiÿ1 ‡ ch2i kuk2;X ‡ c p kuk2;X mi so that we end up with hi ei  2jjjzi ÿ ui jjji ‡ eiÿ1 ‡ ch2i kuk2;X ‡ c p kuk2;X mi hi  c3 e2iÿ1 ‡ c4 h0 kuk2;X eiÿ1 ‡ c5 h0 hi kuk22;X ‡ c6 p kuk2;X ‡ eiÿ1 mi with appropriate constants ck > 0. ( Now we can prove the main error estimate for the cascadic multigrid algorithm CASIP. Theorem 8. Let the number mi of iteration steps be chosen according to mi ˆ dml 4lÿi e

for i ˆ 1; . . . ; l:

…43†

Suppose that h0  H3 and hl ˆ 2ÿl h0 satisfy the relation h20  c7 hl

…44†

with some constant c7  1. Let the approximate solution u0 satisfy the assumptions of Lemma 7 and, additionally, e0  ehl kuk2;X :

…45†

Then the following assertion holds: For suciently small h0 the cascadic multigrid algorithm CASIP generates an approximate solution ul such that

364

V. V. Shaidurov and G. Timmermann

el  c8 hl kuk2;X where the constant

  c6 c8 :ˆ 2c7 e ‡ c5 c7 kuk2;X ‡ p l ml

is independent of h0 and hl . Proof: We de®ne the constant c9 :ˆ …c3 c8 ‡ c4 †kuk2;X . For any constant c9 > 0 the function g…x† ˆ …1 ‡ c9 x†ÿ log2 x is continuous on …0; 1† and has the limit limx!‡0 g…x† ˆ 1. Hence, for a suciently small constant b ˆ b…c9 † > 0 jg…x†j  2

for all x 2 …0; bŠ:

Thus, if h0 satis®es (44) which is equivalent to h0  c7 2ÿl and h0  minfb…c9 †; 1=2; c7 2ÿl g then …1 ‡ c9 h0 †l  …1 ‡ c9 h0 †ÿ log2 h0 ‡log2 c7  2c7 :

…46†

Now we choose h0 such that h0  minfH3 ; b…c9 †; 1=2; c7 2ÿl g. We will show that for i ˆ 0; . . . ; l ei  …1 ‡ c9 h0 †i e0 ‡ c5 h0 kuk22;X

i X

hj …1 ‡ c9 h0 †iÿj

jˆ1

i X hj iÿj ‡ c6 kuk2;X p …1 ‡ c9 h0 † ; m j jˆ1

ei  c8 hl kuk2;X :

…47† …48†

For the proof we use induction on i. Obviously, the estimates (47) and (48) are satis®ed for i ˆ 0. Assume that (47) and (48) hold for a ®xed level i > 0. Using Lemma 7, (47), (48) on level i, and hi ˆ hiÿ1 =2 we obtain   hi‡1 ei‡1  1 ‡ …c3 ei ‡ c4 h0 kuk2;X † ei ‡ c5 h0 hi‡1 kuk22;X ‡ c6 p kuk2;X mi‡1   hi‡1  1 ‡ …c3 c8 ‡ c4 †kuk2;X h0 ei ‡ c5 h0 hi‡1 kuk22;X ‡ c6 kuk2;X p mi‡1 i‡1 X hj …1 ‡ c9 h0 †i‡1ÿj  …1 ‡ c9 h0 †i‡1 e0 ‡ c5 h0 kuk22;X jˆ1

i‡1 X hj i‡1ÿj ‡ c6 kuk2;X p …1 ‡ c9 h0 † m j jˆ1

Cascadic Multigrid Algorithm

365

which is (47) for i ‡ 1. Applying (46) results in i‡1 X

ei‡1  2c7 e0 ‡ 2c5 c7 h0 kuk22;X

jˆ1

hj ‡ 2c6 c7 kuk2;X

i‡1 X hj p : mj jˆ1

…49†

Furthermore, hi ˆ hiÿ1 =2; h20  c7 hl , and (43) imply ei‡1

! lh l  2c7 e0 ‡ c5 kuk22;X h20 2ÿj ‡ c6 kuk2;X p ml jˆ1   c6 l  2c7 e ‡ c5 c7 kuk2;X ‡ p hl kuk2;X ˆ c8 hl kuk2;X : ml i‡1 X

( The arithmetic complexity of the algorithm can essentially be estimated as in [1] since on the levels 1 to l exactly one linear system is solved. For triangulations of two-dimensional domains X obtained by a re®nement process as described in Section 3 we have the relation Ni  4Niÿ1 which implies Nl  4lÿi Ni . Hence, comp…CASIP † ˆ c

l X

mi Ni  clml Nl :

…50†

iˆ1

Additionally, we have to take into account the computational costs at level 0 since 1= the coarsest grid size h0 ˆ O…hhl † tends to zero. For this purpose we assume that u0 is obtained by Newton's method with a conjugate gradient iteration for the solution of the linearized algebraic systems which are transformed by Gauss transformation to ensure positive de®niteness. The most restrictive condition for u0 is (45). Due to the quadratic rate of convergence, cf. [5], the number of Newton iterations is O…log l†. Each conjugate gradient iteration costs O…N1 † and N0 iterations reverse this method into a direct one. Therefore, the number of arithmetic operations for each Newton step is O…N1 †. Using the relation N02 ˆ O…Nl † the total costs on level 0 do not exceed O…Nl log l† which is less than (50). Thus, we get both accuracy and multigrid complexity almost optimal, i.e., with logarithmic multiplier. In practical problems a simple iteration as suggested in the cascadic multigrid algorithm CASIP is unstable for large mi . In this case we recommend another stable form of the same process using a 2-step iteration. For details see [15].

Acknowledgement This work was supported by Volkswagenstiftung under grant I 72342 and by Deutsche Forschungsgemeinschaft under grant GR 705/4-2.

366

V. V. Shaidurov and G. Timmermann: Multigrid Algorithm

References [1] Bornemann, F. A., Deu¯hard, P.: The cascadic multigrid method for elliptic problems. Numer. Math. 75, 135±152 (1996). [2] Bornemann, F. A.: On the convergence of cascadic iterations for elliptic problems. Technical Report SC 94-8, Konrad-Zuse-Zentrum fuÈr Informationstechnik Berlin, 1994. [3] Caloz, G., Rappaz, J.: Numerical analysis for nonlinear and bifurcation problems, In: Handbook of numerical analysis, Vol. V (Ciarlet, P. G., Lions, J. L. eds.). Amsterdam: North-Holland, 1997. [4] Deu¯hard, P.: Cascadic conjugate gradient methods for elliptic partial di€erential equations. I. Algorithm and numerical results. Technical Report SC 93-23, Konrad-Zuse-Zentrum fuÈr Informationstechnik Berlin, 1993. [5] Deu¯hard, P., Potra, F.: Asymptotic mesh-independence of Newton-Galerkin methods via a re®ned Mysovskii theorem. SIAM J. Numer. Anal. 29, 1395±1412 (1992). [6] Gilyova, L. V., Shaidurov, V. V.: Cascade algorithms for solution of discrete analouge of slightly nonlinear equation. Technical Report, Technische UniversitaÈt Dresden, FakultaÈt fuÈr Mathematik und Naturwissenschaften, 1998. [7] Gilyova, L. V., Shaidurov, V. V.: A cascadic multigrid algorithm in ®nite element method for a sign-inde®nite elliptic problem. Technical Report, 1998 (in preparation). [8] Hackbusch, W.: Multi-grid methods and applications. Berlin Heidelberg New York Tokyo: Springer 1985. [9] Oganesjan, L. A., Rukhovets, L. A.: Variational di€erence methods for the solution of elliptic equations. Academy of Sciences of Armenia, Jerewan, 1979 (in Russian). [10] Shaidurov, V. V.: Some estimates of the rate of convergence for the cascadic conjugate-gradient method. Technical Report, Otto-von-Guericke-UniversitaÈt Magdeburg, FakultaÈt fuÈr Mathematik, 1993. [11] Shaidurov, V. V.: The convergence of the cascadic conjugate-gradient method under a de®cient regularity. Problems and methods in mathematical physics (Jentsch, L., TroÈltzsch, F., eds.), pp. 185±194. Stuttgart-Leipzig: Teubner-Verlag, 1994. [12] Shaidurov, V. V.: Multigrid methods for ®nite elements. Dordrecht: Kluwer Academic Publishers, 1995. [13] Shaidurov, V. V.: Cascadic algorithm with nested subspaces in domains with curvilinear boundary. Advanced mathematics: computations and applications (Alekseev, A. S., Bakhvalov, N. S., eds.), pp. 588±595. Novosibirsk: NCC Publisher, 1995. [14] Timmermann, G.: A cascadic algorithm for the solution of a weakly nonlinear problem. Technical Report, Technische UniversitaÈt Dresden, FakultaÈt fuÈr Mathematik und Naturwissenschaften, 1997. [15] Timmermann, G.: Cascadic algorithms for two classes of nonlinear elliptic boundary value problems. PhD thesis, Technische UniversitaÈt Dresden, FakultaÈt fuÈr Mathematik und Naturwissenschaften, 1999. V.V. Shaidurov Institute of Computational Modelling Russian Academy of Sciences Siberian Division 660036 Krasnoyarsk Russia e-mail: [email protected]

G. Timmermann Electrotechnical Institute Technical University of Dresden D-01062 Dresden Germany e-mail: [email protected]