Método de newton

ImprimirCitar

Algoritmo para encontrar ceros de funciones

En el análisis numérico, el método de Newton, también conocido como el método de Newton-Raphson, llamado así por Isaac Newton y Joseph Raphson, es un método de búsqueda de raíces algoritmo que produce aproximaciones cada vez mejores a las raíces (o ceros) de una función de valor real. La versión más básica comienza con una función de variable única $f$ definida para una variable real $x$ , la función derivada $f'$ , y una suposición inicial $x 0$ para una raíz de $f$ . Si la función satisface suposiciones suficientes y la conjetura inicial es cercana, entonces

{displaystyle x_{1}=x_{0}-{frac {f(x_{0})}{f'(x_{0})}}}

es una mejor aproximación de la raíz que $x 0$ . Geométricamente, $(x 1, 0)$ es la intersección de $x$ -eje y la tangente de la gráfica de $f$ en $(x 0, f (x 0))$ : es decir, la suposición mejorada es la única raíz de la aproximación lineal en el punto inicial. El proceso se repite como

{displaystyle x_{n+1}=x_{n}-{frac {f(x_{n})}{f'(x_{n})}}}

hasta alcanzar un valor suficientemente preciso. El número de dígitos correctos se duplica aproximadamente con cada paso. Este algoritmo es el primero en la clase de métodos de Householder, seguido por el método de Halley. El método también se puede extender a funciones complejas ya sistemas de ecuaciones.

Descripción

La idea es comenzar con una suposición inicial, luego aproximar la función por su línea tangente y finalmente calcular la $x-intersección de esta recta tangente. Este intercepto en x será una mejor aproximación a la raíz de la función original que la primera suposición, y el método puede ser iterado.$

x n + 1

es una mejor aproximación que

x n

para la raíz

x

de la función

f

(curva azul)

Si la recta tangente a la curva $f (x)$ en $x = x n$ intercepta el eje x en $x n +1$ entonces la pendiente es

{displaystyle f'(x_{n})={dfrac {f(x_{n})-0}{x_{n}-x_{n+1}}}}

Resolviendo para $x n + 1$ da

{displaystyle x_{n+1}=x_{n}-{frac {f(x_{n})}{f'(x_{n})}}.}

La iteración normalmente mejora la aproximación

Comenzamos el proceso con algún valor inicial arbitrario $x 0$ . (Cuanto más cerca del cero, mejor. Pero, en ausencia de cualquier intuición acerca de dónde podría estar el cero, un método de "adivinar y comprobar" podría reducir las posibilidades a un intervalo razonablemente pequeño apelando a la teorema del valor intermedio). El método generalmente convergerá, siempre que esta suposición inicial sea lo suficientemente cercana al cero desconocido, y que $f ' (x 0) \neq 0$ . Además, para un cero de multiplicidad 1, la convergencia es al menos cuadrática (consulte la tasa de convergencia) en una vecindad del cero, lo que intuitivamente significa que la cantidad de dígitos correctos se duplica aproximadamente en cada paso. Se pueden encontrar más detalles en la sección de análisis a continuación.

Los métodos de Householder son similares pero tienen un orden más alto para una convergencia aún más rápida. Sin embargo, los cálculos adicionales necesarios para cada paso pueden ralentizar el rendimiento general en relación con el método de Newton, especialmente si $f$ o sus derivados son computacionalmente caros de evaluar.

Historia

El nombre "método de Newton" se deriva de la descripción de Isaac Newton de un caso especial del método en De analysi per aequationes numero terminorum infinitas (escrito en 1669, publicado en 1711 por William Jones) y en De metodis fluxionum et serierum infinitarum (escrito en 1671, traducido y publicado como Method of Fluxions en 1736 por John Colson). Sin embargo, su método difiere sustancialmente del método moderno dado anteriormente. Newton aplicó el método solo a polinomios, comenzando con una raíz estimada inicial y extrayendo una secuencia de correcciones de errores. Usó cada corrección para reescribir el polinomio en términos del error restante, y luego resolvió una nueva corrección despreciando los términos de mayor grado. No conectó explícitamente el método con derivadas ni presentó una fórmula general. Newton aplicó este método tanto a problemas numéricos como algebraicos, produciendo series de Taylor en el último caso.

Es posible que Newton haya derivado su método de un método similar pero menos preciso de Vieta. La esencia del método de Vieta se puede encontrar en el trabajo del matemático persa Sharaf al-Din al-Tusi, mientras que su sucesor Jamshīd al-Kāshī usó una forma del método de Newton para resolver $x P - N = 0$ para encontrar raíces de $N$ (Ypma 1995). Un caso especial del método de Newton para calcular raíces cuadradas se conoce desde la antigüedad y a menudo se le llama método babilónico.

El método de Newton fue utilizado por el matemático japonés del siglo XVII Seki Kōwa para resolver ecuaciones de una sola variable, aunque faltaba la conexión con el cálculo.

El método de Newton se publicó por primera vez en 1685 en Un tratado de álgebra histórica y práctica de John Wallis. En 1690, Joseph Raphson publicó una descripción simplificada en Analysis aequationum universalis. Raphson también aplicó el método solo a polinomios, pero evitó el tedioso proceso de reescritura de Newton extrayendo cada corrección sucesiva del polinomio original. Esto le permitió derivar una expresión iterativa reutilizable para cada problema. Finalmente, en 1740, Thomas Simpson describió el método de Newton como un método iterativo para resolver ecuaciones generales no lineales usando cálculo, esencialmente dando la descripción anterior. En la misma publicación, Simpson también da la generalización a los sistemas de dos ecuaciones y señala que el método de Newton se puede usar para resolver problemas de optimización al establecer el gradiente en cero.

Arthur Cayley en 1879 en El problema imaginario de Newton-Fourier fue el primero en notar las dificultades para generalizar el método de Newton a raíces complejas de polinomios con grado mayor que 2 y valores iniciales complejos. Esto abrió el camino al estudio de la teoría de iteraciones de funciones racionales.

Consideraciones prácticas

El método de Newton es una técnica poderosa; en general, la convergencia es cuadrática: a medida que el método converge en la raíz, la diferencia entre la raíz y la aproximación se eleva al cuadrado (el número de dígitos precisos se duplica aproximadamente) en cada paso. Sin embargo, hay algunas dificultades con el método.

Dificultad para calcular la derivada de una función

El método de Newton requiere que la derivada se pueda calcular directamente. Una expresión analítica para el derivado puede no ser fácil de obtener o podría ser costosa de evaluar. En estas situaciones, puede ser apropiado aproximar la derivada usando la pendiente de una línea que pasa por dos puntos cercanos en la función. Usar esta aproximación daría como resultado algo así como el método de la secante cuya convergencia es más lenta que la del método de Newton.

Error del método para converger a la raíz

Es importante revisar la prueba de convergencia cuadrática del método de Newton antes de implementarlo. Específicamente, uno debe revisar las suposiciones hechas en la prueba. Para situaciones en las que el método no converge, es porque no se cumplen las suposiciones hechas en esta prueba.

Exceso

Si la primera derivada no se comporta bien en la vecindad de una raíz en particular, el método puede sobrepasar y divergir de esa raíz. Un ejemplo de una función con una raíz, para la cual la derivada no se comporta bien en la vecindad de la raíz, es

<math alttext="{displaystyle f(x)=|x|^{a},quad 0<af()x)=SilencioxSilencioa,0.a.12{displaystyle f(x)=fortx sometida^{a},quad 0 obtenidosa{tfrac {1}{2}}}<img alt="f(x)=|x|^{a},quad 0<a

para lo cual la raíz se sobrepasará y la secuencia de $x$ divergirá. Para $a = 1 / 2$ , la raíz aún se sobrepasará, pero la secuencia oscilará entre dos valores. Para $1 / 2 < a < 1$ , la raíz aún se sobrepasará pero la secuencia convergerá, y para $a \geq 1$ la raíz no se sobrepasará en absoluto.

En algunos casos, el método de Newton se puede estabilizar utilizando una relajación excesiva sucesiva, o se puede aumentar la velocidad de convergencia utilizando el mismo método.

Punto estacionario

Si se encuentra un punto estacionario de la función, la derivada es cero y el método terminará debido a la división por cero.

Estimación inicial deficiente

Un gran error en la estimación inicial puede contribuir a la falta de convergencia del algoritmo. Para superar este problema, a menudo se puede linealizar la función que se está optimizando usando cálculo, logaritmos, diferenciales o incluso usando algoritmos evolutivos, como el túnel estocástico. Las buenas estimaciones iniciales se encuentran cerca de la estimación final del parámetro globalmente óptimo. En la regresión no lineal, la suma de errores cuadráticos (SSE) es solo "cerca de" parabólica en la región de las estimaciones finales de los parámetros. Las estimaciones iniciales encontradas aquí permitirán que el método de Newton-Raphson converja rápidamente. Solo aquí la matriz hessiana del SSE es positiva y la primera derivada del SSE es cercana a cero.

Mitigación de la falta de convergencia

En una implementación sólida del método de Newton, es común establecer límites en el número de iteraciones, vincular la solución a un intervalo que se sabe que contiene la raíz y combinar el método con un método de búsqueda de raíces más sólido..

Convergencia lenta para raíces de multiplicidad mayor que 1

Si la raíz que se busca tiene una multiplicidad mayor que uno, la tasa de convergencia es simplemente lineal (los errores se reducen por un factor constante en cada paso) a menos que se tomen medidas especiales. Cuando hay dos o más raíces que están muy juntas, pueden pasar muchas iteraciones antes de que las iteraciones se acerquen lo suficiente a una de ellas para que la convergencia cuadrática sea evidente. Sin embargo, si se conoce la multiplicidad $m$ de la raíz, el siguiente algoritmo modificado conserva la tasa de convergencia cuadrática:

{displaystyle x_{n+1}=x_{n}-m{frac {f(x_{n})}{f'(x_{n})}}.}

Esto es equivalente a usar una relajación excesiva sucesiva. Por otro lado, si no se conoce la multiplicidad $m$ de la raíz, es posible estimar $m$ después de realizar una o dos iteraciones, y luego use ese valor para aumentar la tasa de convergencia.

Si la multiplicidad $m$ de la raíz es finita entonces $g (x) = f (x) / f' (x)$ tendrá una raíz en la misma ubicación con multiplicidad 1. Aplicar el método de Newton para encontrar la raíz de $g (x)$ recupera convergencia cuadrática en muchos casos aunque generalmente implica la segunda derivada de $f (x)$ . En un caso particularmente simple, si $f (x) = x m$ luego $g (x) = x //span> m y el método de Newton encuentra la raíz en una sola iteración con$

{displaystyle x_{n+1}=x_{n}-{frac {g(x_{n})}{g'(x_{n})}}=x_{n}-{frac {;{frac {x_{n}}{m}};}{frac {1}{m}}}=0,.}

Análisis

Suponga que la función $f$ tiene un cero en $α$ , es decir, $f (α) = 0$ , y $f$ es diferenciable en una vecindad de $α$ .

Si $f$ es continuamente diferenciable y su derivada es distinta de cero en $α$ , entonces existe una vecindad de $α$ tal que para todos los valores iniciales $x 0$ en ese vecindario, la secuencia $(x n)$ convergerá a $α$ .

Si la función es diferenciable continuamente y su derivada no es 0 en $α$ y tiene una segunda derivada en $α$ entonces la convergencia es cuadrática o más rápida. Si la segunda derivada no es 0 en $α$ entonces la convergencia es meramente cuadrática. Si la tercera derivada existe y está acotada en una vecindad de $α$ , entonces:

{displaystyle Delta x_{i+1}={frac {f''(alpha)}{2f'(alpha)}}left(Delta x_{i}right)^{2}+Oleft(Delta x_{i}right)^{3},,}

dónde

Delta x_{i}triangleq x_{i}-alpha ,.

Si la derivada es 0 en $α$ , entonces la convergencia suele ser solo lineal. Específicamente, si $f$ es dos veces diferenciable continuamente, $f' (α) = 0$ y $f ″ (α) \neq 0$ , entonces existe una vecindad de $α$ tal que, para todos los valores iniciales $x 0$ en esa vecindad, la secuencia de iteraciones converge linealmente, con tasa 1/ 2. Alternativamente, si $f' (α) = 0$ y $f' (x) \neq 0$ para $x \neq α$ , $x$ en una vecindad $U$ de $α$ , $α$ siendo un cero de multiplicidad $r$ , y si $f \in C r (U)$ , entonces existe una vecindad de $α$ tales que, para todos los valores iniciales $x 0$ en ese vecindario, la secuencia de iteraciones se convierte ges linealmente.

Sin embargo, ni siquiera la convergencia lineal está garantizada en situaciones patológicas.

En la práctica, estos resultados son locales y la vecindad de convergencia no se conoce de antemano. Pero también hay algunos resultados sobre la convergencia global: por ejemplo, dada una vecindad derecha $U +$ de $α$ , si $f$ es dos veces diferenciable en $U +$ y si $f' \neq 0$ , $f \cdot f ″ > 0$ en $U +$ , luego, para cada $x 0$ en $U +$ la secuencia $x k$ disminuye monótonamente a $α$ .

Prueba de convergencia cuadrática para el método iterativo de Newton

Según el teorema de Taylor, cualquier función $f (x)$ que tiene una segunda derivada continua puede representarse mediante una expansión sobre un punto que está cerca de una raíz de $f (x)$ . Supongamos que esta raíz es $α$ . Luego, la expansión de $f (α)$ sobre $x n$ es:

{displaystyle f(alpha)=f(x_{n})+f'(x_{n})(alpha -x_{n})+R_{1},}

()1)

donde la forma de Lagrange del resto del desarrollo de la serie de Taylor es

{displaystyle R_{1}={frac {1}{2!}}f''(xi _{n})left(alpha -x_{n}right)^{2},,}

donde $ξ n$ está entre $x n$ y $α.$

Dado que $α$ es la raíz, (1) se convierte en:

{displaystyle 0=f(alpha)=f(x_{n})+f'(x_{n})(alpha -x_{n})+{tfrac {1}{2}}f''(xi _{n})left(alpha -x_{n}right)^{2},}

()2)

Dividir la ecuación (2) por $f' (x n)$ y la reorganización da

{displaystyle {frac {f(x_{n})}{f'(x_{n})}}+left(alpha -x_{n}right)={frac {-f''(xi _{n})}{2f'(x_{n})}}left(alpha -x_{n}right)^{2}}

()3)

Recordando que $x n + 1$ está definido por

{displaystyle x_{n+1}=x_{n}-{frac {f(x_{n})}{f'(x_{n})}},,}

()4)

uno encuentra que

{displaystyle underbrace {alpha -x_{n+1}} _{varepsilon _{n+1}}={frac {-f''(xi _{n})}{2f'(x_{n})}}{(,underbrace {alpha -x_{n}} _{varepsilon _{n}},)}^{2},.}

Es decir,

{displaystyle varepsilon _{n+1}={frac {-f''(xi _{n})}{2f'(x_{n})}}cdot varepsilon _{n}^{2},.}

()5)

Tomando el valor absoluto de ambos lados da

{displaystyle left|{varepsilon _{n+1}}right|={frac {left|f''(xi _{n})right|}{2left|f'(x_{n})right|}}cdot varepsilon _{n}^{2},.}

()6)

La ecuación (6) muestra que el orden de convergencia es al menos cuadrático si se cumplen las siguientes condiciones:

$f . () x)$ ; para todos $x ▪ I$ , donde $I$ es el intervalo $[α - ε 0 Silencio, α + confidencialidad ε 0 Silencio$ ;
$f . () x)$ es continuo, para todos $x ▪ I$ ;
$M Silencio ε 0 TENIDA 1$

donde M viene dado por

{displaystyle M={frac {1}{2}}left(sup _{xin I}vert f''(x)vert right)left(sup _{xin I}{frac {1}{vert f'(x)vert }}right).,}

Si se cumplen estas condiciones,

{displaystyle vert varepsilon _{n+1}vert leq Mcdot varepsilon _{n}^{2},.}

Cuencas de atracción

Los subconjuntos disjuntos de las cuencas de atracción (las regiones de la recta numérica real tales que dentro de cada región la iteración desde cualquier punto conduce a una raíz particular) pueden ser infinitos en número y arbitrariamente pequeños. Por ejemplo, para la función $f (x) = x 3 - 2 x 2 - 11 x + 12 = (x - 4)(x - 1)(x + 3)$ , las siguientes condiciones iniciales están en sucesivas cuencas de atracción:

2.35287527	convergencias a	4;
2.35284172	convergencias a	−3;
2.35283735	convergencias a	4;
2.352836327	convergencias a	−3;
2.352836323	convergencias a	1.

Análisis de fallas

Solo se garantiza que el método de Newton convergerá si se cumplen ciertas condiciones. Si se cumplen las suposiciones hechas en la prueba de convergencia cuadrática, el método convergerá. Para las siguientes subsecciones, la falta de convergencia del método indica que no se cumplieron las suposiciones hechas en la prueba.

Malos puntos de partida

En algunos casos se cumplen las condiciones sobre la función que son necesarias para la convergencia, pero el punto elegido como punto inicial no está en el intervalo donde converge el método. Esto puede suceder, por ejemplo, si la función cuya raíz se busca tiende a cero asintóticamente cuando $x$ va a $\infty$ o $-\infty$ . En tales casos, se debe usar un método diferente, como la bisección, para obtener una mejor estimación del cero para usar como punto inicial.

El punto de iteración es estacionario

Considere la función:

{displaystyle f(x)=1-x^{2}.}

Tiene un máximo en $x = 0$ y soluciones de $f (x) = 0$ en $x = \pm1$ . Si comenzamos a iterar desde el punto estacionario $x 0 = 0$ (donde la derivada es cero), $x 1$ no estará definido, ya que la tangente en $(0, 1)$ es paralelo al eje $x$ :

x_{1}=x_{0}-{frac {f(x_{0})}{f'(x_{0})}}=0-{frac {1}{0}}.

El mismo problema ocurre si, en lugar del punto de inicio, cualquier punto de iteración es estacionario. Incluso si la derivada es pequeña pero no cero, la siguiente iteración será una aproximación mucho peor.

El punto de partida entra en un ciclo

Las líneas tangentes

x 3 - 2 x + 2

a 0 y 1 intersección el

x

-eje a 1 y 0 respectivamente, ilustrando por qué el método de Newton oscila entre estos valores para algunos puntos de partida.

Para algunas funciones, algunos puntos de partida pueden entrar en un ciclo infinito, impidiendo la convergencia. Dejar

f(x)=x^{3}-2x+2!

y toma 0 como punto de partida. La primera iteración produce 1 y la segunda iteración vuelve a 0, por lo que la secuencia alternará entre las dos sin converger a una raíz. De hecho, este 2-ciclo es estable: hay vecindarios alrededor de 0 y alrededor de 1 desde los cuales todos los puntos iteran asintóticamente al 2-ciclo (y por lo tanto no a la raíz de la función). En general, el comportamiento de la secuencia puede ser muy complejo (ver fractal de Newton). La solución real de esta ecuación es −1.76929235….

Problemas de derivados

Si la función no es continuamente diferenciable en una vecindad de la raíz, entonces es posible que el método de Newton siempre diverja y falle, a menos que se adivine la solución en el primer intento.

La derivada no existe en la raíz

Un ejemplo simple de una función donde el método de Newton diverge es intentar encontrar la raíz cúbica de cero. La raíz cúbica es continua e infinitamente diferenciable, excepto $x = 0$ , donde su derivada no está definida:

f(x)={sqrt[{3}]{x}}.

Para cualquier punto de iteración $x n$ , el próximo punto de iteración será:

{displaystyle x_{n+1}=x_{n}-{frac {f(x_{n})}{f'(x_{n})}}=x_{n}-{frac {{x_{n}}^{frac {1}{3}}}{{frac {1}{3}}{x_{n}}^{-{frac {2}{3}}}}}=x_{n}-3x_{n}=-2x_{n}.}

El algoritmo sobrepasa la solución y aterriza al otro lado del eje $y$ , más lejos de lo que estaba inicialmente; aplicar el método de Newton en realidad duplica las distancias desde la solución en cada iteración.

De hecho, las iteraciones divergen hasta el infinito para cada $f (x) = | x | α$ , donde $0 < a < 1 / 2$ . En el caso límite de $α = 1 / 2$ (raíz cuadrada), las iteraciones alternarán indefinidamente entre puntos $x 0$ y $- x 0$ , por lo que tampoco convergen en este caso.

Derivada discontinua

(feminine)

Si la derivada no es continua en la raíz, es posible que la convergencia no se produzca en ninguna vecindad de la raíz. Considere la función

{displaystyle f(x)={begin{cases}0&{text{if }}x=0,\x+x^{2}sin {frac {2}{x}}&{text{if }}xneq 0.end{cases}}}

Su derivada es:

{displaystyle f'(x)={begin{cases}1&{text{if }}x=0,\1+2xsin {frac {2}{x}}-2cos {frac {2}{x}}&{text{if }}xneq 0.end{cases}}}

Dentro de cualquier vecindad de la raíz, esta derivada sigue cambiando de signo a medida que $x$ se aproxima a 0 desde la derecha (o desde la izquierda) mientras que $f (x) \geq x - x 2 > 0$ para $0 < x < 1$ .

Entonces $f (x) / f' (x)$ no tiene límites cerca de la raíz, y el método de Newton divergirá en casi todas partes en cualquier entorno, aunque:

la función es diferente (y así continua) en todas partes;
el derivado en la raíz no es cero;
$f$ es infinitamente diferente excepto en la raíz; y
el derivado está atado en un barrio de la raíz (a diferencia de $f () x) / f . () x)$ ).

Convergencia no cuadrática

En algunos casos, las iteraciones convergen pero no convergen tan rápido como se prometió. En estos casos, los métodos más simples convergen tan rápido como el método de Newton.

Derivada cero

Si la primera derivada es cero en la raíz, la convergencia no será cuadrática. Dejar

f(x)=x^{2}!

entonces $f' (x) = 2 x$ y en consecuencia

{displaystyle x-{frac {f(x)}{f'(x)}}={frac {x}{2}}.}

Entonces, la convergencia no es cuadrática, aunque la función es infinitamente diferenciable en todas partes.

Ocurren problemas similares incluso cuando la raíz es solo "casi" doble. Por ejemplo, deja

{displaystyle f(x)=x^{2}(x-1000)+1.}

Luego, las primeras iteraciones que comienzan en $x 0 = 1$ son

x 0

= 1

x 1

= 0,50250376...

x 2

= 0.251062828...

x 3

= 0.127507934...

x 4

= 0,067671976...

x 5

= 0,041224176...

x 6

= 0,032741218...

x 7

= 0,031642362...

Se necesitan seis iteraciones para llegar a un punto en el que la convergencia parece ser cuadrática.

Sin segunda derivada

Si no hay una segunda derivada en la raíz, es posible que la convergencia no sea cuadrática. Dejar

{displaystyle f(x)=x+x^{frac {4}{3}}.}

Entonces

{displaystyle f'(x)=1+{tfrac {4}{3}}x^{frac {1}{3}}.}

{displaystyle f''(x)={tfrac {4}{9}}x^{-{frac {2}{3}}}}

excepto cuando $x = 0$ donde no está definido. Dado $x n$ ,

{displaystyle x_{n+1}=x_{n}-{frac {f(x_{n})}{f'(x_{n})}}={frac {{frac {1}{3}}{x_{n}}^{frac {4}{3}}}{1+{tfrac {4}{3}}{x_{n}}^{frac {1}{3}}}}}

que tiene aproximadamente 4/3 veces más bits de precisión que $x n$ posee. Esto es menos que las 2 veces que se requerirían para la convergencia cuadrática. Entonces, la convergencia del método de Newton (en este caso) no es cuadrática, aunque: la función es continuamente diferenciable en todas partes; la derivada no es cero en la raíz; y $f$ es infinitamente diferenciable excepto en la raíz deseada.

Generalizaciones

Funciones complejas

Cuencas de atracción para

x 5 - 1 = 0

; más oscuro significa más iteraciones para converger.

Cuando se trata de funciones complejas, el método de Newton se puede aplicar directamente para encontrar sus ceros. Cada cero tiene una cuenca de atracción en el plano complejo, el conjunto de todos los valores iniciales que hacen que el método converja a ese cero en particular. Estos conjuntos se pueden mapear como en la imagen que se muestra. Para muchas funciones complejas, los límites de las cuencas de atracción son fractales.

En algunos casos, hay regiones en el plano complejo que no se encuentran en ninguna de estas cuencas de atracción, lo que significa que las iteraciones no convergen. Por ejemplo, si se usa una condición inicial real para buscar una raíz de $x 2 + 1$ , todas las iteraciones posteriores ser números reales, por lo que las iteraciones no pueden converger a ninguna raíz, ya que ambas raíces no son reales. En este caso, casi todas las condiciones iniciales reales conducen a un comportamiento caótico, mientras que algunas condiciones iniciales iteran hasta el infinito o repiten ciclos de cualquier longitud finita.

Curt McMullen ha demostrado que para cualquier posible algoritmo puramente iterativo similar al método de Newton, el algoritmo diverge en algunas regiones abiertas del plano complejo cuando se aplica a algún polinomio de grado 4 o superior. Sin embargo, McMullen dio un algoritmo generalmente convergente para polinomios de grado 3.

Método de tercer orden de Chebyshev

Iteración Nash-Moser

Sistemas de ecuaciones

K variables, k funciones

También se puede utilizar el método de Newton para resolver sistemas de $k$ ecuaciones, que equivale a encontrar los ceros (simultaneos) de $k$ funciones continuamente diferenciables ${displaystyle f:mathbb {R} ^{k}to mathbb {R}.}$ Esto equivale a encontrar los ceros de una sola función de valor vectorial ${displaystyle F:mathbb {R} ^{k}to mathbb {R} ^{k}.}$ En la formulación anterior, los escalares $x n$ son reemplazados por vectores $x n$ y en lugar de dividir la función $f () x n)$ por su derivados $f . () x n)$ uno tiene que dejar multiplicar la función $F () x n)$ por el inverso de su $k \times k$ Matriz Jacobiana $J F () x n)$ . Esto resulta en la expresión

{displaystyle mathbf {x} _{n+1}=mathbf {x} _{n}-J_{F}(mathbf {x} _{n})^{-1}F(mathbf {x} _{n})}

En lugar de calcular la inversa de la matriz jacobiana, se puede ahorrar tiempo y aumentar la estabilidad numérica resolviendo el sistema de ecuaciones lineales

{displaystyle J_{F}(mathbf {x} _{n})(mathbf {x} _{n+1}-mathbf {x} _{n})=-F(mathbf {x} _{n})}

para la incógnita $x n + 1 - x n$ .

K variables, m ecuaciones, con m > k

La variante $k$ -dimensional del método de Newton se puede usar para resolver sistemas de más de $k$ ecuaciones (no lineales) también si el algoritmo usa el inverso generalizado de la matriz jacobiana no cuadrada $J + = (J T J) -1 J T$ en lugar de la inversa de $J$ . Si el sistema no lineal no tiene solución, el método intenta encontrar una solución en el sentido de mínimos cuadrados no lineales. Consulte Algoritmo de Gauss-Newton para obtener más información.

En un espacio de Banach

Otra generalización es el método de Newton para encontrar una raíz de una $F$ funcional definida en un espacio de Banach. En este caso la formulación es

{displaystyle X_{n+1}=X_{n}-{bigl (}F'(X_{n}){bigr)}^{-1}F(X_{n}),,}

donde $F' (X n)$ es la derivada de Fréchet calculada en X_n. Uno necesita que la derivada de Fréchet sea limitadamente invertible en cada $X n$ para que el método sea aplicable. El teorema de Newton-Kantorovich proporciona una condición para la existencia y la convergencia a una raíz.

Sobre números p-ádicos

En el análisis $p$ -ádico, el método estándar para mostrar una ecuación polinomial en una variable tiene un $p$ -ádica es el lema de Hensel, que utiliza la recursividad del método de Newton en la $p$ -números ádicos. Debido al comportamiento más estable de la suma y la multiplicación en los números $p$ -ádicos en comparación con los números reales (específicamente, la bola unitaria en el $p$ -adics es un anillo), la convergencia en el lema de Hensel se puede garantizar bajo hipótesis mucho más simples que en el método clásico de Newton en la línea real.

Método de Newton-Fourier

El método de Newton-Fourier es la extensión de Joseph Fourier del método de Newton para proporcionar límites en el error absoluto de la aproximación de la raíz, al mismo tiempo que proporciona convergencia cuadrática.

Suponga que $f (x)$ es dos veces continuamente diferenciable en $[a, b]$ y que $f$ contiene una raíz en este intervalo. Suponga que $f' (x), f ″ (x) \neq 0$ en este intervalo (este es el caso, por ejemplo, si $f (a) < 0$ , $f (b) > 0$ y $f' (x) > 0$ y $f ″ (x) > 0$ en este intervalo). Esto garantiza que hay una raíz única en este intervalo, llámela $α$ . Si es cóncavo hacia abajo en lugar de cóncavo hacia arriba, reemplace $f (x)$ por $- f (x)$ ya que tienen las mismas raíces.

Sea $x 0 = b$ el extremo derecho del intervalo y sea $z 0 = a$ sea el extremo izquierdo del intervalo. Dado $x n$ , define

{displaystyle x_{n+1}=x_{n}-{frac {f(x_{n})}{f'(x_{n})}},}

que es solo el método de Newton como antes. Luego define

{displaystyle z_{n+1}=z_{n}-{frac {f(z_{n})}{f'(x_{n})}},}

donde el denominador es $f' (x n)$ y no $f' (z n)$ . Las iteraciones $x n$ disminuirán estrictamente hasta la raíz mientras que las iteraciones $z n$ aumentará estrictamente hasta la raíz. También,

lim _{nto infty }{frac {x_{n+1}-z_{n+1}}{(x_{n}-z_{n})^{2}}}={frac {f''(alpha)}{2f'(alpha)}}

para que la distancia entre $x n$ y $z n$ disminuye cuadráticamente.

Métodos cuasi-Newton

Cuando el jacobiano no está disponible o es demasiado costoso de calcular en cada iteración, se puede usar un método cuasi-Newton.

Q-analógico

El método de Newton se puede generalizar con el análogo q de la derivada habitual.

Métodos de Newton modificado

Procedimiento de Maehly

Una ecuación no lineal tiene múltiples soluciones en general. Pero si el valor inicial no es apropiado, el método de Newton no puede converger a la solución deseada o puede converger a la misma solución que se encontró anteriormente. Cuando ya hemos encontrado N soluciones de $f(x)=0$ , entonces la siguiente raíz se puede encontrar aplicando el método de Newton a la siguiente ecuación:

{displaystyle F(x)={frac {f(x)}{prod _{i=1}^{N}(x-x_{i})}}=0.}

Este método se aplica para obtener ceros de la función de Bessel de segunda especie.

Método de Newton modificado de Hirano

El método de Newton modificado de Hirano es una modificación que conserva la convergencia del método de Newton y evita la inestabilidad. Está desarrollado para resolver polinomios complejos.

Método de intervalo de Newton

Combinar el método de Newton con la aritmética de intervalos es muy útil en algunos contextos. Esto proporciona un criterio de parada más fiable que los habituales (que son un pequeño valor de la función o una pequeña variación de la variable entre iteraciones consecutivas). Además, esto puede detectar casos en los que el método de Newton converge teóricamente pero diverge numéricamente debido a una precisión de punto flotante insuficiente (este suele ser el caso de polinomios de gran grado, donde un cambio muy pequeño de la variable puede cambiar drásticamente la valor de la función; véase el polinomio de Wilkinson).

Considere $f \to C 1 (X)$ , donde $X$ es un intervalo real, y supongamos que tenemos una extensión de intervalo $F'$ de $f'$ , lo que significa que $F '$ toma como entrada un intervalo $Y \subseteq X$ y genera un intervalo <span class="texhtml" F′(Y) tal que:

{displaystyle {begin{aligned}F'([y,y])&={f'(y)}\[5pt]F'(Y)&supseteq {f'(y)mid yin Y}.end{aligned}}}

También asumimos que $0 \notin F' (X)$ , por lo que en particular $f$ tiene como máximo una raíz en $X$ . Luego definimos el operador de intervalo de Newton por:

{displaystyle N(Y)=m-{frac {f(m)}{F'(Y)}}=left{left.m-{frac {f(m)}{z}}~right|~zin F'(Y)right}}

donde $m \in Y$ . Tenga en cuenta que la hipótesis sobre $F'$ implica que $N (Y)$ está bien definido y es un intervalo (consulte la aritmética de intervalos para obtener más detalles sobre las operaciones de intervalo). Esto naturalmente conduce a la siguiente secuencia:

{displaystyle {begin{aligned}X_{0}&=X\X_{k+1}&=N(X_{k})cap X_{k}.end{aligned}}}

El teorema del valor medio asegura que si hay una raíz de $f$ en $X k$ , entonces también está en $X k + 1$ . Además, la hipótesis sobre $F'$ asegura que $X k + 1$ es como máximo la mitad del tamaño de $X k$ cuando $m$ es el punto medio de $Y$ , por lo que esta secuencia converge hacia $[x*, x*]$ , donde $x*$ es la raíz de $f$ en $X$ .

Si $F' (X)$ contiene estrictamente 0, el uso de la división de intervalo extendido produce una unión de dos intervalos para $N (X)$ ; por lo tanto, múltiples raíces se separan y delimitan automáticamente.

Aplicaciones

Problemas de minimización y maximización

El método de Newton se puede usar para encontrar un mínimo o un máximo de una función $f (x)$ . La derivada es cero en un mínimo o un máximo, por lo que los mínimos y máximos locales se pueden encontrar aplicando el método de Newton a la derivada. La iteración se convierte en:

{displaystyle x_{n+1}=x_{n}-{frac {f'(x_{n})}{f''(x_{n})}}.}

Inversos multiplicativos de números y series de potencias

Una aplicación importante es la división de Newton-Raphson, que se puede usar para encontrar rápidamente el recíproco de un número $a$ , usando solo multiplicaciones y restas, es decir el número $x$ tal que $1 / x = a$ . Podemos reformularlo como encontrar el cero de $f (x) = 1 / x - a$ . Tenemos $f' (x) = - 1 / x 2$ .

La iteración de Newton es

{displaystyle x_{n+1}=x_{n}-{frac {f(x_{n})}{f'(x_{n})}}=x_{n}+{frac {{frac {1}{x_{n}}}-a}{frac {1}{x_{n}^{2}}}}=x_{n}(2-ax_{n}).}

Por lo tanto, la iteración de Newton solo necesita dos multiplicaciones y una resta.

Este método también es muy eficiente para calcular el inverso multiplicativo de una serie de potencias.

Resolver ecuaciones trascendentales

Muchas ecuaciones trascendentales se pueden resolver usando el método de Newton. Dada la ecuación

{displaystyle g(x)=h(x),}

con $g (x)$ y/o $h (x)$ una función trascendental, uno escribe

{displaystyle f(x)=g(x)-h(x).}

Los valores de $x$ que resuelven la ecuación original son entonces las raíces de $f (x)$ , que se puede encontrar a través del método de Newton.

Obtención de ceros de funciones especiales

Se aplica el método de Newton a la relación de funciones de Bessel para obtener su raíz.

Verificación numérica para soluciones de ecuaciones no lineales

Se ha establecido una verificación numérica para soluciones de ecuaciones no lineales utilizando el método de Newton varias veces y formando un conjunto de soluciones candidatas.

Ejemplos

Raíz cuadrada

Considere el problema de encontrar la raíz cuadrada de un número $a$ , es decir el número positivo $x$ tal que $x 2 = a . El método de Newton es uno de los muchos métodos para calcular raíces cuadradas. Podemos reformularlo como encontrar el cero de f (x) = x 2 - a . Tenemos f' (x) = 2 x .$

Por ejemplo, para encontrar la raíz cuadrada de 612 con una suposición inicial $x 0 = 10$ , la secuencia dada por el método de Newton es:

{displaystyle {begin{matrix}x_{1}&=&x_{0}-{dfrac {f(x_{0})}{f'(x_{0})}}&=&10-{dfrac {10^{2}-612}{2times 10}}&=&35.6qquad qquad qquad quad ;,{}\x_{2}&=&x_{1}-{dfrac {f(x_{1})}{f'(x_{1})}}&=&35.6-{dfrac {35.6^{2}-612}{2times 35.6}}&=&{underline {2}}6.395,505,617,978dots \x_{3}&=&vdots &=&vdots &=&{underline {24.7}}90,635,492,455dots \x_{4}&=&vdots &=&vdots &=&{underline {24.738,6}}88,294,075dots \x_{5}&=&vdots &=&vdots &=&{underline {24.738,633,753,7}}67dots end{matrix}}}

donde se subrayan los dígitos correctos. Con solo unas pocas iteraciones, se puede obtener una solución precisa con muchos decimales.

Al reorganizar la fórmula de la siguiente manera se obtiene el método babilónico para encontrar raíces cuadradas:

{displaystyle x_{n+1}=x_{n}-{frac {f(x_{n})}{f'(x_{n})}}=x_{n}-{frac {x_{n}^{2}-a}{2x_{n}}}={frac {1}{2}}{biggl (}2x_{n}-{Bigl (}x_{n}-{frac {a}{x_{n}}}{Bigr)}{biggr)}={frac {1}{2}}{Bigl (}x_{n}+{frac {a}{x_{n}}}{Bigr)}}

es decir la media aritmética de la conjetura, $x n$ y $a / x n$ .

Solución de cos(x) = x3

Considerar el problema de encontrar el número positivo ${textstyle x}$ con ${textstyle cos x=x^{3}}$ . Podemos reformular eso como encontrar el cero de ${textstyle f(x)=cos(x)-x^{3}}$ . Tenemos ${textstyle f'(x)=-sin(x)-3x^{2}}$ . Desde ${textstyle cos(x)leq 1}$ para todos ${textstyle x}$ y $1}" xmlns="http://www.w3.org/1998/Math/MathML">x3■1{textstyle x^{3}]1}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3ae03d6d4b823349f5e1e0eb8028426cfc045a8f" style="vertical-align: -0.338ex; width:6.645ex; height:2.509ex;"/>$ para $1}" xmlns="http://www.w3.org/1998/Math/MathML">x■1{textstyle x título1}1}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/638645c800c290bcb96035d96b2813f1cecc328a" style="vertical-align: -0.338ex; width:5.591ex; height:2.176ex;"/>$ , sabemos que nuestra solución está entre 0 y 1.

Por ejemplo, con una suposición inicial $x 0 = 0.5$ , la secuencia dada por Newton's El método es (tenga en cuenta que un valor inicial de 0 conducirá a un resultado indefinido, lo que muestra la importancia de utilizar un punto de partida que esté cerca de la solución):

{displaystyle {begin{matrix}x_{1}&=&x_{0}-{dfrac {f(x_{0})}{f'(x_{0})}}&=&0.5-{dfrac {cos 0.5-0.5^{3}}{-sin 0.5-3times 0.5^{2}}}&=&1.112,141,637,097dots \x_{2}&=&x_{1}-{dfrac {f(x_{1})}{f'(x_{1})}}&=&vdots &=&{underline {0.}}909,672,693,736dots \x_{3}&=&vdots &=&vdots &=&{underline {0.86}}7,263,818,209dots \x_{4}&=&vdots &=&vdots &=&{underline {0.865,47}}7,135,298dots \x_{5}&=&vdots &=&vdots &=&{underline {0.865,474,033,1}}11dots \x_{6}&=&vdots &=&vdots &=&{underline {0.865,474,033,102}}dots end{matrix}}}

Los dígitos correctos están subrayados en el ejemplo anterior. En particular, $x 6$ es correcto con 12 decimales. Vemos que el número de dígitos correctos después del punto decimal aumenta de 2 (para $x 3$ ) a 5 y 10, que ilustra la convergencia cuadrática.

Código

El siguiente es un ejemplo de implementación del método de Newton en el lenguaje de programación Python (versión 3.x) para encontrar la raíz de una función f que tiene la derivada f_prime .

La suposición inicial será $x 0 = 1$ y la función será $f (x) = x 2 - 2$ de modo que $f' (x) = 2 x$ .

Cada nueva iteración del método de Newton se denotará por x1. Comprobaremos durante el cálculo si el denominador (yprime) se vuelve demasiado pequeño (menor que epsilon), que sería el caso si $f' (x n) \approx 0$ , ya que de lo contrario se podría introducir una gran cantidad de error.

def f()x): retorno x#2 - 2 # f(x) = x^2 - 2def f_prime()x):retorno 2*x # f'(x) = 2xdef newtons_method() x0, # La suposición inicial f, # La función cuya raíz estamos tratando de encontrar f_prime, # El derivado de la función tolerancia, # 7-digit accuracy is wanted epsilon, # No dividir por un número menor que este max_iterations, # El número máximo de iteraciones para ejecutar ): para i dentro rango()max_iterations): Sí. = f()x0) Yprime = f_prime()x0) si abdominales()Yprime) . epsilon: # Pare si el denominador es demasiado pequeño descanso x1 = x0 - Sí. / Yprime # Do Newton's computation si abdominales()x1 - x0) . tolerancia: # Pare cuando el resultado está dentro de la tolerancia deseada retorno x1 # x1 es una solución dentro de la tolerancia y el número máximo de iteraciones x0 = x1 # Update x0 to start the process again retorno Ninguno # Newton's method did not converge

`Contenido relacionado`

El dilema del prisionero
Wikipedia: Rouse Historia de las Matemáticas
Blaise Pascual
 Más resultados... 
Te puede interesar