[Link] Métodos Cuasi-Newton. — Cap.

XXIII

CAPITULO XXIII. METODOS CUASI-NEWTON

1. EL METODO DE NEWTON MODIFICADO

El mayor inconveniente al realizar el proceso de Newton

x(k+1) = x(k) − J −1 (x(k) ) F(x(k) ) , (k = 0, 1, 2, . . .) (XXIII.1)

es la necesidad de calcular la matriz inversa J −1 (x(k) ) en cada paso. Si la matriz inversa

J −1 (x(k) ) es continua en la proximidad de la solución deseada p y la aproximación inicial
x(0) está suficientemente próxima a p, entonces podemos escribir de forma aproximada
J −1 (x(k) ) ≈ J −1 (x(0) ). Llegamos de este modo al proceso de Newton modificado:

ξ (k+1) = ξ (k) − J −1 (x(0) ) F(ξ (k) ) , (k = 0, 1, 2, . . .) , (XXIII.2)

donde ξ (0) = x(0) . Obsérvese que las primeras aproximaciones ξ (1) y x(1) coinciden para
los procesos (XXIII.1) y (XXIII.2).

2. EL METODO DE BROYDEN
Una debilidad importante del método de Newton para resolver sistemas de ecuaciones
no lineales es la necesidad de calcular la matriz Jacobiana en cada iteración y resolver un
sistema lineal n × n asociado a esta matriz.
Para ilustrar la magnitud de esta debilidad, consideremos la cantidad de cálculos
necesarios para llevar a cabo una iteración del método de Newton. La matriz Jacobiana
asociada a un sistema de n ecuaciones no lineal escrita en la forma F(x) = 0 requiere la
determinación y evaluación de las n2 derivadas parciales de las n componentes de F. En
la mayorı́a de los casos, la evaluación exacta de las derivadas parciales es complicada y en
muchas ocasiones imposible. Para superar esta dificultad se pueden usar aproximaciones
de diferencia finita a las derivadas parciales. Por ejemplo,

∂fj (i) fj (x(i) + ek h) − fj (x(i) )

(x ) ≈ , (XXIII.3)
∂xk h
donde h es pequeño en valor absoluto y ek es el vector cuyo único elemento diferente
de cero es 1 en la k−ésima coordenada. Esta aproximación, sin embargo, requiere aún
la realización de por lo menos n2 evaluaciones funcionales escalares para aproximar el
Jacobiano y no reduce la cantidad de cálculos, que es en general O(n3 ), para resolver
el sistema lineal que contiene al Jacobiano aproximado. El esfuerzo computacional total
para sólo una iteración del método de Newton es entonces de por lo menos, (n2 + n)
evaluaciones funcionales escalares (n2 para la evaluación de la matriz Jacobiana y n para
la evaluación de F) junto con O(n3 ) operaciones aritméticas para resolver el sistema lineal.
Esta cantidad de esfuerzo computacional es prohibitiva excepto para valores relativamente
pequeños de n y para funciones escalares fáciles de evaluar.
En este apartado consideraremos una generalización del método de la secante en
sistemas de ecuaciones no lineales y, en particular, consideraremos una técnica conocida

307
[Link] Métodos Cuasi-Newton. — Cap. XXIII

como el método de Broyden. El método requiere solamente de n evaluaciones fun-

cionales escalares por iteración y reduce también el número de cálculos aritméticos a
O(n2 ). Es uno de los método conocidos como renovaciones de secante de mı́nimo cambio
que producen los algoritmos llamados cuasi-Newton. Estos métodos reemplazan la matriz
Jacobiana en el método de Newton por una matriz de aproximación que se renueva en
cada iteración. La desventaja de estos métodos consiste en que se pierde la convergencia
cuadrática del método de Newton y se reemplaza por una convergencia llamada super-
(i+1)
lineal. Esto implica que lim ||x −p||
||x(i) −p||
= 0, donde p denota la solución a F(x) = 0 y
i→∞
x(i) y x(i+1) son aproximaciones consecutivas.
En la mayorı́a de las aplicaciones, la reducción a la convergencia superlineal es un
cambio más que aceptable por la reducción en la cantidad de cómputo. Otra desventaja
adicional consiste en que, a diferencia del método de Newton, los métodos cuasi-Newton
no son autocorregibles. El método de Newton, por ejemplo, generalmente corrige errores
de redondeo mediante iteraciones sucesivas; en cambio, el método de Broyden no lo hace.
Supongamos que se da una aproximación inicial x(0) a la solución p de F(x) = 0. Cal-
culamos la siguiente aproximación x(1) de la misma manera que en el método de Newton
(x(1) = x(0) − J −1 (x(0) ) F(x(0) )), o, si no conviene determinar J(x(0) ) exactamente, us-
amos la ecuación de diferencia dada en (XXIII.3) para aproximar las derivadas parciales.
Sin embargo, para calcular x(2) , nos apartamos del método de Newton y examinamos el
método de la secante para una sola ecuación no lineal. El método de la secante usa la
aproximación f (xx11)−f
−x0
(x0 )
para reemplazarla por f 0 (x1 ) en el método de Newton. Para
sistemas no lineales, x(1) − x(0) es un vector y el cociente correspondiente está indefinido.
Sin embargo, el método procede de manera similar reemplazando la matriz J(x(1) ) en el
método de Newton por una matriz A1 con la propiedad de que

A1 (x(1) − x(0) ) = F(x(1) ) − F(x(0) ) . (XXIII.4)

La ecuación (XXIII.4) no define a una matriz sóla debido a que no describe cómo actua
A1 en vectores ortogonales a x(1) − x(0) . Como no se tiene información disponible acerca
de los cambios de F en dirección ortogonal a x(1) − x(0) se pide además que

A1 z = J(x(0) ) z siempre que (x(1) − x(0) )t · z = 0 . (XXIII.5)

Esta condición especifica que cualquier vector ortogonal a x(1) − x(0) no será afectado
por la renovación de J(x(0) ), que se utilizó para calcular x(1) , a A1 , y que se usará en la
determinación de x(2) .
Las condiciones (XXIII.4) y (XXIII.5) definen únicamente a A1 como

[F(x(1) ) − F(x(0) ) − J(x(0) ) (x(1) − x(0) )] (x(1) − x(0) )t

A1 = J(x(0) ) + .
||x(1) − x(0) ||22

Es esta matriz la que se usa en lugar de J(x(1) ) para determinar x(2) :

x(2) = x(1) − A−1

1 F(x
(1)
).

308
[Link] Métodos Cuasi-Newton. — Cap. XXIII

El método se puede repetir entonces para encontrar x(3) usando A1 en lugar de A0 =

J(x(0) ) y con x(2) y x(1) en lugar de x(1) y x(0) . En general, una vez que se ha encontrado
x(i) , se calcula x(i+1) mediante

[F(x(i) ) − F(x(i−1) ) − Ai−1 (x(i) − x(i−1) )] (x(i) − x(i−1) )t

Ai = Ai−1 + , (XXIII.6)
||x(i) − x(i−1) ||22

x(i+1) = x(i) − A−1

i F(x(i) ) . (XXIII.7)

Introduciendo la notación yi = F(x(i) ) − F(x(i−1) ) y si = x(i) − x(i−1) la fórmula

(XXIII.6) se reescribe como

(yi − Ai−1 si ) t
Ai = Ai−1 + si . (XXIII.60 )
||si ||22

Si el método se lleva a cabo como se indica en las ecuaciones (XXIII.6) y (XXIII.7),

el número de evaluaciones funcionales escalares se reduce de (n2 + n) a n, pero el método
aún requiere de O(n3 ) cálculos para resolver el sistema lineal n × n asociado Ai yi =
−F(x(i) ). Y entonces no tendrı́a justificación emplear el método en esta forma debido
a la reducción de la convergencia cuadrática del método de Newton a la convergencia
superlineal. Sin embargo, se puede incorporar una mejorı́a considerable empleando la
fórmula de inversión matricial de Sherman y Morrison. Este resultado dice que si A es
una matriz no singular y x e y son vectores, entonces A + x yt es no singular siempre
que yt A−1 x 6= −1, y

A−1 x yt A−1
(A + x yt )−1 = A−1 − . (XXIII.8)
1 + yt A−1 x

Esta fórmula permite calcular A−1 i directamente de A−1 i−1 , eliminando la necesidad de
invertir una matriz en cada iteración. Tomando A = Ai−1 , x = (yi −A i−1 si )
||si ||22
, e y = si , las
0
fórmulas (XXIII.6 ) junto con la (XXIII.8) implican que
³ ´
−1 (yi −Ai−1 si ) t
³ (y − A s ) ´−1 Ai−1 ||s || 2 si A−1 i−1
i i−1 i
A−1 sti = A−1
i
i = Ai−1 + 2 i−1 − ³2 ´ =
||si ||2 1 + sti A−1 (y i −A i−1 is )
i−1 2
||si ||2
¡ −1 ¢ t −1 ¡ −1
¢ t −1
A i−1 y i − s i s A
i i−1 s i − A i−1 y i si Ai−1
= A−1
i−1 − 2 t −1 2
= A−1
i−1 + t −1 .
||si ||2 + si Ai−1 yi − ||si ||2 si Ai−1 yi

Esta fórmula implica sólo multiplicación de matrices en cada paso y requiere de O(n2 )
cálculos aritméticos.
Algoritmo de Broyden para sistemas no lineales.
==================================================
Para aproximar una solución del sistema no lineal F(x) = 0, dada una aproximación
inicial x:
Entrada: número n de ecuaciones e incógnitas; aproximación inicial x = (x1 , x2 , . . .,
xn )t ; tolerancia T OL; número máximo de iteraciones N0 ;

309
[Link] Métodos Cuasi-Newton. — Cap. XXIII

Salida: solución aproximada x = (x1 , x2 , . . ., xn )t o mensaje de que el número de

iteraciones fue excedido.
∂fi (x)
Paso 1: tomar A0 = J(x) donde J(x)ij = ∂xj para 1 ≤ i, j ≤ n;

v = F(x) ; (N ota : v = F(x(0) ) ; )

Paso 2: tomar A = A−1 ;

Paso 3: tomar k = 1;

s = −A v ; (N ota : s = s1 ; )

x=x+s ; (N ota : x = x(1) ; )

Paso 4: mientras que k ≤ N0 seguir pasos 5–13;

Paso 5: tomar
w=v; (Guardar v ; )
v = F(x) ; (N ota : v = F(x(k) ) ; )
y =v−w ; (N ota : y = y(k) ; )

Paso 6: tomar

z = −A y ; (N ota : z = −A−1
k−1 yk ; )

Paso 7: tomar

p = −st z ; (N ota : p = stk A−1

k−1 yk ; )

Paso 8: tomar

C = pI + (s + z) st ; (N ota : C = stk A−1 −1 t

k−1 yk I + (sk + Ak−1 yk ) sk ; )

Paso 9: tomar

A = C A/p ; (N ota : A = A−1

k ;)

Paso 10: tomar

s = −A v ; (N ota : s = −A−1
k F(x
(k)
) ;)

Paso 11: tomar

x=x+s ; (N ota : x = x(k) ; )

Paso 12: si ||s|| < T OL entonces SALIDA (x = (x1 , x2 , . . . , xn )t );

(procedimiento completado satisfactoriamente) PARAR;
Paso 13: tomar k = k + 1;
Paso 14: SALIDA (0 Número máximo N0 de iteraciones excedido, N0 = 0 , N0 );
PARAR.
==================================================

310
[Link] Métodos Cuasi-Newton. — Cap. XXIII

Veamos ahora una aplicación del método de Broyden, reconsiderando el sistema no

lineal del ejemplo 1 del Capı́tulo XXXI, que se resolvió entonces por el método de Newton.
Ejemplo 1.
Consideremos el sistema no lineal dado por
1
3 x1 − cos(x2 x3 ) − =0 ,
2
x21 − 81 (x2 + 0.1)2 + sin x3 + 1.06 = 0 ,
10π − 3
e−x1 x2 + 20 x3 + =0 .
3
La matriz Jacobiana para este sistema es
 
3 x3 sin(x2 x3 ) x2 sin(x2 x3 )
J(x1 , x2 , x3 ) =  2 x1 −162(x2 + 0.1) cos x3  .
−x2 e−x1 x2 −x1 e−x1 x2 20

Con x(0) = (0.1, 0.1, −0.1)t , tenemos F(x(0) ) = (−1.199949, −2.269832, 8.462026)t .
 
3 9.999836 × 10−4 −9.999836 × 10−4
A0 = J(x(0) ) =  0.2 −323.9999 0.9950041  ,
−2 −2
−9.900498 × 10 −9.900498 × 10 20
 
0.3333331 1.023852 × 10−5 1.615703 × 10−5
A−1
0 = J(x ) =  2.108606 × 10−3 −3.086882 × 10−2 1.535838 × 10−3  ,
(0) −1

1.660522 × 10−3 −1.527579 × 10−4 5.000774 × 10−2

x(1) = x(0) − A−1

0 F(x
(0)
) = (0.4998693, 1.946693 × 10−2 , −0.5215209)t ,
F(x(1) ) = (−3.404021 × 10−4 , −0.3443899, 3.18737 × 10−2 )t ,
y(1) = F(x(1) ) − F(x(0) ) = (1.199608, 1.925442, −8.430152)t ,
s1 = (0.3998693, −8.053307 × 10−2 , −0.4215209)t ,
st1 A−1
0 y1 = 0.3424604 ,
1.0
A−1 −1
1 = A0 + [(s1 − A−1 t −1
0 y 1 ) s 1 A0 ] =
 0.3424604 
0.3333781 1.11077 × 10−5 8.944584 × 10−6
=  −2.021271 × 10−3 −3.094847 × 10−2 2.196909 × 10−3  ,
1.022381 × 10−3 −1.650679 × 10−4 5.010987 × 10−2
y
x(2) = x(1) − A−1
1 F(x
(1)
) = (0.4999863, 8.737888 × 10−3 , −0.5231746)t .
Los resultados de las otras iteraciones se muestran en la tabla siguiente:
Tabla 1

(k) (k) (k)

k x1 x2 x3 ||x(k) − x(k−1) ||∞
3 0.5000066 8.672215 × 10−4 −0.5236918 7.88 × 10−3
4 0.5000005 6.087473 × 10−5 −0.5235954 8.12 × 10−4
5 0.5000002 −1.445223 × 10−6 −0.5235989 6.24 × 10−5

311
[Link] Métodos Cuasi-Newton. — Cap. XXIII

EJERCICIOS.

1. Usar el método de Newton modificado para aproximar las soluciones a los

sistemas no lineales dados en los dos capı́tulos anteriores. Iterar hasta que
||x(i) − x(i−1) ||∞ < 10−5 . Comparar el número de iteraciones requerido
para esta precisión con el número de iteraciones requerido por la aproxi-
mación correspondiente del método de Newton calculada en los ejercicios
del Capı́tulo XXII.
2. Usar el algoritmo de Broyden para aproximar las soluciones a los sistemas
no lineales dados en los dos capı́tulos anteriores. Iterar hasta que ||x(i) −
x(i−1) ||∞ < 10−5 . Comparar el número de iteraciones requerido para esta
precisión con el número de iteraciones requerido por la aproximación cor-
respondiente del método de Newton calculada en los ejercicios del Capı́tulo
XXII.

312