geotecnica

El método de Newton
(P)

Minimizar f ( x)
x ∈ ℝn

En el método de Newton la dirección de búsqueda se define como:

[

]

−1

d ( x ) = − ∇ 2 f ( x ) ∇f T ( x )
La dirección de búsquedase encuentra minimizando el problema:

~
Minimizar f ( x + d)
~

donde f es la aproximación cuadrática de f en x .
Teorema: el método de Newton definido por la iteración xk +1 = xk + d( xk )tiene convergencia local con orden de convergencia p ≥ 2 .
1

El método de Newton
(P)

Minimizar f ( x)
x∈ℝ

n

6

4

f ( x ) = x T Qx
1 1 
Q=
1 10 



x0 = (10, 1)T2

0

-2

-4

-6
-4

-2

0

2

4

Rojo: Steepest descent
Azul: Newton

6

8

10

12

2

El método de Newton
(P)

Minimizar f ( x)
x ∈ ℝn

Correcciones:
1)Introducir búsqueda lineal
a) La dirección puede no ser de descenso.
b) El orden de convergencia puede ser menor de 2.
2) Modificar la matriz del sistema lineal.

3

El método de las direccionesconjugadas
(P)

Minimizar f ( x) =

1 T
x Qx − b T x
2

Con Q positiva definida

x ∈ ℝn
En el método de las direcciones conjugadas se conocen n direcciones d i ≠ 0
que satisfacen:
dT Qd j= 0, ∀i ≠ j
i
En el método de las direcciones conjugadas se considera d k como dirección de
búsqueda del paso k . La iteración queda definida como:

xk +1 = xk + α k d k

αk = −

∇f ( xk )dk
dT Qd k
k
4

El método de las direcciones
conjugadas
(P)

Minimizar f ( x) =

1 T
x Qx − b T x
2

x ∈ ℝn
Teorema: El método de las direcciones conjugadas converge a la solución.Teorema (Expanding subspace theorem):
Sea Bk = [d 0 ,..., d k −1 ], la sucesión generada por el algoritmo tiene la propiedad
que xk minimiza f en el espacio x0 + Bk .

5

El método del gradienteconjugado
(P)

Minimizar f ( x) =

1 T
x Qx − b T x
2

x ∈ ℝn
T
Sea g k = ∇f ( xk ) .

Comenzando por x0 , el método define d0 = −g 0 y, en la iteración k :

xk +1 = xk + α k d k
gT...