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

  • I
  • Thread starter Thread starter PLAGUE
  • Start date Start date
  • Tags Tags
    Numerical analysis
PLAGUE
Messages
35
Reaction score
2
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?
 
Last edited:
Mathematics news on Phys.org
You need two dollars or two hashes to delimit your Latex.
 
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.
 
Last edited:
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.
 
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.##
 
Last edited:
Reply
  • Like
Likes AlexB23, PeroK and PLAGUE
fresh_42 said:
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.
 
PAllen said:
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!
 
Also, note that g’(x) greater than one near the root.
 
PLAGUE said:
$$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.
 
  • #10
PAllen said:
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).
 
  • #11
PAllen said:
A sufficient contrition is different from a necessary condition.
Right! Missed that.
 
  • #12
fresh_42 said:
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.
 
  • #13
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).
 
Last edited:
  • #14
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.
 
Last edited:
  • #15
PAllen said:
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)
 
  • #16
PLAGUE said:
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)
 
  • #17
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).
 
Last edited:

Similar threads

MHB Fixed point,, Jacobi- & Newton Method, Linear Systems
Replies
7
Views
2K
MHB Fixed point iteration: g is a contraction mapping
Replies
17
Views
3K
MHB For which values of a can we solve it iteratively?
Replies
10
Views
1K
I Convergence criterion for Newton-Raphson
Replies
9
Views
2K
I Verifying pointwise convergence of indicator functions
Replies
4
Views
1K
I Looking for Guarantees that the method of fixed-point iteration will work
Replies
22
Views
2K
I Convergence not defined by any metric
Replies
17
Views
970
I Proof for interpolating polynomial and error approximation
Replies
6
Views
2K
I How to get metric field using a path dependent parallel propagator
Replies
24
Views
1K
Show Picard iteration diverges
Replies
2
Views
1K

Hot Threads

Recent Insights

Back
Top