4Expressing errors in terms of derivatives
IB Numerical Analysis
4 Expressing errors in terms of derivatives
As before, we approximate a linear functional L by
L(f) ≈
n
X
i=0
a
i
L
i
(f),
where
L
i
are some simpler linear functionals, and suppose this is exact for
f ∈ P
k
[x] for some k ≥ 0.
Hence we know the error
e
L
(f) = L(f) −
n
X
i=0
a
i
L
i
(f) = 0
whenever
f ∈ P
k
[
x
]. We say the error annihilates for polynomials of degree less
than k.
How can we use this property to generate formulae for the error and error
bounds? We first start with a rather simple example.
Example. Let L(f) = f(β). We decide to be silly and approximate L(f) by
L(f) ≈ f(α) +
β − α
2
(f
0
(β) + f
0
(α)),
where α 6= β. This is clearly much easier to evaluate. The error is given by
e
L
(f) = f(β) − f (α) −
β − α
2
(f
0
(β) + f
0
(α)),
and this vanishes for f ∈ P
2
[x].
How can we get a more useful error formula? We can’t just use the fact that
it annihilates polynomials of degree
k
. We need to introduce something beyond
this — the k + 1th derivative. We now assume f ∈ C
k+1
[a, b].
Note that so far, everything we’ve done works if the interval is infinite, as long
as the weight function vanishes sufficiently quickly as we go far away. However,
for this little bit, we will need to require [
a, b
] to be finite, since we want to make
sure we can take the supremum of our functions.
We now seek an exact error formula in terms of
f
(k+1)
, and bounds of the
form
|e
L
(f)| ≤ c
L
kf
(k+1)
k
∞
for some constant
c
L
. Moreover, we want to make
c
L
as small as possible. We
don’t want to give a constant of 10 million, while in reality we can just use 2.
Definition
(Sharp error bound)
.
The constant
c
L
is said to be sharp if for any
ε > 0, there is some f
ε
∈ C
k+1
[a, b] such that
|e
L
(f)| ≥ (c
L
− ε)kf
(k+1)
ε
k
∞
.
This makes it precise what we mean by
c
L
“cannot be better”. This doesn’t
say anything about whether
c
L
can actually be achieved. This depends on the
particular form of the question.
To proceed, we need Taylor’s theorem with the integral remainder, i.e.
f(x) = f(a) + (x −a)f
0
(a) + ···+
(x − a)
k
k!
f
(k)
(a) +
1
k!
Z
x
a
(x −θ)
k
f
(k+1)
(θ) dθ.
This is not really good, since there is an
x
in the upper limit of the integral.
Instead, we write the integral as
Z
b
a
(x − θ)
k
+
f
(k+1)
(θ) dθ,
where we define (x − θ)
k
+
is a new function defined by
(x − θ)
k
+
=
(
(x − θ)
k
x ≥ θ
0 x < θ.
Then if λ is a linear functional that annihilates P
k
[x], then we have
λ(f) = λ
1
k!
Z
b
a
(x − θ)
k
+
f
(k+1)
(θ) dθ
!
for all f ∈ C
k+1
[a, b].
For our linear functionals, we can simplify by taking the
λ
inside the integral
sign and obtain
λ(f) =
1
k!
Z
b
a
λ((x − θ)
k
+
)f
(k+1)
(θ) dθ,
noting that
λ
acts on (
x − θ
)
k
+
∈ C
k−1
[
a, b
] as a function of
x
, and think of
θ
as
being held constant.
Of course, pure mathematicians will come up with linear functionals for
which we cannot move the
λ
inside, but for our linear functionals (point values,
derivative point values, integrals etc.), this is valid, as we can verify directly.
Hence we arrive at
Theorem
(Peano kernel theorem)
.
If
λ
annihilates polynomials of degree
k
or
less, then
λ(f) =
1
k!
Z
b
a
K(θ)f
(k+1)
(θ) dθ
for all f ∈ C
k+1
[a, b], where
Definition (Peano kernel). The Peano kernel is
K(θ) = λ((x − θ)
k
+
).
The important thing is that the kernel
K
is independent of
f
. Taking suprema
in different ways, we obtain different forms of bounds:
|λ(f)| ≤
1
k!
Z
b
a
|K(θ)| dθkf
(k+1)
k
∞
Z
b
a
|K(θ)|
2
dθ
!
1
2
kf
(k+1)
k
2
kK(θ)k
∞
kf
(k+1)
k
1
.
Hence we can find the constant
c
L
for different choices of the norm. When
computing c
L
, don’t forget the factor of
1
k!
!
By fiddling with functions a bit, we can show these bounds are indeed sharp.
Example. Consider our previous example where
e
L
(f) = f(β) − f (α) −
β − α
2
(f
0
(β) + f
0
(α)),
with exactness up to polynomials of degree 2. We wlog assume α < β. Then
K(θ) = e
L
((x − θ)
2
+
) = (β − θ)
2
+
− (α − θ)
2
+
− (β − α)((β − θ)
+
+ (α − θ)
+
).
Hence we get
K(θ) =
0 a ≤ θ ≤ α
(α − θ)(β − θ) α ≤ θ ≤ β
0 β ≤ θ ≤ b.
Hence we know
e
L
(f) =
1
2
Z
β
α
(α − θ)(β − θ)f
000
(θ) dθ
for all f ∈ C
3
[a, b].
Note that in this particular case, our function
K
(
θ
) does not change sign on
[a, b]. Under this extra assumption, we can say a bit more.
First, we note that the bound
|λ(f)| ≤
1
k!
Z
b
a
K(θ) dθ
kf
(k+1)
k
∞
can be achieved by
x
k+1
, since this has constant
k
+ 1th derivative. Also, we
can use the integral mean value theorem to get the bound
λ(f) =
1
k!
Z
b
a
K(θ) dθ
!
f
(k+1)
(ξ),
where ξ ∈ (a, b) depends on f . These are occasionally useful.
Example.
Continuing our previous example, we see that
K
(
θ
)
≤
0 on [
a, b
],
and
Z
b
a
K(θ) dθ = −
1
6
(β − α)
3
.
Hence we have the bound
|e
L
(f)| ≤
1
12
(β − α)
3
kf
000
k
∞
,
and this bound is achieved for x
3
. We also have
e
L
(f) = −
1
12
(β − α)
3
f
000
(ξ)
for some f-dependent value of some ξ ∈ (a, b).
Finally, note that Peano’s kernel theorem says if
e
L
(
f
) = 0 for all
f ∈ P
k
[
x
],
then we have
e
L
(f) =
1
k!
Z
b
a
K(θ)f
(k+1)
(θ) dθ
for all f ∈ C
k+1
[a, b].
But for any other fixed
j
= 0
, ··· , k −
1, we also have
e
L
(
f
) = 0 for all
f ∈ P
j
[x]. So we also know
e
L
(f) =
1
j!
Z
b
a
K
j
(θ)f
(j+1)
(θ) dθ
for all f ∈ C
j+1
[a, b]. Note that we have a different kernel.
In general, this might not be a good idea, since we are throwing information
away. Yet, this can be helpful if we get some less smooth functions that don’t
have k + 1 derivatives.