11
$\begingroup$

I know that Newton's method approximately doubles the number of the correct digits on each step, but I noticed that it also doubles the number of terms in the continued fraction, at least for square roots.

Explanation. If we start Newton's iterations with some partial convergent of the simple continued fraction for the square root, we get another convergent of the same continued fraction on each step, with double amount of CF terms.

Example. Finding the square root of $2$.

1) Start with $\frac{3}{2}$ which is also the first continued fraction convergent. Listing the values on each step and the number of terms in the continued fraction, we get:

$$ \begin{array}( \frac{3}{2} & 1 & \\ \frac{17}{12} & 3 & +2 \\ \frac{577}{408} & 7 & +4 \\ \frac{665857}{470832} & 15 & +8 \\ \cdots & 31 & +16 \end{array} $$

As you can see, the amount of CF terms (the position of this fraction in the list of all partial convergents) doubles on each step.

2) Start with $\frac{7}{5}$ which is the second continued fraction convergent.

$$ \begin{array}( \frac{7}{5} & 2 & \\ \frac{99}{70} & 5 & +3 \\ \frac{19601}{13860} & 11 & +6 \\ \cdots & 23 & +12 \end{array} $$

The same happens for other square roots I checked.

How does Newton's method 'jump' through the continued fraction this way, exactly doubling the number of CF terms at each step?

Can we prove this observation using the recurrence relations for the continued fraction?


Just in case, the Newton's method:

$$\frac{p_{n+1}}{q_{n+1}}=\frac{p_n^2+bq_n^2}{2p_nq_n}$$

$$\lim_{n \to \infty} \frac{p_{n}}{q_{n}}=\sqrt{b}$$

And the continued fraction recurrence:

$$\frac{P_{n+1}}{Q_{n+1}}=\frac{a_n P_n+P_{n-1}}{a_n Q_n+Q_{n-1}}$$

$$P_1=a_0,~~~Q_1=1,~~~P_0=1,~~~Q_0=0,~~~P_{-1}=0,~~~Q_{-1}=1$$

$$\lim_{n \to \infty} \frac{P_{n}}{Q_{n}}=a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cdots}}$$

How can we even relate these two?


A related question here. But I'm not asking about the digits, I'm asking about continued fraction terms.

$\endgroup$
  • $\begingroup$ The striking thing is that it is on the continued fractions in the first place. Knowing that, the "skipping" should follow directly from quadratic convergence. $\endgroup$ – Ian Apr 8 '16 at 15:57
  • $\begingroup$ @Ian, I'm more intetested in why the skipping is so precise (aways doubles) $\endgroup$ – Yuriy S Apr 8 '16 at 15:57
  • $\begingroup$ Oh, precisely doubles. That seems like a delicate matter; it wouldn't surprise me if it was specific to $\sqrt{2}$ even. $\endgroup$ – Ian Apr 8 '16 at 15:58
  • $\begingroup$ @Ian, also works for $\sqrt{5}$ at least. I'll check more later $\endgroup$ – Yuriy S Apr 8 '16 at 15:58
  • $\begingroup$ Would work the same way for any square root, I believe. $\endgroup$ – Ivan Neretin Apr 8 '16 at 16:21
2
$\begingroup$

First some experimentation might be in order. I wrote up a program that could check for chains like this:

program nr
   implicit none
   integer, parameter :: ik16 = selected_int_kind(38)
   integer, parameter :: N = 200
   integer(ik16) p(N), q(N)
   integer D
   integer sqD
   integer r, s, a
   integer i, j, k
   integer(ik16) e, b, c

   write(*,'(a)',advance='no') 'Enter the value of D:> '
   read(*,*) D
   sqD = sqrt(D+0.5d0)
   r = 0
   s = 1
   a = (sqD+r)/s
   p(1) = a
   q(1) = 1
   r = a*s-r
   s = (D-r**2)/s
   a = (sqD+r)/s
   p(2) = a*p(1)+1
   q(2) = a
   do i = 3, N
      r = a*s-r
      s = (D-r**2)/s
      a = (sqD+r)/s
      p(i) = a*p(i-1)+p(i-2)
      q(i) = a*q(i-1)+q(i-2)
      if(p(i) <= p(i-1) .OR. q(i) <= q(i-1)) exit
   end do
   write(*,'(*(g0))') 'There are ',i-1,' convergents computed'
   outer: do j = 1, 5!(i-1)/2
      write(*,'(*(g0))') 'Starting convergent: ', j
      e = p(j)
      b = q(j)
      k = j
      do
         c = e**2+D*b**2
         if(c <= e) exit
         b = 2*e*b
         e = c
         do k = k+1, i-1
            if(b == q(k)) then
               if(e == p(k)) then
                  write(*,'(*(g0))') 'Matching convergent: ', k
                  exit
               else
                  write(*,'(a)') 'Matched denominator but not numerator'
                  stop
               end if
            else if(b < q(k)) then
               write(*,'(*(g0))') 'Missed convergent: ', k-1
               cycle outer
            end if
         end do
      end do
   end do outer
end program nr

So it always seemed to hit chains for $D=2$, $D=5$, $D=10$, $D=26$, $D=37$, and $D=50$ but for other values of $D$ sometimes it hit and sometimes it missed. My program has indices $1$ bigger than in the original question, so I'm seeing $n\rightarrow2n$ rather than $n\rightarrow2n+1$. Even the infamous $D=61$, which has a pretty large nontrivial solution to Pell's equation, has a chain. When another convergent is hit, it always seems to be exactly $2n$, never $2n-2$ or $2n+2$. It can't be $2n-1$ or $2n+1$ because Newton-Raphson approaches roots from above.

To prove a chain once found, it's probably useful to compare to solutoins to Pell's equation. Probably writing out the solutions in exponential form would lead to proof for a given chain.

EDIT: Just after posting it occurred to me that $$\begin{align}(p^2+Dq^2)^2-D(2pq)^2 & =p^4+2Dp^2q^2+D^2q^4-4Dp^2q^2\\ & =p^4-2Dp^2q^2+D^2q^4\\ & =(p^2-Dq^2)^2\end{align}$$ So every solution to Pell's equation $p^2-Dq^2=1$ leads to an infinite chain of solutions via Newton-Raphson and if $|p^2-Dq^2|\ne1$, then this metric grows exponentially so that the roots computed by Newton-Raphson will not be convergents.

EDIT: Relevant link to Newton-Raphson and Pell's equation.

$\endgroup$
  • $\begingroup$ Thank you, this is almost research level. I've read about the connection between CFs and Pell's equation, and now I understand it better. $\endgroup$ – Yuriy S Apr 9 '16 at 9:36
  • $\begingroup$ Did you notice that the cases where you hit an infinite chain of convergents starting from any convergent are when $D=n^2+1$? In that case the continued fraction expansion is $\langle n,2n,2n,2n,\cdots\rangle$ so each convergent $\frac pq$ satisfies $p^2-Dq^2=\pm1$. $\endgroup$ – user5713492 Apr 9 '16 at 15:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.