Programación AvanzadaSolución de Sistemas de Ecuaciones Lineales-
Semestre 2019-1
Ing. Juan Carlos Sabido AlcántaraIngeniero Petrolero
Facultad de Ingeniería UNAM
Sistemas de Ecuaciones Lineales
• Muchos problemas relacionados con la ingeniería en todassus ramas, se pueden expresar en términos de sistemas deecuaciones lineales simultáneas. Comúnmente se conocendos métodos para resolver estos sistemas, la eliminación delas incógnitas mediante la combinación de ecuaciones, y eluso de determinantes que es lo que se conoce como Reglade Cramer. Aquí se abordarán otro tipo de métodos pararesolver estos sistemas y que pueden ser implementadosen programas de computadora.
Ing. Juan Carlos Sabido Alcántara
Sistemas de Ecuaciones Lineales• Conceptos básicos.
• Un sistema de ecuaciones lineales es un conjunto de ecuaciones dela forma:
•
• Que tiene la siguiente representación matricial:
•
Ing. Juan Carlos Sabido Alcántara
nnnnnnn
nn
nn
nn
bxaxaxaxa
bxaxaxaxa
bxaxaxaxa
bxaxaxaxa
,33,22,11,
3,333,322,311,3
2,233,222,211,2
1,133,122,111,1
...
...
...
...
nnnnnnn
n
n
n
b
b
b
b
x
x
x
x
aaaa
aaaa
aaaa
aaaa
3
2
1
3
2
1
321
3333231
2232221
1131211
Sistemas de Ecuaciones Lineales• Conceptos básicos.
• Y que a su vez se puede representar como: . La solución deeste sistema de ecuaciones es un conjunto de n valores
que satisfacen simultáneamente a todas las ecuaciones.
• La matriz 2 es una matriz de coeficientes, es decir, los elementosque la conforman son los coeficientes de las incógnitas que formanel sistema de ecuaciones, si las constantes b del sistema se agregana la matriz se tendrá la matriz ampliada del sistema:
Ing. Juan Carlos Sabido Alcántara
bxA
1 2 3, , , , nx x x x
nnnnnn
n
n
n
baaaa
baaaa
baaaa
baaaa
321
33333231
22232221
11131211
Sistemas de Ecuaciones Lineales• Método de Cramer.
• La expresión general de la solución de un SEL por el método deCramer es:
• Para aplicar este método en primer lugar hay que evaluar n+1determinantes y luego realizar n divisiones.
Ing. Juan Carlos Sabido Alcántara
niA
aabaa
aabaa
aabaa
xnninninn
nii
nii
i ,,1
1,1,1
21,221,221
11,111,111
Sistemas de Ecuaciones Lineales• Método de Cramer.
• Ejemplo: ቐ
2𝑥 − 𝑦 + 𝑧 = 32𝑦 − 𝑧 = 1
−𝑥 + 𝑦 = 1
• ∆=2 −1 10 2 −1−1 1 0
= 3 𝑥 =
3 −1 11 2 −11 1 0
3=
3
3= 1
• 𝑦 =
2 3 10 1 −1−1 1 0
3=
6
3=2; z=
2 −1 30 2 1−1 1 1
3=
9
3= 3
Ing. Juan Carlos Sabido Alcántara
Sistemas de Ecuaciones Lineales• Método de Cramer.
• Para el cálculo de los determinantes, una de las posibles técnicasnecesita de n!n multiplicaciones y n!-1 sumas. Por consiguiente, elmétodo de Cramer necesita de:
• sumas
• productos
• divisiones
• Cada operación requiere de una cantidad de recursos de lacomputadora para poder efectuarla, por lo que mientras másoperaciones se realicen más complejo será para esta realizar dichasoperaciones.
Ing. Juan Carlos Sabido Alcántara
1!1 nn
nnn !1
n
Sistemas de Ecuaciones Lineales• Método de Cramer.
• El número de operaciones que tendría que realizar unacomputadora para resolver un SEL de orden n utilizando el métodode Cramer esta dado por la siguiente expresión:
• Los datos reportados en la siguiente tabla muestran el número deoperaciones necesarias para resolver un SEL de 5, 10 y 100incógnitas.
Ing. Juan Carlos Sabido Alcántara
!12nnTc
N Tc
5 4319
10 4*108
100 10158
Sistemas de Ecuaciones Lineales• Método de Cramer.
• Si se dispone de una computadora capaz de realizar 100 millones deoperaciones en punto flotante por segundo, el sistema de n=100necesitaría aproximadamente de 3 x 10142 años para ser resuelto,por lo que es evidente que el método de Cramer resulta inadecuadopara resolver cualquier SEL.
Ing. Juan Carlos Sabido Alcántara
!12nnTc
N Tc
5 4319
10 4*108
100 10158
Sistemas de Ecuaciones Lineales• Conceptos de norma, número de condición y estabilidad.
• Norma de una matriz.
• Cuando se manejan matrices o vectores es necesario explicar dealguna manera su magnitud en términos cuantitativos. Una medidade esa magnitud es la norma. Esta expresa la exactitud de lasolución de un SEL en términos cuantitativos determinando lanorma del vector error (la solución verdadera menos la soluciónaproximada). Las normas son también usadas para estudiarcuantitativamente la convergencia de un método iterativo pararesolver SEL. Para esto existen varias maneras de calcular la normade una matriz, estas pueden ser:
Ing. Juan Carlos Sabido Alcántara
Sistemas de Ecuaciones Lineales• Conceptos de norma, número de condición y estabilidad.
• Norma de una matriz.
• Norma de Frobenius.
• Norma de Magnitud Máxima.
Ing. Juan Carlos Sabido Alcántara
21
1
2
1
n
j
ij
m
i
f aA
Renglones de Suma de Máximomax
Columna de Suma de Máximomax
11
1
11
1
n
i
ij
nj
n
i
ij
nj
aA
aA
Sistemas de Ecuaciones Lineales• Conceptos de norma, número de condición y estabilidad.
• Número de condición y error en la solución.
• El número de condición de una matriz es una medida deconfiabilidad de la matriz en el momento de realizar los cálculos. Elnúmero de condición esta dado por:
• El número de condición para la matriz identidad es:
• Por lo tanto la matriz identidad tiene el número de condición másbajo.
Ing. Juan Carlos Sabido Alcántara
1 AAAC
0.1)( IC
Sistemas de Ecuaciones Lineales• Conceptos de norma, número de condición y estabilidad.
• Número de condición y error en la solución.
• Un problema esta bien condicionado si cambios pequeños en lainformación de entrada ocasionan cambios pequeños en la salida.De otro modo se dice que está pobremente condicionado.
• Un número de condición grande indica que la solución es sensible apequeños cambios en el vector independiente. En los cálculosprolongados es probable que se realicen muchos redondeos y cadauno de ellos desempeñe el papel de un error de entrada para elresto del cálculo y cada uno tiene un efecto sobre la siguiente salida.
Ing. Juan Carlos Sabido Alcántara
Sistemas de Ecuaciones Lineales• Conceptos de norma, número de condición y estabilidad.
• Estabilidad.
• Por esto se deben realizar algoritmos estables en que el efectoacumulativo de tales errores sea limitado, de modo que se generenbuenos resultados, útiles para la solución del problema. Cuando elerror acumulativo es grande el algoritmo es inestable.
Ing. Juan Carlos Sabido Alcántara
Sistemas de Ecuaciones Lineales• Solución numérica.
• La eficacia de los algoritmos para la resolución de SEL se evalúa apartir de tres criterios fundamentales.
• Número de operaciones fundamentales: Ligado al tiempo invertidoen la realización de los cálculos por la computadora. Se deben teneren cuenta las operaciones elementales entre números de puntoflotante. El número de operaciones es obviamente un excelenteindicador del número de recursos invertido por la computadora.
Ing. Juan Carlos Sabido Alcántara
Sistemas de Ecuaciones Lineales• Solución numérica.
• Necesidades de almacenamiento: Inciden directamente en laslimitaciones de la memoria de las diversas computadoras; losdiferentes métodos que aquí se estudiarán requieren almacenar lasmatrices de diferentes maneras y esto varía considerablemente losrequerimientos de memoria.
• Rango de aplicabilidad: No todos los métodos sirven para cualquiermatriz no singular (matriz singular: no tiene inversa); además, enfunción del método y de las propiedades de la matriz, la precisiónde los resultados puede verse afectada, como ya se mencionó antes,pequeños errores de redondeo pueden producir erroresdesproporcionados en la solución numérica.
Ing. Juan Carlos Sabido Alcántara
Sistemas de Ecuaciones Lineales
• Métodos directos y métodosindirectos (Iterativos).
• Métodos directos.
• Son aquellos que permiten obtener lasolución después de un número finitode operaciones aritméticas. Estenúmero de operaciones es función deltamaño de la matriz. Algunos de estosmétodos directos son:
• Métodos indirectos.• Un método iterativo es el desarrollo
de una solución aproximada para elsistema de ecuaciones. Laaproximación es remplazadasistemáticamente hasta que convergea la respuesta correcta. Algunos de
estos métodos indirectos son:
Ing. Juan Carlos Sabido Alcántara
Métodos Directos
Eliminación Gaussiana Descomposición LU
Métodos Iterativos
Método de Jacobi
Método de Gauss – Seidel
Método de Relajación Sucesiva (SOR)
Sistemas de Ecuaciones Lineales• Tipos de matrices utilizadas en ingeniería.
• Las matrices que son utilizadas en problemas de Ingeniería y en lasCiencias Aplicadas se clasifican en dos grandes categorías:
• Matrices “llenas” con dimensiones pequeñas. Se entiende por“llenas” que tienen muy pocos elementos iguales a cero y dedimensiones pequeñas se considera aquellas asociadas con SEL quetienen un número de ecuaciones de algunos miles como máximo.Aparecen en problemas estadísticos, matemáticos, físicos eingenieriles.
Ing. Juan Carlos Sabido Alcántara
Sistemas de Ecuaciones Lineales• Tipos de matrices utilizadas en ingeniería.
• Matrices “vacías” con dimensiones grandes. Se entiende por“vacías” que tienen muy pocos elementos diferentes de cero y estánsituados con cierta regularidad. En la mayoría de los casos elnúmero de ecuaciones del SEL alcanza por lo menos las decenas demiles y pueden llegar en ocasiones a los millones. Estas matrices soncomunes en la resolución de ecuaciones diferenciales de problemasde Ingeniería.
• En general para el primer grupo se aplican métodos directos para susolución mientras que para el segundo grupo se hace uso demétodos indirectos (iterativos).
Ing. Juan Carlos Sabido Alcántara
Sistemas de Ecuaciones Lineales• Conceptos de matriz diagonal, triangular superior y triangular
inferior.
• Matriz diagonal: Es una matriz que solo tiene elementos diferentes de cero en su diagonal principal
•
• Y la solución se obtiene directamente:
Ing. Juan Carlos Sabido Alcántara
nn
nn
d
d
d
d
DA
00
0
0
00
1,1
22
11
nid
bx
ii
i
i ,...,1
Sistemas de Ecuaciones Lineales• Conceptos de matriz diagonal, triangular superior y triangular
inferior.
• Existe solución si todos los elementos de la diagonal son no nulos, existenalgunos casos particulares de la matriz diagonal en los que no solo setienen elementos diferentes de cero en la diagonal principal, si no quetambién se presentan diagonales con elementos no nulos en otras partesde la matriz, por ejemplo:
• Matriz Tridiagonal.
Ing. Juan Carlos Sabido Alcántara
nmmn
mn
ba
c
ba
cba
cba
cb
1,
,1
4443
343332
232221
1211
0000
0
00
00
00
0
0000
Sistemas de Ecuaciones Lineales• Conceptos de matriz diagonal, triangular superior y triangular
inferior.
• Matriz Pentagonal.
• Matriz Heptagonal.
Ing. Juan Carlos Sabido Alcántara
nmmnmn
mn
mn
bad
c
d
dbad
cba
ecba
ecb
1,4,
,1
52
,4444341
343332
25232221
141211
000
00
00
00
00
00
000
nmmnmnmn
mn
mn
mn
badf
cf
d
dbad
cba
gecba
gecb
1,4,5,
,161
52
,4444341
343332
,525232221
16141211
00
0
00
00
000
00
000
Sistemas de Ecuaciones Lineales• Conceptos de matriz diagonal, triangular superior y triangular
inferior.
• Matriz triangular superior: Es una matriz que tiene elementospor arriba de la diagonal principal diferentes a cero, y todos losque están por debajo iguales a cero. Suele denominarse a estamatriz como U.
•
Ing. Juan Carlos Sabido Alcántara
nn
nnnn
n
u
uu
u
uuu
UA
00
0
,11,1
22
11211
Sistemas de Ecuaciones Lineales• Conceptos de matriz diagonal, triangular superior y triangular
inferior.
• Matriz triangular superior: En este caso la solución de la última ecuación estrivial . Una vez conocido , la penúltima ecuación (la n-1) sólo tiene unaincógnita que se deduce de forma sencilla. Conocidos ahora y , se pasa ala ecuación anterior (la n-2) y se resuelve para su única incógnita .Retrocediendo progresivamente se obtiene el algoritmo de sustitución haciaatrás que se escribe de la siguiente forma:
•
Ing. Juan Carlos Sabido Alcántara
nn
nn u
bx
nx
nx 1nx
2nx
ii
n
ij
jiji
i
nn
nn
u
xub
x
ub
x
1
)1....(1,...,2,1 nni
Sistemas de Ecuaciones Lineales• Conceptos de matriz diagonal, triangular superior y triangular
inferior.• Matriz triangular inferior: Es una matriz que tiene elementos por abajo de la diagonal principal
diferentes a cero, y todos los que están por arriba iguales a cero. Suele denominarse a estamatriz como L.
• De manera similar al anterior, existe un algoritmo, este se conoce como sustitución haciadelante:
• Los algoritmos de sustitución hacia delante y hacia atrás son de gran importancia para losmétodos de Eliminación.
Ing. Juan Carlos Sabido Alcántara
nnnnn
nn
lll
l
ll
l
LA
1,1
1,1
2221
11
0
00
ii
i
j
jiji
il
xlb
x
lb
x
1
1
11
11
)2...(,...,2 ni
Sistemas de Ecuaciones Lineales• Método de eliminación Gaussiana.
• Este método consiste en transformar la matriz de coeficientes A delSEL a una matriz U del tipo Triangular Superior haciendo uso detransformaciones elementales que permitan realizar esto.
• Dichas transformaciones incluyen:– Intercambio de un renglón por otro.
– Suma o resta entre dos renglones elemento a elemento.
– Multiplicación de los elementos de un renglón por un escalar, este escalardebe ser necesariamente diferente a cero.
Ing. Juan Carlos Sabido Alcántara
Sistemas de Ecuaciones Lineales• Método de eliminación Gaussiana.
• Durante la transformación del sistema original A al sistemaequivalente U las operaciones se realizan sobre la matriz A y almismo tiempo sobre él termino independiente b, quedando unsistema equivalente a:
Ing. Juan Carlos Sabido Alcántara
1
'
3
'
2
1
3
2
1
1
''
3
''
33
'
2
'
23
'
22
1332211
00
0
n
nn
n
nn
n
n
n
b
b
b
b
x
x
x
x
a
aa
aaa
aaaa
Sistemas de Ecuaciones Lineales• Método de eliminación Gaussiana.
• Algoritmo.
• El primer renglón se multiplica por y se resta al segundo renglónpara eliminar el primer elemento de este, del mismo modo se hacecon el primer elemento de los demás renglones, restando el primerrenglón multiplicado por , es importante recordar que tambiénse debe afectar al vector , donde:
Ing. Juan Carlos Sabido Alcántara
1121 aa
111 aai
b
( )
( )
k
ikik k
kk
am
a 1k k k
ij ij ik kja a m a 1,3,4, ,i k n 1,2,3, , 1j k n
Sistemas de Ecuaciones Lineales• Método de eliminación Gaussiana.
• Algoritmo.
• Esto reduciría el sistema a una matriz diagonal superior U, por loque se utiliza la sustitución hacia atrás dada por la ecuación 1:
Ing. Juan Carlos Sabido Alcántara
( )
( )
k
ikik k
kk
am
a 1k k k
ij ij ik kja a m a 1,3,4, ,i k n 1,2,3, , 1j k n
ii
n
ij
jiji
i
nn
nn
u
xub
x
ub
x
1
)1....(1,...,2,1 nni
Sistemas de Ecuaciones Lineales• Método de eliminación Gaussiana.
• Algoritmo.
• Este algoritmo resulta confuso al realizar la prueba de escritorio, yaque se puede observar fácilmente que en realidad no se obtieneuna matriz diagonal U, la razón es que el algoritmo no convierte enceros los elementos por debajo de la diagonal principal,simplemente se ignoran dichos elementos para obtener los valoresde las incógnitas del SEL, sin embargo su efectividad estácomprobada pero no es el mejor método para utilizar en SELrobustos.
Ing. Juan Carlos Sabido Alcántara
( )
( )
k
ikik k
kk
am
a 1k k k
ij ij ik kja a m a 1,3,4, ,i k n 1,2,3, , 1j k n
Sistemas de Ecuaciones Lineales• Método de eliminación Gaussiana.
• Tarea.
• Resolver el siguiente SEL realizando la prueba de escritorio delalgoritmo de eliminación Gaussiana:
•
𝟐𝑿𝟏 + 𝑿𝟐 − 𝑿𝟑 + 𝑿𝟒 = 𝟖𝑿𝟐 + 𝑿𝟑 − 𝑿𝟒 = 𝟒
𝟐𝑿𝟐 + 𝑿𝟑 − 𝑿𝟒 = 𝟐𝑿𝟏 − 𝑿𝟐 + 𝟐𝑿𝟒 = −𝟐
Ing. Juan Carlos Sabido Alcántara
( )
( )
k
ikik k
kk
am
a 1k k k
ij ij ik kja a m a 1,3,4, ,i k n 1,2,3, , 1j k n
Sistemas de Ecuaciones Lineales• Método de descomposición LU.
• Una matriz A puede factorizarse como el producto de una matriztriangular inferior L y otra triangular superior U:
• La descomposición de A seria en función de L y U de la siguientemanera:
Ing. Juan Carlos Sabido Alcántara
ULA *
nnnn lll
ll
l
L
21
2221
11
0
00
nn
n
n
u
uu
uuu
U
00
0 222
11211
Sistemas de Ecuaciones Lineales• Método de descomposición LU.
• Para realizar esta factorización existen tres esquemas:– Esquema Doolittle (mostrado en el ejemplo) Este esquema considera
– Esquema Crout. Este esquema considera
– Esquema Choleski. Este esquema considera
• De lo visto con eliminación Gaussiana podemos fácilmente concluirque LU no es un método sencillo y que su utilización puededemandar muchos recursos de la computadora para funcionar.
Ing. Juan Carlos Sabido Alcántara
1, iil
1, iiu
i,ii,i ul
•
nn
n
n
nnnnan
n
n
u
uu
uuu
ll
l
aaa
aaa
aaa
00
0
1
0
1
001
222
11211
21
21
21
22221
11211
Sistemas de Ecuaciones Lineales• Método de Jacobi.
• El método de Jacobi es un método iterativo, y cuando converge seaproxima a la solución en cada iteración partiendo de un valor inicial,considerando la ecuación:
…(1)
• Se sustituye la matriz A por donde U es una matriz diagonalsuperior y R es otra matriz que contiene ceros en la diagonal principal ylos restantes elementos de A, en sus demás elementos.
en donde
Ing. Juan Carlos Sabido Alcántara
bxA
RUA
•
0
0
0
100
10
1
21
221
112
2
112
21
22221
11211
an
n
n
n
n
nnan
n
n
rr
rr
rr
u
uu
aaa
aaa
aaa
jiji ra ,,
Sistemas de Ecuaciones Lineales• Método de Jacobi.
• Sustituyendo en (1) se tiene:
• Premultiplicando por
• Ecuación que se maneja como fórmula de recurrencia:
• Esto quiere decir que del sistema (1) se despeje de la primeraecuación, de la segunda, y así sucesivamente.
Ing. Juan Carlos Sabido Alcántara
xRbxD
bxRxD
bxRD
1D
xRDbDx 11
kkxRDbDx 111
,...2,1,0k
1x
2x
Sistemas de Ecuaciones Lineales• Método de Jacobi: Algoritmo.
• Despejar cada una de las incógnitas siguiendo el patrón mencionadoanteriormente se tiene:
…(2)
Ing. Juan Carlos Sabido Alcántara
,2,1,0
1
1
1
1
11,22,11,
,
1
,322,311,33
3,3
1
3
,233,211,22
2,2
1
2
,133,122,11
1,1
1
1
k
xaxaxaba
x
xaxaxaba
x
xaxaxaba
x
xaxaxaba
x
k
nnn
k
n
k
nn
nn
k
n
k
nn
kkk
k
nn
kkk
k
nn
kkk
Sistemas de Ecuaciones Lineales• Método de Jacobi: Algoritmo.
• Partiendo de una primera aproximación se tiene:
…(3)
• Estos valores se sustituirán en los segundos miembros de lasecuaciones del sistema (2) para obtener la siguiente aproximación:
…(4)
• Así la siguiente aproximación se obtiene sustituyendo :
…(5)
Ing. Juan Carlos Sabido Alcántara
Tnxxxxx 00
3
0
2
0
1
0,,,,
Tnxxxxx 11
3
1
2
1
1
1,,,,
1x
Tnxxxxx 22
3
2
2
2
1
2,,,,
Sistemas de Ecuaciones Lineales• Método de Jacobi: Algoritmo.
• Como ya se mencionó, este método al ser iterativo necesita de unvalor inicial, este se obtiene de sustituir el vector enlos segundos miembros de las ecuaciones del sistema (2),obteniendo:
Ing. Juan Carlos Sabido Alcántara
Tx 0,,0,0,00
T
nn
n
a
b
a
b
a
b
a
bx
,3,3
3
2,2
2
1,1
1 ,,,,
Sistemas de Ecuaciones Lineales• Método de Jacobi: Ejemplo.
• Resolver el siguiente SEL por medio del método de Jacobi.
• Despejando de la primera ecuación, de la segunda y de la tercera, seobtiene:
Ing. Juan Carlos Sabido Alcántara
236
3028
2226
321
321
321
xxx
xxx
xxx
1x2x 3x
213
312
321
236
1
2308
1
2226
1
xxx
xxx
xxx
Sistemas de Ecuaciones Lineales• Método de Jacobi: Ejemplo.
• Escribiendo este sistema en la forma (2):
Ing. Juan Carlos Sabido Alcántara
213
312
321
236
1
2308
1
2226
1
xxx
xxx
xxx
,2,1,0
236
1
2308
1
2226
1
21
1
3
31
1
2
32
1
1
k
xxx
xxx
xxx
kkk
kkk
kkk
Sistemas de Ecuaciones Lineales• Método de Jacobi: Ejemplo.
• Entonces el vector inicial es , sustituyendo este primer vectorinicial en las ecuaciones anteriores se tiene:
Ing. Juan Carlos Sabido Alcántara
,2,1,0
236
1
2308
1
2226
1
21
1
3
31
1
2
32
1
1
k
xxx
xxx
xxx
kkk
kkk
kkk
T
x
6
23
8
30
6
220
847.38
30
6
2223
6
123
6
1
250.36
232
6
2230
8
1230
8
1
778.16
23
8
30222
6
1222
6
1
0
2
0
1
1
3
0
3
0
1
1
2
0
3
0
2
1
1
xxx
xxx
xxx
Sistemas de Ecuaciones Lineales• Método de Jacobi: Ejemplo.
• Entonces para ; , continuando con el mismoprocedimiento:
• Entonces para ; , continuando con el mismoprocedimiento se obtienen los siguientes vectores:
Ing. Juan Carlos Sabido Alcántara
0k Tx 847.3250.3778.11
079.4250.3778.1236
123
6
1
011.3847.32778.1308
1230
8
1
942.1847.3250.32226
1222
6
1
1
2
1
1
2
3
1
3
1
1
2
2
1
3
1
2
2
1
xxx
xxx
xxx
1k Tx 4079.3011.3942.12
2k ; Tx 012.4973.2989.13
3k ; Tx 998.3995.2007.24
4k ; Tx 998.3001.3002.25
5k ; Tx 000.4001.3000.26
6k ; Tx 000.4000.3000.27
Sistemas de Ecuaciones Lineales• Método de Jacobi: Ejemplo.
• Por lo que la solución del sistema es:
• El número de iteraciones aumentara o disminuirá dependiendo de la toleranciafijada.
Ing. Juan Carlos Sabido Alcántara
000.4
000.3
000.2
3
2
1
x
x
x
Sistemas de Ecuaciones Lineales• Método de Gauss – Seidel.
• El método de Gauss – Seidel es prácticamente el mismo que el de Jacobi, ladiferencia radica en que este cuando converge se aproxima más rápido a lasolución.
• Algoritmo. La rápida convergencia se debe a que la componente una vezque fue calculada se utiliza inmediatamente dentro de la misma iteración, esdecir:
Ing. Juan Carlos Sabido Alcántara
1k
ix
,2,1,0
1
1
1
1
1
11,
1
22,
1
11,
,
1
,3
1
22,3
1
11,33
3,3
1
3
,233,2
1
11,22
2,2
1
2
,133,122,11
1,1
1
1
k
xaxaxaba
x
xaxaxaba
x
xaxaxaba
x
xaxaxaba
x
k
nnn
k
n
k
nn
nn
k
n
k
nn
kkk
k
nn
kkk
k
nn
kkk
Sistemas de Ecuaciones Lineales• Método de Gauss – Seidel.
• Tarea #. Resolver el siguiente SEL por medio del método de Gauss – Seidelrealizando la prueba de escritorio del algoritmo.
• Tarea #. Leer el artículo “How to Build Reliable Code” y hacer un brevecomentario del mismo.
Ing. Juan Carlos Sabido Alcántara
236
3028
2226
321
321
321
xxx
xxx
xxx
Sistemas de Ecuaciones Lineales• Convergencia del Método de Jacobi y Gauss - Seidel.
• Ambos métodos tienen como principal desventaja de no siempreconverger a la solución del sistema, o en algunas ocasiones lo hacenpero de manera muy lenta.
• Para poder aplicar estos métodos los elementos de la diagonalprincipal de la matriz A de coeficientes deben ser diferentes de cero.
• Existe una condición necesaria para que estos converjan y consiste enque dichos elementos de la diagonal principal además de serdiferentes de cero sean mayores en valor absoluto que la suma de losdemás elementos del renglón correspondiente.
• Cuando esta condición se cumple garantiza la convergencia, pero de nocumplirse no se puede afirmar la no convergencia.
Ing. Juan Carlos Sabido Alcántara
Sistemas de Ecuaciones Lineales• Método de Thomas.
• El método de Thomas es un algoritmo utilizado para dar solución a sistemas de ecuaciones lineales que tienen la forma tridiagonal:
Ing. Juan Carlos Sabido Alcántara
1 1 1 1
2 2 2 2 2
3 3 3 3 3
4 4 4 4 4
1 1 1 1 1n n n n n
n n n n
b c x d
a b c x d
a b c x d
a b c x d
a b c x d
a b x d
Sistemas de Ecuaciones Lineales• Método de Thomas.
• Este tipo de sistemas se tiene cuando se aproxima la ecuación dedifusividad por medio de diferencias finitas, para un solo fluido y enuna dirección.
• La ventaja es que no es necesario almacenar toda la matriz, solo loselementos que se encuentran en las tres diagonales, es decir, , enforma de vectores, esto permite el ahorro de recursoscomputacionales además de tiempo en el cálculo.
Ing. Juan Carlos Sabido Alcántara
Sistemas de Ecuaciones Lineales• Método de Thomas.
• Algoritmo.
• Para i=1 se tiene:
y
• Para i=2,3,…,n-1
• Para i=2,3,…,n
• Realizando sustitución hacia atrás, para i=n
• Para n-1,n-2,n-3,…,2,1
Ing. Juan Carlos Sabido Alcántara
11
1
cw
b 1
1
1
dg
b 1 1 1 1
2 2 2 2 2
3 3 3 3 3
4 4 4 4 4
1 1 1 1 1n n n n n
n n n n
b c x d
a b c x d
a b c x d
a b c x d
a b c x d
a b x d
1
ii
i i i
cw
b a w
1
1
i i ii
i i i
d a gg
b a w
n nx g
1i i i ix g w x
Sistemas de Ecuaciones Lineales• Método de Thomas.
• Tarea. Resolver los siguientes SEL tridiagonales:
•
Ing. Juan Carlos Sabido Alcántara
i a(i) b(i) c(i) d(i)
1 0.000000000E+00 1.000000000E+00 0.000000000E+00 0.000000000E+00
2 4.708315231E+00 -3.523217251E+01 4.708315231E+00 -1.839327347E+08
3 4.708315231E+00 -3.523217251E+01 4.708315231E+00 -2.106029904E+08
4 4.708315231E+00 -3.523217251E+01 4.708315231E+00 -2.133265227E+08
5 4.708315231E+00 -3.523217251E+01 4.708315231E+00 -2.135683922E+08
6 4.708315231E+00 -3.523217251E+01 4.708315231E+00 -2.135885091E+08
7 4.708315231E+00 -3.523217251E+01 4.708315231E+00 -2.135901281E+08
8 4.708315231E+00 -3.523217251E+01 4.708315231E+00 -2.135902562E+08
9 4.708315231E+00 -3.523217251E+01 4.708315231E+00 -2.135902662E+08
10 0.000000000E+00 1.000000000E+00 0.000000000E+00 8.273708400E+06
i a(i) b(i) c(i) d(i)
1 0.000000000E+00 1.000000000E+00 0.000000000E+00 0.000000000E+00
2 3.766652185E+01 -1.011485857E+02 3.766652185E+01 -1.036264083E+08
3 3.766652185E+01 -1.011485857E+02 3.766652185E+01 -1.658814244E+08
4 3.766652185E+01 -1.011485857E+02 3.766652185E+01 -1.949159631E+08
5 3.766652185E+01 -1.011485857E+02 3.766652185E+01 -2.067261576E+08
6 3.766652185E+01 -1.011485857E+02 3.766652185E+01 -2.111646327E+08
7 3.766652185E+01 -1.011485857E+02 3.766652185E+01 -2.127551461E+08
8 3.766652185E+01 -1.011485857E+02 3.766652185E+01 -2.133100921E+08
9 3.766652185E+01 -1.011485857E+02 3.766652185E+01 -2.135055896E+08
10 0.000000000E+00 1.000000000E+00 0.000000000E+00 8.273708400E+06
Sistemas de Ecuaciones Lineales• Método de Thomas.
• Tarea. Realizar los cálculos en Excel haciendo uso del algoritmo de Thomas, losresultados obtenidos representan la caída de presión en un intervalo de tiempoen un yacimiento, considerando una sola dimensión y propiedadeshomogéneas dentro del mismo, además de un solo tipo de fluido, a lo largo dediez bloques. Graficar los resultados P vs i y hacer un breve análisis de lo quepuede estar pasando.
•
Ing. Juan Carlos Sabido Alcántara
0.00
200.00
400.00
600.00
800.00
1000.00
1200.00
1400.00
0 2 4 6 8 10 12
Pre
si{
on
i
Presion vs i
Caso1 Pvsi Caso 2 Pvsi
GRACIAS
Ing. Juan Carlos Sabido Alcántara
Ingeniero Petrolero
Facultad de Ingeniería UNAM