Mathematical foundations of Fixed-Point Iteration.
The Fixed-Point Iteration method—historically known as the method of successive approximations or Picard iteration—is one of the most foundational and mathematically profound concepts in all of analysis. Formulated in its modern abstract setting by the Polish mathematician Stefan Banach in his 1922 doctoral dissertation, the Banach Fixed-Point Theorem (or Contraction Mapping Principle) establishes the existence, uniqueness, and constructive convergence of solutions to nonlinear equations across complete metric spaces. Rather than attempting to find where a function f(x) equals zero, the method rephrases the problem into an equivalent fixed-point equation: x = g(x). A point x* satisfying x* = g(x*) is called a fixed point because it is mapped onto itself by the transformation g. The numerical algorithm is deceptively simple: starting from an initial guess x₀, one generates a sequence of successive approximations by repeatedly evaluating the map: x_{k+1} = g(x_k) for k = 0, 1, 2, ... Banach's theorem proves that if the map g is a strict contraction—meaning there exists a Lipschitz constant L < 1 such that |g(x) − g(y)| ≤ L·|x − y| for all points in the domain—then a unique fixed point x* exists, and the iteration sequence is guaranteed to converge to x* from any starting point in the space. On the real line, differentiability implies that the Lipschitz constant is given by the supremum of the derivative: L = sup |g'(x)|. As iterates approach the fixed point, the Mean Value Theorem reveals that the error shrinks by an asymptotic factor of |g'(x*)| at every step: ε_{k+1} ≈ |g'(x*)| · ε_k. Geometrically, this process can be tracked on a Cartesian plane using a cobweb diagram, where vertical moves to y = g(x) alternate with horizontal moves to the diagonal line y = x. In this laboratory investigation, students evaluate the quadratic contraction map g(x) = (x² + 15)/16 on [0, 2], whose unique attracting fixed point is x* = 1.000. By tracking error attenuation across successive Picard iterates and performing linear regression of ε_{k+1} against ε_k, students extract the theoretical Lipschitz contraction constant L = 0.125 with extreme precision, validating the Banach Contraction Mapping Principle in computational mathematics.
Viva voce questions & analytical theory
What is the formal statement of the Banach Fixed-Point Theorem?
Let (X, d) be a complete metric space and let g: X → X be a contraction mapping, meaning there exists a constant L ∈ [0, 1) such that d(g(x), g(y)) ≤ L · d(x, y) for all x, y ∈ X. Then g admits a unique fixed point x* ∈ X such that g(x*) = x*. Furthermore, for any initial point x₀ ∈ X, the Picard sequence x_{k+1} = g(x_k) converges to x* with the error estimate d(x_k, x*) ≤ [L^k / (1 − L)] · d(x₀, x₁).
How does the value of g'(x*) determine the local convergence of fixed-point iteration?
By the Mean Value Theorem, x_{k+1} − x* = g(x_k) − g(x*) = g'(ξ_k) · (x_k − x*). In the limit as x_k → x*, the asymptotic error ratio satisfies lim_{k→∞} |ε_{k+1} / ε_k| = |g'(x*)| = L. If |g'(x*)| < 1, the fixed point is an attracting (stable) fixed point and Picard iteration converges linearly. If |g'(x*)| > 1, the fixed point is a repelling (unstable) fixed point and iteration diverges. If |g'(x*)| = 0, convergence is at least quadratic (as in Newton's method). If g'(x*) = 1, convergence is sublinear.
What is a cobweb diagram and how does it illustrate fixed-point dynamics?
A cobweb plot (or Verhulst diagram) is a visual tool for analyzing 1D iterative maps x_{k+1} = g(x_k). The curve y = g(x) and the line y = x are plotted on the Cartesian plane. Starting at (x₀, 0), one moves vertically to the curve at (x₀, g(x₀)), then horizontally to the identity line at (g(x₀), g(x₀)) = (x₁, x₁), then vertically to (x₁, g(x₁)), and so forth. If 0 < g'(x*) < 1, the path forms a monotonic staircase converging to (x*, x*). If −1 < g'(x*) < 0, the path spirals inwards toward the intersection. If |g'(x*)| > 1, the staircase or spiral expands outwards, illustrating divergence.
Why is Newton-Raphson considered a special case of fixed-point iteration?
Solving f(x) = 0 is equivalent to finding the fixed point of g(x) = x − f(x)/f'(x). Differentiating g(x) using the quotient rule yields g'(x) = 1 − [(f'(x))² − f(x)f''(x)] / (f'(x))² = f(x)f''(x) / (f'(x))². At a simple root x*, f(x*) = 0 while f'(x*) ≠ 0, which guarantees that g'(x*) = 0. Because the first derivative vanishes at the fixed point, Taylor expansion yields ε_{k+1} ≈ [f''(x*) / (2f'(x*))] · ε_k², elevating Newton's method from linear to quadratic convergence.
What is the difference between an a priori and an a posteriori error bound in Banach iteration?
The a priori bound, |x_k − x*| ≤ [L^k / (1 − L)] · |x₁ − x₀|, allows the user to calculate in advance the exact number of iterations k required to achieve a desired tolerance ε before executing any computations. The a posteriori bound, |x_k − x*| ≤ [L / (1 − L)] · |x_k − x_{k-1}|, utilizes the actual distance between the two most recently computed iterates to verify convergence dynamically during program execution.
How can an equation f(x) = 0 be reformulated into an equivalent fixed-point form x = g(x)?
Any algebraic equation f(x) = 0 can be rearranged into infinitely many fixed-point formulations x = g(x). For example, x² − 16x + 15 = 0 can be written as x = (x² + 15)/16, x = 16 − 15/x, or x = √(16x − 15). However, Picard iteration will converge only for formulations where |g'(x*)| < 1. For x* = 1, g₁(x) = (x²+15)/16 has g₁'(1) = 1/8 = 0.125 (convergent), whereas g₂(x) = 16 − 15/x has g₂'(1) = 15/1² = 15 (violently divergent).
What is the significance of the spectral radius in multidimensional fixed-point iteration x_{k+1} = G(x_k)?
In ℝⁿ, the linear convergence of Picard iteration x_{k+1} = G(x_k) is governed by the Jacobian matrix J = ∇G(x*). The Ostrowski theorem states that the iteration converges locally if and only if the spectral radius ρ(J) = max |λ_i| < 1, where λ_i are the eigenvalues of J. The asymptotic convergence rate is precisely ρ(J).
Algorithm precautions and stability rules
- Verify analytically that the chosen reformulation x = g(x) satisfies |g'(x)| < 1 in the neighborhood of the root; otherwise Picard iteration will diverge.
- Confirm that the function g(x) maps the interval [a, b] into itself: g([a, b]) ⊆ [a, b].
- Do not stop iterations purely based on |x_{k+1} − x_k| < ε if L is close to 1, because the true error |x_k − x*| can be much larger: |x_k − x*| ≤ [L/(1−L)]|x_k − x_{k-1}|.
- Guard against repelling fixed points where initial iterates diverge exponentially away from the root.
- Use 64-bit double precision to avoid early convergence stalling due to round-off when ε_k drops below 10⁻¹⁴.
- Check for cycles or bifurcations if testing maps outside the contraction domain |g'(x)| < 1.
Theoretical limitations
- Convergence is strictly linear unless g'(x*) = 0; if L is close to 1 (e.g. L = 0.99), convergence is painfully slow.
- Requires transforming f(x) = 0 into an equivalent contraction form x = g(x), which may not be obvious or possible for all equations.
- Only finds one fixed point at a time; cannot find multiple fixed points simultaneously without changing initial guesses.