Content deleted Content added
→Iterative methods: added fixed point iteration as one of the root finding algorithms. Tags: Mobile edit Mobile app edit Android app edit |
|||
Line 42:
=== Steffensen's method ===
If we use a polynomial fit to remove the quadratic part of the finite difference used in the Secant method, so that it better approximates the derivative, we obtain [[Steffensen's method]], which has quadratic convergence, and whose behavior (both good and bad) is essentially the same as Newton's method but does not require a derivative.
=== Fixed point iteration method ===
We can use the [[fixed-point iteration]] to find the root of a function. Given a function which we have set to zero to find the root (<math> f(x)=0 </math>), we rewrite the equation in terms of <math> x </math> so that <math> f(x)=0 </math> becomes <math> x=g(x) </math> (note, there are often many <math> g(x)=0 </math> functions for each <math> f(x)=0 </math> function. Next, we relabel the each side of the equation as <math> x_{n+1}=g(x_{n}) </math> so that we can perform the iteration. Next, we pick a value for <math> x_{1} </math> and perform the iteration until it converges towards a root of the function. If the iteration converges, it will converge to a root. The iteration will only converge if <math> |g'(root)|<1 </math>.
==== Example ====
If given the function <math> f(x)=x^2+x-1 </math>, we will rewrite it as one of the following equations.
:<math> x_{n+1}=(1/x_n) - 1 </math>,
:<math> x_{n+1}=1/(x_n+1) </math>,
:<math> x_{n+1}=x_n^2+2x_n-1 </math>, or
:<math> x_{n+1}=\pm \sqrt{1-x_n} </math>.
=== Inverse interpolation ===
| |||