# Fixed-point iteration

Jump to navigation Jump to search

{{ safesubst:#invoke:Unsubst||$N=Refimprove |date=__DATE__ |$B= {{#invoke:Message box|ambox}} }} {{#invoke:main|main}} In numerical analysis, fixed-point iteration is a method of computing fixed points of iterated functions.

More specifically, given a function ${\displaystyle f}$ defined on the real numbers with real values and given a point ${\displaystyle x_{0}}$ in the domain of ${\displaystyle f}$, the fixed point iteration is

${\displaystyle x_{n+1}=f(x_{n}),\,n=0,1,2,\dots }$

which gives rise to the sequence ${\displaystyle x_{0},x_{1},x_{2},\dots }$ which is hoped to converge to a point ${\displaystyle x}$. If ${\displaystyle f}$ is continuous, then one can prove that the obtained ${\displaystyle x}$ is a fixed point of ${\displaystyle f}$, i.e.,

${\displaystyle f(x)=x}$.

More generally, the function ${\displaystyle f}$ can be defined on any metric space with values in that same space.

## Examples

The fixed-point iteration xn+1 = sin xn with initial value x0 = 2 converges to 0. This example does not satisfy the assumptions of the Banach fixed point theorem and so its speed of convergence is very slow.
• The requirement that f is continuous is important, as the following example shows. The iteration
${\displaystyle x_{n+1}={\begin{cases}{\frac {x_{n}}{2}},&x_{n}\neq 0\\1,&x_{n}=0\end{cases}}}$

converges to 0 for all values of ${\displaystyle x_{0}}$. However, 0 is not a fixed point of the function

${\displaystyle f(x)={\begin{cases}{\frac {x}{2}},&x\neq 0\\1,&x=0\end{cases}}}$

as this function is not continuous at ${\displaystyle x=0}$, and in fact has no fixed points.

## Applications

• Newton's method for finding roots of a given differentiable function f(x) is
${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}}$.
If we write ${\displaystyle g(x)=x-{\frac {f(x)}{f'(x)}}}$, we may rewrite the Newton iteration as the fixed-point iteration ${\displaystyle x_{n+1}=g(x_{n})}$.
If this iteration converges to a fixed point Template:Mvar of Template:Mvar, then
${\displaystyle x=g(x)=x-{\frac {f(x)}{f'(x)}}}$, so ${\displaystyle f(x)/f'(x)=0}$.
The inverse of anything is nonzero, therefore f(x)=0: Template:Mvar is a root of Template:Mvar. Under the assumptions of the Banach fixed point theorem, the Newton iteration, framed as the fixed point method, demonstrates linear convergence. However, a more detailed analysis shows quadratic convergence, i.e.,
${\displaystyle |x_{n}-x|, under certain circumstances.
• The Picard–Lindelöf theorem, which shows that ordinary differential equations have solutions, is essentially an application of the Banach fixed point theorem to a special sequence of functions which forms a fixed point iteration, constructing the solution to the equation. Solving an ODE in this way is called Picard iteration, Picard's method, or the Picard iterative process.

## Properties

Proof of this theorem:
Since ${\displaystyle f}$ is Lipschitz continuous with Lipschitz constant ${\displaystyle L<1}$, then for the sequence ${\displaystyle \{x_{n},n=0,1,2...\}}$, we have:
${\displaystyle |x_{2}-x_{1}|=|f(x_{1})-f(x_{0})|\leq L|x_{1}-x_{0}|}$,
${\displaystyle |x_{3}-x_{2}|=|f(x_{2})-f(x_{1})|\leq L|x_{2}-x_{1}|}$,
${\displaystyle \cdots }$,
and
${\displaystyle |x_{n}-x_{n-1}|=|f(x_{n-1})-f(x_{n-2})|\leq L|x_{n-1}-x_{n-2}|}$.
Combining the above inequalities yields:
${\displaystyle |x_{n}-x_{n-1}|\leq L^{n-1}|x_{1}-x_{0}|}$.
Since ${\displaystyle L<1}$, ${\displaystyle L^{n-1}\rightarrow 0}$ as ${\displaystyle n\rightarrow \infty }$.
Therefore, we can show ${\displaystyle \{x_{n}\}}$ is a Cauchy sequence and thus it converges to a point ${\displaystyle x^{*}}$.
For the iteration ${\displaystyle x_{n}=f(x_{n-1})}$, let ${\displaystyle n}$ go to infinity on both sides of the equation, we obtain ${\displaystyle x^{*}=f(x^{*})}$. This shows that ${\displaystyle x^{*}}$ is the fixed point for ${\displaystyle f}$. So we proved the iteration will eventually converge to a fixed-point.
This property is very useful because not all iterations can arrive at a convergent fixed-point. When constructing a fixed-point iteration, it is very important to make sure it converges. There are several fixed-point theorems to guarantee the existence of the fixed point, but since the iteration function is continuous, we can usually use the above theorem to test if an iteration converges or not. The proof of the generalized theorem to metric space is similar.

## References

1. One may also consider certain iterations A-stable if the iterates stay bounded for a long time, which is beyond the scope of this article.
2. M A Kumar (2010), Solve Implicit Equations (Colebrook) Within Worksheet, Createspace, ISBN 1-4528-1619-0
3. Bellman, R. (1957). Dynamic programming, Princeton University Press.
4. Sniedovich, M. (2010). Dynamic Programming: Foundations and Principles, Taylor & Francis.
• {{#invoke:citation/CS1|citation

|CitationClass=book }}.