# Preconditioning and Uniform Convergence for Convection-Diffusion Problems Discretized on Shishkin-Type Meshes

Authors: Thái Anh Nhan; Relja Vulanović
Journal: Advances in Numerical Analysis
 (2016)

---

## Abstract

A one-dimensional linear convection-diffusion problem with a perturbation parameterɛ multiplying the highest derivative is considered. The problem is solved numerically by using the standard upwind scheme on special layer-adapted meshes. It is proved that the numerical solution is ɛ-uniform accurate in the maximum norm. This is done by a new proof technique in which the discrete system is preconditioned in order to enable the use of the principle where “ɛ-uniform stability plus ɛ-uniform consistency implies ɛ-uniform convergence.” Without preconditioning, this principle cannot be applied to convection-diffusion problems because the consistency error is not uniform in ɛ. At the same time, the condition number of the discrete system becomes independent of ɛ due to the same preconditioner; otherwise, the condition number of the discrete system before preconditioning increases when ɛ tends to 0. We obtained such results in an earlier paper, but only for the standard Shishkin mesh. In a nontrivial generalization, we show here that the same proof techniques can be applied to the whole class of Shishkin-type meshes.


---

## Body

## 1. Introduction

In this paper we consider a convection-diffusion boundary-value problem in which the coefficient of the diffusion term is a small positive parameterɛ. This makes the problem a singularly perturbed one. Singularly perturbed boundary-value problems are characterized by the presence of the perturbation parameter ɛ which multiplies the highest derivative in the differential equation considered. Therefore, when ɛ tends to 0, the degree of the differential equation is reduced and the solution of the reduced equation typically does not satisfy all the boundary conditions imposed. This is why the solution of the original problem may have boundary and/or interior layers; that is, the solution may change abruptly over narrow regions whose size depends directly on ɛ. It is typical that the derivatives of the solution behave in the layers like O
(
ɛ
-
k
), where k is an appropriate positive number. Because of this, the classical numerical methods for solving boundary-value problems do not work well for singularly perturbed problems and special numerical methods need to be constructed [1–4]. Ideally, the goal of these methods is to achieve ɛ-uniform pointwise convergence. The layer-adapted meshes of Shishkin or Bakhvalov types are frequently used to meet this goal.The interest in singular perturbation problems is motivated by their numerous applications. For instance, the introduction in [4] mentions Navier-Stokes equations with large Reynolds number and other convection-diffusion equations modeling water-pollution problems, oil-extraction processes, flows in chemical reactors, convective heat-transport problems with large Péclet numbers, and semiconductor devices. Let us also mention the application to a steady, fully developed laminar flow of alumina-water nanofluid [5].In this paper, we consider the simplest singularly perturbed convection-diffusion problem in one dimension:(1)
L
u
≔
-
ɛ
u
′
′
-
b
x
u
′
+
c
x
u
=
f
x
,
x
∈
0,1
,
u
0
=
u
1
=
0
,
b
x
≥
β
>
0
,
c
x
≥
0
f
o
r
x
∈
I
≔
0,1
,where 0
<
ɛ
≪
1 and b, c, and f are C
1
(
I
)-functions. The problem has a unique solution u in C
3
(
I
) [6, 7]. In general, this solution exhibits an exponential boundary layer near x
=
0.Problem (1) serves as a model problem for discussing some theoretical aspects related to the proof of ɛ-uniform pointwise convergence of numerical methods for singularly perturbed convection-diffusion problems. This proof is not as simple as for the singularly perturbed reaction-diffusion problems, where the proof can be based on the following classical principle, which originates from nonperturbed problems (cf. [8–10]).Principle 1.
ɛ-uniform stability and ɛ-uniform consistency, both in the maximum norm, imply ɛ-uniform pointwise convergence.Principle1 does not work in the proof of ɛ-uniform pointwise convergence for convection-diffusion problem (1). When (1) is discretized by using the upwind finite-difference scheme on the Shishkin mesh, a careful analysis shows that the consistency error in the layer part is not ɛ-uniformly accurate in the maximum norm (cf. [11, Sec. 6.1.3]). Hence, special techniques like barrier functions [1–4] or the use of hybrid stability inequalities [2, 9, 12, 13] are required to prove the ɛ-uniform pointwise convergence.We show in [14] that it is possible to apply Principle 1 to problems of type (1) after the linear system, which results when (1) is discretized, is preconditioned. The upwind discretization scheme on the standard Shishkin mesh is considered in that paper. Although the scheme is ɛ-uniformly stable, the discrete linear system is ill-posed since its condition number grows unboundedly when ɛ
→
0, as pointed out by Roos in [15]. By using a relatively simple diagonal preconditioner, Roos eliminates the ɛ-dependence of the condition number.It is shown in [14] that a suitable modification of Roos’ preconditioner enables the proof, based on Principle 1, that the pointwise errors of the numerical solution are ɛ-uniformly of almost first order. Since the standard Shishkin mesh is the only one considered in [14], the question is now how to use the same approach and achieve the same result for the general class of Shishkin-type meshes in the sense of [2, 16]. The present paper addresses this question.Therefore, for convection-diffusion problem (1), we consider the new proof technique of ɛ-uniform pointwise convergence, introduced in [14], and we generalize it to the whole class of Shishkin-type meshes. The generalization is not entirely straightforward since the general properties of the meshes require many new technical details. Moreover, we slightly modify the preconditioner used in [14].In this final paragraph of the introduction, we give the outline of the paper. In Section2, we describe the Shishkin-type meshes which are used when discretizing problem (1). We analyze the conditioning of the upwind finite-difference discretization in Section 3. Then, in Section 4, we define the preconditioner and give a proof of ɛ-uniform stability of the preconditioned discrete system. We arrive at the main result, the proof of ɛ-uniform pointwise convergence using Principle 1, in Section 5. The last section, Section 6, contains some final conclusions.


## 2. Shishkin-Type Meshes

LetI
N be a general discretization mesh with points x
i, where(2)
0
=
x
0
<
x
1
<
⋯
<
x
N
-
1
<
x
N
=
1
.We consider the Shishkin-type (or S-type) meshes as introduced in [16]; see [2] as well. Any such mesh is dense in the boundary layer near x
=
0 and transitions to a coarse uniform mesh at a point constructed like in the standard Shishkin mesh:(3)
σ
≔
a
ɛ
L
.Here, a is a user-chosen positive parameter and we think of L as of L
=
ln
⁡
N, although a modification of this value can also be used, like in [17]. We assume that σ
<
1
/
2; otherwise, the values of N are unreasonably large.The coarse part of the mesh is obtained by uniformly dividing the interval[
σ
,
1
] into N
-
J subintervals of length H
=
(
1
-
σ
)
/
(
N
-
J
), where J is a positive integer such that Q
≔
J
/
N satisfies Q
<
1 and Q
-
1
≤
C, and where, from this point on, C denotes a generic positive constant independent of both the perturbation parameter ɛ and the mesh parameter N. Inside the layer, the mesh points are formed by amesh-generating function ϕ, which is a monotonically increasing function satisfying ϕ
(
0
)
=
0 and ϕ
(
Q
)
=
L. In other words, S-type meshes are defined by(4)
x
i
=
a
ɛ
ϕ
t
i
,
i
=
0,1
,
…
,
J
,
σ
+
t
i
-
Q
1
-
σ
1
-
Q
,
i
=
J
+
1
,
…
,
N
,where t
i
≔
i
/
N.The mesh steps are defined ash
i
=
x
i
-
x
i
-
1
,
i
=
1,2
,
…
,
N; the steps for i
=
1,2
,
…
,
J belong to the fine part of the mesh and h
i
=
H for i
=
J
+
1
,
J
+
2
,
…
,
N. Let also ħ
i
=
(
h
i
+
h
i
+
1
)
/
2
,
i
=
1,2
,
…
,
N
-
1, and let mesh functions on I
N be denoted by W
N, U
N, and so forth. For a function g defined on I, g
i indicates g
(
x
i
) and g
N stands for the corresponding mesh function. We identify mesh functions W
N with (
N
+
1
)-dimensional column vectors, W
N
=
[
W
0
N
,
W
1
N
,
…
,
W
N
N
]
T. We use the maximum norm of W
N:(5)
W
N
=
max
0
≤
i
≤
N
⁡
W
i
N
.The matrix norm induced by the above maximum vector norm is also denoted by ·.Following [2, 16], let us define themesh-characterizing function ψ which is related to the mesh-generating function ϕ as follows:(6)
ψ
t
=
e
-
ϕ
t
.This function is monotonically decreasing on [
0
,
Q
] with ψ
(
0
)
=
1 and ψ
(
Q
)
=
N
-
1.We need to assume some further properties of the mesh.Assumption 1.
Let the mesh-generating functionϕ
(
t
) be piecewise differentiable such that(7)
max
t
∈
0
,
Q
⁡
ϕ
′
t
≤
C
N
.Moreover, we also assume that ϕ
(
t
) fulfills(8)
Δ
ϕ
≔
min
i
=
1,2
,
…
,
J
⁡
Δ
i
≥
C
N
-
1
,where Δ
i
≔
ϕ
(
t
i
)
-
ϕ
(
t
i
-
1
)
,
i
=
1,2
,
…
,
N.Remark 2.
Examples of mesh-generating functionsϕ satisfying the above assumptions are the standard Shishkin mesh (S-mesh), Bakhvalov-Shishkin mesh (BS-mesh), and Vulanović-Shishkin mesh (VS-mesh). They are summarized in Table 1.Table 1
Examples of mesh-generating and mesh-characterising functions of S-type meshes.
Mesh
ϕ
t
max
⁡
ϕ
′
ψ
max
⁡
ψ
′
S
t
L
Q
L
Q
N
-
t
/
Q
L
Q
BS
-
ln
⁡
1
-
t
Q
1
-
1
N
N
Q
1
-
t
Q
1
-
1
N
1
Q
VS
t
Q
+
Q
/
L
-
t
2
L
2
Q
exp
⁡
-
t
Q
+
Q
/
L
-
t
4
QWe proceed to provide some estimates for the step size of the S-type meshes generated byϕ in the layer region. Because for i
=
1
,
…
,
J,(9)
x
i
=
a
ɛ
ϕ
t
i
=
-
a
ɛ
ln
⁡
ψ
t
i
⟺
ψ
t
i
=
e
-
x
i
/
a
ɛ
,we can bound the mesh step size inside the layer from above:(10)
h
i
=
a
ɛ
ϕ
t
i
-
ϕ
t
i
-
1
≤
a
ɛ
N
-
1
max
t
∈
t
i
-
1
,
t
i
⁡
ϕ
′
t
≤
a
ɛ
N
-
1
max
t
∈
t
i
-
1
,
t
i
⁡
ψ
′
t
ψ
t
i
=
a
ɛ
N
-
1
max
t
∈
t
i
-
1
,
t
i
⁡
ψ
′
t
e
x
i
/
a
ɛ
≤
a
ɛ
N
-
1
max
⁡
ψ
′
e
x
i
/
a
ɛ
,where we use m
a
x
|
ψ
′
|
≔
m
a
x
t
∈
0
,
Q
|
ψ
′
(
t
)
|. Thus, for 1
≤
i
≤
J
-
1, we have that(11)
ħ
i
≤
a
2
ɛ
N
-
1
max
⁡
ψ
′
e
x
i
/
a
ɛ
+
e
x
i
+
1
/
a
ɛ
≤
a
ɛ
N
-
1
max
⁡
ψ
′
e
x
i
+
1
/
a
ɛ
.


## 3. The Upwind Scheme and Its Condition Number

We consider the following upwind finite-difference discretization onI
N:(12)
U
0
N
=
0
,
L
N
U
i
N
≔
-
ɛ
D
′
′
U
i
N
-
b
i
D
′
U
i
N
+
c
i
U
i
N
=
f
i
,
i
=
1
,
…
,
N
-
1
,
U
N
N
=
0
,where(13)
D
′
′
W
i
=
1
ħ
i
W
i
+
1
-
W
i
h
i
+
1
-
W
i
-
W
i
-
1
h
i
,
D
′
W
i
=
W
i
+
1
-
W
i
h
i
+
1
.The matrix form of the linear system (12) is(14)
A
N
U
N
=
f
^
Nwith a tridiagonal matrix A
N
=
[
a
i
j
] and f
^
N
=
[
0
,
f
1
,
f
2
,
…
,
f
N
-
1
,
0
]
T. The nonzero elements of A
N are a
00
=
1, a
N
N
=
1,(15)
l
i
≔
a
i
-
1
,
i
=
-
ɛ
ħ
i
h
i
,
1
≤
i
≤
J
,
-
ɛ
H
2
,
J
+
1
≤
i
≤
N
-
1
,
r
i
≔
a
i
,
i
+
1
=
-
ɛ
ħ
i
h
i
+
1
-
b
i
h
i
+
1
,
1
≤
i
≤
J
,
-
ɛ
H
2
-
b
i
H
,
J
+
1
≤
i
≤
N
-
1
,
d
i
≔
a
i
i
=
1
,
i
=
0
-
l
i
-
r
i
+
c
i
,
1
≤
i
≤
N
-
1
,
1
,
i
=
N
.MatrixA
N is an L-matrix; that is, it has positive diagonal entries and nonnegative off-diagonal entries. It is also a nonsingular matrix satisfying A
N
-
1
≥
0 (inequalities involving matrices and vectors should be understood componentwise) and, therefore, inverse monotone. In other words, A
N is an M-matrix (an inverse monotone L-matrix). This fact is easy to prove using the following M-criterion; see [8], for instance.Theorem 3 (M
-
c
r
i
t
e
r
i
o
n).
LetA be an L-matrix and there exists a vector w such that w
>
0 and A
w
≥
γ for some positive constant γ. A is then an M-matrix and it holds that A
-
1
≤
γ
-
1
w.In the above theorem, setw
i
=
2
-
x
i
,
i
=
0,1
,
…
,
N, to get that A
N
w
≥
m
i
n
{
1
,
β
}. This implies that A
N is an M-matrix and that(16)
A
N
-
1
≤
2
min
⁡
1
,
β
≤
C
,which means that discrete problem (14) is stable uniformly in ɛ. By examining directly the entries of matrix A
N and noting that the lower bounds for h
i and ħ
i are achieved in the layer region, where h
i
~
ħ
i
≥
C
ɛ
Δ
ϕ, we get that(17)
A
N
≤
C
1
ɛ
Δ
ϕ
2
.Combining this and the ɛ-uniform stability (16), we arrive at the following result related to the condition number κ
(
A
N
) of matrix A
N, κ
(
A
N
)
≔
A
N
A
N
-
1.Theorem 4.
The condition number of matrixA
N satisfies the estimate(18)
κ
A
N
≤
C
1
ɛ
Δ
ϕ
2
.Let us illustrate Theorem4 using a simple example taken from [2, page 1](19)
-
ɛ
u
′
′
x
-
u
′
x
=
1
,
0
<
x
<
1
,
u
0
=
u
1
=
0
.It is easy to observe the ɛ-dependence of the condition numbers in Tables 2 and 3. They clearly show that the bound in Theorem 4 is sharp. For the standard Shishkin mesh, we refer the readers to the numerical experiments in [15].Table 2
The condition number of discrete system (12) on the BS-mesh for problem (19).
ε
N
=
32
N
=
64
N
=
128
N
=
256
N
=
512
N
=
1024
1
e
-
2
2.06
e
+
04
8.96
e
+
04
3.72
e
+
05
1.52
e
+
06
6.13
e
+
06
2.46
e
+
07
1
e
-
3
2.19
e
+
05
9.48
e
+
05
3.93
e
+
06
1.60
e
+
07
6.45
e
+
07
2.59
e
+
08
1
e
-
4
2.20
e
+
06
9.54
e
+
06
3.96
e
+
07
1.61
e
+
08
6.49
e
+
08
2.61
e
+
09
1
e
-
5
2.20
e
+
07
9.55
e
+
07
3.96
e
+
08
1.61
e
+
09
6.50
e
+
09
2.61
e
+
10
1
e
-
6
2.20
e
+
08
9.55
e
+
08
3.96
e
+
09
1.61
e
+
10
6.50
e
+
10
2.61
e
+
11
1
e
-
7
2.20
e
+
09
9.55
e
+
09
3.96
e
+
10
1.61
e
+
11
6.50
e
+
11
2.61
e
+
12
1
e
-
8
2.20
e
+
10
9.55
e
+
10
3.96
e
+
11
1.61
e
+
12
6.50
e
+
12
2.61
e
+
13Table 3
The condition number of  discrete system (12) on the VS-mesh for problem (19).
ε
N
=
32
N
=
64
N
=
128
N
=
256
N
=
512
N
=
1024
1
e
-
2
2.75
e
+
04
1.23
e
+
05
5.11
e
+
05
2.05
e
+
06
8.12
e
+
06
3.20
e
+
07
1
e
-
3
2.91
e
+
05
1.30
e
+
06
5.39
e
+
06
2.16
e
+
07
8.55
e
+
07
3.36
e
+
08
1
e
-
4
2.93
e
+
06
1.31
e
+
07
5.43
e
+
07
2.18
e
+
08
8.61
e
+
08
3.39
e
+
09
1
e
-
5
2.93
e
+
07
1.31
e
+
08
5.43
e
+
08
2.18
e
+
09
8.62
e
+
09
3.39
e
+
10
1
e
-
6
2.93
e
+
08
1.31
e
+
09
5.43
e
+
09
2.18
e
+
10
8.62
e
+
10
3.39
e
+
11
1
e
-
7
2.93
e
+
09
1.31
e
+
10
5.43
e
+
10
2.18
e
+
11
8.62
e
+
11
3.39
e
+
12
1
e
-
8
2.93
e
+
10
1.31
e
+
11
5.43
e
+
11
2.18
e
+
12
8.62
e
+
12
3.39
e
+
13


## 4. Preconditioning and Stability

In this section, we propose an appropriately designed diagonal preconditioner which not only eliminates theɛ-dependence of the condition number of the discrete systems, but also retains its ɛ-uniform stability in the sense of (16). The preconditioner is not of interestper se but as a means to prove ɛ-uniform pointwise convergence via Principle 1.LetM
=
d
i
a
g
(
m
0
,
m
1
,
…
,
m
N
) be a diagonal matrix with the entries(20)
m
0
=
1
,
m
i
=
ħ
i
H
,
i
=
1,2
,
…
,
N
-
1
,
m
N
=
1
.On noting that ħ
i
=
H for i
=
J
+
1
,
…
,
N
-
1, we see that when the discrete system (12) is multiplied by M, this is equivalent to multiplying the equations 1,2
,
…
,
J of system (14) by ħ
i
/
H
,
i
=
1,2
,
…
,
J. The modified system is(21)
A
~
N
U
N
=
M
f
^
N
,where A
~
N
=
M
A
N. Let the entries of A
~
N be denoted by a
~
i
j, the nonzero ones being(22)
l
~
i
≔
a
~
i
-
1
,
i
=
-
ɛ
h
i
H
,
1
≤
i
≤
J
,
-
ɛ
H
2
,
J
+
1
≤
i
≤
N
-
1
,
r
~
i
≔
a
~
i
,
i
+
1
=
-
ɛ
h
i
+
1
H
-
b
i
ħ
i
h
i
+
1
H
,
1
≤
i
≤
J
-
1
,
-
ɛ
H
2
-
b
i
ħ
i
H
2
,
i
=
J
,
-
ɛ
H
2
-
b
i
H
,
J
+
1
≤
i
≤
N
-
1
,
d
~
i
≔
a
~
i
i
=
1
,
i
=
0
-
l
~
i
-
r
~
i
+
c
i
ħ
i
H
,
1
≤
i
≤
J
,
-
l
~
i
-
r
~
i
+
c
i
,
J
+
1
≤
i
≤
N
-
1
,
1
,
i
=
N
.MatrixA
~
N remains an L-matrix since the preconditioning does not change this property of A
N. We show in Lemma 7 below that A
~
N is an M-matrix and that the modified discretization (21) is stable uniformly in ɛ. But first, we give a technical result related to the mesh.Lemma 5.
Leta
β
>
2 and let, in addition to Assumption 1, the mesh-generating function ϕ satisfy the following conditions on [
0
,
Q
]:(i)
ϕ
(
j
)
≥
0, j
=
1,2
,
3;
(ii)
ϕ
′
(
0
)
≥
m
>
0, where m is a constant independent of ɛ and N;
(iii)
ϕ
′
′
≤
2
ϕ
′
2;
(iv)
ϕ
′
≤
C
L
k for some k
>
0.Then, for a sufficiently large N, independent of ɛ, there exists a positive constant δ, independent of both ɛ and N, such that(23)
S
i
≔
β
2
1
+
Δ
i
Δ
i
+
1
-
1
a
1
Δ
i
-
1
Δ
i
+
1
≥
δ
>
0
,
i
=
1
,
…
,
J
-
1
.Proof.
Sincea
β
>
2, we have that β
/
2
≥
1
/
a
+
η for some η
>
0. Then,(24)
S
i
≥
1
a
P
i
+
η
,where(25)
P
i
=
Δ
i
Δ
i
+
1
+
Δ
i
2
+
Δ
i
-
Δ
i
+
1
Δ
i
Δ
i
+
1
.Then, because of (i) and (iii),(26)
P
i
≥
2
P
∗
i
,
where
P
∗
i
≔
ϕ
′
t
i
-
1
2
-
ϕ
′
t
i
+
1
2
N
2
Δ
i
Δ
i
+
1
.If we show that(27)
P
∗
i
⟶
0
uniformly  in
ɛ
when
N
⟶
∞
,then we will have (23) provided N is sufficiently large independently of ɛ. We now show that (27) holds true. First,(28)
P
∗
i
≤
C
ϕ
′
t
i
-
1
2
-
ϕ
′
t
i
+
1
2because of (i) and (ii), and then(29)
P
∗
i
≤
C
N
-
1
L
k
ϕ
′
′
t
i
+
1
≤
C
N
-
1
L
3
kbecause of (i), (iii), and (iv).The meshes defined in Table1 satisfy conditions (i)–(iv) of Lemma 5, with the exception of the BS-mesh which does not fulfill condition (iv). However, estimate (23) still holds true for the BS-mesh if we assume that 2
-
1
≤
Q
<
1. This is not a serious restriction since Q
=
1
/
2 is a typical choice. The proof of this result, stated below in Lemma 6, is given in the appendix.Lemma 6.
Leta
β
>
2 and let 2
-
1
≤
Q
<
1. Then the BS-mesh satisfies estimate (23).Lemma 7.
Under the assumptions of Lemma5 (Lemma 6 if the BS-mesh is used), matrix A
~
N of system (21) satisfies(30)
A
~
N
-
1
≤
C
.Proof.
We construct a vectorv
=
[
v
0
,
v
1
,
…
,
v
N
]
T such that(a)
v
i
>
0
,
i
=
0,1
,
…
,
N,
(b)
v
i
≤
C
,
i
=
0,1
,
…
,
N,
(c)
l
~
i
v
i
-
1
+
d
~
i
v
i
+
r
~
i
v
i
+
1
≥
θ
,
i
=
1,2
,
…
,
N
-
1, where θ is a positive constant independent of both ɛ and N.Then, according to the M-criterion,(31)
A
~
N
-
1
≤
θ
-
1
v
≤
C
.We define the vector v as follows (cf. [14, 15]):(32)
v
i
=
α
-
H
i
+
λ
min
⁡
1
+
ρ
J
-
i
,
1
,where α and λ are appropriately chosen positive constants and ρ
=
β
H
/
ɛ.
SinceH
N
≤
C, there exists a constant α such that v
i
≥
α
-
H
i
>
0 and condition (a) is satisfied. It also holds true that v
i
≤
α
+
λ. Therefore, condition (b) is satisfied if we prove that λ
≤
C. We do this in next steps while we verify condition (c).
When1
≤
i
≤
J
-
1, using Lemma 5, we have(33)
l
~
i
v
i
-
1
+
d
~
i
v
i
+
r
~
i
v
i
+
1
=
l
~
i
+
d
~
i
+
r
~
i
v
i
+
l
~
i
H
-
r
~
i
H
=
ħ
i
H
c
i
v
i
-
ɛ
h
i
+
ɛ
h
i
+
1
+
b
i
ħ
i
h
i
+
1
≥
-
ɛ
h
i
-
ɛ
h
i
+
1
+
b
i
2
+
b
i
h
i
2
h
i
+
1
≥
S
i
≥
δ
>
0
.For i
=
J, condition (c) is verified as follows:(34)
l
~
J
v
J
-
1
+
d
~
J
v
J
+
r
~
J
v
J
+
1
=
ħ
J
H
c
J
v
J
+
l
~
J
H
-
r
~
J
H
+
λ
ρ
1
+
ρ
≥
-
r
~
J
λ
ρ
1
+
ρ
+
l
~
J
-
r
~
J
H
=
ɛ
H
2
+
b
J
ħ
J
H
2
λ
ρ
1
+
ρ
-
ɛ
h
J
+
ɛ
H
+
b
J
ħ
J
H
=
2
ɛ
+
b
J
h
J
+
H
2
H
2
λ
β
H
ɛ
+
β
H
-
ɛ
h
J
+
b
J
2
≥
λ
β
2
H
-
ɛ
h
J
+
β
2
≥
β
2
,where in the last step, invoking (8), we choose a constant λ so that(35)
λ
β
2
H
-
ɛ
h
J
≥
λ
β
2
H
-
ɛ
a
ɛ
ϕ
t
J
-
ϕ
t
J
-
1
≥
λ
β
2
H
-
1
a
Δ
J
≥
λ
β
4
N
-
1
-
1
a
C
N
-
1
=
N
λ
β
4
-
1
a
C
≥
0
.To guarantee this, λ is chosen so that(36)
λ
β
4
≥
1
a
C
.
Finally, whenJ
+
1
≤
i
≤
N
-
1, we have(37)
l
~
i
v
i
-
1
+
d
~
i
v
i
+
r
~
i
v
i
+
1
=
c
i
v
i
+
l
~
i
H
-
r
~
i
H
+
l
~
i
1
+
ρ
J
λ
1
+
ρ
i
-
1
-
J
-
λ
1
+
ρ
i
-
J
+
r
~
i
1
+
ρ
J
λ
1
+
ρ
i
+
1
-
J
-
λ
1
+
ρ
i
-
J
≥
b
i
+
ρ
1
+
ρ
l
~
i
-
ρ
r
~
i
1
+
ρ
J
1
+
ρ
i
+
1
-
J
λ
≥
β
+
l
~
i
-
r
~
i
+
l
~
i
ρ
ρ
1
+
ρ
J
1
+
ρ
i
+
1
-
J
λ
=
β
+
b
i
H
-
β
H
λ
ρ
1
+
ρ
J
-
i
-
1
1
+
ρ
J
≥
β
.By examining the entries ofA
~
N, we easily see that the maximum absolute row sum of A
~
N is achieved in the layer region. Therefore,(38)
A
~
N
≤
C
N
Δ
ϕ
.A combination of Lemma7 and (38) results in the following.Theorem 8.
The condition number of matrixA
~
N satisfies the following ɛ-uniform estimate:(39)
κ
A
~
N
≤
C
N
Δ
ϕ
.Corollary 9.
For the meshes given in Table1, one has the following estimates:(40)
κ
A
~
N
≤
C
N
2
L
,
f
o
r
t
h
e
S
-
m
e
s
h
,
C
N
2
,
f
o
r
t
h
e
B
S
-
a
n
d
V
S
-
m
e
s
h
e
s
.In Tables4 and 5, we present the condition numbers of the preconditioned linear systems (21) for various values of ɛ and N for the BS- and VS-meshes. We can observe that the condition numbers of the preconditioned systems are independent of ɛ and that the bound in Corollary 9 is sharp.Table 4
The condition number of matrixA
~
N on the BS-mesh for problem (19).
ε
N
=
32
N
=
64
N
=
128
N
=
256
N
=
512
N
=
1024
1
e
-
2
6.58
e
+
02
2.68
e
+
03
1.08
e
+
04
4.34
e
+
04
1.74
e
+
05
6.95
e
+
05
1
e
-
3
6.89
e
+
02
2.78
e
+
03
1.11
e
+
04
4.40
e
+
04
1.75
e
+
05
7.00
e
+
05
1
e
-
4
6.94
e
+
02
2.80
e
+
03
1.12
e
+
04
4.43
e
+
04
1.76
e
+
05
7.02
e
+
05
1
e
-
5
6.94
e
+
02
2.80
e
+
03
1.12
e
+
04
4.43
e
+
04
1.76
e
+
05
7.03
e
+
05
1
e
-
6
6.94
e
+
02
2.80
e
+
03
1.12
e
+
04
4.43
e
+
04
1.76
e
+
05
7.03
e
+
05
1
e
-
7
6.94
e
+
02
2.80
e
+
03
1.12
e
+
04
4.43
e
+
04
1.76
e
+
05
7.03
e
+
05
1
e
-
8
6.94
e
+
02
2.80
e
+
03
1.12
e
+
04
4.43
e
+
04
1.76
e
+
05
7.03
e
+
05Table 5
The condition number of matrixA
~
N on the VS-mesh for problem (19).
ε
N
=
32
N
=
64
N
=
128
N
=
256
N
=
512
N
=
1024
1
e
-
2
7.48
e
+
02
3.13
e
+
03
1.27
e
+
04
5.10
e
+
04
2.04
e
+
05
8.11
e
+
05
1
e
-
3
7.80
e
+
02
3.23
e
+
03
1.30
e
+
04
5.20
e
+
04
2.07
e
+
05
8.20
e
+
05
1
e
-
4
7.85
e
+
02
3.25
e
+
03
1.31
e
+
04
5.22
e
+
04
2.08
e
+
05
8.24
e
+
05
1
e
-
5
7.85
e
+
02
3.25
e
+
03
1.31
e
+
04
5.23
e
+
04
2.08
e
+
05
8.25
e
+
05
1
e
-
6
7.85
e
+
02
3.25
e
+
03
1.31
e
+
04
5.23
e
+
04
2.08
e
+
05
8.25
e
+
05
1
e
-
7
7.85
e
+
02
3.25
e
+
03
1.31
e
+
04
5.23
e
+
04
2.08
e
+
05
8.25
e
+
05
1
e
-
8
7.85
e
+
02
3.25
e
+
03
1.31
e
+
04
5.23
e
+
04
2.08
e
+
05
8.25
e
+
05


## 5.ɛ-Uniform Convergence

For the proof ofɛ-uniform convergence, we need to decompose the solution u into the smooth and boundary-layer parts. There exist several decompositions of this kind, but we use the version presented in [2, Theorem 3.48](41)
u
x
=
s
x
+
y
x
,
x
∈
I
,
(42)
s
k
x
≤
C
1
+
ɛ
2
-
k
,
y
k
x
≤
C
ɛ
-
k
e
-
β
x
/
ɛ
,
x
∈
I
,
k
=
0,1
,
2,3
.The details related to the construction of the function s are not important here; they can be found in [2]. As for y, we note that it solves the problem(43)
L
y
x
=
0
,
x
∈
0,1
,
y
0
=
-
s
0
,
y
1
=
0
.We define the consistency error of the finite-difference operatorL
N as(44)
τ
i
=
τ
i
u
≔
L
N
u
i
-
f
i
,
i
=
1,2
,
…
,
N
-
1
.It holds true that(45)
τ
i
=
L
N
u
i
-
L
u
i
=
A
N
u
N
-
U
N
i
.Taylor’s expansion gives(46)
τ
i
u
≤
C
h
i
+
1
ɛ
u
′
′
′
i
+
u
′
′
i
,where g
i
≔
m
a
x
x
i
-
1
≤
x
≤
x
i
+
1
|
g
(
x
)
| for any C
(
I
)-function g. When the diagonal matrix M is multiplied to linear system (14), the consistency error of the multiplied system is(47)
τ
~
i
u
=
ħ
i
H
τ
i
u
,
1
≤
i
≤
J
,
τ
i
u
,
J
+
1
≤
i
≤
N
-
1
.Lemma 10.
Leta
β
≥
2. Then the following estimate holds true:(48)
τ
~
i
u
≤
C
N
-
1
max
⁡
ψ
′
2
,
i
=
1
,
…
,
J
-
1
,
C
N
-
1
,
i
=
J
,
…
,
N
-
1
.Proof.
We use decomposition (41) to get(49)
τ
~
i
u
=
τ
~
i
s
+
τ
~
i
y
.Then (46) and the derivative-estimates of s, given in (42), yield immediately that(50)
τ
~
i
s
≤
C
N
-
1and therefore the following remains to be proved:(51)
τ
~
i
y
≤
C
N
-
1
max
⁡
ψ
′
2
,
i
=
1
,
…
,
J
-
1
,
τ
~
i
y
≤
C
N
-
1
,
i
=
J
,
…
,
N
-
1
.Note that from condition (7), we easily get(52)
h
i
≤
C
ɛ
,
i
=
1
,
…
,
J
,
ħ
i
≤
C
ɛ
,
i
=
1
,
…
,
J
-
1
.This is the key property of S-type meshes, as well as the main ingredient of the following proof.
For1
≤
i
≤
J
-
1 (46), estimates (10) and (11), as well as the derivative-estimates of y in (42), imply(53)
τ
~
i
y
≤
C
ħ
i
H
h
i
+
1
ɛ
y
′
′
′
i
+
y
′
′
i
≤
C
N
-
1
max
⁡
ψ
′
2
e
2
x
i
+
1
/
a
ɛ
e
-
β
x
i
-
1
/
ɛ
≤
C
N
-
1
max
⁡
ψ
′
2
e
2
x
i
+
1
-
a
β
x
i
-
1
/
a
ɛ
=
C
N
-
1
max
⁡
ψ
′
2
e
2
x
i
+
1
-
x
i
-
1
/
a
ɛ
e
-
a
β
-
2
x
i
-
1
/
a
ɛ
≤
C
N
-
1
max
⁡
ψ
′
2
e
ħ
i
/
a
ɛ
≤
C
N
-
1
max
⁡
ψ
′
2
,where we have used (52) and a
β
≥
2 to get(54)
e
ħ
i
/
a
ɛ
≤
C
,
e
-
a
β
-
2
x
i
-
1
/
a
ɛ
≤
C
.
WhenJ
+
2
≤
i
≤
N
-
1, (42) and (46) give(55)
τ
~
i
y
≤
C
H
ɛ
y
′
′
′
i
+
y
′
′
i
≤
C
H
ɛ
2
e
-
β
x
i
-
1
/
ɛ
≤
C
H
ɛ
2
e
-
β
σ
+
H
/
ɛ
≤
C
N
H
2
ɛ
2
e
-
β
H
/
ɛ
e
-
β
σ
/
ɛ
.Estimate (51) follows from the fact that H
ɛ
-
1
2
e
-
β
H
/
ɛ
≤
C and because the definition of σ implies that(56)
e
-
β
σ
/
ɛ
=
e
-
β
a
L
=
N
-
β
a
≤
N
-
2
.
We finally prove (51) when i
=
J
,
J
+
1, in which case(57)
τ
~
J
y
=
ħ
J
H
τ
J
y
≤
τ
J
y
,
τ
~
J
+
1
y
=
τ
J
+
1
y
.We now use the fact that L
y
=
0 and work with a different form of the consistency error (this is a well-known technique, cf. [18, Lemma 5]):(58)
τ
~
i
y
≤
τ
i
y
≤
R
i
+
Q
i
+
c
i
y
i
,where(59)
R
i
=
ɛ
D
′
′
y
i
,
Q
i
=
b
i
D
′
y
i
.We immediately have that(60)
c
i
y
i
≤
C
e
-
β
x
i
/
ɛ
≤
C
e
-
β
σ
/
ɛ
=
C
e
-
β
a
L
=
C
N
-
a
β
≤
C
N
-
2
.As for R
i, it holds true that(61)
R
i
≤
ħ
i
-
1
ɛ
·
2
y
′
i
≤
C
N
e
-
β
σ
-
h
J
/
ɛ
≤
C
N
e
-
β
σ
/
ɛ
e
β
h
J
/
ɛ
≤
C
N
-
1
,by (52). Analogously,(62)
Q
i
≤
C
H
-
1
y
i
≤
C
N
e
-
β
σ
-
h
J
/
ɛ
≤
C
N
-
1
.This completes the proof.In general, the consistency errorτ
i of the layer component of the solution is not bounded pointwise uniformly in ɛ. When the above proof technique is applied to τ
i
[
y
], one can only get(63)
τ
i
y
≤
C
ɛ
-
1
N
-
1
L
,
for  the
S
-mesh
,
C
ɛ
-
1
N
-
1
,
for  the  BS-  and  VS-meshes
.The proposed preconditioner simplifies the analysis of the consistency error by introducing an extra ɛ factor needed for the layer component. Hence, the approach used in the proof of Lemma 10 is natural and straightforward because it only uses the classical Taylor expansion estimate for the truncation error.To illustrate (63), in Tables 6 and 7 we present the results of some numerical experiments on the BS- and VS-meshes, respectively. We refer the reader to [14] for the corresponding numerical results on the S-mesh.Table 6
The maximum norm of the consistency error[
A
N
u
N
-
f
^
N
] on the BS-mesh.
ε
N
=
32
N
=
64
N
=
128
N
=
256
N
=
512
N
=
1024
1
e
-
2
5.50
e
+
00
2.93
e
+
00
1.51
e
+
00
7.69
e
-
01
3.88
e
-
01
1.95
e
-
01
1
e
-
3
5.50
e
+
01
2.93
e
+
01
1.51
e
+
01
7.69
e
+
00
3.88
e
+
00
1.95
e
+
00
1
e
-
4
5.50
e
+
02
2.93
e
+
02
1.51
e
+
02
7.69
e
+
01
3.88
e
+
01
1.95
e
+
01
1
e
-
5
5.50
e
+
03
2.93
e
+
03
1.51
e
+
03
7.69
e
+
02
3.88
e
+
02
1.95
e
+
02
1
e
-
6
5.50
e
+
04
2.93
e
+
04
1.51
e
+
04
7.69
e
+
03
3.88
e
+
03
1.95
e
+
03
1
e
-
7
5.50
e
+
05
2.93
e
+
05
1.51
e
+
05
7.69
e
+
04
3.88
e
+
04
1.95
e
+
04
1
e
-
8
5.50
e
+
06
2.93
e
+
06
1.51
e
+
06
7.69
e
+
05
3.88
e
+
05
1.95
e
+
05Table 7
The maximum norm of the consistency error[
A
N
u
N
-
f
^
N
] on the VS-mesh.
ε
N
=
32
N
=
64
N
=
128
N
=
256
N
=
512
N
=
1024
1
e
-
2
4.67
e
+
00
2.47
e
+
00
1.28
e
+
00
6.59
e
-
01
3.36
e
-
01
1.70
e
-
01
1
e
-
3
4.67
e
+
01
2.47
e
+
01
1.28
e
+
01
6.59
e
+
00
3.36
e
+
00
1.70
e
+
00
1
e
-
4
4.67
e
+
02
2.47
e
+
02
1.28
e
+
02
6.59
e
+
01
3.36
e
+
01
1.70
e
+
01
1
e
-
5
4.67
e
+
03
2.47
e
+
03
1.28
e
+
03
6.59
e
+
02
3.36
e
+
02
1.70
e
+
02
1
e
-
6
4.67
e
+
04
2.47
e
+
04
1.28
e
+
04
6.59
e
+
03
3.36
e
+
03
1.70
e
+
03
1
e
-
7
4.67
e
+
05
2.47
e
+
05
1.28
e
+
05
6.59
e
+
04
3.36
e
+
04
1.70
e
+
04
1
e
-
8
4.67
e
+
06
2.47
e
+
06
1.28
e
+
06
6.59
e
+
05
3.36
e
+
05
1.70
e
+
05By contrast, with preconditioner (20), the preconditioned consistency error converges uniformly in ɛ as shown in Tables 8 and 9.Table 8
The maximum norm of the preconditioned consistency error[
A
~
N
u
N
-
M
f
^
N
] on the BS-mesh.
ε
N
=
32
N
=
64
N
=
128
N
=
256
N
=
512
N
=
1024
1
e
-
2
1.22
e
-
01
6.50
e
-
02
3.38
e
-
02
1.74
e
-
02
8.87
e
-
03
4.52
e
-
03
1
e
-
3
1.14
e
-
01
6.01
e
-
02
3.08
e
-
02
1.56
e
-
02
7.86
e
-
03
3.95
e
-
03
1
e
-
4
1.14
e
-
01
5.97
e
-
02
3.06
e
-
02
1.55
e
-
02
7.78
e
-
03
3.90
e
-
03
1
e
-
5
1.14
e
-
01
5.96
e
-
02
3.05
e
-
02
1.54
e
-
02
7.77
e
-
03
3.90
e
-
03
1
e
-
6
1.14
e
-
01
5.96
e
-
02
3.05
e
-
02
1.54
e
-
02
7.77
e
-
03
3.89
e
-
03
1
e
-
7
1.14
e
-
01
5.96
e
-
02
3.05
e
-
02
1.54
e
-
02
7.77
e
-
03
3.89
e
-
03
1
e
-
8
1.14
e
-
01
5.96
e
-
02
3.05
e
-
02
1.54
e
-
02
7.77
e
-
03
3.89
e
-
03Table 9
The maximum norm of the preconditioned consistency error[
A
~
N
u
N
-
M
f
^
N
] on the VS-mesh.
ε
N
=
32
N
=
64
N
=
128
N
=
256
N
=
512
N
=
1024
1
e
-
2
1.60
e
-
01
9.12
e
-
02
5.02
e
-
02
2.70
e
-
02
1.43
e
-
02
7.47
e
-
03
1
e
-
3
1.50
e
-
01
8.44
e
-
02
4.58
e
-
02
2.42
e
-
02
1.26
e
-
02
6.53
e
-
03
1
e
-
4
1.49
e
-
01
8.37
e
-
02
4.54
e
-
02
2.40
e
-
02
1.25
e
-
02
6.45
e
-
03
1
e
-
5
1.49
e
-
01
8.37
e
-
02
4.53
e
-
02
2.40
e
-
02
1.25
e
-
02
6.44
e
-
03
1
e
-
6
1.49
e
-
01
8.37
e
-
02
4.53
e
-
02
2.40
e
-
02
1.25
e
-
02
6.44
e
-
03
1
e
-
7
1.49
e
-
01
8.37
e
-
02
4.53
e
-
02
2.40
e
-
02
1.25
e
-
02
6.44
e
-
03
1
e
-
8
1.49
e
-
01
8.37
e
-
02
4.53
e
-
02
2.40
e
-
02
1.25
e
-
02
6.44
e
-
03In conclusion, the preconditioning allows us to use Principle1 and combine Lemmas 7 and 10 to obtain the following main convergence result.Theorem 11.
The error of the upwind finite-difference discretization on S-type meshes satisfies(64)
u
i
N
-
U
i
N
≤
C
N
-
1
max
⁡
ψ
′
2
,
i
=
1
,
…
,
J
-
1
,
C
N
-
1
,
i
=
J
,
…
,
N
-
1
.Corollary 12.
For the meshes given in Table1, one has the following estimates:(65)
u
N
-
U
N
≤
C
N
-
1
L
2
,
f
o
r
t
h
e
S
-
m
e
s
h
,
C
N
-
1
,
f
o
r
t
h
e
B
S
-
a
n
d
V
S
-
m
e
s
h
e
s
.Remark 13.
The barrier-function technique can be used to obtain similar results for S-type meshes (see [16]), but it requires another assumption on the mesh-generating function ϕ (cf. [16, Theorem 1]). However, whether the barrier-function approach can be extended to any Bakhvalov-type mesh is still an open question [2, Remark 4.21]. By contrast, as proved in [19], the preconditioner defined in (20) works fine for Vulanović’s modification of the Bakhvalov mesh [10]. The paper [10] is where the original Bakhvalov mesh [20] is generalized (the main difference between Bakhvalov-type meshes and S-type meshes is that the former have a smooth transition from the fine part inside the layer to the coarse uniform part outside the layer; the mesh-generating function ϕ belongs to C
1
(
I
)).


## 6. Conclusion

In this paper we present a proof of pointwise uniform convergence for singularly perturbed convection-diffusion problem (1) discretized on a general class of Shishkin-type meshes. The proof is based on preconditioning of the discrete system, which allows us to use the standard “consistency + stability” principle of convergence. This is a conceptually simple approach which does not require the use of hybrid stability inequalities and discrete Green’s functions. In general, new proof techniques are of interest because although a lot has been achieved in the field of singularly perturbed problems over the last few decades, there are still important questions remaining open [21]. One of them, Question 6, is related to the work presented here. The question is about two-dimensional convection-diffusion problems and it points out that whereas ɛ-uniform pointwise convergence for the upwind finite-difference discretization on S-type meshes is well-established, no similar result for B-type meshes is known. As mentioned in Remark 13, we already know that the preconditioning approach works well for B-mesh and one-dimensional convection-diffusion problems. The next step is to consider two-dimensional problems.



---

*Source: 2161279-2016-02-28.xml*