I Why fixed point iteration of ##x^3 = 1-x^2## doesn't converge when ##x_0= 0##

[PLAGUE]

TL;DR Summary

I am solving $$x^3 = 1 - x^2$$ and wrote $$x = \sqrt[3]{1-x^2}$$. I took $x_0 = 0$. But we don't get the root although $$g'(x_0) = 0<1$$. Why it doesn't converge here?

I am new to numerical methods and am currently learning Fixed point iteration. I have learned that if you can express $$x = g(x)$$, and $$|g'(x_0)|<1$$, then the sequence, $$x_{n+1} = g(x_n)$$ converges to the root.

I am solving $$x^3 = 1 - x^2$$ and wrote $$x = \sqrt[3]{1-x^2}$$. I took $$x_0 = 0$$. But we don't get the root although $$g'(x_0) = 0<1$$. Why it doesn't converge here?

 

[PeroK]

You need two dollars or two hashes to delimit your Latex.

 

[PAllen]

The derivative can’t be zero at any guess. This is assumed in derivations of convergence of the method. It is also required that an initial guess be sufficiently close to a root.

From an old numerical methods text I have, the sufficient condition for convergence is:
Abs(g’(x)) less than one and not zero near the root and that the initial guess is near the root.

 

[Mark44]

I don't recognize the technique you're using for solving the equation $x^3 + x^2 - 1 = 0$, so I'm not able to tell you why your approach isn't working. There's another numerical method called the Newton's Method (https://en.wikipedia.org/wiki/Newton's_method also Newton-Raphson Method) that is one of the first root-finding methods that are presented in numerical methods courses.

To numerically solve the equation $f(x) = 0$, construct the sequence $x_{n + 1} = x_n - \frac{f(x_n}{f'(x_n)}$ starting from an initial guess of $x_0$ for the root of the equation in question. The success of this method hinges on several factors, among them the choice of the initial guess for the root.

 

[fresh_42]

You are looking for a fixed point of the function $g(x)=\sqrt[3]{1-x^2}.$ The first thing is to check whether we have a contraction. $g(x)$ is a contraction if and only if $h(x)=1-x^2$ is one. So we must show that
\begin{align*}
\left|1-x^2-(1-y^2)\right|&=\left|(x-y)(x+y)\right|\\
&=\left|x-y\right|\cdot\left|x+y\right|\\
&\stackrel{!}{\leq } \lambda \left|x-y\right|
\end{align*}
for some $\lambda\in [0,1).$
This is equivalent to
$$
\left|x+y\right|< \lambda
$$
which is generally not the case, so we must look closer at the actual conditions we need.

The theorem behind the fixed point iteration goes in our case:

If $g\, : \,[0,1]\longrightarrow [0,1]$ is continuously differentiable with $g(0)>0\, , \,g(1)<1$ and $g'(x)\neq 1$ for all $x\in [0,1]$ then there is exactly on point $x^\ast\in [0,1]$ with $g(x^{\ast})=x^{\ast}.$

We have
$$
g(0)=1>0\, , \,g(1)=0<1\, , \,g'(x)=-\dfrac{2x}{3\sqrt[3]{(1-x^2)^2}}\neq 1\text{ on }[0,1]
$$
so the conditions are fulfilled except that $g'$ isn't continuous at $x=1.$ So we need to narrow down our interval a bit, say we consider $x\in [0,0.9]$ for which $g(0.9)<0.9$ still holds, so let's start the iteration. If we start with $x_0=0$ then $g(0)=1$ and our iteration breaks down since $x=1$ isn't in the domain anymore. But we needed $x<1$ since $g'$ wasn't defined/continuous at $x=1.$ So the problem is our first iteration step, not the starting point.

The devil is in the details, especially in numerics. Or you start with an interval for which $\left|x+y\right|<\lambda<1$ holds for all values of $x,y.$ In $[0,1]$ we would get $\left|x+y\right|=2$ which isn't less than $1.$

 

[PLAGUE]

You are looking for a fixed point of the function $g(x)=\sqrt[3]{1-x^2}.$ The first thing is to check whether we have a contraction. $g(x)$ is a contraction if and only if $h(x)=1-x^2$ is one. So we must show that
\begin{align*}
\left|1-x^2-(1-y^2)\right|&=\left|(x-y)(x+y)\right|\\
&=\left|x-y\right|\cdot\left|x+y\right|\\
&\stackrel{!}{\leq } \lambda \left|x-y\right|
\end{align*}
for some $\lambda\in [0,1).$
This is equivalent to
$$
\left|x+y\right|< \lambda
$$
which is generally not the case, so we must look closer at the actual conditions we need.

The theorem behind the fixed point iteration goes in our case:

If $g\, : \,[0,1]\longrightarrow [0,1]$ is continuously differentiable with $g(0)>0\, , \,g(1)<1$ and $g'(x)\neq 1$ for all $x\in [0,1]$ then there is exactly on point $x^\ast\in [0,1]$ with $g(x^{\ast})=x^{\ast}.$

We have
$$
g(0)=1>0\, , \,g(1)=0<1\, , \,g'(x)=-\dfrac{2x}{3\sqrt[3]{(1-x^2)^2}}\neq 1\text{ on }[0,1]
$$
so the conditions are fulfilled except that $g'$ isn't continuous at $x=1.$ So we need to narrow down our interval a bit, say we consider $x\in [0,0.9]$ for which $g(0.9)<1$ still holds, so let's start the iteration. If we start with $x_0=0$ then $g(0)=1$ and our iteration breaks down since $x=1$ isn't in the domain anymore. But we needed $x<1$ since $g'$ wasn't defined/continuous at $x=1.$ So the problem is our first iteration step, not the starting point.

The devil is in the details, especially in numerics. Or you start with an interval for which $\left|x+y\right|<\lambda<1$ holds for all values of $x,y.$ In $[0,1]$ we would get $\left|x+y\right|=2$ which isn't less than $1.$

Finally, the savior! Thanks a lot.

 

[PLAGUE]

The derivative can’t be zero at any guess. This is assumed in derivations of convergence of the method. It is also required that an initial guess be sufficiently close to a root.

From an old numerical methods text I have, the sufficient condition for convergence is:
Abs(g’(x)) less than one and not zero near the root and that the initial guess is near the root.

$$x = 3/2 + (cosx)/2$$ here, if you assume $$x_0=0$$, then the derivative becomes 0. Yet, it converges!

 

[PAllen]

Also, note that g’(x) greater than one near the root.

 

[PAllen]

$$x = 3/2 + (cosx)/2$$ here, if you assume $$x_0=0$$, then the derivative becomes 0. Yet, it converges!

A sufficient contrition is different from a necessary condition.

 

[fresh_42]

Also, note that g’(x) greater than one near the root.

Yes, but we only need $\neq 1.$ It doesn't matter if the function decreases or increases, it just may not be stable (plus the other initial conditions).

 

[PLAGUE]

A sufficient contrition is different from a necessary condition.

Right! Missed that.

 

[PAllen]

Yes, but we only need $\neq 1.$ It doesn't matter if the function decreases or increases, it just may not be stable (plus the other initial conditions).

The question was about convergence. For that, the requirement is the the derivative condition holding in a neighborhood of the root.

 

[PAllen]

Looking over the convergence proof in the book I referenced, it seems tweaking the argument can remove the need to prohibit g’ being zero. However, this is irrelevant to the problem at hand. The key is simply that the condition on g’ must hold everywhere in a neighborhood of a root, AND the initial guess must be in this neighborhood, for convergence to be guaranteed. The derivative at some arbitrary point away from the root is wholly irrelevant. In this case, the derivative is greater than 1 in a neighborhood of the root, so no convergence is expected, no matter what initial guess you make (other than the root itself).

 

[PAllen]

Rechecking my work, I find that this is a very interesting case. The root is about .755, and g’(root) just under 1 in absolute value. However, by .8, abs(g’) is greater than 1. If the first iteration sends your guess above this, you won’t necessarily get convergence. So this is a case where the requirement of initial guess being close to the root is crucial. The iterations have to stay within the neighborhood where abs(g’) is less than 1. In this case, that means initial guess .71 is good, but .7 already send you outside the neighborhood. Also, because the derivative is close to 1 around the root, convergence is extremely slow. This method works best with g’ small in absolute value.

So the requirement of starting guess sufficiently close the root can be quantified by the requirement that iterations stay within the neighborhood where the derivative condition is met.

 

[PLAGUE]

Rechecking my work, I find that this is a very interesting case. The root is about .755, and g’(root) just under 1 in absolute value. However, by .8, abs(g’) is greater than 1. If the first iteration sends your guess above this, you won’t necessarily get convergence. So this is a case where the requirement of initial guess being close to the root is crucial. The iterations have to stay within the neighborhood where abs(g’) is less than 1. In this case, that means initial guess .71 is good, but .7 already send you outside the neighborhood. Also, because the derivative is close to 1 around the root, convergence is extremely slow. This method works best with g’ small in absolute value.

So the requirement of starting guess sufficiently close the root can be quantified by the requirement that iterations stay within the neighborhood where the derivative condition is met.

0 0.020000 0.999867 -0.013337 0.979867
1 0.999867 0.064367 -160.886288 0.935499
2 0.064367 0.998617 -0.043031 0.934250
3 0.998617 0.140340 -33.802368 0.858277
4 0.140340 0.993391 -0.094809 0.853052
5 0.993391 0.236176 -11.872960 0.757216
6 0.236176 0.981050 -0.163592 0.744875
7 0.981050 0.334837 -5.833554 0.646213
8 0.334837 0.961137 -0.241641 0.626300
9 0.961137 0.423981 -3.564515 0.537156
10 0.423981 0.936081 -0.322573 0.512100
11 0.936081 0.498330 -2.512975 0.437751
12 0.498330 0.909233 -0.401861 0.410903
13 0.909233 0.557522 -1.950111 0.351711
14 0.557522 0.883301 -0.476380 0.325778
15 0.883301 0.603480 -1.616932 0.279821
16 0.603480 0.859890 -0.544109 0.256410
17 0.859890 0.638732 -1.405123 0.221158
18 0.638732 0.839677 -0.603952 0.200945
19 0.839677 0.665649 -1.263369 0.174028
20 0.665649 0.822739 -0.655587 0.157089
21 0.822739 0.686193 -1.164873 0.136546
22 0.686193 0.808829 -0.699264 0.122636
23 0.808829 0.701897 -1.094509 0.106932
24 0.701897 0.797566 -0.735611 0.095670
25 0.797566 0.713931 -1.043190 0.083635
26 0.713931 0.788536 -0.765459 0.074605
27 0.788536 0.723177 -1.005173 0.065359
28 0.723177 0.781347 -0.789706 0.058170
29 0.781347 0.730300 -0.976675 0.051047
30 0.730300 0.775653 -0.809236 0.045353
31 0.775653 0.735800 -0.955118 0.039853
32 0.735800 0.771160 -0.824859 0.035360
33 0.771160 0.740054 -0.938699 0.031106
34 0.740054 0.767624 -0.837288 0.027570
35 0.767624 0.743350 -0.926126 0.024274
36 0.743350 0.764848 -0.847134 0.021497
37 0.764848 0.745908 -0.916459 0.018940
38 0.745908 0.762671 -0.854908 0.016763
39 0.762671 0.747895 -0.909002 0.014776
40 0.747895 0.760967 -0.861030 0.013072
41 0.760967 0.749439 -0.903236 0.011527
42 0.749439 0.759633 -0.865840 0.010194
43 0.759633 0.750641 -0.898769 0.008992
44 0.750641 0.758591 -0.869613 0.007950
45 0.758591 0.751576 -0.895303 0.007014
46 0.751576 0.757776 -0.872570 0.006200
47 0.757776 0.752305 -0.892611 0.005471
48 0.752305 0.757139 -0.874884 0.004835
49 0.757139 0.752872 -0.890518 0.004268
Apporximate root: 0.7528718305184433

You can see that it is converging even if the derivative is greater than 1. The columns are "Iteration #x_0# #g(x_0)# #g'(x_0)# tolerance"

Or, perhaps i made mistake in my code:

import math as mp
def g(x):
return (1-x**2)**(1/3)
def pg(x):
return (-2*x)*(1/3)*((1-x**2)**(-2/3))
x_0 =0.02
e = 0.0001
max_itr = 50
x_1 = g(x_0)
n=0
while(n<max_itr):
x_1 = g(x_0)
print("{:<10} {:<10.6f} {:<10.6f} {:<10.6f} {:<10.6f}".format(n,x_0,g(x_0), pg(x_0), abs(x_1 - x_0)))
if(abs(x_1 - x_0)< e):
print("Root found at ", x_1)
break;
x_0 = x_1
n+=1
print("Apporximate root: ", x_1)

 

[PLAGUE]

0 0.020000 0.999867 -0.013337 0.979867
1 0.999867 0.064367 -160.886288 0.935499
2 0.064367 0.998617 -0.043031 0.934250
3 0.998617 0.140340 -33.802368 0.858277
4 0.140340 0.993391 -0.094809 0.853052
5 0.993391 0.236176 -11.872960 0.757216
6 0.236176 0.981050 -0.163592 0.744875
7 0.981050 0.334837 -5.833554 0.646213
8 0.334837 0.961137 -0.241641 0.626300
9 0.961137 0.423981 -3.564515 0.537156
10 0.423981 0.936081 -0.322573 0.512100
11 0.936081 0.498330 -2.512975 0.437751
12 0.498330 0.909233 -0.401861 0.410903
13 0.909233 0.557522 -1.950111 0.351711
14 0.557522 0.883301 -0.476380 0.325778
15 0.883301 0.603480 -1.616932 0.279821
16 0.603480 0.859890 -0.544109 0.256410
17 0.859890 0.638732 -1.405123 0.221158
18 0.638732 0.839677 -0.603952 0.200945
19 0.839677 0.665649 -1.263369 0.174028
20 0.665649 0.822739 -0.655587 0.157089
21 0.822739 0.686193 -1.164873 0.136546
22 0.686193 0.808829 -0.699264 0.122636
23 0.808829 0.701897 -1.094509 0.106932
24 0.701897 0.797566 -0.735611 0.095670
25 0.797566 0.713931 -1.043190 0.083635
26 0.713931 0.788536 -0.765459 0.074605
27 0.788536 0.723177 -1.005173 0.065359
28 0.723177 0.781347 -0.789706 0.058170
29 0.781347 0.730300 -0.976675 0.051047
30 0.730300 0.775653 -0.809236 0.045353
31 0.775653 0.735800 -0.955118 0.039853
32 0.735800 0.771160 -0.824859 0.035360
33 0.771160 0.740054 -0.938699 0.031106
34 0.740054 0.767624 -0.837288 0.027570
35 0.767624 0.743350 -0.926126 0.024274
36 0.743350 0.764848 -0.847134 0.021497
37 0.764848 0.745908 -0.916459 0.018940
38 0.745908 0.762671 -0.854908 0.016763
39 0.762671 0.747895 -0.909002 0.014776
40 0.747895 0.760967 -0.861030 0.013072
41 0.760967 0.749439 -0.903236 0.011527
42 0.749439 0.759633 -0.865840 0.010194
43 0.759633 0.750641 -0.898769 0.008992
44 0.750641 0.758591 -0.869613 0.007950
45 0.758591 0.751576 -0.895303 0.007014
46 0.751576 0.757776 -0.872570 0.006200
47 0.757776 0.752305 -0.892611 0.005471
48 0.752305 0.757139 -0.874884 0.004835
49 0.757139 0.752872 -0.890518 0.004268
Apporximate root: 0.7528718305184433

You can see that it is converging even if the derivative is greater than 1. The columns are "Iteration #x_0# #g(x_0)# #g'(x_0)# tolerance"

Or perhaps, i made mistake in my code:
import math as mp
def g(x):
return (1-x**2)**(1/3)
def pg(x):
return (-2*x)*(1/3)*((1-x**2)**(-2/3))
x_0 =0.02
e = 0.0001
max_itr = 50
x_1 = g(x_0)
n=0
while(n<max_itr):
x_1 = g(x_0)
print("{:<10} {:<10.6f} {:<10.6f} {:<10.6f} {:<10.6f}".format(n,x_0,g(x_0), pg(x_0), abs(x_1 - x_0)))
if(abs(x_1 - x_0)< e):
print("Root found at ", x_1)
break;
x_0 = x_1
n+=1
print("Apporximate root: ", x_1)

 

[PAllen]

Read what I wrote more carefully. “You won’t necessarily get convergence”. The question is when it can be guaranteed. If any iteration leaves the neighborhood around the root with abs(g’) less than 1, then PROOF of convergence no longer applies.

Also, once you’ve reached a guess between approx .716 and .787, you have guaranteed convergence.

FYI, the root to 15 digits is: .754877666246693 (Newton-Raphson only needs 5 iterations to reach machine precision starting from guess of .5).