Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Fixed-point iteration
Summary
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).
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.