Unidad III-SOLUCIÓN DE SISTEMAS DE ECUACIONES LINEALES

Los sistemas de ecuaciones representan problemas físicos o

modelos, que involucran la interacción de muchas variables y
propiedades.
Las variables en el sistema representan el estado o la
respuesta del modelo, las propiedades nos dan características
de estos problemas o modelos
Las ecuaciones describen las interacciones entre las variables
y las propiedades.

a1,1 x1 + a1, 2 x2 +  + a1, n xn = b1

a 2,1 x1 + a 2, 2 x2 +  + a2, n xn = b2

a n ,1 x1 + a n , 2 x2 +  + an , n xn = bn

Metodos Numericos 2022 1

Unidad III-SOLUCIÓN DE SISTEMAS DE ECUACIONES LINEALES
El problema que vamos resolver es , dado un sistema de n
ecuaciones lineales con n incógnitas:

a1,1 x1 + a1, 2 x2 +  + a1, n xn = b1

a 2,1 x1 + a 2, 2 x2 +  + a2, n xn = b2

a n ,1 x1 + a n , 2 x2 +  + an , n xn = bn

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

Metodos Numericos 2022

2
Unidad III - SOLUCIÓN DE SISTEMAS DE ECUACIONES LINEALES
Objetivos
• Que puedan reconocer si el problema dado puede ser
modelado con un sistema de ecuaciones lineales
• Que conozcan los distintos métodos existentes para encontrar
la solución de un sistema de ecuaciones lineales
• Que dado un problema determinado, pueda elegir el método
mas apropiado para resolverlo
Contenido
• Métodos directos. Métodos para matrices triangulares. Método
de Eliminación de Gauss. Descomposición LU. Estrategia de
pivoteo y escalamiento. Cálculo de la inversa. Métodos para
matrices especiales: Cholesky, Thomas.
• Análisis del error: concepto de norma, número de condición,
cotas de error. Método de los residuos.
• Métodos iterativos: Gauss Jacobi, Gauss Seidel. Método SOR.
Análisis del error y la convergencia.

Metodos Numericos 2022 3

 Algunas aplicaciones :

• Desarrollo de videojuegos, simuladores

• Programas que simulan procesos de física
Newtoniana en ambientes virtuales (utilizados para
que los efectos parezcan más realistas )
• Detección de colisiones y respuesta
• Simulación Dinámica
• Codificación y decodificación de mensajes
• Motores de búsqueda de páginas en internet/intranet
• Inteligencia Artificial – Aprendizaje Automático
• Modelos de clima
• Calculo de estructuras
• Procesamiento de imágenes
• Modelos económicos
• Ajuste de funciones
• Etc..
Metodos Numericos 2022 4
 MATRICES
Supongamos dada 𝐴 , matriz cuadrada de orden 𝑛

 a1,1 a1, 2  a1, n 

 
a 2,1 a 2, 2  a 2, n
A= 
  
 
 a n ,1 a n,2  a n,n 

Se define la matriz transpuesta , AT, como aji , j=1,n; i=1,n

Una matriz cuadrada A es simétrica si, A = AT,𝑎𝑖𝑗 = 𝑎𝑗𝑖 ∀ i,j

Una matriz cuadrada A es ortonormal si , ATA = A AT = I

Metodos Numericos 2022 5

 MATRICES
Supongamos dada 𝐴 , matriz cuadrada de orden 𝑛
Diremos que es TRIANGULAR SUPERIOR si : 𝑎𝑖𝑗 = 0 para 𝑖 > 𝑗
 a1,1 a1, 2  a1, n 
 
0 a 2, 2  a 2, n 
A=
  
 
 0 0  a n , n 

Diremos que es TRIANGULAR INFERIOR si: 𝑎𝑖𝑗 = 0 para 𝑖 < 𝑗

 a1,1 0  0 
 
a 2,1 a 2, 2  0
A= 
  
 
 a n ,1 a n,2  a n,n 

Si la matriz es cuadrada, su determinante es el producto de los

elementos de la diagonal.
Metodos Numericos 2022 6
Teorema 1: Dada A, matriz cuadrada de orden n, los
enunciados siguientes son equivalentes:

• El sistema homogéneo A x=0 tiene solo la solución

trivial x=0
• ∀ miembro de la derecha, b, el sistema A x = b tiene
una solución
• A es invertible

Metodos Numericos 2022 7

CLASIFICACIÓN DE MÉTODOS

METODOS DIRECTOS: Son aquellos que nos conducirían a la

solución exacta luego de un número finito de operaciones
elementales, si no hubiera errores de redondeo

METODOS ITERATIVOS: parten de una estimación inicial x0 y

construyen una sucesión de aproximaciones, que en principio,
convergen a la solución x

TIPOS DE MATRICES

MATRICES DENSAS: Son aquellas que poseen pocos elementos

nulos y son de orden bajo

MATRICES RALAS(SPARSE): Son aquellas que poseen muchos

ceros y son de orden alto

Metodos Numericos 2022 8

 SISTEMA CON MATRIZ TRIANGULAR SUPERIOR

Dado el sistema A x = b, siendo A una matriz   nxn ,

triangular superior, con todas sus entradas diagonales no
nulas, entonces resolvemos el sistema utilizando
sustitución hacia atrás
Algoritmo:
b
Paso 1 Calcular x n = n
a nn
Paso 2 Para k = n-1 , ... , 1.-1
n
bk − a
j = k +1
kj xj
xk =
a kk
Teorema: Si A es matriz triangular superior, con 𝑎𝑖𝑖 ≠ 0 ∀ 𝑖 ,
entonces A es invertible
Metodos Numericos 2022 9
Ej. Supongamos tener el sig. sistema A x = b para resolver:
2 5 6 10
𝐴= 0 4 3 𝑏= 3
0 0 4 4

b3
Paso 1 x3 = = 4 =1
a 33 4

Paso 2 Para k = 2 ,1,-1

3
b2 − a
j =3
2j xj
3 − a 23 x 3 3 − 3 .1
x2 = = = =0
a 22 a 22 4
3
b1 − a
j =2
1j xj
10 − ( a12 x 2 + a13 x 3 ) 10 − (5.0 + 6.1)
x1 = = = =2
a11 a11 2

x t = ( 2,0,1)

Metodos Numericos 2022 10

Ej. Supongamos tener el sig. sistema A x = b para resolver:
3 6 4 1
𝐴= 0 2 −2 𝑏 = −2
0 0 4 4
b3
x3 = =?
Paso 1 a 33

Paso 2 Para k = 2 ,1,-1

n
b2 − a
j = k +1
2j xj
x2 = =?
a 22
3
b1 − a
j = k +1
1j xj
x1 = =?
a11

Metodos Numericos 2022 11

 SISTEMA CON MATRIZ TRIANGULAR INFERIOR
Dado el sistema A x= b, siendo A una matriz  nxn
,
triangular inferior, con todas sus entradas diagonales no
nulas, entonces resolvemos el sistema utilizando
sustitución hacia adelante
Algoritmo:
b1
Paso 1 Calcular x1 =
a11
Paso 2 Para k = 2 , ... , n,1
k −1
bk − a
j =1
kj xj
xk =
a kk

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

entonces A es invertible
Metodos Numericos 2022 12
Ej. Supongamos tener el sig. sistema A x = b para resolver:
6 0 0 6
𝐴= 8 4 0 𝑏 = 12
2 1 2 5

b1
Paso 1 x1 = = 6 =1
a11 6

Paso 2 Para k = 2,n

1
b2 − aj =1
2j xj
12 − a 21 x1 12 − 8.1
x2 = = = =1
a 22 a 22 4
2
b3 − a
j =1
3j xj
5 − ( a 31 x1 + a 32 x 2 ) 5 − ( 2.1 + 1.1)
x3 = = = =1
a 33 a 33 2

x t = ( 1,1,1)

Metodos Numericos 2022 13

Ej. Supongamos tener el sig. sistema A x = b para resolver:
6 0 0 −3
𝐴= 4 2 0 𝑏= 8
6 −3 1 7

Paso 1 b1
x1 = =?
a11

Paso 2 Para k = 2,n

k −1
b2 − aj =1
2j xj
x2 = =?
a 22
k −1
b3 − a
j =1
3j xj
x3 = =?
a 33

xt = ?
Metodos Numericos 2022 14
 CASO GENERAL

Dado el sistema de ecuaciones lineales de la forma

A x = b , donde A   nxn ; b n

siendo la matriz del sistema no triangular entonces

utilizamos el método de Eliminación de Gauss para
transformar el sistema en uno equivalente con matriz
triangular superior

Metodos Numericos 2022 15

Teorema 2 (INVARIANZA DE LA SOLUCIÓN):
Las soluciones de un sistema Ax = b permanecen
invariantes ante las siguientes operaciones:

• Intercambio de dos ecuaciones cualesquiera

• Multiplicación de una ecuación por un escalar no nulo

• Suma de una ecuación con una combinación lineal no

nula de otras ecuaciones

Metodos Numericos 2022 16

 ELIMINACION DE GAUSS
ALGORITMO DE TRIANGULACION

𝑎11 ⋯ 𝑎1𝑛 𝑥1 𝑏1
Dado el sistema 𝐴𝑥 = 𝑏 ⋮ ⋱ ⋮ ⋮ = ⋮
𝑎𝑛1 ⋯ 𝑎𝑛𝑛 𝑥𝑛 𝑏𝑛
Para resolver el sistema, se requiere el uso de la matriz
ampliada del sistema, la cual se define como
[A:b] 𝑎11 … 𝑎1𝑛 𝑏1
⋮ ⋱ ⋮ ⋮
𝑎𝑛1 … 𝑎𝑛𝑛 𝑏𝑛
Luego, se sustituye A por la matriz escalonada
equivalente, la cual se obtiene aplicando operaciones
elementales.

Metodos Numericos 2022 17

 ELIMINACION DE GAUSS
ALGORITMO DE TRIANGULACION
 2 4 − 2 6
Ejemplo: 2x1 + 4x2 - 2x3 = 6  
x1 - x2 + 5x3 = 0 1 − 1 5 0  matriz
4 1 − 2 2 
4x1 + x2 - 2x3 = 2   ampliada
La idea es llegar a un sistema equivalente que tenga una
matriz triangular superior.
Paso 1: eliminamos los elementos de la primera columna.
Se eligen 𝒎𝟐𝟏 y 𝒎𝟑𝟏 de forma que los elementos de la columna 1 debajo
de la diagonal principal sean nulos
𝟏 − 𝒎𝟐𝟏 × 𝟐 = 𝟎 → 𝒎𝟐𝟏 = 𝟏/𝟐 𝟒 − 𝒎𝟑𝟏 × 𝟐 = 𝟎 → 𝒎𝟑𝟏 = 𝟐
Resto a la 2da ecuación la 1era multiplicada por m21 = 1/2
Resto a la 3era ecuación la 1era multiplicada por m31 = 2
2x1 + 4x2 - 2x3 = 6 2 4 − 2 6 
 
-3x2 + 6x3 = -3 0 − 3 6 − 3  matriz
-7x2 + 2x3 = -10  0 − 7 2 − 10  ampliada
 

Metodos Numericos 2022 18

 2x1 + 4x2 - 2x3 = 6 2 4 − 2 6 
 
-3x2 + 6x3 = -3 0 − 3 6 − 3 
-7x2 + 2x3 = -10 .  0 − 7 2 − 10 
 
Paso 2: eliminamos los elementos de la segunda columna.
𝟕
Calculamos: −7 − 𝑚32 × −3 = 0 → 𝒎𝟑𝟐 = 𝟑
Resto a la 3era ecuación la 2da multiplicada por m32= 7/3

2x1 + 4x2 - 2x3 = 6 2 4 − 2 6 

 
-3x2 + 6x3 = -3 0 − 3 6 − 3
 0 0 − 12 − 3 
-12x3 = -3  

Obtengo una matriz triangular superior.

Utilizando el algoritmo de sustitución hacia atrás resolvemos el

sistema: x T = (1/4, 3/2, 1/4 )
Metodos Numericos 2022 19
 FACTORIZACION LU
Sea el problema general de resolver un sistema de
ecuaciones lineales de la forma

A x = b , donde A   nxn; b   n

Este método se usa para resolver sistemas de ecuaciones

con la misma matriz de coeficientes y distintos términos
independientes.
Se descompone la matriz A en un producto de dos matrices:

 Una matriz triangular inferior unidad L.

 Una matriz triangular superior U,

de tal forma que A=LU

Metodos Numericos 2022 20

 FACTORIZACION LU
Dado el sistema inicial, A x = b,

𝐴1 = (𝑎1 𝑖𝑗 ) , 𝑏1 = (𝑏1 𝑖 ) , 1 ≤ 𝑖, 𝑗 ≤ 𝑛
Paso 1: suponiendo 𝑎111 ≠ 0
mi1 = 𝑎1 𝑖1 / 𝑎111 i = 2, 3, …., n

𝑎2 𝑖𝑗 = 𝑎1 𝑖𝑗 - mi1 𝑎11𝑗 i,j = 2, 3, …., n

𝐴2 = (𝑎2 𝑖𝑗 )
Paso k: suponiendo 𝑎𝑘 𝑘𝑘 ≠ 0
mik = 𝑎𝑘 𝑖𝑘 / 𝑎𝑘 𝑘𝑘 i = k+1, …., n
aijk +1= 𝑎𝑘 𝑖𝑗 - mik 𝑎𝑘 𝑘𝑗 i,j = k+1, …., n
𝐴𝑘+1 = ( a ijk +1 )
Metodos Numericos 2022 21
 FACTORIZACION LU

Despues de n-1 pasos: A n , triangular superior, U = A n

 a11
1
a121 1
a13 . a11n 
 2 2 
 0 a 22 a 23 . a 22n 
U=  0 0 3
a 33 . a 33n 
 
 . . . . . 
 0 0 0. . n 
a nn
 

Definimos ahora la matriz L, formada por los multiplicadores

 1 0 0 . 0
 m21 1 0 . 0
L=  
 m31 m32 1 . .
 . . . . .
m 1
 n1 mn 2 . . 
Metodos Numericos 2022 22
Teorema 3: Factorización LU
Sea 𝐴 = 𝑎𝑖𝑗 ∈ 𝑀𝑛×𝑛 tal que las 𝑛 sub-matrices
principales:
𝑎11 ⋯ 𝑎1𝑘
∆𝑘 = ⋮ ⋱ ⋮ , 𝑘 = 1, … , 𝑛
𝑎𝑘1 ⋯ 𝑎𝑘𝑘

Sean invertibles (esto es, det ∆𝑘 ≠ 0, ∀𝑘 = 1, … , 𝑛 ).

𝑘
Entonces, 𝑎𝑘𝑘 ≠ 0, ∀ 𝑘 = 1, … , 𝑛 y por lo tanto, existe una
matriz triangular inferior 𝐿 = (𝑙𝑖𝑗 ) , con elementos
diagonales 𝑙𝑖𝑖 = 1, ∀𝑖 = 1, … , 𝑛 y una matriz diagonal
superior 𝑈 = (𝑢𝑖𝑗 ) , tales que 𝑨 = 𝑳𝑼 . Además, esta
factorización es única.

Metodos Numericos 2022 23

 FACTORIZACION LU
Dado el sistema inicial, A x = b, y calculada A = LU, la
solución del sistema se calcula:

LU x = b

Se considera Ux=y

Se resuelve el sistema Ly =b

Calculado y, se resuelve Ux=y

Metodos Numericos 2022 24

 FACTORIZACION LU
Ejemplo:
1 3 2
A1 =  
1 5 0
Paso 1: 𝒂𝟏 𝟏𝟏 = 1  1
2 4 
m21 = 𝑎1 21 / 𝑎111 =1/1=1 , 𝑎2 2𝑗 = 𝑎1 2𝑗 - m21 𝑎11𝑗 , j =1,2,3
𝑎2 21 = 𝑎1 21 - m21 𝑎111=1-1.1=0
𝑎2 22 = 𝑎1 22 - m21 𝑎112=5-1.3=2
𝑎2 23 = 𝑎1 23 - m21 𝑎113=0-1.2=-2
m31 = 𝑎1 31 / 𝑎111 =2/1=2 , 𝑎2 3𝑗 = 𝑎1 3𝑗 - m31 𝑎11𝑗 , j=1,2,3

𝑎2 31 = 𝑎1 31 - m31 𝑎111 =2-2.1=0

𝑎2 32 = 𝑎1 32 - m31 𝑎112 =4-2.3=-2 A2 =

𝑎2 33 = 𝑎1 33 - m31 𝑎113 =1-2.2=-3

Metodos Numericos 2022 25
 FACTORIZACION LU

Ejemplo: A2 =

Paso 2: 𝒂𝟐 𝟐𝟐 = 2
m32 = 𝑎2 32 / 𝑎1 22 =-2/2=-1 , 𝑎3 3𝑗 = 𝑎2 3𝑗 - m32 𝑎2 2𝑗 , j =2,3
1 3 2 
𝑎3 𝑎2 - m32 𝑎2 22 =-2- (-1).2=0 0 − 2 
32 = 32
 2
𝑎3 33 = 𝑎2 33 - m32 𝑎2 23=-3-(-1).(-2)=-5 A = 0
3
− 5 
 0
1 0 0 1 3 2 
1 0 − 2 
 1 0
  2
 −1 1 0 − 5 
2  U= 
0
L=
NOTA: No hay necesidad de almacenar los 0
Es posible almacenar las matrices L y U en A
Metodos Numericos 2022 26
 FACTORIZACION LU

Ejemplo:

1 0 0 1 3 2 
L = 1 1 0 U= 0 2 − 2 
  

2 −1 1
 0 0 − 5 

1 0 0 𝑦1 9 Sust. hacia Adelante 9

Ly =b 1 1 0 𝑦2 = 11 𝑦= 2
2 −1 1 𝑦3 11 −5
Sust. hacia Atrás
1 3 2 𝑥1 9 1
Ux=y 0 2 −2 𝑥2 = 2 𝑥= 2
0 0 −5 𝑥3 −5 1
Metodos Numericos 2022 27
 Ejemplo:
A1 =

Paso 1: 𝑎111 = 4

m21 = 𝑎1 21 / 𝑎111 = ? , 𝑎2 2𝑗 = 𝑎1 2𝑗 - m21 𝑎11𝑗 , j =2,3

𝑎2 22 = 𝑎1 22 - m21 𝑎112= ?
𝑎2 23 = 𝑎1 23 - m21 𝑎113= ?
m31 = 𝑎1 31 / 𝑎111 = ? , 𝑎2 3𝑗 = 𝑎1 3𝑗 - m31 𝑎11𝑗 , j= 2,3

𝑎2 32 = 𝑎1 32 - m31 𝑎112 = ? A2 = ?
𝑎2 33 = 𝑎1 33 - m31 𝑎113 = ? Metodos Numericos 2022 28
 FACTORIZACION LU

Paso 2: 𝒂𝟐 𝟐𝟐 = ?

m32 = 𝑎2 32 / 𝑎1 22 = ? , 𝑎3 3𝑗 = 𝑎2 3𝑗 - m32 𝑎2 2𝑗 , j =3

𝑎3 33 = 𝑎2 33 - m32 𝑎2 23 = ?

A3 = ?

L= U=
?
Ly =b Ux=y 𝑥= ?
?

Metodos Numericos 2022 29

 NUMERO DE OPERACIONES
Consideramos el costo de:
i) Cálculo de L y U
n −1 n −1
n −1
 ( n − k )  3
 ( n − 1) 3
1  2 n 3


k =1
2 ( n − k ) 2
 2  ( n − k ) 2
dk = −2
 3 1
 = 2
 3
− 
3 3
1

ii) Resolución de Ly = b
n n
1 + 2n − 1
 2(i − 1) + 1 =  2i − 1 = 1 + 3+...+2n − 1 =
i =1 i =1 2
n = n2

iii) Resolución de Ux = y
n n
1 + 2n − 1

i =1
2 ( i − 1) + 1 = 
i =1
2i − 1 = 1 + 3+ ...+ 2 n − 1 =
2
n = n 2

El costo es O( n3)
Metodos Numericos 2022 30
 CALCULO DEL DETERMINANTE
A = LU det(A) = det(L)det(U) = det(U)

𝐿 triangular con lii=1, ∀ 𝑖, entonces det 𝐿 = 1

CALCULO DE A-1
Dado que: A A-1 = I

Calculamos: A xi = ei , i = 1,…, n
A : matriz de partida
x i: columna i-esima de la matriz inversa
ei : columna i-esima de la matriz identidad, (0....1(i)......0)t
Así se calculan las n columnas de la matriz inversa, A-1
Acá se observa la ventaja de la Factorización LU, pues se
triangulariza una única vez y luego sólo se cambia el
término independiente. Metodos Numericos 2022 31
Pivoteo y Escalamiento en el Método de Gauss

Se ha supuesto que akkk ≠ 0 ∀𝑘 , elemento pivote, caso

contrario hay que realizar intercambio de filas.
También puede ocurrir que el elemento pivote sea pequeño
entonces:

a ik(k +1)
mik = (k +1) , i = k+1, ... ,n
a kk

serán grandes y producen mucho error de redondeo

Metodos Numericos 2022 32

Ejemplo: Sin Pivoteo

1.133 5.281   x1  6.414 

t=4 24 .14 − 1.210   x  =  22 .93
  2   

m21 =
24 .14
= 21 .31 1.133 5.281   x1   6.414 
0.000   =

− 113 .7   x2  − 113 .8
1.133
a 2 22 = a 1 22 − m 21 a 112 
= −113 .7
 x1  0.9956 
 x  =  1.001  Pérdida de precisión
 2  
Metodos Numericos 2022 33
Ejemplo: Con Pivoteo

24 .14 − 1.210   x1  22 .93

1.133 5.281   x  = 6.414 
  2   

1.133 24 .14 − 1.210   x1  22 .93

m21 = = 0.04693 0.000 5.338   x  = 5.338 
24 .14
  2   
a 2 22 = a 1 22 − m 21 a 112
= 5.338
 x1  1.000 
 x  = 1.000 
 2  
Metodos Numericos 2022 34
 Pivoteo Parcial
Wilkinson llama así a tomar como pivote el elemento de mayor
valor absoluto de una columna
Paso k :
ck = max aik
k

i = k ... n

Siendo i el menor índice ≥ 𝑘 tal que se obtiene el valor 𝑐𝑘

Nótese que de esta forma los multiplicadores

mik  1 , i = k+1,…,n

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

Metodos Numericos 2022 35

  a (1) (1)
a12 (1)
a13  a1(i1)  a1(1j)  a1(1n) 
Paso k :  11 ( 2) ( 2)

 0 a 22 a 23  a 2( 2i )  a 2( 2j)  a 2( 2n) 
 ( 3) 
 0 0 a 33  a 3(3i )  a 3(3j)  a 3(3n) 
          
 (k ) (k ) (k ) 
 0 0 0  a kk  a kj  a kn  Fila Pivote
c k = max a ikk           
 
i = k ...n  0 0 0  a ik( k )  a (jjk )  (k )
a jn 
 
          
 0 0 0  (k )
a nk  (k )
a nj  (k )
a nn 
 
Columna Pivote
 a (1) (1)
a12 (1)
a13  a1(i1)  a1(1j)  a1(1n) 
 11
( 2) ( 2)

 0 a 22 a 23  a 2( 2i )  a 2( 2j)  a 2( 2n) 
 ( 3) 
 0 0 a 33  a 3(3i )  a 3(3j)  a 3(3n) 
          
 (k ) (k ) (k ) 
 0 0 0  a kk  a kj  a kn  Fila Pivote
          
El mas grande  
 0 0 0  a (jkk )  a (jjk )  a (jnk ) 
 
          
 0 0 0  (k )
a nk  (k )
a nj  (k )
a nn 
 

Metodos Numericos 2022 36

 Pivoteo Total
Wilkinson llama así a tomar como pivote el elemento de mayor valor
absoluto de toda la matriz
Paso k :
c k = max a ijk
i , j = k ... n

a (1) (1)
a12 (1)
a13  a1(i1)  a1(1j)  a1(1n) 
 11 ( 2) ( 2)

 0 a 22 a 23  a 2( 2i )  a 2( 2j)  a 2( 2n) 
 ( 3) 
 0 0 a 33  a 3(3i )  a 3(3j)  a 3(3n) 
          
 (k ) (k ) 
 0 0 0  a kk  a kj( k )  a kn 
El mas grande           
 
 0 0 0  a ik( k )  a (jjk ) (k )
 a jn 
 
          
 0 0 0  (k )
a nk  (k )
a nj (k )
 a nn 
 

es muy caro por el numero de comparaciones , por ello es mas utilizado el

pivoteo parcial
Metodos Numericos 2022 37
 Implementación de LU con Pivoteo
Si representamos con P = ( Pn-1 ... P1 ) las permutaciones de
filas realizadas, entonces P A = L U

Dado A x = b si P A = L U ∴ A = PLU

El sistema a resolver quedaría:

PLU x = b
Ly=Pb
Ux=y

Nota:
Cuando dos filas de A se intercambian, las filas de b deben también ser
intercambiadas.
Es conveniente usar un vector pivote; se inicializa desde 1 hasta n.
Cuando dos filas de A son intercambiadas, se aplica esto al vector pivote.

Metodos Numericos 2022 38

Ejemplo:  0 3 2   12  1 
A =  − 4 −2 1  b =  − 5 p =  2
 1 4 − 2  3   3

− 4 − 2 1  2
Paso 1: C1 = max {0,-4,1}    
A´=  0 3 2 p = 1 
 1 4 − 2  3

Paso 1: 𝑎111 = -4
m21 = 𝑎1 21 / 𝑎111 =0/-4=0 , 𝑎2 2𝑗 = 𝑎1 2𝑗 - m21 𝑎11𝑗 , j =2,3
𝑎2 22 = 𝑎1 22 - m21 𝑎112 =3-0.(-2)=3
𝑎2 23 = 𝑎1 23 - m21 𝑎113 =2-0.1=2
m31 = 𝑎1 31 / 𝑎111 =-1/4 , 𝑎2 3𝑗 = 𝑎1 3𝑗 - m31 𝑎11𝑗 , j=2,3
− 4 − 2 1 
𝑎2 32 = 𝑎1 32 - m31 𝑎112 =4-(-1/4).(-2)=7/2=3.5  
A2 =  0 3 2 
𝑎2 33 = 𝑎1 33 - m31 𝑎113 =-2-1.(-1/4)=-7/4=-1.75  0 3.5 − 1.75

Metodos Numericos 2022 39

 Paso 2 − 4 − 2 1  2
   
A2 =  0 3 2  p = 1 
C2 = max {3,3.5}  0 3.5 − 1.75  3

− 4 − 2 1  2
   
A 2 ´=  0 3.5 − 1.75 p = 3
 0 3 2  1 

𝑎2 22 = 3.5
m32 = 𝑎2 32 / 𝑎2 22 =3/3.5, 𝑎3 3𝑗 = 𝑎2 3𝑗 - m32 𝑎2 2𝑗 , j=3
− 4 − 2 1 
𝑎3 33 = 𝑎2 33 - m32 𝑎2 23 =2-(3/3.5)(-1.75)=3.5 A 3 =  0 3.5 − 1.75
 
 0 0 3.5 

 1 0 0 − 4 − 2 1  2
     
L =  − 0.25 1 0 U =  0 3.5 − 1.75 p = 3
 0 3 / 3.5 1   0 0 3.5  1 

Metodos Numericos 2022 40

  1 0 0 − 4 − 2 1   12  2
 
L =  − 0.25 1 0 U =  0 3.5 − 1.75  
b =  − 5
 
p = 3
 
 0 3 / 3.5 1   0 0 3.5   3  1 

Para resolver el sistema hay que calcular:

 1 0 0   y1   − 5 y1 = b1 = −5
     y 2 = b2 − (−0.25). y1 = 3 + 0.25 y1 = 1.75
L y = P b 0.25 1 0  y 2  =  3 
 0 3 / 3.5 1   y 3   12  y 3 = b3 − (3 / 3.5). y 2 = 12 − (3 / 3.5) y 2 = 10.5

− 4 − 2 1   x1   − 5  x 3 = y 3 / u 3 = 10.5 / 3.5 = 3
     x 2 = ( y 2 − (−1.75).x 3 ) / u 2 = (1.75 + 1.75.3) / 3.5 = 2
Ux=y  0 3 . 5 − 1 . 75   x 2  = 1.75
 0 0 3.5   x 3  10.5 x1 = ( y1 − (1.x 3 + (−2).x 2 )) / u1 = (−5 − (3 − 4)) / − 4 = 1

xT =(1 , 2, 3)
Metodos Numericos 2022 41
 Escalamiento Implícito
Wilkinson propone que una matriz debe equilibrarse antes
de aplicar una algoritmo de solución de sistemas lineales.
Al aplicar el escalamiento implícito, supongamos estar en
el paso k del proceso de triangulación:
k
a ik
c k = max
i = k ...n si

i es el menor índice tal que 𝑖 ≥ 𝑘, si son distintos se

intercambian las filas

Siendo s, vector tamaño, que se inicializa al comenzar el

algoritmo
si = max aij
j =1... n

Metodos Numericos 2022 42

Ejemplo de pivoteo con escalamiento:
 4 2 1 7  4 1 
       
A = − 1 0 6 b = 5  s = 6  p = 2
 2 2 1  5   2  3
Paso 1:
𝑎𝑖1 4 1 2
C1 = max =max{ , , }
𝑠𝑖 4 6 2

Paso 1: 𝑎111 = 4
m21 = 𝑎1 21 / 𝑎111 =-1/4 , 𝑎2 2𝑗 = 𝑎1 2𝑗 - m21 𝑎11𝑗 , j =2,3
𝑎2 22 = 𝑎1 22 - m21 𝑎112 =0-2.(-1/4)=1/2
𝑎2 23 = 𝑎1 23 - m21 𝑎113 =6-(-1/4)1=25/4
m31 = 𝑎1 31 / 𝑎111 =2/4 =1/2, 𝑎2 3𝑗 = 𝑎1 3𝑗 - m31 𝑎11𝑗 , j =2,3
4 2 1 
𝑎2 32 = 𝑎1 32 - m31 𝑎112 =2-(1/2).2=1  
A 2 = 0 0.5 6.25
𝑎2 33 = 𝑎1 33 - m31 𝑎113 =1-(1/2).1=1/2 0 1 0.5 

Metodos Numericos 2022 43

 Paso 2 4 2 1  4 1 
     
A 2 = 0 0.5 6.25 s = 6  p = 2
𝑎𝑖2 1 1 0 1 0.5   2  3
C2 = max
𝑠𝑖
=max{ ,
12 2
}
4 2 1  4 1 
     
A 2 ´= 0 1 0 .5  s = 2 p = 3
0 0.5 6.25 6   2
𝑎2 22 = 1
m32 = 𝑎2 32 / 𝑎2 22 =0.5, 𝑎3 3𝑗 = 𝑎2 3𝑗 - m32 𝑎2 2𝑗 , j=3
4 2 1 
𝑎3 33 = 𝑎2 33 - m32 𝑎2 23 =6.25-(0.5)(0.5)=6  
A 3 =  0 1 0 .5 
0 0 6 

 1 0 0 4 2 1  4 1 
       
L =  0 .5 1 0 U =  0 1 0 .5  s = 2 p = 3
− 0.25 0.5 1  0 0 6  6   2

Metodos Numericos 2022 44

  1 0 0 4 2 1  7  1 
       
L =  0 .5 1 0 U =  0 1 0 .5  b = 5  p = 3
− 0.25 0.5 1  0 0 6  5   2

Para resolver el sistema hay que calcular:

 1 0 0   y1   7  y1 = b1 = 7
     
L y = P b  0 .5 1 0  y 2  = 5  y 2 = b2 − (−0.25). y1 = 5 − 0.5 y1 = 1.5
− 0.25 0.5 1   y 3  5 y 3 = b3 − (−0.25. y1 + 0.5. y 2 ) = 5 − (−7 / 4 + 3 / 4) = 6

4 2 1   x1   7  x 3 = y 3 / u 33 = 6 / 6 = 1
     
Ux=y 0 1 0 .5   x 2  = 1.5 x 2 = ( y 2 − (0.5).x 3 ) / u 22 = (1.5 − 0.5) / 1 = 1
 0 0 6   x 3   6  x1 = ( y1 − (1.x 3 + 2.x 2 )) / u11 = (7 − (1 + 2)) / 4 = 1

xT =(1 , 1, 1)
Metodos Numericos 2022 45
 Variantes de Eliminación de Gauss
Método de Gauss Jordan
Es similar al método de Gauss, la diferencia es que se
diagonaliza la matriz
Paso k: suponiendo 𝑎𝑘 𝑘𝑘 ≠ 0
mik = 𝑎𝑘 𝑖𝑘 / 𝑎𝑘 𝑘𝑘 i = 1, …., n , i≠k
𝑎𝑘+1 𝑖𝑗 = 𝑎𝑘 𝑖𝑗 - mik 𝑎𝑘 𝑘𝑗 j = k, …., n
𝑏 𝑘+1 𝑖 = 𝑏 𝑘 𝑖 - mik 𝑏 𝑘 𝑘
 a11
(1) (1)
a12  a1(1n) b1(1)   a1(11) 0  0 b1( n −1) 
 (1)   
 a21
(1)
a22  a2(1n) b2(1)   0 a2( 22)  0 b2( n −1) 
             
 (1)   
 an1 an(12) bn(1)   0 an( nn) bn( n ) 
(1)
 ann 0 
Al finalizar el algoritmo tenemos 𝑥 = 𝑏 𝑛
Desventaja: Costo aumenta en 50%
Metodos Numericos 2022 46
 Variantes de Eliminación de Gauss
Método de Cholesky
Sea A  nxn , simétrica y definida positiva :
A simétrica si A = AT
A definida positiva si X T A X > 0 ∀ X≠ 0
Para estas matrices se puede encontrar una matriz triangular
inferior L, con elementos diagonales positivos, tal que
A = L LT
 a11 a12 a13   l11 0 0  l11 l 21 l 31 
    
A =  a 21 a 22 a 23  = LLT = l 21 l 22 0  0 l 22 l 32 
 a 31 a 32 a 33  l 31 l 32 l 33   0 0 l 33 

Una vez calculada L y LT resolvemos el sistema :

Ly= b
LT x = y
Metodos Numericos 2022 47
 Variantes de Eliminación de Gauss
Método de Cholesky

Los elementos de L se obtienen comparando los a ij con l ij

Por ej. para n = 2
𝑎11 𝑎12 𝑙11 0 𝑙11 𝑙21
𝑎21 𝑎22 = 𝑙21 𝑙22 0 𝑙22

𝑙11 = 𝑎11 𝑙21 = 𝑎21 Τ𝑙11 𝑙22 = 𝑎22 − 𝑙21 2

lii = ( aii - σ𝑖−1

𝑘=1 𝑙 ik2 )1/2 i =1,…n
Forma Gral:
lji = ( aji - σ𝑖−1
𝑘=1 ljk lik )/lii j = i +1,…n

n3
Ventajas: costo es la mitad de LU, , y no necesita pivoteo
3
Metodos Numericos 2022 48
Ejemplo:  6 16.5 14   54 
   
A = 16.5 76.25 48 b = 243.5
 14 48 54   100 
Para i = 1
𝑙11 = 𝑎11= 6 = 2.4495
𝑙21 = 𝑎21 Τ𝑙11 = 16.5/2.4495= 6.7361 j=2
𝑙31 = 𝑎31 Τ𝑙11 = 14/2.4495= 5.7155 j=3
Para i = 2

𝑙22 = 𝑎22 − 𝑙21 2 = 76.25 − (6.7361)2 = 5.5565

𝑙32 = (𝑎32−𝑙21 𝑙31 Τ𝑙22 = (48-6.7361x5.7155)/ 5.5565= 1.7097 j=3

Para i = 3

𝑙33 = 𝑎33 − 𝑙31 2 − 𝑙32 2 = 54 − 5.71552 − 1.70972 = 4.2906

Metodos Numericos 2022 49
  2.4495 0 0  2.4495 6.7361 5.7155 
   
L =  6.7361 5.5565 0  LT =  0 5.5565 1.7097 
5.7155 1.7097 4.2907   0 0 4.2907 

Ly=b
2.4495 0 0   y1   54  y = b / l = 54 / 2.4495 = 22.045
    
1 1 11

 6.7361 5.5565 0   y 2 = 24.35 y = (b − 6.7361 . y ) / 5.5565 = 17.097

  2 2 1
5.7155 1.7097 4.2907   y 3   100  y = (b − (5.7155 y + 1.7097 y )) / 4.2907 = − 12.872
3 3 1 2

Ux = y
2.4495 6.7361 5.7155   x1   22.045  x 3 = y 3 / u 33 = −3
    =  17.097  x 2 = ( y 2 − (1.7097 ).x 3 ) / u 22 = 4
 0 5 . 5565 1 . 7097  x2   
 0 0 4.2907   x 3  − 12.872  x1 = ( y1 − (5.7155 x 3 + 6.7361 .x 2 )) / u11 = 5

xT =(5, 4, -3 )

Metodos Numericos 2022 50

 MATRIZ DE BANDA
Supongamos dada 𝐴 , matriz cuadrada de orden 𝑛
Diremos que es de banda si : 𝑎𝑖𝑗 = 0 para | 𝑖 − 𝑗 |>m
Siendo 2m+1 el ancho de banda,
si m = 1 la matriz es tridiagonal,
m = 2 la matriz es pentadiagonal

Una matriz tridiagonal seria : 𝑎𝑖𝑗 = 0 para | 𝑖 − 𝑗 |>1

 a11 a12 0 0 
 
 a 21 a 22 a 23 0 
 0 a 32 a 33 a 34 
 
 0 0 a 43 a 44 

Estas matrices son llamadas matrices de Jacobi

Metodos Numericos 2022 51

 Variantes de Eliminación de Gauss
Método de Thomas
Para estas matrices, tridiagonales, se implementa una
variante de LU, con un costo O(n)

 a11 a12 0 0   l11 0 0 0  1 u12 0 0

a a a 0  l l 0 0  
 21 22 23  =  21 22  0 1 u 23 0 
 0 a32 a33 a34   0 l32 l33 0  0 0 1 u34 
    
0 0 a43 a44   0 0 l43 l44  0 0 0 1

y vale que:
𝑙11 = 𝑎11 , 𝑢12 = 𝑎12 /𝑙11
𝑙𝑖𝑖 = 𝑎𝑖𝑖 - 𝑎𝑖𝑖−1 𝑢𝑖−1𝑖 , 𝑢𝑖 𝑖+1 = 𝑎𝑖 𝑖+1 /𝑙𝑖𝑖 i = 2,…,n-1
𝑙𝑛𝑛 = 𝑎𝑛𝑛 - 𝑎𝑛 𝑛−1 𝑢𝑛−1 𝑛

Metodos Numericos 2022

52