1
Metodos de Solución Iterativos
Empezar con una aproximación inicial para el vector solución (x0)
Actualizar en cada iteración el vector x usando el sistema Ax=b
Cada iteración involucra el producto matriz-vector.
Si A es esparcida este producto es realizado eficientemente.
2
Procedimiento de solución Iterativa
Escribir el sistema Ax=b en una forma equivalente x=Tx+c
Empezando con x0, genere una secuencia de aproximaciones {xk} iterativamente porxk+1=Txk+c
Representación de T y c dependen del tipo de método usado.
Pero para cada método T y c son obtenidas a partir de A y b.
3
Convergencia Cuando k, la secuencia {xk} converge a
un vector solución bajo algunas condiciones en la Matriz T.
Esto impone condiciones diferentes en la matriz A para diferentes métodos.
Para la misma matriz A, un método puede converger mientras que otro puede divergir.
Por lo tanto para cada método la relación entre A y T deben ser encontradas para decidir la convergencia.
4
Diferentes metodos Iterativos
Iteración de Jacobi Iteración de Gauss-Seidel Successive Over Relaxation (S.O.R)
SOR es un método usado para acelerar la convergencia.
La iteración de Gauss-Seidel es un caso especial del método SOR.
5
Iteración de Jacobi
nnnnnn
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
2211
22222121
11212111
0
02
01
0
nx
x
x
x
)(1 0
102121
11
11 nn xaxab
ax
1
1 1
1 1 i
j
n
ij
kjij
kjiji
ii
ki xaxab
ax
)(1 0
11022
011
1 nnnnnn
nnn xaxaxab
ax
)(1 0
20323
01212
22
12 nn xaxaxab
ax
6
Método de Jacobi. Forma Matricial
Descomponiendo A = D - L - U.
-L=tril(A)-D
-U
-L
D
D=diag(diag(A))
=
-U=triu(A)-D
7
xk+1=Txk+c - iteración por el método de Jacobi
Se puede escribir como A=D-L-U (No es una factorización)
000
00
0
0
00
000
00
00
00
23
1312
3231
21
33
22
11
333231
232221
131211
a
aa
aa
a
a
a
a
aaa
aaa
aaa
n
ij
kjij
i
j
kjiji
ii
ki xaxab
ax
1
1
1
1 1 xk+1=D-1(L+U)xk+D-
1b
T=D-1(L+U)
c=D-1b
Ax=b (D-L-U)x=b Dxk+1 = (L+U)xk+b
kk UxLxDxk+1
8
iteración Gauss-Seidel (GS)
nnnnnn
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
2211
22222121
11212111
0
02
01
0
nx
x
x
x
1
1 1
11 1 i
j
n
ij
kjij
kjiji
ii
ki xaxab
ax)(
1 01
02121
11
11 nn xaxab
ax
)(1 1
11122
111
1 nnnnnn
nnn xaxaxab
ax
)(1 0
20323
11212
22
12 nn xaxaxab
ax
Use lo último al actualizar
9
x(k+1)=Tx(k)+x iteración de Gauss-Seidel
1
1 1
11 1 i
j
n
ij
kjij
kjiji
ii
ki xaxab
ax
xk+1=(D-L)-1Uxk+(D-L)-1b
Tgs=(D-L)-1U
cgs=(D-L)-1b
Ax=b (D-L-U)x=b
(D-L)xk+1 =Uxk+b
k1k UxLx Dxk+1
10
Comparación
İteración de Gauss-Seidel converge más rápidamente que la iteración de Jacobi desde que este usa la última actualización.
Pero existen algunos casos que la iteración de Jacobi converge pero Gauss-Seidel no.
El método de sobre relajación sucesiva es usada para acelerar la convergencia del método de Gauss-Seidel.
11
Metodo Sobre Relajación Sucesiva (SOR)
Puede ser escrita como sigue
ki
ki
ki
i
j
n
ij
kjij
kjiji
ii
ki
ki
xx
xaxaba
xx
1
1
1
11 1
término Corrector
0ix
1ix
2ix
3ix
0i
1i
2i
0i
1i
2i
1Multiplicando por
Converge más rápido
12
SOR
11
1
1 1
11
1
1
11
1
~)1(
1)1(
1
ki
ki
ki
i
j
n
ij
kjij
kjiji
ii
ki
ki
i
j
n
ij
kjij
kjiji
ii
ki
ki
ki
ki
ki
xxx
xaxaba
xx
xaxaba
xx
xx
Donde el ultimo termino es la estimación de Gauss-Seidel1<<2 Sobre-relajación (convergencia rápida)0<<1 Sub-relajación (convergencia más lenta)Existe un valor óptimo para Encontrarlo por prueba y error
13
x(k+1)=Tx(k)+c iteración para SOR
1
1 1
11 1)1(
i
j
n
ij
kjij
kjiji
ii
ki
ki xaxab
axx
Dxk+1=(1-)Dxk+b+Lxk+1+Uxk
(D- L)xk+1=[(1-)D+U]xk+b
T=(D- L)-1[(1-)D+U]
c= (D- L)-1b
14
Convergencia de los métodos iterativos
x̂Define el vector solución como
Define el vector error como ke
xex kk ˆ
kkk TecxTcxeTxe ˆ)ˆ(ˆ1
0)1(211 eTTTTeTTeTee kkkkk
Substituye esto en cTxx kk 1
15
Convergencia de los Métodos Iterativos
0)1(0)1(1 eTeTe kkk
Condición de Convergencia
0Lims0Lim )1(1
k
k
k
kTie
iteración potencia
El método iterativo convergería para cualquier vector inicial arbitrario si la siguiente condición es satisfecha
16
Norma de un vector
La norma de un vector debe satisfacer estas condiciones:
yxyx
αaraxαx
xix
xarax
escalar un P
nulo un vector es si soloy s0
nulo novector cualquier P0
Las normas Vectoriales pueden ser definidas de diferentes formas en tanto que la definición de norma sea satisfecha.
17
Normas de vectores Comunmente usadas
nxxxx 211
norma Suma o norma ℓ1
norma Euclideana ó norma ℓ2
222
212 nxxxx
norma Máxima o norma ℓ
ii xx max
18
Norma de una matrizLa norma de una matriz debe satisfacer estas condiciones:
BABA
αaraAαA
AsisoloyiA
A
escalar p
nula matriz una es s0
0
Importante identidad
un vector es xxAAx
19
Normas de matrices mas usadas
Norma Máxima suma_columna o norma ℓ1
Norma Espectral o norma ℓ2
m
iij
njaA
111max
AAA T de propio valor maximo2
n
jij
miaA
11max
Norma Maxima suma_fila o norma ℓ
20
Ejemplo
Calcule las normas ℓ1 y ℓ de la matriz
186
427
593 17
13
15
A
16 19 10
1A
21
Condición de Convergencia
0lims0lim )1(1
k
k
k
kTie
Expresar T en terminos de matriz modal P y : Matriz Diagonal con valores propios de T en la diagonal
1)1()1(
111)1(
1
PPT
PPPPPPT
PPT
kk
k
1
12
11
1
kn
k
k
k
,...,n,i
PPT
iki
k
k
k
k
k
k
k
21for 10lim
0lim0lim0lim
1
)1(1)1()1(
22
Condición Suficiente para convergencia
Si la magnitud de todos los valores propios de la Matriz de iteración T es menor que 1 entonces laiteración es convergente
TTTxTxxTTx
xTx
xTx
)(
Los valores propios son mas fácil de calcular que la norma de una matriz
1)( T condición suficiente para convergencia
23
Convergencia de la iteración de Jacobi
T=D-1(L+U)
0
0
0
11
11
1
22
2
22
23
22
21
11
1
11
12
nn
nn
nn
n
nn
nn
n
n
aa
aa
aa
aa
aa
aa
aa
aa
T
24
Convergencia de la iteración de Jacobi
n
jij
ijii
n
jij ii
ij
aa
a
aT
1
1
n1,2,...,i Para 11
Evaluar la norma infinita (suma máxima fila) de T
Matriz Diagonal estrictamente Dominante
Si A es una matriz con diagonal estrictamente dominante, entonces la iteración de Jacobi converge para cualquier valor inicial
25
Criterios de Parada Ax=b
En cualquier iteración k, el término residual es
rk=b-Axk
Verificar la norma del término residual
||b-Axk||
Si esto es menor que la cota del valor de parada
26
Ejemplo 1 (Iteración de Jacobi)
15
21
7
512
184
114
3
2
1
x
x
x
0
0
00x
5
215
8
421
4
7
02
011
3
03
011
2
03
021
1
xxx
xxx
xxx
0.35
15
625.28
21
75.14
7
7395.262
0 Axb
0452.102
1 Axb
Matriz Diagonal estrictamente dominante
27
Ejemplo 1 continuación...
5
215
8
421
4
7
12
112
3
13
112
2
13
122
1
xxx
xxx
xxx
225.45
625.275.1215
875.38
375.1421
65625.14
3625.27
7413.6
2
2 Axb
8875.25
875.365625.1215
98125.38
225.465625.1421
6625.14
225.4875.37
33
32
31
x
x
x
9534.12
3 Axb
Matriz es diagonal estrictamente dominante, las iteraciones de Jacobi son convergentes.
28
Ejemplo 2
7
21
15
114
184
512
3
2
1
x
x
x
0
0
00x 7395.26
2
0 Axb
02
01
13
03
011
2
03
021
1
47
8
421
2
515
xxx
xxx
xxx
0.7
625.28
21
5.72
15
La matriz no es diagonal estrictamente dominante
8546.542
1 Axb
29
Ejemplo 2 continuación...
625.39625.25.747
25.08
75.7421
3125.112
75625.215
13
12
11
x
x
x
3761.2082
2 Axb
El término del residual aumenta en cada
iteración, de tal forma que las iteraciones
divergen.
Note que la matriz no es diagonalmente
estrictamente dominante
Cuando la matriz no tiene diagonal
estrictamente dominante, puede converger
como no.
30
Convergencia de la iteración de Gauss-Seidel
Iteración GS converge para cualquier vector inicial si A es una matriz diagonal estrictamente dominante
Iteración GS converge para cualquier vector inicial si A es una matriz simétrica y definida positiva – La matriz A es definida positiva si
xTAx>0 para cualquier vector x no nulo.
31
Ejemplo1 (Iteración de Gauss-Seidel)
15
21
7
512
184
114
3
2
1
x
x
x
0
0
00x
5
215
8
421
4
7
12
111
3
03
111
2
03
021
1
xxx
xxx
xxx
0.35
5.375.1215
5.38
75.1421
75.14
7
7395.262
0 Axb
0414.32
1 Axb
Matriz Diagonal estrictamente dominante
0452.102
1 Axb
İteración deJacobi
32
Ejemplo 1 continuación...
5
215
8
421
4
7
22
212
3
13
212
2
13
122
1
xxx
xxx
xxx
9625.25
9375.3875.1215
9375.38
3875.1421
875.14
35.37
4765.02
2 Axb
7413.62
2 Axb
Iteración de Jacobi
Cuando ambos métodos de Jacobi y Gauss-Seidel convergen, Gauss-Seidel converge más rápido.
33
Convergencia del método SOR
Si 0<<2, método SOR converge para cualquier valor inicial si A es una matriz simétrica y definida positiva.
Si >2, método SOR diverge
Si 0<<1, SOR método converge pera la velocidad de convergencia es mas lenta que el método de Gauss-Seidel.
34
Conteo de operaciones El # de operaciones para la Eliminación
gaussiana o la descomposición LU es de 0 (n3), orden de n3
Para los métodos iterativos, el número de multiplicaciones escalares es 0 (n2) en cada iteración.
Si el número total de las iteraciones requeridas para la convergencia es mucho menos que n, entonces los métodos iterativos son más eficiente que métodos directos.
Los Métodos iterativos también se satisfacen bien para las matrices esparcidas.
35
Formas Matriciales. Resumen
La solución del sistema La solución del sistema A x = bA x = b se obtiene se obtiene mediante la siguiente expresión recursiva:mediante la siguiente expresión recursiva:
x x ( k )( k ) = Tx = Tx ( k-1 ) ( k-1 ) + c + c
A= D - L - UA= D - L - U
Método
Jacobi
Gauss-Seidel
SOR
T c
D-1 (L+U) D-1 b
( D -L)-1 U ( D -L)-1 b
(D-w L)-1 [(1-w) D + w U ] w(D-w L)-1 b
36
Problema 1
Resolver el siguiente sistema por el método SOR, considere ω=1.25.
000
24
64
24
03
02
01
32
321
21
xxx
xx
xxx
xx
11 ~)1( ki
ki
ki xxx
Aplicamos el metodo de SOR:
37
Problema 1
52419726562.1025.11017578125.125.1
1~
017578125.14
0703125.22
4
2~
0703125.2
025.1165625.125.11~
65625.14
0625.06
4
6~
625.0025.115.025.11~
5.04
02
4
2~
03
13
13
121
3
02
12
12
03
111
2
01
11
11
021
1
xx
xxx
xx
xxxxx
xxx
xxxxx
xx
38
Problema 1
k x1 x2 x3
0 0 0 0
1 0.625 2.0703125 1.2719727
2 1.1157227 2.1035767 0.9643745
3 1.003437 1.9640469 0.997671
4 0.9879054 2.0044809 1.0019825
5 1.0044239 2.0008818 0.9997799
39
Problema 2Sea el sistema A x = b : Para k=-1, es la matriz A definida positiva? Para que valores de k el sistema converge, al usar el método de Gauss-Seidel? Hacer 03 iteraciones de Gauss-Seidel para k=-3
9
6
31
2
2
1
x
xk
40
Problema 2A es definida positiva si:
nulo. no x todopara 02)(231
12
nulo no columna vector todopara ,0
22
221
21
2
121
xxxxx
xxx
xAxxT
Observese que también satisface el criterio de Silvester
41
Problema 2
6k6- :que siempre cumple se Esto
1)(T :cuando iaconvergenc Existe
6/)( 6/ 0
))(6
(
6/0
2/0
00
0
3/16/1
02/1
3/16/1
02/1)(
31
02)(
)(
G
max21
1
1
kTk
kITDet
k
kkT
LD
LD
ULDT
G
G
G
G
42
Problema 2
3/3
5.13
-3)(k Seidel-Gauss Para
)1(1
)1(2
)(2
)1(1
nn
nn
xx
xx
n x1 x2
0 0 0
1 3 4
2 9 6
3 12 7
4 13.5 7.5
5 14.25 7.75
6 14.625 7.875
7 14.8125 7.9375