Fixed-point iteration

Level UniversityDifficulty ★★★★★Method⌖ Open in the map

What is it?

Rewrite the equation as $x = g(x)$ and iterate $x_{k+1} = g(x_k)$ . If $g$ is a contraction ( $|g'| \le q < 1$ ), Banach's theorem guarantees a unique fixed point and linear convergence with ratio $q$ .

Formulas

|g(x) - g(y)| \le q\,|x - y|,\ q < 1 \implies |x_k - x^\ast| \le \frac{q^k}{1 - q}\,|x_1 - x_0|

Where it shows up in computing

Scientific computing★★★★★frequentScientific computing and algorithms
Jacobi and Gauss–Seidel solvers, and many self-consistent schemes, are fixed-point iterations.

Where it shows up in AI

Reinforcement learning★★★★★fundamentalAI and machine learning
Value iteration converges because the Bellman operator is a $\gamma$ -contraction.

Where is it used?

Computing topics reachable from here, through the chain of ideas that leads to them:

λ Scientific computing and algorithms

Scientific computing★★★★★

ℒ AI and machine learning

Reinforcement learning★★★★★

This page has the essentials. A fuller treatment (intuition, formal definition, worked example) is on the way.