Thread: Numerical analysis- fixed point iteration method

1. Numerical analysis- fixed point iteration method

Q. Compute by the method of fixed point iteration a real root of the equation x^3 + x^2 - 1 =0 correct up to two decimal places.

In the above problem if we take f(x)=0, then to solve it we can write f(x) in the form of x=g(x). Now g(x) can take three different forms.
i) 1/sqrt(1+x)
ii) 1/x+x^2
iii) -1+ (1/x^2)

Now my question is, for which form of g(x) I can be sure that the obtained root converges to the actual root?

2. Re: Numerical analysis- fixed point iteration method

Originally Posted by fpb
Q. Compute by the method of fixed point iteration a real root of the equation x^3 + x^2 - 1 =0 correct up to two decimal places.

In the above problem if we take f(x)=0, then to solve it we can write f(x) in the form of x=g(x). Now g(x) can take three different forms.
i) 1/sqrt(1+x)
ii) 1/x+x^2
iii) -1+ (1/x^2)

Now my question is, for which form of g(x) I can be sure that the obtained root converges to the actual root?
Looking at the Wiki on Fixed-point iteration I see we let

$g(x) = x- \dfrac{f(x)}{f^\prime(x)}$

in this case $g(x)=x-\dfrac{x^3+x^2-1}{3 x^2+2 x}$

and let

$x_{n+1}=g(x_n)$

This recurrence will converge to some $x_f$ and $f(x_f)=0$

I used $x_0=1$ and this recurrence converged very quickly to $x_f \approx 0.754878$

------------------------
Playing with the 3 functions you specified only the first one converges and it does converge to the correct root.

Looking a bit further at the Wiki page it looks like this is because the first function is the only one that is Lipschitz continuous.

3. Re: Numerical analysis- fixed point iteration method

The method you explained above is called Newton- Raphson method which has 2nd order rate of convergence. But I dont think N-R method and fixed point iteration method are same.

4. Re: Numerical analysis- fixed point iteration method

"Newton-Raphson" is a specific type of "fixed point iteration".

But where did you get these "g" functions? I don't see that any of them are equivalent to this problem. Starting from $x^3+ x^2- 1= 0$ we can get $x^2= 1- x^3$ and then $x= \frac{1- x^3}{x}= \frac{1}{x}- x^2$ not $\frac{1}{x}+ x^2$. Or taking the square root of both sides of $x^2= 1- x^3$, $x= \sqrt{1- x^3}$ but not [tex]\frac{1}{\sqrt{1+ x}}. Or we can write $x^3= 1- x^2$ and then $x= \frac{1- x^2}{x^2}= \frac{1}{x^2}- 1$ but not $1- \frac{1}{x^2}$.

In any case, how fast a fixed point iteration, x= g(x), converges depends on the derivatives of g. If p= g(p) and |f'(p)| lies between 0 and 1, we have linear convergence. If |f'(p)|= 0 and |f''(p)| lies between 0 and 1, we have quadratic convergence, etc.