Un método cuasi-Newton para funciones reales de dos variables basado en la minimización del número de condición de la matriz de actualización .
José Jacobo Oliveros Oliveros, Julio Andrés Acevedo Vázquez, Juan Alberto Escamilla Reyna
Resumen
In this work, a quasi-Newton method is proposed to solve unconstrained non-linear equations based on the minimization of the condition number of the updating matrix considering the Frobenius norm. The convergence of the method is proved using fixed point theory. Some numerical examples are presented to show the performance of the method, and it is compared with the classical DFP and BFGS methods. The results show that the method proposed here is feasible, and for certain kinds of problems, the solution is obtained using fewer iterations and less computing time than the other ones. The method is applied to solve systems of ordinary differential equations. The results obtained are compared with the ones obtained with the BFGS method. These results show that the two methods have a similar performance.
Keywords: cuasi-Newton, condition number.
En este trabajo, se propone un método cuasi-Newton para resolver ecuaciones no lineales sin restricciones, que se basa en la minimización del número de condición de la matriz de actualización, considerando la norma de Frobenius. La convergencia del método es probada usando teoría del punto fijo. Se presentan algunos ejemplos numéricos para mostrar el desempeño del método y es comparado con los métodos clásicos DFP y BFGS. Los resultados muestran que el método propuesto es factible y que para cierta clase de problemas, obtiene la solución utilizando menos iteraciones que los otros. El método es aplicado para resolver sistemas de ecuaciones diferenciales ordinarias. Los resultados obtenidos son comparados con aquellos obtenidos con el método BFGS. Estos resultados muestran que los dos métodos tiene un desempeño similar.
Palabras clave: cuasi-Newton, número de condición.
1 Introducción
Los problemas de minimización de funciones tienen gran importancia por sus múltiples aplicaciones y llevan a la resolución de sistemas de ecuaciones ya que tenemos que encontrar los puntos críticos de la función que se minimiza. Resolver ecuaciones tiene gran importancia por si mismo, ya que aparecen con frecuencia en muchas aplicaciones. En particular, los sistemas de ecuaciones aparecen en los métodos numéricos para resolver ecuaciones diferenciales ordinarias, como el método de Euler implícito que es un caso de los llamados métodos BDF (por sus siglas en inglés Backward Differentiation Formulas) [1]. Por lo anterior, se ha puesto especial atención en el desarrollo de métodos para la resolución de estas ecuaciones tanto lineales como no lineales. En este trabajo, se propone un método cuasi-Newton para resolver ecuaciones no lineales y se muestra que para cierta clase de funciones produce mejores resultados que los conocidos métodos DFP y BFGS. También se implementa este método y el BFGS en el Método Implícito de Euler y se halla que producen resultados similares.
A continuación, se presenta el planteamiento del problema de minimización que interesa en este trabajo.
Sea Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {f}:\mathbb{R}^n\to \mathbb{R}}
una función suave. Consideremos el siguiente problema
|
(1) |
El primer método cuasi-Newton (denotado por DFP) fue creado por Davidon, Fletcher y Powell [2,3], demostrando que este método era más eficaz que los métodos existentes. El método DFP es un método de búsqueda en la linea que considera una aproximación cuadrática de la función objetivo en la iteración Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {x}^k} . Tenemos la siguiente notación: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {f}^k=\boldsymbol {f}(\boldsymbol {x}^k)} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \nabla \boldsymbol {f}^k=\nabla \boldsymbol {f}(\boldsymbol {x}^k)}
y Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \nabla ^2\boldsymbol {f}^k=\nabla ^2\boldsymbol {f}(\boldsymbol {x}^k)}
donde Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \nabla ^2\boldsymbol {f}}
denota el hessiano de la función Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {f}}
, por lo que la aproximación está dada por
|
(2) |
donde Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {B_k}}
es una matriz simétrica definida positiva de tamaño Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle n\times n}
, que se actualizará en cada iteración. La matriz Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {B_K}}
no es el hessiano de la función Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {f}}
, pero es una aproximación de ella. Notemos que Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {m}_k(\boldsymbol {0})=\boldsymbol {f}^k}
y dado que Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {m}_k}
es una función convexa, alcanza el mínimo en
|
(3) |
el cual será usado en la nueva iteración
|
(4) |
donde la longitud de paso Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \alpha _k}
se escoge de tal forma que cumpla las condiciones de Wolfe.
Un requerimiento que parece razonable pedir en Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {B}_{k+1}}
es que el gradiente de Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {m}_{k+1}}
debe coincidir con el gradiente de la función objetivo Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {f}}
en al menos dos iteraciones Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {x}^k}
y Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {x}^{k+1}}
. Obsérvese que Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \nabla \boldsymbol {m}_{k+1}(\boldsymbol {0})=\nabla \boldsymbol {f}^{k+1}} , así que la segunda de estas condiciones se satisface. La primera condición puede ser escrita como
|
(5) |
Para simplificar la ecuación anterior se definen los vectores
|
(6.a) |
|
(6.b) |
Así, la ecuación (5) se reescribe como
|
(7) |
la cual es conocida como la ecuación secante.
Del hecho de que la matriz Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {B}_{k+1}}
es definida positiva y por la ecuación secante, se tiene que
|
(8) |
La desigualdad anterior es conocida como la condición de curvatura.
Cuando la función es fuertemente convexa, la condición de curvatura se cumplirá, para cualesquiera dos puntos Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {x}^{k+1}}
y Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {x}^k}
, pero no siempre se cumplirá cuando la función no es convexa. En este último caso, se tiene que forzar a que se cumpla (8) imponiendo las condiciones de Wolfe o las condiciones fuertes de Wolfe en Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \alpha _k}
[4].
Cuando la condición de curvatura se cumple, la ecuación secante (7) tiene infinitas soluciones, ya que hay Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \frac{n(n+1)}{2}}
grados de libertad en una matriz simétrica y la ecuación secante representa Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle n}
condiciones y hay Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle n}
condiciones más como consecuencia de que la matriz es definida positiva, pero estas condiciones no absorben los grados de libertad restantes. Así, hay infinitas maneras de elegir la matriz de actualización Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): \boldsymbol {B}_{k+1}
, lo que da la posibilidad de proponer diferentes métodos que se adapten al problema que se está estudiando.
2 Descripción de los métodos DFP y BFGS
En esta sección se explicará brevemente la manera en que se construyeron los métodos DFP y BFGS usuales. Notamos que, aunque los dos métodos se construyen de manera muy similar, éstos poseen propiedades muy distintas.
2.1 El método DFP
Una manera de determinar Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {B}_{k+1}}
es pidiendo que, entre todas las matrices simétricas que cumplen la ecuación secante, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {B}_{k+1}}
debe ser la más cercana a la matriz actual Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {B}_k}
, en otras palabras, tenemos que resolver el siguiente subproblema
|
(9.a) |
|
(9.b) |
donde Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {s}^k}
y Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {y}^k}
satisfacen la condición de curvatura y Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {B}_k}
es una matriz simétrica definida positiva. Muchas normas pueden ser usadas en (9.a) y cada una de ellas da lugar a un método cuasi-Newton distinto. Una norma que permite una fácil resolución del problema es la norma pesada de Frobenius
|
(10) |
El peso Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {W}}
puede ser escogido como cualquier matriz que satisfaga la relación Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {Wy}^k=\boldsymbol {s}^k}
. Se asume Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {W}=\overline{\boldsymbol {G}}_k^{-1}} , donde Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \overline{\boldsymbol {G}}_k}
es el hessiano promedio, dado por
|
(11) |
Fácilmente puede verificarse que Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \overline{\boldsymbol {G}}_k^{-1}\boldsymbol {y}^k=\boldsymbol {s}^k} .
Con la norma y matriz de peso descritas arriba, la única solución de (9) es
|
(12) |
donde Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \gamma _k=\dfrac{1}{(\boldsymbol {y}^k)^t\boldsymbol {s}^k}.}
Esta fórmula es llamada la fórmula de actualización DFP, ya que fue propuesta por Davidon en 1959 [2], y posteriormente estudiada, implementada y popularizada por Fletcher y Powell [3].
Sea Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {H}_k=\boldsymbol {B}_k^{-1}} . Usando la fórmula de Sherman-Morrison-Woodbury [4] y la ecuación (12) se sigue que
|
(13) |
Esto resulta útil, ya que nos permite calcular la dirección de búsqueda simplemente con una multiplicación matriz-vector.
Nótese que los últimos dos términos del lado derecho de (13) son matrices de rango 1, así Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {H}_k}
es una modificación de rango 2. Esa es la idea fundamental de la actualización cuasi-Newton, en lugar de recalcular la actualización desde cero, se aplica una simple modificación que combina la información recientemente observada de la función objetivo con el conocimiento existente en nuestra aproximación de la hessiana actual.
, tolerancia Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \varepsilon } , aproximación del inverso del hessiano Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {H}_0} . Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {x}^*} mínimo de Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {f}}
. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle k\leftarrow 0.} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): \left\Vert \nabla \boldsymbol {f}(\boldsymbol {x}^k)\right\Vert > \varepsilon
Calcular la dirección de búsqueda
Calcular Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {x}^{k+1}=\boldsymbol {x}^k+\alpha _k\boldsymbol {p}^k} , donde Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \alpha _k} es calculado mediante un procedimiento de búsqueda en la línea que satisfaga las condiciones de Wolfe,
con Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 0<c_1<c_2<1.} Definir Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {s}^k=\boldsymbol {x}^{k+1}-\boldsymbol {x}^k}
y Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {y}^k=\nabla \boldsymbol {f}(\boldsymbol {x}^{k+1})-\nabla \boldsymbol {f}(\boldsymbol {x}^k)}
. Calcular Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {H}_{k+1}} por medio de (13). Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle k\leftarrow k+1.}
| |||||||||
|
Algoritmo. 1 Algoritmo DFP |
2.2 El método BFGS
La fórmula del método BFGS puede ser derivado haciendo un simple cambio en el argumento que lleva a (12). Las condiciones impuestas en las aproximaciones del hessiano Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {B}_k} , pueden ser impuestas en sus inversas Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {H}_k} . Por lo tanto, la actualización Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {H}_{k+1}}
debe ser simétrica, definida positiva, y satisfacer la ecuación secante (7), ahora escrita como Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {H}_{k+1}\boldsymbol {y}^k=\boldsymbol {s}^k.}
La condición de la cercanía a Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {H}_k}
es ahora especificada de forma análoga a (9)
|
(16.a) |
|
(16.b) |
La norma considerada es de nuevo la norma pesada de Frobenius descrita anteriormente, donde la matriz de peso Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {W}}
es ahora cualquier matriz que satisfaga Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {Ws}^k=\boldsymbol {y}^k}
. (Por concreción, se asume de nuevo que Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {W}}
está dado por el inverso del hessiano promedio Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \overline{\boldsymbol {G}}_k}
definida en (11)). La única solución Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {H}_{k+1}}
de (16) está dada por
|
(17) |
donde
|
(18) |
o bien, desarrollando las multiplicaciones
|
(19) |
La demostración del siguiente teorema puede encontrarse en [5].
Teorema 1: Si la fórmula de actualización Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle BFGS}
(19), es ahora escrita como Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {H}_{k+1}=\boldsymbol {H}_k+\boldsymbol {E}}
, entonces Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {E}}
resuelve el problema
|
donde Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {W}}
satisface Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {Ws}^k=\boldsymbol {y}^k}
y Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {\eta }=\boldsymbol {s}^k-\boldsymbol {H}_k\boldsymbol {y}^k}
.
De acuerdo con Nocedal [4], si Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {H}_k}
es definida positiva, entonces Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {H}_{k+1}}
es definida positiva.
, tolerancia Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \varepsilon } , aproximación del inverso del hessiano Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {H}_0} . Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {x}^*} mínimo de Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {f}}
. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle k\leftarrow 0.} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): \left\Vert \nabla \boldsymbol {f}(\boldsymbol {x}^k)\right\Vert > \varepsilon
Calcular la dirección de búsqueda
Calcular Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {x}^{k+1}=\boldsymbol {x}^k+\alpha _k\boldsymbol {p}^k} , donde Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \alpha _k} es calculado mediante un procedimiento de búsqueda en la línea que satisfaga las condiciones de Wolfe (1). Definir Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {s}^k=\boldsymbol {x}^{k+1}-\boldsymbol {x}^k} y Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {y}^k=\nabla \boldsymbol {f}(\boldsymbol {x}^{k+1})-\nabla \boldsymbol {f}(\boldsymbol {x}^k)} . Calcular Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {H}_{k+1}} por medio de (19). Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle k\leftarrow k+1.}
| |||
|
Algoritmo. 2 Algoritmo BFGS |
3 Propuesta del nuevo método
Como se vio en la sección anterior, se puede conseguir distintos métodos cuasi-Newton si se cambia el subproblema que determina la matriz de actualización, tal subproblema puede adaptarse a la naturaleza misma de la función. Cuando se considera funciones con error, los métodos anteriores pueden presentar problemas de convergencia o de velocidad, por ello, en esta sección se cambia el subproblema y se le pide a la matriz de actualización que tenga el menor número de condición. En [6], se utiliza también un criterio que se basa en el menor número de condición para el método de gradiente conjugado.
3.1 Motivación
Considere la función Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {\bar{f}}:\mathbb{R}^2\to \mathbb{R}}
definida por
|
(22) |
donde Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {f}(x,y)=0.00001(x^4+y^4)} y Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {e}(x,y)= 0.1\boldsymbol {f}(x,y)sin( x^2 + y^2 )} , el punto inicial Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {x}^0=(3,1)^t} , una tolerancia de Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 10^{-8}}
y la matriz identidad como matriz inicial. En este ejemplo, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {e}(x,y)}
representa un error que emula los diferentes errores que se pueden presentar, tales como error de mediciones, truncamientos, redondeo de la máquina, etc. Los resultados de la implementación se muestran a continuación
|
| Figura 1: Resultados de los métodos DFP y BFGS para el punto inicial Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): \boldsymbol {x}^0=(3,1)^t
. |
Se observa que los métodos DFP y BFGS no convergen a la solución del problema, lo cual es debido a la presencia de errores. Esto nos lleva a plantear la posibilidad de elegir a la matriz Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {B}_{k+1}}
de una manera diferente.
3.2 Planteamiento del problema
Como se vio anteriormente, el método DFP puede ser modificado si se cambia el problema que lleva a la obtención de la actualización Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {B} _{k+1}} . Tomando en cuenta que la presencia de errores provocó que los métodos DFP y BFGS no convergieran, un requerimiento que parece razonable, es pedir que la siguiente matriz tenga el menor número de condición, es decir, que en lugar de resolver (9) se resuelve
|
(23.a) |
|
(23.b) |
donde Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle cond(\boldsymbol {B} )}
está dado por Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \frac{\lambda _n}{\lambda _1}}
, con Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 0<\lambda _1<\cdots{<\lambda}_n}
valores propios de la matriz Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {B} }
(se verá que la matriz obtenida es definida positiva y por lo tanto la dirección de paso será de descenso). Se enfatiza cuál es la razón de usar este método:
Al pedir el menor número de condición, se trata de que la búsqueda de la dirección de descenso por esta vía, sea menos sensible a los errores.
3.3 Caso bidimensional
Supongamos que Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {f}}
es una función de Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \mathbb{R}^2}
a Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \mathbb{R}}
. Consideramos Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {y}^k=(y_1^k,y_2^k)} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {s}^k=(s_1^k,s_2^k)}
y
|
(24) |
En este caso el número de condición está dado por
|
(25) |
donde Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle tr(\boldsymbol {B} )}
y Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle det(\boldsymbol {B} )}
denotan la traza y el determinante de Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {B} }
, respectivamente. Ahora bien, dado que la matriz tiene que ser simétrica y cumplir la ecuación secante, tenemos que
|
|
de donde se obtiene que
|
|
|
|
Sustituyendo las ecuaciones anteriores en (25), se obtiene una función de Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \mathbb{R}}
a Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \mathbb{R}}
, la cual se minimiza calculando la primera derivada (respecto a Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle b_{12}} ) e igualándola a 0. Con lo cual se obtiene que
|
que al sustituirlo en las expresiones de Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle b_{11}}
y Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle b_{22}}
se llega a
|
Con lo cual se obtienen las entradas de la matriz a la cual llamaremos Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {B}_{k+1}^{MCN}} , ya que es la que tiene el menor número de condición (minor condition number), la cual resuelve el subproblema (23). Además, sustituyendo el valor de Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle b_{12}}
en la expresión del determinante, se obtiene que Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {B} _{k+1}^{MCN}}
es definida positiva. Haciendo los cálculos y simplificaciones necesarias se sigue que
|
(29) |
donde Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle (\boldsymbol {z}^k)^t=((\boldsymbol {s}^k)^\perp )^t=(s_2^k,-s_1^k)} . Notemos que, tanto el primer sumando como el segundo son matrices de rango 1.
Con el fin de que en la dirección de búsqueda no se tenga que calcular el inverso de la matriz anterior, denotamos por Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {H}_k=\boldsymbol {B}_k^{-1}} , teniendo así una expresión del inverso de (29)
|
(30) |
donde Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle (\boldsymbol {w}^k)^t=((\boldsymbol {y}^k)^\perp )^t=(y_2^k,-y_1^k)} .
3.3.1 Existencia de la matriz de peso W.
Siguiendo la idea de la construcción del método DFP, lo que se requiere es que Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {B} _{k+1}^{MCN}}
sea la matriz que resuelva el problema (9) con la misma norma Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \left\Vert \boldsymbol {A}\right\Vert _{\boldsymbol {W}}=tr(\boldsymbol {WA}^t\boldsymbol {WA})}
, pero con una matriz de peso adecuada. Así, el problema ahora es encontrar Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {W}}
de tal forma que Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {Wy}^k=\boldsymbol {s}^k}
y
|
Notando que Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {B} }
y Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {B} _k}
son matrices simétricas se tiene que
|
Además, de la restricción Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {Wy}^k=\boldsymbol {s}^k}
y haciendo un análisis análogo al realizado para Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {B} _{k+1}^{MCN}}
se obtiene que
|
Si se denota por Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle c_1=b_{11}-b_{11}^k} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle c_2=b_{12}-b_{12}^k}
y Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle c_3=b_{22}-b_{22}^k}
, se tiene que
|
Obteniendo los puntos estacionarios de la expresión anterior (con respecto a Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle b_{ij}} ), obtenemos que
|
(33) |
Sustituyendo (33) en (31) y (32), se halla a la matriz de peso Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {W}} .
4 Algoritmo
Definimos ahora, un algoritmo que encuentre la solución de (1)
, tolerancia Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \varepsilon } , aproximación del inverso del hessiano Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {H} _0} . Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {x}^*} mínimo de Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {f}}
. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle k\leftarrow 0.} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): \left\Vert \nabla \boldsymbol {f}(\boldsymbol {x}^k)\right\Vert > \varepsilon
Calcular la dirección de búsqueda
Calcular Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {x}^{k+1}=\boldsymbol {x}^k+\alpha _k\boldsymbol {p}^k} , donde Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \alpha _k} es calculado mediante un procedimiento de búsqueda en la línea que satisfaga las condiciones de Wolfe (1). Definir Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {s}^k=\boldsymbol {x}^{k+1}-\boldsymbol {x}^k} y Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {y}^k=\nabla \boldsymbol {f}(\boldsymbol {x}^{k+1})-\nabla \boldsymbol {f}(\boldsymbol {x}^k)} . Calcular Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {H} _{k+1}} por medio de (30). Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle k\leftarrow k+1.}
| |||
|
Algoritmo. 3 Algoritmo MCN |
5 Convergencia
Para analizar la convergencia del método MCN, usaremos los resultados dados en [7], en donde los métodos cuasi-Newton son analizados utilizando técnicas de punto fijo, se demuestran resultados de convergencia y se hallan tasas de convergencia.
En lo que sigue, se dará un resumen de las definiciones y resultados que están en [7]. Con esto, podremos demostrar la convergencia que nos interesa. Aunque los resultados mostrados en esta sección, son utilizados para resolver sistemas de ecuaciones no lineales, estos pueden ser utilizados en la optimización de funciones ya que nos interesa resolver el sistema Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \nabla \boldsymbol {f}(\boldsymbol {x})=\boldsymbol {0}} .
Sean Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle X}
un espacio lineal (vectorial) de dimensión finita, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle D\subset X}
, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \Omega \subset \mathbb{R}^n} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {\phi }:\Omega \times D\to \mathbb{R}^n} . Se consideran los métodos iterativos definidos por
|
(35) |
Definición 1: Decimos que Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {x}\in \Omega }
es un punto fijo de Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {\phi }}
si y sólo si,
|
(36) |
El objetivo de los algoritmos del tipo (35) es el de aproximar los puntos fijos de Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {\phi }} . Notemos que los métodos cuasi-Newton pertenecen a esta clase de métodos, ya que si consideramos Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle D=\lbrace \boldsymbol {B}\in \mathbb{R}^{n\times n}:\boldsymbol {B}\hbox{ es no singular}\rbrace } , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \Omega =\mathbb{R}^n} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {F}:\Omega \to \mathbb{R}^n} , definimos
|
(37) |
Claramente, el conjunto de puntos Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {x} \in \mathbb{R}^n}
tales que Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {x}=\boldsymbol {\phi }(\boldsymbol {x},\boldsymbol {B})}
para todo Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {B}\in D}
, es el conjunto de soluciones de Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {F}(\boldsymbol {x})=\boldsymbol {0}} . Los métodos definidos por Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {x}^{k+1}=\boldsymbol {\phi }(\boldsymbol {x}^k,\boldsymbol {B}_k)}
forman la familia de métodos cuasi-Newton para resolver sistemas de ecuaciones no lineales.
Se establecen condiciones suficientes para que la sucesión definida por (35) esté bien definida y converja a un punto fijo de Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {\phi }}
con una convergencia lineal. Se consideran dos suposiciones, A1 y A2 que se establecen a continuación.
Suposición A1. Sea Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \Omega }
un conjunto abierto y convexo, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \left\vert \cdot \right\vert }
una norma en Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \mathbb{R}^n}
, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle X}
un espacio lineal de dimensión finita, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \left\Vert \cdot \right\Vert }
una norma en Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle X}
, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle D}
un subconjunto abierto de Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle X}
. Supongamos que Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {\phi }:\Omega \times D\to \mathbb{R}^n}
es continua, y que la derivada de Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {\phi }}
con respecto a Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {x}}
existe y es continua, para todo Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {x}\in \Omega }
, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle E\in D} . Denotamos por Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {\phi }'(\boldsymbol {x},\boldsymbol {E})\in \mathbb{R}^{n\times n}}
la matriz Jacobiana de Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {\phi }}
con respecto a Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {x}}
. Supongamos que:
- Existe Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {x}^*\in \Omega }
, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle L,p>0}
tales que
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): \left\vert \boldsymbol {\phi }'(\boldsymbol {x},E)-\boldsymbol {\phi }'(\boldsymbol {x}^*,E)\right\vert \leq L\left\vert \boldsymbol {x}-\boldsymbol {x}^*\right\vert ^p, (38) - Para todo Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle E\in D}
,
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): \boldsymbol {x}^*=\boldsymbol {\phi }(\boldsymbol {x}^*,E). (41)
para todo Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {x}\in \Omega } , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle E\in D} . Esto implica que para todo Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {x},\boldsymbol {z}\in \Omega } , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle E\in D} ,
|
(39) |
donde
|
(40) |
Suposición A2. Existe Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle E_*\in D}
tal que
|
(42) |
Lema 1: Suponga que Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {\phi },\boldsymbol {x}^*,E_*}
satisfacen las Suposiciones A1 y A2. Sea Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle r\in (r^*,1)}
. Entonces, existen Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \overline{\varepsilon }=\overline{\varepsilon }(r), \overline{\delta }=\overline{\delta }(r)}
tales que
|
(43) |
siempre que Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \left\vert \boldsymbol {x}-\boldsymbol {x}^*\right\vert \leq \overline{\varepsilon }} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \left\Vert E-E_*\right\Vert \leq \overline{\delta }} .
Teorema 2: Suponga que Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {\phi },\boldsymbol {x}^*,E_*}
satisfacen las Suposiciones A1 y A2. Sea Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle r\in (r^*,1)}
. Entonces, existen Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \varepsilon =\varepsilon (r), \delta =\delta (r)}
tales que, si Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \left\vert \boldsymbol {x}^0-\boldsymbol {x}^*\right\vert \leq \varepsilon }
y Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \left\Vert E_k-E_*\right\Vert \leq \delta }
para todo Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle k=0,1,\ldots }
, entonces la sucesión generada por (35) está bien definida, converge a Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {x}^*}
y satisface
|
(44) |
para todo Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle k=0,1,2,\ldots } .
Para el caso de los métodos cuasi-Newton, a fin de verificar la condición (42), se debe calcular Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {\phi }'(\boldsymbol {x},E)}
que en este caso está dada por:
|
de donde se tiene que cumplir
|
Si se toma Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {B}_*=\boldsymbol {F}'(\boldsymbol {x}^*)} , se tiene Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle r_*=0} .
Teorema 3: Suponga que Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {\phi },\boldsymbol {x}^*,E_*}
y la sucesión Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \{ \boldsymbol {x}^k\} }
satisfacen las hipótesis del Teorema 2. Suponga además que Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {x}^k\neq \boldsymbol {x}^*}
para todo Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle k=0,1,2,\ldots }
y que
|
(45) |
Entonces
|
(46) |
Corolario 1: Bajo las hipótesis del Teorema 3, si Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \displaystyle \lim _{k\to \infty }\left\Vert E^k-E^*\right\Vert =0} , entonces
|
Teorema 4: Suponga que Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {\phi },\boldsymbol {x}^*,E_*}
satisfacen las Suposiciones A1 y A2, y que Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle r^*=0}
. Suponga que una sucesión es generada por (35) y que, para todo Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle k=0,1,2,\ldots }
|
(47) |
para algún Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle M>0} . Entonces, existe Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \varepsilon{>0}}
tal que si Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \left\vert \boldsymbol {x}^0-\boldsymbol {x}^*\right\vert \leq \varepsilon }
, la sucesión Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \{ \boldsymbol {x}^k\} }
está bien definida, converge a Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {x}^*}
y satisface
|
(48) |
Habíamos visto que en el caso de los métodos cuasi-Newton, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {\phi }'(\boldsymbol {x},\boldsymbol {B})=\boldsymbol {I}-\boldsymbol {B}^{-1}\boldsymbol {F}'(\boldsymbol {x})} . Así,
|
y
|
Por lo tanto, la condición (45) se convierte en
|
Esto es equivalente a
|
(49) |
Esta es la condición de Dennis-Walker de convergencia de los métodos cuasi-Newton a una tasa ideal (ver [8]). Ya que el método MCN es un método cuasi-Newton, se deduce su convergencia. Más aún, la convergencia del MCN está dada por (49).
6 Ejemplos numéricos
En esta sección, se compara numéricamente el método MCN con los métodos DFP y BFGS para dos tipos de funciones. Para ello, se implementaron los tres métodos en el lenguaje de programación MATLAB. Se considera dos casos: con error y sin error en los datos de la función. Para la función del ejemplo 2, el MCN obtuvo mejores resultados que los otros dos, lo que justifica la propuesta.
6.1 Caso sin error
Se consideró la siguiente función para la primera prueba
|
con el punto inicial Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {x}^0=(-10,17)} , una tolerancia de Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 10^{-8}}
y la matriz identidad como matriz inicial. Se obtuvieron los resultados mostrados en la Figura 2 (que corresponde a una ventana emergente del lenguaje de programación):
|
| Figura 2: Resultados de los métodos. |
|
| Figura 3: Gráfica de la función. |
Se puede observar que el método DFP no converge a la solución, mientras que el MCN y el BFGS si lo hacen. Además, se observa que el método BFGS utiliza un menor número de iteraciones. Una posible explicación de este hecho, es que la función de estudio tiene una buena inclinación lo que hace que el Hessiano promedio para el método BFGS arroje mejores resultados que el método MCN. La Tabla 1 muestra los resultados obtenidos usando los programas elaborados para diferentes puntos iniciales. En algunos de estos puntos, el método DFP no converge. Notar que en los puntos en los que converge el método DFP, lo hace en menos iteraciones que el MCN. El Método BFGS fue el que generó los mejores resultados.
| Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {x}^0} | BFGS [tiempo] | DFP [tiempo] | MCN [tiempo] |
| (-10,17) | 61 [10.55] | - | 76 [14.86] |
| (10,-17) | 21 [3.04] | 27 [3.68] | 31 [4.45] |
| (-10,-17) | 17 [2.7] | 18 [2.63] | 37 [5.59] |
| (10,17) | 56 [9.92] | - | 62 [12.94] |
| (2,1) | 12 [1.75] | 15 [2.05] | 17 [2.38] |
| (-2,1) | 10 [1.63] | 11 [1.72] | 28 [4.1] |
| (-2,-1) | 11 [1.71] | 11 [1.69] | 39 [5.94] |
| (2,-1) | 14 [2.11] | 24 [3.33] | 26 [3.61] |
A continuación veremos un ejemplo en la que la función no tiene la buena inclinación mencionada arriba y el método MCN obtiene mejores resultados que los otros dos.
Consideremos ahora la función
|
con el punto inicial Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {x}^0=(2,1)^T} , una tolerancia de Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 10^{-8}}
y la matriz identidad como matriz inicial. Los resultados de la implementación se muestran a continuación
|
| Figura 4: Resultados de los tres métodos utilizados. El MCN utiliza un menor número de iteraciones y consume menos tiempo de cómputo. |
|
| Figura 5: Gráfica de la función Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): \boldsymbol {f}(x,y)=0.00001(x^4+y^4)
. |
| Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {x}^0} | BFGS [tiempo] | DFP [tiempo] | MCN [tiempo] |
| (2,1) | 32 [4.39] | 526 [73] | 13 [2.15] |
| (-2,1) | 31 [3.95] | 936 [129.07] | 13 [1.75] |
| (-2,-1) | 32 [4.49] | 526 [70.42] | 13 [2.29] |
| (2,-1) | 31 [4.02] | 936 [132.79] | 13 [1.88] |
| (3,1) | 24 [3.69] | 977 [137.59] | 15 [2.94] |
6.2 Caso con error
Consideremos la función (52) del ejemplo anterior, pero le agregaremos un error, por lo que la función a minimizar ahora es
|
(54) |
donde Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {e}(x,y)}
está definido por
|
(55) |
Se hizo uso del mismo punto inicial Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {x}^0=(2,1)^t} , tolerancia Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 10^{-8}}
y matriz inicial. Los resultados obtenidos fueron los siguientes
|
| Figura 6: Resultados de los métodos. |
|
| Figura 7: Gráfica de la función Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): \boldsymbol {\tilde{f}}(x,y)=\boldsymbol {f}(x,y)+\boldsymbol {e}(x,y)
. |
| Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {x}^0} | BFGS [tiempo] | DFP [tiempo] | MCN [tiempo] |
| (2,1) | 30 [4.8] | - | 13 [2.36] |
| (-2,1) | 31 [4.81] | - | 13 [2.35] |
| (-2,-1) | 29 [4.41] | - | 14 [3.09] |
| (2,-1) | 28 [4.71] | 372 [90.37] | 14 [2.41] |
| (3,1) | 33 [5.42] | - | 15 [2.71] |
En este caso, puede observarse que el método MCN fue que que obtuvo mejores resultados, ya que converge en aproximadamente la mitad de iteraciones que el método BFGS, mientras que el método DFP en la mayoría de los casos no converge y en caso de converger, lo hace en número de iteraciones mucho mayor. Además, consume aproximadamente la mitad de tiempo de cómputo.
Consideramos la misma función (54), donde Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {f}(x,y)}
está definido por (52) y ahora
|
(56) |
Se consideró el punto inicial Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {x}^0=(2,1)^t} , una tolerancia de Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 10^{-8}}
y la matriz identidad como matriz inicial. En la Figura 8 se muestran los resultados obtenidos.
|
| Figura 8: Resultados de los métodos considerando error. |
|
| Figura 9: Gráfica de la función considerando errores. |
| Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {x}^0} | BFGS [tiempo (seg)] | DFP [tiempo (seg)] | MCN [tiempo (seg)] |
| (2,1) | 32 [5.47] | 729 [125.09] | 14 [2.72] |
| (1,2) | 32 [5.53] | 371 [70.48] | 14 [3.14] |
| (3,1) | - | - | 15 [2.63] |
| (-3,1) | 29 [4.99] | 218 [51] | 13 [3.04] |
| (3,-1) | 29 [4.91] | 218 [54.7] | 13 [6.33] |
| (-3,-1) | - | - | 15 [2.75] |
De los ejemplos vistos, podemos notar que el método MCN tiene un mejor comportamiento (incluso mejor que el BFGS) en los casos donde hay presencia de errores o la función objetivo es "muy plana cerca del mínimo. El tipo de error considerado tiene por objetivo ilustrar el desempeño de los métodos analizados aquí ya que puede considerarse una buena representación de los errores cometidos en la práctica. En [9], se considera que tanto la función como su gradiente tienen error acotado en la norma uniforme. Este caso, podría considerarse para probar el desempeño del MCN.
7 Aplicación a la solución numérica de sistemas de ecuaciones diferenciales ordinarias
Como se comentó anteriormente, los sistemas no lineales aparecen en la solución numérica de sistemas de ecuaciones diferenciales no lineales. En esta sección, vamos a considerar el caso de un sistema de la forma:
|
(57) |
|
(58) |
con condiciones iniciales
|
(59) |
Las funciones Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {f}_1}
y Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {f}_2}
son suficientemente suaves. Supongamos que las funciones Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {f}_1}
y Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {f}_2}
cumplen las condiciones del Teorema de Existencia y Unicidad dado en [10], por lo cual el problema de valor inicial (57)-(59) tiene una única solución en algún intervalo del eje Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle t}
que contiene a Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle t_0}
. Deseamos determinar valores aproximados Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {y}_1^1,\boldsymbol {y}_1^2,\ldots ,\boldsymbol {y}_1^n,\ldots } y Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {y}_2^1,\boldsymbol {y}_2^2,\ldots ,\boldsymbol {y}_2^n,\ldots }
de las soluciones Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {y}_1=\boldsymbol {\phi }(t)}
, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {y}_2=\boldsymbol {\Phi }(t)}
en los puntos Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle t_n=t_0+nh}
, con Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle n=1,2,\ldots } .
En notación vectorial, el problema de valor inicial (57)-(59) puede ser escrito como
|
(60) |
donde Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {y}}
es un vector con componentes Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {y}_1}
y Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {y}_2}
, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {f}}
es el vector de funciones con componentes Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {f}_1}
y Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {f}_2}
y Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {y}_0}
es el vector con componentes Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle y_1^0,y_2^0}
.
Uno de los métodos que se utiliza para hallar la solución numérica del sistema (60), es el método de Euler que consiste en considerar la fórmula
|
(61) |
Las condiciones iniciales son usadas para determinar Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {f}_0} , el cual es el vector tangente a la gráfica de la solución Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {y}=\boldsymbol {\Phi }(t)}
en el plano Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle y_1y_2}
. Nos movemos en dirección de este vector tangente por un paso de tiempo Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle h}
con el fin de encontrar el siguiente punto Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {y}_1}
. Después, calculamos un nuevo vector tangente Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {f}_1} , nos movemos a lo largo de éste por un paso de tiempo Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle h}
para encontrar Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {y}_2}
, y así sucesivamente.
Una variación del método de Euler puede ser obtenido de la siguiente manera. Dado que Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {y}=\boldsymbol {\Phi }(t)}
es una solución del problema de valor inicial (60), obtenemos
|
(62) |
Aproximando la derivada en (62) por el cociente de diferencias hacia atrás Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \dfrac{\boldsymbol {\phi }(t_n)-\boldsymbol {\phi }(t_{n-1})}{h},}
obteniendo
|
o bien
|
(63) |
y Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {y}_0}
, longitud de paso Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle h} y número de pasos Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle m}
. Aproximación Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {y}} . Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): n desde 1 hasta Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): m
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle t_n=t_{n-1}+h} . Resolver (63).
|
|
Algoritmo. 4 El Método de Euler Implícito |
Aunque la implementación del Algoritmo 4 parece sencilla, tenemos el problema de resolver el sistema de ecuaciones (63). Es en este momento donde hacemos uso del método MCN. El sistema de ecuaciones podemos plantearlo como un problema de optimización haciendo
|
y trabajando con el problema de optimización
|
Se compara el desempeño del MCN y del BFGS en el Método de Euler Implícito (MEI). Para ello, se elaboraron programas en el sistema MATLAB para resolver problemas de valores iniciales por medio del MEI. En todos los casos se usó Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {y}_{n-1}}
como punto inicial, la matriz identidad como matriz inicial y una tolerancia de Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 10^{-8}}
.
Consideremos el problema dado en [1], el cual involucra un sistema lineal de coeficientes constantes no homogéneo de dimensión 2.
|
(64) |
El problema tienen la siguiente solución exacta
|
(65) |
Se tomaron un total de 1 000 puntos de la partición del intervalo temporal Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle [0,10]} . En la Figura 10a, se muestran la solución exacta del sistema y la obtenida usando el método BFGS en el MEI. En la Figura 10b, se muestran la solución exacta del sistema y la obtenida usando el MCN. Obsérvese que las aproximaciones son tan cercanas a la solución, que las gráficas prácticamente están sobrepuestas.
En este ejemplo, el método MCN hizo un promedio de 3.9310 iteraciones, tardando en promedio 0.2775 segundos en cada paso para la resolución del sistema, mientras que el método BFGS hace un promedio de 3.9670 iteraciones, tardando en promedio 0.2783 segundos en cada paso para la resolución del sistema. Así, el MCN tiene un mejor desempeño que el BFGS. Nótese que el error relativo es mayor en los puntos en los que se alcanzan máximo y mínimos.
|
|
| (a) Solución con el método BFGS. | (b) Solución con el método MCN. |
| Figura 10: Solución numérica encontrada usando los dos métodos. | |
|
|
| (a) Error absoluto del método BFGS. | (b) Error absoluto del método MCN. |
|
|
| (c) Error relativo del método BFGS. | (d) Error relativo del método MCN. |
| Figura 11: Error de los métodos en cada componente de la solución. | |
Ahora, consideremos el problema no lineal dado en [1].
|
(66) |
El problema tienen la siguiente solución exacta
|
(67) |
Se tomaron un total de 2 000 puntos de la partición del intervalo temporal Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle [1.5,1.7]} . En la Figura 12a, se muestran la solución exacta del sistema y la obtenida usando el método BFGS en el MEI. En la Figura 12b, se muestran la solución exacta del sistema y la obtenida usando el MCN.
|
|
| (a) Solución con el método BFGS. | (b) Solución con el método MCN. |
| Figura 12: Solución numérica encontrada usando los dos métodos. | |
|
|
| (a) Error absoluto del método BFGS. | (b) Error absoluto del método MCN. |
|
|
| (c) Error relativo del método BFGS. | (d) Error relativo del método MCN. |
| Figura 13: Error de los métodos en cada componente de la solución. | |
En este ejemplo, el método MCN hizo un promedio de 2.4345 iteraciones, tardando en promedio 0.1846 segundos en cada paso para la resolución del sistema, mientras que el método BFGS hace un promedio de 2.7170 iteraciones, tardando en promedio 0.1855 segundos en cada paso para la resolución del sistema. Así, el MCN tuvo un mejor desempeño que el BFGS.
Ahora, consideremos el problema no lineal
|
(68) |
con Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle a=10^{-4}} . El problema tienen la siguiente solución exacta
|
(69) |
Se tomaron un total de 1 000 puntos de la partición del intervalo temporal Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle [1,2]} . En la Figura 14a, se muestran la solución exacta del sistema y la obtenida usando el método BFGS en el MEI. En la Figura 14b, se muestran la solución exacta del sistema y la obtenida usando el MCN.
|
|
| (a) Solución con el método BFGS. | (b) Solución con el método MCN. |
| Figura 14: Solución numérica encontrada usando los dos métodos. | |
En este ejemplo, el método MCN hizo un promedio de 1 iteración, tardando en promedio 0.3006 segundos en cada paso para la resolución del sistema, mientras que el método BFGS hace un promedio de 1 iteración, tardando en promedio 0.2907 segundos en cada paso para la resolución del sistema. Obsérvese que, como en los casos anteriores, las aproximaciones son tan cercanas a la solución, que las gráficas prácticamente están sobrepuestas.
En la Figura 15, se muestran los errores, tanto absolutos como relativos, cometidos por los dos métodos en cada entrada de la solución del sistema. Se observa que el desempeño es similar en ambos métodos.
|
|
| (a) Error absoluto del método BFGS. | (b) Error absoluto del método MCN. |
|
|
| (c) Error relativo del método BFGS. | (d) Error relativo del método MCN. |
| Figura 15: Error de los métodos en cada componente de la solución. | |
Ahora, consideremos el ejemplo dado en [10] dado por un modelo de Lotka-Volterra
|
(70) |
donde Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {y}_1}
y Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \boldsymbol {y}_2}
denotan la población de presa y depredador, respectivamente. Se tomaron un total de 7 000 puntos de la partición del intervalo temporal Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle [0,30]}
. En la Figura 16a, se muestra la solución obtenida usando el método BFGS en el MEI. En la Figura 16b, se muestra la solución obtenida usando el MCN.
|
|
| (a) Solución con el método BFGS. | (b) Solución con el método MCN. |
| Figura 16: Solución numérica encontrada usando los dos métodos. | |
En este ejemplo, el método MCN hizo un promedio de 2.8163 iteraciones, tardando en promedio 0.4433s en cada paso para la resolución del sistema, mientras que el método BFGS hace un promedio de 2.6409 iteraciones, tardando en promedio 0.4064s en cada paso para la resolución del sistema.
8 Conclusiones
Se propone un método cuasi-Newton que tiene como criterio minimizar el número de condición de la matriz de actualización. Esto con la intención de manejar la sensibilidad ante errores en los datos. Se da una fórmula explícita para la actualización en el caso bidimensional. Se ilustra con ejemplos la factibilidad del método. Se distingue el caso sin error y con error. En el primero de ellos, puede observarse que, aunque todos los métodos convergen a la solución, el método DFP lo hace en un número mayor de iteraciones. Esto es acorde con lo reportado en la literatura. Por otra parte, los métodos BFGS y MCN intercambian su rol de mejor opción, dependiendo del tipo de función que se esté minimizando. Para el Ejemplo 1, el método BFGS requiere menos iteraciones que el MCN pero para el Ejemplo 2, sucede lo contrario. Pasando ahora al caso con error, el método MCN converge con menos iteraciones en ambos casos presentados. Aún más, con algunos puntos iniciales no convergen ni el método DFP ni el BFGS. Así, se muestra que el método puede mejorar los resultados tanto en iteraciones como en convergencia para cierta clase de funciones, a saber, aquellas en las que la matriz del sistema para la actualización es mal condicionada.
Se implementó el MCN en el método implícito de Euler para resolver sistema de dos ecuaciones diferenciales ordinarias no lineales. Se comparó su desempeño con el BFGS en el mismo método implícito de Euler con cuatro ejemplos encontrándose que los dos métodos obtienen resultados similares tanto en número de iteraciones como tiempo de cómputo.
BIBLIOGRAFÍA
[1] Lambert, J. D. (1991) "Numerical Methods for Ordinary Differential Systems: The Initial Value Problem". John Wiley & Sons, Inc.
[2] Davidon, W C. (1959) "VARIABLE METRIC METHOD FOR MINIMIZATION", Volume. Technical Report ANL–5990 (revised), Argonne National Laboratory
[3] Fletcher, R. and Powell, M. J. D. (1963) "A Rapidly Convergent Descent Method for Minimization", Volume 6. The Computer Journal 2 163-168
[4] Nocedal, Jorge and Wright, Stephen J. (2006) "Numerical optimization". Springer, 2nd Edition
[5] M. Bazaraa and H. Sherali and C. M. Shetty. (2006) "Unconstrained Optimization". Nonlinear Programming. John Wiley & Sons, Ltd 343-467
[6] Neculai Andrei. (2020) "Nonlinear Conjugate Gradient Methods for Unconstrained Optimization", Volume. Springer International Publishing, 1st Edition
[7] Martínez, José Mario. (1992) "Fixed-Point Quasi-Newton Methods", Volume 29. SIAM Journal on Numerical Analysis 5 1413-1434
[8] J. E. Dennis and Homer F. Walker. (1981) "Convergence Theorems for Least-Change Secant Update Methods", Volume 18. Society for Industrial and Applied Mathematics. SIAM Journal on Numerical Analysis 6 949–987
[9] Xie, Yuchen and Byrd, Richard H. and Nocedal, Jorge. (2020) "Analysis of the BFGS Method with Errors", Volume 30. SIAM Journal on Optimization 1 182-209
[10] William E. Boyce and Richard C. DiPrima. (2000) "Elementary differential equations and boundary value problems.". Elementary differential equations and boundary value problems. John Wiley, 7th Edition
[11] Fletcher, R. (2000) "Newton-Like Methods". Practical Methods of Optimization. John Wiley & Sons, Ltd 44-79
Document information
Published on 12/11/21
Submitted on 30/10/21
Volume 5, 2021
Licence: CC BY-NC-SA license
Share this document
Keywords
claim authorship
Are you one of the authors of this document?