Métodos iterativos para
sistemas de ecuaciones
lineales
Métodos iterativos para
sistemas de ecuaciones
lineales
Introducción
Ecuación del Calor
Método de Jacobi
Método de Gauss-Seidel
Método de Sobrerrelajación
Problema del Condensador
Métodos directos frente a
métodos iterativos
DIRECTOS
ITERATIVOS
Ax =b
x = Cx + d
x = A\ b
x(k+1) = Cx(k) + d
Tamaño moderado
Tamaño grande
Modifican la
estructura
Conservan los ceros
Error de redondeo
Error de truncamiento
Convergencia y número de
operaciones
Coste (para matrices densas)
Directos: n3
Iterativos: k.n2
Convergencia
Criterio de parada:
x
(k +1 )
Ax
x
(k )
(k )
b
p
p
 to l; p  1 ,2 , .. . ,in f
 to l; p  1 ,2 , . . . ,in f
Ecuación del Calor
Sistema de ec. lin.
T1  (T 0  T 2 ) / 2
T 2  (T1  T 3 ) / 2
T 3  (T 2  T 4 ) / 2

Tn  (Tn-1  Tn +1 ) / 2
T0
T1
T2
Matriz asociada
 2

- 1





. . .
-1
2
-1
-1
2



-1
Tn





- 1

2
Tn+1
Matriz de la Ecuación del Calor
con MATLAB
function A = mcalor1(n)
v = ones(1,n-1);
A = 2*eye(n) - diag(v,1) diag(v,-1);
El método de Jacobi
Sistema de ecuaciones lineales
a 1 1x 1  a 1 2 x 2  a 1 3 x 3   a 1 n x n  b 1 

a 2 1x 1  a 2 2 x 2  a 2 3 x 3   a 2 n x n  b 2 

a 3 1x 1  a 3 2 x 2  a 3 3 x 3   a 3 n x n  b 3 








a n 1x n  a n 2 x 2  a n 3 x 3   a n n x n  b n 
Ecuación de punto fijo
x 1  (b 1  a 1 2 x 2  a 1 3 x 3 
x 1  (b 2  a 2 1 x 1  a 2 3 x 3 
x 2  (b 3  a 3 1 x 1  a 3 2 x 2 




x n  (b n  a n 1 x 1  a n 2 x 2 


 a 2n x n ) / a 22 

 a 3n x n ) / a 33 



 a n ,n  1 x n  1 ) / a n n 
 a 1n x n ) / a 11
Iteración de Jacobi
(k)
2
 a 13 x
(k)
 a 23 x 3 
(k)
1
 a 32 x
x
(k +1)
1
 (b 1  a 12 x
x
(k +1)
2
 (b 2  a 21x 1
x
(k +1)
3
 (b 3  a 31x

x
(k +1)
n

 (b n  a n1x
(k)
3
(k)
(k)
2

(k)
1

 a n2 x


(k)
2

 a 1n x ) / a 11 

(k)
 a 2n x n ) / a 22 

(k)
 a 3n x n ) / a 33 




(k)
 a n,n  1x n  1 ) / a nn 
(k)
n
Expresión matricial
Resolución con MATLAB
A LDU
x
(k  1)
D
1
(b  (L  U )x
(k)
)
U = triu(A,1); L = tril(A,-1);
d = diag(A);
x = (b-(L+U)*x)./d
Condición suficiente de
convergencia
Matriz estrictamente diagonalmente
dominante: para i=1,2,...,n
| a ii | | a i1 |   | a i,i  1 | | a i,i  1 |   | a in |
Si A es estrictamente diagonalmente
dominante, los iterados de Jacobi
convergen a la solución del sistema
partiendo de cualquier estimación inicial.
Iteración de Gauss-Seidel
 a 13 x
(k)
3

(k +1)
1
 a 23 x
(k)
3

(k +1)
 a 32 x 2
 (b 1  a 12 x
x
(k +1)
1
x
(k +1)
2
 (b 2  a 21x
x
(k +1)
3
 (b 3  a 31x 1

x
(k +1)
n
(k)
2

 (b n  a n1x
(k +1)

(k +1)
1
 a n2 x


(k +1)
2

 a 1n x ) / a 11 

(k)
 a 2n x n ) / a 22 

(k)
 a 3n x n ) / a 33 




(k +1)
 a n,n  1x n  1 ) / a nn 
(k)
n
Expresión matricial
Resolución con MATLAB
A LDU
(L  D )x
x
(k  1 )
(k  1 )
 b  Ux
1
(k )
 (L  D ) (b  U x
(k )
)
d = diag(A); D = diag(d);
U = triu(A,1); L = tril(A,-1);
x = (L + D)\(b - U*x)
Método de sobrerrelajación
x ik+1
xik
G a u s s  S e id e l:
zi
xik+1
(k +1 )
(k )

xi
 xi  zi
S o b re rre la ja c io n :
x
(k +1 )
i
 x
(k )
i
 w zi ;
0< w <2
(k +1 )
(k )

zi  xi
 xi
x
(k +1 )
i
 (1  w )x
(k )
i
(k +1 )

 w xi
Paso de sobrerrelajación
 a 13 x 3
  a 1n x n ) / a 11
(k +1)
 a 23 x 3
 
(k +1)
 a 32 x 2
 

 
(k)
 (1   )x 1   (b 1  a 12 x 2
x
(k +1)
2
x
(k +1)
3
 (1   )x
(k)
2
  (b 2  a 21x 1
 (1   )x
(k)
3
  (b 3  a 31x 1


(k +1)
xn
(k +1)
 (1   )x n   (b n  a n1x 1
(k)


(k)

a 2n x n ) / a 22


(k)
a 3n x n ) / a 33




(k +1)
a n,n  1x n  1 ) / a nn 
(k)
(k +1)
x1
(k)
(k)
(k +1)
 a n2 x 2
(k +1)
(k)
 
Expresión matricial
Resolución con MATLAB
A  L D U
(  L  D )x
(  L  D )x
(k +1)
(k +1)
 (1   )D x
(k)
  (b  U x
  b  ((1   )D   U )x
(k)
D = diag(diag(A));
c = *b; C = (1-)*D - *U
x = (L + D)\(c + C*x)
(k)
)
Condición suficiente de
convergencia
Matriz simétrica definida positiva:
AT = A, xTAx > 0
Si A es simétrica definida positiva y 0<w<2,
los iterados de SR convergen a la única
solución del sistema, partiendo de cualquier
estimación inicial.
Ecuación del Calor en un
rectángulo
N
W
C
S
VC = (VN + VS + VE + VW)/4
E
Generación de la matriz
con MATLAB
function A = mcalor2(m,n)
p = m*n;
v = ones(1,p-1);
for k=n:n:p-1, v(k) = 0; end
w = ones(1,p-n);
A = 4*eye(p) ...
- diag(v,1) - diag(v,-1)
...
- diag(w,n) - diag(w,-n);
Resumen
Los métodos iterativos se aplican a
matrices grandes y dispersas.
El coste por iteración es O(n2) o menor si
se aprovecha la dispersidad
Se espera que converjan en menos de n
pasos.
La matriz ha de cumplir ciertas
condiciones para que el método converja.
Descargar

Métodos iterativos para sistemas de ecuaciones lineales