2.3 Fixed Point Iteration Convergence

Suppose $f$ is a function with fixed point $\hat{x}$ and $f^{'} (\hat{x})$ exists. Let $x_{0}, x_{1}, x_{2}, . . .$ be a sequence derived from fixed point iteration $(x_{k + 1} = f (x_{k})$ for all $k \geq 1)$ such that $lim_{k \to \infty} x_{k} = \hat{x}$ and $x_{k} \neq \hat{x}$ for all $k = 0, 1, 2, \dots$ Then

\lim_{n \to \infty} \frac{| x_{n + 1} - \hat{x} |}{| x_{n} - \hat{x} |^{1}} = \lim_{n \to \infty} \frac{| f (x_{n}) - f (\hat{x}) |}{| x_{n} - \hat{x} |} = f^{'} (\hat{x}) .

If $f^{'} (\hat{x}) \neq 0$ , fixed point iteration converges linearly (in some neighbourhood of $\hat{x}$ ).

If $f^{'} (\hat{x}) = 0$ , fixed point iteration converges quadratically (in some neighbourhood of $\hat{x}$ )

Error Bound

(proposition 5)
Let $f$ be a differentiable function with fixed point $\hat{x}$ and let $[a, b]$ be an interval containing $\hat{x}$ . If $| f^{'} (x) | \leq M < 1$ for all $x \in [a, b]$ and $f ([a, b]) \subseteq [a, b]$ , then for any initial value $x_{0} \in [a, b]$ , fixed point iteration with $x_{k + 1} = f (x_{k})$ for all $k \geq 0$ , gives an approximation of $\hat{x}$ with absolute error no more than:

M^{k} | x_{0} - \hat{x} |

Aitken's Delta Squared Sequence

If $⟨ p_{n} ⟩$ is a linearly-convergent sequence with limit $p$ , then the sequence $⟨ a_{n} ⟩$ defined by:

a_{n} = p_{n} - \frac{(p_{n + 1} - p_{n})^{2}}{p_{n + 2} - 2 p_{n + 1} + p_{n}}

converges to $p$ faster (but still linearly)

Steffensen’s Method
A modification of fixed point iteration where every third term (i.e. $x_{3}, x_{6}, x_{9}, . . .$ ) is calculated using Aitken’s delta-squared method.