Usando el método de Newton calcule$ \frac{1}{\sqrt{a}} $ sin división

Question

Sugerir algoritmo para el cálculo numérico$ \frac{1}{\sqrt{a}} \ a > 0 $ sin división, use el método de Newton.
Mi idea es:
$$ \frac{1}{\sqrt{a}} = (\sqrt{a})^{-1} = a^{-\frac{1}{2}}$ $$$ x = a^{-\frac{1}{2}} \Rightarrow f(x)=x^2 - a^{-1}$ $ Y el siguiente paso es calcular$ f'(x)=2x $, pero después de la sustitución obtuve:$$ x_{n+1} = \frac{x_n^2+a^{-1}}{2x_n}$ $ Y sé que todavía tengo divion, supongo. Tal vez es mejor idea en esta tarea?

Answer 1

Después de usar la magia oscura para hacer una estimación inicial $y_0$, la rápida inversa de la raíz cuadrada algoritm esencialmente se aproxima $y=1/\sqrt{x}$, $x > 0$, mediante el uso de la iteración

$$ y_{n+1} = \frac{3}{2}y_n - \frac{1}{2}xy_n^3. $$

No hay ninguna división de aquí, a menos de contar con la multiplicación por las constantes $3/2$$1/2$.

Si el límite de $n \to \infty$ existe es una solución de la ecuación cúbica

$$ y = \frac{3}{2}y - \frac{1}{2}xy^3. $$

Por supuesto, las únicas soluciones son $y=0$$y=\pm 1/\sqrt{x}$. Podemos hacer algunos análisis mediante las técnicas estándar para sistemas dinámicos discretos para determinar cuando la iteración será convergen y hasta qué punto.

Vamos

$$ f(y) = \frac{3}{2}y - \frac{1}{2}xy^3. $$

A continuación,$f'(0) = 3/2 > 1$, lo $y=0$ es un equilibrio inestable del sistema. También tenemos $f'(1/\sqrt{x}) = 0$, $<1$ en valor absoluto, de modo que los puntos de $y=\pm 1/\sqrt{x}$ son estables equilibrios.

En otras palabras, si $y_0$ es lo suficientemente cerca como para $\pm 1/\sqrt{x}$ $y_n$ convergerán a $\pm 1/\sqrt{x}$. Podemos determinar que tan cerca tenemos que estar calculando

$$ f'(y) = \frac{3}{2}\left(1-xy^2\right). $$

Requerimos $|f'(y)| < 1$ a fin de $f$ a una contracción, y esto es equivalente a

$$ -\frac{2}{3} < 1 - xy^2 < \frac{2}{3}. $$

Reordenando, obtenemos

$$ \frac{1}{3x} < y^2 < \frac{5}{3x}. $$

Por lo tanto, si

$$ \sqrt\frac{1}{3x} < y_0 < \sqrt\frac{5}{3x} $$

a continuación,$y_n \to 1/\sqrt{x}$$n \to \infty$, y si

$$ -\sqrt\frac{5}{3x} < y_0 < -\sqrt\frac{1}{3x} $$

a continuación,$y_n \to -1/\sqrt{x}$$n \to \infty$.

Como el tradicional método de Newton, este esquema iterativo también converge cuadráticamente. Si dejamos $y_n = 1/\sqrt{x} + \epsilon_n$, entonces el sistema se convierte en

$$ \epsilon_{n+1} = -\frac{3\sqrt{x}}{2} \epsilon_n^2 - \frac{x}{2} \epsilon_n^3. $$

Answer 2

Aplique el Método de Newton a$f(x) = x^{-2} - a$.