Chapter 2 Homework Section 23 The Order Convergence Least Finally

2.3 Fixed Point Iteration Schemes

1. Suppose the sequence {pn}is generated by the fixed point iteration scheme

pn=g(pn−1). Further, suppose that the sequence converges linearly to the

fixed point p.

(a) Show that

g′(p)≈pn−pn−1

pn−1−pn−2

.

(b) Show that

|en| ≈ 

g′(p)

g′(p)−1|pn−pn−1|.

(a) By the Mean Value Theorem,

(b) Recall that when a fixed point iteration scheme converges linearly the asymp-

totic error constant is λ=g′(p). Thus, en≈g′(p)en−1, or en−1≈en/g′(p).

Now,

2. Construct an algorithm for fixed point iteration when the order of convergence

is linear.

Because convergence is linear, we estimate the error using the formulas from Exercise

1. Here is the resulting algorithm. Note its similarity to the algorithm for the method

of false position in Exercise 2 of Section 2.2.

GIVEN: iteration function g

3. Construct an algorithm for fixed point iteration when the order of convergence

is superlinear.

GIVEN: iteration function g

starting approximation x0

4. In the literature, it is not uncommon to find fixed point iteration terminated

when |pn−pn−1|< ǫ, even when convergence is only linear. Comment on the

Fixed Point Iteration Schemes 3

accuracy of this stopping condition when convergence is linear. Consider the

cases g′(p)≈0, g′(p)≈1/2 and g′(p)≈1.

Recall that when convergence is linear

5. Consider the function g(x) = cos x.

(a) Graphically verify that this function has a unique fixed point on the real

line.

(b) Can we prove that the fixed point is unique using the theorems of this

section? Why or why not?

(c) What order of convergence do we expect from the fixed point iteration

scheme pn=g(pn−1) = cos(pn−1)? Why?

(d) Perform seven iterations starting from p0= 0. Verify that the appropriate

error estimate is valid. To ten decimal places, the fixed point is x≈

0.7390851332.

(a) The figure below displays the graphs of y= cos xand y=xfor −1.5≤x≤

4Section 2.3

Here are the results of seven iterations of the fixed point scheme starting from

p0= 0.

theoretical

npn|pn−p|error estimate

1 1.0000000000 0.2609148668

3 0.8575532158 0.1184680826 0.129542854379

6. Consider the function g(x) = 1 + x−1

8x3.

(a) Analytically verify that this function has a unique fixed point on the real

line.

Fixed Point Iteration Schemes 5

(b) Can we prove that the fixed point is unique using the theorems of this

section? Why or why not?

(c) What order of convergence do we expect from the fixed point iteration

scheme pn=g(pn−1)? Why?

(d) Perform seven iterations starting from p0= 0. Verify that the appropriate

error estimate is valid.

cannot use the theorems of this section to prove that the fixed point is unique.

(d) Because we expect linear convergence, the appropriate error estimate is

Here are the results of seven iterations of the fixed point scheme starting from

p0= 0.

theoretical

npn|pn−p|error estimate

2 1.8750000000 0.1250000000

4 1.9725180057 0.0274819943 0.024214600570

6 1.9932809128 0.0067190872 0.006537159153

7. Consider the function g(x) = 2x(1 −x), which has fixed points at x= 0 and at

x= 1/2.

(a) Why should we expect that fixed point iteration, starting even with a value

very close to zero, will fail to converge toward x= 0?

6Section 2.3

(b) Why should we expect that fixed point iteration, starting with p0∈(0,1)

will converge toward x= 1/2? What order of convergence should we

expect?

(c) Perform seven iterations starting from an arbitrary p0∈(0,1) and numer-

ically confirm the order of convergence.

(a) Note that g′(0) = 2 >1. Thus, for x≈0,

(b) Due to the symmetry of gabout x= 1/2, we can restrict attention to p0∈

(c) Here are the results of seven iterations of the fixed point iteration scheme

npn|pn−p| |pn−p|/|pn−1−p|2

0 0.1000000000000000 4.000 ×10−1

2 0.2952000000000000 2.048 ×10−11.418

4 0.4859262511644672 1.407 ×10−21.999

6 0.4999996861449132 3.139 ×10−72.001

8. Verify that x=√ais a fixed point of the function

g(x) = 1

2x+a

x.

Use the techniques of this section to determine the order of convergence and the

asymptotic error constant of the sequence pn=g(pn−1) toward x=√a.

Fixed Point Iteration Schemes 7

Let

g(x) = 1

2x+a

x,

9. Verify that x=√ais a fixed point of the function

g(x) = x3+ 3xa

3x2+a.

Use the techniques of the this section to determine the order of convergence and

the asymptotic error constant of the sequence pn=g(pn−1) toward x=√a.

Let

g(x) = x3+ 3xa

3x2+a,

8Section 2.3

the order of convergence is at least 3. Finally,

10. Verify that x= 1/a is a fixed point of the function g(x) = x(2 −ax). Use the

techniques of the this section to determine the order of convergence and the

asymptotic error constant of the sequence pn=g(pn−1) toward x= 1/a.

Let g(x) = x(2 −ax), and note that

11. Consider the function g(x) = e−x2.

(a) Prove that ghas a unique fixed point on the interval [0,1].

(b) With a starting approximation of p0= 0, use the iteration scheme pn=

e−p2

n−1to approximate the fixed point on [0,1] to within 5 ×10−7.

Fixed Point Iteration Schemes 9

(c) Use the theoretical error bound |pn−p| ≤ kn

1−k|p1−p0|to obtain a theo-

retical bound on the number of iterations needed to approximate the fixed

point to within 5 ×10−7. How does the number of iterations performed in

part (b) compare with the theoretical bound?

(a) Let g(x) = e−x2. We will proceed by showing that gis continuous on [0,1],

maps [0,1] to [0,1] and there exists a k < 1such that |g′(x)| ≤ kfor all

(b) With a starting approximation of p0= 0 and a convergence tolerance of ǫ=

12. Repeat Exercise 11 for the function g(x) = 1

2cos x.

(a) Let g(x) = 1

for all x∈(0,1). Hence, gis decreasing on (0,1). Combining this fact with

with an error estimate of 2.603 ×10−7.

(c) In part (a) we found k=1

2sin 1. With p0= 0, it follows that p1=g(p0) =

1

2cos 0 = 1

2. Solving the equation

13. Repeat Exercise 11 for the function g(x) = 1

3(2 −ex+x2).

Fixed Point Iteration Schemes 11

(a) Let g(x) = 1

for all x∈(0,1). Hence, gis decreasing on (0,1). Combining this fact with

(b) With a starting approximation of p0= 0 and a convergence tolerance of

14. The function f(x) = ex+x2−x−4 has a unique zero on the interval (1,2).

Create three diﬀerent iteration functions corresponding to this function, and

compare their convergence properties for approximating the zero on (1,2). Use

the same starting approximation, p0, for each iteration function.

12 Section 2.3

Answers will of course vary. Here are two possibilities. If we rearrange the equation

ex+x2−x−4 = 0 as

15. Repeat Exercise 14 for the function f(x) = x3−x2−10x+ 7 on the interval

(0,1).

Answers will of course vary. Here are two possibilities. If we rearrange the equation

x3−x2−10x+ 7 = 0 as

16. Repeat Exercise 14 for the function f(x) = 1.05 −1.04x+ ln xon the interval

(1,2).

Answers will of course vary. Here are two possibilities. If we rearrange the equation

Fixed Point Iteration Schemes 13