Fixed-Point Iteration

Rewriting f(x)=0 as x=g(x) and iterating x_{n+1}=g(x_n) converges to a fixed point whenever g is a contraction near the root.

From roots to fixed points

Many equations can be rearranged into the form x = g(x), whose solution is a fixed point of g. Starting from an initial guess and repeatedly applying g generates a sequence x_{n+1} = g(x_n). If it converges, the limit is a fixed point and hence a root of the original equation.

The contraction condition

Convergence hinges on the derivative of g at the fixed point. If |g'(x*)| < 1, iterations near x* shrink the error by that factor each step, giving linear convergence; the smaller |g'|, the faster. If |g'(x*)| > 1 the iteration diverges. The Banach fixed-point theorem makes this precise: a contraction mapping has a unique fixed point that iteration always reaches.

def fixed_point(g, x0, tol=1e-12, nmax=1000):
    x = x0
    for _ in range(nmax):
        xn = g(x)
        if abs(xn - x) < tol:
            return xn
        x = xn
    return x
# solve x = cos(x)
print(fixed_point(lambda x: __import__('math').cos(x), 1.0))

Choosing a good g

The same equation can be rearranged into many forms of g, some convergent and some not. If a natural rearrangement has |g'| > 1, solving instead for a different term, or applying the inverse function, may produce a contraction. Newton's method is itself a fixed-point iteration with g(x) = x - f(x)/f'(x), engineered so that g'(x*) = 0, which is why it converges quadratically.

Fixed-point iteration underlies many coupled solvers: alternating between subsystems until they agree is a fixed-point loop. Picard iteration for coupling plasma, field, and transport equations in the breeder Hyperion models is one example, often accelerated when plain iteration converges too slowly.