SOLUTIONS OF EQUATIONS
IN ONE VARIABLE
Fixed-Point Iteration
Math 176
Numerical Analysis I
What is a fixed point?
A fixed point for a function is a number at which the value of the
function does not change when the function is applied.
The number p is a fixed point for a given function g if g(p) = p.
Given a root-finding problem f (p) = 0, define functions g with a
fixed point at p in a number of ways:
g(x) = x f (x) or as g(x) = x + 3f (x).
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.
What is a fixed point?
Example 1
Determine any fixed points of the function g(x) = x2 2.
What is a fixed point?
Example 1
Determine any fixed points of the function g(x) = x2 2.
Solution 1
p = g(p) = p2 2 = 0 = p2 p 2 = (p + 1)(p 2).
The fixed point for g occurs at p = 1 and at p = 2.
What is a fixed point?
Existence and Uniqueness of a Fixed Point
Theorem 1
1. If g C[a, b] and g(x) [a, b] for all x [a, b], then g has at least
one fixed point in [a, b].
2. If, in addition (to the previous theorem), g 0 (x) exists on (a, b)
and a positive constant k < 1 exists with
0
g (x) 6 k, for all x (a, b),
then there is exactly one fixed point in [a, b].
Existence and Uniqueness of a Fixed Point
Existence and Uniqueness of a Fixed Point
Example 2
Show that g(x) =
x2 1
has a unique fixed point on the [1, 1].
3
Solution 2
g 0 (x) = 2x/3; g is continuous and g 0 (x) exists on [1, 1].
Absolute maximum of g(x) at x = 1 and x = 1; absolute
minimum at x = 0.
|g 0 (x)| = 2x < 2 , x (1, 1).
3
g satisfies all the hypotheses of Theorem (1); has a unique fixed
point in [1, 1].
Existence and Uniqueness of a Fixed Point
Example 2
Show that g(x) =
x2 1
has a unique fixed point on the [1, 1].
3
Existence and Uniqueness of a Fixed Point
Example 3
Show that Theorem (1) does not ensure a unique fixed point of
g(x) = 3x on the interval [0, 1], even though a unique fixed point
on this interval does exist.
Existence and Uniqueness of a Fixed Point
Example 3
Show that Theorem (1) does not ensure a unique fixed point of
g(x) = 3x on the interval [0, 1], even though a unique fixed point
on this interval does exist.
Solution 2
g 0 (x) = 3x ln 3 < 0 on [0, 1]; g is strictly decreasing on [0, 1].
g(1) =
1
3
6 g(x) 6 1 = g(0), x [0, 1].
x [0, 1], g(x) [0, 1]. Hence, Theorem (1) part (1) ensures the
existence of a fixed point in [0, 1].
However, g 0 (0) = ln 3 = 1.0986, so |g 0 (x)| 1 on (0, 1).
Theorem (1) part (2) cannot be used to determine uniqueness.
Fixed-Point Iteration
To approximate the fixed point p of a function g,
I
I
Choose initial approximation p0 ;
Generate the sequence (pn )
n=0 by letting pn = g (pn1 ) for each
n > 1.
If the sequence converges to p and g is continuous, then
p = lim pn = lim g (pn1 ) = g lim pn1 = g(p)
n
and a solution to x = g(x) is obtained.
Fixed-Point Iteration
Fixed-Point Iteration
Illustration: Fixed-Point Iteration
Algorithm for Fixed-Point Iteration
To find a solution p = g(p) given initial approximation p0 :
initial approximation p0 ; tolerance TOL;
maximum number of iterations N.
OUTPUT approximate solution p or a message of a failure.
Step 1 Set i = 1;
Step 2 While i 6 N do Steps 3-6.
Step 3 Set p = g(p0 )
Step 4 If |p p0 | < TOL then
OUTPUT(p); (Procedure successful).
STOP.
Step 5 Set i = i + 1.
Step 6 Set p0 = p.
Step 6 OUTPUT (Method failed after N iterations);
(Procedure unsuccessful.)
STOP.
INPUT
Fixed-Point Iteration
Example 4
The equation x3 + 4x2 10 = 0 has a unique root in [1, 2].
Ways to change the above equation to fixed-point form x = g(x):
(a) x = g1 (x) = x x3 4x2 + 10
1/2
10
(b) x = g2 (x) =
4x
x
1/2
1
(c) x = g3 (x) =
10 x3
2
10 1/2
(d) x = g4 (x) =
4+x
x3 + 4x2 10
(e) x = g5 (x) = x
3x2 + 8x
Using p0 = 1.5
Computations
n
0
1
2
3
4
5
6
7
8
9
10
15
20
25
30
(a)
1.5
0.875
6.732
469.7
1.03 108
(b)
1.5
0.8165
2.9969
(8.65)1/2
(c)
1.5
1.286953768
1.402540804
1.345458374
1.375170253
1.360094193
1.367846968
1.363887004
1.365916734
1.364878217
1.365410062
1.365223680
1.365230236
1.365230006
1.365230013
(d)
1.5
1.348399725
1.367376372
1.364957015
1.365264748
1.365225594
1.365230576
1.365229942
1.365230022
1.365230012
1.365230014
1.365230013
(e)
1.5
1.373333333
1.365262015
1.365230014
1.365230013
Fixed-Point Theorem
Theorem 2 (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 0 exists on (a, b) and that a constant 0 < k < 1 exists
with
0
g (x) 6 k, for all x (a, b).
Then for any number p0 in [a, b], the sequence defined by
pn = g (pn1 ) ,
n > 1,
converges to the unique fixed point p in [a, b].
Fixed-Point Theorem
Corollary 1
If g satisfies the hypotheses of Theorem 2, then bounds for the
error involved in using pn to approximate p are given by
|pn p| 6 kn max {p0 a, b p0 }
and
|pn p| 6
kn
|p1 p0 | ,
1k
for all n > 1.
Analysis using Theorem (2) and Corollary (1)
(a) For g1 (x) = x x3 4x2 + 10
g1 (1) = 6 and g1 (2) = 12; g1 does not map [1, 2] into itself.
0
0
g1 (x) = 1 3x2 8x, g1 (x) > 1, x [1, 2].
No reason to expect convergence.
(b) For g2 (x) =
10
x
4x
1/2
g2 does not map [1, 2] into itself
{pn }
n=0 is not defined when p0 = 1.5
0
No interval with p 1.365 such that g2 (p) 3.4.
No reason to expect convergence.
(c) For g4 (x) =
10 1/2
4+x
0
5
g4 = 10(4+x)
6
3/2
I
5
10(5)3/2
< 0.15 , for all x [1, 2]
0
Smaller bound on the magnitude of g4 (x), which means rapid
convergence.
Analysis using Theorem (2) and Corollary (1)
g5 (x) = x
choices.
x3 +4x2 10
3x2 +8x
converges more rapidly than the other
How to find a fixed-point problem that produces a sequence
that reliably and rapidly converges to a solution to a given
root-finding problem?
Manipulate the root-finding problem into a fixed-point problem
that satisfies the conditions of Fixed-Point Theorem (2) and has
a derivative that is as small as possible near the fixed point.
Reference
Burden, Richard L., and J. Douglas Faires. Numerical analysis. 9th
ed. 2010. Brooks/Cole, USA.
