ELIMINACION GAUSSIANA Y PIVOTEO

Definición

En esta sección desarrollamos un método para resolver un sistema de ecuaciones lineales general
AX  B en N ecuaciones con N incógnitas. El objetivo es construir un sistema triangular superior
equivalente UX  Y que podamos resolver usando el método de la sección 3.3.

Se dice que dos sistemas de orden NxN son equivalentes cuando tienen el mismo conjunto de
soluciones. Los teoremas del algebra lineal prueban que hay ciertas transformaciones que no
cambian el conjunto de soluciones de un sistema de ecuaciones lineales.

TRANSFORMACIONES ELEMENTALES.

Teorema.- Cualquiera de las siguientes operaciones aplicadas a un sistema de ecuaciones lineales

produce un sistema equivalente.

(1) Intercambio: El orden de las ecuaciones puede cambiarse.

(2) Escalado: Multiplicar una ecuación por una constante no nula.
(3) Sustitución: una ecuación puede ser remplazada por la suma de ella misma mas un múltiplo
de otra ecuación.

La forma habitual de usar (3) es reemplazar una ecuación por la diferencia de esa ecuación y un
múltiplo de otra. Estos conceptos se ilustran en el siguiente ejemplo.

Ejemplo 1

Emplee la eliminación de Gauss para resolver el sistema siguiente:

2 x1  x2 – x3  1

5 x1  2 x2  2 x3  –4
3x  x  x  5
 1 2 3

Solución

Aplicando la transformación de escalado (2), multiplicamos a la primera ecuación por 5, a la

segunda ecuación por 2 y a la tercera ecuación por 10. El sistema lineal equivalente es.

10 x1  5 x2 – 5 x3  5

10 x1  4 x2  4 x3  –8
30 x  10 x  10 x  50
 1 2 3
Aplicando la transformación de sustitución (3) , la incógnita x1 es eliminada de las ecuaciones
segunda y tercera sustrayendo la primera de ambas. El sistema lineal equivalente es.

10 x1  5 x2 – 5 x3  5

  x2  9 x3  –13 …………………..(@)
  5 x2  25 x3  35


Ahora, la variable x2 se elimina de la tercera ecuación de (@) restándole a dicha ecuación el

quíntuple de la segunda, lo que nos lleva a un sistema equivalente que es triangular superior

10 x1  5 x2 – 5 x3  5

  x2  9 x3  –13
  20 x3  100


Finalmente, usamos el algoritmo de sustitución regresiva para hallar las incógnitas.

100
x3   5
20
x2  9(5)  13  32
5(32)  5(5)  5
x1   14
10

La forma eficaz de trabajar es almacenar todas las constantes del sistema lineal AX  B En una
matriz de orden N  ( N  1) que se obtiene añadiendo a la matriz A una columna, la columna
(N  1) -ésima, en la que se almacena los términos de B (es decir, akN 1  bk ). Cada fila de su
matriz, que se llama matriz ampliada del sistema y se denota por  A | B , contiene toda la
información necesaria para representar la correspondiente ecuación del sistema lineal:

 a11 a12 ... a1N b1 

 
a a22 ... a2 N b2 
 A | B    :21 : : : 
…………………..(7)
 
 aN 1 aN 2 ... aNN bN 

Un sistema AX  B , cuya matriz amplia viene dad en (7), puede resolverse realizando las
operaciones elementales con las filas de la matriz amplia  A | B . Las variables xk no sirven más
que para marcar el sitio de los coeficientes y pueden ser omitidas hasta el final de los cálculos.
OPERACIONES ELEMENTALES CON LAS FILAS

Teorema.- Cualquiera de las siguientes operaciones aplicada a la matriz ampliada (7) produce un
sistema lineal equivalente.

(8) Intercambio: El orden de las filas pude cambiarse.

(9) Escalado: Multiplicar una fila por una constante no nula.

(10) Sustitución: Una fila pude ser reemplazada por la suma de esa fila mas un múltiplo
de cualquier otra fila; o sea, filar  filar  mrq  filaq .

Como se conoce de los cursos previos de algebra lineal, la fórmula habitual de usar (10) es
reemplazar una fila por la diferencia entre esa fila y un múltiplo de otras.

PIVOTES Y MULTIPLICADORES

Definición.- El elemento aqq de la matriz de los coeficientes en el paso q+1 que se usara en la
eliminación de arq , para r  q  1, q  2,..., N , se llama q-ésimo pivote y la q-ésima se llama fila

pivote, los números mrq  arq / aqq  r  q  1, q  2,..., N  por los que se multiplica la fila pivote
para restarla de las correspondientes filas posteriores se llama multiplicadores de la eliminación.

El siguiente ejemplo muestra cómo se usan las operaciones descritas en el teorema 3.8 para obtener
un sistema triangular superior UX  Y que sea equivalente a un sistema lineal AX  B en el que
A es una matriz de orden N  N .

Ejemplo

9.13 Resuelva el sistema:

 x1  x2 – x3  –3

6 x1  2 x2  2 x3  2
 –3x  4 x  x  1
 1 2 3

Solución

La matriz aplicada es:

Pivote   1 1 1 3
 
m21  6  6 2 2 2 
m31  3  3 4 1 1 
 1 1 1 3
 
Pivote  0 4 8 20 
m32  1.75  0 7 2 8

 1 1 1 3 
 
 0 4 8 20 
 0 0 12 27 

La solución se termina realizando por sustitución

27
x3   2.25
12
20  8(2.25)
x2   0.5
4
x1  3  (0.5)  (2.25)  0.25

GAUSS-JORDAN
Definición
El método de Gauss-Jordan es una variación de la eliminación de Gauss. La principal diferencia
consiste en que cuando una incógnita se elimina en el método de Gauss-Jordan, ésta es eliminada de
todas las otras ecuaciones, no sólo de las subsecuentes. Además, todos los renglones se normalizan
al dividirlos entre su elemento pivote. De esta forma, el paso de eliminación genera una matriz
identidad en vez de una triangular (figura 9.9).
En consecuencia, no es necesario usar la sustitución hacia atrás para obtener la solución.
El método se ilustra mejor con un ejemplo.

Ejemplo
Método de Gauss-Jordan Planteamiento del problema. Con la técnica de Gauss-Jordan resuelva el
sistema del ejemplo:
2 x1 – 6 x2 – x3  –38

 –3x1 – x2  7 x3  –34
 –8 x  x – 2 x  –20
 1 2 3

Solución
2   2 6 1 38 
 
 3 1 7 34 
 8 1 2 20 

 1 3 0.5 19 
 
m21  3  3 1 7 34 
m31  8  8 1 2 20 
 1 3 0.5 19 
 
10  0 10 5.5 91 
(1)  0 23 6 172 

m12  3 1 3 0.5 19 

 
0 1 0.55 9.1 
m32  23 0 23 6 172 

1 0 2.15 8.3 
 
0 1 0.55 9.1 
18.65  0 0 18.65 37.3

m13  2.15 1 0 2.15 8.3

 
m23  0.55 0 1 0.55 9.1
0 0 1 2 

1 0 0 4 
 
0 1 0 8 
0 0 1 2 

Donde los resultados será:

x1  4
x2  8
x3  2

PROGRAMACION

TRIANGULACION SUPERIOR SEGUIDA DE SUSTITUCION REGRESIVA.- Calculo de la

solución del sistema lineal AX  B mediante la reducción a forma triangular superior de la matriz
amplia [A | B] seguida de la sustitución regresiva.

function X=uptrbk(A,B)
%Datos
% -A es una matriz invertible de orden N x N
% -B es una matriz de orden N x 1
%Resultados
% -X es una matriz de orden N x 1 que contiene
% la solucion de AX=B.
%Inicializamos X y una matriz C que sirve de almacentemp
[N N]=size(A);
X=zeros(N,1);
C=zeros(1,N+1);
%Calculo de la matriz ampliada Aug=[A|B]
Aug=[A B];
for q=1:N-1
%Pivote parcial en la columna q-esima
[Y,j]=max(abs(Aug(q:N,q)));
%Intercambiamos las filas q-esima y (j+q-1)-esima
C=Aug(q,:);
Aug(q,:)=Aug(j+q-1,:);
Aug(j+q-1)=C;
if Aug(q,q)==0
'A es singula. No hay solucion o no es unica.';
break
end
%Proceso de eliminacion en la columna q-esima
for k=q+1:N
m=Aug(k,q)/Aug(q,q);
Aug(k,q:N+1)=Aug(k,q:N)-m*Aug(q,q:N+1);
end
end
%Sustitucion regresiva en [U|Y] usando el programa 3.1
X=backsub(Aug(1:N,1:N),Aug(1:N,N+1));

PROBLEMAS RESUELTOS

PROBLEMA 1.- Use la eliminación de Gauss para resolver el sistema que sigue:

8 x1  2 x2 – 2 x3  –2

10 x1  2 x2  4 x3  4
12 x  2 x  2 x  6
 1 2 3

Emplee pivoteo parcial y compruebe las respuestas sustituyéndolas en las ecuaciones originales.

Solución
pivote   8 2 2 2 
 
m21  1.25 10 2 4 4 
m31  1.5 12 2 2 6 

8 2 2 2 
 
pivote  0 0.5 6.5 6.5
m31  2 0 1 5 9 
 8 2 2 2 
 
0 0.5 6.5 6.5
0 0 8 4 

La solución se termina realizando por sustitución

4
x3   0.5
8
6.5  6.5(0.5)
x2   6.5
0.5
2  (2)(0.5)  2(6.5)
x1   1.5
8

Comprobando las respuestas sustituyéndolas en las ecuaciones originales.

8 x1  2 x2 – 2 x3  –2  8 1.5   2  6.5  – 2  0.5   –2  – 2  –2

10 x1  2 x2  4 x3  4  10 1.5  2  6.5  4  0.5  4  44
12 x1  2 x2  2 x3  6  12 1.5   2  6.5   2  0.5  6  66

PROBLEMA 2.- la matriz de hilbert es un ejemplo clasico de matriz mal condicionada: cambios
pequeñosen sus coeficientes provocan cambios grandes en la solucion del sistema perturbado.

Calcule la solucion exacta de AX  B (deje todos los numeros como fracciones y utilice
aritmetica exacta) siendo la matriz de los coeficientes la matriz de Hilbert de orden 4x4
dada por:
 1 1 1
1 2 3 4
  1 
1 1 1 1
0
2 5
 , B   
3 4
A
1 1 1 1

0

3 4 5 6 0
1 1 1 1
 
4 5 6 7

Solución
  1 1 1 1
1 2 3 4 
 
1 1 1 1 1 0
m21  
2 2 3 4 5 
 
1 1 1 1 1 
m21    0
3 3 4 5 6 
1 1 1 1 1 
m21    
4 4 5 6 7 0

 1 1 1 1 
1 2 3 4 1 
 
  0
12 1 1 3 1

1  12 12 40 2
 
1 1 4 1 1
m32   0 
1  12 45 12 3
9  3 1 9 1
m42   0  
10  40 12 112 4

1  1 1 1 1 
m12   1
2  2 3 4 1 

0 1 1
9

6
 10 1
 
180 1 1 1 
  0 0
1  180 120 6 
3  1 9 1 
m43   0 0 
2  120 700 5 

1  1 1 4 
m13    1 0   
6 6 5 1
 
m23   0
1 9 6 
1 1 
1  10 1 
 
0 3 30 
0 1
 2 1 
2800  1 1
  0 0 0  
1  2800 20 
 1  9 
m14   1 
20 1 0 0 1
 20 
m24    
3 36 
3 
5 0 1 0  1 
 5 
3 30 
m34    3
2 0 0 1 1 
 2
140 
0 0 0 1  
 1 

1 0 0 0 16 
 
0 1 0 0 120 
0 0 1 0 240 
 
0 0 0 1 140 

La solución

x1  16
x2  120
x3  240
x4  140

FACTORIZACIÓN LU:

El concepto de factorización triangular o factorización LU de una matriz triangular inferior L ,

cuyos elementos en la diagonal principal son todos iguales a 1 , por una matriz triangular superior
U , cuyos elementos diagonales son distintos de cero. Para facilitar la notación, ilustraremos los
conceptos con matrices de orden 4  4 , pero se aplican a matrices de orden arbitrario N  N .

1. Definición:
Diremos que una matriz invertible A admite una factorización LU si puede expresarse
como el producto de una matriz triangular inferior L , cuyos elementos diagonales son
todos iguales a 1 , por una matriz triangular superior U :

(1) A  LU

O escrito de manera desarrollada:

  a11 a12 a13 a14   1 0 0 0 u11 u12 u13 u14 
a a24   m21 1 0  0 u22 u23 u24 
 21 a22 a23

0
 a31 a32 a33 a34   m31 m32 1 0  0 0 u33 u34 
    
 a41 a42 a43 a44   m41 m42 m43 1  0 0 0 u44 

La condición de que A sea invertible implica que ukk  0 para todo k .La notación para
los elementos de L es mij ; la razón para elegir mij en vez de lij la daremos enseguida.

2. Solución de un sistema lineal:

Supongamos que la matriz de los coeficientes de A de un sistema lineal AX  B admite
una factorización triangular como la de (1) , entonces la solución de:

(2) LUX  B

Puede obtenerse definiendo Y  UX y resolviendo dos sistemas lineales:

(3) primero se halla Y en LY  B y luego X en UX  Y

En forma desarrollada, primero debemos resolver el sistema triangular inferior

y1  b1
m21 y1  y2  b2
(4)
m31 y1  m32 y2  y3  b3
m41 y1  m42 y2  m43 y3  y4  b4

Para obtener y1 , y2 , y3 e y4 y, una vez que los tenemos, resolver el sistema triangular superior

u11 x1  u12 x2  u13 x3  u14 x4  y1

u22 x2  u23 x3  u24 x4  y2
u33 x3  u34 x4  y3
u44 x4  y4

Y con el método de sustitución regresiva se halla x1 , x2 , x3 e x4 .

 EJERCICIOS RESUELTOS

EJERCICIO 1.- Halle la factorización triangular A  LU de la siguiente matriz; (*Problema

propuesto 3 de la pag 180 chapra)

 5 2 1
1 0 3
 
 3 1 6 

Solución:
Usando el método descrito antes y sabiendo que la matriz de los coeficientes admite la
factorización triangular

 5 2 1  1 0 0 u11 u12 u13 

A   1 0 3   l21 1 0  0 u22 u23   LU
 3 1 6  l31 l32 1   0 0 u33 

Hallando U y en el proceso construimos L :

 5 2 1 (1 / 5) ;(3 / 5)

1 0 3
 
 3 1 6 
...(1)

 5 2 1 
 0 2 / 5 14 / 5   11 
    ...(2)
 2 
 0 11 / 5 27 / 5

 5 2 1 
 0 2 / 5 14 / 5
 
 0 0 10 

Nuestra matriz U será:

 5 2 1 
U   0 2 / 5 14 / 5

 0 0 10 
Nuestra matriz L será:

Si en (1) :
a21 1 a31 3
a11  5 
 l21   y l31  
a11 5 a11 5
Si en (2) :

2 11
a32 11
a22  
 l32   5
5 a22 2 2
5

 1 0 0

L   1 / 5 1 0
 3 / 5 11 / 2 1 

Entonces:

 5 2 1  1 0 0  5 2 1 
  
A   1 0 3    1 / 5 1  
0  0 2 / 5 14 / 5  LU
 3 1 6   3 / 5 11 / 2 1   0 0 10 
EJERCICIO 2.- Resolver el sistema AX  B siendo (*Problema propuesto 1de la pag
181 chapra)

1 3 5 7 1 
 2 1 3 5  2
A y B 
0 0 2 5 3
   
 2 6 3 1 4

Solucion

Hallando U y en el proceso encontraremos L :

1 3 5 7  ( 2) ;(2)
 2 1 3 5 
 ...(1)
0 0 2 5
 
 2 6 3 1

1 3 5 7 
0 7 7 9 
   7  ...(2)
0 0 2 5    
  2 
0 0 7 15 

1 3 5 7 
0 7 7 9 

0 0 2 5 
 
0 0 0 5 / 2 

Nuestra matriz U será:

1 3 5 7 
0 7 7 9 
U 
0 0 2 5 
 
0 0 0 5 / 2 

Nuestra matriz L será:

Si en (1) : 
 a11  1
a21 2 a31 0 a 2
l21   2 ; l31    0 y l41  41   2
a11 1 a11 1 a11 1
Si en (2) : 
 a22  1
a32 0 a42 0
l32   0 y l42   0
a22 7 a22 7
Si en (2) : 
 a33  2
a43 7
l43  
a33 2
1 0 0 0
2 1 0 0 
L
0 0 1 0
 
 2 0 7/2 1

Entonces:

1 3 5 7  1 0 0 0  1 3 5 7 
 2 1 3 5   2 1 0  
0  0 7 7 9 
A   LU
0 0 2 5  0 0 1 0  0 0 2 5 
    
 2 6 3 1   2 0 7/2 1  0 0 0 5 / 2 

Usando el algoritmo de sustitución progresiva resolvemos LY  B :

y1  1

2 y1  y2 2

y3 3

2 y1  7 y  y4 4
2 3

Obteniendo:
y1  1 ; y3  3
7(3) 9
y2  2  2(1)  0 ; y4  4  2(1)    4.5
2 2
Osea: Y  [1 0 3 4.5]'

Ahora escribiremos el sistema UX  Y :

 x1  3x2 5 x3 7 x4 1

7 x2 7 x3 9 x4 0

2 x3 5 x4 3
5 x  9 / 2
2 4
Utilizando el método de sustitución regresiva, se obtendrá:
9 7(3)  9(1.8) 24
x4  2  9  1.8 ; x2    0.685714
5 5 7 35
2
3  5(1.8) 3(24) 47
x3   3 ; x1  1   5(3)  7(1.8)   1.342857
2 35 35

47 24
Obteniendo como resultado final: X [ 3 1.8]'
35 35
PROGRAMACIÓN DEL MÉTODO

►PARA EL EJERCICIO 1 TENEMOS EL SIGUIENTE PROGRAMA:

Para poder corroborar los resultados hacemos lo siguiente:

Pasos:
 Abrir nuestro programa que en este caso utilizaremos el MATLAB .

 Escribir en la ventana de comando edit. para poder allí escribir nuestro código:

 Escribir el código en el script que se ha abierto, al cual le daremos el nombre de

slu(A)
function [L,U]=slu(A)
[n,n] = size(A);
for k = 1:n
if abs(A(k, k)) < sqrt(eps)
disp(['Pivote muy pequeño encontrado en columna' int2str(k)
'.'])
end
L(k,k) = 1;
for i = k+1:n
L(i,k) = A(i,k) / A(k,k);
for j = k+1:n
A(i,j) = A(i,j) - L(i,k)*A(k,j);
end
end
for j = k:n
U(k,j) = A(k,j);
 end
end

 Comprobaremos el resultado :

>> A=[-5 2 -1;1 0 3;3 1 6];

>> [L,U]=slu(A)

L=

1.00 0 0
-0.20 1.00 0
 -0.60 5.50 1.00

U=

-5.00 2.00 -1.00

0 0.40 2.80
0 0 -10.00

►PARA EL EJERCICIO 2 TENEMOS EL SIGUIENTE PROGRAMA:

Para poder corroborar los resultados hacemos lo siguiente:

Pasos:
 Abrir nuestro programa que en este caso utilizaremos el MATLAB .

 Escribir en la ventana de comando edit. para poder allí escribir nuestro código:

>> edit
 Escribir el código en el script que se ha abierto, al cual le daremos el nombre de
lufact(A,B)
function X=lufact(A,B)
%Datos
%A : es una matriz de orden NxN
%B : es una matriz de orden Nx1
%Resultado
%X : es la matriz de orden Nx1 solucion de AX=B
%inicializamos X,Y la matriz de almacenamiento temporal C
%y la matriz fila R donde se registran los intercambios de filas
[N,N]=size(A);
X=zeros(N,1);
Y=zeros(N,1);
C=zeros(1,N);
R=1:N;
for q=1:N-1
%determinacion de las filas q-esima y j-esima
[max1,j]=max(abs(A(q:N,q)));
%intercambio de filas q-esima y j-esima
C=A(q,:);
A(q,:)=A(j+q-1,:);
A(j+q-1,:)=C;
d=R(q);
R(q)=R(j+q-1);
R(j+q-1)=d;
if A(q,q)==0
disp('A essingular, no hay solucion o no es unica');
break
end
%calculo del multiplicador
%que se guarda en la parte sub diagonal de A
for k=q+1:N
mult=A(k,q)/A(q,q);
A(k,q)=mult;
A(k,q+1:N)=A(k,q+1:N)-mult*A(q,q+1:N);
end
end
%resolucion para hallar Y
Y(1)=B(R(1));
for k=2:N
Y(k)=B(R(k))-A(k,1:k-1)*Y(1:k-1);
end
%resolucion para hallar X
X(N)=Y(N)/A(N,N);
for k=N-1:-1:1
X(k)=(Y(k)-A(k,k+1:N)*X(k+1:N))/A(k,k);
end

 Comprobaremos el resultado :
 >> A=[1 3 5 7;2 -1 3 5;0 0 2 5;-2 -6 -3 1];
>> B=[1;2;3;4];
>> lufact(A,B)

ans =

1.342857142857142
0.685714285714286
-3.000000000000000
1.800000000000000

La teoría y practica ambas he sácalo del libro CHAPRA