Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Fixed-point iteration
Résumé
In numerical analysis, fixed-point iteration is a method of computing fixed points of a function.
More specifically, given a function defined on the real numbers with real values and given a point in the domain of , the fixed-point iteration is
which gives rise to the sequence of iterated function applications which 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 can be defined on any metric space with values in that same space.
A first simple and useful example is the Babylonian method for computing the square root of 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 method quoted below.
The fixed-point iteration converges to the unique fixed point of the function for any starting point This example does satisfy (at the latest after the first iteration step) the assumptions 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 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 as this function is not continuous at , and in fact has no fixed points.
An attracting fixed point of a function f is a fixed point xfix of f such that for any value of x in the domain that is close enough to xfix, the fixed-point iteration sequence
converges to xfix.
The natural cosine function ("natural" means in radians, not degrees or other units) has exactly one fixed point, and that fixed point is attracting. In this case, "close enough" is not a stringent criterion at all—to demonstrate this, start with any real number and repeatedly press the cos key on a calculator (checking first that the calculator is in "radians" mode).
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Proximité ontologique