Metodos Iterativos

Lecci´
on F

Sistemas de ecuaciones lineales.
M´
etodos iterativos
Los m´etodos iterativos tienen la desventaja de que no se pueden aplicar, por lo menos de forma
elemental, a cualquier sistema de ecuaciones Ax = B y tienen la ventaja de que son m´as eficaces
para sistemas cuyo orden es superior a 1000.

F.1.

M´
etodo de Jacobi

Pr´
actica a

Consideramos las dos expresiones equivalentes de unmismo sistema



x = 1/5(−7 − x2 + x3 )

 1




5x1 + x2 − x3 = −7


1)

−x1 + 3x2
= 1



 x1 + x2 + 6x3 = 11

;

2)

x2 = 1/3(1 + x1 )



 x3 = 1/6(11 − x1 − x2 )

donde el sistema 2) ha sido obtenido a partir del 1) despejando la x de los elementos diagonales.
Matricialmente, los sistemas anteriores tienen la expresi´on:
1) Ax = B;

2) x = Hx + C

para H y C la matriz y elvector que se obtienen a partir de A y B de la siguiente manera:
Dada A consideramos su parte diagonal, D, su parte triangular inferior, I, y su parte triangular
superior, S; claramente, se verifica A = I +D +S con lo que el sistema Ax = (I +D +S)x = B
es equivalente a Dx = −(I + S)x + B y tambi´en equivalente a
x = HJ x + C

(F.1)

donde HJ = −D−1 (I + S) y C = D−1 B
En nuestro caso concreto:




0−1/5 1/5




HJ =  1/3
0
0 ;


−1/6 −1/6 0
45





−7/5




C =  1/3 


11/6

46

´ F. SISTEMAS DE ECUACIONES LINEALES. METODOS
´
LECCION
ITERATIVOS
Ejecutando el listado
H=[0 -1/5 1/5;1/3 0 0;-1/6 -1/6 0] nInf=norm(H,inf), n2=norm(H,2),
n1=norm(H,1)
comprobamos que H
las igualdades:

x

(0)

ind
2

= δ < 1. En consecuencia, si {x(k) } denota la sucesi´on definida por




0

 
=  0 ;
 
0



x(k+1) = H · x(k) + C = 


(k)
(k)
1/5(−7 − x2 + x3 )
(k)
1/3(1 + x1 )
(k)
(k)
1/6(11 − x1 − x2 )







(F.2)

se verifica que {x(k) } es una sucesi´on de Cauchy ya que

x(p+m) − x(p) ≤ x(p+m) − x(p+m−1) + · · · + x(p+1) − x(p)
= H p+m−1 (x(1) − x(0) ) + · · · + H (p−1 (x(1) − x(0) )
≤ x(1) − x(0) ·

H p+m−1 + · · · + H p−1


p+m−1

(1)

≤ x

(0)

−x

·


Hk=p−1

k



∞

δk 

≤ x(1) − x(0) · 
k=p−1

=

δ p−1
1−δ

x(1) − x(0)

p→+∞

−→

0

y, por tanto, que {x(k) } converge a un u
´nico punto x
ˆ que verifica
x
ˆ = HJ x
ˆ+C
que es lo mismo que decir que x
ˆ es la u
´nica soluci´on del sistema Ax = B o de su equivalente
x = HJ x + C.
Vamos a utilizar lo anterior para calcular la citada soluci´on del sistema con una tolerancia
menor a la cent´esima, paraello s´olo tenemos que llevar al ordenador el proceso iterativo
definido en (F.2) y eso lo conseguimos con el listado:
xn1=0; xn2=0; xn3=0;
ii=0; e=1; tol=0.01;
while e>tol
ii=ii+1; x1=xn1; x2=xn2; x3=xn3;
xn1=(-7-x2+x3)/5; xn2=(1+x1)/3; xn3=(11-x1-x2)/6;
e=max([abs(x1-xn1) abs(x2-xn2) abs(x3-xn3)]);
fprintf(’x1=%f x2=%f x3=%f e=%f i=%i \n’, xn1, xn2, xn3, e ,ii);
end

´
F.2. METODO
DE JACOBIAMORTIGUADO

47

Observamos que necesitamos 6 iteraciones para obtener la soluci´on xˆ = (−1, 0, 2) con una
tolerancia menor a la cent´esima.
En la pr´actica anterior hemos descrito el proceso iterativo de Jacobi, el cual convierte un sistema
regular Ax = B a la forma x = HJ x+CJ , donde HJ es la matriz de Jacobi asociada a dicho sistema
y CJ el vector dado por la f´ormula:
HJ = −D(I + S);

CJ = D−1B

La convergencia de la sucesi´on de Jacobi {x(k) } definida a partir de un vector inicial x(0) depende
de las propiedades de la matriz HJ . En cualquier caso y justificados por la pr´actica anterior se
verifica:
Teorema F.1 Si la matriz de Jacobi HJ = (hij ) asociada al sistema regular Ax = B verifica una
de las siguientes condiciones:
1. HJ

ind
2

< 1.

2. HJ

ind
∞

= m´axi

n
j=1

|hij | <1.

3. HJt

ind
∞

= m´axj {

n
i=1

|hij |} < 1.

entonces la sucesi´
on de Jacobi {x(k) } definida con un vector inicial cualquiera x(0) converge a la
u
´nica soluci´
on x
ˆ del sistema Ax = B.
Pr´
actica b El archivo Mt\f_mj.m permite calcular, por el m´etodo de Jacobi, la soluci´on de un
sistema lineal Ax = B con una determinada tolerancia y a partir de una aproximaci´
on inicial
(0)
x...