Uniformconvergenceanalysisofanupwindfinitedifferenceapproximationsofanhomogenoussingularlyperturbedboundaryvalueproblemusinggridequidistribution.doc

精品论文uniform convergence analysis of an upwind finite difference approximations of an homogenous singularly perturbed boundary value problem using grid equidistributionli-nan sun , an-tao wang?school of mathematics and statistics, lanzhou university, lanzhou 730000, china? corresponding author.e-mail: (li-nan sun), (an-tao wang)abstractwe derive -uniform error estimates for two first-order upwind discretizations of a model inhomogeneous, second-order, singularly perturbed boundary value prob- lem on a non-uniform grid. here, is the small parameter multiplying the highest derivative term. the grid is suggested by the equidistribution of a positive monitor function which is a linear combination of a constant floor and a power of the sec- ond derivative of the solution. our analysis shows how the floor should be chosen to ensure -uniform convergence and indicates the convergence behaviour for such grids.key words: singular perturbation, adaptive grid, rate of convergence, error estimate1 introductionthis paper is concerned with finite difference approximations of the model singularly perturbed boundary value problem:t u(x) := u00(x) a(x)u0(x) = 0, f or x (0, 1), (1.1)u(0) = 0, u(1) = 1,精品论文where 0 1 is a small positive parameter. it is also assumed that a(x) c 10, 1, and there exist constants p, p for x 0, 1 such that130 p a(x) pand |a0(x)| p, (1.2)with solution-adaptive methods, a commonly used technique for determining the grid points is to require that they equidistribute a positive monitor func- tion of the numerical solution over the domain (see, for example, 1,2,11,17). for singular perturbation problems the aim is to cluster automatically grid points within a boundary layer and an obvious choice of adaptivity criterion is therefore the solution gradient. qiu and sloan 20 and mackenzie 6 consider a simple first-order upwind scheme (see section 3.1) applied to the homoge- neous version of (1.1) on a non-uniform grid suggested by equidistributionof the monitor function |u0|1/m , where m 2. their analysis and numericalexperiments show that the resulting approximation is indeed first-order uni-formly convergent.in this paper we propose the use of a monitor function that is a linear combina- tion of a positive constant plus an appropriate power of the second derivative of the solution. as a special case, the monitor function of carey and dinh 5 is reproduced which was shown to minimize the l2 norm of the error be- tween a given function and its piecewise linear interpolant. the constant is chosen so that the resulting grid has an equal distribution of points both in- ternal and external to boundary layers. we establish the uniform convergence of two upwind finite difference discretizations of (1.1) with techniques similar to those used by stynes and roos 9 to investigate finite difference methods on shishkin grids. the analysis is achieved by decomposing the numerical and analytical solutions into smooth and singular components and then analyzing the error in the singular component on two non-overlapping regions of the domain that are naturally suggested by the grid structure.the layout of the rest of this paper is as follows: in the next section we describe the upwind finite difference discretizations and the generation of non-uniform grids by equidistribution. throughout the rest of this paper, c will denote a generic constant that is independent of n and , that can take different values at different places, even in the same argument.2 discretisation and non-uniform grids2.1.finite-difference discretisation of the model problembelow we will briefly introduce our numerical scheme that will be investigated in our work. letn = xi |0 = x0 x1 x2 . . . 0, bi 0, ci 0, and ai = bi + ci , f or 1 i n 1.2.2. grid equidistributiona monitor function m(x) is an arbitrary nonnegative function defined on . a mesh xi is said to equidistribute m () ifz xixi1m (x)dx =1 z 1n 0m (x)dx, f or 1 i n 1. (2.3)equditribution can also be thought of as giving rise to a mapping, x = x(), relating a computational coordinate 0, 1 to the physical coordinate x 0, 1, defined byz x()0m (u(s), s)ds = z 1m (u(s), s)ds = (u). (2.4)0the optimal choice of monitor function depends on the problem being solved, the numerical discretization being used, and the norm of the error that is to be minimized. in practice, the monitor function is often based on a simple function of the derivatives of the unknown solution. in this paper, we consider the monitor functionm du 1m (x) = + , m 2, (2.5) dx 精品论文where is a positive constant that is independent of n. the effect of increasing m is to smooth the monitor function, which in turn leads to a smoother dis- tribution of grid nodes. for a truly adaptive algorithm, the monitor function has to be approximated from the numerical solution. for example, a simple discretization of (2.1) results in the set of equationsmi+ 1 (xi+1 xi ) = mi+ 1 (xi xi1 ), f or 1 i n 1, (2.6)2 2where mi+ 1is an approximation to m (u(xi+ 1 ), xi+ 1 ). the coupled set of2 2 2i=1equations (2.1) and (2.6) then has to be solved simultaneously for (ui , xn 1).to make some headway with the analysis of the adaptive system, we willassume that equidistribution is carried out with m being calculated from the exact solution of a constant coefficient approximation of (1.1). that is, we assume that the grid is given by the exact equidistribution of m (u(x), x),whereu00(x) pu0(x) = 0,u(0) = 0,u(1) = 1, (2.7)and a lower bound on a(x). this leads us to consider the mappingp x() p wheree m x() = 1 1(1 e m ) + 1, (2.8) 1 m1 = m mp. (2.9)p1 e this mapping will be a reasonable approximation to the equidistribution of(2.5) as long as a(x) dont vary excessively from p. a non-uniform grid ini=0physical space, xn, corresponds to the evenly distributed nodes. i = i , 0 ni n , in computational space. this identification givespxi p ie m xi = 1 (1 e m ) + . (2.10)nalthough the location of any particular grid point is given by the solution of a scalar nonlinear equation, it is possible to derive some useful properties of the non-uniform grid. a very important insight into the distribution of the mesh points is given by the following lemma. 1lemma 2.1 assume that the non-uniform grid given by (2.10) is generated with = = 1 m1m 1mp. (2.11)pif m1 e 1 p then we haven log(n ) +pme m2 1, (2.12)1x n2 log(n ) x nn 1 + m n log(n )p p .2 e mwe quirep 2mn log(n ) +pn p 2 e m 1 0. (2.14)the inequality (2.14) can be easily to be verified from the (2.12).1to show that x n2 p n2 1 p (2 e m ), (2.15)then we can conclude thatmn p p n log(n ) +p2 e m e m 1, (2.16)that is clearly true since the left hand side of inequality (2.16)m1 n log(n ) +pn p e m 0,2and the right hand side p e m 1 1/p. for singular perturbation problems, = 0 log(n ) and hence we can see that the equidistributed grid is related to the choice 0 = m/p.remark 2.3 as we are mainly interested in solving singularly perturbed prob- lems on adaptive grids, the assumption (2.12) is not a major restriction.throughout the rest of the paper, we will assume that = is given by (2.11) and that (2.12) holds. the next lemma provides an upper bound on the size of the grid cells to the left of the transition point, x = (m/p)log(n ).2lemma 2.4 for i=1,2,., n 1, we havehi mlog p31 +n 2j. (2.17)for the proof of the (2.17) we can reference 3.3 convergence analysis3.1.properties of the exact solution and some useful lemmasthe exact solution of the model problem (1.1) is u(x)=g(x)/g(1), whereg(x) =z xexp 1 z ta(s)dsdt.0 0for the following analysis we require bounds on u(x) and its derivatives.lemma 3.1 given the assumations (1.2), the solution u(x) of (1.1) satisfies the following inequalities: 0 u(x) 1, and| u(k) (x) | ck k eax/ , f or k = 1, 2, 3, (3.1)where x 0, 1, and ck are constants that are independent of .proof. see qiu and sloan (1996).this lemma will be used to bound the truncation error in the next section. an easily derived observation about u(x) is that 0 u0(y) x. therefore, the solution is always monotonically increasing.lemma 3.2 the system t n un = f n , with un and un specified, has a uniqueii0 nsolution. if t n un t n vn , 1 i n 1, and if un vn , un vn , theniiunn0 0 nni vi , 1 i n 1.proof. it is easy to verify that the matrix associated with t n is an irreduciblem-matrix, and so has a positive inverse. hence the result follows.when the conditions of lemma 3.2 are satisfied, we say that vn is a barrier function for un .ilemma 3.3 let zn= 1 + xi , for 0 i n . then there exists a barriericonstant c such that with t n zn cproof. this is an easy computation.for 1 i n 1.from lemma 3.3, it follows that the inverse operator (t n )1 is uniformly bounded independently of n and . this allows us to establish that the rateof convergence of the error is at least equal to that of he truncation error. however, when the truncation error contains inverse powers of we will need the following result.lemma 3.4 define the mesh function sn , such thatisnnyphk 10 = 1, si =1 +k=1 m, i = 1, 2, , n. (3.2)then for i = 1, 2, , n 1, we havet n sn csn , (3.3)for some constant c.proof. see 3 or 6.i max(m/p, hi+1 ) iremark 3.5 the function sn is the piecewise (0,1) p ade approximation ofpxie m . a similar comparison function was used originally by kellogg and tsan10 to analyze methods on uniform grids and more recently by mackenzie 6, qiu and sloan 20, and stynes and roos 9 for analysis on non-uniform grids.3.2.regular solution regionfrom 3 we can have alsolemma 3.6 the grid function sn defined by (3.2) on the grid (2.10) satisfies the boundspxipxiie m sn c e m , f or i = 1, 2, , n 1.then we can get the following lemma.lemma 3.7 for i = 1, 2, , n 1, we havei1 sn ui 1.iproof. we introduce the barrier function w n = 1 sn . it follows from (3.3)it n w n = t n sn 0.since 1 sn = 0 = un , 1 sn 1 = un .0 0 nnthen from lemma 3.2 we conclude that1 sn un .iifrom lemma 3.1 we know the numerical solution is monotonically increasingon an arbitrary grid then 0 un 1, i = 0, 1, 2, , n , hence 1 sn un iii1. so we complete the proof. lemma 3.8 for i = n 1, n , , n , we have2 2cin|u(xi ) un | 1 c e 1 c e, f or i =2 1, , n.using a(x) p, the exact solutionr 1 exp( 1 r t a(s)dtr 1r tu(xi ) = 1 xi 00 exp( 1pt0 a(s)dtexr 1 dtn/21 1 r 1pt0 e dt2pxn/21n nthen 1 c ecm, f or i =c2 1, , n1 n ui 1, 1 n u(xi ) 1.2and hence we have for i= n 1, , n ,cin|u(xi ) un | .3.3.boundary layer regionthe local truncation error at node xi of (2.1) is given byi = t n u(xi ) (t u)(xi ),then it can be expressed ashi = i+ hi+1 1hi+1z xi+1xi(s xi+1 )2u000(s)ds(3.4)1 hiz xixi1(s xi 1 )2u000(s)ds +aihi+1z xi+1xi(s xi+1 )u00(s)ds .精品论文from which we obtain the boundz xi+1z xi+1|i | xi1|u000(s)|ds + pxi1|u00(s)|ds.using the differential equation (1.1)it may be simplified to|i | cz xi+1xi1|u00(s)|ds.(3.5)2lemma 3.9 for i = 1, 2, , n 2, we havec pxi|i | n e m .proof. from (3.5) and lemma 3.1 we havec z xi+1 ps|i | 2xi1e ds p z i+1=2 e mpx()px()e d (using (2.10)i1 p emm + 1c z i+1 px() m1e md i1c pxi1encmpxiphi=e m e m .nwe know from lemma 2.4 we can obtain thatand hence we have finallyphim3 , n 2ic pxi n|i | n e mf or i = 1, 2 2lemma 3.10 for i = 1, 2, , n 2, we have2 2.cin|u(xi ) un | .proof. we first note from lemma 3.6 and lemma 3.9 thatcpxi c n n|i | n e m n sif or i = 1, 2 2 2. (3.6)next we use the fact that the discrete maximum principle still holds when 0,1 is replaced by the interval 0, xn/21. we now apply this principle with the barrier function n which is given byn c n ni = n (1 + si ) f or i = 1, 2 2 2.the relationship between the local truncation error and the nodal error ist n eni = i .using lemma 3.4 and (3.6) we havet n en c n c n n n n ni = i n si n tsi = tif or i = 1, 2 2 2.since en nand en w n, we can conclude that0 0 n 1enn 1n ni if or i = 1, 2 2 2.ithis argument can be repeated with enbeing enand hencenci|en | and this complete the proof.nf or i = 1, 2 2i 2,3.4.the global error boundtheorem 3.11 let u(x) be the exact solution of (1.1) and let ui , 0 i n , be obtained by (2.1) on the grid defined by (2.10). then there exists a constant c, independent of n and , such thati|u(xi ) un | cn , f or i = 0, n.proof. from lemma 3.8 and lemma 3.10, the proof follows immediately.theorem 3.12 let u(x) denote either the piecewise constant or the piecewise linear interpolant of the first-order upwind solution of (1.1) obtained on the grid (2.10). then u(x) satisfies the -uniform estimate| c max u(x) u(x) . x0,1nproof. for the proof we can reference 3 and 6.4 conclusions 1m dx in this paper we consider the monitor function m (x) = + du , where m 2 and is a positive constant that is independent of n, to analyse the model singularly perturbed problem t u(x) := u00(x) a(x)u0(x) = 0, and this is a new attempt. then we have derived the convergence results also at last inour paper. the numerical results are similar to other papers which research this problems, such as 3, 4 and so on , so here we do not give the numerical examples.references1 a.b.white, on selection of equidistributingmeshes for two-point boundary- value problems, siamj. numer. anal. 16 (1979) 472-502.2 c. de boor, good approximation by splines with variable knots ii, in: lecturenotes in mathematics, vol. 363, springer, berlin, 1974, pp. 12-20.3 g. beckett and j.a. mackenzie, convergence analysis of finite difference approximations on equ