Fixed point iteration

El directorio enciclopédico desde la Wikipedia.

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.

1 Examples
2 Applications
3 Properties
4 Notes
5 See also

[edit] 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 12\left(\frac ax + x\right)$ , 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 = sin x_n with initial value x₀ = 2 converges to 0. This example does not satisfy the hypotheses of the Banach fixed point theorem and so its speed of convergence is very slow.

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} = \begin{cases} \frac{x_n}{2}, & x_n \ne 0\\ 1, & x_n=0 \end{cases}$

converges to 0 for all values of $x 0$ . However, 0 is not a fixed point of the function

$f(x) = \begin{cases} \frac{x}{2}, & x \ne 0\\ 1, & x = 0 \end{cases}$

this function is not continuous at $x = 0$ , and in fact has no fixed points.

[edit] 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|<Cq^{n^2}$ . 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|<Cq^{n^3}$ (cubic convergence). In general, it is possible to design methods that converge with speed $Cq^{n^k}$ for any $k\in \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' = a y$ , 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.^[1]

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.

[edit] 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.

[edit] Notes

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

[edit] See also

Banach fixed point theorem

Página espejo de la Wikipedia

Directorio de Enlaces Directorio dmoz Directorio espejo dmoz Pedro Bernardo