Fixed-point iteration

A fixed point \( p \) of \( g \) satisfies \( g(p) = p \). If \( g \) is continuous and the sequence \( x_n \) converges, its limit is a fixed point. The fixed-point theorem states that if \( g \) maps \( [a,b] \) into itself and \( |g'(x)| \le k < 1 \) there, then a unique fixed point exists and the iteration converges to it for any \( x_0 \in [a,b] \). Convergence is linear with constant \( |g'(p)| \) when \( g'(p) \neq 0 \).

To solve \( x^2 - 2 = 0 \) one can use \( g(x) = \frac{x + 2}{x + 1} \), since \( g(x) = x \) is equivalent to \( x^2 = 2 \). Starting with \( x_0 = 1 \) gives \( x_1 = 1.5 \), \( x_2 \approx 1.4 \), and \( x_3 \approx 1.4167 \), approaching \( \sqrt{2} \approx 1.4142 \). Each step is computed by evaluating \( g \) at the previous value.

A typical error is choosing a \( g \) with \( |g'(p)| \ge 1 \) and expecting convergence. For example, \( g(x) = x^2 - 2 \) has fixed points at \( x = 2 \) and \( x = -1 \), but \( |g'(2)| = 4 \), so iterating from values near 2 moves away from the root. Before iterating, it is wise to check the derivative condition.