El método de Newton

Algoritmo para encontrar ceros de funciones.

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 ₀ para una raíz de f . Si f satisface ciertos supuestos y la estimación 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 ₀ . Geométricamente, ( x ₁ , 0) es la intersección con el eje x de la tangente de la gráfica de f en ( x ₀ , f ( x ₀ )) : es decir, la suposición mejorada, x ₁ , es la raíz única de la ecuación lineal . aproximación de f en la estimación inicial, x ₀ . 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 aproximadamente se duplica con cada paso. Este algoritmo es el primero en la clase de métodos de Householder , sucedido por el método de Halley . El método también se puede extender a funciones complejas y a sistemas de ecuaciones .

Descripción

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 .

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} se obtiene

$${\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 ₀ . (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 generalmente convergerá, siempre que esta suposición inicial esté lo suficientemente cerca del cero desconocido y que f ′ ( x ₀ ) ≠ 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.

Historia

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.

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 exactos aproximadamente se duplica) en cada paso. Sin embargo, existen 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. 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.

Fallo 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, 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.

Excederse

Si la primera derivada no se comporta bien en la vecindad de una raíz particular, el método puede sobrepasarse 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

$${\displaystyle f(x)=|x|^{a},\quad 0<a<{\tfrac {1}{2}}}$$

para lo cual la raíz se sobrepasará y la secuencia de x divergirá. Para un =1/2, la raíz seguirá sobrepasándose, pero la secuencia oscilará entre dos valores. Para1/2< a < 1 , la raíz aún se sobrepasará pero la secuencia convergerá, y para a ≥ 1 la raíz no se sobrepasará en absoluto.

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.

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 .

Mala estimación inicial

Un gran error en la estimación inicial puede contribuir a la no convergencia del algoritmo. Para superar este problema, a menudo se puede linealizar la función que se está optimizando mediante cálculo, registros, diferenciales o incluso 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 cuadrados (SSE) es sólo "cerca de" parabólica en la región de las estimaciones de los parámetros finales. Las estimaciones iniciales encontradas aquí permitirán que el método de Newton-Raphson converja rápidamente. Sólo aquí la matriz de Hesse del SSE es positiva y la primera derivada del SSE es cercana a cero.

Mitigación de la no convergencia

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.

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 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]

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

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 la misma ubicación 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/metroy 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

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 ₀ 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:

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

dónde

$${\displaystyle \Delta x_{i}\triangleq x_{i}-\alpha \,.}$$

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 ₀ 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 ₀ 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 ₀ en U ₊ la secuencia x _k disminuye monótonamente a α .

Prueba de convergencia cuadrática del método iterativo de Newton

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

$${\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:

Dividiendo la ecuación ( 2 ) por f ′ ( x _n ) y reordenando se obtiene

Recordando que x _{n + 1} está definido por

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}\,.}$$

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:

1. f ′ ( x ) ≠ 0 ; para todo x ∈ I , donde I es el intervalo [ α − | ε ₀ |, α + | ε ₀ |] ;
2. f ″ ( x ) es continua, para todo x ∈ I ;
3. METRO | ε ₀ | < 1

donde M está dada por

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

Si estas condiciones se mantienen,

$${\displaystyle \vert \varepsilon _{n+1}\vert \leq M\cdot \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, ^[7] para la función f ( x ) = x ³ − 2 x ² − 11 x + 12 = ( x − 4)( x − 1)( x + 3) , las siguientes condiciones iniciales están en cuencas sucesivas de atracción:

Analisis fallido

Sólo se garantiza que el método de Newton convergerá si se cumplen ciertas condiciones. Si se cumplen los supuestos hechos en la prueba de convergencia cuadrática, el método convergerá. Para las siguientes subsecciones, la falla del método para converger indica que no se cumplieron los supuestos hechos en la prueba.

Malos puntos de partida

En algunos casos se satisfacen las condiciones de la función 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 se acerca a cero asintóticamente cuando x va a ∞ o −∞ . En tales casos, se debe utilizar un método diferente, como la bisección , para obtener una mejor estimación del cero que se utilizará 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 = ±1 . Si comenzamos a iterar desde el punto estacionario x ₀ = 0 (donde la derivada es cero), x ₁ no estará definido, ya que la tangente en (0, 1) es paralela al eje x :

$${\displaystyle 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 partida, 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 rectas tangentes de x ³ − 2 x + 2 en 0 y 1 intersectan el eje x en 1 y 0 respectivamente, lo que ilustra 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

$${\displaystyle 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 los dos sin converger a una raíz. De hecho, este 2 ciclo es estable: hay vecindades alrededor de 0 y alrededor de 1 a partir de las cuales todos los puntos iteran asintóticamente hasta el 2 ciclo (y por lo tanto no hasta la raíz de la función). En general, el comportamiento de la secuencia puede ser muy complejo (ver fractal de Newton ). La verdadera solución de esta ecuación es−1,769 292 35 ...

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 sencillo de una función en la que 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:

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

Para cualquier punto de iteración x _n , el siguiente 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 en el otro lado del eje y , más lejos de lo que estaba inicialmente; La aplicación del 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 < α <1/2. En el caso límite de α =1/2(raíz cuadrada), las iteraciones se alternarán indefinidamente entre los puntos x ₀ y − x ₀ , por lo que tampoco convergen en este caso.

Derivado discontinuo

Si la derivada no es continua en la raíz, entonces es posible que no se produzca convergencia 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 }}x\neq 0.\end{cases}}}$$

Su derivada es:

$${\displaystyle f'(x)={\begin{cases}1&{\text{if }}x=0,\\1+2x\sin {\frac {2}{x}}-2\cos {\frac {2}{x}}&{\text{if }}x\neq 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 por la derecha (o por la izquierda) mientras f ( x ) ≥ x − x ² > 0 para 0 < x < 1 .

Entoncesf ( x )/f ' ( x )es ilimitado cerca de la raíz, y el método de Newton divergirá en casi todas partes en cualquier vecindad de ella, aunque:

• la función es diferenciable (y por tanto continua) en todas partes;
• la derivada en la raíz es distinta de cero;
• f es infinitamente diferenciable excepto en la raíz; y
• la derivada está acotada en una vecindad de la raíz (a diferencia def ( x )/f ' ( x )).

Convergencia no cuadrática

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

Derivada cero

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

$${\displaystyle 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.

Problemas similares ocurren incluso cuando la raíz es sólo "casi" doble. Por ejemplo, dejemos

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

Entonces las primeras iteraciones que comienzan en x ₀ = 1 son

x0 ₌ 1

x1 =_​0,500 250 376 ...

x2 =_​0,251 062 828 ...

x ₃ =0,127 507 934 ...

x4 =_​0,067 671 976 ...

x5 =_​0,041 224 176 ..

x ₆ =0,032 741 218 ...

x ₇ =0,031 642 362 ...

se necesitan seis iteraciones para llegar a un punto donde la convergencia parezca cuadrática.

Sin segunda derivada

Si no hay una segunda derivada en la raíz, entonces la convergencia puede no ser cuadrática. Dejar

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

Entonces

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

Y

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

excepto cuando x = 0 donde no está definido. Dado xn ,_​

$${\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 aproximadamente4/3veces más bits de precisión que los que tiene x _n . Esto es menos que el doble que se necesitaría 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 ⁵ − 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. ^[8] 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, ^[9] si uno usa una condición inicial real para buscar una raíz de x ² + 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. ^[10] 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. ^[11]

El método de tercer orden de Chebyshev

Iteración de 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, 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 ) . Esto da como resultado la expresión ${\displaystyle f:\mathbb {R} ^{k}\to \mathbb {R} .}$ ${\displaystyle F:\mathbb {R} ^{k}\to \mathbb {R} ^{k}.}$

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

En lugar de calcular realmente 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 también se puede utilizar para resolver sistemas de ecuaciones mayores que k (no lineales) si el algoritmo utiliza la inversa generalizada de la matriz jacobiana no cuadrada J ⁺ = ( J ^T J ) ⁻¹ 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 un funcional F definido 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 . Es necesario que la derivada de Fréchet sea acotadamente invertible en cada X _n para que el método sea aplicable. El teorema de Newton-Kantorovich da una condición para la existencia y la convergencia de una raíz . ^[12]

Sobre números p -ádicos

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.

Método de Newton-Fourier

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

Supongamos que f ( x ) es dos veces diferenciable de forma continua en [ a , b ] y que f contiene una raíz en este intervalo. Supongamos que f ′ ( x ), f ″ ( x ) ≠ 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 haya una raíz única en este intervalo; llámalo α . 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 ₀ = b el punto extremo derecho del intervalo y sea z ₀ = a el punto extremo izquierdo del intervalo. Dado x _n , defina

$${\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 serán estrictamente decrecientes hasta la raíz, mientras que las iteraciones z _n serán estrictamente crecientes hasta la raíz. También,

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

de modo 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 calcularlo en cada iteración, se puede utilizar un método cuasi-Newton .

q -analógico

El método de Newton se puede generalizar con el q -análogo de la derivada habitual. ^[13]

Métodos de Newton modificados

procedimiento de maehly

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: ^{[14] [15]} ${\displaystyle f(x)=0}$

$${\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 segundo tipo. ^[dieciséis]

El método 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. ^[17] Está desarrollado para resolver polinomios complejos.

Método de intervalo de Newton

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 ). ^{[18] [19]}

Considere f → C ¹ ( 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:

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

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:

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

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:

$${\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 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.

Aplicaciones

Problemas de minimización y maximización.

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. 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 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 que1/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

$${\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 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 .

Resolver ecuaciones trascendentales

Muchas ecuaciones trascendentales se pueden resolver con una precisión arbitraria utilizando el método de Newton.

Cuando el método de Newton se puede aplicar a una ecuación trascendental y converge a una solución de la ecuación, esto implica que la solución es un número computable que está representado exactamente por el par formado por una aproximación inicial y un algoritmo para aumentar la precisión de cualquier aproximación.

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. ^[20]

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. ^{[21] [22]}

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 ² = 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 ² − a . Tenemos f ′ ( x ) = 2 x .

Por ejemplo, para encontrar la raíz cuadrada de 612 con una estimación inicial x ₀ = 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}{2\times 10}}&=&35.6\qquad \qquad \qquad \quad \;\,{}\\x_{2}&=&x_{1}-{\dfrac {f(x_{1})}{f'(x_{1})}}&=&35.6-{\dfrac {35.6^{2}-612}{2\times 35.6}}&=&{\underline {2}}6.395\,505\,617\,978\dots \\x_{3}&=&\vdots &=&\vdots &=&{\underline {24.7}}90\,635\,492\,455\dots \\x_{4}&=&\vdots &=&\vdots &=&{\underline {24.738\,6}}88\,294\,075\dots \\x_{5}&=&\vdots &=&\vdots &=&{\underline {24.738\,633\,753\,7}}67\dots \end{matrix}}}$$

donde los dígitos correctos están subrayados. Con sólo unas pocas iteraciones se puede obtener una solución con una precisión de muchos decimales.

Reorganizando 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 suposición, x _n ya/xn_​.

Solución de cos( x ) = x 3

Considere el problema de encontrar el número positivo x con cos x = x ³ . Podemos reformularlo como encontrar el cero de f ( x ) = cos( x ) − x ³ . Tenemos f ′ ( x ) = −sin( x ) − 3 x ² . Dado que cos( x ) ≤ 1 para todo x y x ³ > 1 para x > 1 , sabemos que nuestra solución se encuentra entre 0 y 1.

Por ejemplo, con una estimación inicial x ₀ = 0,5 , la secuencia dada por el método de Newton 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 cercano a 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-3\times 0.5^{2}}}&=&1.112\,141\,637\,097\dots \\x_{2}&=&x_{1}-{\dfrac {f(x_{1})}{f'(x_{1})}}&=&\vdots &=&{\underline {0.}}909\,672\,693\,736\dots \\x_{3}&=&\vdots &=&\vdots &=&{\underline {0.86}}7\,263\,818\,209\dots \\x_{4}&=&\vdots &=&\vdots &=&{\underline {0.865\,47}}7\,135\,298\dots \\x_{5}&=&\vdots &=&\vdots &=&{\underline {0.865\,474\,033\,1}}11\dots \\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 ₆ es correcto con 12 decimales. Vemos que el número de dígitos correctos después del punto decimal aumenta de 2 (para x ₃ ) a 5 y 10, lo 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 fque tiene derivada f_prime.

La suposición inicial será x ₀ = 1 y la función será f ( x ) = x ² − 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ó

Ver también

• Proceso delta cuadrado de Aitken
• método de bisección
• método de euler
• Raíz cuadrada inversa rápida
• Puntuación de Fisher
• Descenso de gradiente
• raíz cuadrada entera
• teorema de Kantorovich
• El método de Laguerre.
• Métodos para calcular raíces cuadradas
• El método de Newton en optimización.
• extrapolación de Richardson
• Algoritmo de búsqueda de raíces
• método secante
• El método de Steffensen.
• Método de subgradiente

Notas

1. "Capítulo 2. Seki Takakazu". Matemáticas japonesas en el período Edo . Biblioteca Nacional de Dieta . Consultado el 24 de febrero de 2019 .
2. Wallis, Juan (1685). Tratado de álgebra, tanto histórica como práctica. Oxford: Richard Davis. doi : 10.3931/e-rara-8842.
3. Raphson, José (1697). Análisis Æequationum Universalis (en latín) (2ª ed.). Londres: Thomas Bradyll. doi : 10.3931/e-rara-13516.
4. "Métodos de Newton acelerados y modificados". Archivado desde el original el 24 de mayo de 2019 . Consultado el 4 de marzo de 2016 .
5. Ryaben'kii, Victor S.; Tsynkov, Semyon V. (2006), Introducción teórica al análisis numérico, CRC Press, pág. 243, ISBN 9781584886075.
6. Süli y Mayers 2003, ejercicio 1.6
7. Dence, Thomas (noviembre de 1997). "Cúbicas, caos y método de Newton". Gaceta Matemática . 81 (492): 403–408. doi :10.2307/3619617. JSTOR  3619617. S2CID  125196796.
8. Henrici, Peter (1974). "Análisis Complejo Aplicado y Computacional". 1 . {{cite journal}}: Citar diario requiere |journal=( ayuda )
9. Strang, Gilbert (enero de 1991). "Una búsqueda caótica de yo ". La revista universitaria de matemáticas . 22 (1): 3–12. doi :10.2307/2686733. JSTOR  2686733.
10. McMullen, Curt (1987). "Familias de mapas racionales y algoritmos iterativos de búsqueda de raíces" (PDF) . Anales de Matemáticas . Segunda Serie. 125 (3): 467–493. doi :10.2307/1971408. JSTOR  1971408.
11. Hubbard, Juan; Schleicher, Dierk; Sutherland, Scott (octubre de 2001). "Cómo encontrar todas las raíces de polinomios complejos mediante el método de Newton". Invenciones Mathematicae . 146 (1): 1–33. Código Bib : 2001 InMat.146....1H. doi :10.1007/s002220100149. ISSN  0020-9910. S2CID  12603806.
12. Yamamoto, Tetsuro (2001). "Desarrollos históricos en el análisis de convergencia de los métodos de Newton y similares a Newton". En Brezinski, C.; Wuytack, L. (eds.). Análisis numérico: desarrollos históricos en el siglo XX . Holanda del Norte. págs. 241–263. ISBN 0-444-50617-9.
13. Rajkovic, Stankovic y Marinkovic 2002 ^{[ cita breve incompleta ]} harvnb error: no target: CITEREFRajkovicStankovicMarinkovic2002 (help)
14. Prensa y col. 1992 ^{[ cita breve incompleta ]} harvnb error: no target: CITEREFPressTeukolskyVetterlingFlannery1992 (help)
15. Stoer & Bulirsch 1980 ^{[ cita breve incompleta ]} harvnb error: no target: CITEREFStoerBulirsch1980 (help)
16. Zhang y Jin 1996 ^{[ cita breve incompleta ]} harvnb error: no target: CITEREFZhangJin1996 (help)
17. Murota, Kazuo (1982). "Convergencia global de una iteración de Newton modificada para ecuaciones algebraicas". Revista SIAM de Análisis Numérico . 19 (4): 793–799. Código Bib : 1982SJNA...19..793M. doi :10.1137/0719055.
18. Moore, RE (1979). Métodos y aplicaciones del análisis de intervalos (Vol. 2). Siam.
19. Hansen, E. (1978). Formas de intervalo del método de Newton. Computación , 20 (2), 153–163.
20. Gil, Segura & Temme (2007) ^{[ cita breve incompleta ]}
21. Kahan  (1968) ^{[ cita breve incompleta ]}
22. Krawczyk (1969) ^{[ cita breve incompleta ] [ cita breve incompleta ]} harvtxt error: no target: CITEREFKrawczyk1969 (help)

Referencias

• Gil, A.; Segura, J.; Temme, Nuevo México (2007). Métodos numéricos para funciones especiales. Sociedad de Matemática Industrial y Aplicada. ISBN 978-0-89871-634-4.
• Süli, Endre ; Mayers, David (2003). Introducción al análisis numérico . Prensa de la Universidad de Cambridge. ISBN 0-521-00794-1.

Otras lecturas

• Kendall E. Atkinson, Introducción al análisis numérico , (1989) John Wiley & Sons, Inc, ISBN 0-471-62489-6 
• Tjalling J. Ypma, Desarrollo histórico del método Newton-Raphson, SIAM Review 37 (4), 531–551, 1995. doi :10.1137/1037125.
• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude ; Sagastizábal, Claudia A. (2006). Optimización numérica: Aspectos teóricos y prácticos. Universitext (Segunda edición revisada de la traducción de la edición francesa de 1997). Berlín: Springer-Verlag. págs. xiv+490. doi :10.1007/978-3-540-35447-5. ISBN 3-540-35445-X. SEÑOR  2265882.
• P. Deuflhard, Métodos de Newton para problemas no lineales. Invariancia afín y algoritmos adaptativos. Serie Springer en Matemática Computacional, vol. 35. Springer, Berlín, 2004. ISBN 3-540-21099-7 . 
• CT Kelley, Resolución de ecuaciones no lineales con el método de Newton , nº 1 en Fundamentos de algoritmos, SIAM, 2003. ISBN 0-89871-546-6 . 
• JM Ortega, WC Rheinboldt, Solución iterativa de ecuaciones no lineales en varias variables. Clásicos en Matemática Aplicada, SIAM, 2000. ISBN 0-89871-461-3 . 
• Prensa, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Capítulo 9. Búsqueda de raíces y muestreo de importancia de conjuntos no lineales de ecuaciones". Recetas numéricas: el arte de la informática científica (3ª ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8.. Véanse especialmente las Secciones 9.4, 9.6 y 9.7.
• Avriel, Mardoqueo (1976). Programación no lineal: análisis y métodos . Prentice Hall. págs. 216-221. ISBN 0-13-623603-0.

enlaces externos

• "Método de Newton", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Weisstein, Eric W. "El método de Newton". MundoMatemático .
• El método de Newton, Citizendium.
• Mathews, J., Los métodos de Newton acelerado y modificado, Notas del curso.
• Wu, X., Raíces de ecuaciones, Apuntes del curso.