Examples on iterative root-finding

Comp.145  January 1997  Dr. A.J. Mestel

Assessed test, Wednesday 29th January 1997: Do as much as you can in one hour.

Important: In what follows, μ is the ratio of the day and month of your birthday, defined so that 0 < μ ⩽ 1. Thus if you were born on either 11th December or the 12th November, then μ = \frac{11}{12}. At the top of your paper write your appropriate value of μ. Marks will be awarded for obeying the instructions, for understanding the method, and for clarity of presentation as well as for correct answers.

1. Sketch graphs to show that the equation x = cos x has a unique positive root. Discuss whether the iterative scheme

x_{n+1} = cos x_{n}  for n ⩾ 0  with x_{0} = μ

(with μ defined as above) will converge.

Experiment on a calculator (make sure it is set for radians), and see how many iterations are necessary for the first four figures to remain constant between iterations.

2. Show that Newton’s method for the equation x − cos x = 0 is

x_{n+1} = \frac{x_{n} sin x_{n} + cos x_{n}}{1 + sin x_{n}} .

Using x_{0} = μ once more, find how many iterations are necessary for four figure accuracy. Which of the two methods is faster?

3. The logistic equation for a sequence {x_{n}} is

x_{n+1} = kx_{n}(1 − x_{n}) for some positive constant k.

If {x_{n}} tends to a limit X for given k, show that X must take one of two values. If 0 < k < 1 show that one root is preferred, but that if 1 < k < 3 the other is.

Use a calculator to find what happens when x_{0} = μ and k = 3.1.

4. Write down Newton’s method to solve sin x = 0 starting with x = 3. Defining the error, h_{n} = x_{n} − π, prove that the convergence is cubic, with

h_{n+1} ≃ −\frac{1}{3}h_{n}^{3} .