Fixed-point computation refers to the process of computing an exact or approximate fixed point of a given function. In its most common form, the given function ${\displaystyle f}$ satisfies the condition to the Brouwer fixed-point theorem: that is, ${\displaystyle f}$ is continuous and maps the unit d-cube to itself. The Brouwer fixed-point theorem guarantees that ${\displaystyle f}$ has a fixed point, but the proof is not constructive. Various algorithms have been devised for computing an approximate fixed point. Such algorithms are used in various tasks, such as

The unit interval is denoted by ${\displaystyle E:=[0,1]}$, and the unit d-dimensional cube is denoted by ${\displaystyle E^{d}}$. A continuous function ${\displaystyle f}$ is defined on ${\displaystyle E^{d}}$ (from ${\displaystyle E^{d}}$ to itself). Often, it is assumed that ${\displaystyle f}$ is not only continuous but also Lipschitz continuous, that is, for some constant ${\displaystyle L}$, ${\displaystyle |f(x)-f(y)|\leq L\cdot |x-y|}$ for all ${\displaystyle x,y}$ in ${\displaystyle E^{d}}$.

A fixed point of ${\displaystyle f}$ is a point ${\displaystyle x}$ in ${\displaystyle E^{d}}$ such that ${\displaystyle f(x)=x}$. By the Brouwer fixed-point theorem, any continuous function from ${\displaystyle E^{d}}$ to itself has a fixed point. But for general functions, it is impossible to compute a fixed point precisely, since it can be an arbitrary real number. Fixed-point computation algorithms look for approximate fixed points. There are several criteria for an approximate fixed point. Several common criteria are:

For Lipschitz-continuous functions, the absolute criterion is stronger than the residual criterion: If ${\displaystyle f}$ is Lipschitz-continuous with constant ${\displaystyle L}$, then ${\displaystyle |x-x_{0}|\leq \delta }$ implies ${\displaystyle |f(x)-f(x_{0})|\leq L\cdot \delta }$. Since ${\displaystyle x_{0}}$ is a fixed-point of ${\displaystyle f}$, this implies ${\displaystyle |f(x)-x_{0}|\leq L\cdot \delta }$, so ${\displaystyle |f(x)-x|\leq (1+L)\cdot \delta }$. Therefore, a δ-absolute fixed-point is also an ε-residual fixed-point with ${\displaystyle \varepsilon =(1+L)\cdot \delta }$.

The most basic step of a fixed-point computation algorithm is a value query: given any ${\displaystyle x}$ in ${\displaystyle E^{d}}$, the algorithm is provided with an oracle ${\displaystyle {\tilde {f}}}$ to ${\displaystyle f}$ that returns the value ${\displaystyle f(x)}$. The accuracy of the approximate fixed-point depends upon the error in the oracle ${\displaystyle {\tilde {f}}(x)}$.

The function ${\displaystyle f}$ is accessible via evaluation queries: for any ${\displaystyle x}$, the algorithm can evaluate ${\displaystyle f(x)}$. The run-time complexity of an algorithm is usually given by the number of required evaluations.

A Lipschitz-continuous function with constant ${\displaystyle L}$ is called contractive if ${\displaystyle L<1}$; it is called weakly-contractive if ${\displaystyle L\leq 1}$. Every contractive function satisfying Brouwer's conditions has a unique fixed point. Moreover, fixed-point computation for contractive functions is easier than for general functions.

The first algorithm for fixed-point computation was the fixed-point iteration algorithm of Banach. Banach's fixed-point theorem implies that, when fixed-point iteration is applied to a contraction mapping, the error after ${\displaystyle t}$ iterations is in ${\displaystyle O(L^{t})}$. Therefore, the number of evaluations required for a ${\displaystyle \delta }$-relative fixed-point is approximately ${\displaystyle \log _{L}(\delta )=\log(\delta )/\log(L)=\log(1/\delta )/\log(1/L)}$. Sikorski and Wozniakowski showed that Banach's algorithm is optimal when the dimension is large. Specifically, when ${\displaystyle d\geq \log(1/\delta )/\log(1/L)}$, the number of required evaluations of any algorithm for ${\displaystyle \delta }$-relative fixed-point is larger than 50% the number of evaluations required by the iteration algorithm. Note that when ${\displaystyle L}$ approaches 1, the number of evaluations approaches infinity. No finite algorithm can compute a ${\displaystyle \delta }$-absolute fixed point for all functions with ${\displaystyle L=1}$.