CHAPTER 1.
INTRODUCTION
Differentiation (I)
Product rule
(fg )0 = f 0 g + g 0 f .
so
(fgh)0 = f 0 (gh) + (gh)0 f = f 0 gh + g 0 hf + h0 gf .
Example
d
(x x1 )(x x2 )(x x3 ) = (x x2 )(x x3 ) + (x x1 )(x x3 )
dx
+(x x1 )(x x2 ).
Differentiation (II)
n
Y
(x xi ) = (x x1 )(x x2 ) . . . (x xn ).
i=1
Then
n
d Y
(x xi ) = (x x2 )(x x3 ) . . . (x xn ) +
dx
i=1
(x x1 )(x x3 ) . . . (x xn ) + . . . +
(x x1 )(x x2 ) . . . (x xi1 )(x xi+1 ) . . . (x xn ) + . . .
+(x x1 )(x x2 ) . . . (x xn1 ).
O notation (I)
Let h be a quantity. Then we say that a function p(h) is O(h) if
there is a constant C independent of h such that:
|p| C |h|.
Examples: 2h = O(h).
Let n be a positive integer. Then
2
1
n+1
1
= O( ), and
= O( )
n
n
n2
n
because
n + 1 1
1
2
2 = + 2 .
n
n n
n
O notation (II)
If |h| < 1 then |h2 | < |h|, |h3 | < |h2 |, ....Then
|ah + bh2 | |ah| + |bh2 | (|a| + |b|)|h|,
so ah + bh2 is O(h).
Taylor expansion (I)
f (x) = f (x0 )+f 0 (x0 )(xx0 )+
f (n) (x0 )
f 00 (x0 )
(xx0 )2 +. . .+
(xx0 )n +. . . .
2!
n!
The finite form
f 00 (x0 )
(x x0 )2 + . . . +
2!
f (n) ()
f (n1) (x0 )
(x x0 )n1 +
(x x0 )n ,
(n 1)!
n!
f (x) = f (x0 ) + f 0 (x0 )(x x0 ) +
where is between x and x0 : i.e. if x < x0 then x x0 ; if
x0 < x then x0 x.
Taylor expansion (II)
Taylor expansion converges if |x x0 | < a for a fixed a; a is the
radius of convergence. Sometimes a can be infinity.
Example:
x2 x3
+
+ ....
ex = 1 + x +
2!
3!
This holds for all x; here x0 = 0 and a = .
ln(1 + x) = x
x2 x3
+
...;
2
3
this holds for |x| < 1 i.e. a = 1.
There are tests to determine the radius of convergence, but this is
beyond the scope of this course.
Taylor expansion (III)
When |x x0 | < 1, then
f (x) = f (x0 ) + O(x x0 )
= f (x0 ) + f 0 (x0 )(x x0 ) + O((x x0 )2 )
f 00 (x0 )
= f (x0 ) + f 0 (x0 )(x x0 ) +
(x x0 )2 + O((x x0 )3 ).
2
We therefore can take
f (x0 ), f (x0 )+f 0 (x0 )(xx0 ), f (x0 )+f 0 (x0 )(xx0 )+(f 00 (x0 )/2)(xx0 )2 , . . .
as approximations for f (x).
Integration
Definition of integration:
Divide an interval [a, b] into n parts by
a = x0 < x1 < . . . < xn1 < xn = b.
Pick up a point i in (xi1 , xi ).
Then
Z b
n
X
f (x)dx =
lim
f (i )(xi xi1 ).
a
max |xi xi1 |0
i=1
About numerical analysis (I)
Example:
Z
0
1
e dx = e = e 1 = 1.718281828.
x
But for
Z
e x dx,
we cannot find it exactly. We will need to find approximations.
Numerical analysis uses mathematical analysis to approximate
quantities which cannot be, or are difficult to be, computed exactly.
About numerical analysis (II)
Coming back to the example: from the definition of integrals, if we
divide [0, 1] into 1 interval (itself) i.e. x0 = 0, x1 = 1. Pick up
1 = 1/2 then
Z
e x dx e 1/4 = 1.284025.
If we divide [0, 1] into 2 intervals, i.e. x0 = 0, x1 = 1/2 and
x2 = 1. Pick up 1 = 1/4 and 2 = 3/4, then
Z
0
1
2
e x dx (e 1/16 + e 9/16 ) = 1.40977.
2
Dividing [0, 1] into three intervals [0, 1/3], [1/3, 2/3] and [2/3, 1],
and pick up 1 = 1/6, 2 = 1/2 and 3 = 5/6, then
Z
0
e x dx 1.43826
About numerical analysis (III)
The more points we take, the better. To illustrate this, consider
another simple example
Z 1
x 2 dx = 1/3 = 0.333333.
0
Dividing [0, 1] into one interval, and take 1 = 1/2, then
Z 1
1
x 2 dx ( )2 = 0.25.
2
0
Dividing [0, 1] into two intervals as above, then
Z 1
1 1 2
3
x 2 dx
( ) + ( )2 = 0.3125.
2 4
4
0
Dividing [0, 1] into three intervals as above, then
Z 1
x 2 dx 0.324074.
0
About numerical analysis (IV)
We do not need to choose xi so that the length of (xi1 , xi ), i.e.
|xi xi1 |, is exactly the same for all i.
Later on, we will see that it is better that these lengths are not
equal, and we have special ways to choose i .
In this course, we will learn how to approximate roots of an
equation, approximate the values of a function with limited
information, approximate derivatives and integrals, etc.
Error (I)
If p is an approximation for p, then the:
Absolute error is defined as |p p|.
Relative error is defined as |p p|/|p|.
R1
Example: for the integral 0 x 2 dx = 1/3. For the approximated
value 0.3125, the error is
|1/3 0.3125| = 0.020833,
and the relative error is
|1/3 0.3125|/(1/3) = 0.0625.
Error (II)
In practice, we do not know the exact quantity p (otherwise there
is no need to find an approximation). We can only estimate the
error, though this task may be difficult.
For example, from Taylor expansion:
f (x + h) = f (x) + f 0 (x)h + O(h2 ),
if we only know f (x) and f 0 (x) and nothing else, we can say that
f (x) + f 0 (x)h approximates f (x + h) with the error
e = f (x + h) [f (x) + f 0 (x)h],
which is bounded by Ch2 when h 0, for a constant C .
Why relative error
How can we say which approximation is better?
If p = 100, if p1 and p2 are approximations with errors 1 and 2
respectively, then obviously p1 is better.
If q = 1 and if q is an approximation with error 0.1, then how can
we compare p1 and q?
We need to compare the error to the size of the exact quantity,
that is the relative error.
For p1 , the relative error is 1/100 = 0.01, i.e. the error is 1%. For
q, the relative error is 0.1/1 = 0.1, i.e. the error is 10%. So the
approximation p1 for p is better than q for q.
Computer rounding off errors
We can only work with a finite number of digits.
There are two methods to take a finite number of digits: chopping
and rounding off.
Consider = 3.14159265.... We want to take 5 digits.
For chopping, we take 3.1415.
For rounding off, we take 3.1416 as the next digit is 9, which is
large.
In any case, chopping and rounding off always introduce an error,
which we call (for both cases) rounding off errors.
Floating point
Floating point numbers of k digits:
0.d1 d2 . . . dk 10n , 1 d1 9, 0 di 9 for i > 1.
For example: 3.1415 = 0.31415 10, 3.1416 = 0.31416 10.
Given a number y = 0.d1 d2 . . . dk dk+1 . . . 10n .
Floating point number: for chopping we just take the first k digits:
0.d1 d2 . . . dk 10n .
For rounding off: if dk+1 < 5 then we do exactly as chopping, if
dk+1 5, we add 1 into dk .
Loss of accuracy due to rounding off
Solve ax 2 + bx + c = 0, a = 1, b = 62.1, c = 1.
The exact roots are
b b 2 4ac
b + b 2 4ac
, x2 =
,
x1 =
2a
2a
i.e. x1 = 0.01610723, x2 = 62.08390.
Taking 4 digits: b 2 4ac = 3852 = 62.06.
so
62.1 + 62.06
x1 =
= 0.0200.
2
We have lost some accuracy.
If we take 6 digits, i.e. b 2 4ac = 3852.41 = 62.0678, then
x1 = (62.1 + 62.0678)/2 = 0.016100.
Reformulate to avoid loss of accuracy due to rounding off
Sometimes, we can reformulate the problem to get better accuracy.
We can rewrite x1
as (by multiplying both the denominator and
numerator by b + b 2 4ac)
2c
.
b + b 2 4ac
Then if we only take 4 digits: b 2 4ac = 3852 = 62.06, then
x1 =
x1 =
2.000
= 0.01611.
62.10 + 62.06
Algorithm
An algorithm is a procedure describing steps to be performed.
Example: computing the sum x1 + x2 + . . . + xN .
Algorithm:
-
Take the first number x1 and add x2
Note the sum
Add x3 to the sum
Note the new sum
Continue until xN .
Pseudocode
We describe this algorithm by a pseudocode
Step 1:
Step 2:
Step 3:
Step 4:
INPUT N, x1 , x2 ,. . . , xN .
Set SUM = 0.
For i = 1, 2, . . . , N
Set SUM = SUM + xi .
OUTPUT SUM.
We can implement this in a computer language such as Fortran,
C++, Matlab, ...
Rate of convergence (I)
Let {n } be a sequence that converges to 0, and {n } be a
sequence that converges to . If there is a constant K such that
|n | K |n |,
then we say that n converges to with the rate of convergence
O(n ).
Normally, n is of the form
n =
1
.
np
Rate of convergence (II)
Consider
n =
n2 + n + 1
.
n2
Then n 1 as n .
|n 1| =
n+1
1
1
2
= + 2 ,
2
n
n n
n
so |n 1| = O(1/n) the rate of convergence is O(1/n).
Consider
n =
Then
|
n 1| =
n3 + n + 1
.
n3
1
1
2
n+1
= 2 + 3 2.
3
n
n
n
n
The rate of convergence is O(1/n2 ).
Rate of convergence (III)
For functions: Suppose that limh0 G (h) = 0 and
limh0 F (h) = L. If there is a positive constant K such that
|F (h) L| K |G (h)|,
then we say that F (h) converges to L with the rate O(G (h)).
For example: From Taylor expansion:
f (h) = f (0) + f 0 (0)h +
f 00 (0) 2 f 000 () 3
h +
h .
2
6
Assume that |f 000 ()| K for all . Then
|f (h) [f (0) + f 0 (0)h +
f 00 (0) 2
K
h ]| |h3 |.
2
6
so f (h) f 0 (0)h (f 00 (0)/2)h2 converges to f (0) with the rate
O(h3 ).
