Transcript Part1

Engineering
Computation
Part 1
E. T. S. I. Caminos, Canales y Puertos
1
Introduction
• Numerical methods are techniques which allow us to formulate
mathematical problems to be solved by basic arithmetic
operations.
• They are able to handle large systems of equations, nonlinearities, complicated geometries and allow us solving
engineering problems which have no analytical solution.
– The intelligent use of commercial software is favored by the
knowledge of numerical methods.
– They allow us to design ad hoc programs to solve concrete
problems.
– The allow us to become familiar with computers and
understand the way they work.
– They are a good tool to reinforce the mathematical
knowledge, because one of their aims consists in transforming
complicate problems into simple arithmetic operations.
E. T. S. I. Caminos, Canales y Puertos
2
Introduction
• Roots of equations :
– They are methods to solve x0 \ f ( x0 )  0.
– They try to find the values
of a variable for it to satisfy
one equation.
– They are very useful in
engineering projects,
because in many
occasions it is not possible
to solve the design
equations analytically.
E. T. S. I. Caminos, Canales y Puertos
3
Introduction
• Systems of linear equations:
a11x1  a12x 2  b1
a 21x1  a 22x 2  b 2
– They are methods looking
for the set of values that
simultaneously satisfy a
system of algebraic
equations.
– Calculus of structures,
electric circuits, supply
networks, fit of curves, etc.
E. T. S. I. Caminos, Canales y Puertos
4
Introduction
• Optimization:
– Determine the value x0
leding to the optimal
value of f(x).
– They can be subject to
constraints.
E. T. S. I. Caminos, Canales y Puertos
5
Introduction
• Fitting curves. Fitting techniques can be divided into two groups:
– Regression. It is used when one has errors in the experimental
data. One looks for the curve showing the trend of the data.
– Interpolation. It is used to fit tabulated data and predict
intermediate values or extrapolated data.
E. T. S. I. Caminos, Canales y Puertos
6
Introduction
• Integration:
b
I   f ( x )dx
a
– Determine the area
below a given curve.
f(x)
– It has many applications
in engineering. Calculus
of centers of gravity.
Calculus of areas,
volumes, etc.
– It can also be used to
solve differential
equations.
E. T. S. I. Caminos, Canales y Puertos
Integral
a
b
x
7
Introduction
•
Ordinary differential
equations :
dy
= f ( t; y)
dt
– They are very important
because many problems
can be stated in terms of
variations and not in terms
of magnitudes.
– There are two types of
problems: Initial value
problems, and boundary
value problems.
E. T. S. I. Caminos, Canales y Puertos
8
Introduction
• Partial differential
equations:
 2u
x
2

 2u
y
2
 f ( x, y )
– Used for characterizing
engineering problems
where the behavior of the
physical magnitude can
be expressed in terms of
speed change with
respect to two or more
variables.
y
– Approximation by finite
differences or the finite
element method.
E. T. S. I. Caminos, Canales y Puertos
x
9
Mathematical Models
• A mathematical expression of a given model can be
F  ma;
F(kgm / s2 )
F
a ;
m
dv F
 ;
dt m
dv mg  cv

;
dt
m
m(kg )
a(m / s2 )
dv FD  FU

;
dt
m
FU
c(Kg / s)
• Analytic solution (t=0, v=0):
• Approximate solution:
c


v ( t i 1 )  v ( t i )   g  v ( t i ) ( t i 1  t i )
m


E. T. S. I. Caminos, Canales y Puertos
FD
10
Mathematical Models
• To solve the problem numerically, one replaces the derivative by
a divided finite difference, tus transforming the problem into a
very simple one containing only simple algebraic operations:
E. T. S. I. Caminos, Canales y Puertos
11
Numerical Differentiation
Forward:
Centered:
f   xi  
f   xi  
f  x i1   f  x i 
h
f  x i 1   f  x i 1 
2h
 How big a step size should we select?
 One- or two-sided formula:
What are the advantages of each?
 How is optimal step size affected by:
- precision of numerical calculations?
- precision with which f is computed?
- curvature of function f near x=1?
- choice of formula?
E. T. S. I. Caminos, Canales y Puertos
12
APPROXIMATION AND ERRORS
Numerical Methods
Instead of solving for the exact solution we solve
math problems with a series of arithmetic
operations.
b
Example:
1
 x dx
a
analytical solution: ln(b) – ln(a)
numerical solution e. g., Trapezoidal Rule
Error Analysis
(a) identify sources of error
(b) estimate the magnitude of the error
(c) determine how to minimize and control error
E. T. S. I. Caminos, Canales y Puertos
13
Mathematical Models
• Comparing solutions:
0
2
4
6
8
10
12
14
16
18
20
0
16,422
27,798
35,678
41,137
44,919
47,539
49,353
50,611
51,481
52,085
Approximat
(Dt=1s.)
0
17,819339
29,697439
37,615198
42,893056
46,411195
48,756333
50,319566
51,361594
52,056193
52,519203
E. T. S. I. Caminos, Canales y Puertos
Numerical solution,
60
Dt=2seg
50
V (m/sec)
t(sec) Exact
Approximate
(Dt=2s.)
0
19,62
32,037357
39,896213
44,870026
48,017917
50,010194
51,271092
52,069105
52,574162
52,893809
40
Exact
solution
30
Numerical solution,
Dt=1seg
20
10
0
0
2
4
6
8
10
12
14
16
18
T (sec)
14
20
Approximations and Rounding Errors
• Unfortunately, computers introduce errors in calculations.
However, since many engineering problems have not analytical
solution, we are forced to used numerical methods
(approximations). The only noption we have is to accept the
error and try to reduce it up to a tolerable level.
• The only way of minimizing the errors is by knowing and
understanding why they occur and how we can diminish them.
• The most frequent errors are:
– Rounding errors, due to the fact that computers can work
only with a finite representation of numbers.
– Truncation errors, due to differences between the exact and
the approximate (numeric) formulations of the mathematical
problem being dealt with.
• Before centering in each one of them, we will see two important
concepts on the computer representation of numbers.
E. T. S. I. Caminos, Canales y Puertos
15
Approximations and Rounding Errors
• Significant figures of a number:
– The significant figures of a number are those that can be
used with confidence.
– The speedometer and the odometer in the figure estimate up
to three and seven significant figures, respectively, 49.5 and
87324.45.
– This concept has two important implications:
1. An approximation is
acceptable when it is exact for
a given number of significant
figures.
2. There are magnitudes or
constants that cannot be
represented exactly.
  3.14159265...
17  4.123105...
E. T. S. I. Caminos, Canales y Puertos
60
40
40
60
80
20
0
100
4
873245
120
16
Approximations and Rounding Errors
Accuracy closeness of measured/computed values to the
"true" value (vs. inaccuracy or bias)
Bias
systematic deviation from truth, "general trend"
Precision closeness of measured/computed values with
each other (spread or scatter), relates to the
number of significant figures (vs. imprecision or
uncertainty)
E. T. S. I. Caminos, Canales y Puertos
17
Approximations and Rounding Errors
• Accuracy and precision:
– The errors associated with
nd measurements can be
characterized observing
their accuracy and
precision.
– Accuracy refers to how
close the value is to the true
value.
– Precision refers to how
close are different
measured values using the
same method.
Numerical methods must be sufficiently exact (without bias) and
precise to satisfy the requirements of engineering problems. From
now on we will refer to error to refer to the inaccuracy and lack of
precision of our predictions.
E. T. S. I. Caminos, Canales y Puertos
18
Approximations and Rounding Errors
(a) inaccurat imprecise
(b) accurate imprecise
(c) Inaccurate precise
(d) Accurate precise
E. T. S. I. Caminos, Canales y Puertos
19
Approximations and Rounding Errors
• Error definitions:
– True value = approximation + absolute error.
– Absolute error = true value - approximation .
– Relative error = absolute error / true value .
t 
absolute error
true value
100%
– In real cases not always one can know the true value, thus:
aproximate error
a 
100%
approximat e value
– In many occasions, the error is calculated as the difference
between the previous and the actual approximations.
a 
actual approximat ion  previous approximat ion
actual approximat ion
E. T. S. I. Caminos, Canales y Puertos
100%
20
Approximations and Rounding Errors
– Thus, the stopping criterium of a numerical method can be:
a  s
 s  prefixed percent tolerance
– It is convenient to relate the errors with the number of
significant figures.If the following relation holds, one can be
sure that at least n significant figures are correct.
s  (0.5 * 102n )%
E. T. S. I. Caminos, Canales y Puertos
21
Approximations and Rounding Errors
• Numerical systems:
– A numerical system is a
convention to represent
quantities. Since we have
10 fingers in our hands, our
most familiis the numerical
system which basis is 10. It
uses 10 different digits.
104 103 102 101 100
8 6 4 0 9
a)
9x
1=
9
0x
10 =
0
4 x 100 = 400
6 x 1000 = 6000
8 x 10000 = 80000
86409
27 26 25 24 23 22 21 20
1 0 1 0 1 1 0 1
– However, computers, due to
the memory structure can
only store two digits: 0 and
1. Thus, they use the binary
system of numeric
representation.
E. T. S. I. Caminos, Canales y Puertos
b)
1x 1= 1
0x 2= 0
1x 4= 4
1x 8= 8
0 x 16 = 16
1 x 32 = 32
0 x 64 = 64
1 x 128 = 128
173
22
Round-off Errors
Background: How are numbers stored in a computer?
• The fundamental unit, a "word," consists of a string of
"bits" (binary digits).
• Because computers are made up of gates or switches
which are either closed or open, we work in binary or
base 2 system.
Example: An 8 bit word representation of the integer "35"
is 00100011 or
0
0
1
0
0
0
1
1
±
26
25
24
23
22
21
20
+ 0x26 1x25 0x24 0x23 0x22 1x21 1x20 = 35
32
2
1
Note: We can only represent a finite # of numbers; for our
case:
–127
to +127
(127 = 27 – 1)
or a total of 255 numbers (including 0)
E. T. S. I. Caminos, Canales y Puertos
23
Approximations and Rounding Errors
• Representation of integer numbers:
– To represent base 10 numbers in binary form the signed
magnitude method is used. The first digit stores the sign (0,
positive and 1, negative). The remaining bits are used to
store the number.
– A computer working with words of 16 bits can store integer
numbers in the range -32768 to 32767.
E. T. S. I. Caminos, Canales y Puertos
24
Approximations and Rounding Errors
• Floating point representation:
– This representation is used for fractional quantities. It has
the fraction part, called mantissa, and an integer part, called
exponent or characteristic.
m * be
– The mantissa is usually normalized, so that the value of m is
limited:
1
m1
b
E. T. S. I. Caminos, Canales y Puertos
25
Approximations and Rounding Errors
• Hipothetical set:
– We assume a hipothetical set of floating point numbers for a
machine using 7 bits as word.
– The smallest number that can be represented is 0.0625, and
the largest is 7.
E. T. S. I. Caminos, Canales y Puertos
26
Approximations and Rounding Errors
Sign. Sign.
Exponent Mantissa Base 10
man. exp.
0
1
1
1 1 0 0 0,0625
0
1
1
1 1 0 1 0,07813
0
1
1
1 1 1 0 0,09375
0
1
1
1 1 1 1 0,10938
0
1
1
0 1 0 0 0,125
0
1
1
0 1 0 1 0,15625
0
1
1
0 1 1 0 0,1875
0
1
1
0 1 1 1 0,21875
0
1
0
1 1 0 0 0,25
0
1
0
1 1 0 1 0,3125
0
1
0
1 1 1 0 0,375
0
1
0
1 1 1 1 0,4375
0
1
0
0 1 0 0 0,5
0
1
0
0 1 0 1 0,625
0
1
0
0 1 1 0 0,75
Difference
0,015625
0,015625
0,015625
0,015625
0,03125
0,03125
0,03125
0,03125
0,0625
0,0625
0,0625
0,0625
0,125
0,125
E. T. S. I. Caminos, Canales y Puertos
Sign. Sign.
Exponent Mantissa Base 10 Difference
man. exp.
0
1
0
0
1 1 1 0,875 0,125
0
0
0
1
1 0 0 1
0,125
0
0
0
1
1 0 1 1,25
0,25
0
0
0
1
1 1 0 1,5
0,25
0
0
0
1
1 1 1 1,75
0,25
0
0
1
0
1 0 0 2
0,25
0
0
1
0
1 0 1 2,5
0,5
0
0
1
0
1 1 0 3
0,5
0
0
1
0
1 1 1 3,5
0,5
0
0
1
1
1 0 0 4
0,5
0
0
1
1
1 0 1 5
1
0
0
1
1
1 1 0 6
1
0
0
1
1
1 1 1 7
1
27
Round-off Errors
EXAMPLE: “Our” Base 10 Machine:
This "Machine" carries three significant decimal digits and one
exponent digit.
± 0.DDDE ± e
with:
0 < e < 9
100 < DDD < 999
We represent - 0.02778 in our machine:
- 0.277E-1 w/ chopping
t = 0.29%
- 0.278E-1 w/ rounding
t = 0.07%
(most computers round, but some chop to save time)
E. T. S. I. Caminos, Canales y Puertos
28
Round-off Errors
Consequences of Computer Representation of #'s:
 Limited Range of quantities can be represented
because there are a finite # of digits in both the
mantissa and the exponent.
smallest positive # 0.100E-9
largest positive #
or
10-10
0.999E+9 almost 109
 Finite number of floating-point values can be
represented within the above range.
± (0.100 to 0.999) E-9 to E+9
2
x 900 #'s x
19 #'s
plus zero ( 0.000 E±e )
= 34,200 #'s
Thus, 34,201 #'s can be represented within the
above range (zero appears only once).
E. T. S. I. Caminos, Canales y Puertos
29
Consequences of Computer Representation of #'s
The interval between successive represented numbers
(quantization error) is not uniform, and increases as the
numbers grow in magnitude.
- "quantization" error, Dx, is proportional to the
magnitude x.
0.312E  1
| Dx | = 0.01
0.313E  1
0.312E  4
| Dx | = 10.0
0.313E  4


- normalizing | Dx | by | x | gives an approximation of
"machine epsilon"
- p, with both chopping and rounding, is represented
by 0.314E+1 with:"quantizing error" =
E. T. S. I. Caminos, Canales y Puertos
  3.14

x 100%  0.051%
30
Approximations and Rounding Errors
• Conclusions:
– There is a limited range to represent quantities. The
limits correspond to “underflow” and “overflow”.
– There is a finite number of quantities that can be
represented on a given range.
E. T. S. I. Caminos, Canales y Puertos
31
Approximations and Rounding Errors
– The interval between numbers increases as the
numbers grow in magnitude.
– This means that the errors are proportional to the
magnitude of the number to be represented. Analyzing
the relative error one gets:
Dx

x
with chopping
Dx
 /2
x
With rounding
– where  is the machine epsilon, that is the worst
possible relative error.
E. T. S. I. Caminos, Canales y Puertos
32
Machine Epsilon
Machine Epsilon: Smallest number such that: 1 +  > 1
Machine Epsilon on "Our Base 10 Machine"
Try 0.01 - - - >
0.100 E+1 + 0.100 E–1 = 0.101 E=1
1.0
+
0.01
=
1.01
Try 0.00999 - - - >
0.100 E+1 + 0.999 E-2 = 0.100 E+1
1.0
+ 0.00999 = 1.00999
after chopping ==> 1.00
Therefore, Machine epsilon is 0.01;
Quick formula:  = b1- t = 101-3 = 0.01
t = # of sig. figs. in mantissa
E. T. S. I. Caminos, Canales y Puertos
33
Round-off Error due to Arithmetic Operations
Trouble happens when you add (or subtract) a small
number to a large number:
For "our machine": 1,200 + 4 + 6  1,210
Working left-to-right:
1200 + 4 = 1204
which is chopped to 1200
1200
= 0.120E+4
1200 + 6 = 1206
which is chopped to 1200
Reverse the order:
4
+ 6 =
10
which is ok
10
+ 1200 = 1210
which is ok
Remedy: add or subtract small numbers together first.
E. T. S. I. Caminos, Canales y Puertos
34
Round-off Error due to Arithmetic Operations
Subtractive Cancellation (subtracting numbers of
almost equal size) – too few significant figures
left
b  b 2  4ac
Consider formulas such as : Neg. root 
2a
Problems arise when we try to subtract two numbers of
almost equal size
32,232 – 32,181 = 51 (Little precision left.)
Our Machine ("chopper"):
0.322 E+5 – 0.321 E+5
32200 – 32100 = 100
With rounding:
0.322 E+5 – 0.322 E+5
32200 – 32200 = 0
E. T. S. I. Caminos, Canales y Puertos
35
Round-off Error due to Arithmetic Operations
Smearing
Occurs when individual terms are larger than summation
itself. Consider the exponential series with x = -10
x 2 x3 x 4 x5




Consider formulas such as: e  1  x 
2! 3! 4! 5!
x
With 7-decimal-digit accuracy:
exact answer
= 4.54 10-05
computed answer = – 6.26 10-05 (differs from book value)
(45 terms)
wrong sign !
Largest intermediate terms are:
9th = –2,755.732 & 10th = 2,755.732
E. T. S. I. Caminos, Canales y Puertos
36
Modern Computers (IEEE standard)
Single Precision:
32 BIT WORDS
24 BITS assigned to mantissa (including the sign
bit)
8 BITS to signed exponent
Double Precision:
64 BIT WORDS
56 BITS assigned to mantissa (including the sign
bit)
8 BITS to signed exponent (not changed)
223 = 8,400,000 or almost 7 full decimal digits for single
255 = 4x1016 or almost 17 decimal digits for double
27 – 1 = 127; 2+127 ~ 2x1038 for both single and
double
E. T. S. I. Caminos, Canales y Puertos
37
Truncation Error
Error caused by the nature of the numerical technique
employed to approximate the solution.
Example:
Maclaurin series expansion of ex
2
3
4
5
x
x
x
x
ex  1  x 




2! 3! 4! 5!
2
x
x
e
 1 x 
If we use a truncated version of the series:
2!
Then the Truncation Error is:
E. T. S. I. Caminos, Canales y Puertos
x3 x 4 x5



3! 4! 5!
38
Approximations and Rounding Errors
• Precautions:
– Sums of large and small numbers: due to equaling the
exponent. They are common in sums of infinite series
where the individual terms are very small when
compared with the accumulated sum. This error can be
reduced by summing first the small terms and using
double precision.
– Cancellation of the subtraction: The subtraction of very
similar numbers.
– Smearing: The individual terms are larger than the total
sum.
– Inner products: They are prone to rounding errors. Thus,
it is convenient to use double precision in this type of
calculations.
n
 xi y i  x1y1  x2y 2    xn yn
i 1
E. T. S. I. Caminos, Canales y Puertos
39
Taylor Series Expansion
Basic Idea:
Predict the value of a function, ƒ, at a point xi+1
based on the value of the function and all of its
derivatives, ƒ, ƒ', ƒ",… at a neighboring point xi
Given xi, ƒ(xi), ƒ'(xi), ƒ"(xi), ... ƒn+1(xi),
we can predict or approximate ƒ(xi+1)
E. T. S. I. Caminos, Canales y Puertos
40
Taylor Series Expansion
General Form (Eq. 4.7 in C&C):
h2
h3
f (x i1 )  f (x i ) hf (x i )  f (x i )  f (x i ) 
2!
3!
hn n

f (x i )  R n
n!
h = "step size" = xi+1 – xi
Rn = remainder to account for all other terms
h n 1 n 1

f ()
(n  1)!
with xi    xi+1
= O (hn+1) with x not exactly known "on the order of hn+1
"
Note: f(x) must be a function with n+1 continuous derivatives
E. T. S. I. Caminos, Canales y Puertos
41
Taylor Series Expansion
h2
f (x i1 )  f (x i )  h f (x i )  f (x i ) 
2!
hn n
 f (x i )  O(h n 1)
n!
 0th order T.S. approx. (n = 0):
f(xi+1) = f(xi) + O (h1)
 1st order T.S. approx. (n = 1):
f(xi+1) = f(xi) + hf '(xi) + O (h2)
2
h
 2nd order T.S. approx. (n = 2):f (x i1 )  f (x i )  h f (x i )  f (x i )  O (h n 1)
2!
 nth order T.S. approximation will be exact for an nth order
polynomial
E. T. S. I. Caminos, Canales y Puertos
42
Taylor Series Expansion
f(x )
f(xi )
Zero order
f(xi+1 ) f(xi )
f(xi+1 ) f(xi )+f '(xi )h
f(xi+1 ) f(xi )+f '(xi )h+ )+f "(xi )h2/2!
f(xi+1 )
xi
xi+1
x
h
E. T. S. I. Caminos, Canales y Puertos
43
Numerical Differentiation from Taylor Series Expansion
Objective:
Evaluate the derivatives of function, ƒ(xi), without
doing it analytically.
When would we want to do this?
1. function is too complicated to differentiate
analytically:
2  cos(1  x ) 0.5x
e
1  0.5x
2. function is not defined by an equation,
i.e., given a set of data points (xi, ƒ(xi)), i=1,…,n
i
0
1
2
3
4
xi
1.0
3.0
5.0
7.0
9.0
ƒ(xi) 2.3
4.1
5.5
5.7
5.9
E. T. S. I. Caminos, Canales y Puertos
44
Numerical Differentiation from Taylor Series Expansion
– First derivative with backward difference.
f ( xi 1 )  f ( xi )  f ' ( xi )( xi  xi 1 )
f ' ( xi ) 
f ( xi )  f ( xi 1 )
( xi  xi 1 )
E. T. S. I. Caminos, Canales y Puertos
45
Numerical Differentiation from Taylor Series Expansion
Backward Difference Approx.:
First Derivative:
h2
f (x i1 )  f (x i )  (x i1  x i )f '(x i )  f "()
2
Letting h = xi - xi-1
h2
f (x i1 )  f (x i )  hf '(x i )  f "()
2
h2
hf '(x i )  f (x i )  f (x i1 )  f "()
2
f (x i )  f (x i1 )
f '(x) 
 O(h)
h
first backward difference
E. T. S. I. Caminos, Canales y Puertos
46
Example of 1st Backward FDD
Using data below calculate ƒ'(x1) :
i
0
1
2
3
xi
1.0 3.0 5.0 7.0
ƒ(xi) 2.3 4.1 5.5 5.7
4
9.0
5.9
First Backward Finite-Divided-Difference at x1:
f (x1 )  f (x 0 )
f '(x) 
 O(h)
h
f '(x1 ) 
f ' (x1) 
4.1  2.3
 O(h)
2
0.9
E. T. S. I. Caminos, Canales y Puertos
{ + O (h) }
47
Backward Difference Approximation
Second Derivative:
f (x i2 )  f (x i )   x i 2  x i  f '(x) 
 x i 2  x i 
2
f "(x i )
2!
+ O([xi-2– xi]3)
with
h = xi– xi-1
and
2h = xi – xi-2
The 2nd order approximation to ƒ(xi-2) becomes:
ƒ(xi-2) = ƒ(xi) – 2hƒ'(xi) + 2h2 ƒ"(xi) +O (h3)
[1]
2nd order approximation to ƒ(xi-1):
h2
f (x i1 )  f (x i )  hf '(x) 
f "(x i )  O(h 3 )
2!
E. T. S. I. Caminos, Canales y Puertos
[2]
48
Backward Difference Approximation
Subtracting 2*[2] from [1] yields:
f(xi-2) – 2f(xi-1) = –f(xi) + h2f"(xi) + O (h3)
Rearranging:
h2ƒ"(xi) = f(xi) – 2f(xi-1) + f(xi-2) + O (h3)
f "(x i ) 
f "(x i ) 
f (x i )  2f (x i1 )  f (x i 2 )  O(h 3 )
h2
f (x i )  2f (x i1 )  f (x i 2 )
h
2
 O(h)
Second backward difference
E. T. S. I. Caminos, Canales y Puertos
49
Example of 2nd Backward FDD
Using data below calculate ƒ"(x2) :
i
0
1
2
3
xi
1.0 3.0 5.0 7.0
ƒ(xi) 2.3 4.1 5.5 5.7
4
9.0
5.9
Second Backward Finite-Divided-Difference at x2:
f "(x 2 ) 
f "(x 2 ) 
f (x 2 )  2f (x1 )  f (x 0 )
h
2
5.5  2* 4.1  2.3
f " (5.0)  - 0.1
E. T. S. I. Caminos, Canales y Puertos
2
2
 O(h)
 O(h)
{ + O (h) }
50
Other Forms of Numerical Differentiation
What points are used for each form?
Backward:
…, ƒ(xi-2), ƒ(xi-1), ƒ(xi), ƒ(xi+1), ƒ(xi+2), …
Forward:
…, ƒ(xi-2), ƒ(xi-1), ƒ(xi), ƒ(xi+1), ƒ(xi+2), …
Centered:
…, ƒ(xi-2), ƒ(xi-1), ƒ(xi), ƒ(xi+1), ƒ(xi+2), …
E. T. S. I. Caminos, Canales y Puertos
51
Taylor Series and Truncation errors
- Higher order divided differences.
f '' ( xi ) 2
h 
2!
f '' ( xi ) 2
f ( xi 1 )  f ( xi )  f ' ( xi )h 
h 
2!
f ( xi 1 )  f ( xi )  f ' ( xi )h 
- Second finite central divided difference
E. T. S. I. Caminos, Canales y Puertos
52
Other Forms of Numerical Differentiation
Forward:
 (x i1 )   (x i )
f '(x i ) 
 O(h)
h
 (x i 2 )  2 (x i1 )   (x i )
f "(x i ) 
 O(h)
2
h
- f ( xi  2 )  4 f ( xi 1 ) -3 f ( xi )
f '(x i ) =
+ O(h 2 )
2h
Centered:
 (x i1 )   (x i1 )
f '(x i ) 
 O(h 2 )
2h
f "(x i ) 
 (x i1 )  2 (x i )   (x i 1 )
E. T. S. I. Caminos, Canales y Puertos
h2
 O(h 2 )
53
Taylor Series and Truncation errors
• Use of the Taylor series to calculate derivatives.
– First derivative with forward difference.
f ( xi 1 )  f ( xi )  f ' ( xi )(xi 1  xi )
f ' ( xi ) 
f ( x i 1 )  f ( x i )
( x i 1  x i )
E. T. S. I. Caminos, Canales y Puertos
54
Taylor Series and Truncation errors
– First derivative with central differences.
f '' ( xi ) 2
h 
2!
f '' ( xi ) 2
f ( xi 1 )  f ( xi )  f ' ( xi )h 
h 
2!
f ( xi 1 )  f ( xi )  f ' ( xi )h 
f ' ( xi ) 
f ( 3) ( xi ) 3
f ( xi 1 )  f ( xi 1 )  2f ' ( xi )h 
h 
3!
f ( xi 1 )  f ( xi 1 )
2h
E. T. S. I. Caminos, Canales y Puertos
55
Taylor Series and Truncation errors
Questions:
• Which is a better approximation?
Forward, Centered, or Backward?
• Why?
• When would you use which?
Note:
We also can get higher order forward, centered, and
backward difference derivative approximations
[C&C Chapter 23, tabulated in Figs. 23.1-3]
E. T. S. I. Caminos, Canales y Puertos
56
Example Combining Roundoff and Truncation Error
Determine h to minimize the total error of a forward finitedivided difference approximation for:
f (x i1 )  f (x i )
f '(x) 
h
• Truncation Error:
f (x i1 )  f (x i ) h
f '(x) 
 f "()
h
2
• Round-off Error:
f  x   fˆ  x    f  x 
xi    xi+1
with  = machine epsilon.
.
.

(x

h)
(1


)


(x
)
i
i (1  ) h
ˆ
  "()
As a result: f ' =
h
2
Roundoff   (x i  h)    (x i )   2  (x i )
Error
h
h
E. T. S. I. Caminos, Canales y Puertos
57
Example Combining Roundoff and Truncation Error
 Total error  = truncation error + roundoff error 
h
f "() +
E = | Total Error | 
2
2 f (x i )
h
NOTE: Truncation error decreases as h decreases
Round-off error increases as h decreases
E. T. S. I. Caminos, Canales y Puertos
58
Example Combining Roundoff and Truncation Error
E. T. S. I. Caminos, Canales y Puertos
59
Example Combining Roundoff and Truncation Error
To minimize total error E with respect to h, set the first
derivative to zero:
dE f "() 2 f (x i )


0
2
dh
2
h
Solve for h and approximate f "() as f
"(xi):
4 f (x i )
h
f "(x i )
E. T. S. I. Caminos, Canales y Puertos
60
Example Combining Roundoff and Truncation Error
Linear Application:
Determine h that will minimize total error for calculating f’(x)
for
f(x) =  x
at
x=1
Using the first forward-divided-difference approximation with
error O(h) and a 5-decimal-digit machine:
e = b1-t = 101-5 = 10-4 = 0.0001
f '(x) = ;
f "(x) = 0
4 f (x i )
h
 infinity
f "(x i )
E. T. S. I. Caminos, Canales y Puertos
61
Example Combining Roundoff and Truncation Error
h
0
0.000001
0.00001
0.0001
0.001
0.01
0.1
1
f(x+h)=
 (x+h)
3.1415
3.1415
3.1416
3.1419
3.1447
3.1730
3. 4557
6.2831
f(x+h)-f(x)
{exact: 3.1415}
[f(x+h)-f(x)]/h
0
0.0001
0.0004
0.0032
0.0315
0.3142
3.1416
0
10
4.0
3.2
3.15
3.142
3.146
Underlined digits are subject to round-off error. They
are likely to be in error by ± one or two units. This does
not cause much problem when h = 1, but causes large
errors in the final result when h < 10-4.
E. T. S. I. Caminos, Canales y Puertos
62
Example Combining Roundoff and Truncation Error
Nonlinear Application:
Determine h for minimizing the total error for computing f’(x) for
ƒ(x) = ex
at
x=3
Using the first forward-divided-difference approximation with
error O(h) and a 5-decimal-digit machine:
e = b1-t = 101-5 = 10-4 = 0.0001
f(x) = f '(x) = f "(x) = ex = 20.0855;
4  (x i )
h
 0.02
 "(x i )
E. T. S. I. Caminos, Canales y Puertos
or about 0.01
63
Example Combining Roundoff and Truncation Error
h
f(x+h)=ex+h
0
0.00001
0.0001
0.001
0.01
0.1
1
20.085
20.085
20.087
20.105
20.287
22.198
54.598
full precision
f(x+h)-f(x) [f(x+h)-f(x)] [f(x+h)-f(x)]
h
h
{exact = 20.085}
0.0
0
20.086
0.002
20
20.086
0.020
20
20.096
0.202
20.2
20.18
2.113
21.13
21.12
34.513
34.523
34.512
Roundoff
Truncation
Underlined digits subject to roundoff error.
Bold digits in error due to truncation.
E. T. S. I. Caminos, Canales y Puertos
64
Additional Error Terminology:
Error Propagation
Errors which appear because we are basing current calculations
on previous calculations which also incurred some form of error
Stability and Condition Number
[see C&C 4.2.3]
Numerically Unstable: Computations which are so sensitive
to round-off errors that errors grow uncontrollably during
calculations.
Condition: sensitivity to such uncertainty; "well
conditioned" vs. "ill conditioned"
Condition Number: measure of the condition; i.e., extent to
which uncertainty in x is amplified by ƒ(x)
C.N.  1 ===> "well-conditioned"
C.N. >> 1 ===> "ill-conditioned"
E. T. S. I. Caminos, Canales y Puertos
65
Condition Number
Begin with Taylor Series: f (x)  f (x)  f '(x)(x  x)
where x is an approximation of x.
Relative error of f(x)
f (x)  f (x) f '(x)(x  x)

f (x)
f (x)
Relative error of x
xx
x
The condition number is the ratio of the two relative errors:
x f '(x)
Condition number (CN) =
f(x)
E. T. S. I. Caminos, Canales y Puertos
66
Condition Number
x
f'(x)
Condition Number =
f(x)
CN contrasts the uncertainty in x with the uncertainty in f(x)
C.N.  1 ===> "well-conditioned", i.e., The error
in f(x) is similar to the error in
x.
C.N. >> 1
E. T. S. I. Caminos, Canales y Puertos
===> "ill-conditioned", i.e.,
the error in f(x) is amplified
and small errors in x can
produce large errors in f(x).
67
Condition Number
x f'(x)
Condition Number =
f(x)
Example: Compute the condition number for f(x) = tan(x)
x f '(x)
Condition number (CN) =
f(x)
f(x) = tan(x) = sin(x)/cos(x)
f'(x) = sec2(x) = 1/cos2(x)
CN = x/[cos(x) sin(x)]
This becomes large (ill-conditioned) when the denominator
approaches zero, i.e., when x  0,  /2, , …
E. T. S. I. Caminos, Canales y Puertos
68