Ir a través de la fórmula recursiva para aproximar las raíces cada vez es extraordinariamente aburrido, así que me preguntaba por qué no había fórmula que calcula la n-ésima iteración del método de Newton.
Respuestas
¿Demasiados anuncios?
En primer lugar, tenga en cuenta que esta fórmula violaría el "demasiado bueno para ser verdad" de la prueba: le permiten encontrar los mínimos de cualquier (lo suficientemente suaves, estrictamente) convexa de la función en un solo paso, no importa lo complicado!
Para la intuición, para considerar lo que el método de Newton está haciendo: está a partir de una estimación inicial, y tomar una secuencia de "descenso pasos" hasta llegar a la mínima, donde cada paso se utiliza la información local (una ecuación cuadrática local aproximación) acerca de su vecindario para calcular el siguiente destino. Imagina un excursionista subiendo por una montaña, el primero que las alzas en el punto más bajo ella puede ver, a continuación, reorienta a sí misma y va al punto más bajo que puede ver desde su nueva ubicación, etc.
La única manera de hacer un directo de línea recta hacia el punto más bajo ($n\to\infty$) es que, si el caminante sabe de alguna manera la totalidad de la forma del paisaje por adelantado. En términos matemáticos, esto significa que su fórmula tendría que utilice:
- información sobre el valor de la función en todos los puntos, o, equivalentemente, (por muy bien que se portaba funciones)
- los valores de todos los derivados de todos los pedidos a su punto de partida.
Y, por supuesto, ni es práctico en la práctica. Nota a pesar de que a veces te hacen tener esta información completa, por ejemplo, cuando su función es cuadrática, por lo que todas las derivadas de orden superior son cero. Y entonces usted puede fácilmente hacer una línea recta directamente a la solución.
También, usted puede escribir una fórmula para la $n$th iteración, pero como se ha dicho en las otras respuestas, esto no es muy útil: se pone sucio y desordenado el mayor $n$ obtiene (como debe ser, como se explicó anteriormente), no concurre a nada bueno como $n\to \infty$, y asciende a nada más que... se ejecuta el método de Newton para $n$ pasos consecutivos.
m0j0
Puntos
181
Usted no realmente mucho que ganar con una fórmula para la $n$th iteración.
La apelación de la de Newton-Raphson método es que un solo paso:
- es conceptualmente fácil de entender,
- es rápido para calcular, y
- se puede comprobar desde el paso a paso de la cercanía a un punto fijo.
Anidación $n$ de los cálculos en una única fórmula que funciona en contra de esas tres cosas.
Rodrigo de Azevedo
Puntos
608
Dado $y \in \mathbb R^+$, supongamos que queremos calcular la raíz cuadrada de $y$. El método de Newton produce la recurrencia de la relación $x_{k+1} = g (x_k)$ donde
$$g (x) := \frac 12 \left( x + \frac{y}{x}\right)$$
which Hero of Alexandria apparently knew of almost two millennia ago. Suppose that we want a formula for $x_3$ in terms of $s$ and an initial estimate $x_0$. Using SymPy, we define $s$, $x_0$ and $g$:
>>> y, x0 = symbols('y x0')
>>> g = lambdify(x, 0.5 * (x + (y / x)))
Iterating $3$ times:
>>> g(g(g(x0)))
0.5*y 0.25*y 0.125*y
0.125*x0 + --------------------------------- + -------------- + -------
0.5*y 0.25*y 0.5*y x0
0.25*x0 + -------------- + ------ 0.5*x0 + -----
0.5*y x0 x0
0.5*x0 + -----
x0
Simplifying:
>>> simplify(g(g(g(x0))))
/ 8 6 4 2 2 3 4\
1.0*\0.015625*x0 + 0.4375*x0 *y + 1.09375*x0 *y + 0.4375*x0 *y + 0.015625*y /
--------------------------------------------------------------------------------
/ 6 4 2 2 3\
x0*\0.125*x0 + 0.875*x0 *y + 0.875*x0 *y + 0.125*y /
Is working with the ratio of bivariate polynomials of degrees $8$ and $7$ really less tedious than using the recurrence relation $x_{k+1} = g (x_k)$ thrice?
Suppose now that we want a formula for $x_5$ in terms of $s$ and $x_0$. Iterating $5$ times:
>>> g(g(g(g(g(x0)))))
0.5*y 0.25*y 0.125*y 0.0625*y 0.03125*y
0.03125*x0 + --------------------------------------------------------------------------------------------------------------------------------------------------- + ----------------------------------------------------------------------- + --------------------------------- + -------------- + ---------
0.5*y 0.25*y 0.125*y 0.0625*y 0.5*y 0.25*y 0.125*y 0.5*y 0.25*y 0.5*y x0
0.0625*x0 + ----------------------------------------------------------------------- + --------------------------------- + -------------- + -------- 0.125*x0 + --------------------------------- + -------------- + ------- 0.25*x0 + -------------- + ------ 0.5*x0 + -----
0.5*y 0.25*y 0.125*y 0.5*y 0.25*y 0.5*y x0 0.5*y 0.25*y 0.5*y x0 0.5*y x0 x0
0.125*x0 + --------------------------------- + -------------- + ------- 0.25*x0 + -------------- + ------ 0.5*x0 + ----- 0.25*x0 + -------------- + ------ 0.5*x0 + ----- 0.5*x0 + -----
0.5*y 0.25*y 0.5*y x0 0.5*y x0 x0 0.5*y x0 x0 x0
0.25*x0 + -------------- + ------ 0.5*x0 + ----- 0.5*x0 + ----- 0.5*x0 + -----
0.5*y x0 x0 x0 x0
0.5*x0 + -----
x0
Simplifying:
>>> simplify(g(g(g(g(g(x0))))))
/ 32 30 28 2 26 3 24 4 22 5 20 6 18 7 16 8 14 9 12 10 10 11 8 12 6 13 4 14 2 15 16\
1.0*\9.31322574615479e-10*x0 + 4.61935997009277e-7*x0 *y + 3.34903597831726e-5*x0 *y + 0.00084395706653595*x0 *y + 0.00979593023657799*x0 *y + 0.0600817054510117*x0 *y + 0.210285969078541*x0 *y + 0.439058616757393*x0 *y + 0.559799736365676*x0 *y + 0.439058616757393*x0 *y + 0.210285969078541*x0 *y + 0.0600817054510117*x0 *y + 0.00979593023657799*x0 *y + 0.00084395706653595*x0 *y + 3.34903597831726e-5*x0 *y + 4.61935997009277e-7*x0 *y + 9.31322574615479e-10*y /
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
/ 30 28 26 2 24 3 22 4 20 5 18 6 16 7 14 8 12 9 10 10 8 11 6 12 4 13 2 14 15\
x0*\2.98023223876953e-8*x0 + 4.61935997009277e-6*x0 *y + 0.000187546014785767*x0 *y + 0.00313469767570496*x0 *y + 0.0261224806308746*x0 *y + 0.120163410902023*x0 *y + 0.323516875505447*x0 *y + 0.526870340108871*x0 *y + 0.526870340108871*x0 *y + 0.323516875505447*x0 *y + 0.120163410902023*x0 *y + 0.0261224806308746*x0 *y + 0.00313469767570496*x0 *y + 0.000187546014785767*x0 *y + 4.61935997009277e-6*x0 *y + 2.98023223876953e-8*y /
Is this formula useful? If we use floating-point arithmetic, almost certainly not.
However, we can use arbitrary-precision rational arithmetic instead:
from sympy import *
from fractions import Fraction
# declare symbols
x, y, x_0 = symbols('x y x_0')
# declare function g
g = lambdify(x, Fraction(1, 2) * (x + (y / x)))
# iterate
x_1 = g(x_0)
x_2 = g(x_1)
x_3 = g(x_2)
x_4 = g(x_3)
x_5 = g(x_4)
print latex(simplify(x_5))
which produces the following monstrous formula for $x_5$:
$$\color{blue}{\frac{x_{0}^{32} + 496 x_{0}^{30} y + 35960 x_{0}^{28} y^{2} + 906192 x_{0}^{26} y^{3} + 10518300 x_{0}^{24} y^{4} + 64512240 x_{0}^{22} y^{5} + 225792840 x_{0}^{20} y^{6} + 471435600 x_{0}^{18} y^{7} + 601080390 x_{0}^{16} y^{8} + 471435600 x_{0}^{14} y^{9} + 225792840 x_{0}^{12} y^{10} + 64512240 x_{0}^{10} y^{11} + 10518300 x_{0}^{8} y^{12} + 906192 x_{0}^{6} y^{13} + 35960 x_{0}^{4} y^{14} + 496 x_{0}^{2} y^{15} + y^{16}}{32 x_{0} \left(x_{0}^{30} + 155 x_{0}^{28} y + 6293 x_{0}^{26} y^{2} + 105183 x_{0}^{24} y^{3} + 876525 x_{0}^{22} y^{4} + 4032015 x_{0}^{20} y^{5} + 10855425 x_{0}^{18} y^{6} + 17678835 x_{0}^{16} y^{7} + 17678835 x_{0}^{14} y^{8} + 10855425 x_{0}^{12} y^{9} + 4032015 x_{0}^{10} y^{10} + 876525 x_{0}^{8} y^{11} + 105183 x_{0}^{6} y^{12} + 6293 x_{0}^{4} y^{13} + 155 x_{0}^{2} y^{14} + y^{15}\right)}}$$
Suppose that we want to compute $\sqrt{10}$ using the initial estimate $x_0 = 3$:
>>> (x_5.subs(y,10)).subs(x_0,3)
9347391150304592810234881/2955904621546382351702304
>>> 9347391150304592810234881.0/2955904621546382351702304.0
3.1622776601683795
>>> 3.1622776601683795**2
10.000000000000002
which is good enough. Hence,
$$\sqrt{10} \approx \frac{9347391150304592810234881}{2955904621546382351702304} \approx 3.16227766$$
Yves Daoust
Puntos
30126
Una tentativa de explicación:
Como el de Newton iteraciones convergen a la misma raíz, a partir de muchos de los valores iniciales, la función que asocia el valor inicial de la iteración es muy "plana".
Ella es una ilustración con la función de raíz cuadrada:
Como la expresión de la iteración es una fracción racional, el grado del numerador y el denominador deben aumentar para lograr este planitud. Yo no tengo ninguna explicación de por qué el número de términos aumenta, sin embargo.
Robert M Thomson
Puntos
71
El confinamiento de la tarea a la raíz cuadrada de X de la función, hay un acceso directo que puede tomar. En la mayoría de los equipo de la aritmética, de la división es igual en el trabajo a alrededor de tres multiplicaciones. Así que una vez que la raíz cuadrada de dos o tres cifras decimales, tome la mitad de su recíproco. Ajustar el número a K cercanos que es una forma rápida de multiplicar (en la mayoría de los dos internos, uno de bits o dos internos bits cero). A continuación, ajuste su conjetura G <= G-K(G^2-X). Esto ya no tiene convergencia cuadrática, pero cada paso requiere sólo un desagradable multiplicación y una simple multiplicación.
Trabajando con el modelo de TI 30 de analista de negocios (la calculadora de sólo permitido en el actuario de exámenes), yo podría implementar fácilmente. Yo guardé el 1/2f'(X) en uno de los varios recuerdos, y comenzó con un pequeño valor. Nada en el estadio de béisbol le dará la convergencia. Si usted consigue la divergencia, simplemente se invierte el signo. Si el resultado undershoots, aumentar la magnitud, si el resultado oscila por encima y por debajo de un cierto valor, disminuir la magnitud de la almacenan factor de corrección.
El método de Newton falla en algunos casos notables. Por ejemplo, Ln(X) = 1, que va de los frutos secos si su valor inicial es mayor que el correo. (Esto está relacionado con el diodo de la ecuación, que ahora resolver por otros medios sin itera ción).
