Artículos

6.3: Método de Newton


Suponga que tiene una función (f (x) ) y desea encontrar con la mayor precisión posible dónde cruza el eje (x ); en otras palabras, desea resolver (f (x) = 0 ). Suponga que no conoce ninguna forma de encontrar una solución exacta mediante ningún procedimiento algebraico, pero puede usar una aproximación, siempre que se pueda hacer bastante cerca del valor verdadero. El método de Newton es una forma de encontrar una solución a la ecuación con tantos lugares decimales como desee. Es lo que se llama un "procedimiento iterativo", lo que significa que se puede repetir una y otra vez para obtener una respuesta cada vez con mayor precisión. Los procedimientos iterativos como el método de Newton se adaptan bien a la programación para una computadora. El método de Newton utiliza el hecho que la línea tangente a una curva es una buena aproximación a la curva cerca del punto de tangencia.

Ejemplo ( PageIndex {1} )

Aproximada ( sqrt {3} ).

Solución

Dado que ( sqrt {3} ) es una solución de (x ^ 2 = 3 ) o (x ^ 2-3 = 0 ), usamos (f (x) = x ^ 2-3 ). Comenzamos adivinando algo razonablemente cercano al valor verdadero; esto suele ser fácil de hacer; usemos ( sqrt3 approx2 ). Ahora use la línea tangente a la curva cuando (x = 2 ) como una aproximación a la curva, como se muestra en la Figura ( PageIndex {1} ).

Figura ( PageIndex {1} ): Método de Netwon

Como (f '(x) = 2x ), la pendiente de esta recta tangente es 4 y su ecuación es (y = 4x-7 ). La recta tangente está bastante cerca de (f (x) ), por lo que cruza el eje (x ) - cerca del punto en el que (f (x) ) cruza, es decir, cerca de ( sqrt3 ). Es fácil encontrar dónde la recta tangente cruza el eje (x ) -: resuelve (0 = 4x-7 ) para obtener (x = 7/4 = 1.75 ). Ciertamente, esta es una mejor aproximación que 2, pero digamos que no es lo suficientemente cercana. Podemos mejorarlo haciendo lo mismo nuevamente: encuentre la línea tangente en (x = 1.75 ), encuentre dónde esta nueva línea tangente cruza el eje (x ) - y use ese valor como una mejor aproximación. Podemos continuar con esto indefinidamente, aunque se vuelve un poco tedioso. Veamos si podemos atajar el proceso. Suponga que la mejor aproximación a la intersección que tenemos hasta ahora es (x_i ). Para encontrar una mejor aproximación, siempre haremos lo mismo: encontrar la pendiente de la recta tangente en (x_i ), encontrar la ecuación de la recta tangente, encontrar la intersección en (x ). La pendiente es (2x_i ). La recta tangente es

[y = (2x_i) (x-x_i) + (x_i ^ 2-3), ]

utilizando la fórmula punto-pendiente por una línea. Finalmente, la intersección se encuentra resolviendo

[0 = (2x_i) (x-x_i) + (x_i ^ 2-3). label {EX1b} ]

Con un poco de álgebra, la ecuación ref {EX1b} se convierte en

[x = dfrac {x_i ^ 2 + 3} {2x_i} ]

esta es la siguiente aproximación, que naturalmente llamamos (x_ {i + 1} ). En lugar de hacer todo el cálculo de la línea tangente cada vez, simplemente podemos usar esta fórmula para obtener tantas aproximaciones como queramos.

Comenzando con (x_0 = 2 ), obtenemos

[x_1 = dfrac {x_0 ^ 2 + 3} {2x_0} = dfrac {2 ^ 2 + 3} {4} = dfrac {7} {4} ]

(la misma aproximación que obtuvimos arriba, por supuesto),

[x_2 = dfrac {x_1 ^ 2 + 3} {2x_1} = dfrac {(7/4) ^ 2 + 3} {(7/2)} = dfrac {97} {56} approx 1.73214, ]

y

[x_3 approx 1.73205, ]

y así. Esto todavía es un poco tedioso a mano, pero con una calculadora o, mejor aún, un buen programa de computadora, es bastante fácil obtener muchas, muchas aproximaciones. Ya podríamos adivinar que (1.73205 ) tiene una precisión de dos lugares decimales y, de hecho, resulta que tiene una precisión de 5 lugares.

Pensemos en este proceso en términos más generales. Queremos aproximar una solución a (f (x) = 0 ). Comenzamos con una estimación aproximada, que llamamos (x_0 ). Usamos la recta tangente a (f (x) ) para obtener una nueva aproximación que esperamos esté más cerca del valor real. ¿Cuál es la ecuación de la recta tangente cuando (x = x_0 )? La pendiente es (f '(x_0) ) y la recta pasa por ((x_0, f (x_0)) ), por lo que la ecuación de la recta es

[y = f '(x_0) (x-x_0) + f (x_0). ]

Ahora encontramos dónde cruza el eje (x ) - sustituyendo (y = 0 ) y despejando (x ): $$ x = {x_0f '(x_0) -f (x_0) over f '(x_0)} = x_0 - {f (x_0) over f' (x_0)}. $$ Normalmente, querremos calcular más de una de estas aproximaciones mejoradas, por lo que las numeramos consecutivamente; de (x_0 ) hemos calculado (x_1 ):

[x_1 = {x_0f '(x_0) -f (x_0) over f' (x_0)} = x_0 - {f (x_0) over f '(x_0)}, ]

y en general de (x_i ) calculamos (x_ {i + 1} ):

[x_ {i + 1} = {x_if '(x_i) -f (x_i) over f' (x_i)} = x_i - {f (x_i) over f '(x_i)}. ]

( PageIndex {2} )

Volviendo al ejemplo ( PageIndex {1} ), (f (x) = x ^ 2-3 ), (f '(x) = 2x ), y la fórmula se convierte en

[x_ {i + 1} = x_i - dfrac {x_i ^ 2-3} {2x_i} = dfrac {x_i ^ 2 + 3} {2x_i} ]

como antes.

En la práctica, es decir, si necesita aproximar un valor en el curso del diseño de un puente o un edificio o una estructura de avión, deberá tener cierta confianza en que la aproximación que establezca es lo suficientemente precisa. Como regla general, una vez que un cierto número de decimales deja de cambiar de una aproximación a la siguiente, es probable que esos decimales sean correctos. Aún así, esto puede no ser suficiente garantía, en cuyo caso podemos probar la precisión del resultado.

( PageIndex {3} )

Encuentra la coordenada (x ) de la intersección de las curvas (y = 2x ) y (y = tan x ), con una precisión de tres lugares decimales.

Solución

Para poner esto en el contexto del método de Newton, notamos que queremos saber dónde (2x = tan x ) o (f (x) = tan x-2x = 0 ). Calculamos (f '(x) = sec ^ 2 x - 2 ) y configuramos la fórmula:

[x_ {i + 1} = x_i - { tan x_i -2x_i over sec ^ 2 x_i - 2}. ]

Figura ( PageIndex {2} ). (y = tan x ) y (y = 2x ) a la izquierda, (y = tan x -2x )

A partir del gráfico de la Figura ( PageIndex {2} ) suponemos (x_0 = 1 ) como punto de partida, luego, utilizando la fórmula, calculamos

  • (x_1 = 1.310478030 ),
  • (x_2 = 1.223929096 ),
  • (x_3 = 1,176050900 ),
  • (x_4 = 1.165926508 ),
  • (x_5 = 1,165561636 ).

Entonces suponemos que los primeros tres lugares son correctos, pero eso no es lo mismo que decir que (1.165 ) es correcto con tres lugares decimales --- (1.166 ) podría ser la aproximación redondeada correcta. ¿Cómo podemos saberlo? Podemos sustituir 1.165, 1.1655 y 1.166 en ( tan x - 2x ); esto da -0,002483652, -0,000271247, 0,001948654. Dado que los dos primeros son negativos y el tercero es positivo, ( tan x - 2x ) cruza el eje (x ) entre 1.1655 y 1.166, por lo que el valor correcto en tres lugares es 1.166.

Colaboradores

    • Integrado por Justin Marshall.


Optimización de procesos

4.5.4.1 Métodos de Hesse

Los dos métodos que evalúan hessianos o hessianos aproximados utilizando diferencias finitas son: método de Newton & # x27s (Deuflhard, 2004) y SQP.

El método de Newton & # x27s para encontrar ceros de una función de g múltiples variables viene dado por:

dónde [Jgramo(Xnorte)] −1 es la inversa izquierda de la matriz jacobiana Jgramo(Xnorte) de g evaluado para xnorte.

SQP es un método basado en Newton desarrollado para problemas restringidos de pequeña a mediana escala. Algunas versiones pueden manejar problemas de grandes dimensiones.

Los métodos SQP se aplican cuando la función objetivo y las restricciones son dos veces diferenciables de forma continua. El método resuelve una secuencia de subproblemas de optimización, cada uno de los cuales optimiza un modelo cuadrático del objetivo sujeto a una linealización de las restricciones. Si el problema no tiene restricciones, entonces el método se reduce al método de Newton & # x27s para encontrar un punto donde el gradiente del objetivo desaparece. Si el problema solo tiene restricciones de igualdad, entonces el método es equivalente a aplicar el método de Newton & # x27s a las condiciones de optimalidad de primer orden, o condiciones de Karush-Kuhn-Tucker (KKT) (Karush, 1939 Kuhn y Tucker, 1951), de la problema.

Las condiciones KKT (también conocidas como condiciones de Kuhn-Tucker) son condiciones necesarias de primer orden para que una solución en PNL sea óptima, siempre que se satisfagan algunas condiciones de regularidad. Al permitir restricciones de desigualdad, el enfoque KKT de la PNL generaliza el método de los multiplicadores de Lagrange, que solo permite restricciones de igualdad. El sistema de ecuaciones correspondiente a las condiciones de KKT generalmente no se resuelve directamente, excepto en los pocos casos especiales en los que se puede derivar analíticamente una solución de forma cerrada. En general, muchos algoritmos de optimización pueden interpretarse como métodos para resolver numéricamente el sistema de ecuaciones KKT (Boyd y Vandenberghe, 2004).


Descripción

La palabra clave de método significa el inicio de un bloque en el archivo de entrada de Dakota. Dicho bloque contiene las diversas palabras clave necesarias para especificar un método y controlar su comportamiento.

Requisitos del bloque de métodos

Debe aparecer al menos un bloque de método en el archivo de entrada de Dakota. Pueden ser necesarios varios bloques de métodos para definir completamente los enfoques de análisis avanzados.

Cada bloque de método debe especificar un método y, opcionalmente, las palabras clave asociadas que gobiernan el comportamiento del método.

Cada bloque de método debe seleccionar un método.

A partir de Dakota v6.0, los métodos se agrupan en dos tipos: métodos estándar y métodos multicomponente.

Los métodos estándar son independientes y autónomos en el sentido de que solo requieren un modelo para realizar un estudio. No llaman a otros métodos. Si bien métodos como polynomial_chaos yfficient_global utilizan internamente múltiples iteradores y componentes del modelo sustituto, estos componentes generalmente están ocultos del control del usuario debido a restricciones en la modularidad, por lo tanto, estos métodos son independientes.

El grupo de métodos multicomponente proporciona un "meta-algoritmo" de nivel superior que apunta a otros métodos y modelos que admiten la sub-iteración. Por ejemplo, en un método híbrido secuencial, la especificación del método híbrido debe identificar una lista de métodos subordinados y el "meta-algoritmo" ejecuta estos métodos en secuencia y transfiere información entre ellos. Los minimizadores basados ​​en sustitutos proporcionan otro ejemplo en el sentido de que apuntan tanto a otros métodos (p. Ej., Qué método de optimización se utiliza para resolver el subproblema aproximado) como a modelos (p. Ej., Qué tipo de modelo sustituto se emplea). Los métodos de componentes múltiples generalmente proporcionan cierto nivel de modularidad "plug and play", a través de su soporte flexible de una variedad de selecciones de métodos y modelos.

Comandos de iterador basados ​​en componentes

Las especificaciones de iterador basadas en componentes incluyen métodos híbridos, de arranque múltiple, de conjuntos de Pareto, locales basados ​​en sustitutos, globales basados ​​en sustitutos y de bifurcación y enlace. Mientras que una especificación de iterador estándar solo necesita una cadena de puntero de modelo opcional (especificada con model_pointer), las especificaciones de iterador basadas en componentes pueden incluir especificaciones de puntero de método, nombre de método y puntero de modelo para definir los componentes empleados en la "meta-iteración". En particular, estas especificaciones identifican uno o más métodos (por puntero o por nombre) para especificar los iteradores subordinados que se utilizarán en el algoritmo de nivel superior. La identificación de un sub-iterador por nombre en lugar de por puntero es una opción liviana que relaja la necesidad de una especificación de método separada para el sub-iterador, sin embargo, puede ser necesario un puntero de modelo en este caso para proporcionar la conectividad de especificación normalmente soportada por el método puntero. Consulte estas descripciones de métodos individuales para conocer los requisitos específicos de estos métodos avanzados.

Controles independientes del método

Además del método, hay 10 palabras clave opcionales, que se denominan controles independientes del método. Estos controles son válidos para suficientes métodos que era razonable sacarlos de los bloques dependientes del método y consolidar las especificaciones, sin embargo, NO son universalmente respetados por todos los métodos.


7.3 Resolución de un sistema de ecuaciones no lineales

Aquí tratamos con métodos numéricos para la aproximación de soluciones reales de un sistema de ecuaciones no lineales, es decir, encontrar las raíces de una función vectorial. En comparación con el caso unidimensional, la búsqueda de raíces en el caso multidimensional es mucho más complicado. Por ejemplo, en un caso unidimensional se pueden poner entre paréntesis las raíces de una función dada (es decir, determinar los intervalos en los que se encuentra al menos una raíz de la función) pero no existen métodos para poner entre paréntesis las raíces de funciones generales en el caso multidimensional! Por lo general, ni siquiera sabemos si existe una raíz (solución del sistema) y si es única.

7.3.1 Método de Newton-Raphson para sistemas de ecuaciones no lineales

El método de Newton-Raphson es muy popular también en el caso multidimensional (aquí tenemos muchos menos métodos para elegir). Así como en el caso unidimensional, es muy eficiente si se tiene una buena aproximación inicial.

La fórmula para el método multidimensional de Newton-Raphson se puede derivar de manera similar a la de la Sección 7.2.2. Comience de nuevo con la serie de Taylor centrada en (¡vector!)

Lo mismo se puede escribir en notación matricial como

donde es el jacobiano de la función vectorial. Descuidar el término y el entorno implica

Este sistema de ecuaciones lineales se puede resolver para el vector. La nueva iteración se calcula como.

Calcular la derivada: al igual que en el caso unidimensional, también se puede aproximar mediante diferencias (ver 7.6.3).

Terminación: Para conocer los criterios de terminación habituales, consulte la Sección 7.2.1.

7.3.2 Ejemplo


z = nmnewton (fname, fder, x0 <, epsf, epsx,
maxiter, checkcond>)

Su uso más simple está en la forma que se muestra en

ejemplo XEGnum02.xpl, buscando una solución del siguiente sistema de dos ecuaciones no lineales:

A partir de la estimación inicial, obtenemos una aproximación de la solución,:

Si las funciones que calculan las derivadas de fname no están disponibles y se debe influir en la precisión de la aproximación numérica de las derivadas, se puede ingresar un paso h para nmjacobian (ver Sección 7.6.3):

Teniendo disponibles las funciones para el cálculo de las derivadas de fname, se puede ingresar su (s) nombre (s) como parámetro fder: fder debería ser una cadena con el nombre de la función que calcula el jacobiano de fname o un vector de cadenas con nombres de funciones que calculan gradientes del primero, segundo,. -ésimo componente de la función vectorial fname.

Esta posibilidad se muestra en el ejemplo XEGnum03.xpl que resuelve el siguiente sistema:

El jacobiano se calcula usando la fórmula

Estableciendo una estimación inicial en, obtenemos una solución,. Esta es una aproximación de:

Los parámetros epsf, epsx y maxiter influyen en la finalización de un proceso iterativo para encontrar la solución (ver Sección 7.2.1): el procedimiento finaliza si la suma de los valores absolutos de fname o las correcciones az son menores o iguales que epsf o epsx, respectivamente. el proceso también se termina si el número de iteraciones excede maxiter.

En cada iteración multiplicamos por, la matriz inversa al jacobiano de fname el número de condición alto del jacobiano puede causar una inestabilidad numérica del proceso iterativo. Configure el último segundo de verificación del parámetro para verificar la estabilidad. Se producirá un mensaje de advertencia si el número de condición excede el segundo de verificación.

Desafortunadamente, el método de Newton-Raphson puede fallar si la aproximación inicial no está lo suficientemente cerca de la raíz. La falla del método (es decir, la convergencia no se logra después de un número razonable de iteraciones) significa que no tiene raíces o que los pasos de Newton-Raphson fueron demasiado largos en algunas iteraciones (como se mencionó anteriormente, cada paso del método de Newton-Raphson va en la dirección de descenso de la función, teniendo su mínimo, si existe una raíz). La última posible dificultad puede resolverse mediante una modificación del método de Newton-Raphson descrito en la Sección 7.3.3.

7.3.3 Método de Newton-Raphson modificado para sistemas

El método de Newton-Raphson se puede modificar de la siguiente manera para lograr una mayor estabilidad numérica: En cada iteración, calcule el paso de Newton-Raphson y verifique si. Si esta condición no es válida, tenemos que reducir el tamaño del paso hasta tener un aceptable. Se introdujeron formas más o menos ingeniosas de reducir el tamaño del paso (ver, por ejemplo, (Press, Teukolsky, Vetterling y Flannery 1992)) sin embargo, reducirlo demasiado puede disminuir sustancialmente la tasa de convergencia.

7.3.4 Ejemplo

El siguiente quantlet resuelve un sistema no lineal de ecuaciones utilizando el método de Newton-Raphson modificado:


z = nmnewtonmod (fname, fder, x0 <, epsf, epsx,
maxiter, checkcond>)

Su uso es el mismo que para el quantlet nmnewton, consulte la Sección 7.3.2.

Un ejemplo de XEGnum04.xpl muestra un problema en el que es deseable utilizar el método de Newton-Raphson modificado en lugar del original. Debe resolverse la siguiente ecuación:

Su función del lado izquierdo es muy oscilante (ver Fig. 7.2).

Figura: Gráfico de para. El círculo relleno muestra la solución encontrada por el método de Newton-Raphson modificado, XEGnum04.xpl

Al establecer una estimación inicial en, el método de Newton-Raphson modificado da una solución en 5 iteraciones (que se muestra como un círculo relleno en la figura 7.2). Por otro lado, el método original de Newton-Raphson necesita 88 iteraciones para encontrar una raíz mucho más distante.


2.4 Método de Newton

En las dos secciones anteriores estudiamos técnicas para resolver ecuaciones que requerían muy pocas matemáticas sofisticadas. Los métodos de bisección y regula-falsi funcionan muy bien, pero como veremos en esta sección, podemos mejorar enormemente la calidad de los algoritmos de búsqueda de raíces aprovechando algo de Cálculo.

2.4.1 Intuición e implementación

Ejercicio 2.31 Comenzaremos esta sección con un recordatorio de Cálculo diferencial.

  1. Si (f (x) ) es una función diferenciable en (x = x_0 ) entonces la pendiente de la recta tangente a (f (x) ) en (x = x_0 ) es [ text m = subrayado < hspace <1in>> ]
  2. Desde el álgebra, la forma punto-pendiente de una línea es [y - y_0 = m (x-x_0) ] donde ((x_0, y_0) ) es un punto en la línea y (m ) es el Pendiente.
  3. Si (f (x) ) es una función diferencial en (x = x_0 ) entonces la ecuación de la tangente a (f (x) ) en ese punto es [y - underline < hspace < 1 en >> = subrayado < hspace <0.5in >> cdot left (x - underline < hspace <0.5in >> right) ]
  4. Si reorganizamos la respuesta del inciso c) obtenemos [y = underline < hspace <0.5in >> + underline < hspace <0.5in >> cdot left (x - underline < hspace < 0.5in >> derecha) ]

La intersección en (x ) de una función es donde la función es 0. La búsqueda de raíces es realmente el proceso de encontrar la intersección en (x ) de la función. Si la función es complicada (por ejemplo, muy no lineal o no se presta a las técnicas manuales tradicionales), entonces podemos aproximar la intersección en (x ) creando una aproximación de la serie de Taylor de la función en un punto cercano y luego encontrando la intersección (x ) de esa serie de Taylor más simple. La serie de Taylor no trivial más simple es una función lineal: ¡una línea tangente!

Ejercicio 2.33 Ahora usemos los cálculos que hiciste en los ejercicios anteriores para ver un algoritmo para aproximar la raíz de una función. En la siguiente secuencia de gráficos hacemos el siguiente algoritmo:

  • Dado un valor de (x ) que es una aproximación decente de la raíz, dibuja una línea tangente a (f (x) ) en ese punto.
  • Encuentra dónde la línea tangente se cruza con el eje (x ).
  • Use esta intersección como el nuevo valor (x ) y repita.

Se le ha mostrado el primer paso. Da un par de pasos más gráficamente. ¿Parece que el algoritmo converge a la raíz? ¿Crees que esto generalmente tomará más o menos pasos que el método de bisección?

Figura 2.8: Uso de aproximaciones sucesivas de rectas tangentes para encontrar la raíz de una función

El algoritmo con el que acabamos de jugar se conoce como método de Newton. El método fue propuesto originalmente por Isaac Newton, y luego modificado por Joseph Raphson, para aproximar las raíces de la ecuación (f (x) = 0 ). Debe quedar claro que el método de Newton requiere la existencia de la primera derivada, por lo que estamos pidiendo un poco más de nuestras funciones de lo que pedíamos antes. En Bisection y Regula Falsi solo pedimos que las funciones sean continuas, ahora pedimos que sean diferenciables. Deténgase y piense por un momento ... ¿por qué es más restrictivo pedir esto a la función (f (x) )?

Ejercicio 2.36 (método de Newton) El método de Newton-Raphson para resolver ecuaciones se puede describir de la siguiente manera:

Verifique que (f ) sea diferenciable en un dominio dado y encuentre una manera de garantizar que (f ) tenga una raíz en ese dominio (este paso se realiza a mano, no en la computadora).

Elija un punto de partida (x_0 ) en el dominio

Queremos escribir la ecuación de una recta tangente a (f ) en el punto ((x_0, f (x_0)) ).

¿Cuál es la pendiente de la recta tangente a la función (f (x) ) en el punto ((x_0, f (x_0)) )? [metro_ = subrayado < hspace <0.5in >> ]

Usando la forma punto-pendiente de una recta, (y-y_1 = m (x-x_1) ), escribe la ecuación de la recta tangente a (f (x) ) en el punto ((x_0, f (x_0)) ). [y - subrayado < hspace <0.4in >> = underline < hspace <0.4in >> cdot left (x - underline < hspace <0.4in >> right) ]

Encuentra la intersección en (x ) de la ecuación de la recta tangente estableciendo (y = 0 ) y despejando (x ). Llame a este nuevo punto (x_1 ). [x_1 = subrayado < hspace <2in>> ]

Ahora repita el proceso reemplazando las etiquetas " (x_1 )" y " (x_0 )" en el paso anterior con (x_) y (x_) respectivamente. [X_ = subrayado < hspace <2in>> ]

Itere el paso 5 hasta que (f (x_)) es cerca a cero.

2.4.2 Análisis

Hay varias formas en las que el método de Newton se comportará inesperadamente o fallará por completo. Algunos de estos problemas se pueden prever examinando la fórmula de iteración de Newton [x_ = x_n - frac. ] Algunas de las fallas que veremos son un poco más sorprendentes. También en esta sección veremos la tasa de convergencia del método de Newton y mostraremos que podemos superar en gran medida los métodos de bisección y Regula-Falsi.

Ejercicio 2.42 Puede ocurrir una falla interesante con el método de Newton que inicialmente no se esperaba. Considere la función (f (x) = x ^ 3 - 2x + 2 ). Esta función tiene una raíz cercana a (x = -1,77 ). Completa la siguiente tabla y dibuja las rectas tangentes en la figura para aproximar la solución a (f (x) = 0 ) con un punto de partida de (x = 0 ).

(norte) (x_n ) (f (x_n) )
(0) (x_0 = 0 ) (f (x_0) = 2 )
(1) (x_1 = 0 - frac = 1) (f (x_1) = 1 )
(2) (x_2 = 1 - frac =) (f (x_2) = )
(3) (x_3 = ) (f (x_3) = )
(4) (x_4 = ) (f (x_4) = )
( vdots ) ( vdots ) ( vdots )

Figura 2.9: Un interesante fallo del método de Newton.

Ejercicio 2.43 Ahora consideremos la función (f (x) = sqrt [3]). Esta función tiene una raíz (x = 0 ). Además, es diferenciable en todas partes excepto en (x = 0 ) ya que [f & # 39 (x) = frac <1> <3> x ^ <-2/3> = frac <1> <3x ^ <2/3 >>. ] El objetivo de este problema es mostrar lo que puede suceder cuando el punto de no diferenciabilidad es precisamente el punto que estás buscando.

  1. Complete la tabla de iteraciones comenzando en (x = -1 ), dibuje las líneas tangentes en la gráfica y haga una observación general de lo que está sucediendo con las iteraciones de Newton.

Ahora veamos la iteración de Newton con un poco más de detalle. Dado que (f (x) = x ^ <1/3> ) y (f & # 39 (x) = frac <1> <3> x ^ <- 2/3> ) la iteración de Newton puede ser simplificado como [x_ = x_n - frac> < izquierda ( frac <1> <3> x ^ <-2/3> derecha)> = x_n - 3 frac>> = x_n - 3x_n = -2x_n. ] ¿Qué nos dice esto sobre las iteraciones de Newton?
Sugerencia: Debería haber encontrado exactamente lo mismo en el experimento numérico del inciso a).

¿Hubo algo especial en el punto de partida (x_0 = -1 )? ¿Existirá este problema para cada punto de partida?

Figura 2.10: Otro sorprendente fracaso del método de Newton.

Figura 2.11: Otro sorprendente fracaso del método de Newton.

Ejercicio 2.45 Se sabe que el método de Newton tiene un tasa de convergencia cuadrática. Esto significa que hay una constante (C ) tal que [| x_ - x_ * | leq C | x_ - x_ * | ^ 2, ] donde (x _ * ) es la raíz que estamos buscando.

La convergencia cuadrática implica que si graficamos el error en la nueva iteración en el eje (y ) y el error en la iteración anterior en el eje (x ) de una gráfica log-log, entonces veremos una constante pendiente de 2. Para ver esto, podemos tomar el logaritmo (base 10) de ambos lados de la ecuación anterior para obtener [ log (| x_ - x_ * |) = log (C) + 2 log (| x_ - x_ * |), ] y vemos que esta es una función lineal (en una gráfica log-log) y la pendiente es 2. Creamos gráficas como esta en el Ejemplo 2.1.

Vamos a crear una gráfica de error como la que acabamos de describir.

  1. Elija una ecuación en la que sepa la solución.
  2. Cree la gráfica de error con (| x_ - x_ * | ) en el eje horizontal y (| x_ - x_ * | ) en el eje vertical
  3. Demuestre que esta gráfica tiene una pendiente de 2.
  4. Dé una explicación detallada de cómo interpretar la trama que acaba de hacer.
  5. Al resolver una ecuación con el método de Newton, Joe descubrió que el error absoluto en la iteración 1 del proceso era (0,15 ). Basado en el hecho de que el método de Newton es un método de segundo orden, esto significa que el error absoluto en el paso 2 será menor o igual a algunos tiempos constantes (0.15 ^ 2 = 0.0225 ). De manera similar, el error en el paso 3 será menor o igual a algún múltiplo escalar de (0.0025 ^ 2 = 0.00050625 ). ¿Cuál sería el límite del error esperado de Joe para la cuarta iteración, la quinta iteración, etc.?

  • Estructurado para pasar de ideas fundamentales y elementales desde el principio a conceptos más sofisticados. más adelante en el texto. Análisis numérico contiene suficiente contenido para un curso de dos semestres, pero también se puede utilizar para un curso de un semestre con una elección acertada de temas.
  • Focos a lo largo del texto destacan las cinco ideas principales del análisis numérico: convergencia, complejidad, condicionamiento, compresión, y ortogonalidad.
  • Estos Spotlights comentan el tema en cuestión y hacen conexiones informales con otras expresiones del mismo concepto en otras partes del libro, lo que ayuda a los estudiantes a sintetizar material nuevo con lo que ya saben.
  • La función Reality Check bien recibida aparece en cada capítulo para proporcionar ejemplos extendidos de la forma en que los métodos numéricos conducen a soluciones de problemas tecnológicos importantes, haciendo que los temas sean inmediatamente relevantes.
  • Las exposiciones de MATLAB ® aparecen a lo largo del texto, brindar orientación a los estudiantes e instructores sobre el uso de esta importante herramienta de software.
  • El Apéndice B es un breve tutorial de MATLABl que se puede utilizar como una primera introducción a los estudiantes que no han utilizado MATLAB, o como referencia para los estudiantes que ya están familiarizados con el software.
    ¡NUEVO! URL cortas en los márgenes del texto (235 en total) llevan a los estudiantes directamente al contenido relevante para respaldar su uso del libro de texto, que incluye:

      Código MATLAB (bit.ly/2yupqhx): Las instancias más largas de código MATLAB están disponibles para los estudiantes en formato * .m.

      Soluciones a ejercicios seleccionados (bit.ly/2PG6q69): En ediciones anteriores, se podía comprar por separado un Manual de soluciones para estudiantes. La tercera edición brinda a los estudiantes acceso a soluciones para ejercicios seleccionados en línea sin costo adicional.

      Ejemplos adicionales (bit.ly/2Cr0FW2): Cada sección de la 3ª edición se ha mejorado con nuevos ejemplos adicionales, diseñados para reforzar la exposición del texto y facilitar la transición del lector a la solución activa de ejercicios y problemas informáticos. Las soluciones elaboradas de estos ejemplos, más de cien en total, están disponibles en línea. Algunas de las soluciones están en formato de video (creado por el autor).

      La página de inicio de todo el contenido web que respalda el texto es bit.ly/2yN3AEX.

      • ¡NUEVO! Varias docenas de nuevos ejercicios y problemas informáticos. se han añadido a la 3ª edición.

      Nuevo en esta edición

      • URL cortas en los márgenes del texto (235 en total) llevan a los estudiantes directamente al contenido relevante para respaldar su uso del libro de texto, que incluye:
        • Código MATLAB (bit.ly/2yupqhx): Las instancias más largas de código MATLAB están disponibles para los estudiantes en formato * .m.
        • Soluciones a ejercicios seleccionados (bit.ly/2PG6q69): En ediciones anteriores, se podía comprar por separado un Manual de soluciones para estudiantes. La tercera edición brinda a los estudiantes acceso a soluciones para ejercicios seleccionados en línea sin costo adicional.
        • Ejemplos adicionales (bit.ly/2Cr0FW2): Cada sección de la 3ª edición se ha mejorado con nuevos ejemplos adicionales, diseñados para reforzar la exposición del texto y facilitar la transición del lector a la solución activa de ejercicios y problemas informáticos. Las soluciones elaboradas de estos ejemplos, más de cien en total, están disponibles en línea. Algunas de las soluciones están en formato de video (creado por el autor).
        • La página de inicio de todo el contenido web que respalda el texto es bit.ly/2yN3AEX.
        • Discusión más detallada de varios conceptos clave incluye la teoría de la interpolación polinomial, solucionadores de ecuaciones diferenciales de varios pasos, problemas de valores de frontera y descomposición de valores singulares, entre otros.
        • La verificación de la realidad sobre la compresión de audio en el Capítulo 11 se ha renovado y simplificado, y se han agregado y actualizado otros códigos MATLAB a lo largo del texto.
        • Varias docenas de nuevos ejercicios y problemas informáticos. se han añadido a la 3ª edición.

        2 respuestas 2

        Manejo de raíces complejas

        Cuando hay raíces complejas, tiene dos casos, para a1 & gt 0 y a1 & lt 0. Puede colapsar los dos casos usando abs (a1) al definir imagg.

        Mejor aún, Python tiene soporte integrado para un tipo complejo. ¿Por qué no usarlo en lugar de construir una cadena? Entonces ni siquiera tiene que preocuparse por el signo de la parte imaginaria por el bien de una impresión bonita.

        Separación de intereses

        Su función solvedeg3equation () realiza entrada, cálculo y salida. Eso puede hacer el trabajo por usted, pero asegura que su código nunca será reutilizable, más que copiando y pegando - ¡o canalizando la entrada hacia usted e intentando analizar la salida! Además, hace que la prueba unitaria de su código sea igual de difícil. Lo que desea es una función que acepte un polinomio (más sobre eso en breve) y devuelva una tupla de 3 soluciones. La persona que llama sería responsable de la entrada y la salida.

        Notación

        Representar un polinomio de tercer grado como variables a, b, cyd es difícil de manejar. No se puede transmitir fácilmente como una entidad. La proliferación de variables impone una carga mental. Lo más importante es que creo que conduce a una mala notación en su código.

        Propongo la siguiente notación:

        • x0, x1, x2: la primera, segunda y tercera raíces (mejor que g, g2, g3)
        • Polinomio (a, b, c, d): un objeto que representa el polinomio una x 3 + b x 2 + c x + D
        • f: El polinomio a resolver (mejor que a, b, c, d)
        • df_dx: La derivada de f (mejor que 3 * a * g ** 2 + 2 * b * g + c)
        • q: El polinomio cuadrático restante después de que se haya encontrado x0 (mejor que c1 = -d / g a1 = a b1 = (c1-c) / g)
        • q.discriminant (): abreviatura de b1 ** 2-4 * a1 * c1
        • tolerancia: mejor que e (que desafortunadamente parece estar relacionado con a, b, c, d)

        Además, no debe codificar de forma rígida un límite de 100 iteraciones, especialmente el doble como un número mágico en el código.

        Clase polinomial

        Como se señaló anteriormente, tener una clase para polinomios es extremadamente útil para su problema. Además del polinomio a resolver, necesitas su derivada y también tienes una ecuación cuadrática para resolver. Una clase polinomial te permite

        • pasar el polinomio a la función de resolución convenientemente
        • colapsar varias variables en una
        • evaluar el valor del polinomio fácilmente
        • tomar su derivada

        Aquí hay una implementación:

        Manejo de errores

        Si algo sale mal, no se limite a imprimir algo. ¡Genere una excepción, que asegura que la persona que llama notará el problema!

        Límite de iteración

        Python tiene una función de lenguaje para ejecutar una cláusula else cuando un bucle termina naturalmente por agotamiento (es decir, cuando su condición se vuelve falsa, en lugar de por una ruptura temprana). Puedes usarlo así:

        ¡Bonita!

        Toda esa configuración permite que su código se vea como matemáticas, no como un programa C. Ahora puede despejar su mente de las minucias y concentrarse en las cosas que importan, como su técnica matemática.

        También hice algunos comentarios en los comentarios del código.

        Uso de ejemplo

        Próximos pasos

        Como se señaló en los comentarios, recomendaría usar cmath.sqrt () para colapsar los tres casos del discriminante en uno.

        También sería una buena idea descomponer el solucionador de ecuaciones cúbicas en un solucionador genérico del método de Newton para cualquier polinomio, seguido de un solucionador de ecuaciones cuadráticas.


        9 Respuestas 9

        El descenso de gradiente maximiza una función utilizando el conocimiento de su derivada. El método de Newton, un algoritmo de búsqueda de raíces, maximiza una función utilizando el conocimiento de su segunda derivada. Eso puede ser más rápido cuando se conoce la segunda derivada y es fácil de calcular (el algoritmo de Newton-Raphson se usa en regresión logística). Sin embargo, la expresión analítica de la segunda derivada es a menudo complicada o intratable y requiere mucho cálculo. Los métodos numéricos para calcular la segunda derivada también requieren mucho cálculo: si se requieren valores de $ N $ para calcular la primera derivada, se requieren $ N ^ 2 $ para la segunda derivada.

        UKF similar) o métodos DFO-SQP (por ejemplo, BOBYQA). "La optimización" es una pregunta complicada, diría yo. para un problema de aprendizaje automático, frente a un problema de optimización de diseño de ingeniería, la confiabilidad / informatividad de un & quot; arpillera local & quot puede ser dudosa. Quizás el DFO-SQP no local sea

        & Quotstochastic Newton & quot? (p. ej., & quotonline & quot) $ endgroup $ & ndash GeoMatt22 29 de diciembre de 2016 a las 5:26

        Mas gente debería utilizar el método de Newton en el aprendizaje automático *. Digo esto como alguien con experiencia en optimización numérica, que ha incursionado en el aprendizaje automático durante los últimos años.

        Los inconvenientes en las respuestas aquí (e incluso en la literatura) no son un problema si usa el método de Newton correctamente. Además, los inconvenientes importantes también ralentizan el descenso del gradiente en la misma cantidad o más, pero a través de mecanismos menos obvios.

        El uso de la búsqueda de líneas con las condiciones de Wolfe o el uso de regiones de confianza o de confianza evita la convergencia a los puntos de silla. Una implementación de descenso de gradiente adecuada debería estar haciendo esto también. El documento al que se hace referencia en la respuesta de Cam.Davidson.Pilon señala problemas con el "método de Newton" en presencia de puntos de silla, pero la solución que defienden es también un método de Newton.

        El uso del método de Newton no requiere construir el hessiano completo (denso), puede aplicar el inverso del hessiano a un vector con métodos iterativos que solo usan productos matriz-vector (por ejemplo, métodos de Krylov como gradiente conjugado). Consulte, por ejemplo, el método de la región de confianza CG-Steihaug.

        Puede calcular productos de matriz-vector hessiano de manera eficiente resolviendo dos ecuaciones adjuntas de orden superior de la misma forma que la ecuación adjunta que ya se usa para calcular el gradiente (por ejemplo, el trabajo de dos pasos de retropropagación en el entrenamiento de redes neuronales).

        El mal acondicionamiento ralentiza la convergencia de los solucionadores lineales iterativos, pero también ralentiza el descenso del gradiente por igual o peor. El uso del método de Newton en lugar del descenso de gradiente cambia la dificultad de la etapa de optimización no lineal (donde no se puede hacer mucho para mejorar la situación) a la etapa de álgebra lineal (donde podemos atacarla con todo el arsenal de técnicas de preacondicionamiento de álgebra lineal numérica).

        Además, el cálculo cambia de "muchos, muchos pasos baratos" a "algunos pasos costosos", lo que abre más oportunidades para el paralelismo en el nivel de subpaso (álgebra lineal).

        Para obtener información básica sobre estos conceptos, recomiendo el libro "Optimización numérica" ​​de Nocedal y Wright.

        * Por supuesto, el método de Newton no le ayudará con L1 u otras funciones de penalización que promuevan la dispersión / detección comprimida similar, ya que carecen de la suavidad requerida.

        Una combinación de dos razones:

        • El método de Newton atrae a los puntos de silla son comunes en el aprendizaje automático o, de hecho, en cualquier optimización multivariable.

        Mira la función $ f = x ^ 2-y ^ 2 $

        Si aplica el método de Newton multivariado, obtiene lo siguiente. $ mathbf_ = mathbf_n - [ mathbff ( mathbf_n)] ^ <-1> nabla f ( mathbf_n) $

        Obtén el gradiente: $ nabla f = begin 2x [2.2ex] -2y end$

        Entonces, ve cómo el método de Newton lo llevó al punto de silla en $ x = 0, y = 0 $.

        Por el contrario, el método de descenso en pendiente no conducirá al punto de silla. El gradiente es cero en el punto de silla, pero un pequeño paso hacia afuera alejaría la optimización como puede ver en el gradiente de arriba: su gradiente en la variable y es negativo.

        Recientemente aprendí esto yo mismo: el problema es la proliferación de puntos de silla en el espacio de alta dimensión, a los que los métodos de Newton quieren converger. Consulte este artículo: Identificar y atacar el problema del punto silla en la optimización no convexa de alta dimensión.

        De hecho, la relación entre el número de puntos silla y los mínimos locales aumenta exponencialmente con la dimensionalidad N.

        Mientras que la dinámica de descenso de gradiente se repele desde un punto de asiento para reducir el error siguiendo direcciones de curvatura negativa,. el método de Newton no trata apropiadamente los puntos de silla como se argumenta a continuación, los puntos de silla en cambio se vuelven atractivos bajo la dinámica de Newton.

        Hiciste dos preguntas: ¿Por qué más personas no usan el método de Newton y por qué tantas personas usan el descenso de gradiente estocástico? Estas preguntas tienen diferentes respuestas, porque hay muchos algoritmos que reducen la carga computacional del método de Newton, pero a menudo funcionan mejor que SGD.

        Primero: el método de Newton lleva mucho tiempo por iteración y requiere mucha memoria. Como señala jwimberley, el método de Newton requiere calcular la segunda derivada, $ H $, que es $ O (N ^ 2) $, donde $ N $ es el número de características, mientras que calcular el gradiente, $ g $, es solo $ O (N) $. Pero el siguiente paso es $ H ^ <-1> g $, que es $ O (N ^ 3) $ para calcular. Entonces, si bien calcular el arpillera es costoso, invertirlo o resolver mínimos cuadrados suele ser aún peor. (Si tiene características escasas, los asintóticos se ven mejor, pero otros métodos también funcionan mejor, por lo que la escasez no hace que Newton relativamente más atractivo.)

        En segundo lugar, muchos métodos, no solo el descenso de gradiente, se utilizan con más frecuencia que Newton; a menudo son imitaciones del método de Newton, en el sentido de que se aproximan a un paso de Newton a un costo computacional por paso más bajo, pero requieren más iteraciones para converger. Algunos ejemplos:

        Debido al costo de invertir el hessiano, los métodos "cuasi-Newton" como BFGS se aproximan al inverso Hessian, $ H ^ <-1> $, observando cómo ha cambiado el gradiente en los últimos pasos.

        BFGS todavía consume mucha memoria en entornos de alta dimensión porque requiere almacenar todo el $ O (N ^ 2) $ arpillera inversa aproximada. BFGS de memoria limitada (L-BFGS) calcula la dirección del siguiente paso como el hessiano inverso aproximado multiplicado por el gradiente, pero solo requiere almacenar las últimas actualizaciones de gradiente; no almacena explícitamente el hessiano inverso aproximado.

        Cuando no quiere lidiar con la aproximación de segundas derivadas, el descenso de gradiente es atractivo porque solo usa información de primer orden. El descenso de gradiente se aproxima implícitamente al hessiano inverso como la tasa de aprendizaje multiplicada por la matriz de identidad. Yo, personalmente, rara vez uso el descenso de gradiente: L-BFGS es igual de fácil de implementar, ya que solo requiere especificar la función objetivo y el gradiente, tiene una mejor aproximación hessiana inversa que el descenso de gradiente y porque el descenso de gradiente requiere ajustar la tasa de aprendizaje.

        A veces, tiene una gran cantidad de observaciones (puntos de datos), pero podría aprender casi tan bien de un número menor de observaciones. Cuando ese es el caso, puede utilizar "métodos por lotes", como el descenso de gradiente estocástico, que recorre el ciclo mediante el uso de subconjuntos de las observaciones.


        Instructor

        Stephen P. Boyd es profesor de ingeniería de Samsung y profesor de ingeniería eléctrica en el laboratorio de sistemas de información de la Universidad de Stanford. Su investigación actual se centra en aplicaciones de optimización convexa en control, procesamiento de señales y diseño de circuitos.

        El profesor Boyd recibió una licenciatura en matemáticas, summa cum laude, de la Universidad de Harvard en 1980, y un doctorado en EECS de la U. C. Berkeley en 1985. En 1985 se unió a la facultad del Departamento de Ingeniería Eléctrica de Stanford. Ha ocupado puestos de profesor visitante en la Universidad Katholieke (Lovaina), la Universidad McGill (Montreal), la Ecole Polytechnique Federale (Lausana), la Universidad Qinghua (Beijing), la Universidad Paul Sabatier (Toulouse), el Real Instituto de Tecnología (Estocolmo), la Universidad de Kyoto, y el Instituto de Tecnología de Harbin. Tiene un doctorado honorario del Royal Institute of Technology (KTH) de Estocolmo.

        El profesor Boyd es autor de muchos artículos de investigación y tres libros: Linear Controller Design: Limits of Performance (con Craig Barratt, 1991), Linear Matrix Inequalities in System and Control Theory (con L. El Ghaoui, E. Feron y V. Balakrishnan, 1994) y Optimización convexa (con Lieven Vandenberghe, 2004).

        El profesor Boyd ha recibido numerosos premios y distinciones por su investigación en ingeniería y optimización de sistemas de control, incluido un premio ONR Young Investigator, un premio Presidential Young Investigator y un premio de desarrollo docente de IBM. En 1992 recibió el Premio AACC Donald P. Eckman, que se otorga anualmente por la mayor contribución al campo de la ingeniería de control por parte de alguien menor de 35 años. En 1993 fue elegido Profesor Distinguido de la Sociedad de Sistemas de Control IEEE, y en 1999, fue elegido miembro del IEEE, con la mención: "Por sus contribuciones al diseño y análisis de sistemas de control utilizando herramientas CAD basadas en optimización convexa". Ha sido invitado a impartir más de 30 conferencias plenarias y magistrales en conferencias importantes tanto en control como en optimización.

        Además de impartir grandes cursos de posgrado sobre sistemas dinámicos lineales, sistemas de retroalimentación no lineal y optimización convexa, el profesor Boyd ha impartido regularmente cursos de introducción a la ingeniería eléctrica de pregrado sobre circuitos, señales y sistemas, procesamiento de señales digitales y control automático. En 1994 recibió el Premio Perrin a la Docencia Destacada de Pregrado en la Facultad de Ingeniería, y en 1991, un Premio de Docencia de Posgrado de la ASSU. En 2003, recibió el premio AACC Ragazzini Education, por sus contribuciones a la educación de control, con la mención: “Por la excelencia en la enseñanza en el aula, la preparación de libros de texto y monografías, y la tutoría de estudiantes de pregrado y posgrado en el área de sistemas, control y optimización. "


        Pensamientos aleatorios

        Ejercicio 7.3 Para probar el algoritmo de raíz cuadrada de este capítulo, puede compararlo con math.sqrt. Escriba una función llamada test_square_root que imprima una tabla como esta:

        La primera columna es un número, la segunda columna es la raíz cuadrada de a calculada con la función del Ejercicio 7.2 la tercera columna es la raíz cuadrada calculada por math.sqrt la cuarta columna es el valor absoluto de la diferencia entre las dos estimaciones .

        Este tomó un poco de tiempo solo por el formato, todavía no lo veo bien, pero al menos los valores son buenos.

        Algunos ajustes me consiguieron este feo lío:

        Eso produce una salida un poco menos fea:

        Debe haber una forma más fácil:

        05 de enero de 2011
        Se eliminó la función format (), fue solo un intento de eliminar todo el formato de printout () pero lo dejé y olvidé eliminarlo. Añadidos algunos comentarios para más tarde.

        [31 de diciembre de 2011]
        Aquí está la versión que asdfg098 proporcionó en los comentarios formateados un poco.


        Ver el vídeo: Estática Hibbeler. Problema Análisis Estructural. Método de Nodos 14 Edición (Septiembre 2021).