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
x  [1,1]
Then n can be found! (n = 9)
6
Example : ex
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:
Error term
12
Example 1.3 : arctan

Since 2n +1 = 9 implies that n = 4, we have
13
Taylor’s Theorem Expansion
14
1.1.2 Mean Value and Extreme Value
Theorems
15
1.1.2 Mean Value and Extreme Value
Theorems
16
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.
17
1.2.2 Notation: Approximate Equality

Approximate equality

It is an equivalence relation, and satisfy the
following properties:
 Transitive :
 Symmetric :
 Reflexive :
18
1.2.3 Notation: Asymptotic Order (Big O)
19
Example 1.4

Let

Simple calculus shows that
so that we have
 Here

20
1.2.3 Notation:
Asymptotic Order (Big O)
21
Example 1.6
22
23
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)
24
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.
27
Example

Rounding error

Chopping error
28
Subtractive Cancellation
If a and b are accurate to 16 decimal digits.
What about their difference c = a - b ?
 Example: a  e
 0.99990004999833

 (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.
29
Example

Function :

We know that :

Taylor’s Theorem :
30
……
31
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
32
Substitution:
Define
So that we have
Set
where c depends on t and
33
Apply the Integral Mean Value Theorem:
The structured form:
where
34

Use the big O notation:

Use the approximate equality notation:

Simplify: if the values of x between 0 and 2
if k >=1
thus
35
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.
36