2015 MATH 3600 2015.09.07 Cube roots

2453 days ago by calkin

This worksheet will investigate Newton's method to find $\sqrt[3]{m}$.

 

The recurrence is

\[  x_{n+1} = \frac{2x_n}{3} + \frac{m}{3x_n^2} \]

 

which leads to 

\[   a_{n+1} = 2a_n^3 + m b_n^3 \]

and

\[  b_{n+1}  = 3 a_n^2 b_n\]
m=1 def newton_cube(x): return(2*x/3 + m/(3*x^2)) 
       
newton_cube(1000).n() 
        
666.666667333333
666.666667333333
newton_cube(4/3) 
        
155/144
155/144
newton_cube(91/72) 
        
940195/894348
940195/894348
(newton_cube(1126819/894348)^3).n() 
        
1.15742112496514
1.15742112496514
2*72^3 
        
746496
746496
1126819^3 
        
1430745813712011259
1430745813712011259
2*894348^3 
        
1430703422454144384
1430703422454144384

\[  x_{n+1} = \frac{2x_n}{3} +  \frac{2}{3x_n^2} \]

so 

\[ a_{n+1} = 2 a_n^3 + 2 b_n^3 \]

and 

\[ b_{n+1} = 2 a_n^2 b_n \]

(not  relatively prime
100^(1/3.) 
        
4.64158883361278
4.64158883361278
m=2 a0=1 b0=10000 N=13 a_list=[a0] b_list=[b0] for j in range(N): anew=2*a_list[j]^3 + m*b_list[j]^3 bnew=3*a_list[j]^2*b_list[j] #print j, factor(gcd(anew,bnew)) a_list.append(anew) b_list.append(bnew) print 'ratio cubed is', (anew/bnew)^3.n() print j+1,exp((log(bnew)/3^(j+1)).n())/(a0+b0) print j+1, bnew/(-1+b0*sqrt(2.))^(3^(j+1)) 
        
ratio cubed is 2.96296296297185e23
1 0.00310692181377248
1 1.06088520360338e-8
ratio cubed is 8.77914951991660e22
2 0.192304826298903
2 1.59200311573855e-8
ratio cubed is 2.60122948738270e22
3 0.738186910711232
3 2.39104615006580e-8
ratio cubed is 7.70734662928206e21
4 1.14431026360066
4 3.60029076269501e-8
ratio cubed is 2.28365826052802e21
5 1.31993830836785
5 5.46265673355810e-8
ratio cubed is 6.76639484600894e20
6 1.38273984189257
6 8.48047926703125e-8
ratio cubed is 2.00485773215080e20
7 1.40381018775935
7 1.41022151517848e-7
ratio cubed is 5.94031920637273e19
8 1.41073037066657
8 2.88207737873006e-7
ratio cubed is 1.76009457966600e19
9 1.41298645523345
9 1.09339735727062e-6
ratio cubed is 5.21509505086221e18
10 1.41371986992094
10 0.0000265346064861493
ratio cubed is 1.54521334840362e18
11 1.41395795334425
11 0.168552045594713
ratio cubed is 4.57840992119590e17
12 1.41403516570552
12 1.92006370544324e10
ratio cubed is 1.35656590257656e17
13 1.41406018485401
13 1.26147297918662e43
ratio cubed is 2.96296296297185e23
1 0.00310692181377248
1 1.06088520360338e-8
ratio cubed is 8.77914951991660e22
2 0.192304826298903
2 1.59200311573855e-8
ratio cubed is 2.60122948738270e22
3 0.738186910711232
3 2.39104615006580e-8
ratio cubed is 7.70734662928206e21
4 1.14431026360066
4 3.60029076269501e-8
ratio cubed is 2.28365826052802e21
5 1.31993830836785
5 5.46265673355810e-8
ratio cubed is 6.76639484600894e20
6 1.38273984189257
6 8.48047926703125e-8
ratio cubed is 2.00485773215080e20
7 1.40381018775935
7 1.41022151517848e-7
ratio cubed is 5.94031920637273e19
8 1.41073037066657
8 2.88207737873006e-7
ratio cubed is 1.76009457966600e19
9 1.41298645523345
9 1.09339735727062e-6
ratio cubed is 5.21509505086221e18
10 1.41371986992094
10 0.0000265346064861493
ratio cubed is 1.54521334840362e18
11 1.41395795334425
11 0.168552045594713
ratio cubed is 4.57840992119590e17
12 1.41403516570552
12 1.92006370544324e10
ratio cubed is 1.35656590257656e17
13 1.41406018485401
13 1.26147297918662e43

It appears that for $m=2$, when one of $a,b$ is equal to 1, and the other is very large, then 

$b_n$ grows like $(a_0\sqrt{2})^{3^n}$ or  $(b_0\sqrt{2})^{3^n}$!
 
       
sqrt(2.)*(1+3.^(1/3.)) 
        
3.45386246502860
3.45386246502860
sqrt(2.)*3^(1/3.) 
        
2.03964890265551
2.03964890265551
m 
        
2
2
m=2 x0=1 newton_list=[x0] N=10 for j in range(N): x=newton_list[-1] newton_list.append(newton_cube(x)) 
       
for j in range(len(newton_list)): print j,len(continued_fraction(newton_list[j])),3^j 
        
0 1 1
1 2 3
2 6 9
3 15 27
4 37 81
5 114 243
6 321 729
7 996 2187
8 2863 6561
9 8699 19683
10 26217 59049
0 1 1
1 2 3
2 6 9
3 15 27
4 37 81
5 114 243
6 321 729
7 996 2187
8 2863 6561
9 8699 19683
10 26217 59049
2.^(1/3) 
        
1.25992104989487
1.25992104989487
3.^(1/3) 
        
1.44224957030741
1.44224957030741