El método de Newton para las raíces cuadradas "salta" a través de los convergentes de las fracciones continuas

Question

Sé que el método de Newton duplica aproximadamente el número de dígitos correctos en cada paso, pero me he dado cuenta de que también duplica el número de términos de la fracción continua, al menos para las raíces cuadradas.

Explicación. Si empezamos las iteraciones de Newton con algún convergente parcial de la fracción continua simple para la raíz cuadrada, obtenemos otro convergente de la misma fracción continua en cada paso, con el doble de términos de CF.

Ejemplo. Encontrar la raíz cuadrada de $2$ .

1) Empezar con $\frac{3}{2}$ que también es la primera fracción continua convergente. Enumerando los valores en cada paso y el número de términos de la fracción continuada, obtenemos:

$$ \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} $$

Como puede ver, la cantidad de términos CF (la posición de esta fracción en la lista de todos los convergentes parciales) se duplica en cada paso.

2) Empezar con $\frac{7}{5}$ que es la segunda fracción continua convergente.

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

Lo mismo ocurre con otras raíces cuadradas que he comprobado.

¿Cómo es que el método de Newton "salta" a través de la fracción continua de esta manera, duplicando exactamente el número de términos de CF en cada paso?

¿Podemos demostrar esta observación utilizando las relaciones de recurrencia para la fracción continua?

---

Por si acaso, el método de Newton:

$$\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}$$

Y la recurrencia continua de la fracción:

$$\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}}$$

¿Cómo podemos relacionar estas dos cosas?

---

Una pregunta relacionada aquí . Pero no estoy preguntando por los dígitos, sino por los términos de las fracciones continuadas.

Answer 1

En primer lugar, es necesario experimentar un poco. Escribí un programa que podría comprobar las cadenas como esta:

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

Así que siempre parecía golpear las cadenas para $D=2$ , $D=5$ , $D=10$ , $D=26$ , $D=37$ y $D=50$ pero para otros valores de $D$ a veces se acierta y a veces se falla. Mi programa tiene índices $1$ más grande que en la pregunta original, así que estoy viendo $n\rightarrow2n$ en lugar de $n\rightarrow2n+1$ . Incluso el infame $D=61$ que tiene una solución no trivial bastante grande de la ecuación de Pell, tiene una cadena. Cuando se alcanza otro convergente, siempre parece ser exactamente $2n$ , nunca $2n-2$ o $2n+2$ . No puede ser $2n-1$ o $2n+1$ porque Newton-Raphson aborda las raíces desde arriba.

Para probar una cadena una vez encontrada, probablemente sea útil comparar con solutoins a la ecuación de Pell. Probablemente escribir las soluciones en forma exponencial llevaría a la prueba para una cadena dada.

EDITAR : Justo después de publicar se me ocurrió que $$\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}$$ Así que cada solución de la ecuación de Pell $p^2-Dq^2=1$ conduce a una cadena infinita de soluciones vía Newton-Raphson y si $|p^2-Dq^2|\ne1$ entonces esta métrica crece exponencialmente por lo que las raíces calculadas por Newton-Raphson no serán convergentes.

EDITAR : Relevante enlace a la ecuación de Newton-Raphson y Pell .