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

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?

• 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.
– Ian
Apr 8, 2016 at 15:57
• @Ian, I'm more intetested in why the skipping is so precise (aways doubles) Apr 8, 2016 at 15:57
• Oh, precisely doubles. That seems like a delicate matter; it wouldn't surprise me if it was specific to $\sqrt{2}$ even.
– Ian
Apr 8, 2016 at 15:58
• @Ian, also works for $\sqrt{5}$ at least. I'll check more later Apr 8, 2016 at 15:58
• Would work the same way for any square root, I believe. Apr 8, 2016 at 16:21

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:> '
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.

• 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. Apr 9, 2016 at 9:36
• 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$. Apr 9, 2016 at 15:11