Fixed-point iteration
This article needs additional citations for verification. (May 2010) |
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
More generally, the function 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 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 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 functionas this function is not continuous at , and in fact has no fixed points.
Attracting fixed points
An attracting fixed point of a function f is a fixed point xfix of f with a neighborhood U of "close enough" points around xfix such that for any value of x in U, the fixed-point iteration sequence
The natural
Not all fixed points are attracting. For example, 0 is a fixed point of the function f(x) = 2x, but iteration of this function for any value other than zero rapidly diverges. We say that the fixed point of is repelling.
An attracting fixed point is said to be a stable fixed point if it is also
A fixed point is said to be a neutrally stable fixed point if it is
Multiple attracting points can be collected in an attracting fixed set.
Banach fixed-point theorem
The Banach fixed-point theorem gives a sufficient condition for the existence of attracting fixed points. A contraction mapping function defined on a complete metric space has precisely one fixed point, and the fixed-point iteration is attracted towards that fixed point for any initial guess in the domain of the function. Common special cases are that (1) is defined on the real line with real values and is Lipschitz continuous with Lipschitz constant , and (2) the function f is continuously differentiable in an open neighbourhood of a fixed point xfix, and .
Although there are other
Attractors
Attracting fixed points are a special case of a wider mathematical concept of
Iterative methods
In computational mathematics, an iterative method is a mathematical procedure that uses an initial value to generate a sequence of improving approximate solutions for a class of problems, in which the n-th approximation is derived from the previous ones. Convergent fixed-point iterations are mathematically rigorous formalizations of iterative methods.
Iterative method examples
- root-finding algorithmfor finding roots of a given differentiable function . The iteration is
If we write , we may rewrite the Newton iteration as the fixed-point iteration .
If this iteration converges to a fixed point of g, then , so
therefore , that is, is a root of . Under the assumptions of thequadratic convergence, i.e., , under certain circumstances. - Halley's method is similar to Newton's method when it works correctly, but its error is (cubic convergence). In general, it is possible to design methods that converge with speed for any . 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.
- A-stabilityof ODE solvers is to start with the special case , where is a complex number, and to check whether the ODE solver converges to the fixed point whenever the real part of is negative.price theory corresponds to the fixed-point iteration of the composition of the supply function and the demand function.[7]
Convergence acceleration
The speed of convergence of the iteration sequence can be increased by using a
Chaos game
The term chaos game refers to a method of generating the
See also
References
- ^ 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.
- ISBN 978-1-4939-1106-6.
- ^ Weisstein, Eric W. "Dottie Number". Wolfram MathWorld. Wolfram Research, Inc. Retrieved 23 July 2016.
- ISBN 1-4528-1619-0
- ^ Brkic, Dejan (2017) Solution of the Implicit Colebrook Equation for Flow Friction Using Excel, Spreadsheets in Education (eJSiE): Vol. 10: Iss. 2, Article 2. Available at: https://sie.scholasticahq.com/article/4663-solution-of-the-implicit-colebrook-equation-for-flow-friction-using-excel
- ^ Bellman, R. (1957). Dynamic programming, Princeton University Press.
- ^ Sniedovich, M. (2010). Dynamic Programming: Foundations and Principles, Taylor & Francis.
- ISBN 978-4-431-54971-0.
Further reading
- Burden, Richard L.; Faires, J. Douglas (1985). "Fixed-Point Iteration". Numerical Analysis (Third ed.). PWS Publishers. ISBN 0-87150-857-5.
- Hoffman, Joe D.; Frankel, Steven (2001). "Fixed-Point Iteration". Numerical Methods for Engineers and Scientists (Second ed.). New York: CRC Press. pp. 141–145. ISBN 0-8247-0443-6.
- ISBN 0-262-10071-1.
- ISBN 978-0486477053.
- Shashkin, Yuri A. (1991). "9. The Iteration Method". Fixed Points (First ed.). American Mathematical Society. ISBN 0-8218-9000-X.
- S2CID 247259939.