Math Club 2015-09-11

2273 days ago by calkin

A=plot(x^2-2, (x,0,3)) show(A) 
       
B=plot(2*x-3,(x,0,3),color='red') show(A+B) 
       
def newton_iterate(x): a=x/2+1/x return(a) 
       
x0=1 xlist=[x0] N=10 for j in range(N): current_x = xlist[-1] new_x = current_x/2 + 1/current_x xlist.append(new_x) for appr in xlist: print appr 
       
print sqrt(2.) for appr in xlist: print appr.n(),(appr -sqrt(2)).n(digits=14) 
       
N = 20 a_list=[2,3] b_list=[1,2] for i in range(1,N): a=a_list[i] b=b_list[i] a_list.append(a^2 + 2*b^2) #b_list.append(2*a*b) #b_list = b_list + [2*a*b] b_list += [2*a*b] 
       
for j in range(len(b_list)): print exp((log(b_list[j])/2^j).n()) 
       
for j in range(len(b_list)): print (b_list[j]/(1+sqrt(2))^(2^j)).n() 
       
for i in range(10): print b_list[i], floor(sqrt(2)/4*(1+sqrt(2))^(2^i)) 
       
N = 15 a_list=[1] b_list=[1] for i in range(N): a=a_list[i] b=b_list[i] a_list.append(a^2 + 4*b^2) #b_list.append(2*a*b) #b_list = b_list + [2*a*b] b_list += [2*a*b] 
       
for j in range(5): print j, a_list[j],b_list[j] 
       

Continuing our investigations into the approximations using Newton's method of $\sqrt{4}$.

Starting with $x_0=1$, $x_1=5/2$, and 

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

we can write 

\[ x_n = \frac{a_n}{b_n}\]

in which $a_n, b_n$ are integers with no common factors.  Then 

\[ \frac{a_{n+1}}{b_{n+1}} = \frac{a_n}{2b_n} + \frac{2b_n}{a_n} = \frac{a_n^2 + 4 b_n^2}{2a_nb_n} \]

Now, for $n\geq 1$, we have $a_n$ is odd  and $b_n$ is even, so $a_n^2+ 4b_n^2$ is odd.  Furthermore, any odd prime divisor of $2a_nb_n$ must {\em fail} to divide $a_n^2 + 4b_n^2$, since $a_n$ and $b_n$ have no common factors.

Hence 

\[ a_{n+1} = a_n^2 + 4b_n^2 \mbox{ and } b_{n+1} = 2a_nb_n .\]

Proving that $an-2b_n =1$.

We'll prove this by induction.  Suppose that $a_n - 2b_n=1$.  Then 

\[ a_{n+1} - 2 b_{n+1} = (a_n^2 + 4 b_n^2) -2 (2a_nb_n)\]  

\[ = (a_n^2  + 4 b_n^2) - 2(4 a_n b_n) \]

\[= a_n^2- 4 a_nb_n + 4 b_n^2 = (a_n-2b_n)^2 = 1^2 = 1 \]

How big is $x_n - 2$?

\[ x_n-2 = \frac{a_n}{b_n} - 2 = \frac{a_n -2b_n }{b_n} = \frac{1}{b_n}.\]