Fixed point iteration

Fixed point iteration is a simple method for solving the root of an equation. That is to say, it's a bad method to use for solving the root of an equation.

Given any function f(x) = 0, we can find a function g(x) such that x = g(x). Either use algebra to solve for x, or add x to each side.

Ex: x4 - 2x + 9 = 0

    g(x) = x = (x4 + 9)/2

    tan(x) = 0

    g(x) = x = tan(x) + x

Now, to try and find the root of an equation, we first make a guess as to the root. When we plug that value into g(x), it gives us a new value of x! This value of x should be more accurate than your initial guess. If you plug the new guess into g(x), the value you come out with should be even more accurate. Repeat until dead. Or just keep doing it until the estimate is close enough to the actual root.

 x(n+1) = g(xn)

Why is this a bad method to use? Well, for one thing, it will only be converging if |g`(x)| (n+1) is actually getting further away from the real root. This is not good.

Even if |g`(x)| actually is less than 1, that isn't any guarantee that the method will find the root.

Another reason that you shouldn't use this method is because it's slow. Other methods such as the Newton-Raphson method, the "regula falsi" method, or Müller's method work a lot quicker, although they are more complicated than this one.

I suggest avoiding this method if you can. I don't know why they still teach it to us.

Node Your Homework!

Let g(x) (continuous on the interval [a,b]) be bounded between a and b, for all x on the interval [a,b]. Suppose additionally that g' exists on (a,b) and that a constant 0 < k < 1 exists with

|g'(x)| <= k, for all x on the interval (a,b)

p_n = g(p_n-1), n >= 1

a <= g(x) <= b

Finally, something of note is that if you want to solve for the root of an equation using fixed-point iteration, and you transpose/manipulate the equation just right, to where it has the form g(x) = (function)/(function's derivative), with the same fixed point(s) as your original equation, Voila! You have Newton's Method with very rapid convergence.