en>Helpful Pixie Bot: ISBNs (Build KC)

2012-05-05T23:40:03Z

ISBNs (Build KC)

New page

{{refimprove|date=May 2010}}

In [[numerical analysis]], '''fixed-point iteration''' is a method of computing [[fixed point (mathematics)|fixed points]] of [[iterated function]]s.

More specifically, given a function <math>f</math> defined on the [[real number]]s with real values and given a point <math>x_0</math> in the [[domain of a function|domain]] of <math>f</math>, the fixed point [[iteration]] is

:<math>x_{n+1}=f(x_n), \, n=0, 1, 2, \dots</math>

which gives rise to the [[sequence]] <math>x_0, x_1, x_2, \dots</math> which is hoped to [[limit (mathematics)|converge]] to a point <math>x</math>. If <math>f</math> is continuous, then one can prove that the obtained <math>x</math> is a fixed point of <math>f</math>, i.e.,

:<math>f(x)=x</math>.

More generally, the function <math>f</math> can be defined on any [[metric space]] with values in that same space.

==Examples==

* A first simple and useful example is the [[Babylonian method]] for computing the [[square root]] of ''a''>0, which consists in taking <math>f(x)=\frac 12\left(\frac ax + x\right)</math>, i.e. the mean value of ''x'' and ''a/x'', to approach the limit <math>x = \sqrt a</math> (from whatever starting point <math>x_0 \gg 0 </math>). This is a special case of [[Newton's method]] quoted below.

[[File:Sine fixed point.svg|250px|thumb|The fixed-point iteration ''x''''n''+1 = sin ''x''''n'' with initial value ''x''0 = 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 fixed-point iteration <math>x_{n+1}=\cos x_n\,</math> converges to the unique fixed point of the function <math>f(x)=\cos x\,</math> for any starting point <math>x_0.</math> This example does satisfy the assumptions of the [[Banach fixed point theorem]]. Hence, the error after n steps satisfies <math>|x_n-x_0| \leq { q^n \over 1-q } | x_1 - x_0 | = C q^n</math> (where we can take <math>q = 0.85</math>, if we start from <math>x_0=1</math>.) When the error is less than a multiple of <math>q^n</math> for some constant ''q'', we say that we have [[linear convergence]]. The Banach fixed-point theorem allows one to obtain fixed-point iterations with linear convergence.

* The fixed-point iteration <math>x_{n+1}=2x_n\,</math> will diverge unless <math>x_0=0</math>. We say that the fixed point of <math>f(x)=2x\,</math> is repelling.

* The requirement that ''f'' is continuous is important, as the following example shows. The iteration
:<math> x_{n+1} =
\begin{cases}
\frac{x_n}{2}, & x_n \ne 0\\
1, & x_n=0
\end{cases}</math>
converges to 0 for all values of <math>x_0</math>.
However, 0 is ''not'' a fixed point of the function
:<math>f(x) =
\begin{cases}
\frac{x}{2}, & x \ne 0\\
1, & x = 0
\end{cases}</math>
as this function is ''not'' continuous at <math>x=0</math>, and in fact has no fixed points.

==Applications==
* [[Newton's method]] for a given differentiable function <math>f(x)</math> is <math>x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}</math>. If we write <math>g(x)=x-\frac{f(x)}{f'(x)}</math> we may rewrite the Newton iteration as the fixed point iteration <math>x_{n+1}=g(x_n)</math>. If this iteration converges to a fixed point <math>x</math> of <math>g</math> then <math>x=g(x)=x-\frac{f(x)}{f'(x)}</math> so <math>\frac{f(x)}{f'(x)}=0</math>. The inverse of anything is nonzero, therefore <math>f(x)=0</math>: x is a ''root'' of f. 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., <math>|x_n-x|<Cq^{2^n}</math>, under certain circumstances.

* [[Halley's method]] is similar to [[Newton's method]] but, when it works correctly, its error is <math>|x_n-x|<Cq^{3^n}</math> ([[cubic convergence]]). In general, it is possible to design methods that converge with speed <math>Cq^{k^n}</math> for any <math>k\in \Bbb N</math>. As a general rule, the higher the <math>k</math>, the less stable it is, and the more computationally expensive it gets. For these reasons, higher order methods are typically not used.

* [[Runge-Kutta method]]s and numerical [[Ordinary Differential Equation]] solvers in general can be viewed as fixed point iterations. Indeed, the core idea when analyzing the [[A-stability]] of ODE solvers is to start with the special case <math>y'=ay</math>, where a is a [[complex number]], and to check whether the ODE solver converges to the fixed point <math>y=0</math> whenever the real part of a is negative.<ref>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.</ref>

* 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.

* The [[goal seeking]] function in Excel can be used to find solutions to the [[Colebrook equation]] to an accuracy of 15 significant figures.<ref>M A Kumar (2010), Solve Implicit Equations (Colebrook) Within Worksheet, Createspace, ISBN 1-4528-1619-0
</ref>

* Some of the "successive approximation" schemes used in [[dynamic programming]] to solve [[Bellman equation|Bellman's functional equation]] are based on fixed point iterations in the space of the return function.<ref>Bellman, R. (1957). Dynamic programming, Princeton University Press.</ref><ref>Sniedovich, M. (2010). Dynamic Programming: Foundations and Principles, [[Taylor & Francis]].</ref>

==Properties==

* If a function <math>f</math> defined on the real line with real values is [[Lipschitz continuity|Lipschitz continuous]] with Lipschitz constant <math>L<1</math>, then this function has precisely one fixed point, and the fixed-point iteration converges towards that fixed point for any initial guess <math>x_0.</math> This theorem can be generalized to any metric space.

:Proof of this theorem:

:Since <math>f</math> is Lipschitz continuous with Lipschitz constant <math>L<1</math>, then for the sequence <math>\{x_n,n=0,1,2...\}</math>, we have:

:<math>|x_2-x_1|=|f(x_1)-f(x_0)|\leq L|x_1-x_0|</math>,

:<math>|x_3-x_2|=|f(x_2)-f(x_1)|\leq L|x_2-x_1|</math>,

:<math>\cdots</math>,

:and

:<math>|x_n-x_{n-1}|=|f(x_{n-1})-f(x_{n-2})|\leq L|x_{n-1}-x_{n-2}|</math>.

:Combining the above inequalities yields:

:<math>|x_n-x_{n-1}|\leq L^{n-1}|x_1-x_0|</math>.

:Since <math>L<1</math>, <math>L^{n-1}\rightarrow 0</math> as <math>n \rightarrow \infty</math>.

:Therefore, we can show <math>\{x_n\}</math> is a [[Cauchy sequence]] and thus it converges to a point <math>x^*</math>.

:For the iteration <math>x_n=f(x_{n-1})</math>, let <math>n</math> go to infinity on both sides of the equation, we obtain <math>x^*=f(x^*)</math>. This shows that <math>x^*</math> is the fixed point for <math>f</math>. 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 theorem]]s 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.

* The speed of convergence of the iteration sequence can be increased by using a [[convergence acceleration]] method such as [[Aitken's delta-squared process]]. The application of Aitken's method to fixed-point iteration is known as [[Steffensen's method]], and it can be shown that Steffensen's method yields a rate of convergence that is at least quadratic.

==References==

<references/>
* {{cite book| last1=Burden | first1=Richard L. | last2=Faires | first2=J. Douglas
| title=Numerical Analysis | publisher=PWS Publishers | edition=3rd | isbn=0-87150-857-5
| year=1985 | chapter=2.2 Fixed-Point Iteration}}.

==See also==

* [[Root-finding algorithm]]
* [[Fixed-point theorem]]
* [[Fixed-point combinator]]
* [[Banach fixed-point theorem]]
* [[Cobweb plot]]
* [[Markov chain]]

==External links==
*[http://algonum.appspot.com/#fixpoint.picard Fixed-point algorithms online]
*[http://www.maccery.com/maths/fixed_point.php Fixed-point iteration online calculator]
*[http://user.mendelu.cz/marik/maw/index.php?lang=en&form=banach Fixed-point iteration online calculator (Mathematical Assistant on Web)]

{{DEFAULTSORT:Fixed-Point Iteration}}
[[Category:Root-finding algorithms]]
[[Category:Iterative methods]]

Characteristic function (convex analysis) - Revision history

en>Helpful Pixie Bot: ISBNs (Build KC)