Teorema 1: Dada A, matriz cuadrada de orden n, los

Los sistemas de ecuaciones representan problemas físicos enunciados siguientes son equivalentes:
que involucran la interacción de varias propiedades. Las
variables en el sistema representan las propiedades que se
estudian y las ecuaciones describen la interacción entre las El sistema homogeneo Ax=0 tiene solo la solución
variables. trivial x=0
Vamos a resolver un sistema de n ecuaciones lineales con ∀ miembro de la derecha, b, el sistema A x = b tiene
n incógnitas: una solución
a1,1 x1 a1, 2 x2 a1,n xn b1 A es invertible
a 2,1 x1 a2, 2 x2 a 2 , n xn b2

a n,1 x1 an,2 x2 an ,n xn bn

En forma matricial: Ax = b, con A nxn, x n ,b n

1 Patricia Fernández 2 Patricia Fernández

CLASIFICACIÓN DE MÉTODOS SISTEMA CON MATRIZ TRIANGULAR SUPERIOR

nxn
METODOS DIRECTOS: Son aquellos que nos conducirían a Dado el sistema A x = b, siendo A una matriz ,
la solución exacta luego de un número finito de operaciones triangular superior, con todas sus entradas diagonales no
elementales, si no hubiera errores de redondeo nulas, entonces resolvemos el sistema utilizando
METODOS ITERATIVOS: parten de una estimación inicial x0 sustitución hacia atrás
y construyen una sucesión de aproximaciones, que en
principio, convergen a la solución x Algoritmo: bn
P1 Calcular x n a nn

TIPOS DE MATRICES P2 Para k = n-1 , ... , 1.-1

n
bk ak j x j
MATRICES DENSAS: Son aquellas que poseen pocos j k 1
elementos nulos y son de orden bajo xk
MATRICES RALAS(SPARSE): Son aquellas que poseen a kk
muchos ceros y son de orden alto
Teorema: Si A es matriz triangular superior, con 0∀ ,
entonces A es invertible
3 Patricia Fernández 4 Patricia Fernández
SISTEMA CON MATRIZ TRIANGULAR INFERIOR
CASO GRAL
Dado el sistema A x= b, siendo A una matriz ,
triangular inferior, con todas sus entradas diagonales no Dado el sistema de ecuaciones lineales de la forma
nulas, entonces resolvemos el sistema utilizando
sustitución hacia adelante
Algoritmo: A x = b , donde A ; b
P1 b1
Calcular x 1 a 11
siendo la matriz del sistema no triangular entonces
P2 Para k = 2 , ... , n,1 utilizamos el método de Eliminación de Gauss para
k 1
bk ak j x j transformar el sistema en uno equivalente con matriz
j 1
triangular superior
xk
a kk

Teorema: Si A es matriz triangular inferior, con 0∀ ,

entonces A es invertible
5 Patricia Fernández 6 Patricia Fernández

ELIMINACION DE GAUSS
Teorema 2 (INVARIANZA DE LA SOLUCIÓN): ALGORITMO DE TRIANGULACION
Las soluciones de un sistema Ax = b permanecen Para resolver el sistema, se requiere el uso de la matriz
invariantes ante las siguientes operaciones: ampliada del sistema, la cual se define como [A:B]. Luego,
se sustituye A por la matriz escalonada equivalente,
aplicando operaciones elementales.
Intercambio de dos ecuaciones cualesquiera
Ejemplo: 2x1 + 4x2 - 2x3 = 6
Multiplicación de una ecuación por un escalar no nulo
x1 - x2 + 5x3 = 0
Suma de una ecuación con una combinación lineal no 4x1 + x2 - 2x3 = 2
nula de otras ecuaciones
1) eliminamos los elementos de la primera columna.
Sumo a la 2da ecuación la 1era multiplicada por m21 = -1/2
sumo a la 3era ecuación la 1era multiplicada por m31 = -2
2x1 + 4x2 - 2x3 = 6
-3x2 + 6x3 = -3
-7x2 + 2x3 = -10 .
7 Patricia Fernández 8 Patricia Fernández
 FACTORIZACION LU
2x1 + 4x2 - 2x3 = 6
Sea el problema general de resolver un sistema de
-3x2 + 6x3 = -3 ecuaciones lineales de la forma
-7x2 + 2x3 = -10 .
2) eliminamos los elementos de la segunda columna. Ax = b , donde A ;b
Sumo a la 3era ecuación la 2da multiplicada por m31= - 7/3 Este método se usa para resolver sistemas de ecuaciones
2x1 + 4x2 - 2x3 = 6 con la misma matriz de coeficientes y distintos términos
-3x2 + 6x3 = -3 independientes.
Se descompone la matriz A en un producto de dos matrices:
-12x3 = -3
Obtengo una matriz triangular superior. Una matriz triangular inferior unidad L.
Una matriz triangular superior U,
Utilizando el algoritmo de sustitución hacia atrás resolvemos el
sistema x T = (1/4, 3/2, 1/4 ) de tal forma que A=LU

9 Patricia Fernández 10 Patricia Fernández

FACTORIZACION LU FACTORIZACION LU
Dado el sistema inicial, A x = b, Despues de n-1 pasos: A n , triangular superior, U = A n
=( ), =( ) ,1 , 1
a 11 1
a 12 1
a 13 . a 11n
2 2
Paso 1: suponiendo ≠0 0 a 22 a 23 . a 22 n
U= 0 0 3
a 33 . a 33 n
mi1 = / i = 2, 3, …., n
. . . . .
n
= - mi1 i,j = 2, 3, …., n 0 0 0. . a nn

=( ) Definimos ahora la matriz L, formada por los multiplicadores

1 0 0 . 0
Paso k: suponiendo ≠0 m 21 1 0 . 0
mik = / i = k+1, …., n L=
m 31 m 32 1 . .
aijk 1 = - mik i,j = k+1, …., n . . . . .
= ( aijk 1 ) m n1 m n2 . . 1
11 Patricia Fernández 12 Patricia Fernández
 FACTORIZACION LU
Dado el sistema inicial, Ax = b, y calculada A = LU, solución
del sistema es: LU x = b
Ly =b
Ux=y
Ejemplo:

1 0 0 1 3 2
L= 1 1 0 U= 0 2 2 y= x=

2 1 1 0 0 5
13 Patricia Fernández 14 Patricia Fernández

NUMERO DE OPERACIONES CALCULO DEL DETERMINANTE

Consideramos el costo de:
A = LU det(A) = det(L)det(U) = det(U)
i) Cálculo de L y U
CALCULO DE A-1

Dado que: A A-1 = I

ii) Resolución de Ly = b
Calculamos: A xi = ei , i = 1,…, n

iii) Resolución de Ux = y A : matriz de partida

Xi : columna i-esima de la matriz inversa

ei : columna i-esima de la matriz identidad, (0....1(i)......0)t

El costo es O( n3)
15 Patricia Fernández 16 Patricia Fernández
Pivoteo y Escalamiento en el Método de Gauss Pivoteo Parcial
Se ha supuesto que akkk ≠ 0 ∀ , elemento pivote, caso Wilkinson llama así a tomar como pivote el elemento de
contrario hay que realizar intercambio de filas. mayor valor absoluto de una columna
También puede ocurrir que el elemento pivote sea pequeño Paso k :
entonces: ck max a ikk
i k ... n
a ik(k +1)
mik , i = k+1, ... ,n
a (k
kk
+1)
Siendo i el menor índice tal que se obtiene el valor
Nótese que de esta forma los multiplicadores
serán grandes y producen mucho error de redondeo , i = k+1,…,n
mik 1

Si i > k se intercambian las filas en A y b

17 Patricia Fernández 18 Patricia Fernández

Pivoteo Total Implementación de LU con Pivoteo

Wilkinson llama así a tomar como pivote el elemento de
mayor valor absoluto de toda la matriz Si representamos con P = ( Pn-1 ... P1 ) las permutaciones
Paso k : de filas realizadas, entonces P A = L U
Dado A x = b si P A = L U ∴ A = PLU
ck max a ijk PLU x = b
i , j k ... n
Ly=Pb
es muy caro por el numero de comparaciones , por ello es Ux=y
mas utilizado el pivoteo parcial

19 Patricia Fernández 20 Patricia Fernández

Escalamiento Implícito Variantes de Eliminación de Gauss
Wilkinson propone que una matriz debe equilibrarse antes Método de Gauss Jordan
de aplicar una algoritmo de solución de sistemas lineales. Es similar al método de Gauss, la diferencia es que se
diagonaliza la matriz
Al aplicar el escalamiento implícito, supongamos estar en
el paso k del proceso de triangulación: Paso k: suponiendo ≠0
mik = / i = 1, …., n , i≠k
a ikk = - mik j = k, …., n
ck max = - mik
i k ... n si
a 11( 1 ) a 12( 1 ) a 1( 1n ) b1( 1 )
Siendo s, vector tamaño, que se inicializa al comenzar el (1 ) (1 )
a 11( 1 ) 0 0 b1( n 1)

a 21 a 22 a 2( 1n) b 2( 1 )
algoritmo: s max a 0 (2)
a 22 0 b 2( n 1)

i ij
j 1 ... n
a n( 11) a n( 12) (1 )
a nn b n( 1 ) (n)
0 0 a nn b n( n )
i es el menor índice tal que i , si son distintos se
intercambian las filas Al finalizar el algoritmo tenemos
Desventaja: Costo aumenta en 50%
21 Patricia Fernández 22 Patricia Fernández

Variantes de Eliminación de Gauss

Método de Cholesky Método de Thomas(sistemas tridiagonales)
Sea A , simétrica y definida positiva : Para estas matrices, llamadas de Jacobi, se implementa una
A simétrica si A = AT variante de LU, con un costo O(n)
A definida positiva si X T A X > 0 ∀ X≠ 0
a11 a12 0 0 l11 0 0 0 1 u12 0 0
Para estas matrices se puede encontrar una matriz
a21 a22 a23 0 l21 l22 0 0 0 1 u23 0
triangular inferior L, con elementos diagonales positivos, 0 a32 a33 a34 0 l32 l33 0 0 0 1 u34
tal que A = L LT
0 0 a43 a44 0 0 l43 l44 0 0 0 1
ljj = ( ajj - ∑ 2 1/2
jk ) y vale que:
j 1
= , = /
lij ( aij - lik ljk )/ljj , i>j = - , = / i = 2,…,n-1
k 1 = -

Ventajas: costo es la mitad de LU y no necesita pivoteo

23 Patricia Fernández 24 Patricia Fernández