Fixed point iteration


Fixed point iteration

In numerical analysis, fixed point iteration is a method of computing fixed points of iterated functions.

More specifically, given a function f defined on the real numbers with real values and given a point x_0 in the domain of f, the fixed point iteration is

:x_{n+1}=f(x_n), , n=0, 1, 2, dots

which gives rise to the sequence x_0, x_1, x_2, dots which is hoped to converge to a point x. If f is continuous, then one can prove that the obtained x is a fixed point of f, i.e.,

:f(x)=x.

More generally, the function "f" 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 f(x)=frac 12left(frac ax + x ight), i.e. the mean value of "x" and "a/x", to approach the limit x = sqrt a (from whatever starting point x_0 gg 0 ). This is a special case of Newton's method quoted below.

* The fixed point iteration x_{n+1}=cos x_n, converges to the unique fixed point of the function f(x)=cos x, for any starting point x_0. This example does satisfy the hypotheses of the Banach fixed point theorem. Hence, the error after n steps satisfies |x_n-x_0| leq { q^n over 1-q } | x_1 - x_0 | = C q^n (where we can take q = 0.85, if we start from x_0=1.) When the error is less than a multiple of q^n 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 x_{n+1}=2x_n, will diverge unless x_0=0. We say that the fixed point of f(x)=2x, is repelling.

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

Applications

* Newton's method for a given differentiable function f(x) is x_{n+1}=x_n-frac{f(x_n)}{f'(x_n)}. If we write g(x)=x-frac{f(x)}{f'(x)} we may rewrite the Newton iteration as the fixed point iteration x_{n+1}=g(x_n). If this iteration converges to a fixed point x of g then x=g(x)=x-frac{f(x)}{f'(x)} so frac{f(x)}{f'(x)}=0. The inverse of anything is nonzero, therefore f(x)=0: x is a "root" of f. Assuming the hypotheses of the Banach fixed point theorem are satisfied, we have that the Newton iteration converges linearly. However, a more detailed analysis shows that under certain circumstances, |x_n-x|. This is called "quadratic convergence".

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

* Runge-Kutta methods 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 y'=ay, where a is a complex number, and to check whether the ODE solver converges to the fixed point y=0 whenever the real part of a is negative. [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.]

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

Properties

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

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.

Notes

ee also

* Banach fixed point theorem


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Fixed point (mathematics) — Not to be confused with a stationary point where f (x) = 0. A function with three fixed points In mathematics, a fixed point (sometimes shortened to fixpoint, also known as an invariant point) of a function is a point[1] that is …   Wikipedia

  • Fixed-point combinator — Y combinator redirects here. For the technology venture capital firm, see Y Combinator (company). In computer science, a fixed point combinator (or fixpoint combinator[1] ) is a higher order function that computes a fixed point of other functions …   Wikipedia

  • Fixed point combinator — A fixed point combinator (or fixed point operator) is a higher order function that computes a fixed point of other functions. This operation is relevant in programming language theory because it allows the implementation of recursion in the form… …   Wikipedia

  • Théorèmes de point fixe — En analyse, un théorème de point fixe est un résultat qui permet d affirmer qu une fonction f admet sous certaines conditions un point fixe. Ces théorèmes se révèlent être des outils très utiles en mathématiques, principalement dans le domaine de …   Wikipédia en Français

  • Misiurewicz point — A Misiurewicz point is a parameter in the Mandelbrot set (the parameter space of quadratic polynomials) for which the critical point is strictly preperiodic (i.e., it becomes periodic after finitely many iterations but is not periodic itself). By …   Wikipedia

  • Theoremes de point fixe — Théorèmes de point fixe En analyse, un théorème de point fixe est un résultat qui permet d affirmer qu une fonction f admet sous certaines conditions un point fixe. Ces théorèmes se révèlent être des outils très utiles en mathématiques,… …   Wikipédia en Français

  • Théorème du point fixe — Théorèmes de point fixe En analyse, un théorème de point fixe est un résultat qui permet d affirmer qu une fonction f admet sous certaines conditions un point fixe. Ces théorèmes se révèlent être des outils très utiles en mathématiques,… …   Wikipédia en Français

  • Iterated function — In mathematics, iterated functions are the objects of deep study in computer science, fractals and dynamical systems. An iterated function is a function which is composed with itself, repeatedly, a process called iteration.DefinitionThe formal… …   Wikipedia

  • Durand–Kerner method — In numerical analysis, the Durand–Kerner method established 1960–66 and named after E. Durand and Immo Kerner, also called the method of Weierstrass, established 1859–91 and named after Karl Weierstrass, is a root finding algorithm for… …   Wikipedia

  • Durand-Kerner method — In numerical analysis, the Durand ndash;Kerner method (established 1960 ndash;66) or method of Weierstrass (established 1859 ndash;91) is a root finding algorithm for solving polynomial equations. In other words, the method can be used to solve… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.