Outline

1. Source

2. Introduction

3. Estimating Errors in Numerical Solutions

References
RJL Chapter: 1.0
JCS Sections 1.1 - 1.3
◮ The goal is to find an approximate solution to a
continuous problem using some discrete approximations;
◮ In the approach, we replace continuous derivatives with
difference approximations, given the values of the
function at given discrete points;
◮ The resulting finite algebraic system of equations can be
solved in place of the original differential equation (the
continuous problem);
◮ ...but first, let us develop the tools we will need.
Let us assume u(x) is a smooth, differentiable function, of a
single variable containing a point c, say.

h h

u(x)

c −h c c +h x

Figure: Schematic representation of the slope at x = c.

Objective: how would you approximate u ′ (c) given, say u(c),

u(x − c) and u(x + c)?
Consider the schematic figure above: To approximate u ′ (c) by
the finite difference approximation, we may use the following
linear operators,

v (c + h) − v (c)
δ + u(c) = ,
h
v (c) − v (c − h)
δ − u(c) = ,
h
v (c + h/2) − v (c − h/2)
δ 0 u(c) = .
h
See Fig. 4. The operator δ 0 is called the centered operator,
whereas the first one is forward and the second backward.
Example 1
Let u(x) = sin(x) and c = 1. Thus we try and approximate
u ′ (1) = cos(1) = 0.5403023. In Table 1 we show the error
δu(c) − u ′ (c) for various values of h.

h δ + u(x) δ − u(x) δ 0 u(x) δ 3 u(x)

1.0e-1 -4.2939e-02 4.1138e-02 -9.0005e-04 6.8207e-05
5.0e-2 -2.1257e-02 2.0807e-02 -2.2510e-04 8.6491e-06
1.0e-2 -4.2163e-03 4.1983e-03 -9.0050e-06 6.9941e-08
5.0e-3 -2.1059e-03 2.1014e-03 -2.2513e-06 8.7540e-09
1.0e-3 -4.2083e-04 4.2065e-04 -9.0050e-08 6.9979e-11
Table: Errors in various finite difference approximations
◮ We see that

1. δ + u − u ′ (c) ≈ −0.42h
2. δ 0 u − u ′ (c) ≈ −0.09h2
3. δ 3 u − u ′ (c) ≈ 0.007h3

confirming that these methods are 1st , 2nd and 3rd order
accurate respectively.
◮ By including more terms, greater accuracy may be obtained.
◮ The standard way to analyse the error in the
approximations, is to expand each term in a Taylor
series...
Theorem 1
The operators

1. δ + u(c) → u ′ (c) 


2. δ − u(c) → u ′ (c) as h→0

3. δ 0 u(c) → u ′ (c)

Definition 1
We say δu(x) is a consistent approximation of u ′ (x) if

δu(x) → u ′ , as h → 0.

If furthermore, the error |δ + u − u ′ | thus committed is bounded

up to a multiplicative constant, by hp then the approximation
is said to be consistent of order p, i.e.,

|δ + u − u ′ | ≤ Chp .
Definition 2 (Big-O, O(·),)
If f (h) and g (h) are two functions of h, we say that
f (h) = O(g (h)) as h → 0if there exist a constant c such that
f (h)
< c for h sufficiently small, or equivalently, if we can
g (h)
bound |f (h)| < c |g (h)| for h sufficiently small.

Example 2
Consider, for example, the exponential series and two
expressions of it that are valid when x is small:

x2 x3 x4
ex = 1 + x + + + + ··· for all x
2! 3! 4!
x2
=1+x + + O(x 3 )
2!
= 1 + x + O(x 2 )
Example 3
Consider the Taylor series expansion

h2 ′′
u(x + h) = u(x) + hu ′ (x) + u (x) + O(h3 )
2
Rearranging, we have

u(x + h) − u(x) h
= u ′ (x) + u ′′ (x) + O(h2 ),
h 2
and now
h ′′ u ′′ (x)
|δ + u − u ′ | ≈ u (x) ≈ h = hC
2 2
Example 4
Show that
u(x + h) − u(x − h)
h
is not a consistent approximation of u ′ (x).
Notes
◮ Consider the second order centered approximation

u(x − h) − 2u(x) + u(x + h)

δ 2 u(x) =
h2
h 2
= u ′′ (x) + u ′′′ (x) + O(h4 )
12

◮ Note, we can also write

δ 2 u(x) = δ + δ − u(x) = δ − δ + u(x).

◮ Higher order approximations can be derived in several

different ways, e.g.,
◮ method of undetermined coefficients, or
◮ repeated application of lower order approximations.
Example 5
Show that
u(x + 2h) − 3u(x + h) + 3u(x) − u(x − h)
δ + δ 2 u(x) =
h3
h
= u ′′′ (x) + u iv (x) + O(h2 ),
2
which gives an approximation of u ′′′ (x) is of O(h)
Lemma 1
If u is 4 times differentiable in the interval [x − h, x + h]
then
u(x − h) − 2u(x) + u(x + h)
δ0δ0u = δ+δ−u = δ−δ+u = ,
h2
is a second order approximation to u ′′ (x).
Proof.
We will only prove the left hand statement. Consider the
definition of δ 0 , and write
" #
h h
u(x + ) − u(x − )
δ0 2 2
h
 
1 0 h 0 h
= δ u(x + ) − δ u(x − )
h 2 2
" #
1 u(x + 2 + 2 ) − u(x − h2 + h2 ) u(x − h2 + h2 ) − u(x − h2 − h2 )
h h
= −
h h h
1
= [u(x + h) − 2u(x) + u(x − h)]
h2
This is only part of the proof. We leave the rest of the
proof for the reader.
Example 6
Note, we can also write

u ′′′′ = uxxxx = (uxx )xx ∼ δ 2 (δ 2 u)

 
2 u(x − h) − 2u(x) + u(x + h)
=δ
h2
= ...
Notation
◮ The aim is to compute a grid function consisting of values
v0 , v1 , . . . , vM , vM+1 , where vm is an approximation to the
solution, i.e., u(xm );
◮ Here xm = mh, and is the mesh width, i.e., the distance
between grid points;
◮ Throughout, we will assume a uniform mesh width, so that
h = xm − xm−1 .
◮ We can now write

vm+2 ≈ u(xm+2 ) = u(x + 2h)

so that
vm+1 − 2vm + vm−1
δ 2 vm =
h2
Some examples of forward difference representations and
backward difference representations are given in Tables 2 and
Table 3.
vm vm+1 vm+2 vm+3 vm+4
hu ′ (xm ) -1 1
h2 u ′′ (xm ) 1 -1 1
h3 u ′′′ (xm ) -1 3 -3 1
h4 u iv (xm ) 1 -4 6 -4 1
Table: Forward difference representations of O(h).
 vm vm+1 vm+2 vm+3 vm+4 vm+5
2hu ′ (x m) -3 4 -1
h2 u ′′ (xm ) 2 -5 4 -1
2h3 u ′′′ (xm ) -5 18 -24 14 -3
h4 u iv (xm ) 3 -14 26 -24 11 -1
Table: Forward difference representations of O(h2 ).
Notes
◮ The local truncation error (LTE) is defined by replacing
the approximation, vm with the true solution u(xm ).
◮ In general, this won’t be satisfied exactly, and the
discrepancy is the LTE. Consider Exercise 5, the LTE is
h (iv )
τm = δ + δ 2 u − u ′′′ = u (x) + O(h2 ).
2

◮ Although u (iv ) is in general unknown, it is fixed and

independent of h so that τm = O(h) as h → 0.
Notes
◮ In general, we consider finite difference schemes by
defining a grid of points in the (t, x) plane.
◮ Let h and k be some positive numbers, then the grid will
have point (tn , xm ) = (nk, mh) for some integers n and m.
◮ Thus we write vm n for a function value at grid point

(tn , xm ).

k
h

Figure: The finite difference grid.

Notes
◮ Suppose we want to compute a solution of a particular
equation with a true solution u: If we denote the
computed solution by v , then the absolute error E is
|E | = |v − u|.
◮ The differences below are a result of a poor choice of the
scaling.

Example 7
If suppose u = 1.3 m and the numerical approximation is
v = 1.30345 m, then the absolute error is
|E | = |v − u| = 0.00345 = 3.45 × 10−3 .

Example 8
Now consider the above example, but instead, we change the
units of measurement to nonometers so that u = 1.3 × 109 nm and
v = 1.30345 × 109 nm. The absolute error is now
|v − u| = 3.45 × 106 .
Notes
◮ We define the relative error as
|v − u|
|u|

so that whatever the units, like in the above examples, we

will get

Example 9

|v − u| |1.30345 − 1.3|
= = 0.00265 = 2.56 × 10−3 .
|u| |1.3|
◮ If we suppose u ∈ Rn , i.e., solution with n components.
◮ For example, a solution of a PDE at n discrete points.
Here we use the vector norm to define the error e = u − v .
◮ A common choice is the max-norm (infinity norm) denoted by
k·k∞
kek∞ = max |em |.
1≤i≤n

◮ Other norms frequently used are the ℓ1 and the ℓ2

v
n
X
u n
uX
kek1 = |em |, kek2 = t |em |2 ,
i=1 i=1

which are special cases of the general q − norm, q ≥ 1

n
!1/q
X
kekq = |em |q
i=1
Notes
◮ A natural question to ask is whether the convergence of
numerical results will depend on the choice of norm used.
◮ If suppose e(h) is the error obtained with some step size
h and that ke(h)k = O(hp ).
◮ Then is it possible the rate will be different in some
other norm.
◮ The answer is ’no’ due to the ’norm equivalence’ result.
Theorem 2 (Norm equivalence)
Let k·kα and k·kβ represent two different vector norms on Rn ,
then there exists two constants C1 and C2 such that

C1 kxkα ≤ kxkβ ≤ C2 kxkα .

Here we note that one can easily verify the following,

√
kxk2 ≤ kxk1 ≤ n kxk2
√
kxk∞ ≤ kxk2 ≤ n kxk∞
kxk∞ ≤ kxk1 ≤ n kxk∞ .

If we suppose that ke(h)kα ≤ Chp ass h → 0 in some norm k·kα ,

then
ke(h)kβ ≤ C2 ke(h)kα ≤ C2 Chp
so that ke(h)kβ = O(hp ) as well.
Notes
◮ Suppose we have an exact solution of a given differential
equation.
◮ We denote eh the error in the calculation when a grid
spacing h is used. We can write

eh = ku(h) − v (h)k

where u(h) is the exact solution solution evaluated at the

same grid and v (h) is the numerical solution.
◮ If the scheme is p order accurate, then

eh ≈ Chp , as h → 0.
◮ If we refine our grid by a factor of 2, then

eh/2 ≈ C (h/2)p

and taking the ratio of the errors,

eh
R= ≈ 2p or p ≈ log2 (R).
eh/2

◮ Note that for a general refinement of grid spacing h1 and

h2 we have

Ch1p
 p
eh1 h1 log(eh1 /eh2 )
≈ 2
= so that p ≈ .
eh2 Ch2 h2 log(h1 /h2 )

◮ If we can afford to rum computations on a fine grid, we

can use the solution as the ‘exact’ and the above
procedure can be applied.