Thread: Fixed Point Iteration

1. Fixed Point Iteration

HI, I am just doing coursework atm and I don't really understand why I have to rearrange the equation to give x?
e.g x^3-8x+5=0
g1(x)=x^3+35/8
thanks

2. Taking the cube of something might bring you to too big a number...

I would suggest:

$x^3 -8x + 5 = 0$

$x(x^2 - 8) = -5$

$x = \dfrac{-5}{x^2 - 8}$

Having x large and in the denominator will make you closer to the solution

3. The idea behind a fixed-point iteration scheme is that you set up your iteration

$x_{n+1}=f(x_{n}),$

where $x-f(x)=0$ is the equation you're trying to solve. If the function $f$ is well-behaved enough (that is, its derivative is less than one in magnitude in an interval about your solution), then by the Banach Fixed Point Theorem, you're guaranteed that your iteration scheme will converge to a solution of the equation.

There are lots of ways to solve for x in your equation. One way is Unknown008's. And there might be others. The key is to finding a good scheme is the following:

1. Determine intervals containing roots of your equation.
2. Find an iteration scheme where the function on the RHS has a derivative less than 1 in magnitude on an interval which you know contains a root.
3. Start the iteration scheme in that interval.

Then you're guaranteed convergence.

In your case, you can show, using the Intermediate Value Theorem, that the intervals (-4,-2), (0,1), and (2,3) all contain roots of the expression $x^{3}-8x+5.$ (To show this, just claim that a cubic is continuous, and then evaluate the expression at the endpoints of each of those intervals. The expression changes sign in the interval, and therefore has a root there.) Let's take the interval (0,1) first. Your proposed iteration scheme is

$x_{n+1}=\dfrac{1}{8}(x_{n}^{3}+5).$

The derivative of the function on the RHS is

$f'(x)=\dfrac{1}{8}(3x^{2})=\dfrac{3x^{2}}{8}.$ On the interval (0,1), we can easily see that the derivative ranges from 0 to 3/8. Hence, it is nicely behaved on this interval. Therefore, your iteration scheme, if started in the interval (0,1), should converge to that root. And, indeed, I get the root 0.661120314127 this way.

Does this make sense?

The iteration scheme that just worked on (0,1) will not, I think, work well for finding the root in (-4,-2), but there's a different iteration scheme that will work for it.