You do not have permission to edit this page, for the following reason:
You can view and copy the source of this page.
x
1
==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 .==2
3
'''José Jacobo Oliveros Oliveros, Julio Andrés Acevedo Vázquez, Juan Alberto Escamilla Reyna '''4
5
==Resumen==6
7
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.8
9
'''Keywords:''' cuasi-Newton, condition number.10
11
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.12
13
'''Palabras clave:''' cuasi-Newton, número de condición.14
15
==1 Introducción==16
17
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 BFD (por sus siglas en inglés Backward Differentiation Formulas) <span id='citeF-1'></span>[[#cite-1|[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.18
19
A continuación, se presenta el planteamiento del problema de minimización que interesa en este trabajo.20
21
Sea <math display="inline">\boldsymbol {f}:\mathbb{R}^n\to \mathbb{R}</math> una función suave. Consideremos el siguiente problema22
23
<span id="eq-1"></span>24
{| class="formulaSCP" style="width: 100%; text-align: left;" 25
|-26
| 27
{| style="text-align: left; margin:auto;width: 100%;" 28
|-29
| style="text-align: center;" | <math>\min \boldsymbol {f}(\boldsymbol {x});</math>30
|-31
| style="text-align: center;" | <math> \hbox{ s. a} \boldsymbol {x}\in \mathbb{R}^n. </math>32
|}33
| style="width: 5px;text-align: right;white-space: nowrap;" | (1)34
|}35
36
El primer método cuasi-Newton (denotado por DFP) fue creado por Davidon, Fletcher y Powell <span id='citeF-2'></span><span id='citeF-3'></span>[[#cite-2|[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 <math display="inline">\boldsymbol {x}^k</math>. Tenemos la siguiente notación: <math display="inline">\boldsymbol {f}^k=\boldsymbol {f}(\boldsymbol {x}^k)</math>, <math display="inline">\nabla \boldsymbol {f}^k=\nabla \boldsymbol {f}(\boldsymbol {x}^k)</math> y <math display="inline">\nabla ^2\boldsymbol {f}^k=\nabla ^2\boldsymbol {f}(\boldsymbol {x}^k)</math> donde <math display="inline">\nabla ^2\boldsymbol {f}</math> denota el hessiano de la función <math display="inline">\boldsymbol {f}</math>, por lo que la aproximación está dada por37
38
<span id="eq-2"></span>39
{| class="formulaSCP" style="width: 100%; text-align: left;" 40
|-41
| 42
{| style="text-align: left; margin:auto;width: 100%;" 43
|-44
| style="text-align: center;" | <math>\boldsymbol {m}_k(\boldsymbol {p})=\boldsymbol {f}^k+(\nabla \boldsymbol {f}^k)^t \boldsymbol {p}+\frac{1}{2}\boldsymbol {p}^t\boldsymbol {B}_k\boldsymbol {p}, </math>45
|}46
| style="width: 5px;text-align: right;white-space: nowrap;" | (2)47
|}48
49
donde <math display="inline">\boldsymbol {B_k}</math> es una matriz simétrica definida positiva de tamaño <math display="inline">n\times n</math>, que se actualizará en cada iteración. La matriz <math display="inline">\boldsymbol {B_K}</math> no es el hessiano de la función <math display="inline">\boldsymbol {f}</math>, pero es una aproximación de ella. Notemos que <math display="inline">\boldsymbol {m}_k(\boldsymbol {0})=\boldsymbol {f}^k</math> y dado que <math display="inline">\boldsymbol {m}_k</math> es una función convexa, alcanza el mínimo en50
51
<span id="eq-3"></span>52
{| class="formulaSCP" style="width: 100%; text-align: left;" 53
|-54
| 55
{| style="text-align: left; margin:auto;width: 100%;" 56
|-57
| style="text-align: center;" | <math>\boldsymbol {p}^k=-\boldsymbol {B}_k^{-1}\nabla \boldsymbol {f}^k, </math>58
|}59
| style="width: 5px;text-align: right;white-space: nowrap;" | (3)60
|}61
62
el cual será usado en la nueva iteración63
64
<span id="eq-4"></span>65
{| class="formulaSCP" style="width: 100%; text-align: left;" 66
|-67
| 68
{| style="text-align: left; margin:auto;width: 100%;" 69
|-70
| style="text-align: center;" | <math>\boldsymbol {x}^{k+1}=\boldsymbol {x}^k+\alpha _k\boldsymbol {p}^k, </math>71
|}72
| style="width: 5px;text-align: right;white-space: nowrap;" | (4)73
|}74
75
donde la longitud de paso <math display="inline">\alpha _k</math> se escoge de tal forma que cumpla las condiciones de Wolfe.76
77
Un requerimiento que parece razonable pedir en <math display="inline">\boldsymbol {B}_{k+1}</math> es que el gradiente de <math display="inline">\boldsymbol {m}_{k+1}</math> debe coincidir con el gradiente de la función objetivo <math display="inline">\boldsymbol {f}</math> en al menos dos iteraciones <math display="inline">\boldsymbol {x}^k</math> y <math display="inline">\boldsymbol {x}^{k+1}</math>. Obsérvese que <math display="inline">\nabla \boldsymbol {m}_{k+1}(\boldsymbol {0})=\nabla \boldsymbol {f}^{k+1}</math>, así que la segunda de estas condiciones se satisface. La primera condición puede ser escrita como78
79
<span id="eq-5"></span>80
{| class="formulaSCP" style="width: 100%; text-align: left;" 81
|-82
| 83
{| style="text-align: left; margin:auto;width: 100%;" 84
|-85
| style="text-align: center;" | <math>\boldsymbol {B}_{k+1}(\boldsymbol {x}^{k+1}-\boldsymbol {x}^k) = \nabla \boldsymbol {f}^{k+1}-\nabla \boldsymbol {f}^k. </math>86
|}87
| style="width: 5px;text-align: right;white-space: nowrap;" | (5)88
|}89
90
Para simplificar la ecuación anterior se definen los vectores <span id="eq-6"></span>91
92
<span id="eq-6.a"></span>93
{| class="formulaSCP" style="width: 100%; text-align: left;" 94
|-95
| 96
{| style="text-align: left; margin:auto;width: 100%;" 97
|-98
| style="text-align: center;" | <math>\boldsymbol {s}^k = \boldsymbol {x}^{k+1}-\boldsymbol {x}^k = \alpha _k\boldsymbol {p}^k; </math>99
|}100
| style="width: 5px;text-align: right;white-space: nowrap;" | (6.a)101
|}102
103
<span id="eq-6.b"></span>104
{| class="formulaSCP" style="width: 100%; text-align: left;" 105
|-106
| 107
{| style="text-align: left; margin:auto;width: 100%;" 108
|-109
| style="text-align: center;" | <math>\boldsymbol {y}^k = \nabla \boldsymbol {f}^{k+1}-\nabla \boldsymbol {f}^k. </math>110
|}111
| style="width: 5px;text-align: right;white-space: nowrap;" | (6.b)112
|}113
114
Así, la ecuación [[#eq-5|(5)]] se reescribe como115
116
<span id="eq-7"></span>117
{| class="formulaSCP" style="width: 100%; text-align: left;" 118
|-119
| 120
{| style="text-align: left; margin:auto;width: 100%;" 121
|-122
| style="text-align: center;" | <math>\boldsymbol {B}_{k+1}\boldsymbol {s}^k=\boldsymbol {y}^k, </math>123
|}124
| style="width: 5px;text-align: right;white-space: nowrap;" | (7)125
|}126
127
la cual es conocida como la ''ecuación secante''.128
129
Del hecho de que la matriz <math display="inline">\boldsymbol {B}_{k+1}</math> es definida positiva y por la ecuación secante, se tiene que130
131
<span id="eq-8"></span>132
{| class="formulaSCP" style="width: 100%; text-align: left;" 133
|-134
| 135
{| style="text-align: left; margin:auto;width: 100%;" 136
|-137
| style="text-align: center;" | <math>(\boldsymbol {s}^k)^t\boldsymbol {y}^k>0. </math>138
|}139
| style="width: 5px;text-align: right;white-space: nowrap;" | (8)140
|}141
142
La desigualdad anterior es conocida como la ''condición de curvatura''.143
144
Cuando la función es fuertemente convexa, la condición de curvatura se cumplirá, para cualesquiera dos puntos <math display="inline">\boldsymbol {x}^{k+1}</math> y <math display="inline">\boldsymbol {x}^k</math>, pero no siempre se cumplirá cuando la función no es convexa. En este último caso, se tiene que forzar a que se cumpla [[#eq-8|(8)]] imponiendo las condiciones de Wolfe o las condiciones fuertes de Wolfe en <math display="inline">\alpha _k</math> <span id='citeF-4'></span>[[#cite-4|[4]]].145
146
Cuando la condición de curvatura se cumple, la ecuación secante [[#eq-7|(7)]] tiene ''infinitas soluciones'', ya que hay <math display="inline">\frac{n(n+1)}{2}</math> grados de libertad en una matriz simétrica y la ecuación secante representa <math display="inline">n</math> condiciones y hay <math display="inline">n</math> 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 <math>\boldsymbol {B}_{k+1}</math>'', lo que da la posibilidad de proponer diferentes métodos que se adapten al problema que se está estudiando.147
148
==2 Descripción de los métodos DFP y BFGS==149
150
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.151
152
===2.1 El método DFP===153
154
Una manera de determinar <math display="inline">\boldsymbol {B}_{k+1}</math> es pidiendo que, entre todas las matrices simétricas que cumplen la ecuación secante, <math display="inline">\boldsymbol {B}_{k+1}</math> debe ser la más cercana a la matriz actual <math display="inline">\boldsymbol {B}_k</math>, en otras palabras, tenemos que resolver el siguiente subproblema <span id="eq-9"></span>155
156
<span id="eq-9.a"></span>157
{| class="formulaSCP" style="width: 100%; text-align: left;" 158
|-159
| 160
{| style="text-align: left; margin:auto;width: 100%;" 161
|-162
| style="text-align: center;" | <math>\min _{\boldsymbol {B}} \left\Vert \boldsymbol {B}-\boldsymbol {B}_k\right\Vert ; </math>163
|}164
| style="width: 5px;text-align: right;white-space: nowrap;" | (9.a)165
|}166
167
<span id="eq-9.b"></span>168
{| class="formulaSCP" style="width: 100%; text-align: left;" 169
|-170
| 171
{| style="text-align: left; margin:auto;width: 100%;" 172
|-173
| style="text-align: center;" | <math>\hbox{s. a } \boldsymbol {B} =\boldsymbol {B}^t;</math>174
|-175
| style="text-align: center;" | <math> \boldsymbol {Bs}^k =\boldsymbol {y}^k, </math>176
|}177
| style="width: 5px;text-align: right;white-space: nowrap;" | (9.b)178
|}179
180
donde <math display="inline">\boldsymbol {s}^k</math> y <math display="inline">\boldsymbol {y}^k</math> satisfacen la condición de curvatura y <math display="inline">\boldsymbol {B}_k</math> es una matriz simétrica definida positiva. Muchas normas pueden ser usadas en [[#eq-9.a|(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''181
182
<span id="eq-10"></span>183
{| class="formulaSCP" style="width: 100%; text-align: left;" 184
|-185
| 186
{| style="text-align: left; margin:auto;width: 100%;" 187
|-188
| style="text-align: center;" | <math>\left\Vert \boldsymbol {A}\right\Vert _{\boldsymbol {W}}^2=tr\left(\boldsymbol {WA}^t\boldsymbol {WA}\right). </math>189
|}190
| style="width: 5px;text-align: right;white-space: nowrap;" | (10)191
|}192
193
El peso <math display="inline">\boldsymbol {W}</math> puede ser escogido como cualquier matriz que satisfaga la relación <math display="inline">\boldsymbol {Wy}^k=\boldsymbol {s}^k</math>. Se asume <math display="inline">\boldsymbol {W}=\overline{\boldsymbol {G}}_k^{-1}</math>, donde <math display="inline">\overline{\boldsymbol {G}}_k</math> es el hessiano promedio, dado por194
195
<span id="eq-11"></span>196
{| class="formulaSCP" style="width: 100%; text-align: left;" 197
|-198
| 199
{| style="text-align: left; margin:auto;width: 100%;" 200
|-201
| style="text-align: center;" | <math>\overline{\boldsymbol {G}}_k=\int _0^1 \nabla ^2 \boldsymbol {f}(\boldsymbol {x}^k+\tau \alpha _k \boldsymbol {p}^k)d\tau{.} </math>202
|}203
| style="width: 5px;text-align: right;white-space: nowrap;" | (11)204
|}205
206
Fácilmente puede verificarse que <math display="inline">\overline{\boldsymbol {G}}_k^{-1}\boldsymbol {y}^k=\boldsymbol {s}^k</math>.207
208
Con la norma y matriz de peso descritas arriba, la única solución de [[#eq-9|(9)]] es209
210
<span id="eq-12"></span>211
{| class="formulaSCP" style="width: 100%; text-align: left;" 212
|-213
| 214
{| style="text-align: left; margin:auto;width: 100%;" 215
|-216
| style="text-align: center;" | <math>\boldsymbol {B}_{k+1}^{DFP}=(\boldsymbol {I}-\gamma _k\boldsymbol {y}^k(\boldsymbol {s}^k)^t)\boldsymbol {B}_k(\boldsymbol {I}-\gamma _k\boldsymbol {s}^k(\boldsymbol {y}^k)^t)+\gamma _k\boldsymbol {y}^k(\boldsymbol {y}^k)^t, </math>217
|}218
| style="width: 5px;text-align: right;white-space: nowrap;" | (12)219
|}220
221
donde <math display="inline">\gamma _k=\dfrac{1}{(\boldsymbol {y}^k)^t\boldsymbol {s}^k}.</math>222
223
Esta fórmula es llamada la ''fórmula de actualización DFP'', ya que fue propuesta por Davidon en 1959 <span id='citeF-2'></span>[[#cite-2|[2]]], y posteriormente estudiada, implementada y popularizada por Fletcher y Powell <span id='citeF-3'></span>[[#cite-3|[3]]].224
225
Sea <math display="inline">\boldsymbol {H}_k=\boldsymbol {B}_k^{-1}</math>. Usando la fórmula de Sherman-Morrison-Woodbury <span id='citeF-4'></span>[[#cite-4|[4]]] y la ecuación [[#eq-12|(12)]] se sigue que226
227
<span id="eq-13"></span>228
{| class="formulaSCP" style="width: 100%; text-align: left;" 229
|-230
| 231
{| style="text-align: left; margin:auto;width: 100%;" 232
|-233
| style="text-align: center;" | <math>\boldsymbol {H}_{k+1}^{DFP}=\boldsymbol {H}_k-\frac{\boldsymbol {H}_k\boldsymbol {y}^k(\boldsymbol {y}^k)^t\boldsymbol {H}_k}{(\boldsymbol {y}^k)^t\boldsymbol {H}_k\boldsymbol {y}^k}+ \frac{\boldsymbol {s}^k(\boldsymbol {s}^k)^t}{(\boldsymbol {y}^k)^t\boldsymbol {s}^k}. </math>234
|}235
| style="width: 5px;text-align: right;white-space: nowrap;" | (13)236
|}237
238
Esto resulta útil, ya que nos permite calcular la dirección de búsqueda simplemente con una multiplicación matriz-vector.239
240
Nótese que los últimos dos términos del lado derecho de [[#eq-13|(13)]] son matrices de rango 1, así <math display="inline">\boldsymbol {H}_k</math> 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.241
242
243
{| style="margin: 1em auto;border: 1px solid darkgray;"244
|-245
|246
:Punto inicial <math display="inline">\boldsymbol {x}^0</math>, tolerancia <math display="inline">\varepsilon </math>, aproximación del inverso del hessiano <math display="inline">\boldsymbol {H}_0</math>. <math display="inline">\boldsymbol {x}^*</math> mínimo de <math display="inline">\boldsymbol {f}</math>. <math display="inline">k\leftarrow 0.</math> <math>\left\Vert \nabla \boldsymbol {f}(\boldsymbol {x}^k)\right\Vert > \varepsilon </math>Calcular la dirección de búsqueda247
248
{| class="formulaSCP" style="width: 100%; text-align: left;" 249
|-250
| 251
{| style="text-align: left; margin:auto;width: 100%;" 252
|-253
| style="text-align: center;" | <math>\boldsymbol {p}^k=-\boldsymbol {H}_k\nabla \boldsymbol {f}(\boldsymbol {x}^k). </math>254
|}255
| style="width: 5px;text-align: right;white-space: nowrap;" | (14)256
|}257
258
Calcular <math display="inline">\boldsymbol {x}^{k+1}=\boldsymbol {x}^k+\alpha _k\boldsymbol {p}^k</math>, donde <math display="inline">\alpha _k</math> es calculado mediante un procedimiento de búsqueda en la línea que satisfaga las condiciones de Wolfe, <span id="eq-15"></span>259
260
261
<span id="eq-15.a"></span>262
{| class="formulaSCP" style="width: 100%; text-align: left;" 263
|-264
| 265
{| style="text-align: left; margin:auto;width: 100%;" 266
|-267
| style="text-align: center;" | <math>\boldsymbol {f}(\boldsymbol {x}_k+\alpha \boldsymbol {p}_k) \leq \boldsymbol {f}(\boldsymbol {x}_k)+c_1\alpha \nabla \boldsymbol {f}_k^t\boldsymbol {p}_k, </math>268
|}269
| style="width: 5px;text-align: right;white-space: nowrap;" | (15.a)270
|}271
272
273
274
<span id="eq-15.b"></span>275
{| class="formulaSCP" style="width: 100%; text-align: left;" 276
|-277
| 278
{| style="text-align: left; margin:auto;width: 100%;" 279
|-280
| style="text-align: center;" | <math>\nabla \boldsymbol {f}(\boldsymbol {x}_k+\alpha _k \boldsymbol {p}_k)^T\boldsymbol {p}_k \geq c_2 \nabla \boldsymbol {f}_k^t\boldsymbol {p}_k, </math>281
|}282
| style="width: 5px;text-align: right;white-space: nowrap;" | (15.b)283
|}284
285
con <math display="inline">0<c_1<c_2<1.</math> Definir <math display="inline">\boldsymbol {s}^k=\boldsymbol {x}^{k+1}-\boldsymbol {x}^k</math> y <math display="inline">\boldsymbol {y}^k=\nabla \boldsymbol {f}(\boldsymbol {x}^{k+1})-\nabla \boldsymbol {f}(\boldsymbol {x}^k)</math>. Calcular <math display="inline">\boldsymbol {H}_{k+1}</math> por medio de [[#eq-13|(13)]]. <math display="inline">k\leftarrow k+1.</math> 286
287
288
|-289
| style="text-align: center; font-size: 75%;"|290
<span id='algorithm-1'></span>'''Algoritmo. 1''' Algoritmo DFP291
|}292
293
===2.2 El método BFGS===294
295
La fórmula del método BFGS puede ser derivado haciendo un simple cambio en el argumento que lleva a [[#eq-12|(12)]]. Las condiciones impuestas en las aproximaciones del hessiano <math display="inline">\boldsymbol {B}_k</math>, pueden ser impuestas en sus inversas <math display="inline">\boldsymbol {H}_k</math>. Por lo tanto, la actualización <math display="inline">\boldsymbol {H}_{k+1}</math> debe ser simétrica, definida positiva, y satisfacer la ecuación secante [[#eq-7|(7)]], ahora escrita como <math display="inline">\boldsymbol {H}_{k+1}\boldsymbol {y}^k=\boldsymbol {s}^k.</math>296
297
La condición de la cercanía a <math display="inline">\boldsymbol {H}_k</math> es ahora especificada de forma análoga a [[#eq-9|(9)]]298
299
<span id="eq-16"></span>300
301
<span id="eq-16.a"></span>302
{| class="formulaSCP" style="width: 100%; text-align: left;" 303
|-304
| 305
{| style="text-align: left; margin:auto;width: 100%;" 306
|-307
| style="text-align: center;" | <math>\min _{\boldsymbol {H}} \left\Vert \boldsymbol {H}-\boldsymbol {H}_k\right\Vert ; </math>308
|}309
| style="width: 5px;text-align: right;white-space: nowrap;" | (16.a)310
|}311
312
<span id="eq-16.b"></span>313
{| class="formulaSCP" style="width: 100%; text-align: left;" 314
|-315
| 316
{| style="text-align: left; margin:auto;width: 100%;" 317
|-318
| style="text-align: center;" | <math>\hbox{s. a } \boldsymbol {H} =\boldsymbol {H}^t;</math>319
|-320
| style="text-align: center;" | <math> \boldsymbol {Hy}^k =\boldsymbol {s}^k. </math>321
|}322
| style="width: 5px;text-align: right;white-space: nowrap;" | (16.b)323
|}324
325
La norma considerada es de nuevo la norma pesada de Frobenius descrita anteriormente, donde la matriz de peso <math display="inline">\boldsymbol {W}</math> es ahora cualquier matriz que satisfaga <math display="inline">\boldsymbol {Ws}^k=\boldsymbol {y}^k</math>. (Por concreción, se asume de nuevo que <math display="inline">\boldsymbol {W}</math> está dado por el inverso del hessiano promedio <math display="inline">\overline{\boldsymbol {G}}_k</math> definida en [[#eq-11|(11)]]). La única solución <math display="inline">\boldsymbol {H}_{k+1}</math> de [[#eq-16|(16)]] está dada por326
327
<span id="eq-17"></span>328
{| class="formulaSCP" style="width: 100%; text-align: left;" 329
|-330
| 331
{| style="text-align: left; margin:auto;width: 100%;" 332
|-333
| style="text-align: center;" | <math>\boldsymbol {H}_{k+1}^{BFGS}=\left(\boldsymbol {I}-\rho _k\boldsymbol {s}^k(\boldsymbol {y}^k)^t\right)\boldsymbol {H}_k\left(\boldsymbol {I}-\rho _k\boldsymbol {y}^k(\boldsymbol {s}^k)^t\right)+\rho _k\boldsymbol {s}^k(\boldsymbol {s}^k)^t, </math>334
|}335
| style="width: 5px;text-align: right;white-space: nowrap;" | (17)336
|}337
338
donde339
340
<span id="eq-18"></span>341
{| class="formulaSCP" style="width: 100%; text-align: left;" 342
|-343
| 344
{| style="text-align: left; margin:auto;width: 100%;" 345
|-346
| style="text-align: center;" | <math>\rho _k=\frac{1}{(\boldsymbol {y}^k)^t\boldsymbol {s}^k}, </math>347
|}348
| style="width: 5px;text-align: right;white-space: nowrap;" | (18)349
|}350
351
o bien, desarrollando las multiplicaciones352
353
<span id="eq-19"></span>354
{| class="formulaSCP" style="width: 100%; text-align: left;" 355
|-356
| 357
{| style="text-align: left; margin:auto;width: 100%;" 358
|-359
| style="text-align: center;" | <math>\boldsymbol {H}_{k+1}^{BFGS}=\boldsymbol {H}_k+\left(1+\frac{(\boldsymbol {y}^k)^t\boldsymbol {H}_k\boldsymbol {y}^k}{(\boldsymbol {s}^k)^t\boldsymbol {y}^k}\right)\frac{\boldsymbol {s}^k(\boldsymbol {s}^k)^t}{(\boldsymbol {s}^k)^t\boldsymbol {y}^k}-\left(\frac{\boldsymbol {s}^k(\boldsymbol {y}^k)^t\boldsymbol {H}_k+\boldsymbol {H}_k\boldsymbol {y}^k(\boldsymbol {s}^k)^t}{(\boldsymbol {s}^k)^t\boldsymbol {y}^k}\right). </math>360
|}361
| style="width: 5px;text-align: right;white-space: nowrap;" | (19)362
|}363
364
La demostración del siguiente teorema puede encontrarse en <span id='citeF-5'></span>[[#cite-5|[5]]].365
366
<span id='theorem-3.3.2'></span>Teorema 1: Si la fórmula de actualización <math display="inline">BFGS</math> [[#eq-19|(19)]], es ahora escrita como <math display="inline">\boldsymbol {H}_{k+1}=\boldsymbol {H}_k+\boldsymbol {E}</math>, entonces <math display="inline">\boldsymbol {E}</math> resuelve el problema <span id="eq-20"></span>367
368
{| class="formulaSCP" style="width: 100%; text-align: left;" 369
|-370
| 371
{| style="text-align: left; margin:auto;width: 100%;" 372
|-373
| style="text-align: center;" | <math>\min _{\boldsymbol {E}} \left\Vert \boldsymbol {E}\right\Vert _{\boldsymbol {W}};</math>374
| style="width: 5px;text-align: right;white-space: nowrap;" | (20.a)375
|-376
| style="text-align: center;" | <math> s. a \boldsymbol {E} = \boldsymbol {E}^t,</math>377
| style="width: 5px;text-align: right;white-space: nowrap;" | (20.b)378
|-379
| style="text-align: center;" | <math> \boldsymbol {Ey}^k = \boldsymbol {\eta }, </math>380
| style="width: 5px;text-align: right;white-space: nowrap;" | (20.c)381
|}382
|}383
384
donde <math display="inline">\boldsymbol {W}</math> satisface <math display="inline">\boldsymbol {Ws}^k=\boldsymbol {y}^k</math> y <math display="inline">\boldsymbol {\eta }=\boldsymbol {s}^k-\boldsymbol {H}_k\boldsymbol {y}^k</math>.385
386
De acuerdo con Nocedal <span id='citeF-4'></span>[[#cite-4|[4]]], si <math display="inline">\boldsymbol {H}_k</math> es definida positiva, entonces <math display="inline">\boldsymbol {H}_{k+1}</math> es definida positiva.387
388
389
{| style="margin: 1em auto;border: 1px solid darkgray;"390
|-391
|392
:Punto inicial <math display="inline">\boldsymbol {x}_0</math>, tolerancia <math display="inline">\varepsilon </math>, aproximación del inverso del hessiano <math display="inline">\boldsymbol {H}_0</math>. <math display="inline">\boldsymbol {x}^*</math> mínimo de <math display="inline">\boldsymbol {f}</math>. <math display="inline">k\leftarrow 0.</math> <math>\left\Vert \nabla \boldsymbol {f}(\boldsymbol {x}^k)\right\Vert > \varepsilon </math>Calcular la dirección de búsqueda393
394
{| class="formulaSCP" style="width: 100%; text-align: left;" 395
|-396
| 397
{| style="text-align: left; margin:auto;width: 100%;" 398
|-399
| style="text-align: center;" | <math>\boldsymbol {p}^k=-\boldsymbol {H}_k\nabla \boldsymbol {f}(\boldsymbol {x}^k). </math>400
|}401
| style="width: 5px;text-align: right;white-space: nowrap;" | (21)402
|}403
404
Calcular <math display="inline">\boldsymbol {x}^{k+1}=\boldsymbol {x}^k+\alpha _k\boldsymbol {p}^k</math>, donde <math display="inline">\alpha _k</math> es calculado mediante un procedimiento de búsqueda en la línea que satisfaga las condiciones de Wolfe [[#algorithm-1|(1)]]. Definir <math display="inline">\boldsymbol {s}^k=\boldsymbol {x}^{k+1}-\boldsymbol {x}^k</math> y <math display="inline">\boldsymbol {y}^k=\nabla \boldsymbol {f}(\boldsymbol {x}^{k+1})-\nabla \boldsymbol {f}(\boldsymbol {x}^k)</math>. Calcular <math display="inline">\boldsymbol {H}_{k+1}</math> por medio de [[#eq-19|(19)]]. <math display="inline">k\leftarrow k+1.</math> 405
406
407
|-408
| style="text-align: center; font-size: 75%;"|409
<span id='algorithm-2'></span>'''Algoritmo. 2''' Algoritmo BFGS410
|}411
412
<!-- comment413
414
===Algoritmo BFGS===415
416
Sólo un problema tiene que ser resuelto antes de que podamos definir un algoritmo BFGS completo ¿Cómo debemos escoger la aproximación inicial <math display="inline">H_0</math>? Desafortunadamente, no hay una fórmula que funcione bien en todos los casos. Podemos usar información especifica acerca del problema, por ejemplo, configurándolo como el inverso de una aproximación del hessiano calculado por diferencias finitas en <math display="inline">x_0</math>. De otra manera, podemos simplemente configurarla para que sea la matriz identidad, o un múltiplo de la matriz identidad, donde el múltiplo es escogido para reflejar el escalamiento de las variables.417
418
419
{| style="margin: 1em auto;border: 1px solid darkgray;"420
|-421
|422
:Punto inicial <math display="inline">x_0</math>, tolerancia <math display="inline">\varepsilon </math>, aproximación del inverso de el hessiano <math display="inline">H_0</math>. <math display="inline">x_*</math> <math display="inline">k\leftarrow 0;</math> <math>\Vert \nabla f_k\Vert > \varepsilon </math> Calcular la dirección de búsqueda423
424
<span id=""></span>425
{| class="formulaSCP" style="width: 100%; text-align: left;" 426
|-427
| 428
{| style="text-align: left; margin:auto;width: 100%;" 429
|-430
| style="text-align: center;" | <math>p_k=-H_k\nabla f_k; </math>431
|}432
|}433
434
Configurar <math display="inline">x_{k+1}=x_k+\alpha _kp_k</math>, donde <math display="inline">\alpha _k</math> es calculado mediante un procedimiento de búsqueda en la línea que satisfaga las condiciones de Wolf; Definir <math display="inline">s^k=x_{k+1}-x_k</math> y <math display="inline">y_k=\nabla f_{k+1}-\nabla f_k</math>; Calcule <math display="inline">H_{k+1}</math> por medio de [[#eq-17|(17)]]; <math display="inline">k\leftarrow k+1;</math> 435
436
437
|-438
| style="text-align: center; font-size: 75%;"|439
'''Algoritmo. ''' Algoritmo BFGS440
|}441
442
Cada iteración puede ser ejecutado con un costo de <math display="inline">O(n^2)</math> operaciones aritméticas (más el costo de las evaluaciones en la función y el gradiente); no hay operaciones de <math display="inline">O(n^3)</math>, tales como solución de un sistema de ecuaciones lineal u operaciones matriz-matriz. El algoritmo es robusto, y su rapidez de convergencia es superlineal, lo cual es suficientemente rápido para la mayoría de los propósitos prácticos. Incluso aunque el método de Newton converge más rápido a la solución (es decir, cuadráticamente), su costo por iteración es mayor, ya que requiere la solución de un sistema lineal. Una ventaja muy importante del método BFGS es, por supuesto, que no requiere el cálculo de segundas derivadas. 443
444
-->445
446
==3 Propuesta del nuevo método==447
448
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 <span id='citeF-6'></span>[[#cite-6|[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.449
450
===3.1 Motivación===451
452
Considere la función <math display="inline">\boldsymbol {\bar{f}}:\mathbb{R}^2\to \mathbb{R}</math> definida por453
454
<span id="eq-22"></span>455
{| class="formulaSCP" style="width: 100%; text-align: left;" 456
|-457
| 458
{| style="text-align: left; margin:auto;width: 100%;" 459
|-460
| style="text-align: center;" | <math>\boldsymbol {\bar{f}}(x,y)=\boldsymbol {f}(x,y)+\boldsymbol {e}(x,y), </math>461
|}462
| style="width: 5px;text-align: right;white-space: nowrap;" | (22)463
|}464
465
donde <math display="inline">\boldsymbol {f}(x,y)=0.00001(x^4+y^4)</math> y <math display="inline">\boldsymbol {e}(x,y)= 0.1\boldsymbol {f}(x,y)sin( x^2 + y^2 )</math>, el punto inicial <math display="inline">\boldsymbol {x}^0=(3,1)^t</math>, una tolerancia de <math display="inline">10^{-8}</math> y la matriz identidad como matriz inicial. En este ejemplo, <math display="inline">\boldsymbol {e}(x,y)</math> 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ón466
467
<div id='img-1'></div>468
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"469
|-470
|[[Image:Draft_Acevedo Vazquez_103892577-PP.png|390px|Resultados de los métodos DFP y BFGS para el punto inicial x⁰=(3,1)<sup>t</sup>.]]471
|- style="text-align: center; font-size: 75%;"472
| colspan="1" | '''Figura 1:''' Resultados de los métodos DFP y BFGS para el punto inicial <math>\boldsymbol {x}^0=(3,1)^t</math>.473
|}474
475
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 <math display="inline">\boldsymbol {B}_{k+1}</math> de una manera diferente.476
477
===3.2 Planteamiento del problema===478
479
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 <math display="inline">\boldsymbol {B} _{k+1}</math>. 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 [[#eq-9|(9)]] se resuelve <span id="eq-23"></span>480
481
<span id="eq-23.a"></span>482
{| class="formulaSCP" style="width: 100%; text-align: left;" 483
|-484
| 485
{| style="text-align: left; margin:auto;width: 100%;" 486
|-487
| style="text-align: center;" | <math>\min _{\boldsymbol {B} } cond(\boldsymbol {B} ); </math>488
|}489
| style="width: 5px;text-align: right;white-space: nowrap;" | (23.a)490
|}491
492
<span id="eq-23.b"></span>493
{| class="formulaSCP" style="width: 100%; text-align: left;" 494
|-495
| 496
{| style="text-align: left; margin:auto;width: 100%;" 497
|-498
| style="text-align: center;" | <math>\hbox{s. a }\boldsymbol {B} =\boldsymbol {B} ^t;</math>499
|-500
| style="text-align: center;" | <math> \boldsymbol {{B}s}^k=\boldsymbol {y}^k, </math>501
|}502
| style="width: 5px;text-align: right;white-space: nowrap;" | (23.b)503
|}504
505
donde <math display="inline">cond(\boldsymbol {B} )</math> está dado por <math display="inline">\frac{\lambda _n}{\lambda _1}</math>, con <math display="inline">0<\lambda _1<\cdots{<\lambda}_n</math> valores propios de la matriz <math display="inline">\boldsymbol {B} </math> (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:506
507
''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.''508
509
===3.3 Caso bidimensional===510
511
Supongamos que <math display="inline">\boldsymbol {f}</math> es una función de <math display="inline">\mathbb{R}^2</math> a <math display="inline">\mathbb{R}</math>. Consideramos <math display="inline">\boldsymbol {y}^k=(y_1^k,y_2^k)</math>, <math display="inline">\boldsymbol {s}^k=(s_1^k,s_2^k)</math> y512
513
{| class="formulaSCP" style="width: 100%; text-align: left;" 514
|-515
| 516
{| style="text-align: left; margin:auto;width: 100%;" 517
|-518
| style="text-align: center;" | <math>\boldsymbol {B} = \begin{bmatrix}b_{11} & b_{12}\\ b_{12} & b_{22} \end{bmatrix}. </math>519
|}520
| style="width: 5px;text-align: right;white-space: nowrap;" | (24)521
|}522
523
En este caso el número de condición está dado por524
525
<span id="eq-25"></span>526
{| class="formulaSCP" style="width: 100%; text-align: left;" 527
|-528
| 529
{| style="text-align: left; margin:auto;width: 100%;" 530
|-531
| style="text-align: center;" | <math>cond(\boldsymbol {B} )=\frac{\lambda _2}{\lambda _1}=\frac{tr(\boldsymbol {B} )+\sqrt{tr(\boldsymbol {B} )^2-4det(\boldsymbol {B} )}}{tr(\boldsymbol {B} )-\sqrt{tr(\boldsymbol {B} )^2-4det(\boldsymbol {B} )}}, </math>532
|}533
| style="width: 5px;text-align: right;white-space: nowrap;" | (25)534
|}535
536
donde <math display="inline">tr(\boldsymbol {B} )</math> y <math display="inline">det(\boldsymbol {B} )</math> denotan la traza y el determinante de <math display="inline">\boldsymbol {B} </math>, respectivamente. Ahora bien, dado que la matriz tiene que ser simétrica y cumplir la ecuación secante, tenemos que537
538
{| class="formulaSCP" style="width: 100%; text-align: left;" 539
|-540
| 541
{| style="text-align: left; margin:auto;width: 100%;" 542
|-543
| style="text-align: center;" | <math>b_{11}s_1^k+b_{12}s_2^k=y_1^k, </math>544
|}545
|}546
547
{| class="formulaSCP" style="width: 100%; text-align: left;" 548
|-549
| 550
{| style="text-align: left; margin:auto;width: 100%;" 551
|-552
| style="text-align: center;" | <math>b_{12}s_1^k+b_{22}s_2^k=y_2^k, </math>553
|}554
|}555
556
de donde se obtiene que557
558
{| class="formulaSCP" style="width: 100%; text-align: left;" 559
|-560
| 561
{| style="text-align: left; margin:auto;width: 100%;" 562
|-563
| style="text-align: center;" | <math>b_{11}=\frac{y_1^k-b_{12}s_2^k}{s_1^k}, </math>564
|}565
|}566
567
{| class="formulaSCP" style="width: 100%; text-align: left;" 568
|-569
| 570
{| style="text-align: left; margin:auto;width: 100%;" 571
|-572
| style="text-align: center;" | <math>b_{22}=\frac{y_2^k-b_{12}s_1^k}{s_2^k}, </math>573
|}574
|}575
576
{| class="formulaSCP" style="width: 100%; text-align: left;" 577
|-578
| 579
{| style="text-align: left; margin:auto;width: 100%;" 580
|-581
| style="text-align: center;" | <math>tr(\boldsymbol {B} )=\frac{y_1^k}{s_1^k}+\frac{y_2^k}{s_2^k}-b_{12}\left(\frac{s_2^k}{s_1^k}+\frac{s_1^k}{s_2^k}\right), </math>582
|}583
|}584
585
{| class="formulaSCP" style="width: 100%; text-align: left;" 586
|-587
| 588
{| style="text-align: left; margin:auto;width: 100%;" 589
|-590
| style="text-align: center;" | <math>det(\boldsymbol {B} )=\left(\frac{y_1^k-b_{12}s_2^k}{s_1^k}\right)\left(\frac{y_2^k-b_{12}s_1^k}{s_2^k}\right)-b_{12}^2. </math>591
|}592
|}593
594
Sustituyendo las ecuaciones anteriores en [[#eq-25|(25)]], se obtiene una función de <math display="inline">\mathbb{R}</math> a <math display="inline">\mathbb{R}</math>, la cual se minimiza calculando la primera derivada (respecto a <math display="inline">b_{12}</math>) e igualándola a 0. Con lo cual se obtiene que595
596
{| class="formulaSCP" style="width: 100%; text-align: left;" 597
|-598
| 599
{| style="text-align: left; margin:auto;width: 100%;" 600
|-601
| style="text-align: center;" | <math>b_{12}=\frac{y_1^ky_2^k\left\Vert \boldsymbol {s}^k\right\Vert ^2-s_1^ks_2^k\left\Vert \boldsymbol {y}^k\right\Vert ^2}{\left\Vert \boldsymbol {s}^k\right\Vert ^2(\boldsymbol {s}^k)^t\boldsymbol {y}^k}, </math>602
|}603
|}604
605
que al sustituirlo en las expresiones de <math display="inline">b_{11}</math> y <math display="inline">b_{22}</math> se llega a606
607
{| class="formulaSCP" style="width: 100%; text-align: left;" 608
|-609
| 610
{| style="text-align: left; margin:auto;width: 100%;" 611
|-612
| style="text-align: center;" | <math>b_{11}=\frac{(y_1^k)^2\left\Vert \boldsymbol {s}^k\right\Vert ^2 + (s_2^k)^2\left\Vert \boldsymbol {y}^k\right\Vert ^2}{\left\Vert \boldsymbol {s}^k\right\Vert ^2(\boldsymbol {s}^k)^t\boldsymbol {y}^k}, b_{22}=\frac{(y_2^k)^2\left\Vert \boldsymbol {s}^k\right\Vert ^2 + (s_1^k)^2\left\Vert \boldsymbol {y}^k\right\Vert ^2}{\left\Vert \boldsymbol {s}^k\right\Vert ^2(\boldsymbol {s}^k)^t\boldsymbol {y}^k}. </math>613
|}614
|}615
616
Con lo cual se obtienen las entradas de la matriz a la cual llamaremos <math display="inline">\boldsymbol {B}_{k+1}^{MCN}</math>, ya que es la que tiene el ''menor número de condición (minor condition number)'', la cual resuelve el subproblema [[#eq-23|(23)]]. Además, sustituyendo el valor de <math display="inline">b_{12}</math> en la expresión del determinante, se obtiene que <math display="inline">\boldsymbol {B} _{k+1}^{MCN}</math> es definida positiva. Haciendo los cálculos y simplificaciones necesarias se sigue que617
618
<span id="eq-29"></span>619
{| class="formulaSCP" style="width: 100%; text-align: left;" 620
|-621
| 622
{| style="text-align: left; margin:auto;width: 100%;" 623
|-624
| style="text-align: center;" | <math>\boldsymbol {B} _{k+1}^{MCN}=\frac{\boldsymbol {y}^k(\boldsymbol {y}^k)^t}{(\boldsymbol {s}^k)^t\boldsymbol {y}^k}+\frac{\left\Vert \boldsymbol {y}^k\right\Vert ^2\boldsymbol {z}^k (\boldsymbol {z}^k)^t }{\left\Vert \boldsymbol {s}^k\right\Vert ^2(\boldsymbol {s}^k)^t\boldsymbol {y}^k}, </math>625
|}626
| style="width: 5px;text-align: right;white-space: nowrap;" | (29)627
|}628
629
donde <math display="inline">(\boldsymbol {z}^k)^t=((\boldsymbol {s}^k)^\perp )^t=(s_2^k,-s_1^k)</math>. Notemos que, tanto el primer sumando como el segundo son matrices de rango 1.630
631
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 <math display="inline">\boldsymbol {H}_k=\boldsymbol {B}_k^{-1}</math>, teniendo así una expresión del inverso de [[#eq-29|(29)]]632
633
<span id="eq-30"></span>634
{| class="formulaSCP" style="width: 100%; text-align: left;" 635
|-636
| 637
{| style="text-align: left; margin:auto;width: 100%;" 638
|-639
| style="text-align: center;" | <math>\boldsymbol {H}_{k+1}^{MCN}=\frac{\boldsymbol {s}^k(\boldsymbol {s}^k)^t}{(\boldsymbol {s}^k)^t\boldsymbol {y}^k}+\frac{\left\Vert \boldsymbol {s}^k\right\Vert ^2\boldsymbol {w}^k (\boldsymbol {w}^k)^t }{\left\Vert \boldsymbol {y}^k\right\Vert ^2(\boldsymbol {s}^k)^t\boldsymbol {y}^k}, </math>640
|}641
| style="width: 5px;text-align: right;white-space: nowrap;" | (30)642
|}643
644
donde <math display="inline">(\boldsymbol {w}^k)^t=((\boldsymbol {y}^k)^\perp )^t=(y_2^k,-y_1^k)</math>.645
646
====3.3.1 Existencia de la matriz de peso W.====647
648
Siguiendo la idea de la construcción del método DFP, lo que se requiere es que <math display="inline">\boldsymbol {B} _{k+1}^{MCN}</math> sea la matriz que resuelva el problema [[#eq-9|(9)]] con la misma norma <math display="inline">\left\Vert \boldsymbol {A}\right\Vert _{\boldsymbol {W}}=tr(\boldsymbol {WA}^t\boldsymbol {WA})</math>, pero con una matriz de peso adecuada. Así, el problema ahora es encontrar <math display="inline">\boldsymbol {W}</math> de tal forma que <math display="inline">\boldsymbol {Wy}^k=\boldsymbol {s}^k</math> y649
650
{| class="formulaSCP" style="width: 100%; text-align: left;" 651
|-652
| 653
{| style="text-align: left; margin:auto;width: 100%;" 654
|-655
| style="text-align: center;" | <math>\boldsymbol {B} _{k+1}^{MCN} =\arg \min _{\boldsymbol {B} } \left\Vert \boldsymbol {B} -\boldsymbol {B} _k\right\Vert _{\boldsymbol {W}};</math>656
|-657
| style="text-align: center;" | <math> \hbox{ s. a }\boldsymbol {B} =\boldsymbol {B} ^t;</math>658
|-659
| style="text-align: center;" | <math> \boldsymbol {{B}s}^k=\boldsymbol {y}^k. </math>660
|}661
|}662
663
Notando que <math display="inline">\boldsymbol {B} </math> y <math display="inline">\boldsymbol {B} _k</math> son matrices simétricas se tiene que664
665
{| class="formulaSCP" style="width: 100%; text-align: left;" 666
|-667
| 668
{| style="text-align: left; margin:auto;width: 100%;" 669
|-670
| style="text-align: center;" | <math>\left\Vert \boldsymbol {B} -\boldsymbol {B} _k\right\Vert _{\boldsymbol {W}}=tr\left(\left(\boldsymbol {W}(\boldsymbol {B} -\boldsymbol {B} _k)\right)^2 \right).</math>671
|}672
|}673
674
Además, de la restricción <math display="inline">\boldsymbol {Wy}^k=\boldsymbol {s}^k</math> y haciendo un análisis análogo al realizado para <math display="inline">\boldsymbol {B} _{k+1}^{MCN}</math> se obtiene que675
676
<span id="eq-31"></span>677
<span id="eq-32"></span>678
{| class="formulaSCP" style="width: 100%; text-align: left;" 679
|-680
| 681
{| style="text-align: left; margin:auto;width: 100%;" 682
|-683
| style="text-align: center;" | <math>w_{11}=\frac{s_1^k-w_{12}y_2^k}{y_1^k},</math>684
| style="width: 5px;text-align: right;white-space: nowrap;" | (31)685
|-686
| style="text-align: center;" | <math> w_{22}=\frac{s_2^k-w_{12}y_1^k}{y_2^k}. </math>687
| style="width: 5px;text-align: right;white-space: nowrap;" | (32)688
|}689
|}690
691
Si se denota por <math display="inline">c_1=b_{11}-b_{11}^k</math>, <math display="inline">c_2=b_{12}-b_{12}^k</math> y <math display="inline">c_3=b_{22}-b_{22}^k</math>, se tiene que692
693
{| class="formulaSCP" style="width: 100%; text-align: left;" 694
|-695
| 696
{| style="text-align: left; margin:auto;width: 100%;" 697
|-698
| style="text-align: center;" | <math>\boldsymbol {g}(w_{12}) = \left\Vert \boldsymbol {B} -\boldsymbol {B} _k\right\Vert _{\boldsymbol {W}}</math>699
|-700
| style="text-align: center;" | <math> = 2\left(c_1w_{12} +\frac{c_2(s_2^k - w_{12}y_1^k)}{y_2^k}\right)\left(c_3w_{12} +\frac{c_2(s_1^k - w_{12}y_2^k)}{y_1^k}\right)</math>701
|-702
| style="text-align: center;" | <math> + \left(c_2w_{12} + \frac{c_1(s_1^k - w_{12}y_2^k)}{y_1^k}\right)^2 + \left(c_2w_{12} +\frac{c_3(s_2^k - w_{12}y_1^k)}{y_2^k}\right)^2. </math>703
|}704
|}705
706
Obteniendo los puntos estacionarios de la expresión anterior (con respecto a <math display="inline">b_{ij}</math>), obtenemos que707
708
<span id="eq-33"></span>709
{| class="formulaSCP" style="width: 100%; text-align: left;" 710
|-711
| 712
{| style="text-align: left; margin:auto;width: 100%;" 713
|-714
| style="text-align: center;" | <math>w_{12}=\frac{b^k_{22}(s_2^k)^2(y_1^k)^2 - 2b^k_{12}(s_2^k)^2(y_1^k)(y_2^k) + b^k_{11}(s_2^k)^2(y_2^k)^2 + (s_2^k)(y_1^k)^2(y_2^k) + (s_1^k)(y_1^k)^3}{((\boldsymbol {s}^k)^t\boldsymbol {y}^k)^2} </math>715
|}716
| style="width: 5px;text-align: right;white-space: nowrap;" | (33)717
|}718
719
Sustituyendo ([[#eq-33|33]]) en ([[#eq-31|31]]) y ([[#eq-32|32]]), se halla a la matriz de peso <math display="inline">\boldsymbol {W}</math>.720
721
==4 Algoritmo==722
723
Definimos ahora, un algoritmo que encuentre la solución de [[#eq-1|(1)]]724
725
726
{| style="margin: 1em auto;border: 1px solid darkgray;"727
|-728
|729
:Punto inicial <math display="inline">\boldsymbol {x}^0</math>, tolerancia <math display="inline">\varepsilon </math>, aproximación del inverso del hessiano <math display="inline">\boldsymbol {H} _0</math>. <math display="inline">\boldsymbol {x}^*</math> mínimo de <math display="inline">\boldsymbol {f}</math>. <math display="inline">k\leftarrow 0.</math> <math>\left\Vert \nabla \boldsymbol {f}(\boldsymbol {x}^k)\right\Vert > \varepsilon </math>Calcular la dirección de búsqueda730
731
{| class="formulaSCP" style="width: 100%; text-align: left;" 732
|-733
| 734
{| style="text-align: left; margin:auto;width: 100%;" 735
|-736
| style="text-align: center;" | <math>\boldsymbol {p}^k=-\boldsymbol {H}_k\nabla \boldsymbol {f}(\boldsymbol {x}^k). </math>737
|}738
| style="width: 5px;text-align: right;white-space: nowrap;" | (34)739
|}740
741
Calcular <math display="inline">\boldsymbol {x}^{k+1}=\boldsymbol {x}^k+\alpha _k\boldsymbol {p}^k</math>, donde <math display="inline">\alpha _k</math> es calculado mediante un procedimiento de búsqueda en la línea que satisfaga las condiciones de Wolfe [[#algorithm-1|(1)]]. Definir <math display="inline">\boldsymbol {s}^k=\boldsymbol {x}^{k+1}-\boldsymbol {x}^k</math> y <math display="inline">\boldsymbol {y}^k=\nabla \boldsymbol {f}(\boldsymbol {x}^{k+1})-\nabla \boldsymbol {f}(\boldsymbol {x}^k)</math>. Calcular <math display="inline">\boldsymbol {H} _{k+1}</math> por medio de [[#eq-30|(30)]]. <math display="inline">k\leftarrow k+1.</math> 742
743
744
|-745
| style="text-align: center; font-size: 75%;"|746
<span id='algorithm-3'></span>'''Algoritmo. 3''' Algoritmo MCN747
|}748
749
==5 Convergencia==750
751
Para analizar la convergencia del método MCN, usaremos los resultados dados en <span id='citeF-7'></span>[[#cite-7|[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.752
753
En lo que sigue, se dará un resumen de las definiciones y resultados que están en <span id='citeF-7'></span>[[#cite-7|[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 <math display="inline">\nabla \boldsymbol {f}(\boldsymbol {x})=\boldsymbol {0}</math>.754
755
Sean <math display="inline">X</math> un espacio lineal (vectorial) de dimensión finita, <math display="inline">D\subset X</math>, <math display="inline">\Omega \subset \mathbb{R}^n</math>, <math display="inline">\boldsymbol {\phi }:\Omega \times D\to \mathbb{R}^n</math>. Se consideran los métodos iterativos definidos por756
757
<span id="eq-35"></span>758
{| class="formulaSCP" style="width: 100%; text-align: left;" 759
|-760
| 761
{| style="text-align: left; margin:auto;width: 100%;" 762
|-763
| style="text-align: center;" | <math>\boldsymbol {x}^{k+1}=\boldsymbol {\phi }(\boldsymbol {x}^k,E_k). </math>764
|}765
| style="width: 5px;text-align: right;white-space: nowrap;" | (35)766
|}767
768
<span id='theorem-punto fijo'></span>Definición 1: Decimos que <math display="inline">\boldsymbol {x}\in \Omega </math> es un punto fijo de <math display="inline">\boldsymbol {\phi }</math> si y sólo si,769
770
{| class="formulaSCP" style="width: 100%; text-align: left;" 771
|-772
| 773
{| style="text-align: left; margin:auto;width: 100%;" 774
|-775
| style="text-align: center;" | <math>\boldsymbol {x}=\boldsymbol {\phi }(\boldsymbol {x},E),\quad \hbox{para todo }E\in D. </math>776
|}777
| style="width: 5px;text-align: right;white-space: nowrap;" | (36)778
|}779
780
El objetivo de los algoritmos del tipo [[#eq-35|(35)]] es el de aproximar los puntos fijos de <math display="inline">\boldsymbol {\phi }</math>. Notemos que los métodos cuasi-Newton pertenecen a esta clase de métodos, ya que si consideramos <math display="inline">D=\lbrace \boldsymbol {B}\in \mathbb{R}^{n\times n}:\boldsymbol {B}\hbox{ es no singular}\rbrace </math>, <math display="inline">\Omega =\mathbb{R}^n</math>, <math display="inline">\boldsymbol {F}:\Omega \to \mathbb{R}^n</math>, definimos781
782
<span id="eq-37"></span>783
{| class="formulaSCP" style="width: 100%; text-align: left;" 784
|-785
| 786
{| style="text-align: left; margin:auto;width: 100%;" 787
|-788
| style="text-align: center;" | <math>\boldsymbol {\phi }(\boldsymbol {x},\boldsymbol {B})=\boldsymbol {x}-\boldsymbol {B} ^{-1}\boldsymbol {F}(\boldsymbol {x}). </math>789
|}790
| style="width: 5px;text-align: right;white-space: nowrap;" | (37)791
|}792
793
Claramente, el conjunto de puntos <math display="inline">\boldsymbol {x} \in \mathbb{R}^n</math> tales que <math display="inline">\boldsymbol {x}=\boldsymbol {\phi }(\boldsymbol {x},\boldsymbol {B})</math> para todo <math display="inline">\boldsymbol {B}\in D</math>, es el conjunto de soluciones de <math display="inline">\boldsymbol {F}(\boldsymbol {x})=\boldsymbol {0}</math>. Los métodos definidos por <math display="inline">\boldsymbol {x}^{k+1}=\boldsymbol {\phi }(\boldsymbol {x}^k,\boldsymbol {B}_k)</math> forman la familia de métodos cuasi-Newton para resolver sistemas de ecuaciones no lineales.794
795
Se establecen condiciones suficientes para que la sucesión definida por [[#eq-35|(35)]] esté bien definida y converja a un punto fijo de <math display="inline">\boldsymbol {\phi }</math> con una convergencia lineal. Se consideran dos suposiciones, A1 y A2 que se establecen a continuación.796
797
'''Suposición A1.''' Sea <math display="inline">\Omega </math> un conjunto abierto y convexo, <math display="inline">\left\vert \cdot \right\vert </math> una norma en <math display="inline">\mathbb{R}^n</math>, <math display="inline">X</math> un espacio lineal de dimensión finita, <math display="inline">\left\Vert \cdot \right\Vert </math> una norma en <math display="inline">X</math>, <math display="inline">D</math> un subconjunto abierto de <math display="inline">X</math>. Supongamos que <math display="inline">\boldsymbol {\phi }:\Omega \times D\to \mathbb{R}^n</math> es continua, y que la derivada de <math display="inline">\boldsymbol {\phi }</math> con respecto a <math display="inline">\boldsymbol {x}</math> existe y es continua, para todo <math display="inline">\boldsymbol {x}\in \Omega </math>, <math display="inline">E\in D</math>. Denotamos por <math display="inline">\boldsymbol {\phi }'(\boldsymbol {x},\boldsymbol {E})\in \mathbb{R}^{n\times n}</math> la matriz Jacobiana de <math display="inline">\boldsymbol {\phi }</math> con respecto a <math display="inline">\boldsymbol {x}</math>. Supongamos que:798
799
<ol>800
801
<li> Existe <math display="inline">\boldsymbol {x}^*\in \Omega </math>, <math display="inline">L,p>0</math> tales que802
803
<span id="eq-38"></span>804
{| class="formulaSCP" style="width: 100%; text-align: left;" 805
|-806
| 807
{| style="text-align: left; margin:auto;width: 100%;" 808
|-809
| style="text-align: center;" | <math>810
811
\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, </math>812
|}813
| style="width: 5px;text-align: right;white-space: nowrap;" | (38)814
|}</li>815
816
para todo <math display="inline">\boldsymbol {x}\in \Omega </math>, <math display="inline">E\in D</math>. Esto implica que para todo <math display="inline">\boldsymbol {x},\boldsymbol {z}\in \Omega </math>, <math display="inline">E\in D</math>,817
818
<span id="eq-39"></span>819
{| class="formulaSCP" style="width: 100%; text-align: left;" 820
|-821
| 822
{| style="text-align: left; margin:auto;width: 100%;" 823
|-824
| style="text-align: center;" | <math>825
826
\left\vert \boldsymbol {\phi }(\boldsymbol {z},E)-\boldsymbol {\phi }(\boldsymbol {x},E)-\boldsymbol {\phi }'(\boldsymbol {x}^*,E)(\boldsymbol {z}-\boldsymbol {x})\right\vert \leq L\left\vert \boldsymbol {z}-\boldsymbol {x}\right\vert \sigma (\boldsymbol {x},\boldsymbol {z})^p, </math>827
|}828
| style="width: 5px;text-align: right;white-space: nowrap;" | (39)829
|}830
831
donde832
833
<span id="eq-40"></span>834
{| class="formulaSCP" style="width: 100%; text-align: left;" 835
|-836
| 837
{| style="text-align: left; margin:auto;width: 100%;" 838
|-839
| style="text-align: center;" | <math>840
841
\sigma (\boldsymbol {x},\boldsymbol {z})=\max \left\{\left\vert \boldsymbol {x}-\boldsymbol {x}^*\right\vert ,\left\vert \boldsymbol {z}-\boldsymbol {x}^*\right\vert \right\}. </math>842
|}843
| style="width: 5px;text-align: right;white-space: nowrap;" | (40)844
|}845
<li>Para todo <math display="inline">E\in D</math>,846
847
<span id="eq-41"></span>848
{| class="formulaSCP" style="width: 100%; text-align: left;" 849
|-850
| 851
{| style="text-align: left; margin:auto;width: 100%;" 852
|-853
| style="text-align: center;" | <math>854
855
\boldsymbol {x}^*=\boldsymbol {\phi }(\boldsymbol {x}^*,E). </math>856
|}857
| style="width: 5px;text-align: right;white-space: nowrap;" | (41)858
|}</li>859
860
</ol>861
862
'''Suposición A2.''' Existe <math display="inline">E_*\in D</math> tal que863
864
<span id="eq-42"></span>865
{| class="formulaSCP" style="width: 100%; text-align: left;" 866
|-867
| 868
{| style="text-align: left; margin:auto;width: 100%;" 869
|-870
| style="text-align: center;" | <math>\left\vert \boldsymbol {\phi }'(\boldsymbol {x}^*,E_*)\right\vert =r^*<1. </math>871
|}872
| style="width: 5px;text-align: right;white-space: nowrap;" | (42)873
|}874
875
<span id='theorem-3.6'></span>Lema 1: Suponga que <math display="inline">\boldsymbol {\phi },\boldsymbol {x}^*,E_*</math> satisfacen las Suposiciones A1 y A2. Sea <math display="inline">r\in (r^*,1)</math>. Entonces, existen <math display="inline">\overline{\varepsilon }=\overline{\varepsilon }(r), \overline{\delta }=\overline{\delta }(r)</math> tales que876
877
{| class="formulaSCP" style="width: 100%; text-align: left;" 878
|-879
| 880
{| style="text-align: left; margin:auto;width: 100%;" 881
|-882
| style="text-align: center;" | <math>\left\vert \boldsymbol {\phi }(\boldsymbol {x},E)-\boldsymbol {x}^*\right\vert \leq \left\vert \boldsymbol {x}-\boldsymbol {x}^*\right\vert , </math>883
|}884
| style="width: 5px;text-align: right;white-space: nowrap;" | (43)885
|}886
887
siempre que <math display="inline">\left\vert \boldsymbol {x}-\boldsymbol {x}^*\right\vert \leq \overline{\varepsilon }</math>, <math display="inline">\left\Vert E-E_*\right\Vert \leq \overline{\delta }</math>.888
889
<span id='theorem-T3.1'></span>Teorema 2: Suponga que <math display="inline">\boldsymbol {\phi },\boldsymbol {x}^*,E_*</math> satisfacen las Suposiciones A1 y A2. Sea <math display="inline">r\in (r^*,1)</math>. Entonces, existen <math display="inline">\varepsilon =\varepsilon (r), \delta =\delta (r)</math> tales que, si <math display="inline">\left\vert \boldsymbol {x}^0-\boldsymbol {x}^*\right\vert \leq \varepsilon </math> y <math display="inline">\left\Vert E_k-E_*\right\Vert \leq \delta </math> para todo <math display="inline">k=0,1,\ldots </math>, entonces la sucesión generada por [[#eq-35|(35)]] está bien definida, converge a <math display="inline">\boldsymbol {x}^*</math> y satisface890
891
<span id="eq-44"></span>892
{| class="formulaSCP" style="width: 100%; text-align: left;" 893
|-894
| 895
{| style="text-align: left; margin:auto;width: 100%;" 896
|-897
| style="text-align: center;" | <math>\left\vert \boldsymbol {x}^{k+1}-\boldsymbol {x}^*\right\vert \leq \left\vert \boldsymbol {x}^k-\boldsymbol {x}^*\right\vert , </math>898
|}899
| style="width: 5px;text-align: right;white-space: nowrap;" | (44)900
|}901
902
para todo <math display="inline">k=0,1,2,\ldots </math>.903
904
Para el caso de los métodos cuasi-Newton, a fin de verificar la condición [[#eq-42|(42)]], se debe calcular <math display="inline">\boldsymbol {\phi }'(\boldsymbol {x},E)</math> que en este caso está dada por:905
906
{| class="formulaSCP" style="width: 100%; text-align: left;" 907
|-908
| 909
{| style="text-align: left; margin:auto;width: 100%;" 910
|-911
| style="text-align: center;" | <math>\boldsymbol {\phi }'(\boldsymbol {x},\boldsymbol {B})=\boldsymbol {I}-\boldsymbol {B}^{-1}\boldsymbol {F}'(\boldsymbol {x}), </math>912
|}913
|}914
915
de donde se tiene que cumplir916
917
{| class="formulaSCP" style="width: 100%; text-align: left;" 918
|-919
| 920
{| style="text-align: left; margin:auto;width: 100%;" 921
|-922
| style="text-align: center;" | <math>\left\vert \boldsymbol {I}-\boldsymbol {B}^{-1}\boldsymbol {F}'(\boldsymbol {x})\right\vert =r_*<1. </math>923
|}924
|}925
926
Si se toma <math display="inline">\boldsymbol {B}_*=\boldsymbol {F}'(\boldsymbol {x}^*)</math>, se tiene <math display="inline">r_*=0</math>.927
928
<span id='theorem-T4.1'></span>Teorema 3: Suponga que <math display="inline">\boldsymbol {\phi },\boldsymbol {x}^*,E_*</math> y la sucesión <math display="inline">\{ \boldsymbol {x}^k\} </math> satisfacen las hipótesis del Teorema [[#theorem-T3.1|2]]. Suponga además que <math display="inline">\boldsymbol {x}^k\neq \boldsymbol {x}^*</math> para todo <math display="inline">k=0,1,2,\ldots </math> y que929
930
<span id="eq-45"></span>931
{| class="formulaSCP" style="width: 100%; text-align: left;" 932
|-933
| 934
{| style="text-align: left; margin:auto;width: 100%;" 935
|-936
| style="text-align: center;" | <math>\lim _{k\to \infty }\frac{\left\vert \left[(\boldsymbol {I}-\boldsymbol {\phi }'(\boldsymbol {x}^*,\boldsymbol {E}_k))^{-1}-(\boldsymbol {I}-\boldsymbol {\phi }'(\boldsymbol {x}^*,E_*))^{-1}\right](\boldsymbol {x}^{k+1}-\boldsymbol {x}^k)\right\vert }{\left\vert \boldsymbol {x}^{k+1}-\boldsymbol {x}^k\right\vert }=0. </math>937
|}938
| style="width: 5px;text-align: right;white-space: nowrap;" | (45)939
|}940
941
Entonces942
943
<span id="eq-46"></span>944
{| class="formulaSCP" style="width: 100%; text-align: left;" 945
|-946
| 947
{| style="text-align: left; margin:auto;width: 100%;" 948
|-949
| style="text-align: center;" | <math>\overline{\lim }\frac{\left\vert \boldsymbol {x}^{k+1}-\boldsymbol {x}^*\right\vert }{\left\vert \boldsymbol {x}^k-\boldsymbol {x}^*\right\vert }\leq r_*. </math>950
|}951
| style="width: 5px;text-align: right;white-space: nowrap;" | (46)952
|}953
954
<span id='theorem-C4.1'></span>Corolario 1: Bajo las hipótesis del Teorema [[#theorem-T4.1|3]], si <math display="inline">\displaystyle \lim _{k\to \infty }\left\Vert E^k-E^*\right\Vert =0</math>, entonces955
956
{| class="formulaSCP" style="width: 100%; text-align: left;" 957
|-958
| 959
{| style="text-align: left; margin:auto;width: 100%;" 960
|-961
| style="text-align: center;" | <math>\overline{\lim }\frac{\left\vert \boldsymbol {x}^{k+1}-\boldsymbol {x}^*\right\vert }{\left\vert \boldsymbol {x}^k-\boldsymbol {x}^*\right\vert }\leq r_*. </math>962
|}963
|}964
965
<span id='theorem-T4.3'></span>Teorema 4: Suponga que <math display="inline">\boldsymbol {\phi },\boldsymbol {x}^*,E_*</math> satisfacen las Suposiciones A1 y A2, y que <math display="inline">r^*=0</math>. Suponga que una sucesión es generada por [[#eq-35|(35)]] y que, para todo <math display="inline">k=0,1,2,\ldots </math>966
967
<span id="eq-47"></span>968
{| class="formulaSCP" style="width: 100%; text-align: left;" 969
|-970
| 971
{| style="text-align: left; margin:auto;width: 100%;" 972
|-973
| style="text-align: center;" | <math>\left\vert \boldsymbol {\phi }'(\boldsymbol {x}^*,\boldsymbol {E}_k)-\boldsymbol {\phi }'(\boldsymbol {x}^*,E_*)\right\vert \leq M\left\vert \boldsymbol {x}^k-\boldsymbol {x}^*\right\vert ^p, </math>974
|}975
| style="width: 5px;text-align: right;white-space: nowrap;" | (47)976
|}977
978
para algún <math display="inline">M>0</math>. Entonces, existe <math display="inline">\varepsilon{>0}</math> tal que si <math display="inline">\left\vert \boldsymbol {x}^0-\boldsymbol {x}^*\right\vert \leq \varepsilon </math>, la sucesión <math display="inline">\{ \boldsymbol {x}^k\} </math> está bien definida, converge a <math display="inline">\boldsymbol {x}^*</math> y satisface979
980
<span id="eq-48"></span>981
{| class="formulaSCP" style="width: 100%; text-align: left;" 982
|-983
| 984
{| style="text-align: left; margin:auto;width: 100%;" 985
|-986
| style="text-align: center;" | <math>\left\vert \boldsymbol {x}^{k+1}-\boldsymbol {x}^*\right\vert \leq (L+M)\left\vert \boldsymbol {x}^k-\boldsymbol {x}^*\right\vert ^{p+1}. </math>987
|}988
| style="width: 5px;text-align: right;white-space: nowrap;" | (48)989
|}990
991
Habíamos visto que en el caso de los métodos cuasi-Newton, <math display="inline">\boldsymbol {\phi }'(\boldsymbol {x},\boldsymbol {B})=\boldsymbol {I}-\boldsymbol {B}^{-1}\boldsymbol {F}'(\boldsymbol {x})</math>. Así,992
993
{| class="formulaSCP" style="width: 100%; text-align: left;" 994
|-995
| 996
{| style="text-align: left; margin:auto;width: 100%;" 997
|-998
| style="text-align: center;" | <math>\boldsymbol {\phi }'(\boldsymbol {x}^*,\boldsymbol {B} _k)=\boldsymbol {I}-\boldsymbol {B} _k^{-1}\boldsymbol {F}'(\boldsymbol {x}^*) </math>999
|}1000
|}1001
1002
y1003
1004
{| class="formulaSCP" style="width: 100%; text-align: left;" 1005
|-1006
| 1007
{| style="text-align: left; margin:auto;width: 100%;" 1008
|-1009
| style="text-align: center;" | <math>\left[\boldsymbol {I}-\boldsymbol {\phi }'(\boldsymbol {x}^*,\boldsymbol {B} _k)\right]^{-1} =\left[\boldsymbol {F}'(\boldsymbol {x}^*)\right]^{-1}\boldsymbol {B} _k,</math>1010
|-1011
| style="text-align: center;" | <math> \left[\boldsymbol {I}-\boldsymbol {\phi }'(\boldsymbol {x}^*,\boldsymbol {B}_*)\right]^{-1} =\left[\boldsymbol {F}'(\boldsymbol {x}^*)\right]^{-1}\boldsymbol {B}_*. </math>1012
|}1013
|}1014
1015
Por lo tanto, la condición [[#eq-45|(45)]] se convierte en1016
1017
{| class="formulaSCP" style="width: 100%; text-align: left;" 1018
|-1019
| 1020
{| style="text-align: left; margin:auto;width: 100%;" 1021
|-1022
| style="text-align: center;" | <math>\lim _{k\to \infty }\frac{\left\vert \boldsymbol {F}'(\boldsymbol {x}^*)(\boldsymbol {B} _k-\boldsymbol {B}_*)(\boldsymbol {x}^{k+1}-\boldsymbol {x}^k)\right\vert }{\left\vert \boldsymbol {x}^{k+1}-\boldsymbol {x}^k\right\vert }=0. </math>1023
|}1024
|}1025
1026
Esto es equivalente a1027
1028
<span id="eq-49"></span>1029
{| class="formulaSCP" style="width: 100%; text-align: left;" 1030
|-1031
| 1032
{| style="text-align: left; margin:auto;width: 100%;" 1033
|-1034
| style="text-align: center;" | <math>\lim _{k\to \infty }\frac{\left\vert (\boldsymbol {B} _k-\boldsymbol {B}_*)(\boldsymbol {x}^{k+1}-\boldsymbol {x}^k)\right\vert }{\left\vert \boldsymbol {x}^{k+1}-\boldsymbol {x}^k\right\vert }=0. </math>1035
|}1036
| style="width: 5px;text-align: right;white-space: nowrap;" | (49)1037
|}1038
1039
Esta es la condición de Dennis-Walker de convergencia de los métodos cuasi-Newton a una tasa ideal (ver <span id='citeF-8'></span>[[#cite-8|[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 ([[#eq-49|49]]).1040
1041
==6 Ejemplos numéricos==1042
1043
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.1044
1045
===6.1 Caso sin error===1046
1047
Se consideró la siguiente función para la primera prueba1048
1049
<span id="eq-50"></span>1050
{| class="formulaSCP" style="width: 100%; text-align: left;" 1051
|-1052
| 1053
{| style="text-align: left; margin:auto;width: 100%;" 1054
|-1055
| style="text-align: center;" | <math>\boldsymbol {f}: \mathbb{R}^2 \to \mathbb{R},</math>1056
| style="width: 5px;text-align: right;white-space: nowrap;" | (50)1057
|-1058
| style="text-align: center;" | <math> (x_1,x_2) \longmapsto x_1^4+(x_1+x_2)^2+\left(e^{x_2}-1\right)^2, </math>1059
| style="width: 5px;text-align: right;white-space: nowrap;" | (51)1060
|}1061
|}1062
1063
con el punto inicial <math display="inline">\boldsymbol {x}^0=(-10,17)</math>, una tolerancia de <math display="inline">10^{-8}</math> y la matriz identidad como matriz inicial. Se obtuvieron los resultados mostrados en la Figura [[#img-2|2]] (que corresponde a una ventana emergente del lenguaje de programación):1064
1065
<div id='img-2'></div>1066
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"1067
|-1068
|[[Image:Draft_Acevedo Vazquez_103892577-Resultados sin error.png|420px|Resultados de los métodos.]]1069
|- style="text-align: center; font-size: 75%;"1070
| colspan="1" | '''Figura 2:''' Resultados de los métodos.1071
|}1072
1073
<div id='img-3'></div>1074
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"1075
|-1076
|[[Image:Draft_Acevedo Vazquez_103892577-Grafica sin error.png|300px|Gráfica de la función.]]1077
|- style="text-align: center; font-size: 75%;"1078
| colspan="1" | '''Figura 3:''' Gráfica de la función.1079
|}1080
1081
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 [[#table-1|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.1082
1083
1084
{| class="floating_tableSCP wikitable" style="text-align: center; margin: 1em auto;min-width:50%;"1085
|+ style="font-size: 75%;" |<span id='table-1'></span>Tabla. 1 Número de iteraciones y tiempo, medido en segundos, de los distintos métodos usando distintos puntos iniciales. Se observa que el método MCN converge en todos los puntos. El método DFP no converge en todos los puntos y en los que lo hace, emplea menos iteraciones que el método MCN. El método BFGS converge en todos los puntos y en menos iteraciones que los otros dos.1086
|- style="border-top: 2px solid;"1087
| <math display="inline">\boldsymbol {x}^0</math> 1088
| BFGS [tiempo] 1089
| DFP [tiempo] 1090
| MCN [tiempo]1091
|- style="border-top: 2px solid;"1092
| (-10,17) 1093
| 61 [10.55] 1094
| - 1095
| 76 [14.86] 1096
|-1097
| (10,-17) 1098
| 21 [3.04] 1099
| 27 [3.68] 1100
| 31 [4.45]1101
|-1102
| (-10,-17) 1103
| 17 [2.7]1104
| 18 [2.63] 1105
| 37 [5.59] 1106
|-1107
| (10,17) 1108
| 56 [9.92] 1109
| - 1110
| 62 [12.94]1111
|-1112
| (2,1) 1113
| 12 [1.75] 1114
| 15 [2.05] 1115
| 17 [2.38]1116
|-1117
| (-2,1) 1118
| 10 [1.63] 1119
| 11 [1.72] 1120
| 28 [4.1]1121
|-1122
| (-2,-1) 1123
| 11 [1.71] 1124
| 11 [1.69]1125
| 39 [5.94]1126
|- style="border-bottom: 2px solid;"1127
| (2,-1) 1128
| 14 [2.11] 1129
| 24 [3.33] 1130
| 26 [3.61] 1131
1132
|}1133
1134
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.1135
1136
Consideremos ahora la función1137
1138
<span id="eq-52"></span>1139
{| class="formulaSCP" style="width: 100%; text-align: left;" 1140
|-1141
| 1142
{| style="text-align: left; margin:auto;width: 100%;" 1143
|-1144
| style="text-align: center;" | <math>\boldsymbol {f}: \mathbb{R}^2 \to \mathbb{R},</math>1145
| style="width: 5px;text-align: right;white-space: nowrap;" | (52)1146
|-1147
| style="text-align: center;" | <math> (x_1,x_2) \longmapsto 0.00001(x_1^4+x_2^4), </math>1148
| style="width: 5px;text-align: right;white-space: nowrap;" | (53)1149
|}1150
|}1151
1152
con el punto inicial <math display="inline">\boldsymbol {x}^0=(2,1)^T</math>, una tolerancia de <math display="inline">10^{-8}</math> y la matriz identidad como matriz inicial. Los resultados de la implementación se muestran a continuación1153
1154
<div id='img-4'></div>1155
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"1156
|-1157
|[[Image:Draft_Acevedo Vazquez_103892577-Felix sin error.png|420px|Resultados de los tres métodos utilizados. El MCN utiliza un menor número de iteraciones y consume menos tiempo de cómputo.]]1158
|- style="text-align: center; font-size: 75%;"1159
| colspan="1" | '''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.1160
|}1161
1162
<div id='img-5'></div>1163
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"1164
|-1165
|[[Image:Draft_Acevedo Vazquez_103892577-Felix sin error grafica.png|300px|Gráfica de la función f(x,y)=0.00001(x⁴+y⁴).]]1166
|- style="text-align: center; font-size: 75%;"1167
| colspan="1" | '''Figura 5:''' Gráfica de la función <math>\boldsymbol {f}(x,y)=0.00001(x^4+y^4)</math>.1168
|}1169
1170
1171
{| class="floating_tableSCP wikitable" style="text-align: center; margin: 1em auto;min-width:50%;"1172
|+ style="font-size: 75%;" |<span id='table-2'></span>Tabla. 2 Número de iteraciones y tiempo, medido en segundos, de los tres métodos usando distintos puntos iniciales.1173
|- style="border-top: 2px solid;"1174
| <math display="inline">\boldsymbol {x}^0</math> 1175
| BFGS [tiempo] 1176
| DFP [tiempo] 1177
| MCN [tiempo]1178
|- style="border-top: 2px solid;"1179
| (2,1) 1180
| 32 [4.39] 1181
| 526 [73] 1182
| 13 [2.15]1183
|-1184
| (-2,1) 1185
| 31 [3.95] 1186
| 936 [129.07] 1187
| 13 [1.75]1188
|-1189
| (-2,-1) 1190
| 32 [4.49] 1191
| 526 [70.42] 1192
| 13 [2.29]1193
|-1194
| (2,-1) 1195
| 31 [4.02] 1196
| 936 [132.79] 1197
| 13 [1.88]1198
|- style="border-bottom: 2px solid;"1199
| (3,1) 1200
| 24 [3.69] 1201
| 977 [137.59] 1202
| 15 [2.94] 1203
1204
|}1205
1206
===6.2 Caso con error===1207
1208
Consideremos la función [[#eq-52|(52)]] del ejemplo anterior, pero le agregaremos un error, por lo que la función a minimizar ahora es1209
1210
<span id="eq-54"></span>1211
{| class="formulaSCP" style="width: 100%; text-align: left;" 1212
|-1213
| 1214
{| style="text-align: left; margin:auto;width: 100%;" 1215
|-1216
| style="text-align: center;" | <math>\boldsymbol {\tilde{f}}(x,y)=\boldsymbol {f}(x,y)+\boldsymbol {e}(x,y), </math>1217
|}1218
| style="width: 5px;text-align: right;white-space: nowrap;" | (54)1219
|}1220
1221
donde <math display="inline">\boldsymbol {e}(x,y)</math> está definido por1222
1223
<span id="eq-55"></span>1224
{| class="formulaSCP" style="width: 100%; text-align: left;" 1225
|-1226
| 1227
{| style="text-align: left; margin:auto;width: 100%;" 1228
|-1229
| style="text-align: center;" | <math>\boldsymbol {e}(x,y)=0.1\boldsymbol {f}(x,y)\sin{(x+y)}. </math>1230
|}1231
| style="width: 5px;text-align: right;white-space: nowrap;" | (55)1232
|}1233
1234
Se hizo uso del mismo punto inicial <math display="inline">\boldsymbol {x}^0=(2,1)^t</math>, tolerancia <math display="inline">10^{-8}</math> y matriz inicial. Los resultados obtenidos fueron los siguientes1235
1236
<div id='img-6'></div>1237
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"1238
|-1239
|[[Image:Draft_Acevedo Vazquez_103892577-Resultados error simple.png|420px|Resultados de los métodos.]]1240
|- style="text-align: center; font-size: 75%;"1241
| colspan="1" | '''Figura 6:''' Resultados de los métodos.1242
|}1243
1244
<div id='img-7'></div>1245
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"1246
|-1247
|[[Image:Draft_Acevedo Vazquez_103892577-Grafica error simple.png|300px|Gráfica de la función ̃f(x,y)=f(x,y)+e(x,y).]]1248
|- style="text-align: center; font-size: 75%;"1249
| colspan="1" | '''Figura 7:''' Gráfica de la función <math>\boldsymbol {\tilde{f}}(x,y)=\boldsymbol {f}(x,y)+\boldsymbol {e}(x,y)</math>.1250
|}1251
1252
1253
{| class="floating_tableSCP wikitable" style="text-align: center; margin: 1em auto;min-width:50%;"1254
|+ style="font-size: 75%;" |<span id='table-3'></span>Tabla. 3 Número de iteraciones y tiempo, medido en segundos, de los tres métodos usando distintos puntos iniciales.1255
|- style="border-top: 2px solid;"1256
| <math display="inline">\boldsymbol {x}^0</math> 1257
| BFGS [tiempo] 1258
| DFP [tiempo] 1259
| MCN [tiempo]1260
|- style="border-top: 2px solid;"1261
| (2,1) 1262
| 30 [4.8] 1263
| - 1264
| 13 [2.36]1265
|-1266
| (-2,1) 1267
| 31 [4.81]1268
| - 1269
| 13 [2.35]1270
|-1271
| (-2,-1) 1272
| 29 [4.41] 1273
| - 1274
| 14 [3.09]1275
|-1276
| (2,-1) 1277
| 28 [4.71] 1278
| 372 [90.37] 1279
| 14 [2.41]1280
|- style="border-bottom: 2px solid;"1281
| (3,1) 1282
| 33 [5.42] 1283
| - 1284
| 15 [2.71] 1285
1286
|}1287
1288
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.1289
1290
Consideramos la misma función [[#eq-54|(54)]], donde <math display="inline">\boldsymbol {f}(x,y)</math> está definido por [[#eq-52|(52)]] y ahora1291
1292
<span id="eq-56"></span>1293
{| class="formulaSCP" style="width: 100%; text-align: left;" 1294
|-1295
| 1296
{| style="text-align: left; margin:auto;width: 100%;" 1297
|-1298
| style="text-align: center;" | <math>\boldsymbol {e}(x,y)=0.1\boldsymbol {f}(x,y)\sin{(x^2+y^2)}. </math>1299
|}1300
| style="width: 5px;text-align: right;white-space: nowrap;" | (56)1301
|}1302
1303
Se consideró el punto inicial <math display="inline">\boldsymbol {x}^0=(2,1)^t</math>, una tolerancia de <math display="inline">10^{-8}</math> y la matriz identidad como matriz inicial. En la Figura [[#img-8|8]] se muestran los resultados obtenidos.1304
1305
<div id='img-8'></div>1306
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"1307
|-1308
|[[Image:Draft_Acevedo Vazquez_103892577-Resultados ejemplo 2.png|390px|Resultados de los métodos considerando error.]]1309
|- style="text-align: center; font-size: 75%;"1310
| colspan="1" | '''Figura 8:''' Resultados de los métodos considerando error.1311
|}1312
1313
<div id='img-9'></div>1314
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"1315
|-1316
|[[Image:Draft_Acevedo Vazquez_103892577-Grafica Felix con error.png|300px|Gráfica de la función considerando errores.]]1317
|- style="text-align: center; font-size: 75%;"1318
| colspan="1" | '''Figura 9:''' Gráfica de la función considerando errores.1319
|}1320
1321
1322
{| class="floating_tableSCP wikitable" style="text-align: center; margin: 1em auto;min-width:50%;"1323
|+ style="font-size: 75%;" |<span id='table-4'></span>Tabla. 4 Número de iteraciones y tiempo, medido en segundos, de los tres métodos considerando el error descrito y usando distintos puntos iniciales.1324
|- style="border-top: 2px solid;"1325
| <math display="inline">\boldsymbol {x}^0</math> 1326
| BFGS [tiempo (seg)] 1327
| DFP [tiempo (seg)] 1328
| MCN [tiempo (seg)]1329
|- style="border-top: 2px solid;"1330
| (2,1) 1331
| 32 [5.47] 1332
| 729 [125.09] 1333
| 14 [2.72]1334
|-1335
| (1,2) 1336
| 32 [5.53] 1337
| 371 [70.48] 1338
| 14 [3.14]1339
|-1340
| (3,1) 1341
| - 1342
| - 1343
| 15 [2.63] 1344
|-1345
| (-3,1) 1346
| 29 [4.99] 1347
| 218 [51] 1348
| 13 [3.04] 1349
|-1350
| (3,-1) 1351
| 29 [4.91] 1352
| 218 [54.7] 1353
| 13 [6.33] 1354
|- style="border-bottom: 2px solid;"1355
| (-3,-1) 1356
| - 1357
| - 1358
| 15 [2.75]1359
1360
|}1361
1362
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 <span id='citeF-9'></span>[[#cite-9|[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.1363
1364
==7 Aplicación a la solución numérica de sistemas de ecuaciones diferenciales ordinarias==1365
1366
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:1367
1368
<span id="eq-57"></span>1369
{| class="formulaSCP" style="width: 100%; text-align: left;" 1370
|-1371
| 1372
{| style="text-align: left; margin:auto;width: 100%;" 1373
|-1374
| style="text-align: center;" | <math>\frac{d\boldsymbol {y}_1}{dt}=\boldsymbol {f}_1(t,\boldsymbol {y}_1,\boldsymbol {y}_2), </math>1375
|}1376
| style="width: 5px;text-align: right;white-space: nowrap;" | (57)1377
|}1378
1379
<span id="eq-58"></span>1380
{| class="formulaSCP" style="width: 100%; text-align: left;" 1381
|-1382
| 1383
{| style="text-align: left; margin:auto;width: 100%;" 1384
|-1385
| style="text-align: center;" | <math>\frac{d\boldsymbol {y}_2}{dt}=\boldsymbol {f}_2(t,\boldsymbol {y}_1,\boldsymbol {y}_2), </math>1386
|}1387
| style="width: 5px;text-align: right;white-space: nowrap;" | (58)1388
|}1389
1390
con condiciones iniciales1391
1392
<span id="eq-59"></span>1393
{| class="formulaSCP" style="width: 100%; text-align: left;" 1394
|-1395
| 1396
{| style="text-align: left; margin:auto;width: 100%;" 1397
|-1398
| style="text-align: center;" | <math>\boldsymbol {y}_1(t_0)=y_1^0,\quad \boldsymbol {y}_2(t_0)=y_2^0. </math>1399
|}1400
| style="width: 5px;text-align: right;white-space: nowrap;" | (59)1401
|}1402
1403
Las funciones <math display="inline">\boldsymbol {f}_1</math> y <math display="inline">\boldsymbol {f}_2</math> son suficientemente suaves. Supongamos que las funciones <math display="inline">\boldsymbol {f}_1</math> y <math display="inline">\boldsymbol {f}_2</math> cumplen las condiciones del Teorema de Existencia y Unicidad dado en <span id='citeF-10'></span>[[#cite-10|[10]]], por lo cual el problema de valor inicial [[#eq-57|(57)]]-[[#eq-59|(59)]] tiene una única solución en algún intervalo del eje <math display="inline">t</math> que contiene a <math display="inline">t_0</math>. Deseamos determinar valores aproximados <math display="inline">\boldsymbol {y}_1^1,\boldsymbol {y}_1^2,\ldots ,\boldsymbol {y}_1^n,\ldots </math> y <math display="inline">\boldsymbol {y}_2^1,\boldsymbol {y}_2^2,\ldots ,\boldsymbol {y}_2^n,\ldots </math> de las soluciones <math display="inline">\boldsymbol {y}_1=\boldsymbol {\phi }(t)</math>, <math display="inline">\boldsymbol {y}_2=\boldsymbol {\Phi }(t)</math> en los puntos <math display="inline">t_n=t_0+nh</math>, con <math display="inline">n=1,2,\ldots </math>.1404
1405
En notación vectorial, el problema de valor inicial [[#eq-57|(57)]]-[[#eq-59|(59)]] puede ser escrito como1406
1407
<span id="eq-60"></span>1408
{| class="formulaSCP" style="width: 100%; text-align: left;" 1409
|-1410
| 1411
{| style="text-align: left; margin:auto;width: 100%;" 1412
|-1413
| style="text-align: center;" | <math>\boldsymbol {y}'=\boldsymbol {f}(t,\boldsymbol {y}),\quad \boldsymbol {y}(t_0)=\boldsymbol {y}_0, </math>1414
|}1415
| style="width: 5px;text-align: right;white-space: nowrap;" | (60)1416
|}1417
1418
donde <math display="inline">\boldsymbol {y}</math> es un vector con componentes <math display="inline">\boldsymbol {y}_1</math> y <math display="inline">\boldsymbol {y}_2</math>, <math display="inline">\boldsymbol {f}</math> es el vector de funciones con componentes <math display="inline">\boldsymbol {f}_1</math> y <math display="inline">\boldsymbol {f}_2</math> y <math display="inline">\boldsymbol {y}_0</math> es el vector con componentes <math display="inline">y_1^0,y_2^0</math>.1419
1420
Uno de los métodos que se utiliza para hallar la solución numérica del sistema [[#eq-60|(60)]], es el método de Euler que consiste en considerar la fórmula1421
1422
<span id="eq-61"></span>1423
{| class="formulaSCP" style="width: 100%; text-align: left;" 1424
|-1425
| 1426
{| style="text-align: left; margin:auto;width: 100%;" 1427
|-1428
| style="text-align: center;" | <math>\boldsymbol {y}_{n+1}=\boldsymbol {y}_n+h\boldsymbol {f}_n. </math>1429
|}1430
| style="width: 5px;text-align: right;white-space: nowrap;" | (61)1431
|}1432
1433
Las condiciones iniciales son usadas para determinar <math display="inline">\boldsymbol {f}_0</math>, el cual es el vector tangente a la gráfica de la solución <math display="inline">\boldsymbol {y}=\boldsymbol {\Phi }(t)</math> en el plano <math display="inline">y_1y_2</math>. Nos movemos en dirección de este vector tangente por un paso de tiempo <math display="inline">h</math> con el fin de encontrar el siguiente punto <math display="inline">\boldsymbol {y}_1</math>. Después, calculamos un nuevo vector tangente <math display="inline">\boldsymbol {f}_1</math>, nos movemos a lo largo de éste por un paso de tiempo <math display="inline">h</math> para encontrar <math display="inline">\boldsymbol {y}_2</math>, y así sucesivamente.1434
1435
Una variación del método de Euler puede ser obtenido de la siguiente manera. Dado que <math display="inline">\boldsymbol {y}=\boldsymbol {\Phi }(t)</math> es una solución del problema de valor inicial [[#eq-60|(60)]], obtenemos1436
1437
<span id="eq-62"></span>1438
{| class="formulaSCP" style="width: 100%; text-align: left;" 1439
|-1440
| 1441
{| style="text-align: left; margin:auto;width: 100%;" 1442
|-1443
| style="text-align: center;" | <math>\boldsymbol {\Phi }'(t)=\boldsymbol {f}(t,\boldsymbol {y}(t)). </math>1444
|}1445
| style="width: 5px;text-align: right;white-space: nowrap;" | (62)1446
|}1447
1448
Aproximando la derivada en [[#eq-62|(62)]] por el cociente de diferencias hacia atrás <math display="inline">\dfrac{\boldsymbol {\phi }(t_n)-\boldsymbol {\phi }(t_{n-1})}{h},</math> obteniendo1449
1450
{| class="formulaSCP" style="width: 100%; text-align: left;" 1451
|-1452
| 1453
{| style="text-align: left; margin:auto;width: 100%;" 1454
|-1455
| style="text-align: center;" | <math>\boldsymbol {\phi }(t_n)-\boldsymbol {\phi }(t_{n-1})\approx h\boldsymbol {f}(t_n,\boldsymbol {y}_n)), </math>1456
|}1457
|}1458
1459
o bien1460
1461
<span id="eq-63"></span>1462
{| class="formulaSCP" style="width: 100%; text-align: left;" 1463
|-1464
| 1465
{| style="text-align: left; margin:auto;width: 100%;" 1466
|-1467
| style="text-align: center;" | <math>\boldsymbol {y}_n=\boldsymbol {y}_{n-1}+h\boldsymbol {f}(t_n,\boldsymbol {y}_n)). </math>1468
|}1469
| style="width: 5px;text-align: right;white-space: nowrap;" | (63)1470
|}1471
1472
1473
{| style="margin: 1em auto;border: 1px solid darkgray;"1474
|-1475
|1476
:Valores iniciales <math display="inline">t_0</math> y <math display="inline">\boldsymbol {y}_0</math>, longitud de paso <math display="inline">h</math> y número de pasos <math display="inline">m</math>. Aproximación <math display="inline">\boldsymbol {y}</math>. <math>n</math> desde 1 hasta <math>m</math><math display="inline">t_n=t_{n-1}+h</math>. Resolver [[#eq-63|(63)]]. 1477
1478
1479
|-1480
| style="text-align: center; font-size: 75%;"|1481
<span id='algorithm-4'></span>'''Algoritmo. 4''' El Método de Euler Implícito1482
|}1483
1484
Aunque la implementación del Algoritmo [[#algorithm-4|4]] parece sencilla, tenemos el problema de resolver el sistema de ecuaciones [[#eq-63|(63)]]. Es en este momento donde hacemos uso del método MCN. El sistema de ecuaciones podemos plantearlo como un problema de optimización haciendo1485
1486
{| class="formulaSCP" style="width: 100%; text-align: left;" 1487
|-1488
| 1489
{| style="text-align: left; margin:auto;width: 100%;" 1490
|-1491
| style="text-align: center;" | <math>\boldsymbol {g}(\boldsymbol {a})=\boldsymbol {y}_{n-1}+h\boldsymbol {f}(t_n,\boldsymbol {a})-\boldsymbol {a},</math>1492
|}1493
|}1494
1495
y trabajando con el problema de optimización1496
1497
{| class="formulaSCP" style="width: 100%; text-align: left;" 1498
|-1499
| 1500
{| style="text-align: left; margin:auto;width: 100%;" 1501
|-1502
| style="text-align: center;" | <math>\min _{\boldsymbol {a}\in \mathbb{R}^2} \frac{\left\Vert g(\boldsymbol {a})\right\Vert ^2}{2}. </math>1503
|}1504
|}1505
1506
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ó <math display="inline">\boldsymbol {y}_{n-1}</math> como punto inicial, la matriz identidad como matriz inicial y una tolerancia de <math display="inline">10^{-8}</math>.1507
1508
Consideremos el problema dado en <span id='citeF-1'></span>[[#cite-1|[1]]], el cual involucra un sistema lineal de coeficientes constantes no homogéneo de dimensión 2.1509
1510
<span id="eq-64"></span>1511
{| class="formulaSCP" style="width: 100%; text-align: left;" 1512
|-1513
| 1514
{| style="text-align: left; margin:auto;width: 100%;" 1515
|-1516
| style="text-align: center;" | <math>\begin{bmatrix}\boldsymbol {y}_1'\\ \boldsymbol {y}_2' \end{bmatrix} = \begin{bmatrix}-2 & 1\\ 1 & -2 \end{bmatrix} \begin{bmatrix}\boldsymbol {y}_1\\ \boldsymbol {y}_2 \end{bmatrix} + \begin{bmatrix}2\sin{t}\\ 2(\cos{t}-\sin{t}) \end{bmatrix} ;\quad \begin{bmatrix}\boldsymbol {y}_1(0)\\ \boldsymbol {y}_2(0) \end{bmatrix} = \begin{bmatrix}2\\ 3 \end{bmatrix}. </math>1517
|}1518
| style="width: 5px;text-align: right;white-space: nowrap;" | (64)1519
|}1520
1521
<!-- comment1522
1523
'''Problema 2'''1524
1525
<span id=""></span>1526
{| class="formulaSCP" style="width: 100%; text-align: left;" 1527
|-1528
| 1529
{| style="text-align: left; margin:auto;width: 100%;" 1530
|-1531
| style="text-align: center;" | <math>\begin{bmatrix}\boldsymbol {y}_1'\\ \boldsymbol {y}_2' \end{bmatrix} = \begin{bmatrix}-2 & 1\\ 998 & -999 \end{bmatrix} \begin{bmatrix}\boldsymbol {y}_1\\ \boldsymbol {y}_2 \end{bmatrix} + \begin{bmatrix}2\sin{t}\\ 999(\cos{t}-\sin{t}) \end{bmatrix} ;\quad \begin{bmatrix}\boldsymbol {y}_1(0)\\ \boldsymbol {y}_2(0) \end{bmatrix} = \begin{bmatrix}2\\ 3 \end{bmatrix} </math>1532
|}1533
|}1534
1535
--> El problema tienen la siguiente solución exacta1536
1537
<span id="eq-65"></span>1538
{| class="formulaSCP" style="width: 100%; text-align: left;" 1539
|-1540
| 1541
{| style="text-align: left; margin:auto;width: 100%;" 1542
|-1543
| style="text-align: center;" | <math>\begin{bmatrix}\boldsymbol {y}_1(t)\\ \boldsymbol {y}_2(t) \end{bmatrix} = 2e^{-t} \begin{bmatrix}1\\ 1 \end{bmatrix} + \begin{bmatrix}\sin{t}\\ \cos{t} \end{bmatrix}. </math>1544
|}1545
| style="width: 5px;text-align: right;white-space: nowrap;" | (65)1546
|}1547
1548
Se tomaron un total de 1 000 puntos de la partición del intervalo temporal <math display="inline">[0,10]</math>. En la Figura [[#img-10a|10a]], se muestran la solución exacta del sistema y la obtenida usando el método BFGS en el MEI. En la Figura [[#img-10b|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.1549
1550
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.1551
1552
<div id='img-10a'></div>1553
<div id='img-10b'></div>1554
<div id='img-10'></div>1555
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"1556
|-1557
|[[Image:Draft_Acevedo Vazquez_103892577-Solucion BFGS.png|600px|Solución con el método BFGS.]]1558
|[[Image:Draft_Acevedo Vazquez_103892577-Solucion MCN.png|600px|Solución con el método MCN.]]1559
|- style="text-align: center; font-size: 75%;"1560
| (a) Solución con el método BFGS.1561
| (b) Solución con el método MCN.1562
|- style="text-align: center; font-size: 75%;"1563
| colspan="2" | '''Figura 10:''' Solución numérica encontrada usando los dos métodos.1564
|}1565
1566
<div id='img-11a'></div>1567
<div id='img-11b'></div>1568
<div id='img-11c'></div>1569
<div id='img-11d'></div>1570
<div id='img-11'></div>1571
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"1572
|-1573
|[[Image:Draft_Acevedo Vazquez_103892577-Error BFGS.png|600px|Error absoluto del método BFGS.]]1574
|[[Image:Draft_Acevedo Vazquez_103892577-Error MCN.png|600px|Error absoluto del método MCN.]]1575
|- style="text-align: center; font-size: 75%;"1576
| (a) Error absoluto del método BFGS.1577
| (b) Error absoluto del método MCN.1578
|-1579
|[[Image:Draft_Acevedo Vazquez_103892577-Error relativo BFGS.png|600px|Error relativo del método BFGS.]]1580
|[[Image:Draft_Acevedo Vazquez_103892577-Error relativo MCN.png|600px|Error relativo del método MCN.]]1581
|- style="text-align: center; font-size: 75%;"1582
| (c) Error relativo del método BFGS.1583
| (d) Error relativo del método MCN.1584
|- style="text-align: center; font-size: 75%;"1585
| colspan="2" | '''Figura 11:''' Error de los métodos en cada componente de la solución.1586
|}1587
1588
Ahora, consideremos el problema no lineal dado en <span id='citeF-1'></span>[[#cite-1|[1]]].1589
1590
{| class="formulaSCP" style="width: 100%; text-align: left;" 1591
|-1592
| 1593
{| style="text-align: left; margin:auto;width: 100%;" 1594
|-1595
| style="text-align: center;" | <math>\boldsymbol {y}_1'=\dfrac{1}{\boldsymbol {y}_1}-\boldsymbol {y}_2\frac{e^{t^2}}{t^2}-t,\quad \boldsymbol {y}_1(1.5)=2/3,</math>1596
|-1597
| style="text-align: center;" | <math> \boldsymbol {y}_2'=\dfrac{1}{\boldsymbol {y}_2}-e^{t^2}-2te^{-t^2},\quad \boldsymbol {y}_2(1.5)=e^{-9/4}. </math>1598
|}1599
| style="width: 5px;text-align: right;white-space: nowrap;" | (66)1600
|}1601
1602
El problema tienen la siguiente solución exacta1603
1604
{| class="formulaSCP" style="width: 100%; text-align: left;" 1605
|-1606
| 1607
{| style="text-align: left; margin:auto;width: 100%;" 1608
|-1609
| style="text-align: center;" | <math>\boldsymbol {y}_1(t)=\dfrac{1}{t},</math>1610
|-1611
| style="text-align: center;" | <math> \boldsymbol {y}_2(t)=e^{-t^2}. </math>1612
|}1613
| style="width: 5px;text-align: right;white-space: nowrap;" | (67)1614
|}1615
1616
Se tomaron un total de 2 000 puntos de la partición del intervalo temporal <math display="inline">[1.5,1.7]</math>. En la Figura [[#img-12a|12a]], se muestran la solución exacta del sistema y la obtenida usando el método BFGS en el MEI. En la Figura [[#img-12b|12b]], se muestran la solución exacta del sistema y la obtenida usando el MCN.1617
1618
<div id='img-12a'></div>1619
<div id='img-12b'></div>1620
<div id='img-12'></div>1621
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"1622
|-1623
|[[Image:Draft_Acevedo Vazquez_103892577-Solucion E2 BFGS.png|600px|Solución con el método BFGS.]]1624
|[[Image:Draft_Acevedo Vazquez_103892577-Solucion E2 MCN.png|600px|Solución con el método MCN.]]1625
|- style="text-align: center; font-size: 75%;"1626
| (a) Solución con el método BFGS.1627
| (b) Solución con el método MCN.1628
|- style="text-align: center; font-size: 75%;"1629
| colspan="2" | '''Figura 12:''' Solución numérica encontrada usando los dos métodos.1630
|}1631
1632
<div id='img-13a'></div>1633
<div id='img-13b'></div>1634
<div id='img-13c'></div>1635
<div id='img-13d'></div>1636
<div id='img-13'></div>1637
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"1638
|-1639
|[[Image:Draft_Acevedo Vazquez_103892577-Error E2 BFGS.png|600px|Error absoluto del método BFGS.]]1640
|[[Image:Draft_Acevedo Vazquez_103892577-Error E2 MCN.png|600px|Error absoluto del método MCN.]]1641
|- style="text-align: center; font-size: 75%;"1642
| (a) Error absoluto del método BFGS.1643
| (b) Error absoluto del método MCN.1644
|-1645
|[[Image:Draft_Acevedo Vazquez_103892577-Error relativo E2 BFGS.png|600px|Error relativo del método BFGS.]]1646
|[[Image:Draft_Acevedo Vazquez_103892577-Error relativo E2 MCN.png|600px|Error relativo del método MCN.]]1647
|- style="text-align: center; font-size: 75%;"1648
| (c) Error relativo del método BFGS.1649
| (d) Error relativo del método MCN.1650
|- style="text-align: center; font-size: 75%;"1651
| colspan="2" | '''Figura 13:''' Error de los métodos en cada componente de la solución.1652
|}1653
1654
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.1655
1656
Ahora, consideremos el problema no lineal1657
1658
{| class="formulaSCP" style="width: 100%; text-align: left;" 1659
|-1660
| 1661
{| style="text-align: left; margin:auto;width: 100%;" 1662
|-1663
| style="text-align: center;" | <math>\boldsymbol {y}_1'=\dfrac{4\boldsymbol {y}_1}{t},\quad \boldsymbol {y}_1(1)=10^{-4},</math>1664
|-1665
| style="text-align: center;" | <math> \boldsymbol {y}_2'=\dfrac{4\boldsymbol {y}_2}{t},\quad \boldsymbol {y}_2(1)=10^{-4}, </math>1666
|}1667
| style="width: 5px;text-align: right;white-space: nowrap;" | (68)1668
|}1669
1670
con <math display="inline">a=10^{-4}</math>. El problema tienen la siguiente solución exacta1671
1672
{| class="formulaSCP" style="width: 100%; text-align: left;" 1673
|-1674
| 1675
{| style="text-align: left; margin:auto;width: 100%;" 1676
|-1677
| style="text-align: center;" | <math>\boldsymbol {y}_1(t)=10^{-4}t^4,</math>1678
|-1679
| style="text-align: center;" | <math> \boldsymbol {y}_2(t)=10^{-4}t^4. </math>1680
|}1681
| style="width: 5px;text-align: right;white-space: nowrap;" | (69)1682
|}1683
1684
Se tomaron un total de 1 000 puntos de la partición del intervalo temporal <math display="inline">[1,2]</math>. En la Figura [[#img-14a|14a]], se muestran la solución exacta del sistema y la obtenida usando el método BFGS en el MEI. En la Figura [[#img-14b|14b]], se muestran la solución exacta del sistema y la obtenida usando el MCN.1685
1686
<div id='img-14a'></div>1687
<div id='img-14b'></div>1688
<div id='img-14'></div>1689
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"1690
|-1691
|[[Image:Draft_Acevedo Vazquez_103892577-Solución E3 BFGS.png|600px|Solución con el método BFGS.]]1692
|[[Image:Draft_Acevedo Vazquez_103892577-Solución E3 MCN.png|600px|Solución con el método MCN.]]1693
|- style="text-align: center; font-size: 75%;"1694
| (a) Solución con el método BFGS.1695
| (b) Solución con el método MCN.1696
|- style="text-align: center; font-size: 75%;"1697
| colspan="2" | '''Figura 14:''' Solución numérica encontrada usando los dos métodos.1698
|}1699
1700
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.1701
1702
En la Figura [[#img-15|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.1703
1704
<div id='img-15a'></div>1705
<div id='img-15b'></div>1706
<div id='img-15c'></div>1707
<div id='img-15d'></div>1708
<div id='img-15'></div>1709
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"1710
|-1711
|[[Image:Draft_Acevedo Vazquez_103892577-Error absoluto E3 BFGS.png|600px|Error absoluto del método BFGS.]]1712
|[[Image:Draft_Acevedo Vazquez_103892577-Error absoluto E3 MCN.png|600px|Error absoluto del método MCN.]]1713
|- style="text-align: center; font-size: 75%;"1714
| (a) Error absoluto del método BFGS.1715
| (b) Error absoluto del método MCN.1716
|-1717
|[[Image:Draft_Acevedo Vazquez_103892577-Error relativo E3 BFGS.png|600px|Error relativo del método BFGS.]]1718
|[[Image:Draft_Acevedo Vazquez_103892577-Error relativo E3 MCN.png|600px|Error relativo del método MCN.]]1719
|- style="text-align: center; font-size: 75%;"1720
| (c) Error relativo del método BFGS.1721
| (d) Error relativo del método MCN.1722
|- style="text-align: center; font-size: 75%;"1723
| colspan="2" | '''Figura 15:''' Error de los métodos en cada componente de la solución.1724
|}1725
1726
Ahora, consideremos el ejemplo dado en <span id='citeF-10'></span>[[#cite-10|[10]]] dado por un modelo de Lotka-Volterra1727
1728
{| class="formulaSCP" style="width: 100%; text-align: left;" 1729
|-1730
| 1731
{| style="text-align: left; margin:auto;width: 100%;" 1732
|-1733
| style="text-align: center;" | <math>\boldsymbol {y}_1'=\boldsymbol {y}_1-0.5\boldsymbol {y}_1\boldsymbol {y}_2,\quad \boldsymbol {y}_1(0)=2.5,</math>1734
|-1735
| style="text-align: center;" | <math> \boldsymbol {y}_2'=-0.75\boldsymbol {y}_2+0.25\boldsymbol {y}_1\boldsymbol {y}_2,\quad \boldsymbol {y}_2(0)=1, </math>1736
|}1737
| style="width: 5px;text-align: right;white-space: nowrap;" | (70)1738
|}1739
1740
donde <math display="inline">\boldsymbol {y}_1</math> y <math display="inline">\boldsymbol {y}_2</math> denotan la población de presa y depredador, respectivamente. Se tomaron un total de 7 000 puntos de la partición del intervalo temporal <math display="inline">[0,30]</math>. En la Figura [[#img-16a|16a]], se muestra la solución obtenida usando el método BFGS en el MEI. En la Figura [[#img-16b|16b]], se muestra la solución obtenida usando el MCN.1741
1742
<div id='img-16a'></div>1743
<div id='img-16b'></div>1744
<div id='img-16'></div>1745
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"1746
|-1747
|[[Image:Draft_Acevedo Vazquez_103892577-Solucion LV 7000 BFGS.png|600px|Solución con el método BFGS.]]1748
|[[Image:Draft_Acevedo Vazquez_103892577-Solucion LV 7000 MCN.png|600px|Solución con el método MCN.]]1749
|- style="text-align: center; font-size: 75%;"1750
| (a) Solución con el método BFGS.1751
| (b) Solución con el método MCN.1752
|- style="text-align: center; font-size: 75%;"1753
| colspan="2" | '''Figura 16:''' Solución numérica encontrada usando los dos métodos.1754
|}1755
1756
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.1757
1758
==8 Conclusiones==1759
1760
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. 1761
1762
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.1763
1764
===BIBLIOGRAFÍA===1765
1766
<div id="cite-1"></div>1767
'''[[#citeF-1|[1]]]''' Lambert, J. D. (1991) "Numerical Methods for Ordinary Differential Systems: The Initial Value Problem". John Wiley & Sons, Inc.1768
1769
<div id="cite-2"></div>1770
'''[[#citeF-2|[2]]]''' Davidon, W C. (1959) "VARIABLE METRIC METHOD FOR MINIMIZATION", Volume. Technical Report ANL–5990 (revised), Argonne National Laboratory1771
1772
<div id="cite-3"></div>1773
'''[[#citeF-3|[3]]]''' Fletcher, R. and Powell, M. J. D. (1963) "A Rapidly Convergent Descent Method for Minimization", Volume 6. The Computer Journal 2 163-1681774
1775
<div id="cite-4"></div>1776
'''[[#citeF-4|[4]]]''' Nocedal, Jorge and Wright, Stephen J. (2006) "Numerical optimization". Springer, 2nd Edition1777
1778
<div id="cite-5"></div>1779
'''[[#citeF-5|[5]]]''' M. Bazaraa and H. Sherali and C. M. Shetty. (2006) "Unconstrained Optimization". Nonlinear Programming. John Wiley & Sons, Ltd 343-4671780
1781
<div id="cite-6"></div>1782
'''[[#citeF-6|[6]]]''' Neculai Andrei. (2020) "Nonlinear Conjugate Gradient Methods for Unconstrained Optimization", Volume. Springer International Publishing, 1st Edition1783
1784
<div id="cite-7"></div>1785
'''[[#citeF-7|[7]]]''' Martínez, José Mario. (1992) "Fixed-Point Quasi-Newton Methods", Volume 29. SIAM Journal on Numerical Analysis 5 1413-14341786
1787
<div id="cite-8"></div>1788
'''[[#citeF-8|[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–9871789
1790
<div id="cite-9"></div>1791
'''[[#citeF-9|[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-2091792
1793
<div id="cite-10"></div>1794
'''[[#citeF-10|[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 Edition1795
1796
<div id="cite-11"></div>1797
'''[11]''' Fletcher, R. (2000) "Newton-Like Methods". Practical Methods of Optimization. John Wiley & Sons, Ltd 44-791798
1799
<!-- comment-->1800
Return to Oliveros et al 2021b.
Back to Top
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?