4/1 - 吳漢銘

2.2 Fixed-Point Iteration
1. Fixed Point
1. Fixed Point
2. Fixed-Point Iteration
3. Fixed-Point Theorem
C程式: ALG022 Fixed Point Iteration
Definition 2.2
The number p is a fixed point for a given function g if
g p
p .
開課班級: 數學系資統組2A 數值分析
授課教師: 吳漢銘 (淡江大學數學系)
(1) Given a root-finding problem f p
0 , we can define g with
a fixed point at p in a number of ways, for example, as
g x
x f x or as g x
x 3f x .
教學網站: http://www.hmwu.idv.tw
Textbook: Burden & Faires’ Numerical
Analysis, 9/E
系級:
數學系資統組2A 數值分析
學號:
(2) Conversely, if the function g has a fixed point at p, then the
function defined by f x
x g x has a zero at p .
姓名:
2.2 Fixed-Point Iteration
September 14, 2014
1 / 16
Theorem 2.3
數學系資統組2A 數值分析
2.2 Fixed-Point Iteration
September 14, 2014
2 / 16
The Existence and Uniqueness of A Fixed Point
Example 1
Determine any fixed points of the function g x
Sol:
x2
2.
Let p be a fixed point for g, we have p g p
p2 2.
➁ 0 p2 p 2
p 1 p 2
p
1, p 2.
So g has two fixed points.
end end
Theorem 2.3
(i) If g
C a, b and g x
a, b for all
at least one fixed point in a, b .
x
a, b
, then g has
(ii) If, in addition, g x exists on a, b and a positive constant k
exists with g x
k , for all x a, b , then there is
fixed
point
in a, b .
exactly one
數學系資統組2A 數值分析
2.2 Fixed-Point Iteration
September 14, 2014
1
3 / 16
數學系資統組2A 數值分析
2.2 Fixed-Point Iteration
September 14, 2014
4 / 16
Example 2(a)
Show that g x
1, 1 .
x2
Example 2(b)
1 3 has a unique fixed point on the interval
x2
Find the fixed points of g x
3, 4 .
Sol:
1 3 in the interval
1, 1 and
Sol:
➀ Since g x
2x 3, the function g is continuous and g x exists on
1, 1 .
➁ The maximum and minimum values of g x occur at x
1, x 0,
or x 1.
➂ maximum: g 1
0, g 1
0; minimum : g 0
1 3.
➃ Moreover
2x
2
g x
, for all x
1, 1 .
3
3
So g satisfies all the hypotheses of Theorem 2.3 and has a unique
fixed point in 1, 1 .
end end
數學系資統組2A 數值分析
Example 2(b)
2.2 Fixed-Point Iteration
September 14, 2014
5 / 16
p2
➀ Let p be the fixed point. If g p
p2
3p
1
0
1 3
3
p
p
p, then
13 2
13 2
3
1, 1
3, 4
➁ However, g 4
5 and g 4
8 3 1, so g does not satisfy the
hypotheses of Theorem 2.3 on 3, 4 .
end end
(1) The hypotheses of Theorem 2.3 are sufficient
unique fixed point but are not necessary .
數學系資統組2A 數值分析
2.2 Fixed-Point Iteration
to guarantee a
September 14, 2014
6 / 16
2. Fixed-Point Iteration
(conti.)
(1) To approximate the fixed point of a function g, we choose an initial
approximation p0 and generate the sequence pn n 1 by
letting pn g pn 1 , for each n 1.
(2) If the sequence converges to p and g is continuous, then
p
limn
pn
limn
g pn
1
pn
1
g limn
g p
,
and a solution to x g x is obtained. This technique is called
fixed-point, or functional iteration .
數學系資統組2A 數值分析
2.2 Fixed-Point Iteration
September 14, 2014
7 / 16
數學系資統組2A 數值分析
2.2 Fixed-Point Iteration
September 14, 2014
8 / 16
Fixed-Point Iteration
ALGORITHM 022: Fixed-Point Iteration
(conti.)
To find a solution to p
數學系資統組2A 數值分析
2.2 Fixed-Point Iteration
September 14, 2014
數學系資統組2A 數值分析
9 / 16
Fixed-Point Iteration: illustration
g p given an initial approximation p0 .
2.2 Fixed-Point Iteration
Fixed-Point Iteration: illustration
September 14, 2014
10 / 16
(conti.)
[程式] Find the root of the equation x3 4x2 10 0 in 1, 2 using
the fixed-point iteration approach with the following fixed-point form
x g x . Suppose p0 1.5.
Sol:
(a) x
g1 x
(c) x
g3 x
(e) x
g5 x
x
10
x
x3
x3
x3
4x2
1 2
10.
2.
4x2
10
(b) x
(d) x
g4 x
3x2
8x .
g2 x
10
x
4x
1 2.
10 1 2
.
4 x
➀ The actual root is 1.365230013 .
➁ 以 (c) 為例: 原式 x3 4x2 10 0
4x2 10 x3 , so
x2
10 x3 4 , and x
10 x3 1 2 2 . Choose a positive
solution.
➁ Excellent results for choices (c), (d), and (e) (the Bisection method requires
27 iterations for this accuracy).
➂ (a) was divergent and (b) became undefined because it
involved the square root of a negative number.
數學系資統組2A 數值分析
2.2 Fixed-Point Iteration
September 14, 2014
11 / 16
How to find a fixed-point problem that produces a sequence that
and
rapidly converges
數學系資統組2A 數值分析
reliably
to a solution to a given root-finding problem?
2.2 Fixed-Point Iteration
September 14, 2014
12 / 16
3. Fixed-Point Theorem
Corollary 2.5
Corollary 2.5
Theorem 2.4 (Fixed-Point Theorem)
Let g
C a, b be such that g x
a, b , for all x a, b .
Suppose, in addition, that g exists on a, b and that a constant
0 k 1 exists with
g x
k , for all x a, b .
Then for any number p0 a, b , the sequence defined by
pn g pn 1 , n 1,
converges to the unique fixed point p a, b .
If g satisfies the hypotheses of Theorem 2.4, then bounds for the
error involved in using pn to approximate p are given by
pn p
k n max p0 a, b p0
and
kn
pn p
p1 p0 , for all n 1.
1 k
Question: How can we find a fixed-point problem that produces a
sequence that reliably and rapidly converges to a solution to a given
root-finding problem?
Answer: Manipulate the
problem into a fixed point
problem that satisfies the conditions of Fixed-Point Theorem 2.4 and
has a derivative that is as small as possible near the fixed point .
數學系資統組2A 數值分析
2.2 Fixed-Point Iteration
September 14, 2014
13 / 16
數學系資統組2A 數值分析
2.2 Fixed-Point Iteration
September 14, 2014
14 / 16
C 程式: ALG022 Fixed Point Iteration
Exercise Set 2.2
(0) 用程式跑出講義 12/16 頁之表格。
(1) 用手、或計算機算: 1, 2
(2) 用電腦或寫程式算 (列出表格): 5, 9
數學系資統組2A 數值分析
2.2 Fixed-Point Iteration
September 14, 2014
15 / 16
數學系資統組2A 數值分析
2.2 Fixed-Point Iteration
September 14, 2014
16 / 16

Download Report