Does convergence require a globally contractive map?

No. Other conditions can suffice, including local convergence from suitable starts, but their scope must be stated.

What does linear convergence mean here?

It means the error shrinks geometrically by a fixed factor, not that the iterates move along a straight line in ordinary coordinates.

Can changing the starting point help?

Sometimes. Different starts can lie in different regions of attraction, though changing a start does not repair every unstable mapping.

AI Glossary / Mathematics and optimization / Intermediate

Fixed-point iteration

Definition

Fixed-point iteration is a numerical procedure that repeatedly applies a mapping to its current estimate: x_(k+1) = T(x_k). It aims to approach a value x* satisfying T(x*) = x*. Many optimization and equation-solving methods can be expressed this way. Success depends on the mapping, starting point and domain; repeating a rule is not itself evidence that the sequence will converge.

What it means

Each new estimate becomes the input for the next calculation. The method can be simple to implement and may avoid solving a large equation directly. However, algebraically equivalent formulations can behave very differently when iterated. A good mapping draws relevant estimates toward a solution, while a poor one can produce oscillation or divergence. The central questions are whether the iterates remain valid, whether their error decreases, and whether the limiting point, if any, solves the intended original problem.

How it works

Choose an initial estimate, calculate T at that estimate, and repeat while monitoring appropriate stopping criteria. A useful sufficient condition is that T maps a nonempty closed subset of Euclidean space into itself and is a contraction there: distances shrink by at least a uniform factor q with 0 ≤ q < 1. Then the iteration converges to the unique fixed point in that set. The requirement that the set is preserved matters. More general convergence results exist, but they need their own assumptions rather than a blanket assertion that repeated updates work.

Three practical examples

A scalar calibration equation can be solved by an update whose slope keeps nearby errors shrinking.
A linear-system solver can express its matrix splitting as a fixed-point iteration and analyze the resulting error propagation.
An optimization method can repeatedly apply a gradient or proximal update while monitoring a residual appropriate to its underlying solution condition.

Think of it this way

Think of adjusting a dial using a rule that corrects a fraction of the remaining discrepancy each time. Sensible corrections can settle toward a target, while overcorrection can create growing swings. The analogy assumes a target and informative corrections; a general mapping may have neither. Mathematical conditions establish when the reassuring picture is justified.

Worked example

Take T(x) = 0.25x + 6 on the real line. Its fixed point is 8, and its contraction factor is q = 0.25. Starting at x_0 = 0 gives x_1 = 6, x_2 = 7.5, x_3 = 7.875 and x_4 = 7.96875. The errors from 8 are 8, 2, 0.5, 0.125 and 0.03125: each is a quarter of the preceding error. At x_3, the residual magnitude is |T(x_3) − x_3| = 0.09375. A contraction gives the error bound |x_3 − x*| ≤ 0.09375/(1 − 0.25) = 0.125, which is exact here. To obtain error at most 0.01 from this start, use 8(0.25)^k ≤ 0.01. At k = 4 the error is 0.03125; at k = 5 it is 0.0078125, so five updates suffice. Compare S(x) = 16 − x, which has the same fixed point 8 but cycles between 0 and 16 from zero. Its slope magnitude is one rather than strictly below one. The correct solution exists, yet this iteration fails to approach it from that starting value.

Illustrative case study

In a fictional numerical prototype, Elm Calibration uses repeated updates for an offset estimate. The team logs both consecutive changes and the residual of the original equation. A trial mapping alternates between two values, so increasing the iteration limit simply repeats the cycle. Engineers derive another mapping and verify its behavior on a controlled example before applying it to their data. The case illustrates diagnosis of the update rule rather than an invented improvement in measurement quality.

Common misconceptions and mistakes

A small change between iterates is not always a reliable error estimate. If a mapping is close to the identity, it can move very little while remaining far from a fixed point. A residual-to-error bound needs additional information, such as a contraction factor. Contraction is sufficient, not necessary, for convergence. A local slope condition near a fixed point does not prove convergence from every starting value. In multidimensional problems, updating coordinates simultaneously and updating them sequentially define different procedures unless a special equivalence is established.

Business use

Use the method when the mapping is inexpensive to evaluate and its numerical behavior is understood. Specify the domain, initial estimate, tolerances and maximum workload. Keep an independent check of the original problem, especially when the mapping came from an algebraic rearrangement. Record termination status so a resource limit is not mistaken for convergence. If evaluations are noisy or approximate, assess how that affects stopping criteria and accuracy. Compare alternatives using both the number and cost of evaluations; a faster-converging iteration can still be more expensive per step.

Check your understanding

Why do five updates suffice for the worked affine iteration's 0.01 error target?

Answer: Its exact error after k updates is 8(0.25)^k. The fourth error exceeds 0.01, while the fifth is 0.0078125.

Related terms

Fixed point
Residual
contraction mapping
convergence rate
initialization
relaxation

Learn next

reproduce the affine sequence and verify the residual bound at each step. Then use a slope close to one and observe how a small residual can correspond to a larger error. Compare a cycling map with a relaxed update and investigate what conditions the modification changes.

Residual

Sources

Sources: David Bindel, Cornell CS 4220, Fixed point iteration and Newton, https://www.cs.cornell.edu/courses/cs4220/2026sp/lec/2026-03-27.html ; Jung and colleagues, The Aalto Dictionary of Machine Learning, https://aaltodictionaryofml.github.io/ADictML_Main.pdf ; SciPy, fixed_point, https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.fixed_point.html . The affine iteration, stopping calculation, residual bound evaluation and fictional calibration case are original.

Previous: Fixed-point equation Next: Fixed-point solving