Fixed-Point Iteration — Mathematics Knowledge System

Overview

Fixed-point iteration solves an equation by rewriting it in the form x = g(x) and then repeatedly applying g, starting from an initial guess: x₀, x₁ = g(x₀), x₂ = g(x₁), and so on. A value x* with x* = g(x*) is called a fixed point of g, and if the iterates converge, they converge to such a fixed point — which is exactly a solution of the original equation. This is one of the simplest and most general iterative schemes in numerical analysis: Newton's method, the Babylonian square-root algorithm, and many implicit-equation solvers (like the Colebrook pipe-friction equation) are all special cases of fixed-point iteration for a particular choice of g. Whether the iteration converges, and how fast, is governed entirely by the size of g′ near the fixed point.

Intuition

Picture the curve y = g(x) and the line y = x drawn on the same axes; a fixed point is exactly where they cross. Starting from x₀, plot the point (x₀, g(x₀)) on the curve, then step horizontally over to the line y = x — that horizontal coordinate becomes x₁ — and repeat. This 'cobweb' picture makes convergence visual: if the curve g is shallower than the line y = x near the crossing (|g′| < 1), each step's horizontal jump shrinks and the cobweb spirals or staircases into the intersection point. If g is steeper than the line (|g′| > 1) near the crossing, the same process flings the iterates farther away instead of pulling them in — the fixed point exists but the iteration fails to find it.

Formal Definition

Definition

Given an equation rewritten as x = g(x), the iteration generates a sequence from an initial guess x₀. The Banach fixed-point theorem guarantees convergence when g is a contraction on an interval containing the fixed point:

x_{n+1} = g(x_n), \qquad n = 0, 1, 2, \ldots

Fixed-point iteration

x^* = g(x^*)

Definition of a fixed point

|g'(x)| \le k < 1 \ \text{ for all } x \text{ near } x^* \ \Longrightarrow\ x_n \to x^*

Sufficient convergence condition (g is a contraction)

|x_{n+1} - x^*| \approx |g'(x^*)|\cdot|x_n - x^*|

Linear convergence rate governed by |g′(x*)|

Worked Examples

g(x) = √(x+2). Step 1 from x₀ = 1.
$x_1 = \sqrt{1+2} = \sqrt{3} \approx 1.7321$
Step 2 from x₁ ≈ 1.7321.
$x_2 = \sqrt{1.7321+2} = \sqrt{3.7321} \approx 1.9319$
Step 3 from x₂ ≈ 1.9319.
$x_3 = \sqrt{1.9319+2} = \sqrt{3.9319} \approx 1.9829$
Step 4 from x₃ ≈ 1.9829.
$x_4 = \sqrt{1.9829+2} = \sqrt{3.9829} \approx 1.9957$
The sequence is clearly approaching the true root x* = 2 (check: 2² = 2+2 = 4 ✓).
$x_n \to 2$

Answer: The iterates 1, 1.7321, 1.9319, 1.9829, 1.9957, … converge toward x* = 2.

Practice Problems

Difficulty 3/10

Using g(x) = √(x+2) starting from x₀ = 1 (as above), compute x₅ given x₄ ≈ 1.9957.

Difficulty 4/10

For g(x) = √(x+2) near the fixed point x* = 2, g′(x) = 1/(2√(x+2)). Evaluate g′(2) and determine whether the iteration is guaranteed to converge there.

g′(2) = 1, borderlineg′(2) = 0.25, so |g′(2)| < 1 and it convergesg′(2) = 2, so it divergesg′(2) is undefined

Difficulty 6/10

The implicit Colebrook equation for pipe friction factor f can be rearranged into a fixed-point form f = g(f). Explain, in terms of the convergence condition |g′(f*)| < 1, why engineers check that an iterative scheme for such implicit equations actually converges before trusting it, rather than assuming any rearrangement works.

Quiz

Summary

Fixed-point iteration solves x = g(x) via x_{n+1} = g(x_n), converging (when it does) to a fixed point x* = g(x*).
Convergence is governed by |g′(x*)|: if less than 1 near the fixed point, iterates are drawn in (linear convergence); if greater than 1, they are repelled.
Example: g(x) = √(x+2) from x₀ = 1 converges quickly to x* = 2 since g′(2) = 0.25; g(x) = cos(x) from x₀ = 1 converges more slowly and with oscillation to x* ≈ 0.739085 since g′(x*) ≈ −0.674.
Newton's method and many implicit-equation solvers (e.g., the Colebrook friction-factor equation) are special cases of fixed-point iteration for a particular choice of g.

References

WebsiteWikipedia — Fixed-point iteration
BookBurden, R. L. & Faires, J. D. Numerical Analysis, 10th ed. Cengage, 2015.