Introduction
CS/SE 4X03
Ned Nedialkov
McMaster University
January 13, 2021
Outline
Taylor series
Errors in computing Mean-value theorem The Patriot disaster
Taylor series Errors in computing Mean-value theorem The Patriot disaster Taylor series
Taylor series of an infinitely differentiable (real or complex) f at c f (x) = f (c) + f ′ (c)(x − c) + f ′′ (c) (x − c)2 + · · ·
2! = ∞ f ( k ) ( c ) ( x − c ) k
k! k=0
Maclaurin series c = 0
f (x) = f (0) + f ′ (c)x + f ′′ (0) x2 + · · ·
2! = ∞ f(k)(0)xk
k! k=0
Copyright © 2021 N. Nedialkov. All rights reserved. 3/16
Taylor series Errors in computing Mean-value theorem The Patriot disaster Taylor series cont.
Assume f has n + 1 continuous derivatives in [a, b], denoted f ∈ Cn+1[a,b]
Then for any c and x in [a,b]
f(x) = n f(k)(c)(x − c)k + En+1,
(n+1)!
Replacing x by x+h and c by x, we obtain
k! k
where
En+1 =f(n+1)(ξ)(x−c)n+1 andξ=ξ(c,x)isbetweencandx
f(x + h) = n f(k)(x)hk + En+1,
where En+1 = f(n+1)(ξ)hn+1 and ξ is between x and x+h (n+1)!
k! k
Copyright © 2021 N. Nedialkov. All rights reserved. 4/16
Taylor series Errors in computing Mean-value theorem The Patriot disaster Taylor series cont.
We say the error term En+1 is of order n + 1 and write as En+1 = f(n+1)(ξ)hn+1 = O(hn+1)
That is,
(n+1)!
|En+1| ≤ chn+1, for some c > 0
Copyright © 2021 N. Nedialkov. All rights reserved. 5/16
Taylor series Errors in computing Mean-value theorem The Patriot disaster Taylor series cont.
Example 1. How to approximate ex for given x? x x2x3
e =1+x+2!+3!+··· Suppose we approximate using ex ≈ 1 + x + x2
Then
x x2
e =1+x+2!+E3
2!
ξ3
E3 = 3!, ξbetween0andx
Let x = 0.1. Then e0.1 ≈ 1.105. The error is
ξ3 0.13 −4
E3 = 3! ≤ 3! ≈1.6667×10 Copyright © 2021 N. Nedialkov. All rights reserved.
6/16
Taylor series Errors in computing Mean-value theorem The Patriot disaster Taylor series cont.
How to measure the error?
Example 2. We can compute a more accurate value using Matlab’s exp function:
exp(0.1) = 1.105170918075648e+00 Using this value, the error in our approximation is
|1.105 − 1.105170918075648| ≈ 1.7092 × 10−4 Theoretical error is usually ≤ computed error:
E3 1.6667 × 10−4 ≤ 1.7092 × 10−4
Copyright © 2021 N. Nedialkov. All rights reserved. 7/16
Taylor series Errors in computing Mean-value theorem The Patriot disaster Taylor series cont.
Example 3. If we approximate using three terms ex ≈ 1 + x + x2 + x3 :
e0.1 ≈ 1.105166666666667 TheerrorisE4=ξ4 ≤x4:
4! 4!
0.14 −6 E4 ≤ 4! ≈4.1667×10
2!
3!
Using exp(0.1), the error is
|1.105166666666667 − 1.105170918075648| ≈ 4.2514 × 10−6
Copyright © 2021 N. Nedialkov. All rights reserved.
8/16
Taylor series Errors in computing Mean-value theorem The Patriot disaster Errors in computing
Roundoff errors
Example 4.
• Consider computing exp(0.1)
• 0.1 binary’s representation is infinite:
0.110 = (0.0 0011 0011···)2
• In floating-point arithmetic, this binary representation is rounded:
roundoff error
• The input to the exp function is not exactly 0.1 but 0.1 + ε, for
some ε
• The input to exp is 0.1+ε
• The exp function has its own error
• Then the output of exp(0.1) is rounded when converting from binary to decimal
Copyright © 2021 N. Nedialkov. All rights reserved. 9/16
Taylor series Errors in computing Mean-value theorem The Patriot disaster Errors in computing cont.
Example 5. Compute (3*(4/3-1)-1)*2^52 in favourite language
exact value 0 double precision -1 single precision 536870912
Example 6. This code
#include
int main() {
int i = 0, j = 0;
float f;
double d;
for(f=0.5;f<1.0;f+=0.1) i++; for(d=0.5;d<1.0;d+=0.1) j++; printf("float loop %d double loop %d \n", i, j);
}
outputs float loop 5 double loop 6
Copyright © 2021 N. Nedialkov. All rights reserved.
10/16
Taylor series Errors in computing Mean-value theorem The Patriot disaster Errors in computing cont.
Example 7. Let ai = i · ai−1 − 1, where a0 = e − 1. Find a25
#include
int main(){
int i;
a = exp(1)-1;
for (i = 1; i <= 25; i++)
a = i * a - 1;
printf("%e\n", a);
return 0;
a = exp(1)-1;
for i = 1:25
a = i * a - 1; end
fprintf(’%e\n’, a);
}
true value C
Matlab Octave
≈ 3.993873e-02 -2.242373e+09
clang v11.0.3, MacOS X 4.645988e+09 R2020b
-2.242373e+09
Copyright © 2021 N. Nedialkov. All rights reserved.
11/16
Taylor series Errors in computing Mean-value theorem The Patriot disaster Errors in computing cont.
Truncation errors
Consider
x x 2 x 3 ∞ x k x 2 x 3 ξ 4
e =1+x+2!+3!+ Suppose we approximate
k!=1+x+2!+3!+4! x x2x3
k=4
e ≈1+x+2!+3!
That is we truncate the series. The resulting error is truncation error
Copyright © 2021 N. Nedialkov. All rights reserved.
12/16
Taylor series Errors in computing Mean-value theorem The Patriot disaster Errors in computing cont.
Approximating first derivative
f(x) scalar with continuous second derivative
f(x+h)=f(x)+f′(x)h+f′′(ξ)h2, ξbetweenxandx+h 2
f′(x)h = f(x + h) − f(x) − f′′(ξ)h2 2
f′(x) = f(x + h) − f(x) − f′′(ξ)h h2
If we approximate
f′(x) ≈ f(x + h) − f(x) the truncation error is −f′′(ξ)h
h2
Copyright © 2021 N. Nedialkov. All rights reserved.
13/16
Taylor series Errors in computing Mean-value theorem The Patriot disaster Errors in computing
Absolute and relative errors
Suppose y is exact result and y is an approximation for y • Absolute error |y − y|
• Relative error |y − y|/|y|
Example 8. Suppose y = 8.1472 × 10−1, y = 8.1483 × 10−1. Then |y−y|=1.1000×10−4, |y−y| =1.3502×10−4
|y| Suppose y = 1.012 × 1018, y = 1.011 × 1018. Then
|y−y|=1015, |y−y| ≈9.8814×10−4 ≈10−3 |y|
Copyright © 2021 N. Nedialkov. All rights reserved.
14/16
Taylor series Errors in computing Mean-value theorem The Patriot disaster Mean-value theorem
If f ∈ C1[a,b], a < b, then
f(b)=f(a)+(b−a)f′(ξ), forsomeξ∈(a,b)
From which
f′(ξ)= f(b)−f(a) b−a
Copyright © 2021 N. Nedialkov. All rights reserved.
15/16
Taylor series Errors in computing Mean-value theorem The Patriot disaster The Patriot disaster
During the Gulf War in 1992, a Patriot missile missed an Iraqi Skud, which killed 28 Americans. What happened?
• Patriot’s internal clock counted tenths of a second and stored the result as an integer.
• To convert to a floating-point number, the time was multiplied by 0.1 stored in 24 bits.
• 0.1 in binary is 0.001 1001 1001 ..., which was chopped to 24 bits. Roundoff error ≈ 9.5 × 10−8.
• After 100 hours the measured time had an error of 100×60×60×10×9.5×10−8 ≈0.34seconds.
• A Skud flies at ≈ 1, 676 meters per second. 0.34 seconds error results in
0.34 × 1, 676 ≈ 569 meters. Copyright © 2021 N. Nedialkov. All rights reserved.
16/16