gradiente conjugado

Programación y Métodos Numéricos

Carlos Conde, Arturo Hidalgo y Alfredo López
ETSI Minas de la Universidad Politécnica de Madrid

EJERCICIO RESUELTO SOBRE MÉTODOS ITERATIVOS DE RESOLUCIÓN
DESISTEMAS DE ECUACIONES LINEALES
Dado el sistema de ecuaciones lineales:
⎧ x + 2y = 3
⎨
⎩2 x + 5y = 7
Se pide:
a)
Determinar si es resoluble por el método de gradiente
conjugado.
b)
Obtenerla funcional cuadrática asociada a este sistema.
c)
Realizar dos iteraciones del método de gradiente conjugado a
partir del vector semilla x(0) = (2, 2)T.
Solución:
a)
El sistema dado puedeescribirse como Ax = b, con:
⎛1 2⎞
A=⎜
⎟
⎝2 5⎠

⎛ 3⎞
b=⎜ ⎟
⎝7⎠

⎛ x⎞
x=⎜ ⎟
⎝ y⎠

Para que el método de gradiente conjugado pueda aplicarse es necesario que la
matriz A sea definidapositiva, lo cual puede comprobarse viendo si todos sus valores
propios son reales y estrictamente positivos:
2 ⎞
⎧ λ1 = 5.82…
⎛1 − λ
det ( Α − λ I ) = det ⎜
⎟ = (1 − λ )( 5 − λ ) − 4 = 0 ⇒ ⎨λ = 0.17…
5−λ⎠
⎝ 2
⎩ 2

luego la matriz A es definida positiva.
b)

La funcional cuadrática asociada es:
J ( x, y ) =

=

c)

⎡1 2⎤ ⎛ x ⎞
⎛ x⎞
y) ⎢
⎥ ⎜ y ⎟ − (3 7) ⎜ y ⎟ + c =
⎣2 5⎦ ⎝ ⎠⎝ ⎠

1 T
1
x Ax - bT x + c = ( x
2
2

1 2
5
x + 2 xy + y 2 − 3 x + 7 y + c
2
2

La primera dirección de descenso es:
⎛ 3 ⎞ ⎡ 1 2 ⎤ ⎛ 2 ⎞ ⎛ −3 ⎞
0
0
0
d( ) = r ( ) = b − Ax( ) = ⎜ ⎟ −⎢
⎥⎜ ⎟ = ⎜ ⎟
⎝ 7 ⎠ ⎣ 2 5 ⎦ ⎝ 2 ⎠ ⎝ −7 ⎠

y el parámetro de descenso:

1

Programación y Métodos Numéricos

ρ=

( )
( d( ) ) A d( )
d(
0

0)

T

T

d(

0)

0

CarlosConde, Arturo Hidalgo y Alfredo López
ETSI Minas de la Universidad Politécnica de Madrid

⎛ 3⎞
7) ⎜ ⎟
58
⎝7⎠
=
=
= 0.1715976331
⎛ 1 2 ⎞⎛ 3 ⎞ 338
(3 7) ⎜
⎟⎜ ⎟
⎝ 2 5 ⎠⎝ 7 ⎠

(3

⎛ 2⎞
⎛−3 ⎞ ⎛ 1.485207101 ⎞
1
0
0
x( ) = x( ) + ρ d( ) = ⎜ ⎟ + 0.1715976331⎜ ⎟ = ⎜
⎟
⎝ 2⎠
⎝ −7 ⎠ ⎝ 0.798816568 ⎠
⎛ −3 ⎞
⎛ 1 2 ⎞ ⎛ −3 ⎞ ⎛ -0.082840237 ⎞
1
0
0
r ( ) = r ( ) − ρ Ad( ) = ⎜ ⎟ −...