This paper provides a new application similar to the Local Defect Correction (LDC) technique to solve Poisson problem −
u
′′(
x
) =
ƒ
(
x
) with Dirichlet boundary conditions. The exact solution is supposed to have high activity in some region of the domain. LDC is combined with a fourth order compact scheme which is recently developed in Abbas (Num. Meth. Partial differential equations, 2013). Numerical tests illustrate the interest of this application.
AMS Mathematics Subject Classification : 65N55, 65N55.
1. Introduction
The Local Defect Correction (LDC) method was introduced byW. Hackbusch
[8]
for solving elliptic boundary value problem. LDC is a domain decomposition technique in which the local domain fully overlaps the global one. It is a generic iterative algorithm of multiscale type for the resolution of discrete problem. Two or more grids of calculation can be used. We refer to
[6]
for applications to problems in combustion and numerical simulations of the flow and heat transfer in a glass tank. An analysis of the LDC technique in combination with finite difference discretizations is presented in
[4]
. In
[7]
the method is extended to include adaptivity, multilevel refinement, domain decomposition and regredding. The LDC method is combined with finite volume discretizations in
[5]
and finite elements discretizations in
[1
,
2]
.
Let’s briefly outline the basic version of the LDC technique. Consider the elliptic boundary value problem
where
L
is a linear elliptic differential operator,
ƒ
and
g
are the source term and Dirichlet boundary condition, respectively. To discretize (1), we first choose a global coarse grid (grid spacing
H
), which we denote by Ω
^{H}
. Let
L^{H}
be a discrete operator approximating the continuous operator
L
. An initial approximation
i
= 0, on Ω
^{H}
is obtained by solving the system
In (2), the vector
ƒ
^{H}
contains the source term
ƒ
and the Dirichlet boundary condition
g
as well. Suppose that
L^{H}
is invertible. Moreover, suppose that the exact solution
u
(
x, y
) of (1) has a high activity region in some (small) part of the domain. We select a subdomain Ω
_{l}
⊂ Ω such that the high activity region of
u
is contained in Ω
_{l}
. The subdomain Ω
_{l}
is discretized by a local fine grid (grid spacing
h
). We denote it by
. The fine grid
is built such that
This means that the coarse grid points that lie in the region of refinement are also points of
. In order to formulate a discrete problem on
, we should define artificial boundary conditions on Ґ, the interface between Ω
_{l}
and Ω \ Ω
_{l}
, (
Figure 1
). Actually, we use an interpolation operator
P^{h,H}
to obtain artificial boundary conditions on Ґ. The operator
P^{h,H}
gives the values of the fine grid points on Ґ
^{h}
by interpolating the values of the coarse grid points on the interface Ґ
^{H}
.
Discretization in one dimension. The big points represent the coarse grid Ω^{H}, the small points represent the fine domain .
On
∂
Ω
_{l}
\ Ґ, we obtain boundary conditions using the Dirichlet boundary conditions
g
in (1)
_{b}
. On the fine grid
we consider the following discrete problem, at iteration
i
= 0,
where
In (3),
i
represents an index of iteration and
is a square matrix representing the dependence of the fine grid solution on the artificial boundary conditions on Ґ. In (3), the matrix
(assumed to be invertible) is a discrete approximation of the operator
L
on the subdomain Ω
_{l}
. In the right term in (3),
contains the source term
ƒ
and the Dirichlet boundary condition
g
on
∂
Ω
_{l}
\ Ґ given in (1). Notice that Ґ ∩
∂
Ω can be empty as in the
figure 1
. If we know the values of the defect
d^{H}
=
L^{H}
(
u

_{ΩH}
)−
ƒ^{H}
, we can use it to find more accurate approximation on the coarse grid. This can be obtained by replacing
d^{H}
in the right hand side of (2). However, we do not know the exact solution of the exact continuous problem then we cannot calculate
d^{H}
. We will use
calculated on the fine grid to approximate
d^{H}
. Indeed, for all
i
, index of iteration, the function
is the function on the coarse grid defined by:
For each index of iteration
i
we define
by
Actually,
provides an estimate of the local discrestization error at all points of
. We observed numerically it is better to use the approximation (6) on a proper subset of
only. In particular, the points of the coarse grid near
∂
Ω
_{l}
should be excluded. This leads to introduce a “
Safety region
” denoted by
(
Figure 2
). The estimation of the local error of discretization of the coarse grid is placed in the right hand side of the equations corresponding to coarse grid points belonging to
only. Then we apply the correction step on the coarse
The small points consist of points of Ω^{h}, the big ones are the points of the safety region .
As (7) contains estimations of the local error of the discretization on the coarse grid, we expect
to be a more accurate approximation than
Then we obtain better boundary conditions on Ґ and a solution on the fine local grid by (3) with
i
= 1. By performing the iterations on the index
i
, we obtain the following algorithm:
Algorithm 1.1.
•
Initialization

Solve the problem(2) on the coarse grid
Ω
^{H}
with i
= 0.
We obtain the vector

Solve the problem(3) on the fine local grid
with
_{i = 0}
.
We obtain the vector
•
Iteration i
= 1, 2...

Compute
by (5).

Compute
by (6).

Resolve the problem (7) on the coarse grid
Ω
^{H}
.
We obtain the vector

Solve the problem (3) on the local fine grid
We obtain the vector
In practice, one iteration is enough to obtain a satisafactory approximation on the composite grid Ω
^{H,h}
which is the grid formed by the union of the coarse grid and the fine grid,
The algorithm 1.1 is an elementary version of the LDC method. Several generalizations are possible:
• Use of several fine grids. Notice that the local problems are independent each other and can be solved simultaneously. Recursive refinement where a local fine grid can be a coarse grid for another local fine grid.
• Use of different discretizations. We refer to
[6]
for a detailed analysis of the behavior of the convergence for the Poisson problem solved with classic five points finite difference scheme.
2. Main results
2.1. Analysis of a fourth order scheme.
We recall and analyse a new scheme called hermitian Boxscheme (HBscheme), for the Poisson problem in one dimension based on the previous work
[12]
. This scheme appears to be fourth order accurate in practice. It has been successfully extended to two dimensions in
[9]
and three dimensions in
[10]
. Let’s recall the principle of this scheme. Consider the onedimensional Poisson problem on the interval Ω = (
a, b
) with length
L
=
b
−
a
,
Equation (8) is recast in mixed form:
We lay out on Ω a regular grid
x_{j}
=
a
+
jh
, 0 ≤
j
≤
N
with stepsize
h
=
L/N
, (
Figure 3
). The unknowns are denoted by
u_{j}
≈
u
(
x_{j}
) and
u_{x,j}
≈
u
′(
x_{j}
). The vectors
U
,
U_{x}
∈ ℝ
^{N−1}
stand for the unknowns at internal points,
Grid in dimension 1. The two boundary points x_{0}, x_{N} (denoted by “◦”). The points x_{i}, i = 1, · · · ,N − 1 are the interior points (denoted by “•”).
In analogy to the original boxscheme
[13]
, the HBscheme is deduced from the integration of the two equations (9)
_{a,b}
on a box
K_{j}
=]
x
_{j1}
,
x
_{j+1}
[ of length 2
h
.
Suppose given the averaged values of the source term
ƒ
(
x
) on the box
K_{j}
,
In practice, (11) can be approximated using Simpson formula
The conservation equation (9)
_{a}
becomes
Second, the equation (9)
_{b}
is integrated on the box
K_{j}
. This yields
Approximating the integral in the lefthand side of (14) by Simpson formula suggests the following fourthorder hermitian approximation
Equations (15) require approximations of the derivatives on the boundaries. Here, we consider the following thirdorder approximations
Relations (16) are obtained using Taylor expansions. In summary, the equations (13), (15), (16) with Dirichlet boundary conditions translate to the following HBscheme: Find
u
= (
u_{i}
)
_{0≤i≤N}
and
v
= (
v_{i}
)
_{0≤i≤N}
solution of:
This HBscheme is found numerically to be fourth order accurate as it is shown in the numerical tables.
Lemma 2.1.
Suppose that
Π
^{0}
ƒ_{j} is approximated by Simpson formula:
and
(
u_{j}
)
_{j∈ℤ}
, (
u_{x,j}
)
_{j∈ℤ}
are two sequences verifying
Then
(
u_{j}
)
_{j∈ℤ}
verifies
Proof
. Denote by
E_{j}
,
j
∈
ℤ
, the jth equation of (19)
_{a}
. Using the sum
and (19)
_{b}
, we find that the left term of (21) verifies
The right term of (21) verifies
where the equality (20) for
j
∈ ℤ.
We refer to
[11]
for a detailed proof of the following lemma concerning the maximum principles of the standard three point Laplacian scheme.
Lemma 2.2.
Let u
= (
u_{i}
)
_{0≤i≤N}
.
Suppose that
then
Similarly, if
then
The scheme (17) verifies the following discrete maximum and minimum principles.
Proposition 2.1
(Principles of maximum and minimum).
Let u
= (
u_{i}
)
_{0≤i≤N}
be the solution of HBscheme (17). Suppose that ƒ_{i}
≤ 0, ∀ 1 ≤
i
≤
N
− 1,
then
Similarly, if ƒ_{i}
≥ 0, ∀ 1 ≤
i
≤
N
− 1,
u verifies
This means that u attains its maxima and minima on the boundary points x
_{0}
and x_{N}
.
Proof
. Suppose that
ƒ_{i}
≤ 0, ∀ 1 ≤
i
≤
N
− 1 then
By (20),
If
N
is even, using the maximum principle of Lemma 2.2 we obtain
In the same manner if
N
is odd, we obtain
It results for all
N
,
Then to prove (25) it is enough to prove that
Suppose that
We have
This gives
u
_{x,0}
≤
u
_{x,2}
and
u
_{x,1}
≤
u
_{x,3}
. The HBscheme (17) verifies
Moreover,
Therefore,
But we have
u
_{2}
≤
u
_{0}
, then
therefore
where (32). Suppose that
The equations (17) give
In addition, using (34),
u
_{x,N−2}
≤
u_{x,N}
, therefore
as
u
_{N−1}
≥
u
_{N−3}
, and
u_{N}
≥
u
_{N−2}
, we get
We deduce
where
Finally,
where (25). In the same manner we can prove the minimum principle (26).
Corollary 2.1
(existence and uniqueness of solution).
The HBscheme (17) has unique solution
Proof
. We have (17) a linear system with 2
N
equations and 2
N
unknowns. To prove the existence and uniqueness of the solution, it is enough to prove that Π
^{0}
ƒ
_{i}
= 0, 1 ≤
i
≤
N
− 1, implies
u
=
v
=
0
. Let
u
= (
u_{i}
)
_{0≤i≤N}
and
v
= (
v_{i}
)
_{0≤i≤N}
such that
Using the discrete maximum principle of proposition 2.1, we obtain
then
which proves that the matrix associated to the HBscheme (17) has nul kernel. As it is square matrix then it is invertible, where the existence and uniqueness of the solution of HBscheme.
2.2. Matrix form of hermitian Boxscheme.
We summarize the finitedifference and matrix notations used in the sequel.
• The tridiagonal matrix
is
• The Simpson matrix
P_{s}
∈
is
where
I
is the identity matrix of order
N
− 1.
• The antisymmetric matrix
K
∈
given by
• Denoting (
e_{i}
)
_{1≤i≤N−1}
the canonical basis of ℝ
^{N−1}
, the matrices
F
_{1}
,
F
_{2}
∈
are defined by
Let us turn now to the matrix form of the scheme. We use the notation
U_{L}
=
u
_{0}
,
U_{R}
=
u_{N}
,
u_{x,L}
=
u
_{x,0}
,
u_{x,R}
=
u_{x,N}
for the boundary values.
Proposition 2.2.
For all linear approximation of the derivatives on the boundary U_{x,L}, U_{x,R} in terms of U, U_{x} and the values on the boundary U_{L}, U_{R}, there exist matrices
such that
Proof
. Any linear approximation of
u
_{x,0}
in terms of
u
= (
u_{i}
)
_{0≤i≤N}
,
u_{x}
= (
u_{x,i}
)>)
_{0≤i≤N}
and
u
_{0}
,
u_{N}
can be written in general form as:
with
Similarly,
with
Multiplying (53) by
e
_{1}
and (54) by
e
_{N−1}
we get
Adding the equations (55) together
Using the fact that
and
we can write (56) as
Finally to complete the proof, let
be the matrices
We claim that (16) translates into matrix form as
[9]
where the matrices
A, B, C
are given by
and the vector of derivative is given in terms of
U
and the boundary conditions by
where the matrices
D
and
ε
are
Using (59) and (61),
U_{x}
can be eliminated which gives the expression of the HBscheme in the sole unknown
U
as
where
F
= [Π
^{0}
ƒ
_{1}
, · · · , Π
^{0}
ƒ
_{N1}
]
^{T}
(Π
^{0}
ƒ_{j}
is given in (11)). The matrices
are
If needed, the gradient is recovered as a postprocessing by (61).
2.3. Twogrid refinement algorithm.
Here, a multiscale technique is combined with the hermitian Boxscheme. We consider the problem
The domain Ω is discretized with stepsize
H
= 1/
N
such that the discrete coarse points are
The coarse grid is Ω
^{H}
. The unknowns vectors are
U^{H}
and
such that
To avoid any confusion between variables, we perform a change of notations for the sequel
The hermitian Boxscheme corresponding to the problem (65) has the following matrix form
with
F
=
F
= [Π
^{0}
ƒ
_{1}
, Π
^{0}
ƒ
_{2}
, Π
^{0}
ƒ
_{N1}
]
^{T}
. By comparing with (2), let
By resolving (67) we obtain the solution vector
i
= 0, on Ω
^{hc}
and the global vector solution
The domain Ω
_{l}
has been choosen such that Ω
_{l}
= (
a
_{1}
,
b
_{1}
), with
a
_{1}
,
b
_{1}
two fixed scalars between
a
and
b, a
≤
a
_{1}
<
b
_{1}
≤
b
. The choice of
a
_{1}
and
b
_{1}
is adapted such that for all
N
there exist
i
_{0}
and
j
_{0}
between 1 and
N
− 1 such that
that is to say
a
_{1}
and
b
_{1}
are two points of the coarse grid Ω
^{hc}
. In order that
has the same number of points as Ω
^{H}
, we choose
a
_{1}
and
b
_{1}
such that
Suppose that we know the values
g
_{a1}
=
u
(
a
_{1}
) and
g
_{b1}
=
u
(
b
_{1}
) where
u
(
x
) is the exact solution. Hence, on the domain Ω
_{l}
we can write
with
u_{l}
=
u

_{Ωl}
and
ƒ_{l}
=
ƒ

_{Ωl}
. The domain Ω
_{l}
is discretized with stepsize
such that the discrete fine points are
with
Notice the equality between
N
and
N_{ƒ}
when
The fine grid is
The unknown vectors are
such that
and
1 ≤
i
≤
N
− 1. The interface between Ω
_{l}
and Ω is
∂
Ω
_{l}
= {
a
_{1}
,
b
_{1}
}. Based on the matrix form (63), the hermtian Boxscheme corresponding to (71) is
with
F_{l}
= [Π
^{0}
ƒ
_{1}
, Π
^{0}
ƒ
_{2}
, ..., Π
^{0}
ƒ
_{N1}
]
^{T}
∈ ℝ
^{N1}
. The problem is that we do not know the values
g
_{a1}
and
g
_{b1}
on
∂
Ω
_{l}
in (71). To approach these values, we replace it by artificial boundary conditions
with
i
_{0}
and
j
_{0}
are the indices of the points
a
_{1}
and
b
_{1}
in the coarse grid defined in (70). Here, in particular, the artificial boundary
∂
Ω
_{l}
= {
a
_{1}
,
b
_{1}
} is composed of two points of the coarse grid Ω
^{hc}
then there is no need to interpolate therefore the matrix
is zero. By comparing (72) and (3), let
By solving (72) with
i
= 0 we get
then we obtain the approximation
Following (5) the vector
verifies
The defect vector
is calculated by
Finally, the algorithm is the following:
Algorithm 2.1.
•
Initialization

Solve the problem (67) on the coarse grid
Ω
^{hc}
.
The vector solution is denoted by

Solve the problem (75) on the local grid
The vector solution is denoted by
•
Iteration i
= 1, 2, ...

Compute the vector
by (76).

Compute the defect vector
by (77).

Solve on the coarse grid
with ε
> 0.
The solution vector is denoted by

Solve the problem (75) on the fine grid. The vector solution is denoted by
2.4. Numerical results.
In this part, we display some numerical results proving the interest of the technique presented in the last section. The calculation is performed using Matlab. The CPU time is calculated by the functions tic and toc. Notice that the CPU time can be extremely reduced using FFT or another programming language
[3]
. The algorithm used so far is the algorithm 2.1 after only one iteration. We intend to study in another paper the behavior of the convergence of this algorithm. In the numerical tables,
u_{ex}
,
u_{x,ex}
are the exact solution and derivative,
u
,
u_{x}
are the computed solution and derivative on the uniform grid and
are the computed solution and derivative on the composite domain. We use the discrete norm
L
^{∞}
to estimate the error:
The convergence rate is calculated using the formula
where
e_{N}
is the error obtained on a mesh of size
N
.
Error and convergence rate for Test 1 on uniform grid
Error and convergence rate for Test 1 on uniform grid
Error and convergence rate for Test 1 on composite grid
Error and convergence rate for Test 1 on composite grid
Test 1:
We consider the Gaussian function
This function has a high activity region around
The results obtained on the composite grid are compared with those computed by the HBscheme on the uniform grid with fine stepsize
h_{ƒ}
. Observe in tables 1 and 2 the same accuracy obtained by the two approaches with less points on the composite grid.
Test 2:
Suppose that the exact solution is
on Ω = (0, 1). This function has a deep gradient around
We choose
The numerical results are given in tables 3 and 4.
3. Conclusion
This paper provides a new application of the multiscale technique combined with a new high order scheme called HBscheme. The high order accuracy of this scheme is particularly interesting in applications where physical fields have to be calculated as an outcome of a potential solution of a Poisson problem (electromagnetism, gravitation). The main features of this work are the high order of precision on the boundaries and the calculation of the derivatives. This application illustrates the gain in memory and CPU time using this technique as it is shown in the numerical tables. For instance, we have obtained for Test 1 the same precision using 3072 points instead of 4096. This gain is expected to be more interesting in higher dimensions. A generalization of this application to higher dimensions using cubic spline interpolations, based on the previous results in
[9
,
10]
will be a part of future work.
Error and convergence rate for Test 2 on uniform grid
Error and convergence rate for Test 2 on uniform grid
Error and convergence rate of Test 2 on composite grid
Error and convergence rate of Test 2 on composite grid
BIO
Ali Abbas received Ph.D at University of Paul Verlaine, France. Since 2012, he has been at Lebanese International University. His research interests include finite differences and finite volumes methods.
Department of Mathematics, Lebanese International University, RayakBekaa, Lebanon.
email: ali.abbas@liu.edu.lb
Huang P.
,
Feng X.
,
Su H.
(2012)
A new defectcorrection method for the stationary NavierStokes equations based on local Gauss integration
Mathematical Methods in the Applied Sciences
35
1033 
1046
DOI : 10.1002/mma.1618
Huang P.
,
Feng X.
,
He Y.
(2013)
Twolevel defect correction Oseen iterative stabilized finite element methods for the stationary NavierStokes equations
Applied Mathematical Modelling
37
728 
741
DOI : 10.1016/j.apm.2012.02.051
Abbas A.
2011
Schémas compacts hermitiens Algorithmes rapides pour la discrétisation des équations aux dérivées partielles
Univ. Paul Verlaine  Metz
Ferket Peter J. J.
,
Reusken Arnold A.
(1996)
A finite difference discretization method on composite grids
Computing
56
343 
369
DOI : 10.1007/BF02253460
Hof Bas van ’t
1998
Numerical aspects of laminar flame simulation
Eindhoven University of Technology  Eindhoven
Anthonissen M.G.H.
2001
Local Defect correction Techniques : Analysis and Application to combustion
Eindhoven University of Technology
Ferket P.J.J.
,
Reusken A.A.
(1996)
Further Analysis of the Local Defect Correction Method
Computing
56
117 
139
DOI : 10.1007/BF02309341
Hackbush W.
(1984)
Local Defect Correction Method and Domain Decomposition Techniques
Computing
5
89 
113
Abbas A.
,
Croisille JP.
(2011)
A fourth order Hermitian BoxScheme with fast solver for the Poisson problem in a square
J. Sci. Comput
49
239 
367
DOI : 10.1007/s109150109458y
Abbas A.
2013
A fourth order Hermitian BoxScheme with fast solver for the Poisson problem in a cube, Numer. Methods. Partial differential equations
BenArtzi M.
,
Croisille JP.
,
Fishelov D.
2013
NavierStokes equations in planar domains
Imperial College Press
Croisille JP.
(2006)
A Hermitian BoxScheme for onedimensional elliptic equations  Application to problems with high contrasts in the ellipticity
Computing
78
329 
353
DOI : 10.1007/s0060700601813
Keller H. B.
1971
A new difference scheme for parabolic problems
Academic Press