Método numérico para encontrar la raíz cuadrada.

Question

He encontrado una foto de Evan O''Dorney del proyecto ganador, que lo ganó el primer lugar en el Intel Science talent search. Propuso un método numérico para encontrar la raíz cuadrada, que lo ganó $100,000 USD.

Estos son algunos enlaces de fotos de el cartel de mostrar el método.

• Link 1
• Enlace 2
• Link 3

¿Cómo funciona este método numérico de trabajo y qué es la prueba?

Su método hace uso de Moebius Transformación.

Answer 1

La iteración para encontrar $\sqrt k$ es $f(x) = \frac{d x+k}{x+d}$ donde $d = \lfloor \sqrt k \rfloor$. Las iteraciones de inicio con $x = d$.

Si $x$ es un punto fijo de este, $x = \frac{d x+k}{x+d}$, o $x(x+d) = dx + k$ o $x^2 = k$, por lo que cualquier punto fijo debe ser la raíz cuadrada.

Ahora wee ver si la iteración aumenta o disminuye. Si $y = \frac{d x+k}{x+d}$, $$y - x = \frac{d x+k}{x+d} - x = \frac{d x+k - x(x+d)}{x+d} = \frac{k - x^2}{x+d} $$ así que si $x^2 < k$, $y > x$ y si $x^2 > k$, $y < x$.

También, procediendo de análisis del método de Newton, $y^2-k = \frac {d x+k)^2}{(x+d)^2} - k = \frac{d^2 x^2 +2 d x k + k^2 - k(x+d)^2}{(x+d)^2} = \frac{d^2 x^2 +2 d x k + k^2 - k(x^2 + 2dx +d^2)}{(x+d)^2} = \frac{d^2 x^2 +2 d x k + k^2 - kx^2 - 2dkx -kd^2)}{(x+d)^2} = \frac{d^2 x^2 + k^2 - kx^2 -kd^2)}{(x+d)^2} = \frac{d^2 (x^2-k) + k^2 - kx^2)}{(x+d)^2} = \frac{d^2 (x^2-k) - k(x^2-k))}{(x+d)^2} = \frac {d^2-k) (x^2-k)}{(x+d)^2} = (x^2-k)\frac{d^2-k}{(x+d)^2} $.

Desde $d = \lfloor \sqrt k \rfloor$, $d < \sqrt k < d+1$ o $d^2 < k < d^2 + 2d +1$ o $-2d - 1 < d^2 - k < 0$, por lo $|d^2-k| < 2d+1$. El uso de esta, $|y^2-k| < |x^2-k|\frac{2d+1}{(x+d)^2}| = |x^2-k|\frac{2d+1}{x^2+2dx+d^2} $, por lo $|y^2-k|< |x^2-k|$, y en cada iteración se pone más cerca de la raíz cuadrada.

Desde el inicio recorrer es $d$, todos los siguientes recorre exceder $d$ así $|y^2-k| < |x^2-k|\frac{2d+1}{(d+d)^2}| < |x^2-k|\frac{2d+1}{4d^2}| < |x^2-k|\frac{1+1/(2d)}{2d}| \le 3|x^2-k|/4$ desde $d \ge 1$.

Esto demuestra que la iteración converge. Sin embargo, esto no muestra que converge cuadráticamente como las de Newton, sólo que converge linealmente.