World Library  
Flag as Inappropriate
Email this Article

Fixed-point iteration

Article Id: WHEBN0007344320
Reproduction Date:

Title: Fixed-point iteration  
Author: World Heritage Encyclopedia
Language: English
Subject: Chase (algorithm), Iterative methods, Fixed point, Mean value analysis, Method of successive substitution
Collection: Iterative Methods, Root-Finding Algorithms
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Fixed-point iteration

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.

Contents

  • Examples 1
  • Applications 2
  • Properties 3
  • See also 4
  • References 5
  • External links 6

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 xn+1 = sin xn with initial value x0 = 2 converges to 0. This example does not satisfy the assumptions 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 assumptions 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}

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

Applications

  • Newton's method for finding roots of 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 f(x)/f'(x)=0.
The inverse of anything is nonzero, therefore f(x)=0: x is a root of f. Under the assumptions of the Banach fixed point theorem, the Newton iteration, framed as the fixed point method, demonstrates linear convergence. However, a more detailed analysis shows quadratic convergence, i.e.,
|x_n-x|, under certain circumstances.
  • Halley's method is similar to Newton's method but, when it works correctly, its error is |x_n-x| (cubic convergence). In general, it is possible to design methods that converge with speed Cq^{k^n} 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'=ay, 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, constructing the solution to the equation. Solving an ODE in this way is called Picard iteration, Picard's method, or the Picard iterative process.

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.
Proof of this theorem:
Since f is Lipschitz continuous with Lipschitz constant L<1, then for the sequence \{x_n,n=0,1,2...\}, we have:
|x_2-x_1|=|f(x_1)-f(x_0)|\leq L|x_1-x_0|,
|x_3-x_2|=|f(x_2)-f(x_1)|\leq L|x_2-x_1|,
\cdots,
and
|x_n-x_{n-1}|=|f(x_{n-1})-f(x_{n-2})|\leq L|x_{n-1}-x_{n-2}|.
Combining the above inequalities yields:
|x_n-x_{n-1}|\leq L^{n-1}|x_1-x_0|.
Since L<1, L^{n-1}\rightarrow 0 as n \rightarrow \infty.
Therefore, we can show \{x_n\} is a Cauchy sequence and thus it converges to a point x^*.
For the iteration x_n=f(x_{n-1}), let n go to infinity on both sides of the equation, we obtain x^*=f(x^*). This shows that x^* is the fixed point for f. So we proved the iteration will eventually converge to a fixed-point.
This property is very useful because not all iterations can arrive at a convergent fixed-point. When constructing a fixed-point iteration, it is very important to make sure it converges. There are several fixed-point theorems to guarantee the existence of the fixed point, but since the iteration function is continuous, we can usually use the above theorem to test if an iteration converges or not. The proof of the generalized theorem to metric space is similar.

See also

References

  1. ^ 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.
  2. ^ M A Kumar (2010), Solve Implicit Equations (Colebrook) Within Worksheet, Createspace, ISBN 1-4528-1619-0
  3. ^ Bellman, R. (1957). Dynamic programming, Princeton University Press.
  4. ^ Sniedovich, M. (2010). Dynamic Programming: Foundations and Principles, Taylor & Francis.
  • Burden, Richard L.; Faires, J. Douglas (1985). "2.2 Fixed-Point Iteration". Numerical Analysis (3rd ed.). PWS Publishers. .  

External links

  • Fixed-point algorithms online
  • Fixed-point iteration online calculator
  • Fixed-point iteration online calculator (Mathematical Assistant on Web)
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 



Copyright © World Library Foundation. All rights reserved. eBooks from World eBook Library are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.