stringtranslate.com

El método de Newton.

Una ilustración del método de Newton.

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

Ilustración del método de Newton.
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

Resolviendo para x n +1 se obtiene

Ilustración del método de Newton.
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 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 ) ≠ 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 PN = 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.

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.

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]

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

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 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 fC 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 α .

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

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:

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

donde M está dada por

Si estas condiciones se mantienen,

condiciones de fourier

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 se puede extender 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]

Ejemplos

Uso del método de Newton para calcular raíces cuadradas

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 2a . 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 ax 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 suave. 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.

Solución de cos( x ) = x 3 usando el método de Newton

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.

Por ejemplo, con una estimación inicial x 0 = 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):

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.

Convergencia lenta

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]

Convergencia dependiente de la inicialización

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á (super)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 .

Divergencia incluso cuando la inicialización está cerca de la raíz

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 + 1x 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 + 1x 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 + 1x n y f ( x n ) pueda identificar falsamente una raíz.

Comportamiento oscilatorio

Las rectas tangentes de x 3 − 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.

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.

Indefinición del método de Newton

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 intersecta al 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.

Formulaciones multidimensionales

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 ) . [15] [16] [17] Esto da como resultado la expresión

o, resolviendo el sistema de ecuaciones lineales

para la incógnita x n + 1x n . [18]

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 ) −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.

Ejemplo

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

Iteraciones

Las siguientes iteraciones se realizaron durante el transcurso de la solución.

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

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

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 . [24]

Iteración de Nash-Moser

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ícito 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 .

Modificaciones

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 .

El método de tercer orden de Chebyshev

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.

q -analógico

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

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: [28] [29]

Este método se aplica para obtener ceros de la función de Bessel de segundo tipo. [30]

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. [31] 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 ). [32] [33]

Considere fC 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 YX 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 metroY . 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.

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. [34] La iteración se convierte en:

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

Resolver ecuaciones trascendentales

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 .

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. [35] [36]

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

Ver también

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. 243, ISBN 9781584886075.
  6. ^ Süli y Mayers 2003, ejercicio 1.6
  7. ^ abc Ostrowski, AM (1973). Solución de ecuaciones en espacios euclidianos y de Banach . Matemática Pura y Aplicada. vol. 9 (Tercera edición de la edición original de 1960). Nueva York-Londres: Academic Press . Señor  0359306. Zbl  0304.65002.
  8. ^ Ortega y Rheinboldt, Sección 13.3
  9. ^ Traub, JF (1964). Métodos iterativos para la solución de ecuaciones . Serie Prentice-Hall en Computación Automática. Englewood Cliffs, Nueva Jersey: Prentice-Hall, Inc. MR  0169356. Zbl  0121.11204.
  10. ^ ab JE Dennis, Jr. y Robert B. Schnabel. Métodos numéricos para optimización sin restricciones y ecuaciones no lineales. SIAM
  11. ^ Anthony Ralston y Philip Rabinowitz. Un primer curso de análisis numérico, segunda edición.
  12. ^ Yuri Nésterov. Conferencias sobre optimización convexa, segunda edición. Optimización de Springer y sus aplicaciones, volumen 137.
  13. ^ Suli y Mayers 2003.
  14. ^ a b C Kenneth L. Judd. Métodos numéricos en economía. Prensa del MIT
  15. ^ ab Carga, Burton; Ferias, J. Douglas; Reunolds, Albert C (julio de 1981). Análisis numérico (2ª ed.). Boston, MA, Estados Unidos: Prindle, Weber & Schmidt. págs. 448 a 452. ISBN 0-87150-314-X.{{cite book}}: CS1 maint: date and year (link)
  16. ^ A. Evans, Gwynne (1995). Análisis numérico práctico. Baffins Lane, Chichester, West Suffix, DIU PO19, Inglaterra: John Wiley & Sons, Ltd. págs. 30 a 33. ISBN 0471955353.{{cite book}}: CS1 maint: location (link)
  17. ^ Demidovich, Boris Pavlovich; Marón, Isaac Abramovich (1981). Matemática Computacional (Tercera edición de impresión). Moscú: Editores MIR. págs. 460–478. ISBN 9780828507042.{{cite book}}: CS1 maint: date and year (link)
  18. ^ Kiusalaas, Jaan (marzo de 2013). Métodos numéricos en ingeniería con Python 3 (3ª ed.). Nueva York: Cambridge University Press. págs. 175-176. ISBN 978-1-107-03385-6.
  19. ^ Este ejemplo es similar al de la referencia [15] , páginas 451 y 452, pero simplificado a dos ecuaciones en lugar de tres.
  20. ^ Henrici, Peter (1974). "Análisis Complejo Aplicado y Computacional". 1 . {{cite journal}}: Citar diario requiere |journal=( ayuda )
  21. ^ 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.
  22. ^ 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.
  23. ^ 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.
  24. ^ 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.
  25. ^ Hamilton, Richard S. (1982). "El teorema de la función inversa de Nash y Moser". Boletín de la Sociedad Matemática Estadounidense . Series nuevas. 7 (1): 65–222. doi : 10.1090/s0273-0979-1982-15004-2 . SEÑOR  0656198. Zbl  0499.58003.
  26. ^ Gromov, Mikhael (1986). Relaciones diferenciales parciales . Ergebnisse der Mathematik und ihrer Grenzgebiete (3). vol. 9. Berlín: Springer-Verlag . doi :10.1007/978-3-662-02267-2. ISBN 3-540-12177-3. SEÑOR  0864505.
  27. ^ Rajkovic, Stankovic y Marinkovic 2002 [ cita breve incompleta ]
  28. ^ Prensa y col. 1992 [ cita breve incompleta ]
  29. ^ Stoer & Bulirsch 1980 [ cita breve incompleta ]
  30. ^ Zhang y Jin 1996 [ cita breve incompleta ]
  31. ^ 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.
  32. ^ Moore, RE (1979). Métodos y aplicaciones del análisis de intervalos (Vol. 2). Siam.
  33. ^ Hansen, E. (1978). Formas de intervalo del método de Newton. Computación , 20 (2), 153–163.
  34. ^ Boyd, Esteban ; Vandenberghe, Lieven (2004). Optimizacion convexa . Cambridge: Prensa de la Universidad de Cambridge . doi :10.1017/CBO9780511804441. ISBN 0-521-83378-7. SEÑOR  2061575. Zbl  1058.90049.
  35. ^ Kahan  (1968) [ cita breve incompleta ]
  36. ^ Krawczyk (1969) [ cita breve incompleta ] [ cita breve incompleta ]

Referencias

Otras lecturas

enlaces externos