En análisis numérico , el método de Newton , también conocido como método de Newton-Raphson , llamado así en honor a Isaac Newton y Joseph Raphson , es un algoritmo de búsqueda de raíces que produce sucesivamente mejores aproximaciones 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 valor real f , su derivada f ′ y una estimación inicial x 0 para una raíz de f . Si f satisface ciertos supuestos y la estimación inicial es cercana, entonces
es una mejor aproximación de la raíz que x 0 . Geométricamente, ( x 1 , 0) es la intersección con el eje x de la tangente de la gráfica de f en ( x 0 , f ( x 0 )) : es decir, la suposición mejorada, x 1 , es la raíz única de la ecuación lineal. aproximación de f en la estimación inicial, x 0 . El proceso se repite como
hasta alcanzar un valor suficientemente preciso. El número de dígitos correctos aproximadamente se duplica con cada paso. Este algoritmo es el primero en la clase de métodos de Householder y fue sucedido por el método de Halley . El método también se puede extender a funciones complejas y sistemas de ecuaciones .
La idea es comenzar con una suposición inicial, luego aproximar la función por su recta tangente y, finalmente, calcular la intersección con el eje x de esta recta tangente. Esta intersección con el eje x normalmente será una mejor aproximación a la raíz de la función original que la primera suposición, y el método se puede iterar .
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
Resolviendo para x n +1 se obtiene
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 sobre 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 al teorema del valor intermedio .) El método normalmente convergerá, siempre que esta suposición inicial esté lo suficientemente cerca del cero desconocido y que f ′ ( x 0 ) ≠ 0 . Además, para un cero de multiplicidad 1, la convergencia es al menos cuadrática (ver Tasa de convergencia ) en una vecindad del cero, lo que intuitivamente significa que el número de dígitos correctos aproximadamente se duplica en cada paso. Se pueden encontrar más detalles en el § Análisis a continuación.
Los métodos de los hogares son similares pero tienen un orden superior 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 derivadas son computacionalmente costosas de evaluar.
El nombre "método de Newton" se deriva de la descripción que hizo 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 Método de Fluxiones en 1736 por John Colson ). Sin embargo, su método difiere sustancialmente del método moderno expuesto anteriormente. Newton aplicó el método sólo a polinomios, comenzando con una estimación de raíz 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 ignorando los términos de mayor grado. No relacionó explícitamente el método con derivadas ni presentó una fórmula general. Newton aplicó este método a problemas tanto numéricos como algebraicos, produciendo series de Taylor en el último caso.
Newton pudo haber derivado su método de un método similar, 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ī utilizó 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. [1]
El método de Newton se publicó por primera vez en 1685 en Tratado de álgebra histórica y práctica de John Wallis . [2] En 1690, Joseph Raphson publicó una descripción simplificada en Analysis aequationum universalis . [3] Raphson también aplicó el método sólo 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 mediante cálculo, dando esencialmente la descripción anterior. En la misma publicación, Simpson también ofrece la generalización a sistemas de dos ecuaciones y señala que el método de Newton se puede utilizar para resolver problemas de optimización estableciendo 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 las iteraciones de funciones racionales.
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 exactos aproximadamente se duplica) en cada paso. Sin embargo, existen algunas dificultades con el método.
El método de Newton requiere que la derivada se pueda calcular directamente. Es posible que no sea fácil obtener una expresión analítica para la derivada o que su evaluación sea costosa. En estas situaciones, puede ser apropiado aproximar la derivada utilizando la pendiente de una recta que pasa por dos puntos cercanos de la función. Usar esta aproximación daría como resultado algo parecido al método de la secante cuya convergencia es más lenta que la del método de Newton.
Es importante revisar la prueba de convergencia cuadrática del método de Newton antes de implementarlo. Específicamente, se deben revisar los supuestos hechos en la prueba. Para situaciones en las que el método no converge, es porque no se cumplen los supuestos hechos en esta prueba.
Por ejemplo, en algunos casos, si la primera derivada no se comporta bien en la vecindad de una raíz particular, entonces es posible que el método de Newton no converja sin importar dónde se establezca la inicialización. En algunos casos, el método de Newton se puede estabilizar mediante el uso de una relajación excesiva sucesiva , o se puede aumentar la velocidad de convergencia utilizando el mismo método.
En una implementación sólida del método de Newton, es común imponer límites al 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.
Si la raíz que se busca tiene una multiplicidad mayor que uno, la tasa de convergencia es meramente lineal (los errores se reducen en 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 ser necesarias 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: [4]
Esto equivale a utilizar sucesivas sobrerelajaciones . 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 utilizar 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 el mismo lugar con multiplicidad 1. La aplicación del método de Newton para encontrar la raíz de g ( x ) recupera la convergencia cuadrática en muchos casos, aunque generalmente involucra la segunda derivada de f ( x ) . En un caso particularmente simple, si f ( x ) = x m entonces g ( x ) = X/metro y el método de Newton encuentra la raíz en una sola iteración con
Supongamos que la función f tiene un cero en α , es decir, f ( α ) = 0 , y f es derivable 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 esa vecindad, la secuencia ( x n ) convergerá a α . [5]
Si f es continuamente diferenciable, su derivada es distinta de cero 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:
dónde
Si la derivada es 0 en α , entonces la convergencia suele ser sólo lineal. Específicamente, si f es dos veces continuamente diferenciable, f ′ ( α ) = 0 y f ″ ( α ) ≠ 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 . [6] Alternativamente, si f ′ ( α ) = 0 y f ′ ( x ) ≠ 0 para x ≠ α , x en una vecindad U de α , siendo α un cero de multiplicidad r , y si f ∈ C r ( U ) , entonces existe una vecindad de α tal que, para todos los valores iniciales x 0 en esa vecindad, la secuencia de iteraciones converge 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 ′ ≠ 0 , f · f ″ > 0 en U + , entonces, para cada x 0 en U + la secuencia x k disminuye monótonamente a α .
Según el teorema de Taylor , cualquier función f ( x ) que tenga una segunda derivada continua puede representarse mediante una expansión alrededor de un punto cercano a una raíz de f ( x ) . Supongamos que esta raíz es α . Entonces la expansión de f ( α ) alrededor de x n es:
donde la forma de Lagrange del resto de la expansión de la serie de Taylor es
donde ξ n está entre x n y α .
Dado que α es la raíz, ( 1 ) se convierte en:
Dividiendo la ecuación ( 2 ) por f ′ ( x n ) y reordenando se obtiene
Recordando que x n + 1 está definido por
uno encuentra que
Eso es,
Tomando el valor absoluto de ambos lados se obtiene
La ecuación ( 6 ) muestra que el orden de convergencia es al menos cuadrático si se cumplen las siguientes condiciones:
donde M está dada por
Si estas condiciones se mantienen,
Supongamos que f ( x ) es una función cóncava en un intervalo, que es estrictamente creciente . Si es negativo en el extremo izquierdo y positivo en el extremo derecho, el teorema del valor intermedio garantiza que hay un cero ζ de f en algún lugar del intervalo. A partir de principios geométricos, se puede ver que la iteración de Newton x i que comienza en el punto final izquierdo es monótonamente creciente y convergente, necesariamente a ζ . [7]
Joseph Fourier introdujo una modificación del método de Newton comenzando en el punto final derecho:
Esta secuencia es monótonamente decreciente y convergente. Pasando al límite en esta definición, se puede ver que el límite de y i también debe ser el cero ζ . [7]
Entonces, en el caso de una función cóncava creciente con cero, la inicialización es en gran medida irrelevante. La iteración de Newton que comienza en cualquier lugar a la izquierda del cero convergerá, al igual que la iteración de Newton modificada de Fourier que comienza en cualquier lugar a la derecha del cero. La precisión en cualquier paso de la iteración se puede determinar directamente a partir de la diferencia entre la ubicación de la iteración desde la izquierda y la ubicación de la iteración desde la derecha. Si f es dos veces continuamente diferenciable, se puede demostrar utilizando el teorema de Taylor que
mostrando que esta diferencia de ubicaciones converge cuadráticamente a cero. [7]
Todo lo anterior puede extenderse a sistemas de ecuaciones en múltiples variables, aunque en ese contexto los conceptos relevantes de monotonicidad y concavidad son más sutiles de formular. [8] En el caso de ecuaciones simples en una sola variable, la convergencia monótona anterior del método de Newton también se puede generalizar para reemplazar la concavidad por condiciones de positividad o negatividad en una derivada arbitraria de orden superior de f . Sin embargo, en esta generalización, la iteración de Newton se modifica para basarse en polinomios de Taylor en lugar de en la recta tangente . En el caso de la concavidad, esta modificación coincide con el método estándar de Newton. [9]
El método de Newton es uno de los muchos métodos conocidos para calcular raíces cuadradas . Dado un número positivo a , el problema de encontrar un número x tal que x 2 = a es equivalente a encontrar una raíz de la función f ( x ) = x 2 − a . La iteración de Newton definida por esta función viene dada por
Esto coincide con el método "babilónico" de encontrar raíces cuadradas , que consiste en sustituir una raíz aproximada x n por la media aritmética de x n y a ⁄ x n . Al realizar esta iteración, es posible evaluar una raíz cuadrada con la precisión deseada utilizando únicamente las operaciones aritméticas básicas .
Las siguientes tres tablas muestran ejemplos del resultado de este cálculo para encontrar la raíz cuadrada de 612, con la iteración inicializada en los valores de 1, 10 y −20. Cada fila de una columna " x n " se obtiene aplicando la fórmula anterior a la entrada que está encima, por ejemplo
Los dígitos correctos están subrayados. Se ve que con sólo unas pocas iteraciones se puede obtener una solución con una precisión de muchos decimales. La primera tabla muestra que esto es cierto incluso si la iteración de Newton se inicializó mediante la estimación muy inexacta de 1 .
Al calcular cualquier raíz cuadrada distinta de cero, la primera derivada de f debe ser distinta de cero en la raíz, y f es una función uniforme. Entonces, incluso antes de cualquier cálculo, se sabe que cualquier iteración convergente de Newton tiene una tasa de convergencia cuadrática. Esto se refleja en las tablas anteriores por el hecho de que una vez que una iteración de Newton se acerca a la raíz, el número de dígitos correctos aproximadamente se duplica con cada iteración.
Considere el problema de encontrar el número positivo x con cos x = x 3 . Podemos reformularlo como encontrar el cero de f ( x ) = cos( x ) − x 3 . Tenemos f ′ ( x ) = −sin( x ) − 3 x 2 . Dado que cos( x ) ≤ 1 para todo x y x 3 > 1 para x > 1 , sabemos que nuestra solución se encuentra entre 0 y 1.
Un valor inicial de 0 conducirá a un resultado indefinido que ilustra la importancia de utilizar un punto de partida cercano a la solución. Por ejemplo, con una estimación inicial x 0 = 0,5 , la secuencia dada por el método de Newton es:
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, lo que ilustra la convergencia cuadrática.
La función f ( x ) = x 2 tiene una raíz en 0. [10] Dado que f es continuamente diferenciable en su raíz, la teoría garantiza que el método de Newton, inicializado lo suficientemente cerca de la raíz, convergerá. Sin embargo, dado que la derivada f ′ es cero en la raíz, la teoría no garantiza la convergencia cuadrática. En este ejemplo particular, la iteración de Newton viene dada por
De esto se desprende que el método de Newton podría inicializarse en cualquier lugar y converger a cero, pero sólo a una velocidad lineal. Si se inicializa en 1, se necesitarán docenas de iteraciones antes de alcanzar diez dígitos de precisión.
La función f ( x ) = x + x 4/3 también tiene una raíz en 0, donde es continuamente diferenciable. Aunque la primera derivada f ′ es distinta de cero en la raíz, la segunda derivada f ′′ no existe allí, por lo que no se puede garantizar la convergencia cuadrática. De hecho, la iteración de Newton viene dada por
De esto se puede ver que la tasa de convergencia es superlineal pero subcuadrática. Esto se puede ver en las siguientes tablas, la izquierda de las cuales muestra el método de Newton aplicado a f ( x ) = x + x 4/3 y la derecha muestra el método de Newton aplicado a f ( x ) = x + x 2 . La convergencia cuadrática en la iteración que se muestra a la derecha se ilustra con los órdenes de magnitud en la distancia desde la iteración hasta la raíz verdadera (0,1,2,3,5,10,20,39,...) que se duplican aproximadamente. de fila en fila. Si bien la convergencia de la izquierda es superlineal, el orden de magnitud sólo se multiplica por aproximadamente 4/3 de una fila a otra (0,1,2,4,5,7,10,13,...).
La tasa de convergencia se distingue del número de iteraciones necesarias para alcanzar una precisión determinada. Por ejemplo, la función f ( x ) = x 20 − 1 tiene una raíz en 1. Como f ′(1) ≠ 0 y f es suave, se sabe que cualquier iteración de Newton convergente a 1 convergerá cuadráticamente. Sin embargo, si se inicializa en 0,5, las primeras iteraciones del método de Newton son aproximadamente 26214, 24904, 23658, 22476, disminuyendo lentamente, siendo solo la iteración número 200 1,0371. Las siguientes iteraciones son 1.0103, 1.00093, 1.0000082 y 1.00000000065, lo que ilustra la convergencia cuadrática. Esto resalta que la convergencia cuadrática de una iteración de Newton no significa que sólo se requieran unas pocas iteraciones; esto sólo se aplica una vez que la secuencia de iteraciones está lo suficientemente cerca de la raíz. [11]
La función f ( x ) = x (1 + x 2 ) −1/2 tiene una raíz en 0. La iteración de Newton viene dada por
De esto se puede ver que hay tres fenómenos posibles para una iteración de Newton. Si se inicializa estrictamente entre ±1 , la iteración de Newton convergerá (súper)cuadráticamente a 0; si se inicializa exactamente en 1 o −1 , la iteración de Newton oscilará infinitamente entre ±1 ; si se inicializa en cualquier otro lugar, la iteración de Newton divergirá. [12] Esta misma tricotomía ocurre para f ( x ) = arctan x . [10]
En los casos en que la función en cuestión tiene múltiples raíces, puede resultar difícil controlar, mediante la elección de la inicialización, qué raíz (si la hay) se identifica mediante el método de Newton. Por ejemplo, la función f ( x ) = x ( x 2 − 1)( x − 3)e −( x − 1) 2 /2 tiene raíces en −1, 0, 1 y 3. [13] Si se inicializa en −1,488, la iteración de Newton converge a 0; si se inicializa en −1,487, diverge a ∞ ; si se inicializa en −1,486, converge a −1; si se inicializa en −1,485, diverge a −∞ ; si se inicializa en −1,4843, converge a 3; si se inicializa en −1,484, converge a 1 . Este tipo de dependencia sutil de la inicialización no es infrecuente; se estudia frecuentemente en el plano complejo en forma de fractal de Newton .
Considere el problema de encontrar una raíz de f ( x ) = x 1/3 . La iteración de Newton es
A menos que el método de Newton se inicialice en la raíz exacta 0, se ve que la secuencia de iteraciones no logrará converger. Por ejemplo, incluso si se inicializa con una estimación razonablemente precisa de 0,001, las primeras iteraciones son −0,002, 0,004, −0,008, 0,016, alcanzando 1048,58, −2097,15, ... en la vigésima iteración. Esta falla de convergencia no se contradice con la teoría analítica, ya que en este caso f no es diferenciable en su raíz.
En el ejemplo anterior, el fracaso de la convergencia se refleja en el hecho de que f ( x n ) no logra acercarse a cero a medida que n aumenta, así como en el hecho de que las iteraciones sucesivas se alejan cada vez más. Sin embargo, la función f ( x ) = x 1/3 e − x 2 también tiene una raíz en 0. La iteración de Newton viene dada por
En este ejemplo, donde nuevamente f no es diferenciable en la raíz, cualquier iteración de Newton que no comience exactamente en la raíz divergirá, pero tanto x n + 1 − x n como f ( x n ) convergerán a cero. [14] Esto se ve en la siguiente tabla que muestra las iteraciones con la inicialización 1:
Aunque la convergencia de x n + 1 − x n en este caso no es muy rápida, se puede demostrar a partir de la fórmula de iteración. Este ejemplo resalta la posibilidad de que un criterio de parada para el método de Newton basado únicamente en la pequeñez de x n + 1 − x n y f ( x n ) pueda identificar falsamente una raíz.
Es fácil encontrar situaciones en las que el método de Newton oscila infinitamente entre dos valores distintos. Por ejemplo, para que el método de Newton aplicado a una función f oscile entre 0 y 1, sólo es necesario que la recta tangente a f en 0 interseque al eje x en 1 y que la recta tangente a f en 1 intersecte al eje x en 1. -eje en 0. [14] Este es el caso, por ejemplo, si f ( x ) = x 3 − 2 x + 2 . Para esta función, incluso se da el caso de que la iteración de Newton, inicializada lo suficientemente cerca de 0 o 1, oscilará asintóticamente entre estos valores. Por ejemplo, el método de Newton inicializado en 0,99 produce iteraciones 0,99, −0,06317, 1,00628, 0,03651, 1,00196, 0,01162, 1,00020, 0,00120, 1,000002, etc. Este comportamiento está presente a pesar de la presencia de una raíz de f aproximadamente igual a −1,76929.
En algunos casos ni siquiera es posible realizar la iteración de Newton. Por ejemplo, si f ( x ) = x 2 − 1 , entonces la iteración de Newton se define por
Por tanto, el método de Newton no puede inicializarse en 0, ya que esto haría que x 1 no estuviera definido. Geométricamente, esto se debe a que la línea tangente a f en 0 es horizontal (es decir, f ′(0) = 0 ), y nunca cruza el eje x .
Incluso si la inicialización se selecciona de manera que pueda comenzar la iteración de Newton, los mismos fenómenos pueden impedir que la iteración continúe indefinidamente.
Si f tiene un dominio incompleto, es posible que el método de Newton envíe las iteraciones fuera del dominio, de modo que sea imposible continuar la iteración. [14] Por ejemplo, la función logaritmo natural f ( x ) = ln x tiene una raíz en 1 y se define solo para x positivo . La iteración de Newton en este caso viene dada por
Entonces, si la iteración se inicializa en e , la siguiente iteración es 0; Si la iteración se inicializa con un valor mayor que e , entonces la siguiente iteración es negativa. En cualquier caso, el método no se puede continuar.
También se puede utilizar el método de Newton para resolver sistemas de k ecuaciones, lo que equivale a encontrar los ceros (simultáneos) de k funciones continuamente diferenciables. Esto equivale a encontrar los ceros de una única función con valores vectoriales. En la formulación dada anteriormente, los escalares x n se reemplazan por vectores x n y en lugar de dividir la función f ( x n ) por su derivada f ′ ( x n ) se debe multiplicar por la izquierda la función F ( x n ) por la inversa de su matriz jacobiana k × k J F ( x norte ) . [15] [16] [17] Esto da como resultado la expresión
o, resolviendo el sistema de ecuaciones lineales
para la incógnita x n + 1 − x n . [18]
La variante k -dimensional del método de Newton también se puede utilizar para resolver sistemas de ecuaciones (no lineales) mayores que k si el algoritmo utiliza la inversa generalizada 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.
Por ejemplo, es necesario resolver el siguiente conjunto de ecuaciones para el vector de puntos dado el vector de valores conocidos [19]
el vector de función, la matriz jacobiana, para la iteración k, y el vector de valores conocidos, se definen a continuación.
Tenga en cuenta que podría haberse reescrito para absorber y así eliminar de las ecuaciones. La ecuación a resolver para cada iteración es
y
Las iteraciones deben repetirse hasta que haya un valor lo suficientemente pequeño como para cumplir con los requisitos de la aplicación.
Si inicialmente se elige que el vector sea es decir, y y se elige que sea 1,10 −3 , entonces el ejemplo converge después de cuatro iteraciones a un valor de
Las siguientes iteraciones se realizaron durante el transcurso de la solución.
Cuando se trata de funciones complejas , el método de Newton se puede aplicar directamente para encontrar sus ceros. [20] 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, [21] si uno usa una condición inicial real para buscar una raíz de x 2 + 1 , todas las iteraciones posteriores serán números reales y, por lo tanto, las iteraciones no pueden converger a ninguna de las raíces, 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 se iteran hasta el infinito o hasta ciclos repetidos de cualquier longitud finita.
Curt McMullen ha demostrado que para cualquier posible algoritmo puramente iterativo similar al método de Newton, el algoritmo divergirá en algunas regiones abiertas del plano complejo cuando se aplique a algún polinomio de grado 4 o superior. Sin embargo, McMullen dio un algoritmo generalmente convergente para polinomios de grado 3. [22] Además, para cualquier polinomio, Hubbard, Schleicher y Sutherland dieron un método para seleccionar un conjunto de puntos iniciales tales que el método de Newton ciertamente convergerá en uno de ellos. al menos. [23]
Otra generalización es el método de Newton para encontrar una raíz de un funcional F definido en un espacio de Banach . En este caso la formulación es
donde F ′ ( X n ) es la derivada de Fréchet calculada en X n . Es necesario que la derivada de Fréchet sea acotadamente invertible en cada X n para que el método sea aplicable. Una condición para la existencia y la convergencia de una raíz viene dada por el teorema de Newton-Kantorovich . [24]
En la década de 1950, John Nash desarrolló una versión del método de Newton para aplicarlo al problema de construir incrustaciones isométricas de variedades riemannianas generales en el espacio euclidiano . El problema de la pérdida de derivadas , presente en este contexto, hizo que la iteración estándar de Newton fuera inaplicable, ya que no podía continuar indefinidamente (y mucho menos converger). La solución de Nash implicó la introducción de operadores de suavizado en la iteración. Pudo demostrar la convergencia de su método de Newton suavizado, con el fin de demostrar un teorema de función implícita para incrustaciones isométricas. En la década de 1960, Jürgen Moser demostró que los métodos de Nash eran lo suficientemente flexibles como para aplicarse a problemas más allá de la incrustación isométrica, particularmente en la mecánica celeste . Desde entonces, varios matemáticos, incluidos Mikhael Gromov y Richard Hamilton , han encontrado versiones abstractas generalizadas de la teoría de Nash-Moser. [25] [26] En la formulación de Hamilton, el teorema de Nash-Moser forma una generalización del método de Newton del espacio de Banach que tiene lugar en ciertos espacios de Fréchet .
Cuando el jacobiano no está disponible o es demasiado costoso calcularlo en cada iteración, se puede utilizar un método cuasi-Newton .
En el análisis p -ádico, el método estándar para mostrar una ecuación polinómica en una variable tiene una raíz p -ádica es el lema de Hensel , que utiliza la recursividad del método de Newton en los números p -á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 los p -ádicos es un anillo), la convergencia en el lema de Hensel puede garantizarse bajo hipótesis mucho más simples que en El método clásico de Newton sobre la recta real.
El método de Newton se puede generalizar con el q -análogo de la derivada habitual. [27]
Una ecuación no lineal tiene múltiples soluciones en general. Pero si el valor inicial no es apropiado, es posible que el método de Newton no converja a la solución deseada o que converja a la misma solución encontrada anteriormente. Cuando ya hemos encontrado N soluciones de , entonces la siguiente raíz se puede encontrar aplicando el método de Newton a la siguiente ecuación: [28] [29]
Este método se aplica para obtener ceros de la función de Bessel de segundo tipo. [30]
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. [31] Está desarrollado para resolver polinomios complejos.
Combinar el método de Newton con la aritmética de intervalos resulta 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 el valor de la función). ; ver polinomio de Wilkinson ). [32] [33]
Considere f → 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 ⊆ X y genera un intervalo F ′ ( Y ) tal que:
También suponemos que 0 ∉ F ′ ( X ) , por lo que en particular f tiene como máximo una raíz en X . Luego definimos el operador de Newton de intervalo como:
dónde metro ∈ Y . Tenga en cuenta que la hipótesis sobre F ′ implica que N ( Y ) está bien definido y es un intervalo (consulte aritmética de intervalos para obtener más detalles sobre las operaciones de intervalo). Esto naturalmente conduce a la siguiente secuencia:
El teorema del valor medio asegura que si hay una raíz de f en X k , entonces también lo estará en X k + 1 . Además, la hipótesis sobre F′ asegura que X k + 1 tiene 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 intervalos extendidos produce una unión de dos intervalos para N ( X ) ; por lo tanto, varias raíces se separan y delimitan automáticamente.
El método de Newton se puede utilizar para encontrar el mínimo o el máximo de una función f ( x ) . La derivada es cero en un mínimo o máximo, por lo que los mínimos y máximos locales se pueden encontrar aplicando el método de Newton a la derivada. [34] La iteración se convierte en:
Una aplicación importante es la división de Newton-Raphson , que se puede utilizar para encontrar rápidamente el recíproco de un número a , usando únicamente la multiplicación y la resta, es decir el número x tal que 1/X = un . Podemos reformularlo como encontrar el cero de f ( x ) = 1/X − un . Tenemos f ′ ( x ) = − 1/x2 .
La iteración de Newton es
Por lo tanto, la iteración de Newton necesita sólo dos multiplicaciones y una resta.
Este método también es muy eficiente para calcular el inverso multiplicativo de una serie de potencias .
Muchas ecuaciones trascendentales se pueden resolver con una precisión arbitraria utilizando el método de Newton. Por ejemplo, encontrar la función de densidad de probabilidad acumulada , como una distribución normal que se ajuste a una probabilidad conocida, generalmente implica funciones integrales sin medios conocidos para resolver en forma cerrada. Sin embargo, generalmente se sabe calcular las derivadas necesarias para resolverlos numéricamente con el método de Newton, lo que hace posibles las soluciones numéricas. Para ver un ejemplo, consulte la solución numérica de la distribución acumulativa normal inversa .
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. [ cita necesaria ]
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 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
), lo que sería el caso si f ′ ( x n ) ≈ 0 , ya que de lo contrario se podría introducir una gran cantidad de error.
definición f ( x ): devolver x ** 2 - 2 # f(x) = x^2 - 2def f_prime ( x ):devolver 2 * x # f'(x) = 2xdef método_newtons ( x0 , f , f_prime , tolerancia , épsilon , max_iterations ): """Método de Newton Argumentos: x0: la suposición inicial f: La función cuya raíz estamos tratando de encontrar f_prime: La derivada de la función. tolerancia: se detiene cuando las iteraciones cambian menos que esto épsilon: No divida por un número menor que este max_iterations: el número máximo de iteraciones para calcular """ para _ dentro del rango ( max_iterations ): y = f ( x0 ) yprime = f_prime ( x0 ) if abs ( yprime ) < epsilon : # Ríndete si el denominador es demasiado pequeño romper x1 = x0 - y / yprime # Haz el cálculo de Newton if abs ( x1 - x0 ) <= tolerancia : # Detener cuando el resultado esté dentro de la tolerancia deseada return x1 # x1 es una solución dentro de la tolerancia y el número máximo de iteraciones x0 = x1 # Actualiza x0 para iniciar el proceso nuevamente return Ninguno # El método de Newton no convergió