Algoritmo más rápido que el de Newton para calcular$\sqrt{2}$

Question

Es bien sabido que el esquema de iteración

PS

converge a$$ x_{n+1} = \frac{1}{2} (x_n + \frac{2}{x_n })$muy rápido. Más precisamente, converge cuadráticamente. El problema es, ¿hay algún algoritmo aún más rápido? Es decir, podemos encontrar otro polinomio$\sqrt{2}$de$P(x, 1/x)$y$x$ con coeficientes racionales , de manera tal que el esquema de iteración

PS

converge incluso más rápido?

La conjetura es que no existe tal algoritmo. Pero no tengo idea de cómo probarlo.

Answer 1

Aquí está uno que converge más rápido (menos pasos), al menos en un cierto rango:

$x_{n+1}=-{1\over32}x_n^3+{5\over8}x_n+{7\over8}{1\over x_n}$

Que tiene las propiedades deseadas de $P(\sqrt 2)=\sqrt 2$ y un mínimo local en a $x=\sqrt 2$:

Se puede observar que la curva (y por lo tanto la iteración a partir de $x < 3$, de todos modos) es más cercano a $\sqrt 2$ que el Newton de la curva.

La relación de los primeros siete recorre a $\sqrt 2$, a partir de $x=3$:

new&improved      Newton
2.121320343559642 2.121320343559642
0.935443345944703 1.296362432175337
1.001184535464119 1.033875824007604
1.000000349950901 1.000554985146933
1.000000000000031 1.000000153918834
1.000000000000000 1.000000000000012
1.000000000000000 1.000000000000000

Por supuesto, sólo se trata de un paso adelante, y no el costo adicional del cubo factor de