FixedPointIteration

Fixed-point iteration is a simple method for solving equations by rewriting them in the form x = g(x). Starting from an initial guess x0, the method generates a sequence x_{n+1} = g(x_n). If the sequence converges to a limit x*, then x* satisfies x* = g(x*), i.e., it is a fixed point of g, and x* solves the original equation.

Convergence of fixed-point iteration is not guaranteed and depends on the properties of g. A common and practical condition is that g be a contraction on a closed interval I, meaning there exists a constant L with 0 ≤ L < 1 such that |g(x) − g(y)| ≤ L|x − y| for all x, y in I. If g maps I into itself and x0 ∈ I, then there exists a unique fixed point x* in I and the iteration converges to x*. When g is differentiable, a convenient sufficient condition is sup_{x∈I} |g′(x)| ≤ L < 1, which ensures linear convergence with error roughly reducing by a factor L at each step.

The method is a particular instance of the Banach fixed-point theorem. The theorem guarantees existence and uniqueness of the fixed point under contraction and provides a convergence framework for any initial guess in the domain. Practical use often involves choosing or transforming g so that the contraction condition holds; otherwise, the iteration may diverge or oscillate.

Example: solve x = cos x by fixed-point iteration with g(x) = cos x. Starting from x0 = 1, the sequence x_{n+1} = cos(x_n) converges to the unique solution x* ≈ 0.739085, since |g′(x)| = |−sin x| ≤ sin(1) < 1 in a neighborhood of the fixed point.