Javascript required
Skip to content Skip to sidebar Skip to footer
Home / Fixed Point Iteration Finding the Solution Accurate

Fixed Point Iteration Finding the Solution Accurate

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 { x0} 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 {x0, x1, x2,… } 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.

{\displaystyle f(x)=x.\,}

More generally, the function {f} can be defined on any metric space with values in that same space.

Contents

  • Examples
  • Applications
  • Properties
  • References
  • External links

Examples

Applications

  • Newton's method for finding roots of a given differentiable function {f(x)} is
{\displaystyle 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 pointx ofg, then

x=g(x)=x-{\frac {f(x)}{f'(x)}}

, so

{\displaystyle f(x)/f'(x)=0.}

The reciprocal of anything is nonzero, thereforef(x) = 0:x is aroot off. 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

, under certain circumstances.

  • Halley's method is similar to Newton's method but, when it works correctly, its error is |x_{n}-x|<Cq^{3^n} (cubic convergence). In general, it is possible to design methods that converge with speed Cq^{k^{n}} for any {k from {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.[a]
  • 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 calledPicard iteration,Picard's method, or thePicard iterative process.
  • The iteration capability in Excel can be used to find solutions to the Colebrook equation to an accuracy of 15 significant figures.[1][2]
  • Some of the "successive approximation" schemes used in dynamic programming to solve Bellman's functional equation are based on fixed point iterations in the space of the return function.[3][4]

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 {x0} 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

{\displaystyle \{x_{n},n=0,1,2,\ldots \}}

, we have:

{\displaystyle {\begin{aligned}|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}|,\\&\,\,\,\vdots \end{aligned}}}

and

{\displaystyle |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:

{\displaystyle |x_{n}-x_{n-1}|\leq L^{n-1}|x_{1}-x_{0}|.}

Since

L^{n-1}\rightarrow 0

as

n \rightarrow \infty.

Therefore, we can show xn 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.

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

Fixed Point Matlab Code

  • Get Matlab code for Fixed Point Method

References

  1. ^ M A Kumar (2010), Solve Implicit Equations (Colebrook) Within Worksheet, Createspace, ISBN 1-4528-1619-0
  2. ^ 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
  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. ISBN 0-87150-857-5..

External Links

  • Fixed-point algorithms online
  • Fixed-point iteration online calculator (Mathematical Assistant on Web)

Fixed Point Iteration Finding the Solution Accurate

Source: https://codetobuy.com/fixed-point-iteration/