Método de newton

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 25 de enero de 2022; las comprobaciones requieren 3 ediciones .

El método de Newton, el algoritmo de Newton (también conocido como el método de la tangente ) es un método numérico iterativo para encontrar la raíz ( cero ) de una función dada . El método fue propuesto por primera vez por el físico , matemático y astrónomo inglés Isaac Newton ( 1643-1727 ) . La búsqueda de una solución se realiza mediante la construcción de aproximaciones sucesivas y se basa en los principios de iteración simple . El método tiene convergencia cuadrática . Una modificación del método es el método de cuerdas y tangentes . Además, el método de Newton se puede utilizar para resolver problemas de optimización en los que se requiere determinar el cero de la primera derivada o gradiente en el caso de un espacio multidimensional.

Descripción del método

Justificación

Para resolver numéricamente la ecuación por el método de iteración simple , se debe reducir a una ecuación equivalente: , donde es el mapeo de contracción . $f(x)=0$ $x=\varfi(x)$ $\varphi$

Para la mejor convergencia del método en el punto de la próxima aproximación , la condición debe ser satisfecha . La solución de esta ecuación se busca en la forma , entonces: $x^{*}$ ${\displaystyle\varphi'(x^{*})=0}$ ${\ estilo de visualización \ varphi (x) = x + \ alfa (x) f (x)}$

\varphi '(x^{*})=1+\alpha '(x^{*})f(x^{*})+\alpha (x^{*})f'(x^{ *})=0.

Suponiendo que el punto de aproximación está "lo suficientemente cerca" de la raíz y que la función dada es continua , la fórmula final para es: ${\ tilde {x}}$ $(f(x^{*})\approx f({\tilde {x)))=0)$ $\alfa(x)$

\alpha (x)=-{\frac {1}{f'(x))).

Con esto en mente, la función se define: $\varfi(x)$

\varphi (x)=x-{\frac {f(x)}{f'(x))).

Bajo ciertas condiciones, esta función realiza un mapeo de contracción en una vecindad de la raíz.

Prueba

Sea dada una función de variable real que sea dos veces continuamente diferenciable en su dominio de definición y cuya derivada nunca se anule:

\scriptstyle {f(x)\colon {\mathbb {X}}\to \mathbb{R} ,\;f(x)\in {\mathrm {C}}^{2}({\mathbb {X} });\quad \forall x\in {\mathbb {X}}\;f'(x)\neq 0.}

Y es necesario probar que la función realiza un mapeo de contracción cerca de la raíz de la ecuación . $\scriptstyle {\varphi (x)=x-{\frac {f(x)}{f'(x)))}$ $\scriptstyle {f(x)=0}$

Debido a la diferenciabilidad continua de la función y la desigualdad de cero, su primera derivada es continua . $\scriptstyle {f(x)}$ $\scriptstyle {\varphi (x)}$

la derivada es: $\scriptstyle {\varphi '(x)}$

\scriptstyle {\varphi '(x)={\frac {f(x)f''(x)}{\left(f'(x)\right)^{2))}.}

Bajo las condiciones impuestas a , también es continuo. Sea la raíz buscada de la ecuación: , por lo tanto, en su vecindad : $\scriptstyle {f(x)}$ $\scriptstyle {{\tilde {x}}}$ $\scriptstyle {f({\tilde {x)))=0}$ $\scriptstyle {\varphi '(x)\aproximadamente 0}$

\scriptstyle {\forall \varepsilon \colon 0<\varepsilon <1,\;\exists \delta >0\;\forall x\in {\mathbb {X}}\;|x-{\tilde {x}} |<\delta \colon |\varphi '(x)-0|<\varepsilon .}

Entonces, según el teorema de Lagrange :

\scriptstyle {\forall x_{1},\;x_{2}\in {\mathrm {U}}_{\delta }({\tilde {x)))\;\existe \xi \in {\mathrm {U}}_{\delta }({\tilde {x}})\colon |\varphi (x_{1})-\varphi (x_{2})|=|\varphi '(\xi )|| x_{1}-x_{2}|<\varepsilon |x_{1}-x_{2}|.}

Debido al hecho de que en el mismo barrio del delta, lo siguiente es cierto: $\scriptstyle {\varphi ({\tilde {x)))={\tilde {x}}}$

\scriptstyle {\forall x\in U_{{\delta }}({\tilde {x}})\colon \;|\varphi (x)-{\tilde {x}}|<\varepsilon |x-{ \tilde{x}}|.}

La función así obtenida en la vecindad de la raíz implementa un mapeo de contracción . ■ $\scriptstyle {\varphi (x)}$ $\scriptstyle {U_{\delta }({\tilde {x)))}$

En este caso, el algoritmo para encontrar una solución numérica a la ecuación se reduce a un procedimiento de cálculo iterativo : $f(x)=0$

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

Según el teorema de Banach , la secuencia de aproximaciones tiende a la raíz de la ecuación . $f(x)=0$

Interpretación geométrica

La idea principal del método es la siguiente: la aproximación inicial se establece cerca de la raíz hipotética, luego de lo cual se traza una tangente a la gráfica de la función en estudio en el punto de aproximación, para lo cual la intersección con el eje de abscisas es fundar. Este punto se toma como la siguiente aproximación. Y así sucesivamente, hasta alcanzar la precisión requerida.

Sea 1) una función de valor real continuamente diferenciable en el intervalo ; 2) hay un punto requerido : ; 3) también hay tales que por y para ; 4) el punto es tal que . Entonces , la fórmula para la aproximación iterativa a k se puede derivar del significado geométrico de la tangente de la siguiente manera: $f(x)\colon (a,\,b)\to \mathbb {R}$ ${\ estilo de visualización (a, \, b)}$
${\ estilo de visualización x ^ {*} \ en (a, \, b)}$ ${\ estilo de visualización f (x ^ {*}) = 0}$
$C > 0$ $\delta>0$
${\ estilo de visualización \ vert f'(x) \ vert \ geqslant C}$ $x\in (a,\,x^{*}-\delta ]\cup [x^{*}+\delta ,\,b)$
$f'(x)\neq 0$ $x\in (x^{*}-\delta ,\,x^{*})\cup (x^{*},\,x^{*}+\delta )$
${\ Displaystyle x_ {n} \ en (a, \, b)}$ ${\ Displaystyle f (x_ {n}) \ neq 0}$
$x_{n}$ $x^{{*}}$

f'(x_{n})=\mathrm {tg} \,\alpha _{n}={\frac {\Delta y}{\Delta x))={\frac {f(x_{n })-0}{x_{n}-x_{n+1}}}={\frac{0-f(x_{n})}{x_{n+1}-x_{n}}},

donde es el ángulo de inclinación de la recta tangente a la gráfica en el punto . ${\ estilo de visualización \ alfa _ {n}}$ ${\displaystyle y(x)=f(x_{n})+(x-x_{n})\cdot \mathrm {tg} \,\alpha _{n))$ $F$ ${\ estilo de visualización (x_ {n}; f (x_ {n}))}$

Por tanto (en la ecuación de la recta tangente suponemos ) la expresión deseada para tiene la forma: ${\ estilo de visualización y (x_ {n + 1}) = 0}$ $x_{{n+1}}$

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

Si , entonces este valor puede usarse como la siguiente aproximación a . ${\ estilo de visualización x_ {n + 1} \ en (a, \, b)}$ $x^{{*}}$

Si , entonces hay un “vuelo” (la raíz se encuentra cerca del límite ). En este caso, es necesario (usando la idea del método de bisección ) reemplazar con hasta que el punto "retorne" al área de búsqueda . $x_{n+1}\notin (a,\,b)$ $x^{{*}}$ ${\ estilo de visualización (a, \, b)}$ $x_{{n+1}}$ ${\frac{x_{n}+x_{n+1}}{2}}$ ${\ estilo de visualización (a, \, b)}$

Comentarios. 1) La presencia de una derivada continua permite construir una tangente que cambia continuamente en toda el área de la búsqueda de una solución . 2) Los casos de ubicación límite (en un punto o en un punto ) de la solución deseada se consideran de manera similar. 3) Desde un punto de vista geométrico, la igualdad significa que la recta tangente a la gráfica en el punto - es paralela al eje y no lo corta al final. 4) Cuanto mayor sea la constante y menor la constante del párrafo 3 de las condiciones, más cerca estará la intersección de la tangente a la gráfica y el eje al punto , es decir, más cerca será el valor del deseado . ${\ estilo de visualización (a, \, b) \;}$
$a$ $b$ $x^{{*}}$
$f'(x_{n})=0$ $F$ ${\ estilo de visualización (x_ {n}; f (x_ {n}))}$ $BUEY$ ${\ Displaystyle f (x_ {n}) \ neq 0}$
$C > 0$ $\delta>0$ $x_{n}\in (a,\,x^{*}-\delta ]\cup [x^{*}+\delta ,\,b)$ $F$ $BUEY$ ${\ estilo de visualización (x^{*};\;0)}$ $x_{{n+1}}$ ${\ estilo de visualización x ^ {*} \ en (a, \, b)}$

El proceso iterativo comienza con alguna aproximación inicial , y entre y el punto deseado no debe haber otros ceros de la función , es decir, “cuanto más cerca de la raíz deseada , mejor”. Si no hay suposiciones sobre el hallazgo , la prueba y el error pueden reducir el rango de valores posibles aplicando el teorema del valor intermedio . $x_{0}\en (a,\,b)$ $x_{0}\en (a,\,b)$ ${\ estilo de visualización x ^ {*} \ en (a, \, b)}$ $F$ $x_{0}$ $x^{{*}}$ $x^{{*}}$

Para predefinido , el proceso iterativo finaliza si y . En particular, para la matriz de visualización y puede calcularse en función de la escala de visualización del gráfico , es decir, si y cae en una fila vertical y en una horizontal. ${\ estilo de visualización \ varepsilon _ {x}> 0}$ ${\ estilo de visualización \ varepsilon _ {f}> 0}$ $\left\vert {\frac {f(x_{n})}{f'(x_{n))}}\right\vert \approx \vert x_{n+1}-x_{n}\ vert<\varepsilon_{x}$ ${\displaystyle \vert f(x_{n+1})\vert </varepsilon _{f))$
${\ estilo de visualización \ varepsilon _ {x}}$ ${\ estilo de visualización \ varepsilon _ {f}}$ $F$ $x_{n}$ $x_{{n+1}}$ ${\ estilo de visualización f (x_ {n})}$ ${\ estilo de visualización f (x_ {n + 1})}$

Algoritmo

Se establece la aproximación inicial . $x_{0}$
Hasta que se cumpla la condición de parada, que puede tomarse como o (es decir, el error está dentro de los límites requeridos), se calcula una nueva aproximación: . $|x_{n+1}-x_{n}|<\varepsilon$ ${\ estilo de visualización | f (x_ {n + 1}) | <\ varepsilon}$ $x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n))}}$

Ejemplo

Considere el problema de encontrar positivo , para lo cual . Esta tarea se puede representar como la tarea de encontrar el cero de la función . Tenemos una expresión para la derivada . Como para todos y para , es obvio que la solución se encuentra entre 0 y 1. Tomemos el valor como una aproximación inicial , entonces: $X$ $\cos x=x^{3}$ $f(x)=\cos xx^{3}$ $f'(x)=-\sen x-3x^{2}$ $\cos x\leqslant 1$ $X$ $x^{3}>1$ $x>1$ $x_{0}=0{,}5$

{\begin{matriz}x_{1}&=&x_{0}-{\dfrac {f(x_{0})}{f'(x_{0})))&=&1{,}112\;141 \;637\;097,\\x_{2}&=&x_{1}-{\dfrac {f(x_{1})}{f'(x_{1})))&=&\subrayar {0 {,}}909\;672\;693\;736,\\x_{3}&=&x_{2}-{\dfrac {f(x_{2})}{f'(x_{2})} }&=&\subrayado {0{,}86}7\;263\;818\;209,\\x_{4}&=&x_{3}-{\dfrac {f(x_{3})}{ f'(x_{3})}}&=&\subrayado {0{,}865\;47}7\;135\;298,\\x_{5}&=&x_{4}-{\dfrac { f(x_{4})}{f'(x_{4})}}&=&\subrayado {0{,}865\;474\;033\;1}11,\\x_{6}&= &x_{5}-{\dfrac {f(x_{5})}{f'(x_{5})}}&=&\subrayado {0{,}865\;474\;033\;102}. \end{matriz}}

Los dígitos significativos válidos están subrayados . Se puede ver que su número aumenta de paso a paso (aproximadamente duplicándose con cada paso): de 1 a 2, de 2 a 5, de 5 a 10, lo que ilustra la tasa de convergencia cuadrática .

Condiciones de uso

Consideremos una serie de ejemplos que señalan las deficiencias del método.

Contraejemplos

Si la aproximación inicial no está lo suficientemente cerca de la solución, es posible que el método no converja.

Dejar

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

Después

x_{{n+1}}=x_{{n}}-{\frac {x_{n}^{3}-2x_{n}+2}{3x_{n}^{2}-2}}.

Tomemos cero como una aproximación inicial. La primera iteración dará la unidad como una aproximación. A su vez, el segundo volverá a dar cero. El método se repetirá y no se encontrará ninguna solución. En general, la construcción de una secuencia de aproximaciones puede resultar muy confusa .

Si la derivada no es continua en el punto de la raíz, entonces el método puede divergir en cualquier vecindad de la raíz.

Considere una función:

f(x)={\begin{cases}0,&x=0,\\x+x^{2}\sin \left({\dfrac {2}{x}}\right),&x\ neq 0.\end{casos}}

Entonces y en todas partes excepto 0. ${\ estilo de visualización f' (0) = 1}$ $f'(x)=1+2x\sin(2/x)-2\cos(2/x)$

En las proximidades de la raíz, la derivada cambia de signo cuando se acerca a cero por la derecha o por la izquierda. mientras que para . $X$ $f(x)\geqslantxx^{2}>0$ ${\ estilo de visualización 0 <x <1}$

Por lo tanto, no está acotada cerca de la raíz y el método diverge, aunque la función es diferenciable en todas partes, su derivada es distinta de cero en la raíz, infinitamente diferenciable en todas partes excepto en la raíz, y su derivada está acotada alrededor de la raíz. . ${\ estilo de visualización f (x)/f' (x)}$ $F$

Si no hay una segunda derivada en el punto raíz, entonces la tasa de convergencia del método puede reducirse notablemente.

Considere un ejemplo:

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

Entonces y excepto donde no está definido. ${\displaystyle f'(x)=1+(4/3)x^{1/3))$ ${\ estilo de visualización f''(x)=(4/9)x^{-2/3))$ $x=0$

En el siguiente paso, tenemos : $x_{n}$

x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n))}}={\frac {(1/3)x_{ n}^{4/3}}{(1+(4/3)x_{n}^{1/3})}}.

La tasa de convergencia de la secuencia resultante es de aproximadamente 4/3. Esto es significativamente menor que 2, lo cual es necesario para la convergencia cuadrática, por lo que en este caso solo podemos hablar de convergencia lineal, aunque la función es continuamente diferenciable en todas partes , la derivada en la raíz no es igual a cero y es infinitamente diferenciable en todas partes . excepto en la raíz. $F$

Si la derivada en el punto raíz es igual a cero, entonces la tasa de convergencia no será cuadrática y el método en sí puede terminar la búsqueda prematuramente y dar una aproximación incorrecta para una precisión dada.

Dejar

{\ estilo de visualización f (x) = x ^ {2}.}

Entonces y por lo tanto . Así, la convergencia del método no es cuadrática, sino lineal, aunque la función es infinitamente diferenciable en todas partes. ${\ estilo de visualización f' (x) = 2x}$ ${\ estilo de visualización xf(x)/f'(x)=x/2}$

Restricciones

Sea dada la ecuación , donde y es necesario encontrar su solución. $f(x)=0$ $f(x)\colon \mathbb {X} \to \mathbb {R}$

A continuación se presenta la formulación del teorema principal, que nos permite dar condiciones claras de aplicabilidad. Lleva el nombre del matemático y economista soviético Leonid Vitalievich Kantorovich ( 1912-1986 ) .

El teorema de Kantorovich.

Si existen constantes tales que: $A B C$

${\frac{1}{|f'(x)|}}<A$ on , es decir, existe y no es igual a cero; $[a,\;b]$ $f'(x)$
$\left|{\frac {f(x)}{f'(x)}}\right|<B$ en , es decir, limitado; $[a,\;b]$ $f(x)$
$\existe f''(x)$ en , y ; $[a,\;b]$ $|f''(x)|\leqslant C\leqslant {\frac {1}{2AB))$

Además, la longitud del segmento considerado . Entonces las siguientes afirmaciones son verdaderas: $|ab|<{\frac {1}{AB}}\left(1-{\sqrt {1-2ABC}}\right)$

existe una raíz de la ecuación ; $[a,\;b]$ $x^{*}$ $f(x)=0\dos puntos \existe x^{*}\en [a,\;b]\dos puntos f(x^{*})=0$
si , entonces la secuencia iterativa converge a esta raíz: ; $x_{0}={\frac{a+b}{2))$ $\left\{x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})))\right\}\to x^ {*}$
el error se puede estimar mediante la fórmula . $|x^{*}-x_{n}|\leqslant {\frac {B}{2^{n-1}}}(2ABC)^{2^{n-1}}$

Del último enunciado del teorema, en particular, se sigue la convergencia cuadrática del método:

|x^{*}-x_{n}|\leqslant {\frac {B}{2^{n-1}}}(2ABC)^{2^{n-1}}={\frac {1}{2}}{\frac {B}{2^{n-2}}}\left((2ABC)^{2^{n-2}}\right)^{2}=\alpha | x^{*}-x_{n-1}|^{2}.

Entonces las restricciones en la función original se verán así: $f(x)$

la función debe ser limitada;
la función debe ser suave , dos veces diferenciable ;
su primera derivada está uniformemente separada de cero; $f'(x)$
su segunda derivada debe estar uniformemente acotada. $f''(x)$

Antecedentes históricos

El método fue descrito por Isaac Newton en el manuscrito On the Analysis by Equations of Infinite Series ( en latín: De analysi per aequationes numero terminorum infinitas ) dirigido a Barrow en 1669 , y en The Method of Fluxions and Infinite Series ( en latín: De metodis fluxionum et serierum infinitarum" ) o " Geometría analítica " ( del lat. "Geometria analytica" ) en las colecciones de las obras de Newton, que fue escrita en 1671 . En sus escritos, Newton introduce conceptos como la expansión de una función en una serie , infinitesimales y fluxiones ( derivadas en el sentido actual). Estas obras se publicaron mucho más tarde: la primera se publicó en 1711 gracias a William Johnson, la segunda fue publicada por John Colzon en 1736 tras la muerte del creador. Sin embargo, la descripción del método difería significativamente de su exposición actual: Newton aplicó su método exclusivamente a polinomios . No calculó aproximaciones sucesivas , sino una secuencia de polinomios y como resultado recibió una solución aproximada . $x_{n}$ $X$

El método fue publicado por primera vez en el tratado "Álgebra" de John Wallis en 1685, a cuyo pedido el mismo Newton lo describió brevemente. En 1690, Joseph Raphson publicó una descripción simplificada en su "Analysis aequationum universalis" ( en latín: "Analysis aequationum universalis" ). Raphson vio el método de Newton como puramente algebraico y limitó su aplicación a polinomios, pero describió el método en términos de aproximaciones sucesivas en lugar de la secuencia de polinomios más difícil de entender utilizada por Newton. Finalmente, en 1740, Thomas Simpson describió el método de Newton como un método iterativo de primer orden para resolver ecuaciones no lineales usando una derivada, como se presenta aquí. En la misma publicación, Simpson generalizó el método al caso de un sistema de dos ecuaciones y señaló que el método de Newton también se puede aplicar a problemas de optimización al encontrar el cero de la derivada o gradiente . $x_{n}$

En 1879, Arthur Cayley , en El problema imaginario de Newton-Fourier, fue el primero en señalar las dificultades de generalizar el método de Newton al caso de raíces imaginarias de polinomios de grado superior al segundo y aproximaciones iniciales complejas. Este trabajo allanó el camino para el estudio de la teoría fractal .

Generalizaciones y modificaciones

El método de la secante

El método de la secante relacionado es el método "aproximado" de Newton y evita calcular la derivada. El valor de la derivada en la fórmula iterativa se reemplaza por su estimación para los dos puntos de iteración anteriores:

${\displaystyle f'(x_{n})\approx {\frac {f(x_{n})-f(x_{n-1})}{x_{n}-x_{n-1))))$ .

Por lo tanto, la fórmula principal tiene la forma

x_{n+1}=x_{n}-f(x_{n})\cdot {\frac {x_{n}-x_{n-1}}{f(x_{n})-f (x_{n-1})}}.

Este método es similar al de Newton, pero tiene una tasa de convergencia ligeramente más lenta. El orden de convergencia del método es igual a la proporción áurea - 1.618 ...

Comentarios. 1) Para iniciar el proceso iterativo se requieren dos valores diferentes de y . 2) En contraste con el “método de Newton real” (el método de la tangente), que requiere almacenar solo (y temporalmente durante los cálculos y ), el método de la secante requiere guardar , , , . 3) Se utiliza si el cálculo es difícil (por ejemplo, requiere una gran cantidad de recursos de la máquina: tiempo y/o memoria). $x_{0}$ $x_{1}$
${\ estilo de visualización x_ {n}}$ ${\ estilo de visualización f (x_ {n})}$ $f'(x_{n})$ ${\ Displaystyle x_ {n-1}}$ ${\ estilo de visualización x_ {n}}$ ${\ estilo de visualización f (x_ {n-1})}$ ${\ estilo de visualización f (x_ {n})}$
$f'(x)$

Método de una tangente

Para reducir el número de llamadas a los valores de la derivada de una función, se utiliza el llamado método de una tangente.

La fórmula de iteración para este método es:

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

La esencia del método es calcular la derivada solo una vez, en el punto de aproximación inicial , y luego usar este valor en cada iteración subsiguiente: $x_{0}$

\alpha (x)=\alpha _{0}=-{\dfrac {1}{f'(x_{0}))).

Con esta elección , se cumple la siguiente igualdad en el punto : $\alpha _{0}$ $x_{0}$

\varphi '(x_{0})=1+\alpha _{0}f'(x_{0})=0,

y si el segmento en el que se supone la presencia de una raíz y se elige la aproximación inicial es lo suficientemente pequeño, y la derivada es continua, entonces el valor no diferirá mucho de y, por lo tanto, la gráfica pasará casi horizontalmente, cortando la recta , que a su vez asegurará una rápida convergencia de la secuencia de puntos de aproximación a la raíz. $x^{*}$ $x_{0}$ ${\ estilo de visualización \ varphi '(x)}$ ${\ estilo de visualización \ varphi '(x^{*})}$ ${\ estilo de visualización \ varphi '(x_{0}) = 0}$ ${\ estilo de visualización y = \ varphi (x)}$ $y=x$

Este método es un caso especial del método de iteración simple . Tiene un orden lineal de convergencia.

Caso multidimensional

Generalicemos el resultado obtenido al caso multidimensional.

Sea necesario encontrar una solución al sistema:

\left\{{\begin{matriz}{lcr}f_{1}(x_{1},\;x_{2},\;\ldots,\;x_{n})&=&0,\ \\ldots &&\\f_{m}(x_{1},\;x_{2},\;\ldots,\;x_{n})&=&0.\end{matriz}}\right.

Eligiendo algún valor inicial , se obtienen aproximaciones sucesivas resolviendo sistemas de ecuaciones : ${\vec{x}}^{[0]}$ ${\vec{x}}^{[j+1]}$

f_{i}+\sum _{k=1}^{n}{\frac {\parcial f_{i}}{\parcial x_{k}}}(x_{k}^{[j+ 1 ]}-x_{k}^{[j]})=0,\qquad i=1,\;2,\;\ldots,\;m,

donde _ ${\vec {x}}^{[j]}=(x_{1}^{[j]},\;x_{2}^{[j]},\;\ldots,\;x_ {n}^{[j]}),\quad j=0,\;1,\;2,\;\ldots$

Aplicado a problemas de optimización

Sea necesario encontrar el mínimo de una función de varias variables . Esta tarea es equivalente al problema de encontrar el cero del gradiente . Apliquemos el método de Newton anterior: $f({\vec {x}})\colon \mathbb {R} ^{n}\to \mathbb {R}$ $\nabla f({\vec {x)))$

\nabla f({\vec {x}}^{[j]})+H({\vec {x}}^{[j]})({\vec {x}}^{[j +1]}-{\vec {x}}^{[j]})=0,\quad j=1,\;2,\;\ldots,\;n,

donde es el hessiano de la función . $H({\vec{x)))$ $f({\vec {x)))$

En una forma iterativa más conveniente, esta expresión se ve así:

{\vec {x}}^{[j+1]}={\vec {x}}^{[j]}-H^{-1}({\vec {x}}^{[ j]})\nabla f({\vec {x}}^{[j]}).

Cabe señalar que en el caso de una función cuadrática, el método de Newton encuentra un extremo en una iteración.

Encontrar la matriz hessiana es computacionalmente costoso y, a menudo, no es posible. En tales casos, los métodos cuasi-newtonianos pueden servir como una alternativa , en los que se construye una aproximación de la matriz hessiana en el proceso de acumulación de información sobre la curvatura de la función.

Método de Newton-Raphson

El método de Newton-Raphson es una mejora del método extremum de Newton descrito anteriormente. La principal diferencia es que en la siguiente iteración, uno de los métodos de optimización unidimensional selecciona el paso óptimo:

{\vec {x}}^{[j+1]}={\vec {x}}^{[j]}-\lambda _{j}H^{-1}({\vec { x}}^{[j]})\nabla f({\vec {x}}^{[j]}),

donde Para optimizar los cálculos, se utiliza la siguiente mejora: en lugar de recalcular la hessiana de la función objetivo en cada iteración , nos restringimos a la aproximación inicial y la actualizamos solo una vez por pasos, o no la actualizamos en absoluto. $\lambda_{j}=\arg \min_{\lambda}f({\vec {x}}^{[j]}-\lambda H^{-1}({\vec {x} }^{[j]})\nabla f({\vec {x}}^{[j]})).$ $H(f({\vec {x))^{[0]}))$ $metro$

Aplicado a problemas de mínimos cuadrados

En la práctica, a menudo hay tareas en las que se requiere ajustar los parámetros libres de un objeto o ajustar el modelo matemático a datos reales. En estos casos, aparecen problemas de mínimos cuadrados :

F({\vec {x)))=\|{\vec {f}}({\vec {x}})\|=\sum_{{i=1}}^{m}f_{i} ^{2}({\vec {x}})=\sum_{{i=1}}^{m}(\varphi_{i}({\vec {x}})-{\mathcal {F }}_{i})^{2}\to\min .

Estos problemas se distinguen por un tipo especial de gradiente y matriz hessiana :

\nabla F({\vec {x)))=2J^{T}({\vec {x))){\vec {f}}({\vec {x}}),

H({\vec {x)))=2J^{T}({\vec {x)))J({\vec {x)))+2Q({\vec {x))),\qquad Q ({\vec {x)))=\sum_{{i=1}}^{m}f_{i}({\vec {x}})H_{i}({\vec {x}}) ,

donde es la matriz de Jacobi de la función vectorial , es la matriz hessiana de su componente . $J({\vec{x)))$ ${\ vec {f)} ({\ vec {x)})$ $H_{i}({\vec {x)))$ $f_{i}({\vec {x)))$

Luego, el siguiente paso se determina a partir del sistema: ${\ vec {p}}$

\left[J^{T}({\vec {x}})J({\vec {x}})+\sum _{{i=1}}^{m}f_{i}({\vec {x)))H_{i}({\vec {x)))\right]{\vec {p}}=-J^{T}({\vec {x}}){\vec {f} }({\vec {x}}).

Método de Gauss-Newton

El método de Gauss-Newton se basa en la suposición de que el término domina sobre . Este requisito no se cumple si los residuos mínimos son grandes, es decir, si la norma es comparable al valor propio máximo de la matriz . De lo contrario, puedes escribir: $J^{T}({\vec {x)))J({\vec {x)))$ $Q({\vec{x)))$ $\|{\vec {f}}({\vec {x}})\|$ $J^{T}({\vec {x)))J({\vec {x)))$

J^{T}({\vec {x}})J({\vec {x}}){\vec {p}}=-J^{T}({\vec {x}}){\vec {f}}({\ vec {x}}).

Así, cuando la norma es cercana a cero, y la matriz tiene rango de columna completo , el paso difiere poco del newtoniano (teniendo en cuenta ), y el método puede alcanzar una tasa de convergencia cuadrática, aunque no se toman en cuenta las segundas derivadas. cuenta. Una mejora del método es el algoritmo de Levenberg-Marquardt basado en consideraciones heurísticas . $\|Q({\vec {x)))\|$ $J({\vec{x)))$ ${\ vec {p}}$ $Q({\vec{x)))$

Generalización al plano complejo

Hasta ahora, en la descripción del método se utilizaban funciones que realizan mapeos dentro del conjunto de valores reales . Sin embargo, el método también se puede aplicar para encontrar el cero de una función de una variable compleja . Sin embargo, el procedimiento sigue siendo el mismo:

z_{n+1}=z_{n}-{\frac {f(z_{n})}{f'(z_{n))))).

De particular interés es la elección de la aproximación inicial . En vista del hecho de que una función puede tener varios ceros, en diferentes casos el método puede converger a diferentes valores, y es bastante natural querer averiguar qué áreas asegurarán la convergencia a una raíz particular. Esta pregunta interesó a Arthur Cayley allá por 1879 , pero solo fue posible resolverla en los años 70 del siglo XX con la llegada de la tecnología informática. Resultó que en las intersecciones de estas regiones (que generalmente se llaman regiones de atracción ), se forman los llamados fractales : infinitas figuras geométricas autosimilares. $z_{0}$

Debido al hecho de que Newton aplicó su método exclusivamente a polinomios , los fractales formados como resultado de dicha aplicación se conocieron como fractales de Newton o piscinas de Newton .

Implementación

escala

objeto NewtonMethod { precisión de valor = 1e -6 método @tailrec def ( x0 : Doble , f : Doble => Doble , dfdx : Doble => Doble , e : Doble ): Doble = { val x1 = x0 - f ( x0 ) / dfdx ( x0 ) if ( abs ( x1 - x0 ) < e ) x1 otro método ( x1 , f , dfdx , e ) } def g ( C : Doble ) = ( x : Doble ) => x * x - C def dgdx ( x : Doble ) = 2 * x def sqrt ( x : doble ) = x partido { caso 0 => 0 caso x si ( x < 0 ) => doble . NaN case x if ( x > 0 ) => método ( x / 2 , g ( x ), dgdx , precision ) } }

Pitón

from math import sin , cos de tipear import Callable import unittest def newton ( f : Invocable [[ float ], float ], f_prime : Invocable [[ float ], float ], x0 : float , eps : float = 1e-7 , kmax : int = 1e3 ) -> float : """ resuelve f(x) = 0 por el método de Newton con precisión eps :param f: f :param f_prime: f' :param x0: punto de partida :param eps: precisión buscada :return: raíz de f(x) = 0 """ x , x_prev , i = x0 , x0 + 2 * eps , 0 while abs ( x - x_prev ) >= eps y i < kmax : x , x_prev , i = x - f ( x ) / f_prime ( x ), x , i + 1 volver x clase TestNewton ( unittest . TestCase ): def test_0 ( self ): def f ( x : float ) -> float : return x ** 2 - 20 * sin ( x ) def f_prime ( x : float ) -> float : return 2 * x - 20 * cos ( x ) x0 , x_estrella = 2 , 2.7529466338187049383 uno mismo afirmar Casi Igual ( newton ( f , f_prime , x0 ), x_star ) if __name__ == '__main__' : unittest . principal ()

PHP

<?php // Función PHP 5.4 newtons_method ( $a = - 1 , $b = 1 , $f = función ( $x ) { volver pow ( $x , 4 ) - 1 ; }, $derivada_f = función ( $x ) { devuelve 4 * pow ( $x , 3 ); }, $eps = 1E-3 ) { $xa = $a ; $xb = $b ; $iteración = 0 ; while ( abs ( $xb ) > $eps ) { $p1 = $f ( $xa ); $q1 = $derivada_f ( $xa ); $xa -= $p1 / $q1 ; $xb = $p1 ; ++ $iteración ; } devolver $xa ; }

Octava

funcion res = nt () eps = 1e-7 ; x0_1 = [ - 0.5 , 0.5 ]; max_iter = 500 ; xopt = nuevo (@ resh , eps , max_iter ); función de función final xopt a = nuevo ( f, eps, max_iter ) x = - 1 ; p0 = 1 ; yo = 0 _ while ( abs ( p0 ) > = eps ) [ p1 , q1 ]= f ( x ); x = x - p1 / q1 ; p0 = p1 ; yo = yo + 1 ; fin i a = x ; función función final [p,q] = resh ( x ) % p= -5*x.^5+4*x.^4-12*x.^3+11*x.^2-2*x+1; p = - 25 * x .^ 4 + 16 * x .^ 3 - 36 * x .^ 2 + 22 * x - 2 ; q = - 100 * x .^ 3 + 48 * x .^ 2 - 72 * x + 22 ; función final

Delfos

// función calculada función fx ( x : Doble ) : Doble ; comenzar Resultado := x * x - 17 ; fin ; // función derivada de f(x) function dfx ( x : Double ) : Double ; comenzar Resultado := 2 * x ; fin ; función resolver ( fx , dfx : TFunc < Double , Double > ; x0 : Double ) : Double ; constante eps = 0.000001 ; var x1 : Doble ; comenzar x1 := x0 - fx ( x0 ) / dfx ( x0 ) ; // primera aproximación while ( Abs ( x1 - x0 ) > eps ) do begin // hasta alcanzar la precisión 0.000001 x0 := x1 ; x1 := x1 - fx ( x1 ) / dfx ( x1 ) ; // terminan las aproximaciones posteriores ; Resultado := x1 ; fin ; // Llamar a resolver ( fx , dfx , 4 ) ;

C++

#incluir <iostream> #incluir <matemáticas.h> double fx ( double x ) { return x * x - 17 ;} // función calculada double dfx ( double x ) { return 2 * x ;} // función derivada typedef doble ( * función )( doble x ); // asignación de función de tipo resolver doble ( función fx , función dfx , doble x0 , doble eps = 1e-8 ) { doble xi = x0 ; //Punto actual en la i-ésima iteración while ( fabs ( fx ( xi )) >= eps ) // hasta que se alcanza la precisión 0.00000001 xi = xi - fx ( xi ) / dfx ( xi ); // aproximaciones posteriores devuelven xi ; } int principal () { std :: cout << resolver ( fx , dfx , 4 ) << std :: endl ; devolver 0 ; }

C

typedef doble ( * función )( doble x ); método tangente doble ( función f , función df , doble xn , doble eps ) { doble x1 = xn - f ( xn ) / df ( xn ); doble x0 = xn ; mientras ( abs ( x0 - x1 ) > eps ) { x0 = x1 ; x1 = x1 - f ( x1 ) / gl ( x1 ); } devolver x1 ; } //Seleccione el cálculo inicial xn = MyFunction ( A ) * My2Derivative ( A ) > 0 ? B : A ; double MyFunction ( double x ) { return ( pow ( x , 5 ) - x - 0.2 ); } //Su función double MyDerivative ( double x ) { return ( 5 * pow ( x , 4 ) - 1 ); } //Primera derivada double My2Derivative ( double x ) { return ( 20 * pow ( x , 3 )); } //Segunda derivada //Ejemplo de llamada a una función double x = TangentsMethod ( MyFunction , MyDerivative , xn , 0.1 )

Haskell

importar Data.List ( iterar' ) principal :: IO () principal = imprimir $ resolver ( \ x -> x * x - 17 ) ( * 2 ) 4 -- La función de resolución es universal para todos los tipos reales cuyos valores se pueden comparar. resolver = resolver 0.000001 resolver epsilon func deriv x0 = fst . head $ dropWhile pred pares donde pred ( xn , xn1 ) = ( abs $ xn - xn1 ) > epsilon -- La función pred determina si se ha logrado la precisión requerida. next xn = xn - func xn / deriv xn -- La siguiente función calcula una nueva aproximación. iters = iterate' next x0 -- Una lista infinita de iteraciones. pairs = zip iters ( tail iters ) -- Una lista infinita de pares de iteraciones de la forma: [(x0, x1), (x1, x2) ..].

Literatura

Akulich I. L. Programación matemática en ejemplos y tareas: Proc. Subsidio para la economía de los estudiantes. especialista. universidades - M. : Escuela Superior, 1986. - 319 p. : enfermo. -BBK 22.1 A44 . - CDU 517.8 .
Amosov A. A., Dubinsky Yu. A., Kopchenova N. P. Métodos computacionales para ingenieros: Proc. tolerancia. - M. : Escuela superior, 1994. - 544 p. : enfermo. -BBK 32,97 A62 . - CDU 683.1 . — ISBN 5-06-000625-5 .
Bakhvalov N. S., Zhidkov N. P. , Kobelkov G. G. Métodos numéricos. - 8ª edición. - M. : Laboratorio de Conocimientos Básicos, 2000.
Vavilov S. I. Isaac Newton . - M. : Ed. Academia de Ciencias de la URSS, 1945.
Volkov E. A. Métodos numéricos. — M. : Fizmatlit, 2003.
Gill F., Murray W., Wright M. Optimización práctica. Por. De inglés. — M .: Mir, 1985.
Korn G., Korn T. Manual de matemáticas para científicos e ingenieros. - M. : Nauka, 1970. - S. 575-576.
Korshunov Yu. M., Korshunov Yu. M. Fundamentos matemáticos de la cibernética. - Energía atomizada, 1972.
Maksimov Yu. A., Filippovskaya EA Algoritmos para resolver problemas de programación no lineal. — M. : MEPHI, 1982.
Morozov AD Introducción a la teoría de los fractales. — MEPHI, 2002.

Véase también

Enlaces

"Piscinas de Newton" en fractalworld.xaoc.ru
"Isaac Newton" en www.scottish-wetlands.org
"Obras matemáticas de Kantorovich" en el sitio web del Instituto de Matemáticas de la SB RAS
Hazewinkel, Michiel, ed. (2001), método de Newton , Enciclopedia de Matemáticas , Springer , ISBN 978-1-55608-010-4
Weisstein, Eric W. Newton's Method (inglés) en el sitio web Wolfram MathWorld .
Método de Newton, Citizendium.
Mathews, J., Los Métodos de Newton Acelerado y Modificado, Notas del curso.
Wu, X., Roots of Equations, Notas del curso.

Métodos de optimización
unidimensional	método de la sección áurea Dicotomía método de parábola búsqueda de cuadrícula Método de búsqueda de bloque uniforme método fibonacci búsqueda ternaria método Piyavsky Método Strongin
orden cero	método de Gauss Método Nelder-Mead Método Hook-Jeeves método de Rosenbrock metodo powell
Primer orden	descenso de gradiente método Zeutendijk Descenso coordinado método de gradiente conjugado Métodos Cuasi-Newtonianos Algoritmo de Levenberg-Marquardt
segundo orden	método de newton Método de Newton-Raphson Algoritmo de Broyden-Fletcher-Goldfarb-Shanno (BFGS)
estocástico	Método de Montecarlo recocido simulado Algoritmos evolutivos evolución diferencial Algoritmo de hormiga método de enjambre de partículas Algoritmo de colonia de abejas Método de paseo aleatorio
Métodos de programación lineal	método símplex algoritmo de gomori método elipsoide método potencial
Métodos de programación no lineal	Programación cuadrática secuencial