Fixed point iteration
numerical analysis, fixed point iteration is a method of computing fixed points of iterated functions.
More specifically, given a function defined on the
real numbers with real values and given a point in the domain of , the fixed point iterationis
which gives rise to the
sequencewhich is hoped to converge to a point . If is continuous, then one can prove that the obtained is a fixed point of , i.e.,
More generally, the function "f" can be defined on any
metric spacewith values in that same space.
* A first simple and useful example is the
Babylonian methodfor computing the square rootof "a">0, which consists in taking , i.e. the mean value of "x" and "a/x", to approach the limit (from whatever starting point ). This is a special case of Newton's methodquoted below.
* The fixed point iteration converges to the unique fixed point of the function for any starting point This example does satisfy the hypotheses of the
Banach fixed point theorem. Hence, the error after n steps satisfies (where we can take , if we start from .) When the error is less than a multiple of 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 will diverge unless . We say that the fixed point of is repelling.
* The requirement that "f" is continuous is important, as the following example shows. The iteration :converges to 0 for all values of .However, 0 is "not" a fixed point of the function:this function is "not" continuous at , and in fact has no fixed points.
Newton's methodfor a given differentiable function is . If we write we may rewrite the Newton iteration as the fixed point iteration . If this iteration converges to a fixed point of then so . The inverse of anything is nonzero, therefore : x is a "root" of f. Assuming the hypotheses of the Banach fixed point theoremare satisfied, we have that the Newton iteration converges linearly. However, a more detailed analysis shows that under certain circumstances,
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 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 ) 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