Transcript Document

Chapter 1
Introductory Concepts
and Calculus Review
1
Introduction

The subjects



The derivation of the algorithms
The implementation of the algorithms
Analyze the algorithms mathematically

Accuracy, efficiency, and stability
2
1.1 Basic Tools of Calculus
1.1.1 Taylor’s Theorem
Integral mean
value theorem
3
Three particular expansions of Taylor’s
Theorem
where x0= ?
0
1
2
3
(
x

0
)
(
x

0
)
(
x

0
)
(
x

0
)
ex 
e0 
e0 
e0 
e 0  ...
0!
1!
2!
3!
4
Three particular expansions of Taylor’s
Theorem
where x0= 0
where x0= 0
5
Example : ex
Let
x  [1,1] x0= 0
If we want
then
Finally, n can be found! (here n = 9)
6
Example : ex
p9 (x)
p2 (x)
exp(x)
7
Example : ex
8
Example : ex

The result tells us

We can approximate the exponential function to
within 10-6 accuracy using a specific polynomial, and
this accuracy holds for all x in a specified interval.
9
Example 1.1

Let f (x) = (x+1)1/2, then the second-order Taylor
polynomial (computed about x0= 0) is computed as
follows:
2
10
Example 1.2: sin
Function:
 Accuracy:



11
Example 1.3: arctan

Function:
http://zh.wikipedia.org/wiki/File:Atan_acot_plot.svg
12
Example 1.3: arctan

Function:
and
Let
Error term
13
Example 1.3 : arctan


Please determine the error in a ninth-degree Taylor
approximation to the arctangent function.
Since 2n +1 = 9 implies that n = 4, we have
14
Taylor’s Theorem Expansion
Let x  x + h and x0 x
15
1.1.2 Mean Value and Extreme Value
Theorems
http://en.wikipedia.org/wiki/Mean_value_theorem
16
1.1.2 Mean Value and Extreme Value
Theorems
W
17
1.1.2 Mean Value and Extreme Value
Theorems
Critical point
Critical point
M
m
18
1.1.2 Mean Value and Extreme Value
Theorems
The integral mean value theorem (a corollary of
the intermediate value theorem) states that a
function continuous on an interval takes on its
average value somewhere in the interval. More
exactly, if is continuous on
, then there
exists in
such that
.
19
1.1.2 Mean Value and Extreme Value
Theorems
20
1.2 Error, Approximate Equality, and Asymptotic
Order Notation
1.2.1 Error




A : a quantity(數量) we want to compute
Ah: an approximation(近似值) to that quantity
Relative error (相對誤差) is better.
These errors are both computational errors.
21
1.2.2 Notation: Approximate Equality

Approximate equality

It is an equivalence relation, and satisfy the
following properties:

Transitive(遞移性):

Symmetric(對稱性):

Reflexive(反身性):
22
1.2.3 Notation: Asymptotic Order (Big O)
23
Example 1.4

Let

Simple calculus shows that
so that we have
 Here

24
1.2.3 Notation:
Asymptotic Order (Big O)
25
Example 1.6
26
27
1.3 A Primer on Computer Arithmetic

Computer arithmetic is generally inexact.


While the errors are very small, they can
accumulate and dominate the calculation.
Example: floating-point arithmetic

Reference: An Introduction to Computer Science, Chapter
3, Excess System (Excess_127 or Excess_1023)
 is the sign of the number, f is the fraction (0 <= f <= 1),
 is the base of the internal number system
28
IEEE standards for floating-point representation
（底數 尾數）
Example
Show the representation of the normalized
number + 26 x 1.01000111001
Solution
The sign is positive. The Excess_127 representation of
the exponent is 133. You add extra 0s on the right to
make it 23 bits. The number in memory is stored as:
0 10000101 01000111001000000000000
Errors

Rounding error v.s. chopping error
 Rounding:
四捨五入
 Chopping: 無條件捨去
 Discussion:
 Rounding
is more accurate but chopping is faster.
 The chopping error is indeed lager than the
rounding error.
31
Example

Rounding error

Chopping error
32
Subtractive Cancellation
If a and b are accurate to 16 decimal digits.
What about their difference c = a - b ?
 Example: a  e
 0.9999000049998333

 (1/100) 2
b  e(1/1000)  0.9999990000005000
2
The result c is accurate to 12 digits.
 This is because we were subtracting two nearly
equal numbers.
33
Example

Function :

We know that :

Taylor’s Theorem :
34
……
35
1.5 Simple Approximations
Error function:
(probability theory)
 It is not possible to evaluate this integral by means of


the fundamental theorem of calculus.
Use Taylor’s Theorem to approximate.
where
36
Substitution:
Define
So that we have
Set
where c depends on t and
37
Apply the Integral Mean Value Theorem:
The structured form:
where
38

Use the big O notation:

Use the approximate equality notation:

Simplify: if the values of x between 0 and 2
if k >=1
thus
39
Fundamental Idea

When confronted with a computation that
cannot be done exactly, we often replace that
relevant function with something simpler that
approximates it, and carry out the computation
exactly on the simple approximation.
40