```Numerical Analysis
EE, NCKU
Tien-Hao Chang (Darby Chang)
1
Summary
1 exam, 1project and some exercises
http://zoro.ee.ncku.edu.tw/na/
2
Target
Solve problems with numerical methods
3
In this slide

Why numerical methods?
– differences between human and computer
– a very simple numerical method

What is algorithm?
– definition and components
– three problems and three algorithms

Convergence
– compare rate of convergence
4
Why such methods?
Computer is stupid
5
x-2=0
Human says, “x=2, easy!”
6
{ x-2=0; }
Computer says, “compilation error!”
7
What is the difference?
8
http://www.wallcoo.com/paint/Donald_Zolan_Early_Childhood_02/wallpapers/1280x1024/painting_children_kjb_DonaldZolan_68TheThinker_sm.jpg
Human is logical (thinking)
9
http://files.myopera.com/conansakura/albums/31567/thumbs/2.jpg_thumb.jpg
Can do inference
10
http://www.aclibrary.org/eventkeeper/Graphics/SLZ/computer.jpg
Computer is procedural (executing)
11
An example

(((x+3)-2)+6)=0
– Human requires only the rules (in this
case, arithmetic),
– and can inference the steps for the
solution
12
Computer

(((x+3)-2)+6)=0
– Requires the exact procedure (steps)
• { x0=0–6; }
• { x1=x0+2; }
• { x=x1–3; }
– These steps is numerical method
13
14
http://www.masternewmedia.org/images/fast_snail_id86636_size350.jpg
It is fast
15
So, why numerical methods?

Computer is stupid

Computer is fast (and works hard)

Sometimes, stupid methods can
solve difficult problems
16
17
18
1

72 +  − + 18 +
1

−
= 98.6
is the time of death,
which cannot be solved explicitly
19
We know that
is no earlier than PM 7:15, and
is no later than PM 8:00. So…
20
could be PM 7:38
rubbish =.=
21
1

1

−
72 +  − + 18 +
= 98.6
A systematic procedure
1.
Let  as PM 7:38
2.
Evaluate the above formula
3.
4.
If the result exceeds 98.6, we use
PM 7:27, otherwise, we use PM 7:49
Repeat step 2 & 3 until the result is
close to 98.6 enough
22
http://www.leda-tutorial.org/en/unofficial/Pictures/BisectionMethod.png
Bisection method
23
Bisection method

The concept is
– 1) find the mid-point, 2) evaluate it,
and 3) shrink the solution range

It is stupid: just trial and error

But it works, because  is ascending

And…
24
And very accurate
Actually, it is getting accurate
after every trial
25
When #trails → ∞
Computer works hard, so
it could happen
26
Any Questions?
27
Algorithm
The heart of numerical analysis
28
Algorithm

Definition
– A precisely defined sequence of steps

In this course
– design;
– implement; and
– examine the performance
29
How to implement?
30
By hand
too painful
(but you might need to)
31
With computer
in other words, do programming
32
Programming
Even scared!
33
Algorithm could be simple
34
An example from statistics

Mean and standard deviation on n
values
=

=1

, =

2

=1
2

=1
−
( − 1)
35
36
In action
input is 1,2,3,4,5
37
38
It is also an algorithm
(a precisely defined sequence of steps)
39
Not
A difficult sequence of steps
40
Any Questions?
41
Another example
Definite integral using trapezoidal rule
42

A partition
= 0 < 1 < ⋯ < −1 =
43

ℎ
≈   + 2
2
−1
+ ()
=1
where  =  + ℎ, and ℎ = ( − )/
44
45
In action
2
1
=

1
, = 4

46
47
Error


The analytic solution is 2
The absolute error is
2 − 0.697023809 ≈ 3.877 × 10−3
48
49
Observations of the errors



, the absolute error, is a
decreasing function of
When  is doubled,  is reduced by
a factor (roughly 1/4)
From the numerical evidence

≈ 2

where  is independent of
50
Any Questions?
51
The third example

Square root
–  is a nonnegative real number
– +1 =
1
2
+

– +1 converges to

52
53
Stopping condition

+1 − ) <
– +1 −  ) <  provides an estimate

Prevent infinite loop
– give a limit of the number of iterations
54
In action
2, i.e.,  = 2
0 = 2,  = 0.005,  = 10
55
56
So far
a statistics problem,
the integral problem, and
the square root problem
57
Any Questions?
58
What is the differences among them?
(hint: the concepts of the output)
59
Type of methods

The statistics algorithm
– generates an exact (analytic) solution

The integral algorithm
– generates an approximate (numerical) solution
– many numerical methods work in much the same
way

The square root algorithm
– generates a sequence of approximations which
converge to the solution
– another typical class of numerical methods
60
Poll
Programming ability
61
Learnt
C/C++ (??/24)
Java (??/24)
Other (??/24)
62
Learnt
Data structure (??/24)
Algorithm (??/24)
63
Language vs. algorithm

Two languages
– The same concept, different patterns
– e.g., Chinese and English
– 想睡覺, feel sleepy

English vs. C
– Increase i by 1
– { ++i; }


Language is/defines the pattern
Algorithm is/describes the concept
64
Pseudo-code
Not any real programming language
65
A pseudo-code example
66
Can You
67
Convergence
When several numerical methods are available,
choose the fastest one
68
lim  =
→∞
The sequence { } converges to the value , and
is called the limit of the sequence
69
Rate of convergence

Let { } converges to , { }
converges to 0,  is a constant, and
−  ≤

Rate of convergence of { } is ( )

is typically of the form
– 1/
– 1/
70
71
72
73
74
Any Questions?
75
Which Is Better?

1
1
1
,

(
)
2
10

2
76
Using L'Hôpital's rule (羅必達法則)



This is provided by a student 陳攀任
In its simplest form, L'Hôpital's rule states that for
functions  and :
′
If lim () = lim () = 0 or ± ∞ and lim ′
exists,
→
→
→  ()

′
then lim
= lim ′
→ ()
→  ()
To compare 10 and 2
Let   = 10 and   = 2 ,

10
10 ∙ 9
10 ∙ 9 ∙ 8
then lim
= lim  = lim
= lim 2
→∞ ()
→∞ 2
→∞ ln 2 ∙ 2
→∞ ln 2 ∙ 2
10!
= ⋯ = lim 10
=0

→∞ ln 2 ∙ 2
77
78
Rate of Convergence
There is another definition for function
79
Another definition of rate of
convergence for function
80
81
Rate of convergence

Let { } converges to , { }
converges to 0,  is a constant, and
−  ≤

Rate of convergence of { } is ( )

is typically of the form
– 1/
– 1/
82
Order of Convergence


A different measure of convergence speed
than rate of convergence
Examines the relationship between
successive error values
83
Order of Convergence
Iterative Method


An iterative method is said to be of order  if
the sequence it generates converges of order
The most common values of  in practice are
–  = 1 (linear convergence)
–  = 3 (cubic convergence)

Non-integer values for  are possible
84
Note the dramatic difference between 1 and 2,
and the slight difference between 2 and 3
85
86
```