AI Glossary / Mathematics and optimization / Advanced
Fixed-point computation
Definition
Fixed-point computation is the task of finding a value x such that applying a specified mapping G leaves it unchanged: G(x) = x. Numerical methods often seek an approximate fixed point to a stated tolerance. One basic approach repeatedly applies the mapping, forming x_next = G(x), but the existence of a fixed point alone does not guarantee that this iteration converges to it.
What it means
A fixed point is a self-consistent value for an update rule. If an estimate is fed through that rule and comes back unchanged, it satisfies the fixed-point equation.
The idea appears in models with feedback and in iterative numerical methods. It should be distinguished from fixed-point arithmetic, which is a way of representing numbers with a fixed scaling convention. It should also be distinguished from optimization: a fixed point is not automatically a minimum or maximum unless the mapping connects it to that objective under suitable assumptions.
How it works
For basic fixed-point iteration, choose an initial value x0, compute x1 = G(x0), and continue. Monitor a stopping criterion and any restrictions on the allowed domain.
A useful sufficient condition is contraction: distances between mapped points shrink by at least a uniform factor q < 1. On a nonempty closed subset of Euclidean space that the mapping sends into itself, this condition gives a unique fixed point in that subset and convergence from any starting point there.
For such a contraction, the residual r(x) = ||G(x) - x|| gives the bound ||x - x_star|| <= r(x)/(1 - q). This follows by combining the contraction inequality with the triangle inequality. Without appropriate assumptions, a small update or residual does not by itself provide the same error guarantee.
Three practical examples
1. Feedback model: A planning calculation says the next workload estimate equals a baseline plus a fraction of the current estimate. Solving the fixed-point equation gives a self-consistent modeled workload.
2. Numerical solver: An equation is rearranged into x = G(x), then solved by iteration. Different rearrangements of the same equation can produce very different convergence behavior, even though they share the desired solution.
3. Iterative software: A program repeats an update until a residual falls below a threshold. Reporting the threshold is useful, but explaining how it relates to solution error is necessary when the result must meet a numerical accuracy requirement.
Think of it this way
Think of repeatedly revising a plan using one consistent review rule. A fixed point is a plan that the rule no longer changes. Some rules steadily bring revisions closer together. Others make the plan oscillate or drift farther away, even when an unchanged plan exists in principle.
Worked example
Consider the original scalar mapping G(x) = (x + 3)/4. Solving x = G(x) gives 4x = x + 3, hence x_star = 1. The mapping contracts distances by a factor of 1/4, because |G(x) - G(y)| = |x - y|/4.
Starting at x0 = 0 produces x1 = 3/4, x2 = 15/16, x3 = 63/64, and x4 = 255/256. The corresponding errors from one are 1/4, 1/16, 1/64, and 1/256. Each iteration reduces the error by a factor of four.
At x3 = 63/64, the residual is |G(x3) - x3| = 3/256. Dividing by 1 - q = 3/4 gives an error bound of 1/64, which equals the actual error here. At x4, the error is 1/256, approximately 0.00390625, meeting an absolute error target of 0.005. At x3 it does not.
Now consider the rearranged mapping H(x) = 4x - 3. Its fixed-point equation also has solution one. However, starting from zero gives -3, -15, and -63. The errors grow by a factor of four rather than shrinking. Having the correct fixed point is therefore insufficient to justify the basic iteration.
Finally, let J(x) = 0.999x + 0.1. Its fixed point is 100. At x = 90, the residual is only 0.01, but the solution error is ten. The contraction bound gives 0.01/(1 - 0.999) = 10, explaining why a small residual alone can be misleading. These calculations were checked with exact fractions.
Illustrative case study
In a fictional capacity-planning tool, a developer uses the slow mapping J from the worked example. The program stops when the update is no larger than 0.01 and reports the result near 90 as sufficiently close to equilibrium.
A reviewer asks what numerical error the threshold actually certifies. Because the contraction factor is 0.999, a residual of 0.01 permits an error of ten. To certify error at most 0.1 using this bound, the residual must be at most 0.0001.
The team revises the stopping rule and records the convergence assumptions. It also recognizes that the simple affine example can be solved directly.
Common misconceptions and mistakes
A fixed point need not attract nearby iterates. An iteration that stops changing in floating-point arithmetic may have stagnated rather than achieved the desired mathematical accuracy. A small residual is not automatically a small solution error.
Contraction is a useful sufficient condition, not a necessary condition for every convergent method. Uniqueness supplied by a theorem applies within its stated domain. Different initial values can behave differently when the relevant global assumptions do not hold.
Business use
Fixed-point methods can support iterative models and numerical components inside analytical systems. Teams should state the update mapping, domain, initial conditions, stopping rule, and evidence for convergence. For decisions sensitive to numerical error, relate the stopping test to an error bound where possible. Also distinguish solving the model accurately from validating the model's assumptions and inputs.
People also ask
Is repeated substitution the only method?
No. Fixed-point equations can also be approached through other equation-solving or acceleration methods when their assumptions apply.
Does a fixed point always exist?
No. For example, G(x) = x + 1 has no real fixed point.
Can the same equation lead to a bad iteration?
Yes. The mappings G and H in the example demonstrate this.
Check your understanding
What is the fixed point of G(x) = (x + 3)/4?
Answer: One.
Why does iteration with H(x) = 4x - 3 fail from zero?
Answer: Its error grows by a factor of four at each step.
What residual certifies error at most 0.1 when q = 0.999?
Answer: At most 0.0001 using the stated bound.
Related terms
- Fixed point
- Residual
- Convergence
- Root finding
- contraction mapping
- numerical iteration
Learn next
Compare residual and solution error for several affine mappings with different contraction factors. Then study how nonlinear behavior changes the role of the initial guess and domain, and why acceleration methods require their own convergence analysis.
More in Mathematics and optimization
- Absolute error loss - Absolute error loss measures a numerical prediction's error as the absolute difference between its predicted and reference values: L(y,y-hat)=|y-y-hat|.
- Active-set method - An active-set method is an optimization approach that works with a changing subset of constraints believed to be tight at the solution.
- Adjoint state method - The adjoint state method computes how a chosen objective changes when the parameters of a mathematical model change.
- Σ-algebra
- Algebraic connectivity - Algebraic connectivity is the second-smallest eigenvalue of a graph's Laplacian matrix.
- Algorithm IMED - Algorithm IMED, short for Indexed Minimum Empirical Divergence, is a method for choosing actions in a stochastic multi-armed bandit problem.
Sources
David Bindel, Cornell Numerical Analysis notes on fixed points and contraction mappings: https://www.cs.cornell.edu/~bindel/class/cs4220-s16/lec/2016-04-06-notes.pdf
The affine mappings, residual calculations, and fictional planning case are original illustrations. The residual bound is derived from contraction and the triangle inequality.
Previous: Fixed-point characterization Next: Fixed-point equation