Newton's method for square roots 'jumps' through the continued fraction convergents

Question

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.

Answer 1

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.