Mathematics
Fixed-Point Iteration and Convergence in Numerical Analysis
Quick fact
Fixed-point iteration is the foundation of Newton's method, one of the most widely used algorithms for solving equations in science and engineering.
Why this is interesting
Imagine solving an equation by guessing an answer, repeating a simple calculation, and watching the guess magically improve. How does such a simple, mindless loop lead to accurate solutions?
Read the full explanation
Understanding Fixed-Point Iteration and Convergence in Numerical Analysis
A fixed point of a function f(x) is a value p such that f(p) = p. Fixed-point iteration finds such p by starting with a guess x₀ and repeatedly computing xₙ₊₁ = f(xₙ). If the sequence converges, the limit is a fixed point. This is like adjusting a photo to fit a frame: each iteration brings you closer until the picture stays put. For example, to solve x = cos(x), you simply start with any number and keep pressing the cosine button; soon you get 0.739, a fixed point. The method works because when the function is 'flat' near the fixed point, the distance between consecutive iterates shrinks.
A deeper explanation
The core condition for convergence is that f is a contraction near the fixed point: |f(x) - f(p)| ≤ L|x - p| with 0 ≤ L < 1. This Lipschitz-like condition ensures that each iteration reduces the error by at least a factor of L, guaranteeing the error approaches zero. The Banach Fixed-Point Theorem formalizes this, stating that on a complete metric space, a contraction has a unique fixed point and iteration converges to it from any starting point. The mechanism is geometric: if f's graph intersects the line y = x with a slope whose absolute value is less than 1, then the cobweb plot spirals inward. If the slope exceeds 1, the process diverges. This simple condition explains the behavior of many iterative methods and underlies the analysis of Newton's method, where the iteration function is designed to be a contraction near a root.