EcuacionesAlgebraicas2014

Vista previa del material en texto

Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
Cálculo Avanzado-Fundamentos para el
Análisis de Señales
Docentes: Cavalieri Federico - Contini Liliana
Ayudantes: Fabio Tibaldo - Maciel Martı́n
Ecuaciones Algebraicas
September 23, 2014
mailto:cavafede@gmail.com
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
Motivación
Nos proponemos determinar los valores de x1, x2, ...xn que en forma
simultánea satisfacen un sistema de ecuaciones
f1(x1, x2, . . . , xn) = 0
f2(x1, x2, . . . , xn) = 0
f3(x1, x2, . . . , xn) = 0
...
...
fn(x1, x2, . . . , xn) = 0
(1)
En particular, se resolverán sistemas de ecuaciones algebraicas
lineales, que tienen la forma de
a11x1 + a12x2 + . . . + a1nxn = b1
a21x1 + a22x2 + . . . + a2nxn = b2
...
...
an1x1 + an2x2 + . . . + annxn = bn
(2)
donde las a son constantes, las b son los términos independientes
constantes y n el número de ecuaciones.
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
Motivación
Si son pocas ecuaciones n ≤ 3, el sistema se puede resolver con
técnicas simples como las estudiadas en los cursos de álgebra. Sin
embargo, con cuatro o más ecuaciones, la solución se vuelve laboriosa.
Históricamente, la incapacidad para resolver a mano sistemas de
ecuaciones grandes limitaba el alcance de resolución de problemas de
aplicación en ingenierı́a.
El surgimiento de las computadoras
hizo posible resolver grandes sistemas de ecuaciones algebraicas
simultáneas. Ası́ se pueden enfrentar ejemplos y problemas más
complicados. Además, se cuenta con más tiempo para usar
habilidades creativas, ya que se podrá mayor énfasis en la
formulación del problema y en la interpretación de la solución.
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
¿Te imaginás resolver este reticulado a
mano?
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
¿y este circuito?
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
Notación
Matriz. Es un arreglo rectangular de elementos representado por un
solo sı́mbolo.
[A] =

a11 a12 a13 .... a1m
a21 a22 a23 .... a1m
...
...
...
. . .
...
an1 an2 an3 .... anm
 (3)
Matriz renglón.
[B] = [b1 b2 .... bm] (4)
Vector columna. Para distinguir una vector columna de otras
matrices se utilizarán las llaves.
{C} =

c1
c2
...
cn
 (5)
Notar que: {B} = [B]T
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
Tipos de Matrices
Matriz Diagonal. Es un matriz cuadrada donde tiene elementos solo
en la diagonal
[D] =

a11 0 0 . . . 0
0 a22 0 . . . 0
...
...
...
. . .
...
0 0 0 . . . amm
 (6)
Matriz Identidad. Es un matriz diagonal donde todos los elementos
de la diagonal son iguales a 1.
[I] =

1 0 0 . . . 0
0 1 0 . . . 0
...
...
...
. . .
...
0 0 0 . . . 1
 (7)
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
Tipos de Matrices
Matriz Triangular Superior. Upper. Todos los elementos por debajo
de la diagonal principal son cero.
[U ] =

a11 a12 a13 . . . a1m
0 a22 a23 . . . a2m
...
...
...
. . .
...
0 0 0 . . . amm
 (8)
Matriz Triangular Inferior. Lower. Todos los elementos por debajo
de la diagonal principal son cero.
[L] =

a11 0 0 . . . 0
a21 a22 0 . . . 0
...
...
...
. . .
...
an1 an2 an3 . . . ann
 (9)
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
Operaciones. Producto: Matriz-Vector
Producto: [A] · {x} = {b} donde A � Rm×n y b � Rn.
La operación está definida como:
bi =
n∑
j=1
Aijxj (10)
La matriz [A] se puede escribir como
[A] = [{A1}|{A2}|...{An}] (11)
donde {An} es el enésimo vector columna de [A]. Por tanto
[A] ·{x} = [{A1}|{A2}|...{An}] ·

x1
x2
...
xn
 = x1{A1}+x2{A2}+ ...xn{An}
es decir, el vector resultante {b} resulta de una combinación lineal de
los vectores {An} y donde los coeficientes son los elementos
(escalares) del vector {x}
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
Operaciones. Producto: Matriz-Matriz
Producto: [A] · [B] = [C] donde A � Rm×l, B � Rl×n y C � Rm×n.
La operación está definida como:
Cij =
l∑
k=1
AikAkj (12)
En forma análoga a lo visto anteriormente, el producto puede
escribirse como
[{A1}|{A2}|...{Al}] · [{B1}|{B2}|...{Bn}] = [{C1}|{C2}|...{Cn}] (13)
su k ésima columna quedará definida como
{Ck} = [A] · {Bk} (14)
El producto de dos matrices es tal que su k ésima columna se
obtiene como una combinación lineal de las columnas de A, siendo
los coeficientes de la combinación lineal, los elemento de la k ésima
columna de B.
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
Dado el siguiente Sistema de Ecuaciones Algebraicas Lineales
(SEAL)
E1 : a11x1 + a12x2 + . . . + a1nxn = b1
E2 : a21x1 + a22x2 + . . . + a2nxn = b2
...
...
En : an1x1 + an2x2 + . . . + annxn = bn
(15)
puede representarse matricialmente como: [A]{x} = {b}, donde
{x} es un vector que contiene n incógnitas;
[A] es una matriz cuadrada de n× n con coeficientes constantes del
sistema;
{b} un vector con los términos independientes;
[A]{x} = {b} =⇒
a11 a12 a13 a14
a21 a22 a23 a24
a31 a32 a33 a34
a41 a42 a43 a44
 ·

x1
x2
x3
x4
 =

b1
b2
b3
b4
 (16)
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
La resolución de un sistema de ecuaciones lineales algebraicas,
puede realizarse de diferentes maneras.
Métodos directos. Son métodos que, en un número finito de
operaciones se obtiene la solución exacta. (Con precisión de épsilon de
máquina).
Métodos iterativos. Son métodos que generan una sucesión de
aproximaciones que converge a la solución del sistema {x} = [A]−1{b}
Estacionarios.
No estacionarios.
En este curso se estudiarán ambos métodos.
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
METODOS DIRECTOS
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
Sistemas equivalentes:
dos sistemas [A]{x} = {b} y [B]{x} = {d} se dicen equivalentes si
tienen la misma solución x.
Se puede demostrar que realizando una serie de operaciones
elementales sobre un SEAL se obtiene otro equivalente.
Operaciones elementales:
Intercambio de 2 ecuaciones: Ei ↔ Ej
Multiplicación de una ec. por un escalar ( 6= 0): λEi → Ei
Sumar a una ec. un multiplo de otra: Ei + λEj → Ei
Hay métodos que se basan en transformar un SEAL mediante
operaciones elementales de modo de obtener un sistema
equivalente, más fácil de resolver.
Sistemas más fáciles para resolver.
Sistemas con matrices diagonales.
Sistemas con matrices triangulares.
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
Matriz Diagonal
Dado el siguiente SEAL
a11 0 0 . . . 0
0 a22 0 . . . 0
...
...
...
. . .
...
0 0 0 . . . ann
 ·

x1
x2
...
xn
 =

b1
b2
...
bn
 (17)
la solución será simplemente
{x} =

b1/a11
b2/a22
...
bn/ann
 (18)
En forma general
xi =
bi
aii
(19)
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
Matriz Diagonal Superior [U ]
Dado el siguiente SEAL
a11 a12 a13 a14
0 a22 a23 a24
0 0 a33 a34
0 0 0 a44
 ·

x1
x2
x3
x4
 =

b1
b2
b3
b4
 (20)
x4 =
b4
a44
→ x3 =
b3 − a34x4
a33
→ x2 =
b2 − a23x3 − a24x4
a22
→ x1 =
b1 − a12x2 − a13x3 − a14x4
a11
(21)
o bien en forma general (algoritmo de sustitución hacia atrás)
xi =
bi −
∑n
j=1+i aijxj
aii
i = n− 1 . . . 1 (22)
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
Matriz Diagonal Inferior [L]
De manera similar
a11 0 0 0
a21 a22 0 0
a31 a23 a33 0
a41 a24 a34 a44
 ·

x1
x2
x3
x4
 =

b1
b2
b3
b4
(23)
Sustitución hacia adelante
xi =
bi −
∑i−1
j=1 aijxj
aii
j = 2 . . . n (24)
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
Eliminación de Gauss
Un método basado en esta transformación del sistema de ecuaciones
es el método de Eliminación de Gauss.
Se basa en realizar una serie de transformaciones sobre el sistema de
modo de obtener un sistema equivalente, con matriz triangular.
En un sistema de n ecuaciones se efectúan n− 1 pasos de eliminación.
La matriz [A] del sistema, va siendo transformada en matrices A(k) en
cada paso k de la eliminación.
El vector de términos independientes va transformándose también en
sucesivos vectores b(k).
Se introducirá el método a través de un ejemplo sencillo.
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
E1
E2
E3
E4

6 −2 2 4
12 −8 6 10
3 −13 9 3
−6 4 1 18
 ·

x1
x2
x3
x4
 =

12
34
27
−38
 (25)
Primer paso
E1
E2 − 2E1
E3 − 1/2E1
E4 − (−1)E1

6 −2 2 4
0 −4 2 2
0 −12 8 1
0 2 3 22
 ·

x1
x2
x3
x4
 =

12
10
21
−26
 (26)
Segundo paso
E1
E2
E3 − 3E2
E4 − (−1/2)E2

6 −2 2 4
0 −4 2 2
0 0 2 −5
0 0 4 23
 ·

x1
x2
x3
x4
 =

12
10
−9
−21
 (27)
Tercer paso
E1
E2
E3
E4 − (2)E3

6 −2 2 4
0 −4 2 2
0 0 2 −5
0 0 0 33
 ·

x1
x2
x3
x4
 =

12
10
−9
−3
 (28)
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
Algoritmo de Gauss. Eliminación hacia
adelante
i = 1
i = 2
i = 3 = k
i = 4
i = 5

a11 a12 a13 a14 a15
a21 a22 a23 a24 a25
a31 a32 a33 a34 a35
a41 a42 a43 a44 a45
a51 a52 a53 a54 a55
 (29)
j = 1 2 k = 3 4 5
ak+1ij =

akij i ≤ k j ≤ n No se modifica
akij − (
akik
akkk
)akkj i ≥ k + 1 j ≥ k + 1 parte activa
0 i ≥ k + 1 j ≤ k
(30)
bk+1i =
{
bki i ≤ k j ≤ n No se modifica
bki − (
akik
akkk
)bkk i ≥ k + 1 j ≥ k + 1 parte activa
(31)
Luego se resuelve por sustitución hacia atrás.
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
Factorización LU
Un método que presenta ventajas comparado con el método de
eliminación Gaussiana es el LU. El procedimiento LU transforma una
matriz [A] en un producto de dos matrices
[A] = [L][U ] (32)
donde [L] es una matriz triangular inferior y [U ] es una matriz
triangular superior. Con [A] = [L][U ], una ecuación del tipo,
[A]{x} = {b} puede escribirse como: [L][U ]{x} = {b} (33)
Si se define
{y} = [U ]{x} → [L]{y} = {b} (34)
donde puedo conocer {y} por sustitución hacia atrás. Luego, una
vez conocido {y},
[U ]{x} = {y} (35)
puedo obtener {x} por sustitución hacia adelante.
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
¿Cómo se obtienen las matrices [L] y [U ]?
El sistema original es
[A]{x} = {b} [A] = [L][U ] (36)
Luego, pre-multiplicando a ambos miembros por [L]−1
[L]−1[A]{x} = [L]−1{b} → [U ]{x} = [L]−1{b} (37)
Por lo tanto, cuando se pre-multiplica a la matriz [A] por [L]−1 se
obtiene una matriz [U ]. En otras palabra,[L]−1 es una matriz de
transformación.
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
Obtención de la matriz [U ]
Supongamos que tenemos una matriz [A],
[A] =
[
X X X X
X X X X
X X X X
X X X X
]
y le aplicamos una matriz de transformación, tal que,
[L1]
−1 [A] =
[
X X X X
0 + + +
0 + + +
0 + + +
]
→ [L2]−1[L1]−1[A] =
[
X X X X
0 + + +
0 0 ∆ ∆
0 0 ∆ ∆
]
[L3]−1[L2]−1[L1]−1[A] =
[
X X X X
0 + + +
0 0 ∆ ∆
0 0 0 �
]
[Lk]−1: Debe dejar intactas las primeras k filas y las primeras
k − 1 columnas. A su vez tiene que dejar ceros bajo la diagonal
en la k-ésima columna
[Lk]−1[Lk−1]−1 . . . [L1]−1[A] = [U ] → [L]−1[A] = [U ]
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
Obtención de la matriz [L]
Se demostró que
[Lk]−1[Lk−1]−1 . . . [L1]−1[A] = [U ]
Luego,
[L]−1 = [Lk]−1[Lk−1]−1 . . . [L1]−1
finalmente
[L] = [L1] . . . [Lk−1][Lk]
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
Generalización
k
k

0
[Ik−1,k−1]
... [0]
0
0 . . . 0 1 0 . . . 0
µk+1
[0]
... [Im−k,m−k]
µm

·

α1
[U ]
... [A13]
αk−1
0 . . . 0 αk [A23]
αk+1
[0]
... [A33]
αm

=

α1
[U ]
... [A13]
αk−1
0 . . . 0 αk [A23]
0
[0]
...
[
Ã33
]
0

Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
miremos la columna k de la matriz [A]. Se quiere obtener 0 en las
filas αk+1...αm de la column k de la matriz [A] usando [Lk]−1,
[Lk]−1

α1
...
αk−1
αk
αk+1
...
αm

→

α1
...
αk−1
αk
0
...
0

entonces
αk
 µk+1...
µm
 + [Im−k,m−k]
 αk+1...
αm
 =
 0...
0

finalmente  µk+1...
µm
 = −1
αk
 αk+1...
αm

Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
La matriz de transformación y la matriz triangular superior [U ]
resultan
[L]−1 =

1 0 . . . . . . 0
µ11 1 . . . . . .
...
µ12 µ
2
2 1 . . .
...
...
...
...
. . .
...
µ1m µ
2
m µ
3
m . . . 1

→ [U ] = [L]−1[A]
siendo [U ] igual a la obtenida por la eliminación de Gauss. La
matriz tirangular inferior [L] es,
[L] =

1 0 . . . . . . 0
−µ11 1 . . . . . .
...
−µ12 −µ
2
2 1 . . .
...
...
...
...
. . .
...
−µ1m −µ
2
m −µ
3
m . . . 1
 =

1 0 . . . . . . 0
a121/a
1
11 1 . . . . . .
...
a131/a
1
11 a
2
32/a
2
22 1 . . .
...
...
...
...
. . .
...
a1m1/a
1
11 a
2
m2/a
2
22 a
3
m3/a
3
33 . . . 1

donde los coeficientes akij/a
k
kk se obtienen de la eliminación de
Gauss.
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
Ejemplo
[A] =
[
6 −2 2 4
12 −8 6 10
3 −13 9 3
−6 4 1 18
]
→ [L1]−1 =
[
1 0 0 0
−12/6 1 0 0
−3/6 0 1 0
6/6 0 0 1
]
[L1]−1[A] =
[
6 −2 2 4
0 −4 2 2
0 −12 8 1
0 2 3 22
]
→ [L2]−1 =
[
1 0 0 0
0 1 0 0
0 −12/4 1 0
0 2/4 0 1
]
[L2]−1[L1]−1[A] =
[
6 −2 2 4
0 −4 2 2
0 0 2 −5
0 0 4 23
]
→ [L3]−1 =
[
1 0 0 0
0 1 0 0
0 0 1 0
0 0 −4/2 1
]
[U ] = [L3]−1[L2]−1[L1]−1[A] =
[
6 −2 2 4
0 −4 2 2
0 0 2 −5
0 0 0 33
]
→ [L]−1 = [L3]−1[L2]−1[L1]−1 → [L] = [L1][L2][L3] =
[
1 0 0 0
2 1 0 0
1/2 3 1 0
−1 −1/2 2 1
]
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
[L] =

1 0 0 0
2 1 0 0
1/2 3 1 0
−1 −1/2 2 1

Notar que los elementos de la matriz son los factores que se
obtuvieron de la eliminación de Gauss: Ecs.(26, 27, 28), estos son
los akij/a
k
kk.
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
Ventajas del LU comparado a la eliminación
Gaussiana.
Si sumamos todas la operaciones del método LU, nos dará que son
las mismas que las utilizadas por el método de eliminación
Gaussiana. Pero, una vez calculadas las matrices L y U, el vector {b}
no se re-calcula y entonces puedo definir diferentes vectores {b} con
las mismas matrices L y U, y entonces en ese caso, la cantidad de
operaciones se reduce pues únicamente se utiliza sustitución hacia
adelante y hacia atrás.
En otras palabras, en el caso de eliminación Gaussiana, si quiero
definir un nuevo problema con la misma matriz [A] y con un diferente
vector {b}, el proceso se inicia desde cero. En cambio con el método
LU, las matrices L y U se calculan una única vez.
{y} = [U ]{x} → [L]{y} = {b} → {y} [U ]{x} = {y} → {x} (38)
Los métodos de eliminación Gaussiana y LU tienen un serio
inconveniente ¿Cuál es?
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
METODOS ITERATIVOS
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
1 En curso se estudiarán los métodos iterativos de Jacobi, Gauss-Seidel
y SOR.
2 Los métodos iterativos se usan rara vez para resolver sistemas
lineales de pequeña dimensión, pues el tiempo necesario para
conseguir una exactitud satisfactoriaes mayor que el de los métodos
directos.
3 En el caso de sistemas lineales de grandes dimensiones resultan
eficientes.
4 Los métodos iterativos estacionarios no buscan transformar las
matrices. Tienen que ser diagonal dominante.
5 Se los utiliza cuando la matriz es rala es decir, tiene muchos
coeficientes nulos. En estos casos trabajar con los métodos directos
se vuelve muy poco práctico, pues debemos hacer muchas
operaciones con coeficientes nulos y, lo que es peor, muchas veces
transformar un coeficiente nulo en otro no nulo, incorporando un error
que antes no existı́a.
6 Los métodos iterativos se los utiliza en los análisis de circuitos,
análisis estructural, entre otros.
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
Matriz rala de gran dimensión
El método de los elementos finitos (ver Unidad XII) genera matrices
ralas de gran dimensión.
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
Un método iterativo que resuelve un sistema lineal del tipo [A]{x} = {c}
comienza con una aproximación inicial o semilla {x}0 y genera una
sucesión de vectores {x}k tal que
lim
k→∞
{x}k = {x}
donde {x} es la solución al problema de [A]{x} = {c}.
Sin embargo, como es imposible computar infinitos términos, hay que
interrumpir el proceso en algún punto y ello genera un error de
truncamiento.
Los sistemas iterativos traen consigo un proceso que convierte el
sistema [A]{x} = {c} en otro equivalente de la forma:
{x} = [B]{x}+ {d}. Luego de seleccionar el vector inicial la sucesión
de los vectores de la solución se genera calculando
{x}k+1 = [B]{x}k + {d}
donde [B] se denomina matriz de iteración y {d} es un vector. Tanto [B]
como {d}, no cambian durante las iteraciones.
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
Resolvamos un sistema de ecuaciones de 3× 3 del tipo [A]{x} = {c},
se puede verificar fácilmente que
x1 =
c1 − a12x2 − a13x3
a11
x2 =
c2 − a21x1 − a23x3
a22
x3 =
c3 − a31x1 − a32x2
a33
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
Método de Jacobi
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
Ejemplo del Método de Jacobi
Resuelva por el método de Jacobi el siguiente sistema
10x1 − 2x2 + 2x3 + 0 = 6
−x1 + 11x2 − x3 + 3x4 = 25
2 + x1 − x2 + 10x3 − x4 = −11
3x2 − x3 + 8x4 = 15
Despejando la incógnita xi de la ecuación Ei, se tiene
x1 = 1/10x2 − 1/5x3 + 3/5
x2 = 1/11x1 + 1/11x3 − 3/11x4 + 25/11
x3 = −1/5x1 + 1/10x2 + 1/10x4 − 11/10
x4 = −3/8x2 + 1/8x3 + 15/8
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
La solución exacta es {x} = [1 2 − 1 1]T . Por el método de Jacobi
con el vector inicial {x}0 = [0 0 0 0]T se tienen los siguientes
resultados
k 0 1 2 3 10
x1 0.0 0.6 1.0473 0.9326 1.001
x2 0.0 2.2727 1.7159 2.053 1.9998
x3 0.0 -1.1 -0.8052 -1.0493 -0.9998
x4 0.0 1.875 0.8852 1.1309 0.9998
Table: Método de Jacobi.
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
Desarrollo general del método de Jacobi
Si partimos de este sistema simple 3× 3
x1 =
c1 − a12x2 − a13x3
a11
x2 =
c2 − a21x1 − a23x3
a22
x3 =
c3 − a31x1 − a32x2
a33
se puede verificar que
xk+1i =
ci −
∑i−1
j=1 aijx
k
j −
∑n
j=i+1 aijx
k
j
aii
Nota. Realizar las sumatorias para verificar el resultado de esta
ecuación.
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
Notación matricial del método de Jacobi
Se puede observar que: ci → {d} (39)
i−1∑
j=1
aij → −[L] =

0 . . . 0
−a21
. . .
...
...
. . .
...
−an1 −an,n−1 0
 (40)
n∑
j=m
aij → −[U ] =

0 −a12 −a1,n
...
. . .
...
...
. . . −an−1,n
0 . . . 0
 (41)
n∑
j=m
aij → [D] =

a11 0 0
... a22
...
...
. . . 0
0 . . . ann
 (42)
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
Reemplazando las matrices en la fórmula de Jacobi,
xk+1i =
ci −
∑i−1
j=1 aijx
k
j −
∑n
j=i+1 aijx
k
j
aii
{x}k+1 = [D]−1({c}+ [L]{x}k + [U ]{x}k)
reordenando
{x}k+1 = [D]−1([L] + [U ]){x}k + [D]−1{c} → {x}k+1 = [B]{x}k + {d}
Se llega a la forma matricial de Jacobi.
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
Método de Gauss Seidel
Una mejora del método de Gauss es el método de Gauss seidel.
Notar que utiliza aproximaciones de la iteración actual k + 1.
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
xk+1i =
ci −
∑i−1
j=1 aijx
k+1
j −
∑n
j=i+1 aijx
k
j
aii
Al utilizar una aproximación en la iteración k + 1 en vez de la iteración
k, el método usa valores más recientemente calculados y eso hace
que se converja más rápidamente a la solución.
Nota. Realizar las sumatorias para verificar el resultado de esta
ecuación.
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
Ejemplo
x1 = 3/5 + 1/10xk−12 − 1/5x
k−1
3
x2 = 25/11 + 1/11xk1 + 1/11x
k−1
3 − 3/11x
k−1
4
x3 = −11/10− 1/5xk1 + 1/10xk2 + 1/10xk−14
x4 = 15/8− 3/8xk2 + 1/8xk3
k 0 1 2 3 5
x1 0.0 0.6 1.03 1.0065 1.0001
x2 0.0 2.3272 2.037 2.036 2.000
x3 0.0 -0.9873 -1.014 -1.0025 -1.000
x4 0.0 0.8789 0.9844 0.9983 1.000
Table: Método de Gauss Seidel.
Con Gauss Seidel se obtuvo casi la solución exacta en la 5 iteración,
en tanto que con Jacobi llevó 5 iteración más!!!
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
Notación matricial del método de Gauss
Seidel
Con las matrices definidas anteriormente en las Ecs.(39, 42, 40, 41)
y luego de unas operaciones algebraicas se tiene
{x}k+1 = [D]−1({c}+ [L]{x}k+1 + [U ]{x}k)
despejando {x}k+1, se tiene
{x}k+1 = ([I]− [D]−1[L])−1[D]−1[U ]{x}k + ([I]− [D]−1[L])−1[U ]
{x}k+1 = [B]GS{x}k + [C]GS [U ] → {x}k+1 = [B]GS{x}k + {d}
Introducción METODOS DIRECTOS METODOS ITERATIVOS Condición de Convergencia
Condición de Convergencia para los
métodos iterativos
La condición necesaria y suficiente para que un método iterativo
converja es
ρ([B]) = máx‖λi([B])‖ < 1
donde
ρ([B]) es el radio espectral de la matriz de iteración [B] de cada método.
λi es el autovalor de la matriz de iteración [B].
máx‖ • ‖ es el operador maximización
En palabras, para que un método iterativo converja, el máximo
autovalor de la matriz de iteración [B] tiene que ser menor que uno.
	Introducción
	METODOS DIRECTOS
	METODOS ITERATIVOS
	Condición de Convergencia