sistemas de ecuaciones algebraicas lineales metodos iterativos
TRANSCRIPT
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
1/129
CATEDRA 0
8
METODOSNUMERICOS
Ingeniera Civil
ING. CRISTIAN CASTRO P.
Facultad de Ingeniera de Minas, Geologa y CivilDepartamento acadmico de ingeniera de minas y civil
1
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
2/129
apitulo VI
Sistema de Ecuaciones
Algebraicas Lineales
Mtodos Iterativos
ING. CRISTIAN CASTRO P.2
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
3/129
3
IntroduccinIntroduccin
MTODO ESTABILIDAD PRECISINRANGO DE
APLICACINCOMPLEJIDAD DE
LA PROGRAMACIN COMENTARIOS
GRFICO --- Pobre Limitado ---
Puede tomar mstiempo que el mtodo
numrico
Regla de Cramer ---Afectado por errores
de redondeo Limitado ---
Escesiva complejidadde clculo para msde tres ecuaciones
Eliminacin de Gauss(con pivoteo paracial) ---
Afectado por erroresde redondeo General Moderada
Descomposicin LU ---Afectado por errores
de redondeo General Moderada
Mtodo de eliminacin
preferido; permite elclculo de la matriz
inversa
Gauss_Seidel
Puede no converger sino es diagonalmente
dominante EXCELENTE
Apropiado solo parasistemas
diagonalmentedominantes FCIL
TABLA No. 1: Comparacin de las caractersticas de diversos mtodos alternativos para encontrar soluciones de ecuaciones algebraicaslineales simultneas
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
4/129
4
Comparacin de Mtodos Directos e Iterativos apartir de la cantidad de operaciones matemticas
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
5/129
5
MTODOS ITERATIVOS DE SOLUCIN
Debemos resaltar que lo mtodos vistos hasta laactualidad para solucionar sistemas de ecuaciones
algebraicas lineales son muy caros
computacionalmente.
Estos mtodos exigen una memoria de mquinaproporcional al cuadrado del orden de la matriz decoeficiente A.
De igual manera se producen grandes errores deredondeo como consecuencia del nmero de
operaciones.
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
6/129
6
MTODOS ITERATIVOS DE SOLUCIN
Debemos mencionar que en estos mtodos necesitantener una aproximacin inicial de la solucin y no
esperamos tener una solucin exacta aun cuando
todas las operaciones se realicen utilizando una
aritmtica exacta.
Pero podemos decir que en muchos casos son mas
efectivos que los mtodos directos por requerir mucho
menos esfuerzo computacional y sus errores se
reducen, esto es cierta cuando la matriz es dispersaes decir cuando la matriz tienen un alto porcentaje de
elementos nulos
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
7/129
7
AplicacionesAplicaciones Rara vez para resolver sistemas lineales de dimensin
pequea.
Tiempo requerido mayor para lograr la precisin
Los mtodos directos son suficientemente exactos.
Utilidad para la resolucin de los sistemas de ecuacionesdiferenciales en aplicaciones de:
Todas las ramas de ingeniera
Ciencias sociales
Economa
Estos mtodos son tiles en la prediccin del clima,
anlisis matricial de estructuras, donde el volumen devariables amerita el uso de extensas matrices.
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
8/129
Estos mtodos en mencin son ms efectivos que losvistos anteriormente y han permitido solucionar
sistemas de hasta 1000 ecuaciones y variables a unms, sistemas que se presentan en la solucin numrica
de ecuaciones diferenciales parciales (EDP).
Supongamos que tenemos el sistema
Ax= b (1)
Luego podemos escribir como:
Ax b = 0 (2)
Que es una ecuacin vectorial que se puede escribir as:
f(x) = 0 (3)
8
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
9/129
El propsito es buscar una matriz B y su vector C de tal
forma que la ecuacin vectorial es la siguiente:
x= B x+ C (4)
Sea un arreglo de la ecuacin (1) ie que la solucin de
una ecuacin sea tambin solucin de la otra ecuacin,luego se propone lo siguiente:
Primero: Proponer un vector inicial x(0) como la primera
aproximacin al vector solucin x
Segundo: calcular la sucesin de vectores que son
soluciones aproximadas
9
MTODOS ITERATIVOS DE SOLUCIN
solucinvectorxxxxx ,.....,,,, )4()3()2()1(
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
10/129
Usando:
Donde:
10
MTODOS ITERATIVOS DE SOLUCIN
,.....2,1,0,)()1( RCBxx RR
TRnRRR xxxx ,......,, 21)(
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
11/129
Observacin:
1. Para que la sucesin de soluciones converja a x
vector solucin es necesario que seaproxime al vector decir
sean menores que un valor pequeo fijado
previamente y que se mantengan menores para
todos los vectores siguientes de la iteracin.
Es decir:
2. La forma como llegar a la ecuacin x = B x + C se
define al algoritmo y su convergencia.
11
MTODOS ITERATIVOS DE SOLUCIN
njxm
j 1,njx j 1, njxx j
m
j 1,
njxx jm
jm
1,lim
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
12/129
. Sea dada el sistema
Con a11 0, a22 0, a33 0
De tenemos que:
(5)
12
MTODOS ITERATIVOS DE SOLUCIN
3
2
1
3
2
1
3
2
1
333231
232221
131211
b
b
b
x
x
x
aaa
aaa
aaa
1
3
11
132
11
12
11
11 xa
ax
a
a
a
bx
2
33
32
1
33
31
33
3
3
3
22
23
1
22
21
22
2
2
xa
ax
a
a
a
bx
xa
ax
a
a
a
bx
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
13/129
(6)
13
MTODOS ITERATIVOS DE SOLUCIN
CBxx
a
ba
b
a
b
x
x
x
a
a
a
aa
a
a
a
a
a
a
a
x
x
x
33
3
22
2
11
1
3
2
1
33
32
33
31
22
23
22
21
11
13
11
12
3
2
1
0
0
0
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
14/129
Una vez que es determinada la ecuacin (6) se
propone un vector inicial x(0) que puede ser x(0) = 0
cero o algn otro vector que sea aproximado alvector solucin x.
Para determinar la sucesin buscada de solucin
iterativo tenemos los siguientes mtodos numricos:
Mtodo de Jacobi (Desplazamiento simultaneo)
Mtodo de Gauss Seidel (Desplazamiento sucesivo)
Mtodo de Sobrerelajacin (Succesive-Over-Relaxations)
14
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
15/129
15
Convergencia Este criterio tambin se aplica a las ecuaciones lineales que se
resuelven con el mtodo de Gauss-Seidel. Por tanto, al aplicar este
criterio sobre las ecuaciones de Gauss-Seidel y evaluando conrespecto a cada una de las incgnitas, obtenemos la expresin
siguiente:
En otras palabras, el valor absoluto de las pendientes en laecuacin, deben ser menor que la unidad para asegurar la
convergencia.
Esto es, el elemento diagonal debe ser mayor que el elemento fuerade la diagonal para cada regln de ecuaciones. La generalizacin del
criterio anterior para un sistema de n ecuaciones es:
122
21 a
a1
11
12 a
a
2122 aa 1211 aa
n
jiii aa1
,
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
16/129
16
Convergencia
Resultado de las iteracionesutilizando las ecuaciones sinordenar
Divergencia Seidel
-40
-30
-20
-10
0
10
20
30
40
50
60
70
-20 -10 0 10 20 30 40 50 60 70
X1
X2
Divergencia Jacobi
-100
-80
-60
-40
-20
0
20
40
60
80
-60 -40 -20 0 20 40 60 80
X1
X2
X1 X2
0.00 0.00
26.00 0.00
26.00 20.78
1.44 20.78
1.44 -9.23
36.91 -9.23
36.91 34.12
-14.32 34.12
-14.32 -28.50
59.68 -28.50
59.68 61.95
-47.21 61.95
-47.21 -68.70107.19 -68.70
107.19 120.01
-115.83 120.01
-115.83 -152.57
Divergencia Seidel
X1 X2
0.00 0.0026.00 -11.00
39.00 20.78
1.44 36.67
-17.33 -9.23
36.91 -32.19
64.04 34.12
-14.32 67.27
-53.50 -28.5059.68 -76.39
Divergencia Jacobi
99911:
2861311:
21
21
xxv
xxu
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
17/129
17
Convergencia Resultado de las iteraciones
utilizando previamente el criterio
de diagonal dominante
Convergencia Seidel
0
2
4
6
8
10
12
14
16
0 5 10 15 20 25X1
X2
Convergencia Jacobi
-5
0
5
10
15
20
25
0 5 10 15 20 25 30
X1
X2
X1 X2
0.00 0.00
9.00 0.00
9.00 14.38
20.77 14.38
20.77 4.43
12.62 4.43
12.62 11.32
18.26 11.32
18.26 6.5514.36 6.55
14.36 9.85
17.06 9.85
17.06 7.56
15.19 7.56
15.19 9.15
16.48 9.15
16.48 8.0515.59 8.05
15.59 8.81
Convergencia Seidel
X1 X20.00 0.009.00 22.0027.00 14.3820.77 -0.858.31 4.4312.62 14.9721.25 11.3218.26 4.0212.29 6.5514.36 11.6018.49 9.8517.06 6.3514.20 7.5615.19 9.9917.17 9.15
16.48 7.4715.11 8.05
Convergencia Jacobi
2861311:
99911:
21
21
xxu
xxv
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
18/129
18
Mtodos
Iterativos
Mtodos
IterativosJacobi, Gauss Seidel, Relajacin
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
19/129
19
Mtodo de Jacobi
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
20/129
MTODO DE DESPLAZAMIENTO SIMULTNEO DEJACOBI
Si es el vector de aproximacin a la
solucin x despus de R iteraciones, entonces,
tendremos la siguiente aproximacin
20
MTODOS ITERATIVOS DE SOLUCIN
R
R
R
R
x
xx
x
3
2
1
)(
)(1
)(1
)(1
2321313
33
3231212
22
3132121
11
1
3
1
2
1
11
RR
RR
RR
R
R
R
R
xaxab
a
xaxaba
xaxaba
x
x
x
x
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
21/129
Fenmeno que se puede generalizar para necuaciones
21
MTODOS ITERATIVOS DE SOLUCIN
nixabax
n
ijj
R
jjii
ii
R
i ,.....,2,1,
1
1
1
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
22/129
22
Mtodo de Jacobi Este mtodo se puede ilustrar usando las siguientes ecuaciones:
(1)
1313212111 bxaxaxa
2323222121 bxaxaxa
3333232131 bxaxaxa
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
23/129
23
Mtodo de Jacobi
El mtodo comienza resolviendo la ec. 1 parax1
, x2
y x3
e
introduciendo el ndice k que se utilizara para indicar el nmero de
iteraciones, se obtiene:
(2)
11
)(
313
)(
2121)1(
1
a
xaxabx
kkk
22
)(
323
)(
1212)1(
2a
xaxabx
kkk
33
)(
232
)(
1313)1(
3a
xaxabx
kkk
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
24/129
24
Mtodo de Jacobi Adems se requiere de un vector inicial
xi= (x
1
(k), x2
(k), x3
(k))
el cual representa la primera aproximacin de la solucin del
sistema, con lo que se produce x k+1.
Este vector si no se conoce se puede asumir como:
x0= (0 (0), 0 (0), 0 (0))
Con estos valores y las frmulas de las ecuaciones (2) se vancalculando los nuevos valores de xi
El proceso se continua hasta que | xi+1 xi| ea.
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
25/129
25
Mtodo de JacobiEjemplo 1:
Resolver el siguiente sistema de tres ecuaciones por el Mtodo de
Jacobi, para un a= 5% :
17 X1 2 X2 3 X3= 500
-5 X1 + 21 X2 2 X3= 200
-5 X1 5 X2+ 22 X3= 30
Las siguientes frmulas las utilizamos para encontrar
X1, X2y X3en cada una de las iteraciones
11
31321211
a
xaxabx
22
3231212
2a
xaxabx
33
23213133
axaxabx
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
26/129
26
Para la primera iteracin el valor de X1, X2y X3a sustituir en cadauna se asumir como cero.
Aplicando (2) se obtiene:
41176,29
170302500
1
1
11
31321211
x
x
a
xaxabx
41176,29
170302500
1
1
11
31321211
x
x
a
xaxabx
52381,9
210205200
2
2
22
32312122
x
x
a
xaxabx
52381,9
210205200
2
2
22
32312122
x
x
a
xaxabx
36364,1
22
050530
3
3
33
23213133
x
x
axaxabx
36364,1
22
050530
3
3
33
23213133
x
x
axaxabx
Mtodo de Jacobi
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
27/129
27
Mtodo de Jacobi Para la segunda iteracin el valor de X1, X2y X3 sern los calculados
anteriormente.
Aplicando (2) se obtiene:
77285,30
17
36364,1352381,92500
1
1
11
31321211
x
x
a
xaxabx
77285,30
17
36364,1352381,92500
1
1
11
31321211
x
x
a
xaxabx
65648,16
2136364,1241176,295200
2
2
22
32312122
x
x
a
xaxabx
65648,16
2136364,1241176,295200
2
2
22
32312122
x
x
a
xaxabx
21263,10
22
52381,9541176,29530
3
3
33
2321313
3
x
x
a
xaxabx
21263,10
22
52381,9541176,29530
3
3
33
2321313
3
x
x
a
xaxabx
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
28/129
28
Mtodo de Jacobi Una vez obtenidos estos resultados se debe calcular el error
aproximado porcentual para cada uno de los resultados, para ello
utilizamos la siguiente frmula:
Dado que no se cumple con el a se debe continuar iterando.
%100
nuevo
r
anterior
r
nuevo
ra
x
xx
%5%423,4
%10077285,30
41176,2977285,30
1
1
ax
ax
%5%423,4
%10077285,30
41176,2977285,30
1
1
ax
ax
%5%822,42
%10065648,16
52381,965648,16
2
2
ax
ax
%5%822,42
%10065648,16
52381,965648,16
2
2
ax
ax
%5%648,86
%10021263,10
36364,121263,10
3
3
ax
ax
%5%648,86
%10021263,10
36364,121263,10
3
3
ax
ax
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
29/129
29
Mtodo de Jacobi Siguiendo el mismo procedimiento, se obtiene el siguiente cuadro de
resultados:
Se resaltan los datos donde los errores obtenidos son menores que 5%, se
logra un error aproximado porcentual menor en las tres incgnitas hasta
la quinta iteracin.
Iteracin x
x
x
3
a
x
a
x
a
x
3
0 0,00000 0,00000 0,00000
1 29,41176 9,52381 1,36364
2 30,77285 16,65648 10,21263 4,423% 42,822% 86,648%
3 33,17358 17,82331 12,14303 7,237% 6,547% 15,897%
4 33,65151 18,57876 12,95384 1,420% 4,066% 6,259%
5 33,88347 18,76977 13,23415 0,685% 1,018% 2,118%
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
30/129
30
Mtodo de Jacobi Si sustituimos estos valores en las ecuaciones originales para verificar los
resultados se obtiene:
17 *(33,88347) 2 *(18,76977) 3 *(13,23415) = 498,77703
-5 *(33,88347) + 21 *(18,76977) 2 *(13,23415) = 198,27957
-5 *(33,88347) 5 *(18,76977) + 22 *(13,23415) = 27,88513
Al calcular los porcentajes de error de estos resultados se obtiene:
0,88%%10030
27,88513-30Error
0,10%%100200
198,27957-200Error
0,03%%100500
498,77703-500Error
EC3
EC2
EC1
0,88%%10030
27,88513-30Error
0,10%%100200
198,27957-200Error
0,03%%100500
498,77703-500Error
EC3
EC2
EC1
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
31/129
Ejemplo:
Solucin:
31
MTODOS ITERATIVOS DE SOLUCIN
1400
140104
1004
4321
4321
4321
4321
xxxx
xxxxxxxx
xxxx
CxBx
xx
x
x
xx
x
x
xx
xxx
xxx
xx
4/14/1
4/1
4/1
04/1004/104/10
04/104/1
004/10
44
1444
1
444
14
1
4
4
3
2
1
4
3
2
1
3
4
423
31
2
2
1
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
32/129
Valor Inicial
Cuando no tenemos una aproximacin inicial del vector
solucin, se usa como vector inicial el vector cero, ie
Mtodo de Jacobi
Para determinar x(1) reemplazamos x(0) en el sistema dado
ie
32
MTODOS ITERATIVOS DE SOLUCIN
T
x 0,0,0,00
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
33/129
Para determinar x(1) reemplazamos x(0) en el sistema dado
ie
33
MTODOS ITERATIVOS DE SOLUCIN
T
x
x
x
x
x
x
x
x
xx
4
1,
4
1,
4
1,
4
1
4
14
141
4
1
4
0
4
1 4
0
4
0
4
141
40
40
4
1
4
)1(
4
3
2
1
1
4
1
3
1
2
21
1
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
34/129
Determinandox(2)
34
MTODOS ITERATIVOS DE SOLUCIN
T
x
xx
xx
xx
xxx
16
5,
16
5,
16
5,
16
5
16
5
6
5
4
1
4
114
1
16
6
4
6
4
1
4
1
4
111
4
1
166
46
41
411
4141
41
16
5
4
11
4
101
4
1
)2(
3
4
2
4
3
3
2
3
32
22
3
1
2
2
2
1
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
35/129
35
MTODOS ITERATIVOS DE SOLUCIN
R
0 0.0000 0.0000 0.0000 0.00001 0.2500 0.2500 0.2500 0.2500
2 0.3125 0.3750 0.3750 0.3125
3 0.3438 0.4219
4 0.3555 0.4414
5 0.3604 0.4492
6 0.3223 0.4524
7 0.3631 0.4537
8 0.3634 0.4542
9 0.3635 0.4544
10 0.3636 0.4545 0.4545 0.3636
Rx1Rx 2
Rx3Rx4
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
36/129
36
Mtodo Gauss-Seidel
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
37/129
MTODO GAUSS SEIDEL DESPLAZAMIENTO SUCESIVO
Este mtodo se diferencia del anterior en que los valores
que se van calculando en la (R + 1) sima iteracin seusan para calcular los valores restantes de esa misma
interaccin.
37
MTODOS ITERATIVOS DE SOLUCIN
nixaxaba
x
xaxaba
xaxaba
xaxaba
x
x
x
x
i
ijj
R
ji
Rn
Iiij
jii
ii
R
i
RR
RR
RR
R
R
R
R
1,1
)(
1
)(1
)(1
1
1
1
1
1
1
232
1
131333
323
1
1212
22
3122121
11
1
3
1
2
1
1
1
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
38/129
38
Este mtodo en general converge mas rpidamente que el mtodo deJacobi.
Supone que una mejor aproximacin a la solucin, se obtienesustituyendo los valores parciales calculados, en lugar de asumir una
aproximacin inicial.
Utilizando las ecuaciones de (1):
1313212111 bxaxaxa
2323222121 bxaxaxa
3333232131 bxaxaxa
Mtodo de Gauss-Seidel
MTODOS ITERATIVOS DE SOLUCIN
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
39/129
39
Y despejando para x1, x2 y x3y adicionando los valores ya obtenidos,esta se puede expresar como:
El valor de x1se calcula con los valores asumidos de x2y x3.
Posteriormente el valor de x1 obtenido y x3 asumido, se usan para
calcular x2. Y finalmente el nuevo valor de x3 sale de los valores
calculados x1 y x2.
33
)1(232
)1(1313)1(
3a
xaxabx
kkk
33
)1(232
)1(1313)1(
3a
xaxabx
kkk
22
)(323
)1(1212)1(
2a
xaxabx
kkk
22
)(323
)1(1212)1(
2a
xaxabx
kkk
11
)(
313
)(
2121)1(
1a
xaxabx
kkk
11
)(
313
)(
2121)1(
1a
xaxabx
kkk
Mtodo de Gauss-Seidel
MTODOS ITERATIVOS DE SOLUCIN
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
40/129
40
Ejemplo: Resolver el siguiente sistema de tres ecuaciones por el
Mtodo de Gauss Seidel, para un a= 5% :17 X1 2 X2 3 X3= 500
-5 X1 + 21 X2 2 X3= 200
-5 X1 5 X2+ 22 X3= 30
Las siguientes frmulas las utilizamos para encontrar
X1, X2y X3en cada una de las iteraciones
11
31321211
axaxabx
11
31321211
axaxabx
22
32312122
axaxabx
22
32312122
axaxabx
33
23213133
a
xaxabx
33
23213133
a
xaxabx
Mtodo de Gauss-Seidel
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
41/129
41
El valor de x1se calcula con los valores asumidos de x2y x3 que en principioes cero. Posteriormente el valor de x1obtenido y x3asumido (0), se usan
para calcular x2. Y finalmente el nuevo valor de x3 sale de los valorescalculados x1 y x2.
41176,29
17
0302500
1
1
11
31321211
x
x
a
xaxabx
41176,29
17
0302500
1
1
11
31321211
x
x
a
xaxabx
52661,16
21
0241176,295200
2
2
22
32312122
x
x
a
xaxabx
52661,16
21
0241176,295200
2
2
22
32312122
x
x
a
xaxabx
80418,11
22
52661,16541176,29530
3
3
33
23213133
x
x
a
xaxabx
80418,11
22
52661,16541176,29530
3
3
33
23213133
x
x
a
xaxabx
Mtodo de Gauss-Seidel
MTODOS ITERATIVOS DE SOLUCIN
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
42/129
42
Para la segunda iteracin, en el clculo de X1el valor de X2y X3sern loscalculados anteriormente. Entonces para X1:
Para X2se utiliza el valor de X3de la primera iteracin y el de X1de lasegunda iteracin:
43916,33
17
80418,11352661,162500
1
1
11
31321211
x
x
a
xaxabx
43916,33
17
80418,11352661,162500
1
1
11
31321211
x
x
a
xaxabx
60972,18
21
80418,11243916,335200
2
2
22
32312122
x
x
axaxabx
60972,18
21
80418,11243916,335200
2
2
22
32312122
x
x
axaxabx
Mtodo de Gauss-Seidel
MTODOS ITERATIVOS DE SOLUCIN
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
43/129
43
Una vez obtenidos estos resultados,se debe calcular el error aproximado
porcentual para cada uno de los
resultados, con la frmula:
19293,13
22
60972,18543916,33530
3
3
33
23213133
x
x
axaxabx
19293,13
22
60972,18543916,33530
3
3
33
23213133
x
x
axaxabx
%100
nuevor
anterior
r
nuevo
ra
xxx %100
nuevo
r
anterior
r
nuevo
ra
xxx
Para X3 se utiliza el valor de X1 y X2 calculados en la segunda iteracin:
Mtodo de Gauss-Seidel
MTODOS ITERATIVOS DE SOLUCIN
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
44/129
44
Una vez aplicado el clculo de error se determina que los valores sonsuperiores a la premisa inicial (
a = 5%), determinndose que se
deben continuar las iteraciones hasta que se cumpla el criterio.
Se resaltan los datos donde los errores obtenidos son menores que5%, se logra un error aproximado porcentual menor en las tresincgnitas en la tercera iteracin
Iteracin x1 x2 x3 ax1 ax2 ax3
0 0,00000
1 29,41176 16,52661 11,80418
2 33,43916 18,60972 13,19293 12,044% 11,194% 10,526%
3 33,92931 18,85869 13,36091 1,445% 1,320% 1,257%
Mtodo de Gauss-Seidel
MTODOS ITERATIVOS DE SOLUCIN
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
45/129
45
Si sustituimos estos valores en las ecuaciones originales para verificar losresultados se obtiene:
17 *(33,92931) 2 *(18,85869) 3 *(13,36091) = 498,99813
-5 *(33,92931) + 21*(18,85869) 2 *(13,36091) = 199,66404
-5 *(33,92931) 5 *(18,85869) +22 *(13,36091) = 30,00000
Al calcular los porcentajes de error de estos resultados se obtiene:
Los resultados obtenidos son una aproximacin muy buena de los valoresverdaderos.
0,00%%10030
30-30Error
0,17%%100200
199,66404-200Error
0,20%%100500
498,99813-500Error
EC3
EC2
EC1
0,00%%10030
30-30Error
0,17%%100200
199,66404-200Error
0,20%%100500
498,99813-500Error
EC3
EC2
EC1
Mtodo de Gauss-Seidel
MTODOS ITERATIVOS DE SOLUCIN
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
46/129
Mtodo de Gauss Seidel
46
MTODOS ITERATIVOS DE SOLUCIN
1
332
1
1313
33
4
12
323
1
121222
414313121
11
1
4
13
1
2
1
1
1
1
1
1
RR
RR
RRR
R
R
R
R
R
xaxaba
xxaxaba
xaxaxaba
x
x
x
x
x
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
47/129
Determinacin del
47
MTODOS ITERATIVOS DE SOLUCIN
134312421141444
)1( 1 RRR xaxaxaba
x
256
89,
64
25,
12
5,
4
1
256
89)14/25001(
4
1 64
25))16/5(1)4/1(11(
4
116
5))0(1)4/1(11(
4
1 4
1)0)0(1(
4
1
1
1
4
1
4
1
3
1
3
1
2
1
2
1
1
1
1
x
xx
xx
xx
xx
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
48/129
Observacin:
La sucesin de vectores converge o sealeja del vector solucin
Cuando se detendr el proceso iterativo
Rpta: Si la sucesin converge a la solucin x casoesperado que los componentes de x(R) converjan a suselementos
48
MTODOS ITERATIVOS DE SOLUCIN
,....,....,,, )()3()2()1( Rxxxx
Tnxxxxx ,.....,,, 321
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
49/129
Ejemplo:
Resolver el siguiente sistema con el mtodo de Gauss
Seidel con E = 10-2 aplicando a |xK+1 xK|
49
MTODOS ITERATIVOS DE SOLUCIN
32
2
15489
10253
4321
42
4321
4321
xxxx
xx
xxxx
xxxx
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
50/129
Resolviendo: x1de (1) x2 de (2) x3de (4) y x4 de (3)
50
M TO OS IT RATIVOS SO UCIN
2
322
915
9
4
9
8
9
10253
24
43213
4312
4321
xx
xxxxx
xxxx
xxxx
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
51/129
Six0 = (0, 0, 0, 0)T : determinamos:
51
05.143971.1680.11082.1701.6313
0.15917.202.121172.189889.672
62.177778.0222.147778.20000.101
000000
|| 14321
KKKKKK xxxxxxK
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
52/129
El proceso diverge: Luego podemos arreglar las ecuaciones
para despejar los diferentes x y, que despejadas
sean distintas, para aplicar el teorema se debe tener soloen cuenta una aproximacin pues caso contrario son raros
en donde se encontrara tales sistemas
52
2
5
10
5
2
5
3
5
9
15
9
4
9
8
9
23
222
24
421
3
431
2
4321
xx
xxxx
xxxx
xxxx
n
K
n
K
K
xx
xx
xx
22
11
Caso contrario se
alejan
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
53/129
Los valores absolutos
que sean todos menores de nmeropequeo Ecuyo valor ser dado
Si el nmero de iteraciones ha excedido unmximo dado
Detener el proceso una vez que
53
||,......|,||,| 121
21
1
1
K
n
K
n
KKKK xxxxxx
Exx KK || 1
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
54/129
Cmo asegurar la convergencia si existe?
El proceso de Jacobi y Gauss Seidel convergern si en la
matriz de coeficiente cada elemento de la diagonalprincipal es mayor que la suma de los valores absolutos
de todos los dems elementos de la misma fila o
columna (matriz diagonal dominante)
54
njaa
y
niaa
jii
ijii
n
jjj
ijii
1||
1||||
1
1
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
55/129
55
Mtodos de Relajacin
Mtodo de SOR
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
56/129
MTODO DE RELAJACIN DE SOR
Este mtodo es muy similar al mtodo de Jacobi y Gauss-Seidel se
diferencia por usar una escala para reducir el error de aproximacin,
es una metodologa mas reciente, para determinar X(k) lo realiza con
el modelo:
0bsevemos que cuanto w=1, tenemos de Gauss-Seidel, cuanto
0
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
57/129
Cuando 1
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
58/129
Ejemplo
La solucin del sistema dado es (3,4,-5)t , usaremos w=1.25 para el
mtodo de SOR con un valor inicial de (1,1,1)t, para k=1
Tenemos
58
Mtodo de SOR
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
59/129
Cuadro en 7 iteraciones
59
k 0 1 2 3 4 5 6 7
1 6.312500 2.6223145 3.133027 2.9570512 3.0037211 2.9963276 3.00004
1 3.5195313 3.9585266 4.0102646 4.0074838 4.0029250 4.0009262 4.00026
1 -6.6501465 -4.6004238 -5.0966863 -4.9734897 -5.0057135 -4.998282 -5.0004
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
60/129
60
Mtodo Gauss-Seidel con relajacin
El mtodo de Gauss-Seidel con Relajacin es muy similar a al mtodo de
Gauss-Seidel, la diferencia es que usa un factor de escala para reducir elerror de aproximacin.
Este mtodo obtiene un nuevo valor estimado haciendo una ponderacinentre el valor previo y el calculado utilizando un factor de ponderacin
0 2
)( )1()()1()(
k
i
k
i
k
i
k
i xxxx )( )1()()1()(
k
i
k
i
k
i
k
i xxxx
anteriori
nuevoi
nuevoi xxx )1(
anteriori
nuevoi
nuevoi xxx )1(
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
61/129
61
Mtodo Gauss-Seidel con relajacin = 1
El resultado no se modifica
Se convierte en la ecuacin de Gauss-Siedel
< 1
Se conoce como subrelajacin Para hacer que un sistema no convergente converja o apresure la
convergencia al amortiguar las oscilaciones.
> 1
Se conoce como sobrerelajacin
Se usa cuando la convergencia va en la direccin correcta hacia la solucinverdadera, pero con una velocidad demasiado lenta. Para llevarla ms cerca
de la verdadera.
La eleccin dees emprica, se utiliza para la solucin de un sistema que se deberesolver de manera repetitiva.
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
62/129
62
Mtodo Gauss-Seidel con relajacin Y despejando para x1 , x2y x3, y adicionando los valores ya obtenidos,
esta se puede expresar como:
El valor de x1se calcula con los valores asumidos de x2y x3.
Posteriormente el valor de x1 obtenido y x3 asumido, se usan para
calcular x2. Y finalmente el nuevo valor de x3 sale de los valores
calculados x1 y x2.
33
)1(232
)1(1313)1(
3a
xaxabx
kkk
33
)1(232
)1(1313)1(
3a
xaxabx
kkk
22
)(323
)1(1212)1(
2a
xaxabx
kkk
22
)(323
)1(1212)1(
2a
xaxabx
kkk
11
)(
313
)(
2121)1(
1a
xaxabx
kkk
11
)(
313
)(
2121)1(
1a
xaxabx
kkk
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
63/129
63
Mtodo Gauss-Seidel con relajacinEjemplo 3:
Emplee el mtodo de Gauss-Seidel con relajacin para resolver(=0.90 y
a= 5%):
-5 X1 + 12 X3 = 80
4 X1 1 X2 1 X3 = - 2
6 X1 + 8 X2 = 45
Si es necesario reordene las ecuaciones para que el sistema
converja.
45
2
80
86
114
125
3
2
1
x
x
x
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
64/129
64
Mtodo Gauss-Seidel con relajacin
Verificando el criterio de convergencia:
Para un sistema de 3 x 3 obtenemos:
n
ij
jjiii aa
1,,
323133
232122
131211
aaa
aaa
aaa
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
65/129
65
Mtodo Gauss-Seidel con relajacin
Esto quiere decir que el elemento diagonal debe ser mayor al elemento
fuera de la diagonal para cada fila. Por tanto reorganizamos el sistemade la siguiente forma:
Por lo tanto se puede asegurar la convergencia con este arreglo.
8045
2
12586
114
3
2
1
xx
x
51268
114
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
66/129
66
Mtodo Gauss-Seidel con relajacin
Para calcular el primer valor de X1, se
asumirn X2 y X3 con valores cero.Entonces para X1,
Para calcular el valor de X2, se utilizarsolamente el valor encontrado de X1, dado
que a23es cero.
Para calcular el valor de X3, se utilizar
solamente el valor encontrado de X1, dado
que a32es cero.
50000,04
01012
1
1
11
31321211
x
x
a
xaxabx
50000,04
01012
1
1
11
31321211
x
x
a
xaxabx
00000,6
8
)50000,0(645
2
2
22
32312122
x
x
a
xaxabx
00000,6
8
)50000,0(645
2
2
22
32312122
x
x
a
xaxabx
45833,6
12
)50000,0(580
3
3
33
23213133
x
x
a
xaxabx
45833,6
12
)50000,0(580
3
3
33
23213133
x
x
a
xaxabx
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
67/129
67
Mtodo Gauss-Seidel con relajacin Segunda iteracin:
61458,2
445833,610000,612
1
1
11
31321211
x
x
a
xaxabx
30313,2)50000,0()9,01(61458,29,0
)1(
1
1
111
nuevo
nuevo
anteriornuevonuevo
xx
xxx
89766,3
8
)30313,2(645
2
2
22
3231212
2
x
x
a
xaxabx
10789,4
)00000,6()9,01(89766,39,0
2
2
nuevo
nuevo
x
x
62630,7
12
)30313,2(580
3
3
33
23213133
x
x
a
xaxabx
50951,7
)45833,6()9,01(62630,79,0
3
3
nuevo
nuevo
x
x
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
68/129
68
Mtodo Gauss-Seidel con relajacin
Se debe realizar el clculo de los errores y se debe continuar iterandohasta que se cumpla la premisa inicial (
a
= 5%).
Se resaltan los datos donde los errores obtenidos son menores que5%, se logra un error aproximado porcentual menor en las tres
incgnitas en la cuarta iteracin
Iteracin x1 x2 x3 ax1 ax2 ax3
0 0,00000 0,00000 0,00000
1 -0,50000 6,00000 6,458332 2,30313 4,10789 7,50951 121,71% 46,06% 14,00%
3 2,39423 3,85719 7,64879 3,81% 6,50% 1,82%
4 2,37827 3,84289 7,65673 0,67% 0,37% 0,10%
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
69/129
69
Mtodo Gauss-Seidel con relajacin Si sustituimos estos valores en las ecuaciones originales para verificar los
resultados se obtiene:
4 *(2,37827) 1 *(3,84289) 1 *(7,65673) = -1,98655
6 *(2,37827) + 8 *(3,84289) + 0 *(7,65673) = 45,01271
-5 *(2,37827) + 0 *(3,84289) + 12 *(7,65673) = 79,98941
Al calcular los porcentajes de error de estos resultados se obtiene:
0,01%%100
80
79,98941-80Error
0,03%%10045
45,01271-45Error
0,67%%1002-
(-1,98655)-2-Error
EC3
EC2
EC1
0,01%%100
80
79,98941-80Error
0,03%%10045
45,01271-45Error
0,67%%1002-
(-1,98655)-2-Error
EC3
EC2
EC1
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
70/129
70
Comparacin de Mtodos
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
71/129
71
Ejercicio
Resolver el siguiente sistema de ecuaciones, para un error a5 %, con los tres mtodos analizados.
14
4124
21
12112
3
2
1
x
xx
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
72/129
72
Jacobi
%100
nuevo
r
anterior
r
nuevo
r
a x
xx
33
23213133
a
xaxabx
11
31321211
a
xaxabx
22
32312122
a
xaxabx
Iteracin X1 x2 x3 ax1 ax2 ax3
0 0,00000 0,00000 0,00000
1 62,00000 2,00000 7,00000
2 63,00000 36,50000 8,00000 1,587% 94,521% 12,500%
3 80,25000 37,50000 25,25000 21,495% 2,667% 68,317%
4 80,75000 54,75000 25,75000 0,619% 31,507% 1,942%
5 89,37500 55,25000 34,37500 9,650% 0,905% 25,091%
6 89,62500 63,87500 34,62500 0,279% 13,503% 0,722%7 93,93750 64,12500 38,93750 4,591% 0,390% 11,075%
8 94,06250 68,43750 39,06250 0,133% 6,301% 0,320%
9 96,21875 68,56250 41,21875 2,241% 0,182% 5,231%
10 96,28125 70,71875 41,28125 0,065% 3,049% 0,151%
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
73/129
73
Gauss-Seidel
%100 nuevor
anterior
r
nuevo
ra
xxx
33
23213133
a
xaxabx
11
31321211
a
xaxabx
22
32312122
a
xaxabx
Iteracin x1 x2 x3 ax1 ax2 ax3
0 0,000001 62,00000 33,00000 23,50000
2 78,50000 53,00000 33,50000 21,019% 37,736% 29,851%
3 88,50000 63,00000 38,50000 11,299% 15,873% 12,987%
4 93,50000 68,00000 41,00000 5,348% 7,353% 6,098%
5 96,00000 70,50000 42,25000 2,604% 3,546% 2,959%
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
74/129
74
Gauss-Seidel con Relajacin
%100nuevo
r
anterior
r
nuevo
ra
xxx
33
23213133
a
xaxabx
11
31321211
a
xaxabx
22
32312122
a
xaxabx
anteriori
nuevoi
nuevoi xxx )1(
Iteracin x1 x2 x3 ax1 ax2 ax3
0 0,00000 0,00000 0,00000
1 62,00000 33,00000 23,50000
2 81,80000 58,98000 39,08800 24,205% 44,049% 39,879%
3 93,42800 70,11360 42,65056 12,446% 15,879% 8,353%
4 97,78256 72,63715 43,45218 4,453% 3,474% 1,845%
= 1,20
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
75/129
75
Comparacin de MtodosHaciendo un resumen de los resultados obtenidos en la siguiente tabla:
El mtodo de Jacobi es el que utiliza una mayor cantidad de iteracionesy que adems tiene errores mayores con respecto al valor verdadero.
Gauss-Seidel los errores son medianos, pero la cantidad de lasiteraciones en mucho menor que en el caso de Jacobi.
Gauss-Seidel con relajacin se obtienen valores ms cercanos a losverdaderos con una cantidad de iteraciones menor. Sin embargo el
inconveniente radica en la eleccin del valor de.
Incgnita Valores
verdaderos
Iteracio-
nes
Valores aproximados Errores verdaderos
Jacobi Seidel C/Relaj Jacobi Seidel C/Relaj
X1 98,5 10 96,281 96,000 97,783 2,25% 2,54% 0,73%
X2 73,0 5 70,719 70,500 72,637 3,13% 3,42% 0,50%
X3 43,5 4 41,281 42,250 43,452 5,10% 2,87% 0,11%
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
76/129
76
Comparacin de Mtodos
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
77/129
77
Comparacin de Mtodos
Se observa que para las tres incgnitas con mtodo de Jacobilos resultados son ms oscilantes y convergen de forma mslenta.
Por el Mtodo de Gauss-Seidel se da una convergenciarelativamente rpida.
Si al Mtodo de Gauss-Seidel le aplicamos relajacin laconvergencia es mucho ms rpida hacia los valoresverdaderos.
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
78/129
78
Algoritmos
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
79/129
79
Algoritmos
En la prctica, normalmente utilizamos computadoras
para realizar las iteraciones, es por esta razn que
necesitamos implementar algoritmos para encontrar
soluciones de sistemas n x n mediante los mtodos
anteriormente descritos.
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
80/129
ALGORITMO DE LOS MTODOS DE JACOBI GAUSSSEIDEL
Para solucionar el sistema de Ax = bDatos:Nmero de ecuaciones N
La matriz de coeficientes A
El vector de trminos independientes bEl vector inicial x
El nmero de iteracin MATIZ
El valor de Eps.y M = 0 para usar Jacobi y M
0 para usar GaussSeidel obtenemos la solucin aproximada x y el nmero de
iteraciones K o el mensaje No se alcanz la convergencia
80
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
81/129
Paso1:Arreglar la matriz aumentada de manera que la matrizcoeficiente quede lo ms cercano posible a la diagonal dominante
Paso2:Hace K = 1
Paso3:Mientras K Maxit repetir los pasos 4 a 18
Paso4:Si M = 0 ir al paso 5 de otro modo hacer x = x
Paso5:Hacer I = 1
Paso6:Mientras I N repetir los pasos 7 al 14
Paso7:Hacer suma = 0
Paso8:Hacer J = 1
Paso9:Mientras J N, repetir los pasos 10 a 12
Paso10:Si J = I ir al paso 12
81
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
82/129
Paso11:Hacer suma = suma + A(IJ) * x(J)
Paso12:Hacer J = J + 1Paso13:Si M = 0 hacer
x(J) = -(b(J) - suma)/A(JJ)de otro modo hacer
x(I) = (b(J) suma)/A(JJ)
Paso14: Hacer I = J + 1
82
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
83/129
Paso15:Si |x x| Eps.Ir al paso 19
de otro modo hacer
Paso16:Si M = 0, hacer x = x
Paso17:Hacer K = K + 1
Paso18:Imprimir mensaje No se alcanz la convergencia,el vector x, MAXIT
Paso19:Imprimir el mensaje Vector Solucin, x, K y elmensaje iteraciones terminada
83
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
84/129
84
Algoritmo JacobiFor k=1,2,
For i=1,2,, nxi=0For j=1,2,,i-1,i+1,,n
End
End
End
1 kjijii Xaxx
xxk
iiiii axbx /)(
)1(,i
ii
(k)
i -ba
1
k
j
n
ij
ji xax
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
85/129
85
Algoritmo Gauss-SeidelFor k=1,2,
For i=1,2,, nsum=0For j=1,2,,i-1,
End
For j=i+1,,n
End
EndEnd
ii
n
ij
k
jij
i
j
k
jiji
k
ia
xaxab
x
1
11
1
k
jijXasumsum
1 kjijXasumsum
iii
k
i asumbx /)(
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
86/129
86
Algoritmo Gauss-Seidel con relajacin
in
ij
k
jij
i
j
k
jiji
ii
k
i Xxaxaba
x
1
1
11
1
For k=1,2,For i=1,2,, n
sum=0
For j=1,2,,i-1,EndFor j=i+1,,n
End
End
End
k
jijXasumsum
1 kjijXasumsum
iii
k
i asumbx /)(
)( 11 k
iki
ki
ki xxxx
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
87/129
87
Primera iteracin
Segunda iteracin
Gauss-Seidel Iterativo de Jacobi
anterior
i
nuevo
i
nuevo
i xxx )1( Gauss-Seidel con relajacin
Desplazamiento
simultneo
Desplazamiento
succesivo
Resumen de los pasos de los mtodos iterativos Jacobi,Gauss-Seidel sin y con relajacin
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
88/129
88
SntesisLos mtodos iterativos son ptimos para grandes sistemas yson mejor aprovechados cuando se tienen matrices esparcidas.
Estos mtodos iterativos estn basados en el concepto de puntofijo, es decir ( xi= gi(x), i = 1.. n), para resolver sistemas deecuaciones lineales.
Para garantizar la convergencia se debe de cumplir que elsistema tenga una diagonal dominante, es decir que se cumplala desigualdad siguiente, si se cambio el orden de las
ecuaciones esta puede divergir
n
iji
ija
iia
1
S i
MTODOS ITERATIVOS DE SOLUCIN
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
89/129
89
SntesisPara mejorar la convergencia, se usan tcnicas como:Utilizacin de los clculos previos asumiendo que una mejor
aproximacin que el vector de condiciones iniciales. (Gauss-Siedel )
Un factor de ponderacin para reducir el error residual ( Relajacin )
La seleccin de un vector de condiciones iniciales apropiado ayuda a
reducir el nmero de iteraciones.
La seleccin de es de carcter prctico y de su eleccin se pueden
lograr tambin que el nmero total de iteraciones se reduzcan.
La finalizacin del clculo de iteraciones se logra cuando todos loselementos de vector de residual estn debajo de la tolerancia requerida.
El mtodo de Jacobi presenta mas oscilaciones que los mtodos de
Gauss-Siedel y relajacin.
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
90/129
90
Mtodos de Gradiente
MTODOS DEL DESCENSO MS RPIDO DELGRADIENTE CONJUGADO
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
91/129
En esta oportunidad reflexionaremos sobre algunos
mtodos especiales para resolver sistemas de ecuaciones
lineales.
En donde la matriz A es de orden nxn simtrica y definida
positiva, en otras palabras, ,y debemosrecordar que el producto escalar de dos vectores X ,Y de
componentes reales es:
91
MTODOS DEL DESCENSO MS RPIDO DELGRADIENTE CONJUGADO
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
92/129
Propiedades
1.
2.
3.
4.
Observemos que la propiedad 1 se refiere al orden de los
elementos, 2, y 3 indican que se pueden invertir.
92
MTODOS DEL DESCENSO MS RPIDO DELGRADIENTE CONJUGADO
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
93/129
Recordemos que si A es simtrica y definida positiva,
entonces el problema de resolver Ax=b es equivalente
al problema:
Veamos por que esta afirmacin es cierta; primero
veamos como se comporta q(x) a lo largo de un rayounidimensional. Para lo cual consideremos x+tv en
donde x y v son vectores y t un escalar grficamente
tenemos
93
x
tv
x+ tv
MTODOS DEL DESCENSO MS RPIDO DELGRADIENTE CONJUGADO
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
94/129
Mediante un calculo directo tenemos que para todo
escalar t :
(*)
94
MTODOS DEL DESCENSO MS RPIDO DELGRADIENTE CONJUGADO
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
95/129
Como A es simtrica es decir AT =A, entonces en la
ecuacin (*) el coeficiente de t2, es positivo, de esta
manera la funcin cuadrtica sobre el rayo
unidimensional tiene un mnimo y no un mximo.
Calculando la derivada de la ecuacin (*) con respecto at.
95
MTODOS DEL DESCENSO MS RPIDO DELGRADIENTE CONJUGADO
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
96/129
Cuando la derivada es cero, existe un mnimo de q a lo
largo del rayo unidimensional en este caso el valor de t
es: ,
en consecuencia usando este valor podemos
determinar el mnimo de q sobre el rayo unidimensional
(**)
96
MTODOS DEL DESCENSO MS RPIDO DELGRADIENTE CONJUGADO
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
97/129
Lo que quiere decir esto es que al pasar q(x) de x a, siempre hay una reduccin en el valor de q(x), a
menos que v sea ortogonal al residuo es decirSi x no es una solucin del sistema Ax=b entonces
existen una diversidad de vectores que satisfacen
Por lo tanto entonces x no minimiza q(x) y por lo contrario
si Ax=b no existe ningn rayo unidimensional que salga de x
sobre el cual q(x) tome un valor menor a q(x), en consecuenciauna x con las caractersticas es un mnimo para q(x).
97
MTODOS DEL DESCENSO MS RPIDO DELGRADIENTE CONJUGADO
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
98/129
Debemos manifestar que la reflexin anterior sugiere la
existencia de los mtodos iterativos para resolver Ax=b,
luego entonces procedemos de manera natural porminimizar q(x) a lo largo de una sucesin de rayos. Es
decir el algoritmo dispondr de un proceso de:
En seguida nos preocupa determinar la direccin de
bsqueda adecuada
Nuestro algoritmo ser
98
MTODOS DEL DESCENSO MS RPIDO DELGRADIENTE CONJUGADO
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
99/129
En donde
Debemos decir que una diversidad de mtodositerativos tienen la forma general:
99
MTODOS DEL DESCENSO MS RPIDO DELGRADIENTE CONJUGADO
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
100/129
Para valores particulares del escalar tK, y los valores de
vK, si , entonces tk, mide la distancia que nos
movemos de xK, para hasta la obtencin de xk+1, ver lasiguiente figura.
100
MTODOS DEL DESCENSO MS RPIDO DELGRADIENTE CONJUGADO
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
101/129
MTODO DEL DESCENSO MS RPIDO
Este mtodo se le considera dentro del grupo de
mtodos iterativos que usan el algoritmo anterior,considera que vK, debera ser el gradiente negativo
de q(x) en x(k), resultando que este gradiente apunta
en la direccin del residuoEs decir tenemos:
101
MTODOS DEL DESCENSO MS RPIDO DELGRADIENTE CONJUGADO
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
102/129
Es decir tenemos:
inputx(0), A, b, M
output0, x(0)
fork=0,1,2,, M-1 do
.
outputk+1, x(k+1)
end
102
MTODOS DEL DESCENSO MS RPIDO DELGRADIENTE CONJUGADO
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
103/129
Debemos destacar al programar este algoritmo no es
necesario conservar los vectores de la sucesin , lo mismo
ocurre con , de manera el algoritmo seria:
inputx, A, b, M
output0, x)
fork=0,1,2,, M-1 do
,
.
outputk, x)
end
103
Debemos destacar que este
mtodo generalmente no se
aplica a este tipo de
problemas como consecuenciade su lentitud
MTODOS DEL DESCENSO MS RPIDO DELGRADIENTE CONJUGADO
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
104/129
MTODO DEL GRADIENTE CONJUGADO
Otro mtodo considerado dentro del algoritmo analizado
anterior es el mtodo del gradiente conjugado de Hestenes yStiefel, el cual es aplicado a sistemas de la forma Ax=b, en
donde A es considerada simtrica y definida positiva.
En este mtodo las direcciones vK , son elegidas de una enuna en el proceso iterativo y forman un sistema A-ortogonal,
los residuos forman un sistema ortogonal es
decir,
104
MTODO DEL GRADIENTE CONJUGADO
MTODOS DEL DESCENSO MS RPIDO DELGRADIENTE CONJUGADO
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
105/129
MTODO DEL GRADIENTE CONJUGADO
Debemos decir que este mtodo es preferible que el
mtodo de eliminacin Gaussiana simple cuando la matrizA es muy grande y rala.
Este mtodo en su inicio fue muy sorprendente e
importante pero despus de dos dcadas las cosas ya nofue as como consecuencia que se descubri que la
terminacin finita no era asequible en la prctica.
105
MTODOS DEL DESCENSO MS RPIDO DELGRADIENTE CONJUGADO
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
106/129
MTODO DEL GRADIENTE CONJUGADO
Pues la terminacin finita era indeseable para un mtodo
directo, sin embargo posteriormente cuando se le
considero como un mtodo iterativo las cosas fue
diferente, pues en estos mtodos no es necesario obtener
una solucin absoluta despus de n pasos lo que seespera es obtener una respuesta satisfactoria.
106
La ejecucin del algoritmo en una computadora precisa de un lugar
MTODOS DEL DESCENSO MS RPIDO DELGRADIENTE CONJUGADO
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
107/129
j g p p g
de almacenamiento para cuatro vectores
107
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
108/129
108
Convergencia
CONVERGENCIA
CONVERGENCIA,
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
109/129
CONVERGENCIA
LONGITUD DE UN VECTORSupongamos x un vector en R2, su longitud denotado
por |x| es definido como un nmero positivo o cero.
En trminos de producto punto
109
l d
CONVERGENCIA
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
110/129
Ejemplo: sea determinar su norma
Debemos tener en consideracin que el campo de losnmeros reales R tiene el defecto de que un
polinomio de grado n con coeficientes reales no
necesariamente tiene n ceros realesejemplo
110
Su conjugado, norma, o modulo, se le define:
,,,,,,,,
,
CONVERGENCIA
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
111/129
j g
El campo de los complejos ya no tiene la anomala de los reales, esmas tenemos el teorema fundamental del algebra, que establece
que todo polinomio no constante con coeficientes complejostiene al menos un cero en el plano complejo.
La afirmacin anterior permite afirmar que todo polinomio de
grado n se puede descomponer como un producto de n factoreslineales.
111
ESPACIO VECTORIAL Cn
,,,,,,,
,
CONVERGENCIA
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
112/129
El espacio vectorial Cn, esta compuesto de todos
los vectores en donde los
Si al vector complejo x es multiplicado por tambin complejo el
resultado es otro vector complejo.
En consecuencia Cn, es un espacio vectorial sobre el cambo deescalares C. En consecuencia en este espacio Cn. El producto
interno se define
112
NORMA DE VECTORES
.
CONVERGENCIA
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
113/129
NORMA DE VECTORES
Una norma en Rn es una funcin de || || de Rn en R que verifica las
propiedades
113
La norma Euclidiana se define:
CONVERGENCIA
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
114/129
Podemos observar que,
Consideremos A una matriz con elementos complejos, y A* denota
su conjugada transpuesta es decir en particular, si x es
una matriz de nx1 (o vector columna), entonces , es una
matriz de 1xn o vector fila,
114
CONVERGENCIA
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
115/129
En general podemos definir norma de un vector x
Como casos particulares tenemos la norma Euclidiana cuando p=2
115
Mximo valor absoluto
CONVERGENCIA
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
116/129
Estas propiedades son familiares en relacin a la norma Euclidiana
o longitud de un vector.
La norma de una matriz cuadrada, A , puede ser definida enforma consistente con la definicin de norma de un vector:
116
La norma llamado generalmente norma infinito
CONVERGENCIA
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
117/129
Ejemplo:Dado el vector
determinar sus normas Euclidiana e Infinito
117
DISTANCIA EN ENTRE VECTORES
CONVERGENCIA
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
118/129
Dado dos vectores en Rn, , , la
distancia I2 y , entre x e y se definen :
118
Ejemplo:Dado el sistema:
CONVERGENCIA
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
119/129
3.3330x1+ 1.5920x2 10.333x3=15.913
2.2220x1+ 16.710x2+9.6120x3=28.5441.5611x1+ 5.1791x2+1.6852x3=8.4254
Consideremos la solucin inicial, ,usamos eliminacin de Gauss con Pivoteo parcial
usando aritmtica de cinco cifras con redondeo,
obtenemos la siguiente solucin:
119
Las dos medidas de la exactitud de aproximacin de
CONVERGENCIA
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
120/129
a x son:
120
Observamos que las componentes y son buenas
CONVERGENCIA
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
121/129
aproximaciones a x2y a x3, y la primera componente es
una aproximacin muy pobre en trminos de distanciasde ambas normas.
Pues el trmino de distancia en Rn , es utilizada para
definir el limite de una sucesin de vectores.
Diremos que una sucesin de vectores converge
a x con respecto a la norma ||*|| si dado cualquier
existe un entero tal que:
121
Ejemplo.Dada la sucesin definida:
CONVERGENCIA
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
122/129
Tenemos que,
Es as que podemos encontrar un numero entero de tal
manera que para todos los nmeros
122
son menores que lo que nos afirma esto es que la
CONVERGENCIA
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
123/129
sucesin converge a con respecto a la norma .
Los siguientes trminos son equivalentes:
La sucesin de vectores , converge a x con respecto a
alguna norma.
La sucesin de vectores , converge a x con respecto a
todas las normas.
El , la componente i-sima de x, para cadai =1,2,..,n sucesin de vectores, converge a x con
respecto a alguna norma.
123
NORMAS MATRICIALES
CONVERGENCIA
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
124/129
Una norma matricial en el espacio de matricial nxnes una
funcin de variable real que verifica las siguientescondiciones para todas las matrices A y B de dimensin
nxn y todos los nmeros reales
124
NORMA MATRICIAL MXIMO O SUBORDINADA
CONVERGENCIA
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
125/129
Es la norma , vectorial en Rn, la cual se le define sobre
el conjunto de todas las matrices de orden nxn as
Consecuentemente las normas que consideramos son:
125
Cuando n=2 su interpretacin grfica es:
CONVERGENCIA
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
126/129
126
1
x
1-1
-1
x1
1
Ax
1-1
-1x1-2
2
3
-3
Norma de una matriz
CONVERGENCIA
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
127/129
127
1
x
1-1
-1
x1
1
x
1-1
-1
x1-2 2
-2
2
AX
Ejemplo: dada la matriz
CONVERGENCIA
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
128/129
DeterminarSolucin
128
-
7/26/2019 sistemas de ecuaciones algebraicas lineales metodos iterativos
129/129
Muchas Gracias129