03 truncation errors

1. 1
Part 3
Truncation Errors

2. 2
Key Concepts
•Truncation errors
•Taylor's Series
–To approximate functions
–To estimate truncation errors
•Estimating truncation errors using other
methods
–Alternating Series, Geometry series,
Integration

3. 3
Introduction
...),log(,,,),cos(),sin( xxxexx
yx
on a computer using only +, -, x, ÷?
How do we calculate
One possible way is via summation of infinite
series. e.g.,
...
)!1(!
...
!3!2
1
132
+
+
++++++=
+
n
x
n
xxx
xe
nn
x

4. 4
Introduction
•How to derive the series for a given function?
•How many terms should we add?
or
•How good is our approximation if we only sum
up the first N terms?
...
)!1(!
...
!3!2
1
132
+
+
++++++=
+
n
x
n
xxx
xe
nn
x

5. 5
A general form of approximation is in
terms of Taylor Series.

6. 6
Taylor's Theorem: If the function f and its first n+1
derivatives are continuous on an interval containing a
and x, then the value of the function at x is given by
n
n
n
Rax
n
af
ax
af
ax
af
axafafxf
+-+
+-+-+-+=
)(
!
)(
...)(
!3
)(
)(
!2
)("
))((')()(
)(
3
)3(
2
ò
+-
=
x
a
n
n
n
dttf
n
tx
R )(
!
)(
)1(
where the remainder R
n
is defined as
(the integral form)
Taylor's Theorem

7. 7
1
)1(
)(
)!1(
)(
+
+
-
+
=
n
n
n ax
n
cf
R
The remainder R
n
can also be expressed as
Derivative or Lagrange Form of the remainder
for some c between a and x
(the Lagrange form)
The Lagrange form of the remainder makes
analysis of truncation errors easier.

8. 8
•Taylor series provides a mean to approximate any
smooth function as a polynomial.
•Taylor series provides a mean to predict a function
value at one point x in terms of the function and its
derivatives at another point a.
•We call the series "Taylor series of f at a" or "Taylor
series of f about a".
Taylor Series
n
n
n
Rax
n
af
ax
af
ax
af
axafafxf
+-+
+-+-+-+=
)(
!
)(
...)(
!3
)(
)(
!2
)("
))((')()(
)(
3
)3(
2

9. 9
Example – Taylor Series of e
x
at 0
...
!
...
!3!2
1
...)0(
!
)0(
...)0(
!2
)0("
)0)(0(')0(
becomes 0at of seriesTaylor the,0With
.0any for 1)0( Thus
0any for )()(")(')(
32
)(
2
)(
)(
++++++=
+-++-+-+
=
³=
³==>==>==>=
n
xxx
x
x
n
f
x
f
xff
fa
kf
kexfexfexfexf
n
n
n
k
xkxxx
Note:
Taylor series of a function f at 0 is also known as the
Maclaurin series of f.

10. 10
Exercise – Taylor Series of cos(x) at 0

0)0()sin()(1)0()cos()(
0)0()sin()(1)0(")cos()("
0)0(')sin()('1)0()cos()(
)5()5()4()4(
)3()3(
==>-===>=
==>=-==>-=
==>-===>=
fxxffxxf
fxxffxxf
fxxffxxf
å
¥
=
-=
+-+++-+=
+-++-+-+
=
0
2
642
)(
2
)!2(
)1(
...
!6
0
!4
0
!2
01
...)0(
!
)0(
...)0(
!2
)0("
)0)(0(')0(
becomes 0at of seriesTaylor the,0 With
n
n
n
n
n
n
x
xxx
x
n
f
x
f
xff
fa

11. 11
Question
What will happen if we sum up only the first n+1
terms?
...
)!1(!
...
!3!2
1
132
+
+
++++++=
+
n
x
n
xxx
xe
nn
x

12. 12
Truncation Errors
Truncation errors are the errors that result from
using an approximation in place of an exact
mathematical procedure.
...
)!1(!
...
!3!2
1
132
+
+
++++++=
+
n
x
n
xxx
xe
nn
x
Approximation Truncation Errors
Exact mathematical formulation

13. 13
How good is our approximation?
How big is the truncation error if we only sum up
the first n+1 terms?
...
)!1(!
...
!3!2
1
132
+
+
++++++=
+
n
x
n
xxx
xe
nn
x
To answer the question, we can analyze the
remainder term of the Taylor series expansion.
n
n
n
Rax
n
af
ax
af
ax
af
axafafxf
+-+
+-+-+-+=
)(
!
)(
...)(
!3
)(
)(
!2
)("
))((')()(
)(
3
)3(
2

14. 14
Analyzing the remainder term of the
Taylor series expansion of f(x)=e
x
at 0
1
)1(
)(
)!1(
)(
+
+
-
+
=
n
n
n ax
n
cf
R
The remainder R
n
in the Lagrange form is
for some c between a and x
For f(x) = e
x
and a = 0, we have f
(n+1)
(x) = e
x
. Thus
1
1
)!1(
]0[in somefor
)!1(
+
+
+
£
+
=
n
x
n
c
n
x
n
e
, xcx
n
e
R
We can estimate the largest possible
truncation error through analyzing R
n
.

15. 15
Example
Estimate the truncation error if we calculate e as
!7
1
...
!3
1
!2
1
!1
1
1 +++++=e
This is the Maclaurin series of f(x)=e
x
with x = 1 and
n = 7. Thus the bound of the truncation error is
48
1
17
7
106742.0
!8
)1(
!8)!17(
-+
´»==
+
£
ee
x
e
R
x
The actual truncation error is about 0.2786 x 10
-4
.

16. 16
Observation
For the same problem, with n = 8, the bound of the truncation
error is
5
8 107491.0
!9
-
´»£
e
R
More terms used implies better approximation.
With n = 10, the bound of the truncation error is
7
10 106810.0
!11
-
´»£
e
R

17. 17
Example (Backward Analysis)
...
!
...
!3!2
1
32
++++++=
n
xxx
xe
n
x
If we want to approximate e
0.01
with an error
less than 10
-12
, at least how many terms are
needed?
This is the Maclaurin series expansion for e
x

18. 18
xnx
exfexfcx ==>=££=
+
)()(,01.00,01.0With
)1(
To find the smallest n such that R
n
< 10
-12
, we can find
the smallest n that satisfies
121
10)01.0(
)!1(
1.1
-+
<
+
n
n
Note:1.1
100
is about 13781 > e
With the help of a computer:
n=0 Rn=1.100000e-02
n=1 Rn=5.500000e-05
n=2 Rn=1.833333e-07
n=3 Rn=4.583333e-10
n=4 Rn=9.166667e-13So we need at least 5 terms
11
01.0
1
)01.0(
)!1(
1.1
)01.0(
)!1()!1(
+++
+
<
+
£
+
=
nnn
c
n
nn
e
x
n
e
R

19. 19
xnx
exfexfcx ==>=££=
+
)()(,5.00,5.0With
)1(
Note:1.7
2
is 2.89 > e
With the help of a computer:
n=0 Rn=8.500000e-01
n=1 Rn=2.125000e-01
n=2 Rn=3.541667e-02
n=3 Rn=4.427083e-03
n=4 Rn=4.427083e-04
So we need at least 12 terms
n=5 Rn=3.689236e-05
n=6 Rn=2.635169e-06
n=7 Rn=1.646980e-07
n=8 Rn=9.149891e-09
n=9 Rn=4.574946e-10
n=10 Rn=2.079521e-11
n=11 Rn=8.664670e-13
Same problem with larger step size
11
5.0
1
)5.0(
)!1(
7.1
)5.0(
)!1()!1(
+++
+
<
+
£
+
=
nnn
c
n
nn
e
x
n
e
R

20. 20
To approximate e
10.5
with an error less than 10
-12
,
we will need at least 55 terms. (Not very efficient)
How can we speed up the calculation?

21. 21
Exercise
If we want to approximate e
10.5
with an error less
than 10
-12
using the Taylor series for f(x)=e
x
at 10,
at least how many terms are needed?
xcx
n
cf
R
R
n
xx
xe
Rx
n
f
x
f
x
f
fxf
xf
n
n
n
n
n
n
n
n
and 10 between somefor )10(
)!1(
)(
)
!
)10(
...
!2
)10(
)10(1(
)10(
!
)10(
...)10(
!2
)10("
)10(
!1
)10('
)10()(
is 10at )( of expansion seriesTaylor The
1
)1(
2
10
)(
2
+
+
-
+
=
+
-
++
-
+-+=
+-++-+-+=
The smallest n that satisfy R
n
< 10
-12
is n = 18. So we need
at least 19 terms.

22. 22
Observation
•A Taylor series converges rapidly near the
point of expansion and slowly (or not at
all) at more remote points.

23. 23
Taylor Series Approximation Example:
More terms used implies better approximation
f(x) = 0.1x
4
- 0.15x
3
- 0.5x
2
- 0.25x + 1.2

24. 24
Taylor Series Approximation Example:
Smaller step size implies smaller error
f(x) = 0.1x
4
- 0.15x
3
- 0.5x
2
- 0.25x + 1.2
Reduced step size
Errors

25. 25
If we let h = x – a, we can rewrite the Taylor series
and the remainder as
Taylor Series (Another Form)
n
n
n
Rh
n
af
h
af
hafafxf +++++=
!
)(
...
!2
)("
)(')()(
)(
2
1
)1(
)!1(
)(
+
+
+
=
n
n
n
h
n
cf
R
h is called the step size.
h can be +ve or –ve.
When h is small, h
n+1
is much
smaller.

26. 26
The Remainder of the Taylor Series Expansion
)(
)!1(
)(
11
)1(
++
+
=
+
=
nn
n
n hOh
n
cf
R
Summary
To reduce truncation errors, we can reduce h or/and
increase n.
If we reduce h, the error will get smaller quicker (with less n).
This relationship has no implication on the magnitude of the
errors because the constant term can be huge! It only give
us an estimation on how much the truncation error would
reduce when we reduce h or increase n.

27. 27
Other methods for estimating
truncation errors of a series
1.By Geometry Series
2.By Integration
3.Alternating Convergent Series Theorem
  
nn
R
nnn
S
n
ttttttttS ......
3213210
+++++++++=
+++
Note: Some Taylor series expansions may exhibit certain
characteristics which would allow us to use different methods
to approximate the truncation errors.

28. 28
Estimation of Truncation Errors
By Geometry Series
k
t
kkkt
tktkt
tttR
n
n
nnn
nnnn
-
=
++++=
+++£
+++=
+
+
+++
+++
1
...)1(
...
...
1
32
1
1
2
11
321
k
tk
R
n
n
-
£
1
If |t
j+1
| ≤ k|t
j
| where 0 ≤ k < 1 for all j ≥ n, then

29. 29
Example (Estimation of Truncation Errors by Geometry Series)
11.0
6
6
1
1
1
1
1
21
2
2
22
1
<
³"+£
+=
+
=
-+
-
-
--
+
j
t
t
jj
j
t
t
j
j
j
j
j
j
p
p
p
p
k
tk
R
n
n
-
£
1
j
j
j
jt
jS
2
2642
......321
-
----
=
++++++=
p
pppp
What is |R
6
| for the following series expansion?
6
6
6
6
103
11.01
11.0
1
103,11.0
-
-
´´
-
<
-
£
´<=
k
tk
R
tk
n
Solution:
Is there a k (0 ≤ k < 1) s.t.
|t
j+1
| ≤ k|t
j
| or |t
j+1
|/|t
j
| ≤ k
for all j ≤ n (n=6)?
If you can find this k, then

30. 30
Estimation of Truncation Errors
By Integration
ò
¥
£
n
n dxxfR )(
If we can find a function f(x) s.t. |t
j
| ≤ f(j) "j ≥ n
and f(x) is a decreasing function "x ≥ n, then
åå
¥
+=
¥
+=
+++ £=+++=
11
321 )(...
njnj
jnnnn jfttttR

31. 31
Example (Estimation of Truncation Errors by Integration)
1
1
11
33
³"
+
³ j
jj
13
1
)1(where
-
=
+==å jttS
j
j
j
Estimate |R
n
| for the following series expansion.
23
2
11
n
dx
x
R
n
n =£ò
¥
Solution:
We can pick f(x) = x
–3
because it would provide a
tight bound for |t
j
|. That is
So

32. 32
Alternating Convergent Series
Theorem (Leibnitz Theorem)
If an infinite series satisfies the conditions
–It is strictly alternating.
–Each term is smaller in magnitude than that
term before it.
–The terms approach to 0 as a limit.
Then the series has a finite sum (i.e., converge)
and moreover if we stop adding the terms after the
n
th
term, the error thus produced is between 0 and
the 1
st
non-zero neglected term not taken.

33. 33
Alternating Convergent Series Theorem
16666.0
6
1
09.02ln
693.02ln
7833333340.0
5
1
4
1
3
1
2
1
1
,5 With
=£»-=
=
=+-+-=
=
SR
S
n
Example 1:
Eerror
estimated
using the
althernating
convergent
series
theorem
Actual error
å
¥
=
-
£<--=+-+-=
+
1
1
432
)11()1(...
432
)ln(1 of series Maclaurin
n
n
n
x
n
xxxx
xS
x

34. 34
Alternating Convergent Series Theorem
Example 2:
77
8642
1076.2
!10
1
1073.2)1cos(
5403023059.0 )1cos(
5403025793.0
!8
1
!6
1
!4
1
!2
1
1
5, With
--
´=£´=-
=
=+-+-=
=
S
S
n
Eerror
estimated
using the
althernating
convergent
series
theoremActual error
å
¥
=
+
+
-=+-+-=
0
12642
)!12(
)1(...
!6!4!2
1
)cos( of series Maclaurin
n
n
n
n
xxxx
S
x

35. 35
Exercise
If the sine series is to be used to compute sin(1) with an
error less than 0.5x10
-14
, how many terms are needed?
...
!17
1
!15
1
!13
1
!11
1
!9
1
!7
1
!5
1
!3
1
1)1sin(
171513119753
-+-+-+-+-=
This series satisfies the conditions of the Alternating
Convergent Series Theorem.
14
10
2
1
)!32(
1
-
´£
+
£
n
R
n
Solving
for the smallest n yield n = 7 (We need 8 terms)
Solution:
R
0
R
1
R
2
R
3
R
4
R
5
R
6
R
7

36. 36
Exercise
How many terms should be taken in order to compute
π
4
/90 with an error of at most 0.5x10
-8
?
...
4
1
3
1
2
1
1
90
444
4
++++=
p
405406)1(10
2
1
)1(3
1
8
3
³=>³+=>´<
+
-
nn
n
Solution (by integration):
3
)1(
3
)1(
)1(
)1(
1
...
33
4
1
421
-
¥
-
¥
-
¥
+=
++
+
=
-
+
=
+<
+
=++= òå
nx
dxx
j
ttR
n
n
nj
nnn
Note: If we use f(x) = x
-3
(which is easier to analyze) instead
of f(x) = (x+1)
-3
to bound the error, we will get n >= 406
(just one more term).

37. 37
Summary
•Understand what truncation errors are
•Taylor's Series
–Derive Taylor's series for a "smooth" function
–Understand the characteristics of Taylor's Series
approximation
–Estimate truncation errors using the remainder term
•Estimating truncation errors using other methods
–Alternating Series, Geometry series, Integration