Analysis of a cell-vertex finite volume method for convection-diffusion problems K. W. Morton Bill.Morton@comlab.ox.ac.uk Martin Stynes STMT8007@iruccvax.ucc.ie Endre Suli Endre.Suli@comlab.ox.ac.uk Morton_K W | Stynes_Martin | Suli_Endre -norm.

]]> A cell-vertex finite volume approximation of elliptic convection-dominated diffusion equations is considered in two dimensions. The scheme is shown to be stable and second-order convergent in a mesh-dependent -norm. BS P. Balland and E. Suli, Analysis of the cell vertex finite volume method for hyperbolic equations with variable coefficients, SIAM J. Numer. Anal. 34 , No. 3, June 1997. CMM P.I. Crumpton, J.A. Mackenzie and K.W. Morton, Cell vertex algorithms for the compressible Navier-Stokes equations, Journal of Computational Physics, 109 (1993), 1--15. 94e:76081 Jameson79 A. Jameson, Acceleration of transonic potential flow calculations on arbitrary meshes by the multiple grid method, AIAA Paper 79 , p. 1458, 1979. Keller H. Keller, A new finite difference scheme for parabolic problems, In: Numerical Solution of Partial Differential Equations II, SYNSPADE 1970 (Ed., B. Hubbard,) Academic Press, 1971, 327--350. 43:2866 Morch K. W. Morton, Numerical Solution of Convection-Diffusion Problems, Applied Mathematics and Mathematical Computation, 12 , Chapman and Hall, London, 1996. MCM K.W. Morton, P.I. Crumpton and J.A. Mackenzie, Cell vertex methods for inviscid and viscous flows, Computers Fluids, 22 (1993), 91--102. MorMac92 J. A. Mackenzie and K. W. Morton, Finite volume solutions of convection-diffusion test problems, Mathematics of Computation, 60 (1992), 189--220. 93d:76065 MortPais89 K. W. Morton and M. F. Paisley, A finite volume scheme with shock fitting for the steady Euler equations, Journal of Computational Physics, 80 (1989), 168--203. MortSty K. W. Morton and M. Stynes, An analysis of the cell vertex method, Mathematical Modelling and Numerical Analysis, 28 (1994), 699-724. 95h:65072 MortSu K. W. Morton and E. Suli, Finite volume methods and their analysis, IMA Journal of Numerical Analysis, 11 (1991), 241--260. 93e:65145 Ni82 R. H. Ni, A multiple grid method for solving the Euler equations, AIAA J. 20 (1982), 1565--1571. OR L.A. Oganesian and L.A. Ruhovec, Variational-difference methods for the solution of elliptic equations, Publ. of the Armenian Academy of Sciences, Yerevan, 1979. (In Russian). Preissmann A. Preissmann, Propagation des intumescences dans les canaux et rivieras, Paper presented at the First Congress of the French Association for Computation, held at Grenoble, France, 1961. RST H. G. Roos, M. Stynes and L. Tobiska, Numerical Methods for Singularly Perturbed Differential Equations , Springer Computational Mathematics, 24 , Springer-Verlag, 1996. Suli2 E. Suli, Finite volume methods on distorted partitions: stability, accuracy, adaptivity, Technical Report NA89 6, Oxford University Computing Laboratory, 1989. Suli1 E. Suli, The accuracy of finite volume methods on distorted partitions, Mathematics of Finite Elements and Applications VII (J.R. Whiteman, ed.) Academic Press, 1991, 253--260. 92i:65171 Suli E. Suli, The accuracy of cell vertex finite volume methods on quadrilateral meshes, Mathematics of Computation, 59 (1992), 359--382. 93a:65158 Thomas H. A. Thomas, Hydraulics of Flood Movements in Rivers, Carnegie Institute of Technology, Pittsburgh, Pennsylvania, 1937. Wend B. Wendroff, On centered difference equations for hyperbolic systems, J. Soc. Indust. Appl. Math. 8 (1960), 549--555. 22:7259

1.
P. Balland and E. Süli, Analysis of the cell vertex finite volume method for hyperbolic equations with variable coefficients, SIAM J. Numer. Anal. 34, No. 3, June 1997.

2.
P.I. Crumpton, J.A. Mackenzie and K.W. Morton, Cell vertex algorithms for the compressible Navier-Stokes equations, Journal of Computational Physics, 109 (1993), 1-15.MR 94e:76081

3.
A. Jameson, Acceleration of transonic potential flow calculations on arbitrary meshes by the multiple grid method, AIAA Paper 79, p. 1458, 1979.

4.
H. Keller, A new finite difference scheme for parabolic problems, In: Numerical Solution of Partial Differential Equations II, SYNSPADE 1970 (Ed., B. Hubbard,) Academic Press, 1971, 327-350. MR 43:2866
5.
K. W. Morton, Numerical Solution of Convection-Diffusion Problems, Applied Mathematics and Mathematical Computation, 12, Chapman and Hall, London, 1996.

6.
K.W. Morton, P.I. Crumpton and J.A. Mackenzie, Cell vertex methods for inviscid and viscous flows, Computers Fluids, 22 (1993), 91-102.

7.
J. A. Mackenzie and K. W. Morton, Finite volume solutions of convection-diffusion test problems, Mathematics of Computation, 60 (1992), 189-220. MR 93d:76065
8.
K. W. Morton and M. F. Paisley, A finite volume scheme with shock fitting for the steady Euler equations, Journal of Computational Physics, 80 (1989), 168-203.

9.
K. W. Morton and M. Stynes, An analysis of the cell vertex method, Mathematical Modelling and Numerical Analysis, 28 (1994), 699-724. MR 95h:65072
10.
K. W. Morton and E. Süli, Finite volume methods and their analysis, IMA Journal of Numerical Analysis, 11 (1991), 241-260. MR 93e:65145
11.
R. H. Ni, A multiple grid method for solving the Euler equations, AIAA J. 20 (1982), 1565-1571.

12.
L.A. Oganesian and L.A. Ruhovec, Variational-difference methods for the solution of elliptic equations, Publ. of the Armenian Academy of Sciences, Yerevan, 1979. (In Russian).

13.
A. Preissmann, Propagation des intumescences dans les canaux et rivieras, Paper presented at the First Congress of the French Association for Computation, held at Grenoble, France, 1961.

14.
H. G. Roos, M. Stynes and L. Tobiska, Numerical Methods for Singularly Perturbed Differential Equations, Springer Computational Mathematics, 24, Springer-Verlag, 1996.

15.
E. Süli, Finite volume methods on distorted partitions: stability, accuracy, adaptivity, Technical Report NA89/6, Oxford University Computing Laboratory, 1989.

16.
E. Süli, The accuracy of finite volume methods on distorted partitions, Mathematics of Finite Elements and Applications VII (J.R. Whiteman, ed.) Academic Press, 1991, 253-260. MR 92i:65171
17.
E. Süli, The accuracy of cell vertex finite volume methods on quadrilateral meshes, Mathematics of Computation, 59 (1992), 359-382. MR 93a:65158

18.
H. A. Thomas, Hydraulics of Flood Movements in Rivers, Carnegie Institute of Technology, Pittsburgh, Pennsylvania, 1937.

19.
B. Wendroff, On centered difference equations for hyperbolic systems, J. Soc. Indust. Appl. Math. 8 (1960), 549-555. MR 22:7259
]]> 1997 American Mathematical Society Mathematics of Computation of the American Mathematical Society Math. Comp. mcom 66 220 19971001 November 22, 1994 January 26, 1996 and June 12, 1996 Finite volume methods stability error analysis 1389 1389-1406 18 S0025-5718-97-00886-7 10.1090/S0025-5718-97-00886-7 0025-5718 1088-6842 English 65N99 65L10 76M25 1991 http://www.ams.org/jourcgi/jour-getitem?pii=S0025-5718-97-00886-7 Introduction equation 0 A finite volume formulation is the preferred technique for discretising systems of partial differential equations where conservation is the most important property to be modelled, compressible gas dynamics being the prime example--see Jameson Jameson79 and a large subsequent literature. Of the various formulations that are possible, the cell-vertex scheme is often advocated for its compactness and its accuracy for first-order equations on distorted meshes (see Morton and Paisley MortPais89 and Suli Suli ); moreover, Morton et al. MCM and Crumpton et al. CMM have also demonstrated the effectiveness of the cell-vertex scheme for the compressible Navier-Stokes equations (see also Mackenzie and Morton MorMac92 ). Numerous practical computations have, indeed, shown this discretisation to be of very general utility, with recent extensions to unstructured three-dimensional meshes on general domains, and applicable to the very high aspect ratio meshes encountered with high Reynolds number, turbulent flows. However, the resulting system of discrete equations is difficult to solve and its accuracy is hard to analyse. Some of these issues can be studied with simple model problems on rectangular meshes. In the earlier form of the method, for purely hyperbolic problems, when it was referred to as the finite difference box scheme of Thomas Thomas , Preissmann Preissmann , Wendroff Wend , Keller Keller and others, the equations were always solved by marching in a special coordinate direction. This is not possible with the equations for steady inviscid transonic flow and various alternatives have been developed, based on the work of Ni Ni82 ; marching techniques are even less appropriate when second-order viscous terms are present, but Ni's techniques are still effective (see CMM and MorMac92 ). The present paper is one in a series devoted to the analysis of the resulting cell-vertex finite volume schemes. Scalar convection-dominated diffusion problems, with general convective velocity fields, show both the remarkable approximation properties of cell-vertex methods and highlight the challenge posed by their analysis. Mackenzie and Morton MorMac92 presented a two-dimensional cell-vertex finite volume scheme which reduces to a non-standard twelve-point difference scheme on a uniform rectangular mesh; they demonstrated its accuracy in some well-known model problems and analysed its one-dimensional analogue. Morton and Stynes MortSty adopted an alternative approach to the one-dimensional problem and analysed the case of pure convection in two dimensions, making use of the techniques of Suli Suli2 , Suli1 , Suli . The present paper is developed from this approach. The key ideas in the analysis are, firstly, to treat the finite volume scheme as a Petrov-Galerkin finite element method with a trial space U h consisting of continuous piecewise bilinear functions, a test space M h of piecewise constant functions, and an associated discrete bilinear form B h(,) ; secondly, a mapping E from U h to M h is constructed such that B h(v, E v) C v 2 for all v in U h , where C is a fixed positive constant and is a suitable norm on U h , so that B h is coercive over U h M h . The bulk of the effort is in the construction of this mapping. We consider the model convection-diffusion problem eqnarray (-u a u) f on , 1.1 u 0 on , 1.2 eqnarray where (0,1)(0,1) R 2 , is a small positive parameter, and a (a 1, a 2) is a variable convective velocity, a (C 1()) 2 . We assume that there exist positive constants 1 and 2 such that a i i on , i 1,2 , and that fL 2() . The well-posedness of this problem can be demonstrated by multiplying ( 1.2 ) by g u , where g is a bounded non-negative weight-function constructed so that - 2 g - a g ( a )g 0 in . Our stability analysis of the cell-vertex finite volume approximation of ( 1.1 ), ( 1.2 ) makes use of a similar construction, and also requires that the discretisation takes particular forms at inflow and outflow boundaries. To clarify these points we have assumed that both components of a are strictly positive; then the construction of g is simplified and the inflow boundaries for the reduced problem (corresponding to 0 ) are at x 0 and y 0 , with the outflow boundaries at x 1 and y 1 . In any case, the presence of the zero Dirichlet boundary condition along the outflow boundary of the reduced problem implies that, for 1 , the analytical solution contains a thin boundary layer in the neighbourhood of this part of . Wide-ranging comparisons of finite difference, finite element and finite volume methods for this problem are given in Morch and RST . It is shown in Morch that the distinctive feature of the cell-vertex scheme for convection-diffusion problems is its uniform effectiveness as tends to 0 , without the use of any adjustable parameters; indeed, as highlighted below, this is also a distinctive feature of the stability analysis. On the other hand, a dominant difficulty arises from the presence of the spurious chequer-board mode, which of course does not appear in one-dimensional problems. In nearly all other methods that suffer from chequer-board oscillations, the spurious mode is damped out by the diffusion term approximation, but not in the cell-vertex scheme where the diffusion term is transparent to the chequer-board mode: in practical computations with the cell-vertex scheme chequer-board oscillations are controlled by a fourth-order artificial dissipation term. However, since the inclusion of such a term complicates the analysis even further, in the present paper we make an assumption on the convective velocity which reduces the generation of the chequer-board mode and so simplifies the argument. In Section sec:2 we state the cell-vertex approximation of the convection-diffusion equation ( 1.1 ) using the terminology of Petrov-Galerkin finite element methods. In Section sec:3 we prove that the cell-vertex scheme is stable in a mesh-dependent L 2 -norm, uniformly as tends to zero. In doing so, we introduce the technical assumption on the velocity field a (see ( l3.1 )) which takes the form of a discrete analogue of y a 1 x a 2 0 . A general class of vector functions a satisfying condition ( l3.1 ) is given by a(x,y) (a 1(x,y), a 2(x,y)), with a 1(x,y) A 1(x) By,a 2(x,y) A 2(y)-Bx, where A 1 and A 2 are arbitrary functions of x and y , respectively, and B is a real constant. This gives quite a large class of velocity fields which the analysis can handle. However, we believe that condition ( l3.1 ) could be overcome by either a slight change in the scheme or a more sophisticated analysis: indeed, in the case of variable-coefficient linear advection, corresponding to 0 , the analysis of Balland and Suli BS establishes the stability of the cell-vertex scheme in the absence of hypothesis ( l3.1 ). Unfortunately, the argument in BS is difficult to extend to the case of 0 . The stability of the scheme is a straightforward consequence of the discrete G rding inequality stated in Theorem t3.1 . Second-order convergence in a mesh-dependent L 2 -norm is then deduced from a superconvergence result of Balland and Suli (see Proposition P2 in BS ); the resulting error estimate is stated in Theorem t3.3 . Throughout the paper, C (sometimes subscripted) will denote a generic positive constant, independent of and of the mesh-size, and may take different values at different occurrences. We denote by H s() and H s() the norm and the semi-norm of the hilbertian Sobolev space H s() of index s , and by L p() the norm of the Lebesgue space L p() , for 1p . The cell-vertex discretisation sec:2 equation 0 Consider the uniform square mesh (x i,y j) ,: , x i i h, , , ,y j j h; , , ,i, j 0,...,N of step-size h 1 N , where N is an integer, N3 . The approximate solution U will be assumed to be continuous and piecewise bilinear on , that is, bilinear on each cell K ij (x i-1 , x i) (y j-1 , y j). Following the usual route, we construct the cell-vertex finite volume approximation of problem ( 1.1 ), ( 1.2 ) by integrating ( 1.1 ) over each cell (except for those cells that lie adjacent to the part of the boundary of which is the outflow boundary for the reduced problem corresponding to 0 ) and using Gauss' Theorem to convert integrals over cells into integrals over cell boundaries; we note that the outflow boundary for the reduced problem is (x,y) ,: , a (x,y) n (x,y) 0 , where n (x,y) denotes the unit outward normal to at (x,y) . An approximation of the contour integrals is needed to proceed further: we use the trapezium rule to evaluate integrals of (a u -u) , and approximate u by finite differences of u . Motivated by this approximate equality satisfied by the exact solution, we define the cell-vertex approximation of u as a continuous piecewise bilinear function U that satisfies the same relation as u but with approximate equality replaced by the equality sign. The equations resulting from this construction are supplemented with a zero Dirichlet boundary condition. In order to give a precise definition of the cell-vertex finite volume scheme, we shall employ the terminology of Petrov-Galerkin finite element methods. Thus, we let denote, for a mesh of size h , the linear space of all continuous piecewise bilinear functions that vanish on , and let M h denote the linear space of piecewise constant functions on the mesh which vanish on those K ij for which i N or j N . Let I h : (H 0 1() C()) 2 () 2 be the interpolation projector onto () 2 . The desired discretisation of the convection term is obtained by defining the bilinear form B c : M h R by equation B c(w, p) ( I h(aw), p), 2.1 equation where (, ) is the inner product in L 2() . It is easy to see that the use of this bilinear form is equivalent to applying Gauss' Theorem followed by the use of the trapezium rule. Indeed, for vC() let v ij denote v(x i,y j) , and for q M h let q ij denote the value of q on K ij ; then, by choosing p in ( 2.1 ) as the characteristic function ij of the cell K ij , we have that eqnarray B c(w, ij ) 2 (a 1w) (a 1w)-(a 1w)- (a 1w) 2 (a 2w) (a 2w)-(a 2w)-(a 2w) h (a 1w) h (a 2w), 2.2 eqnarray where we have employed the finite difference operators eqnarray v v- v, v v- v, v (v v) 2, v (v v) 2. eqnarray We use the methods of Mackenzie and Morton MorMac92 to discretise the diffusion term in ( 1.1 ), together with a simple second-order boundary condition on the inflow boundary. For this purpose we consider the bilinear form B d : M h defined by equation B d(w,p) -h p ij (w x)- (w x) (w y)- (w y) , 2.3 equation where, for j 1, , N-1 , we set equation (w x) array ll h -1 (w i 1,j - w), if i 1, , N-1 , h -1 (2w 1j - 12w 2j ), if i 0 , array . 2.4 equation with (w y) defined analogously. Now the cell-vertex finite volume approximation of ( 1.1 ), ( 1.2 ) is defined as follows: find U such that equation B h(U, p) B d(U,p) B c(U,p) (f,p) p M h. 2.5 equation This is a system of (N-1) 2 linear equations in the (N-1) 2 unknowns U , the nodal values of the continuous piecewise bilinear function U , where i, j 1, , N-1 . In the next section we show that B h is coercive over M h , and therefore U is well-defined. Stability and convergence sec:3 equation 0 The crucial step in the analysis of the cell-vertex scheme is to prove stability via a discrete G rding inequality that guarantees coercivity in a generalised sense. Let P h : L 2() M h be the orthogonal projector onto M h . It is easily seen that (P hw) ij x yw ij for any w in . We shall consider B h(w, GP hw P h I h(aw)), where G and are suitable elements in M h chosen so as to achieve the desired coercivity. We analyse this expression in the following four lemmas. Let h (0, x N-1 ) (0, y N-1 ) . Then, as in Suli Suli2 , Suli1 , Suli , Morton and Suli MortSu , and Morton and Stynes MortSty , we define the l 2( h) -seminorm v l 2( h) of a locally integrable function v by v l 2( h) K ij h h 2 1 h 2 K ij v , dx ,dy , 2 1 2 . We note that this seminorm is a norm on the linear space . lemma l3.1 Assume that there exist positive constants 1 and 2 such that a i i , i 1,2 , and that equation (a 1) (a 2) 0 5.1 equation for all i and j . There exist G M h and positive constants C i , i 1, 2, 3, 4 , such that C 1 G ij C 2 , G ij - G i 1,j C 3h and G ij - G i,j 1 C 4h for all i and j , and eqnarray B c(w, G P h w) 2 C 2 w 2 j 1 N-1 h (18 1 G N-1,j - C 2h) ( y w N-1,j ) 2 i 1 N-1 h (18 2 G i,N-1 - C 2h) ( x w i,N-1 ) 2, eqnarray for all w and for all hh 0( a ) , where h 0( a ) depends only on a C 2( ) . lemma proof From ( 2.2 ) and the definition of M h we have that equation B c(w, G P h w) h G ij (w) (a 1w) (a 2w) . 5.2 equation Using the elementary identities eqnarray (bc) (b)(c) (b)(c), (bc) (b)(c) 14(b)(c) eqnarray and their , analogues, we can rewrite ( 5.2 ) as eqnarray B c(w, G P h w) h G ij (w) 2 (a 1) (a 2) 14h G ij (w)(w) (a 1) (a 2) h G ij (w)(w) (a 1) 14(a 2) h G ij (w)(w) 14(a 1) (a 2) S 1 S 2 S 3 S 4. 5.3 eqnarray We define G(x,y) -( 1 x i-1 2 y j-1 ) , for (x,y) K ij , where l , l 1,2 , are positive constants which will be chosen appropriately in the course of the proof. First we bound S 1 from below. Observing that equation (w) 2 12 (w) 2 (w) 2 , 5.7 equation it follows that eqnarray S 1 - 12 h 2 G ij (w) 2 A ij -12 j 1 N-2 h 2 G i,j 1 (w) 2 A i,j 1 , eqnarray with a similar bound in terms of ( y w ij ) 2 , where equation A ij 1h( x y(a 1) ij x y (a 2) ij ). equation Noting that G ij G i,j 1 and separating out the term with j N-1 from the first double summation, eqnarray S 1 - 12 j 1 N-2 h 2 G ij (w) 2 ( A ij A i,j 1 ) -12 h 2 G i,N-1 (w i,N-1 ) 2 A i,N-1 . eqnarray Now (b)(b) (1 2)b 2 ; we use this identity and sum by parts to get eqnarray S 3 12 i 1 N-2 (w) 2 (G ij B ij -G i 1,j B i 1,j ) 12 (w N-1,j ) 2 G N-1,j B N-1,j , 5.4 eqnarray where B ij h ((a 1) 14(a 2)). Let us write G ij B ij - G i 1,j B i 1,j (G ij - G i 1,j )B i 1,j G ij (B ij -B i 1,j ). Recalling the definition of G ij , it follows that G ij -G i 1,j 12 1h G ij , provided h 1 1 . In addition, since a 1 , a 2C 1() , B ij h(a 1) ij O(h 2) h (a 1) i-1,j O(h 2). Thus, for 0 hh 0 , where h 0 h 0(a) , we have B ij 12h 1. Similarly, for 0 hh 0 , where h 0 h 0(a) (with a possible adjustment of the previous h 0 ), B ij -B i 1,j 2h 2 a L () . Consequently, G ij B ij -G i 1,j B i 1,j h 2G ij (14 1 1 -2 a L () ). Returning to S 3 , we deduce that eqnarray S 3 12 i 1 N-2 j 1 N-1 h 2G ij ( y w ij ) 2 (14 1 1 - 2 a L () ) 14 j 1 N-1 h G N-1,j ( y w N-1,j ) 2 1. eqnarray Analogously, eqnarray S 4 12 i 1 N-1 j 1 N-2 h 2G ij ( x w ij ) 2 (14 2 2 - 2 a L () ) 14 i 1 N-1 h G i,N-1 ( x w i,N-1 ) 2 2. eqnarray Now combining the lower bounds for S 1 and S 4 we obtain eqnarray 12S 1 S 4 i 1 N-1 j 1 N-2 h 2G ij ( x w ij ) 2 (18 2 2 - a L () -14 A ij A i,j 1 ) 14 i 1 N-1 h G i,N-1 ( x w i,N-1 ) 2 ( 2 - h A i,N-1 ). eqnarray Noting that A i,j(1) 2 a L () for 0 hh 0 , where h 0 h 0( a ) (with a possible adjustment of the previous h 0 ), it follows that 2 - h A i,N-1 12 2. Choosing 2 such that 2 8 2 (1 2 a L () ), it follows that for 0 hh 0 , where h 0 depends only on a , 12S 1 S 4 i 1 N-1 j 1 N-2 h 2G ij ( x w ij ) 2 18 2 i 1 N-1 h G i,N-1 ( x w i,N-1 ) 2. Similarly, choosing 1 such that 1 8 1 (1 2 a L () ) and using the alternative bound for S 1 , we have that 12S 1 S 3 i 1 N-2 j 1 N-1 h 2 G ij ( y w ij ) 2 18 1 j 1 N-1 h G N-1,j ( y w N-1,j ) 2. Finally, eqnarray S 1 S 3 S 4 i 1 N-2 j 1 N-1 h 2 G ij ( y w ij ) 2 i 1 N-1 j 1 N-2 h 2G ij ( x w ij ) 2 18 1 j 1 N-1 h G N-1,j ( y w N-1,j ) 2 18 2 i 1 N-1 h G i,N-1 ( x w i,N-1 ) 2, eqnarray provided hh 0(a) , and i , i 1,2 , are chosen as indicated above. Inserting this lower bound into ( 5.3 ) and recalling that due to ( 5.1 ) the term S 2 0 , we deduce that equation split -1.5pc B c(w, G P h w)C 2 ( i 1 N-2 j 1 N-1 h 2 ( y w ij ) 2 i 1 N-1 j 1 N-2 h 2 ( x w ij ) 2) -1.5pc 18( 1 j 1 N-1 hG N-1,j ( y w N-1,j ) 2 2 i 1 N-1 h G i,N-1 ( x w i,N-1 ) 2 ) -1.5pc in10 split equation for all w and for all h h 0( a ) . To complete the proof of the lemma we bound from below the right-hand side of this inequality in terms of w l 2( h) . This is easily accomplished by defining w ij 1 h 2 K ij w ,dx ,dy, and noting that, for w , w 2 l 2( h) i 1 N-1 j 1 N-1 h 2 (w ij ) 2, w ij 12( x w ij x w i,j-1 ), and w ij 12( y w ij y w i-1,j ). Since (w ij ) 2 12 ( x w ij ) 2 12( x w i,j-1 ) 2, and w 0 on , it follows that C 2 i 1 N-1 j 1 N-1 h 2 w ij 2 C 2 i 1 N-1 j 1 N-2 h 2 ( x w ij ) 2 C 2h i 1 N-1 h ( x w i,N-1 ) 2. Similarly, C 2 i 1 N-1 j 1 N-1 h 2 w ij 2 C 2 i 1 N-2 j 1 N-1 h 2 ( y w ij ) 2 C 2h j 1 N-1 h ( y w N-1,j ) 2. Substituting the sum of these two inequalities into ( in10 ), we deduce the desired coercivity of the bilinear form B c(,) for all w and for all h h 0( a ) . proof We note that condition ( 5.1 ) was necessary in order to remove the term S 2 that contained the second-difference x y ; this term cannot be absorbed into any of the positive terms in the lower bound on B c(w,GP hw) . lemma l3.2 For all w and all M h , 0 , B c(w, P h I h(a w)) 1 2 I h(a w) 2. lemma proof This is immediate from ( 2.1 ). proof lemma l3.3 Assume that there exist positive constants C 2 and C 5 such that G ij C 2 , G ij - G i-1,j C 5 h , and G ij - G i,j-1 C 5 h for all i and j . Then there exist positive constants C 6 C 6(C 2,C 5) and h 1 h 1(C 2,C 5) , such that eqnarray B d(w, GP hw) 18C 2 i 1 N h 2 ((w x)) 2 . . j 1 N h 2 ((w y)) 2 - C 6 w 2 - 8h i 1 N-1 hG i,N-1 xw i,N-1 2 j 1 N-1 hG N-1,j yw N-1,i 2 eqnarray for all w and all h h 1 . lemma proof We give details only for the terms, postponing the analogous contribution from the terms of ( 2.3 ) until later in the proof. Thus we write, for any w , B d(w, GP hw) -h G ij (w) (w x)- (w x) (w y terms ) equation h i 2 N-1 (w x) G ij w- G i-1,j w . 5.9 equation - (w x) N-1,j G N-1,j w N-1,j .(w x) 0,j G 1,j w 1,j i 2 N-1 (w y terms ). Now for 1iN we have that G ij w- G i-1,j w h G ij (w x) (G ij - G i-1,j ) w. Therefore, using G ij - G i-1,j C 5 h together with the arithmetic-geometric mean inequality, we get eqnarray (w x) i-1,j (G ij w- G i-1,j w) h G ij ((w x) i-1,j ) 2 - C 5 (w x) i-1,j , , x y w i-1,j 12h G ij ((w x) i-1,j ) 2 - C 5 2 (G ij ) -1 ( x y w i-1,j ) 2 . 5.10 eqnarray On the other hand, eqnarray - (w x) N-1,j , , w N-1,j h ((w x) N-1,j ) 2 -(w x) N-1,j , ,w N,j 2 ((w x) N-1,j ) 2 - 1 8h (w N-1,j ) 2, eqnarray and therefore eqnarray - (w x) N-1,j G N-1,j , , w N-1,j 2 G N-1,j ((w x) N-1,j ) 2 - 1 8h G N-1,j (w N-1,j ) 2. 5.11 eqnarray Analogously, since (w x) 0,j (w x) 1,j (4 h) x y w 1,j , it follows that eqnarray (w x) 0,j , , w 1,j 4((w x) 0,j ) 2 4 (w x) 0,j (w x) 1,j 8((w x) 0,j ) 2 - 8((w x) 1,j ) 2, eqnarray and therefore equation (w x) 0,j G 1,j , , w 1,j 8G 1,j ((w x) 0,j ) 2 - 8G 1,j ((w x) 1,j ) 2. 5.12 equation Substituting ( 5.10 )--( 5.12 ) into ( 5.9 ), absorbing the last term of ( 5.12 ) into the corresponding term of ( 5.10 ), and noting that G ij C 2 , we deduce that eqnarray B d(w, GP hw) 18C 2 i 1 N h 2 (w x) i-1,j 2 j 1 N h 2 (w y) i,j-1 2 -12C 6 j 1 N-1 i 2 N-1 h 2 w i-1,j 2 i 1 N-1 j 2 N-1 h 2 w i,j-1 2 - 8h i 1 N-1 h G i,N-1 w i,N-1 2 j 1 N-1 h G N-1,j y w N-1,j 2 eqnarray with C 6 C 5 2 C 2 , where we have assumed that h is sufficiently small, namely h h 1(C 2,C 5) . Recalling the definition of l 2( h) , we obtain the desired result. proof We note that with G ij -( 1 x i-1 2 y j-1 ) and 1 and 2 chosen as in the proof of Lemma l3.1 all hypotheses on G in Lemma l3.3 are satisfied. lemma l3.4 For all w and all M h , 0 , eqnarray B d(w, P h I h(a w)) ( 2) i 1 Nh ( i-1,j ij ) ((w x)) 2 , j 1 N h ( i,j-1 ij )((w y)) 2 2 h ij (( P h I h(a w)) ij ) 2 , eqnarray where we set 0j i0 0 . lemma proof As in the proof of Lemma l3.3 , we write out the details only for the terms. The Cauchy-Schwarz inequality gives eqnarray B d(w, P h I h(a w)) ij h (P h I h(a w)) ij ( w x)- ( w x) (w y terms ) ij h ( w x)- ( w x) 2 1 2 ij h ((P h I h(a w)) ij ) 2 1 2 (w y terms ) ( 2) ij h (( w x)) 2 (( w x)) 2 ( 2) ij h ((P h I h(a w)) ij ) 2 (w y terms ) ( 2) i 1 N h ( i-1,j ij ) (( w x)) 2 ( 2) ij h ((P h I h(a w)) ij ) 2 (w y terms ). eqnarray Including the w y terms, we obtain the desired result. proof We now combine these four lemmas to reach our coercivity bound. theorem t3.1 Assume that there exist positive constants 1 and 2 such that a i i , i 1,2 , and that (a 1) (a 2) 0 for all i and j . Choose G M h such that C 1 GC 2 0 , G ij - G i 1,j C 3h , G ij - G i,j 1 C 4h , G ij - G i-1,j C 5h and G ij - G i,j-1 C 5h for all i and j . Let M h be defined as follows: ij array ll C 2 82 h, if h 2 2 , 0, otherwise, array . with the convention that 0j i0 0 . Then, for all h(h 0( a ), h 1(C 2,C 5)) and all such that equation star i h (1- 8h i ) -1 ,i 1,2, equation we have that equation B h(w, GP hw P h I h(a w)) C 2 w 2 12 1 2 I h(a w) 2 equation for all w . Here h 0( a ) and h 1(C 2,C 5) are as in Lemmas l3.1 and l3.3 , respectively. theorem We note that a function G satisfying the conditions of Theorem t3.1 has been constructed in Lemma l3.1 . The hypothesis ( star ) requires the mesh Peclet number to be greater than or equal to 1 Ch ; this condition is automatically satisfied for the convection-dominated diffusion equations considered here. proof Adding the results of the previous lemmas, we obtain eqnarray B h(w, GP hw P h I h(a w)) (2C 2- C 6) w 2 1 2 I h(a w) 2 - 2 2 h ij (( P h I h(a w)) ij ) 2 i 1 Nh 18h C 2 - 1 2 ( i-1,j ij ) ((w x)) 2 j 1 N h 18h C 2 - 1 2 ( i,j-1 ij ) ((w y)) 2 j 1 N-1 h (18( 1 - h) G N-1,j - C 2h ) ( y w N-1,j ) 2 i 1 N-1 h (18( 2 - h) G i,N-1 - C 2h ) ( x w i,N-1 ) 2. 5.14 eqnarray Recalling our assumed lower bound on i h , it follows that the last two sums are non-negative. In order to deal with the remaining terms, we need so small that 2C 2 - C 6C 2 0 ; since C 6 C 2 5 C 2 , this can be achieved by supposing that (C 2 C 5) 2 . Next, we claim that 2 2 h ij 12 h 2 ij for each i and j . For if ij 0 , the inequality is trivial. If ij 0 , then h (2 2 ) by hypothesis, as required. Finally, 1 2 ( i-1,j ij ) 18 C 2 h, and similarly, 1 2 ( i,j-1 ij ) 18C 2 h. Using the above inequalities in ( 5.14 ), the result follows. proof We can now derive a bound on u-U . theorem t3.2 Suppose that the hypotheses of Theorem t3.1 hold. Then, for all sufficiently small and h , such as in ( star ) , eqnarray u-U 1 2 I h(a (u-U)) C h 2 1h (u x I)- 1h y j-1 y j u x(x i,y) , dy -(u x I) 1h y j-1 y j u x(x i-1 ,y) , dy 1h (u y I)- 1h x i-1 x i u y(x,y j) , dx -(u y I) 1h x i-1 x i u y(x,y j-1 ) , dx 2 1 2 C (I h(a u) - au) u-u I , eqnarray where u I is the interpolant of u from . theorem proof For brevity, set GP h(u I - U) P h I h(a (u I-U)) and eqnarray ij 1h (u x I)- 1h y j-1 y j u x(x i,y) , dy -(u x I) 1h y j-1 y j u x(x i-1 ,y) , dy 1h (u y I)- 1h x i-1 x i u y(x,y j) , dx -(u y I) 1h x i-1 x i u y(x,y j-1 ) , dx . eqnarray From Theorem t3.1 we have that eqnarray u I-U 2 1 2 I h(a (u I-U)) 2 C B h(u I - U, ) C B h(u I, ) - C (f, ) C B h(u I, ) - C ((-u a u), ) -Ch 2 ij ij C (I h(a u I) - (au), ) C h 2 ij 2 1 2 (I h(a u I) - au) . eqnarray Noting that I h(a u I) I h(a u) , we deduce that eqnarray u I-U 1 2 I h(a (u-U)) C h 2 ij 2 1 2 C (I h(a u) - au) . eqnarray We combine this with the triangle inequality u-U u-u I u I - U and recall the definition of ij to complete the argument. proof Hence we easily obtain our final bound on the global error. theorem t3.3 Let the hypotheses of Theorem t3.1 hold. Suppose, further, that u H s()H 1 0() , s 2 , and assume that the entries of a belong to C s () , where s denotes the smallest integer greater than or equal to s . Let be as in Theorem t3.1 . There exist positive constants K 1 , K 2 and K 3 such that eqnarray u-U 1 2 I h(a (u-U)) K 1(,u) h r 1-1 K 2(, u) h r 2-1 K 3(u)h r 3 , eqnarray where eqnarray K 1(,u) C 1 u H r 1 1 () C 2 u H r 1 ( h) ,1r 1 (s,3), K 2(,u) C 1 1 2 u H r 2 1 ( h) ,2 r 2 (s,3), K 3(u) C 3 u H r 3 ( h) ,1r 3 2. eqnarray theorem The proof of this theorem relies on the following superconvergence result (see Balland and Suli BS ). proposition P2 Given that s is a real number, s 1 , there exists a constant C , independent of the mesh-size h , such that P h( d - (I h d )) L 2() C h r-1 , d H r() , with 1 r (s,3), for all d (d 1,d 2) in (H s()) 2 . proposition We shall also need the following boundary layer estimate. proposition P3 Let D (0,A)(0,B) , where A,B 0 . Suppose that r is a positive real number, and let D (0,)(0,B) with 0 A . Then u H r(D ) C 1 2 u H r 1 (D) . proposition proof We shall prove the estimate for 0r 1 ; for r 1 , the proof is identical. According to a classical result (see, for example, Chapter 1, Section 4, of Oganesian and Ruhovec OR ): equation in1 u L 2(D ) C 1 2 u H 1(D) . equation Consequently, equation in2 u H 1(D ) C 1 2 u H 2(D) . equation Combining ( in1 ) and ( in2 ) we also have that equation in3 u H 1(D ) C 1 2 u H 2(D) . equation Now inequalities ( in1 ) and ( in3 ) imply that I : u u is a bounded linear operator from H 1(D) to L 2(D ) and from H 2(D) to H 1(D ) . Using the K-method of function space interpolation it follows that I is a bounded linear operator from H r 1 (D) to H r(D ) , for 0 r 1 , and that u H r(D ) C 1 2 u H r 1 (D) . Therefore also, u H r(D ) C 1 2 u H r 1 (D) , 0 r 1. For r 0 and r 1 , the desired inequalities are ( in1 ) and ( in2 ), respectively. proof proof (of Theorem t3.3 ) Let us label the three terms on the right-hand side of the inequality in Theorem t3.2 by T 1 , T 2 and T 3 . We begin by considering T 1 . For the sake of notational simplicity, we define, as in the proof of Theorem t3.2 , eqnarray ij 1h (u x I)- 1h y j-1 y j u x(x i,y) , dy -(u x I) 1h y j-1 y j u x(x i-1 ,y) , dy 1h (u y I)- 1h x i-1 x i u y(x,y j) , dx -(u y I) 1h x i-1 x i u y(x,y j-1 ) , dx ij (1) ij (2) , 1 i, j N-1 . eqnarray For 2 i N-1 and 1jN-1 , a simple application of the Bramble-Hilbert lemma yields ij (1) C h -2 h r-1 u H r(T ij ) , 2 r(s,4), where T ij (x i-2 ,x i 1 )(y j-1 ,y j) . Consequently, for 2 i N-1 and 1jN-1 , ( i 2 N-1 j 1 N-1 h 2 (1) ij 2 ) 1 2 Ch r-2 u H r() , 2 r (s,4). Now let us consider the case when i 1 and 1jN-1 ; recalling the definition of y(u x I) 0,j and appealing to the Bramble-Hilbert lemma, we deduce that eqnarray ( j 1 N-1 h 2 (1) 1j 2 ) 1 2 C ( j 1 N-1 h 2 1 h 4 h 2t-2 u 2 H t((x 0,x 2)(y j-1 ,y j) ) 1 2 Ch t-2 u H t( 0) ,2 t(s,3), eqnarray where 0 (x 0,x 2)(y 0,y N-1 ) . Combining these two bounds we get ( i 1 N-1 j 1 N-1 h 2 ij (1) 2) 1 2 C(h r-2 u H r() h t-2 u H t( 0) ), with 2 r(s,4) and 2 t(t,3) . Exploiting the boundary layer estimate stated in Proposition P2 , u H t( 0) Ch 1 2 u H t 1 ( h) . Thus, ( i 1 N-1 j 1 N-1 h 2 ij (1) 2) 1 2 C(h r-1 u H r 1 () h t-2 h 1 2 u H t 1 ( h) ), with 1 r(s,3) , 2 t(s,3) . Similarly, ( i 1 N-1 j 1 N-1 h 2 ij (2) 2) 1 2 C(h r-1 u H r 1 () h t-2 h 1 2 u H t 1 ( h) ), with 1 r(s,3) , 2 t(s,3) . Thus, recalling from the statement of Theorem t3.1 that Ch , it follows that eqnarray T 1 C 1(h r-1 u H r 1 () 1 2 h t-1 u H t 1 ( h) ), for 1 r(s,3) , 2 t(s,3) . eqnarray Term T 2 is estimated using Proposition P2 with d a u ; we obtain the bound T 2 C 2 h r-1 u H r( h) , 1 r(s,3). Finally, the term T 3 can be bounded using a standard interpolation error estimate to obtain T 3 C 3 h r u H r( h) , 1 r(s,2) 2. Combining the bounds on T 1 , T 2 and T 3 yields the desired error estimate. proof Conclusions In this paper we have been concerned with the stability and the convergence of a cell-vertex finite volume method for linear elliptic convection-dominated diffusion equations in the plane. Using a combination of techniques from the theory of finite difference and finite element methods we proved that the scheme is stable, uniformly as the diffusion coefficient tends to zero, and second-order convergent. In addition to the error bound in the mesh-dependent l 2 -norm, Theorem t3.3 implies that, provided u H 4() H 1 0() , the derivative of the global error in the stream-wise direction is O(h 3 2 ) , as long as h22 . The results presented here may be extended to tensor-product non-uniform meshes. amsplain