PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 67(81) (2000), 145–158

FINITE DIFFERENCE SCHEMES ON NONUNIFORM MESHES FOR PARABOLIC PROBLEMS WITH GENERALIZED SOLUTIONS

Boško S. Jovanović and Peter P. Matus

Communicated by Gradimir Milovanović

Abstract. We investigate the convergence of finite difference schemes for one dimensional heat conduction equation on nonuniform rectangular meshes. For schemes with averaged right hand sides convergence rate estimates consistent with the smoothness of the solution in discrete L_{2} norm are obtained. Possible extensions of obtained results are noted.

Introduction

Nonuniform meshes are often used for approximation of problems with generalized solutions. In this case, the order of local error is usually reduced.

In many papers it is shown that the accuracy of the method can be increased using approximation of the considered differential equation in some non–mesh points (see e.g. [1], [5], [6]). In [15] for one dimensional heat conduction equation on a nonuniform in space variable rectangular mesh finite difference schemes (FDSs) of second order accuracy on x are constructed. The convergence of these schemes in discrete C–norm is proved under some restrictions on the step sizes of the mesh. Analogous results are obtained for hyperbolic problems. In [16] similar results for the Poisson equation are obtained.

Clearly, the employment of strong norms (e.g. C^{k}) in the proofs of convergence involves supplementary restrictions on the smoothness of solutions of boundary value problems, restricting the class of admissible problems. Notice that the first results on the convergence of discrete methods for the problems with solutions from Sobolev spaces were obtained in finite element method theory framework [3]. However, the ways of construction of difference schemes and methods for establishing the convergence rate estimates for the finite difference methods are essentially different from those for finite element methods (see [12], [13]). In particular, so called convergence rate estimates consistent with the smoothness of data are of the major interest [10]. In the case of uniform meshes such estimates are obtained for a large class of boundary value problems (see bibliographies in [9] and [14]). Estimates of this type are usually based on the application of the Bramble–Hilbert lemma [2], [4].

1991 Mathematics Subject Classification. Primary 65M15.

Key words and phrases. Parabolic problem, finite differences, nonuniform mesh, generalized solution, rate of convergence.

Partially supported by Ministry of Science and Technology of Serbia (grant 04M03/C) and Belorussian Fund for Fundamental Fesearch (grant F96–173).

In present paper the convergence of FDSs defined in [15] is proved in discrete L_{2}–norm assuming that the generalized solution of the considered initial boundary value problem (IBVP) belongs to the corresponding Sobolev space. Obtained convergence rate estimates are consistent with the smoothness of data. These estimates are obtained by direct estimation of the truncation error, using the interpolation theory of function spaces. In such a way, application of the Bramble-Hilbert lemma, which usually involves unnecessary restriction on the mesh step sizes is avoided. Contrary to FDSs considered in [15], where the right hand sides of equations are taken in some intermediate non–mesh points, we replace the right hand sides with some averaged values. This is necessary because in the problems with generalized solutions, the right hand sides of equations may be discontinuous functions.

Preliminaries and notations.

Let us consider the first initial–boundary value problem for the heat conduction equation

(1)  \begin{matrix}\frac{∂u}{∂t} = \frac{∂^{2}u}{∂x^{2}} + f(x, t) ,  (x, t) ∈ Q = (0, l) × (0, T) \\ u(x, 0) = u_{0}(x) ,  0 < x < l , \\ u(0, t) = u(l, t) = 0 ,  0 < t < T . \end{matrix}

In the domain Q̄ we define the mesh Q̄_{hτ} = ˆ ω̄ × ω̄_{τ}, where

ˆω̄ = {x = x_{i} = x_{i−1} + h_{i} , i = 1, 2, …, n − 1 , x_{0} = 0 , x_{n} = l} ,  ∑_{i=1}^{n} h_{i} = l ,

is nonuniform mesh on [0, l] and ω̄_{τ} – uniform mesh on [0, T] with the step size τ = T/m. We assume that

(2)  \frac{1}{c_{1}} ≤ \frac{h_{i+1}}{h_{i}} ≤ c_{1} ,

where c_{1} is a positive constant.

Denote

ω̂ = ˆ ω̄ ∩(0, l), ω̂^{+} = ˆ ω̄ ∩(0, l], ω_{τ}^{+} = ω̄_{τ} ∩(0, T], Q_{hτ} = ω̂ ×ω_{τ}^{+}, Q_{hτ}^{0} = ω̂ ×ω̄_{τ} .

In the sequel we shall use the notation

x = x_{i} , x_{±} = x_{i±1} , t = t_{j} = j τ , h = h_{i} , h_{±} = h_{i±1} , ℏ = (h + h_{+})/2 , v = v(x, t) , v_{±} = v(x_{±}, t) , v̂ = v(x, t + τ) , v̌ = v(x, t − τ) .

We introduce finite differences in a standard way (see [12])

v_{x} = (v_{+} − v)/h_{+} ,  vx̄ = (v − v_{−})/h ,  vx̂ = (v_{+} − v)/ℏ ,
v_{t} = (v̂ − v)/τ , vt̄ = (v − v̌)/τ ,

Let us introduce the discrete inner products

(u, v)_{∗} = ∑_{x∈ω̂} u v ℏ , (u, v] = ∑_{x∈ω̂^{+}} u v h ,

and the norms

∥v∥_{L_{2}(ω̂)}^{2} = ∥v∥_{∗}^{2} = (v, v)_{∗} ,  ∥v]|^{2} = (v, v] ,  ∥v∥_{L_{2}(Q_{hτ})}^{2} = τ ∑_{t∈ω_{τ}^{+}} ∥v( · , t)∥_{∗}^{2} .

The following assertion holds true.

Lemma 1. [13] For arbitrary mesh functions v(x) and w(x), defined on ˆ ω̄ which vanish for x = 0, l, the following relations hold

(vx̂, w)_{∗} = −(v, wx̄] ,
(v_{x̄x̂}, w)_{∗} = −(v_{x}, wx̄] .

Let us define the Steklov smoothing operator on variable t

Tt̄f(x, t) = \frac{1}{τ} ∫_{t−τ}^{t} f(x, t′) dt′ ,

and asymmetric Steklov smoothing operators on x (for x ∈ ω̂):

T_{1}f(x, t) = \frac{1}{ℏ} ∫_{x−h/2}^{x+h_{+}/2} f(x′, t) dx′ , T_{2}f(x, t) = \frac{1}{ℏ} ∫_{x_{−}}^{x_{+}} K(x′) f(x′, t) dx′ ,

where

K(x′) = \{ \begin{matrix}1 + \frac{x′−x}{h} , & x′ ∈ (x_{−}, x) \\ 1 − \frac{x′−x}{h_{+}} , & x′ ∈ (x, x_{+}) . \end{matrix}

Notice that in the mesh nodes: Tt̄\frac{∂u}{∂t} = ut̄ and T_{2} \frac{∂^{2}u}{∂x^{2}} = u_{x̄x̂}.

As usual, let W_{2}^{s}(Ω) be the Sobolev space in Ω. Following [11], we also define spaces W_{2}^{s}((0, T); W_{2}^{r}(Ω)) and anisotropic Sobolev spaces in Q: W_{2}^{s, r}(Q) = W_{2}^{0}((0, T); W_{2}^{s}(0, l)) ∩ W_{2}^{r}((0, T); W_{2}^{0}(0, l)).

The following assertion holds true (comp. [11]).

Lemma 2. If a ∈ W_{2}^{σ}(0, 1), 0.5 < σ < 1 and a(0) = 0 , then

( ∫_{0}^{1} ξ^{−2σ} a^{2}(ξ) dξ)^{1/2} ≤ \frac{2 σ + 1}{2 σ − 1} |a|_{W_{2}^{σ}(0, 1)} .

In the sequel we need some results of interpolation theory of function spaces. Let X and Y be two Hilbert spaces, X dense in Y, and continuously imbedded. Following [11], let us introduce interpolation space [X, Y]_{θ}. The following assertions hold true (see [11]).

Lemma 3. For u ∈ X and 0 < θ < 1 the following inequality holds

∥u∥_{[X, Y]_{θ}} ≤ C_{θ} ∥u∥_{X}^{1−θ} ∥u∥_{Y}^{θ} .

Lemma 4. If s_{1}, s_{2}, r_{1}, r_{2} ≥ 0 and 0 < θ < 1 then

[W_{2}^{s_{1}}((0, T); W_{2}^{r_{1}}(0, l)), W_{2}^{s_{2}}((0, T); W_{2}^{r_{2}}(0, l))]_{θ}

= W_{2}^{(1−θ) s_{1}+θ s_{2}}((0, T); W_{2}^{(1−θ) r_{1}+θ r_{2}}(0, l)) .

In the following, by C and C_{i} we shall denote positive generic constants independent of mesh step sizes.

Divergent scheme.

We approximate the problem (1) by implicit FDS

(3)

vt̄ + (\frac{h^{2}}{6} vt̄ ; x̄)x̂ = v_{x̄x̂} + T_{2}Tt̄f in Q_{hτ} ;

v = T_{2}u_{0} − (\frac{h^{2}}{6} u_{0, x̄})x̂ for t = 0 ; v = 0 for x = 0, l .

The FDS (3) is proposed in [15] for problems with smooth solutions. The value of the right hand side is taken in an intermediate point (x̄, t), where x̄ = x+(h_{+}−h)/3. In our case the right hand side may be discontinuous and we must take its averaged value. Notice that FDS (3) is exactly the scheme produced by the finite element method for linear elements (on variable x).

The error z = u − v satisfies the following conditions

(4) zt̄ + (\frac{h^{2}}{6} zt̄ ; x̄)x̂ = z_{x̄x̂} + φ_{x̄x̂} + ψt̄ in Q_{hτ} ;

z = ψ( · , 0) for t = 0 ; z = 0 for x = 0, l ,

where

φ = Tt̄u − u  and  ψ = u − T_{2}u + (\frac{h^{2}}{6} ux̄)x̂ .

To derive the a priori estimate in discrete L_{2}–norm, let us set z = z^{(1)} + z^{(2)} where z^{(1)} and z^{(2)} are the solutions of the following FDSs

(5) z(1) ; t̄ + (\frac{h^{2}}{6} z(1) ; t̄ ; x̄)x̂ = z_{x̄x̂}^{(1)} + φ_{x̄x̂} in Q_{hτ} ;

z^{(1)} = 0 for t = 0 ; z^{(1)} = 0 for x = 0, l ,

and

(6) z(2) ; t̄ + (\frac{h^{2}}{6} z(2) ; t̄ ; x̄)x̂ = z_{x̄x̂}^{(2)} + ψt̄ in Q_{hτ} ;

z^{(2)} = ψ( · , 0) for t = 0 ; z^{(2)} = 0 for x = 0, l .

Let ζ be a mesh function satisfying

−ζ_{x̄x̂} = z^{(1)} + (\frac{h^{2}}{6} z(1) ; x̄)x̂ in Q_{hτ}^{0} ; ζ = 0 for x = 0, l .

Multiplying (5) by ζ and summing over the mesh ω̂, we immediately obtain

(7)  \begin{matrix}\frac{τ}{2} ∥ζx̄t̄]|^{2} + \frac{1}{2 τ} (∥ζx̄]|^{2} − ∥ζ̌x̄]|^{2}) + ∥z^{(1)}∥_{∗}^{2} \\ = \frac{1}{6} ∥h z(1) ; x̄]|^{2} + \frac{1}{6} (h z(1) ; x̄, h φx̄] − (φ, z^{(1)})_{∗} . \end{matrix}

Using the inequality

∥h zx̄]|^{2} = ∑_{x∈ω̂^{+}}(z − z_{−})^{2} h ≤ 4 ∥z∥_{∗}^{2}

and ε–inequality, from (7) we obtain

(8) \frac{τ}{2} ∥ζx̄t̄]|^{2} + \frac{1}{2 τ} (∥ζx̄]|^{2} − ∥ζ̌x̄]|^{2}) + ∥z^{(1)}∥_{∗}^{2}

≤ \frac{2}{3} ∥z^{(1)}∥_{∗}^{2} + \frac{4}{12} (ε ∥z^{(1)}∥_{∗}^{2} + \frac{1}{ε} ∥φ∥_{∗}^{2}) + \frac{1}{2} (ε ∥z^{(1)}∥_{∗}^{2} + \frac{1}{ε} ∥φ∥_{∗}^{2}) .

From (8), summing over the mesh ω_{τ}^{+}, we obtain

(\frac{1}{3} − \frac{5 ε}{6} ) ∥z^{(1)}∥_{L_{2}(Q_{hτ})}^{2} ≤ \frac{5}{6 ε} ∥φ∥_{L_{2}(Q_{hτ})}^{2} ,

wherefrom, for 0 < ε < 2/5 , we obtain the estimate

(9)  ∥z^{(1)}∥_{L_{2}(Q_{hτ})} ≤ C ∥φ∥_{L_{2}(Q_{hτ})} .

150 JOVANOVIĆ AND MATUS

Let us now estimate z^{(2)}. We multiply (6) in scalar way by η, where

−η_{t} = z^{(2)} in Q_{hτ}^{0} ; η = 0 for t = T + τ .

Applying partial summing on t, we obtain

−τ ∑_{t=τ}^{T}(z^{(2)}, η_{t})_{∗} − τ ∑_{t=τ}^{T} ((\frac{h^{2}}{6} z(2) ; x̄)x̂, η_{t})_{∗} − ((\frac{h^{2}}{6} ψx̄( · , 0))x̂, η( · , τ))_{∗}

= τ ∑_{t=τ}^{T}(z_{x̄x̂}^{(2)}, η)_{∗} − τ ∑_{t=τ}^{T}(ψ, η_{t})_{∗} .

Further

(z_{x̄x̂}^{(2)}, η)_{∗} = −(z(2) ; x̄, ηx̄] = (η_{x̄t}, ηx̄] = \frac{1}{2 τ} (∥η̂x̄]|^{2} − ∥ηx̄]|^{2}) − \frac{τ}{2} ∥η_{x̄t}]|^{2}

= \frac{1}{2 τ} (∥η̂x̄]|^{2} − ∥ηx̄]|^{2}) − \frac{τ}{2} ∥z(2) ; x̄]|^{2} ,

((\frac{h^{2}}{6} z(2) ; x̄)x̂, η_{t})_{∗} = −((\frac{h^{2}}{6} z(2) ; x̄)x̂, z^{(2)})_{∗} = \frac{1}{6} ∥h z(2) ; x̄]|^{2} ≤ \frac{2}{3} ∥z^{(2)}∥_{∗}^{2} ,

and

((\frac{h^{2}}{6} ψx̄( · , 0))x̂, η( · , τ))_{∗} = −(\frac{h^{2}}{6} ψx̄( · , 0), ηx̄( · , τ)]

≤ \frac{1}{2} ∥ηx̄( · , τ)]|^{2} + \frac{1}{2} ∥\frac{h^{2}}{6} ψx̄( · , 0)]|^{2} ≤ \frac{1}{2} ∥ηx̄( · , τ)]|^{2} + \frac{h_{max}^{2}}{72} ∥h ψx̄( · , 0)]|^{2}

≤ \frac{1}{2} ∥ηx̄( · , τ)]|^{2} + \frac{h_{max}^{2}}{18} ∥ψ( · , 0)∥_{∗}^{2} .

It follows

τ ∑_{t=τ}^{T} ∥z^{(2)}∥_{∗}^{2} + \frac{1}{2} ∥ηx̄( · , τ)]|^{2} + \frac{τ^{2}}{2} ∑_{t=τ}^{T} ∥z(2) ; x̄]|^{2}

= τ ∑_{t=τ}^{T}(ψ, z^{(2)})_{∗} + \frac{τ}{6} ∑_{t=τ}^{T} ∥h z(2) ; x̄]|^{2} − (\frac{h^{2}}{6} ψx̄( · , 0), ηx̄( · , τ)] (10)

≤ (ε + \frac{2}{3}) τ ∑_{t=0}^{T} ∥z^{(2)}∥_{∗}^{2} + \frac{1}{4 ε} τ ∑_{t=0}^{T} ∥ψ∥_{∗}^{2} + \frac{1}{2} ∥ηx̄( · , τ)]|^{2} + \frac{h_{max}^{2}}{18} ∥ψ( · , 0)∥_{∗}^{2} .

From (10) for 0 < ε < 1/3 it follows

(11)  ∥z^{(2)}∥_{L_{2}(Q_{hτ})} ≤ C [∥ψ∥_{L_{2}(Q_{hτ})} + h_{max} ∥ψ( · , 0)∥_{L_{2}(ω̂)}] .

From (9) and (11) we obtain the desired a priori estimate

(12) ∥z∥_{L_{2}(Q_{hτ})} ≤ C [∥φ∥_{L_{2}(Q_{hτ})} + ∥ψ∥_{L_{2}(Q_{hτ})} + h_{max} ∥ψ( · , 0)∥_{L_{2}(ω̂)}] .

In such a manner, to obtain the convergence rate estimate of FDS (3), we need to estimate the right hand side terms in (12). Let us set

φ = φ_{1} + φ_{2} = T_{1}(Tt̄u − u) + [(Tt̄u − u) − T_{1}(Tt̄u − u)] .

Further

φ_{1}(x, t) = \frac{1}{ℏ} ∫_{x−h/2}^{x+h_{+}/2} [\frac{1}{τ} ∫_{t−τ}^{t} u(x′, t′) dt′ − u(x′, t)] dx′

= \frac{1}{ℏτ} ∫_{x−h/2}^{x+h_{+}/2} ∫_{t−τ}^{t} [u(x′, t′) − u(x′, t)] dt′ dx′ = \frac{1}{ℏτ} ∫_{x−h/2}^{x+h_{+}/2} ∫_{t−τ}^{t} ∫_{t}^{t′} \frac{∂u(x′, t′′)}{∂t} dt′′ dt′ dx′

Estimating integrals in the right hand side by Cauchy–Schwartz inequality, we obtain

|φ_{1}(x, t)| ≤ \frac{τ}{\sqrt{ℏτ}} ∥\frac{∂u}{∂t}∥_{L_{2}(e)} ,  where  e = (x − h/2, x + h_{+}/2) × (t − τ, t) .

Summing over the mesh Q_{hτ}, we obtain:

(13)  ∥φ_{1}∥_{L_{2}(Q_{hτ})} ≤ τ ∥\frac{∂u}{∂t}∥_{L_{2}(Q)} .

To estimate φ_{2} let us set α(t) = T_{1}u − u. For 1/2 < σ < 1 , from lemma 2 follows

|φ_{2}(x, t)| = |α − Tt̄α| = |\frac{1}{τ} ∫_{t−τ}^{t} [α(t) − α(t′)] dt′| ≤

≤ \frac{1}{τ} \{ ∫_{t−τ}^{t} (t − t′)^{−2 σ} [α(t) − α(t′)]^{2} dt′\}^{1/2} \{ ∫_{t−τ}^{t} (t − t′)^{2 σ} dt′\}^{1/2}

≤ \frac{\sqrt{2 σ + 1}}{2 σ − 1} τ^{σ−1/2} (∫_{t−τ}^{t} ∫_{t−τ}^{t} \frac{|α(t′) − α(t′′)|^{2}}{|t′ − t′′|^{1+2 σ}} dt′ dt′′)^{1/2} .

Further

|α(t′) − α(t′′)| = |\frac{1}{ℏ} ∫_{x−h/2}^{x+h_{+}/2} [u(x′, t′) − u(x, t′) − u(x′, t′′) + u(x, t′′)] dx′|

≤ \frac{1}{ℏ} ∫_{x−h/2}^{x+h_{+}/2} |β(x′) − β(x)| dx′ ,

152 JOVANOVIĆ AND MATUS

where

β(x) = u(x, t′) − u(x, t′′) .

Estimating β(x) − β(x′) in an analogous manner, we finally obtain

|φ_{2}(x, t)| ≤ \frac{C ℏ^{ϱ−1/2} τ^{σ−1/2}}{(ϱ − 1/2) (σ − 1/2)} |u|_{(ϱ, σ); e} ,

where |u|_{(ϱ, σ); e}^{2} =

= ∫_{x−h/2}^{x+h_{+}/2} ∫_{x−h/2}^{x+h_{+}/2} ∫_{t−τ}^{t} ∫_{t−τ}^{t} \frac{|u(x′, t′) − u(x′′, t′) − u(x′, t′′) + u(x′′, t′′)|^{2}}{|x′ − x′′|^{1+2ϱ} |t′ − t′′|^{1+2σ}} dt′ dt′′ dx′ dx′′

and 1/2 < ϱ, σ < 1 . Summing over the mesh we obtain

(14)  ∥φ_{2}∥_{L_{2}(Q_{hτ})} ≤ C h_{max}^{ϱ} τ^{σ} |u|_{(ϱ, σ); Q}^{2} .

Let us choose σ ∈ (1/2, 3/4) and set ϱ = 2 (1 − σ). It follows that ϱ + 2 σ = 2 and h_{max}^{ϱ} τ^{σ} ≤ h_{max}^{2} + τ . Using lemma 4, we obtain

[W_{2}^{0}((0, T); W_{2}^{2}(0, l)), W_{2}^{1}((0, T); W_{2}^{0}(0, l))]_{σ} = W_{2}^{σ}((0, T); W_{2}^{2−2 σ}(0, l)) . Finally, accordingly to lemma 3

(15) \begin{matrix}|u|_{(2−2 σ, σ); Q} ≤ ∥u∥_{W_{2}^{σ}((0,T); W_{2}^{2−2 σ}(0,l))} \\ ≤ C ∥u∥_{W_{2}^{0}((0,T); W_{2}^{2}(0,l))}^{1−σ} ∥u∥_{W_{2}^{1}((0,T); W_{2}^{0}(0,l))}^{σ} \\ ≤ C (∥u∥_{W_{2}^{0}((0,T); W_{2}^{2}(0,l))}^{2} + ∥u∥_{W_{2}^{1}((0,T); W_{2}^{0}(0,l))}^{2})^{1/2} = C ∥u∥_{W_{2}^{2,1}(Q)} . \end{matrix}

In such a way, from (13–15) follows

(16)  ∥φ∥_{L_{2}(Q_{hτ})} ≤ C (h_{max}^{2} + τ) ∥u∥_{W_{2}^{2,1}(Q)} .

To estimate the term ψ, let us set

ψ = ψ_{1} + ψ_{2} = Tt̄[u − T_{2}u + (\frac{h^{2}}{6} ux̄)x̂]

+\{[u − T_{2}u + (\frac{h^{2}}{6} ux̄)x̂] − Tt̄[u − T_{2}u + (\frac{h^{2}}{6} ux̄)x̂]\} .

Further

ψ_{2} = −(Tt̄u − u) + T_{2}(Tt̄u − u) − [\frac{h^{2}}{6} (Tt̄u − u)x̄]x̂ = −φ + T_{2}φ − (\frac{h^{2}}{6} φx̄)x̂ ,

and, using estimate (16), we immediately obtain

(17)  ∥ψ_{2}∥_{L_{2}(Q_{hτ})} ≤ C (h_{max}^{2} + τ) ∥u∥_{W_{2}^{2,1}(Q)} .

The term ψ_{1} can be presented in the form

ψ_{1}(x, t) = \frac{1}{ℏτ} ∫_{x_{−}}^{x_{+}} ∫_{x′}^{x} ∫_{x}^{x′′} ∫_{t−τ}^{t} K(x′) \frac{∂^{2}u(x′′′, t′)}{∂x^{2}} dt′ dx′′′ dx′′ dx′

+\frac{h}{6 ℏτ} ∫_{x_{−}}^{x} ∫_{x′}^{x} ∫_{t−τ}^{t} \frac{∂^{2}u(x′′, t′)}{∂x^{2}} dt′ dx′′ dx′ + \frac{h_{+}}{6 ℏτ} ∫_{x}^{x_{+}}∫_{x}^{x′} ∫_{t−τ}^{t} \frac{∂^{2}u(x′′, t′)}{∂x^{2}} dt′ dx′′ dx′ .

Estimating integrals at the right hand side by the Cauchy–Schwartz inequality, one obtains

|ψ_{1}(x, t)| ≤ \frac{C h_{max}^{2}}{\sqrt{ℏτ}} ∥\frac{∂^{2}u}{∂x^{2}} ∥_{L_{2}(e′)} ,  where  e′ = (x_{−}, x_{+}) × (t − τ, t) .

Summing over the mesh Q_{hτ}, we obtain:

(18)  ∥ψ_{1}∥_{L_{2}(Q_{hτ})} ≤ C h_{max}^{2} ∥\frac{∂^{2}u}{∂x^{2}} ∥_{L_{2}(Q)} .

The term ψ(x, 0) can be presented in the form

ψ(x, 0) = \frac{1}{ℏ} ∫_{x_{−}}^{x_{+}}∫_{x′}^{x} K(x′) u_{0}′(x′′) dx′′ dx′ + \frac{h_{+}}{6 ℏ} ∫_{x}^{x_{+}}u_{0}′(x′) dx′ − \frac{h}{6 ℏ} ∫_{x_{−}}^{x} u_{0}′(x′) dx′ ,

wherefrom follows

|ψ(x, 0)| ≤ C \sqrt{ℏ} ∥u_{0}′∥_{L_{2}(i)} , i = (x_{−}, x_{+})

and by summing over the mesh ω̂

(19)  ∥ψ( · , 0)∥_{L_{2}(ω̂)} ≤ C h_{max} ∥u_{0}∥_{W_{2}^{1}(0, l)} ≤ C h_{max} ∥u∥_{W_{2}^{2, 1}(Q)} .

From (12) and (16–19) we obtain the desired convergence rate estimate for FDS (3)

(20)  ∥u − v∥_{L_{2}(Q_{hτ})} ≤ C (h_{max}^{2} + τ) ∥u∥_{W_{2}^{2, 1}(Q)} .

In such a manner, the following assertion is proved.

Theorem 1. FDS (3) converges in the discrete L_{2} norm and the inequality (20) holds.

Notice, that the convergence rate estimate (20) is consistent with the smoothness of the solution of IBVP (1) (see [10]). In the case of uniform mesh estimate of the form (20) is obtained in [7] for τ ≍ h^{2}. Equation with variable coefficients is considered in [8]. For the less smooth solutions (u ∈ W_{2}^{2s,s}, 0 < s < 1) analogous lower order convergence rate estimate can be obtained. Analogous result (in continuous L_{2}–norm) follows from the existing finite element theory.

Monotonous scheme.

Let us approximate now the IBVP (1) with the following implicite monotonous FDS (see [15])

(21)

vt̄ + \frac{h_{+} − h}{3} vt̄ ; x̄ = v_{x̄x̂} + T_{2}Tt̄f in Q_{hτ} ;

v + \frac{h_{+} − h}{3} vx̄ = T_{2}u_{0} for t = 0 ; v = 0 for x = 0, l .

For the sake of simplicity we assume that the mesh ω̂ satisfies the condition

(22)  h < h_{+} < c_{1} h ,

The error z = u − v satisfies the conditions

(23)

zt̄ + \frac{h_{+} − h}{3} zt̄ ; x̄ = z_{x̄x̂} + φ_{x̄x̂} + ψt̄ in Q_{hτ} ;

z + \frac{h_{+} − h}{3} zx̄ = ψ(x, 0) for t = 0 ; z = 0 for x = 0, l ,

where

φ = Tt̄u − u  and  ψ = u − T_{2}u + \frac{h_{+} − h}{3} ux̄ .

To obtain the a priori estimate in discrete L_{2}–norm, let us set z = z^{(1)} + z^{(2)} , where z^{(1)} and z^{(2)} are the solutions of the following FDSs

(24) z(1) ; t̄ + \frac{h_{+} − h}{3} z(1) ; t̄ ; x̄ = z_{x̄x̂}^{(1)} + φ_{x̄x̂} in Q_{hτ} ;

z^{(1)} = 0 for t = 0 ; z^{(1)} = 0 for x = 0, l ,

and

(25)

z(2) ; t̄ + \frac{h_{+} − h}{3} z(2) ; t̄ ; x̄ = z_{x̄x̂}^{(2)} + ψt̄ in Q_{hτ} ;

z^{(2)} + \frac{h_{+} − h}{3} z(2) ; x̄ = ψ(x, 0) for t = 0 ; z^{(2)} = 0 for x = 0, l .

Let ζ be a mesh–function satisfying

(26)  −ζ_{x̄x̂} = z^{(1)} + \frac{h_{+} − h}{3} z(1) ; x̄ in Q_{hτ}^{0} ;  ζ = 0 for x = 0, l .

Multiplying (24) by ζ, after some simple transformations, we obtain

(27)  (ζx̄t̄, ζx̄] − (z^{(1)}, ζ_{x̄x̂})_{∗} = (φ, ζ_{x̄x̂})_{∗} .

FINITE DIFFERENCE SCHEMES ON NONUNIFORM MESHES 155

From (27) and (26), using the identity

(ζx̄t̄, ζx̄] = \frac{τ}{2} ∥ζx̄t̄]|^{2} + \frac{1}{2 τ} (∥ζx̄]|^{2} − ∥ζ̌x̄]|^{2}) ,

we obtain

\frac{1}{2 τ} (∥ζx̄]|^{2} − ∥ζ̌x̄]|^{2}) + \frac{τ}{2} ∥ζx̄t̄]|^{2} + ∥z^{(1)}∥_{∗}^{2}

= −(φ, z^{(1)})_{∗} − (φ, \frac{h_{+} − h}{3} z(1) ; x̄)_{∗} − (z^{(1)}, \frac{h_{+} − h}{3} z(1) ; x̄)_{∗} .

Further

∥\frac{h_{+} − h}{3} zx̄∥_{∗}^{2} = ∑_{x∈ω̂} (\frac{h_{+} − h}{3} · \frac{z − z_{−}}{h} )^{2}ℏ ≤ \frac{2 (c_{1} − 1)^{2}}{9} ∑_{x∈ω̂}(z^{2} + z_{−}^{2}) ℏ

= \frac{2 (c_{1} − 1)^{2}}{9} ( ∑_{x∈ω̂} z^{2} ℏ + ∑_{x∈ω̂\\{x_{n−1}\}} z^{2} ℏ_{+}) ≤ \frac{2}{9} (c_{1} − 1)^{2} (c_{1} + 1) ∥z∥_{∗}^{2} ,

wherefrom follows

|(z, \frac{h_{+} − h}{3} zx̄)_{∗}| ≤ \frac{c_{1} − 1}{3} \sqrt{2 (c_{1} + 1)} ∥z∥_{∗}^{2} ,

|(φ, \frac{h_{+} − h}{3} zx̄)_{∗}| ≤ \frac{c_{1} − 1}{3} \sqrt{2 (c_{1} + 1)} ∥φ∥_{∗} ∥z∥_{∗}

≤ ε ∥z∥_{∗}^{2} + \frac{2 (c_{1} + 1) (c_{1} − 1)^{2}}{36 ε} ∥φ∥_{∗}^{2}

and

|(φ, z)_{∗}| ≤ ε ∥z∥_{∗}^{2} + \frac{1}{4 ε} ∥φ∥_{∗}^{2} .

From here follows

\frac{1}{2 τ} (∥ζx̄]|^{2} − ∥ζ̌x̄]|^{2}) + \frac{τ}{2} ∥ζx̄t̄]|^{2} + [1 − \frac{c_{1} − 1}{3} \sqrt{2 (c_{1} + 1)} − 2 ε] ∥z^{(1)}∥_{∗}^{2}

≤ \frac{1}{4 ε} [\frac{2 (c_{1} + 1) (c_{1} − 1)^{2}}{9} + 1] ∥φ∥_{∗}^{2} .

If

(28)  1 − \frac{c_{1} − 1}{3} \sqrt{2 (c_{1} + 1)} > 0 ,

then, for sufficiently small ε > 0, one obtains

\frac{1}{2 τ} (∥ζx̄]|^{2} − ∥ζ̌x̄]|^{2}) + \frac{τ}{2} ∥ζx̄t̄]|^{2} + C_{0} ∥z^{(1)}∥_{∗}^{2} ≤ C_{1} ∥φ∥_{∗}^{2} .

156 JOVANOVIĆ AND MATUS

From here, summing over the mesh ω_{τ} we obtain

\frac{1}{2} ∥ζx̄( · , T)]|^{2} + \frac{τ^{2}}{2} ∑_{t=τ}^{T} ∥ζx̄t̄]|^{2} + C_{0} τ ∑_{t=τ}^{T} ∥z^{(1)}∥_{∗}^{2} ≤ C_{1} τ ∑_{t=τ}^{T} ∥φ∥_{∗}^{2} ,

and finally

(29)  ∥z^{(1)}∥_{L_{2}(Q_{hτ})} ≤ C_{2} ∥φ∥_{L_{2}(Q_{hτ})} .

Notice that the condition (28) is satisfied for

(c_{1} − 1) (c_{1} + 1)^{2} < 4.5

wherefrom follows

(30)  c_{1} < 2.188 .

Let us estimate z^{(2)}. Multiplying (25) in a scalar way by η, where

−η_{t} = z^{(2)} in Q_{hτ}^{0} ; η = 0 for t = T + τ ,

and using partial summing on t, we obtain

−τ ∑_{t=τ}^{T}(z^{(2)}, η_{t})_{∗} − τ ∑_{t=τ}^{T} (\frac{h_{+} − h}{3} z(2) ; x̄, η_{t})_{∗} = τ ∑_{t=τ}^{T}(z_{x̄x̂}^{(2)}, η)_{∗} − τ ∑_{t=τ}^{T}(ψ, η_{t})_{∗} .

Further

(z_{x̄x̂}^{(2)}, η)_{∗} = −(z(2) ; x̄, ηx̄] = (η_{x̄t}, ηx̄]

= \frac{1}{2 τ} (∥η̂x̄]|^{2} − ∥ηx̄]|^{2}) − \frac{τ}{2} ∥η_{x̄t}]|^{2} = \frac{1}{2 τ} (∥η̂x̄]|^{2} − ∥ηx̄]|^{2}) − \frac{τ}{2} ∥z(2) ; x̄]|^{2}

wherefrom follows

(31)  \begin{matrix}τ ∑_{t=τ}^{T} ∥z^{(2)}∥_{∗}^{2} + \frac{1}{2} ∥ηx̄( · , τ)]|^{2} + \frac{τ^{2}}{2} ∑_{t=τ}^{T} ∥z(2) ; x̄]|^{2} \\ = τ ∑_{t=τ}^{T}(ψ, z^{(2)})_{∗} − τ ∑_{t=τ}^{T} (\frac{h_{+} − h}{3} z(2) ; x̄, z^{(2)})_{∗} . \end{matrix}

From (31) follows

τ ∑_{t=τ}^{T} ∥z^{(2)}∥_{∗}^{2} ≤ −τ ∑_{t=τ}^{T} (\frac{h_{+} − h}{3} z(2) ; x̄, z^{(2)})_{∗} + τ ∑_{t=τ}^{T}(ψ, z^{(2)})_{∗}

≤ \frac{c_{1} − 1}{3} \sqrt{2 (c_{1} + 1)} τ ∑_{t=τ}^{T} ∥z^{(2)}∥_{∗}^{2} + ε τ ∑_{t=τ}^{T} ∥z^{(2)}∥_{∗}^{2} + \frac{1}{4 ε} τ ∑_{t=τ}^{T} ∥ψ∥_{∗}^{2} .

From here, under the condition (30), for sufficiently small ε > 0 , we obtain

(32)  ∥z^{(2)}∥_{L_{2}(Q_{hτ})} ≤ C_{3} ∥ψ∥_{L_{2}(Q_{hτ})} .

From (29) and (32) we obtain the desired a priori estimate

(33)  ∥z∥_{L_{2}(Q_{hτ})} ≤ C (∥φ∥_{L_{2}(Q_{hτ})} + ∥ψ∥_{L_{2}(Q_{hτ})}) .

Notice that contrary to the case of divergent scheme (3), this a priori estimate is obtained under restriction to the ratio h_{+}/h.

The terms φ and ψ in the right hand side of (33) can be estimated in an analogous way as in the case of divergent FDS: φ is the same as in the previous case, while ψ may be represented in the form

ψ = ψ_{1} + ψ_{2} = Tt̄(u − T_{2}u + \frac{h_{+} − h}{3} ux̄)

+[(u − T_{2}u + \frac{h_{+} − h}{3} ux̄) − Tt̄(u − T_{2}u + \frac{h_{+} − h}{3} ux̄)] .

Further

ψ_{2} = −(Tt̄u − u) + T_{2}(Tt̄u − u) − [\frac{h_{+} − h}{3} (Tt̄u − u)x̄] = −φ + T_{2}φ − \frac{h_{+} − h}{3} φx̄ ,

and

ψ_{1}(x, t) = \frac{1}{ℏτ} ∫_{x_{−}}^{x_{+}} ∫_{x′}^{x} ∫_{x}^{x′′} ∫_{t−τ}^{t} K(x′) \frac{∂^{2}u(x′′′, t′)}{∂x^{2}} dt′ dx′′′ dx′′ dx′

+\frac{h_{+} − h}{3 hτ} ∫_{x_{−}}^{x} ∫_{x}^{x′} ∫_{t−τ}^{t} \frac{∂^{2}u(x′′, t′)}{∂x^{2}} dt′ dx′′ dx′ .

In such a manner, estimates (16–18) and the convergence rate estimate (20) are satisfied.

Theorem 2. FDS (21) converges in discrete norm L_{2}, under assumptions (22) and (30), and the convergence rate estimate (20) holds.

Remark. Analogous results can be obtained for FDS approximating other boundary value problems, including problems with variable coefficients and hyperbolic problems.

References

[1] B.M. Berkovskiĭ, V.K. Polevikov, Numerical Experiments in Convection, Minsk, 1988 (in Russian).

[2] J.H. Bramble, S.R. Hilbert, Bounds for a class of linear functionals with application to Hermite interpolation, Numer. Math. 16 (1971), 362–369.

[3] P.G. Ciarlet, The Finite Element Method for Elliptic Problems, North Holland, Amsterdam – New York – Oxford, 1978.

[4] T. Dupont, R. Scott, Polynomial approximation of functions in Sobolev spaces, Math. Comput. 34 (1980), 441–463.

[5] V.A. Gushchin, V.V. Shchennikov, On a monotone second–order difference scheme, Zh. Vychisl. Mat. i Mat. Fiz. 14 (1974), 789–792 (in Russian).

[6] V.P. Il’in, Balance approximations of high accuracy for Poisson equation, Sibirsk. Mat. Zh. 37 (1996), 151–161 (in Russian).

[7] L.D. Ivanović, B.S. Jovanović, E.E. Süli, On the rate of convergence of difference schemes for the heat transfer equation on the solutions from W_{2}^{s, s/2}, Mat. Vesnik 36 (1984), 206–212.

[8] B.S. Jovanović, On the convergence of finite–difference schemes for parabolic equations with variable coefficients, Numer. Math. 54 (1989), 395–404.

[9] B.S. Jovanović, The Finite Difference Method for Boundary Value Problems with Weak Solutions, Posebna izdanja Mat. Instituta 16, Beograd, 1993.

[10] R.D. Lazarov, V.L. Makarov, A.A. Samarskiĭ, Application of exact difference schemes for construction and investigation of difference schemes for generalized solutions, Mat. Sbornik 117 (1982), 469–480 (in Russian).

[11] J.L. Lions, E. Magenes, Problèmes aux Limites non Homogènes et Applications, Dunod, Paris, 1968.

[12] A.A. Samarskiĭ, Theory of Difference Schemes, Nauka, Moscow, 1983 (in Russian).

[13] A.A. Samarskiĭ, A.V. Gulin, Stability of Difference Schemes, Nauka, Moscow, 1973 (in Russian).

[14] A.A. Samarskiĭ, R.D. Lazarov, V.L. Makarov, Finite Difference Schemes for Differential Equations with Generalized Solutions, Vysshaya shkola, Minsk 1987 (in Russian).

[15] A.A. Samarskiĭ, P.N. Vabishchevich, P.P. Matus, Difference schemes of high accuracy on nonuniform meshes, Differentsial’nye Uravneniya 32 (1996), 265–274 (in Russian).

[16] A.A. Samarskiĭ, P.N. Vabishchevich, P.P. Matus, Second–order difference schemes on nonuniform meshes, Zh. Vychisl. Mat. i Mat. Fiz. 38 (1998), 413–424 (in Russian).

Matematički fakultet (Received 07 02 1998) Studentski trg 16 (Revised 02 02 1999) 11001 Beograd, p.p. 550 Yugoslavia

Institute of Mathematics National Academy of Sciences of Belarus 11 Surganov Str. 220072 Minsk Belarus