Examples on iterative root-finding

Comp.145  29th January 1997  A.J. Mestel

Assessed test: Do as much as you can in the hour.

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

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

will converge.

2. Show that a Newton’s method for the equation x = cos x can be written

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

Discuss which of the above two schemes is preferable if (a) x_{0} = 1, and (b) x_{0} = −1.5.

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. For suitable initial values, show that if 0 < k < 1 the sequence will tend to converge to one of these two roots, but that if 1 < k < 3 the other root is preferred.

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

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