Lección 10.

Eliminación Gaussiana

MIGUEL ANGEL UH ZAPATA1

Análisis Numérico I
Facultad de Matemáticas, UADY

Septiembre 2014

1
Centro de Investigación en Matemáticas, Unidad Mérida.
En esta lección analizaremos los errores al reali-
zar operaciones con los números punto flotante.
Al final debemos de:
En base al análisis de errores indicar si
distintas operaciones aritméticas con pun-
to flotante son bien condicionadas o no.

Explicar la razón por la cual tenemos

pérdida de dı́gitos significativos en la res-
ta de dos números muy parecidos.
 Análisis Numérico

Eliminación Gaussiana
En esta sección se desarrollará un método para resolver un sistema de ecuaciones lineales ge-
neral Ax = b de n ecuaciones con n incógnitas. El objetivo es construir un sistema triangular
superior equivalente U x = y que se pueda resolver usando el método de sustitución regresiva.

1. Motivación del algoritmo

A continuación consideraremos el siguiente ejemplo donde se requiere la solución de un sistema
lineal de tamaño 3 × 3. En este se usa uno de los procedimientos más comunes para de solución
de este sistema lineal.

Ejemplo:
Determinar la parábola de ecuación y = A + Bx + Cx2 que pasa por los puntos (1, 1), (2, −1)
y (3, 1).

Solución:
Para cada punto se obtiene una ecuación que relaciona el valor de la abscisa x con el de la
ordenada y. El resultado es el sistema lineal
A+B+C = 1 en (1, 1)
A + 2B + 4C = −1 en (2, −1)
A + 3B + 9C = 1 en (3, 1)
Aplicando la transformación de sustitución, la incógnita A es eliminada de la segunda y tercera
ecuaciones sustrayendo la primera de ambas. El sistema lineal equivalente es
A+B+C = 1
B + 3C = −2
2B + 8C = 0
Ahora, la variable B se elimina de la tercera ecuación, restándole a dicha ecuación el doble de
la segunda, lo que resulta en un sistema equivalente que es triangular superior:
A+B+C = 1
B + 3C = −2
2C = 4
Finalmente, se usa el algoritmo de sustitución regresiva para hallar las incógnitas, los coeficien-
tes de la ecuación de la parábola: C = 4/2 = 2, B = −2−3(2) = −8 y A = 1−(−8)−2 = 7,
con lo que dicha ecuación es y = 7 − 8x + 2x2 .

2. Sistemas equivalentes
Se dice que dos sistemas de orden n × n son equivalentes cuando tienen el mismo conjunto de
soluciones. El siguiente teorema establece que hay ciertas transformaciones que no cambian el
conjunto de soluciones de un sistema de ecuaciones lineales.

Eliminación Gaussiana 3
 Análisis Numérico

Teorema (Transformaciones elementales):

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 reemplazarse por la suma ella misma más un múlti-
plo de otra ecuación.

Una 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 almacenan los términos de b (es decir, ak,n+1 = bk ). Cada fila de
esta matriz, que se llama matriz aumentada 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
 a21 a22 · · · a2n b2 
[A | B] =  . (1)
 
.. .. .. 
 .. . . . 
an1 an2 · · · ann bn

Un sistema Ax = b, cuya matriz aumentada está dada por (1), puede resolverse realizando las
operaciones elementales con las filas de la matriz aumentada [A | b]. Las variables xk no sirven
más que para marcar el sitio de los coeficientes y pueden omitirse hasta el final de los cálculos.

Teorema (Operaciones elementales con las filas).

Cualquiera de las siguientes operaciones aplicada a la matriz aumentada (1) produce un
sistema lineal equivalente.

1. Intercambio: El orden de las filas pueden cambiarse.

2. Escalado: Multiplicar una fila por una constante no nula.

3. Sustitución: Una fila puede reemplazarse por la suma de esa fila más un múltiplo de
cualquier otra fila.

3. Algoritmo de Eliminación Gaussiana

El siguiente ejemplo muestra cómo se usan las operaciones descritas en el teorema anterior para
obtener un sistema triangular superior U x = y que sea equivalente a un sistema lineal Ax = B
en el que A es una matriz de orden n × n.

El procedimiento es simple. Primero eliminamos todos los elementos debajo de a11 (el primer
pivote). Para esto

Eliminación Gaussiana 4
 Análisis Numérico

 
a21
multiplicamos m21 =− por la primera lı́nea y sumar la segunda lı́nea
 a11 
a31
multiplicamos m31 =− por la primera lı́nea y sumar la tercera lı́nea
 a11 
a41
multiplicamos m41 =− por la primera lı́nea y sumar la cuarta lı́nea
a11
Y ası́ progresivamente hasta tener una matriz triangular superior. Es importante recalcar que los
valores mij juegan un papel muy importante en este procedimiento.

Ejemplo:
Resolver el siguiente sistema lineal
    
1 1 1 1 x1 10
 2 3 1 5   x2   31 
  x3  =  −2
    
 −1 1 −5 3 
3 1 7 −2 x4 18

Solución:

Primero consideremos la matriz en

su forma aumentada eliminando las  
1 1 1 1 10
variables  2
 3 1 5 31 

 −1 1 −5 3 −2 
3 1 7 −2 18
Eliminando todos los elementos de-
bajo de a11 = 1  
1 1 1 1 10
 0 −1 1 −3 11 
 
 0 2 −4 4 8 
0 −2 4 −5 −12
Eliminando todos los elementos de-
bajo de a22 = −1  
1 1 1 1 10
 0
 1 −1 3 11 

 0 0 −2 −2 −14 
0 0 2 1 10
Eliminando todos los elementos de-
bajo de a33 = −2  
1 1 1 1 10
 0
 1 −1 3 11 

 0 0 −2 −2 −14 
0 0 0 −1 −4

Eliminación Gaussiana 5
 Análisis Numérico

Ahora podemos aplicar el método de

sustitución hacia atrás dado que te-
nemos una matriz triangular supe- x4 = (−4)/(−1) = 4
rior. La solución es x3 = (−14 + 2x4 )/(−2) = 3
 
1 x2 = 11 + x3 − 3x4 = 2
 2  x1 = 10 − x2 − x3 − x4 = 1
x=  3 


4
El proceso que se acaba de describir se llama eliminación Gaussiana o método de eliminación de
Gauss, pero se debe modificar si se desea que funcione en casi todas las situaciones. El problema
que puede aparecer es el siguiente: Si akk = 0, entonces no se puede usar la fila k−ésima para
eliminar los elementos de la columna k−ésima que están por debajo de la diagonal principal.
En la siguiente lección veremos como solucionar este problema.

4. Implementación del algoritmo en MATLAB

El siguiente código es una implementación eficiente del algoritmo de eliminación Guasianna.
Este programa puede fallar para los problemas donde es necesario pivoteo.

% gauss.m
% Resuelve el sistem Ax=b usando eliminación Gausianna sin pivoteo.
function x = gauss(A,b)

n = length(b);
x = zeros(n,1);
%____________________________
% PRIMER PASO: simplificacion
for j=1:n-1 % Para cada columna j<n
for i=j+1:n % Ciclo sobre cada elemento abajo de a_jj
A(i,j) = -A(i,j)/A(j,j)
A(i,j+1:n) = A(i,j+1:n) + A(i,j)*A(j,j+1:n);
b(i) = b(i) + A(i,j)*b(j);
end
end
%____________________________
% SEGUNDO PASO: sustitucion regresiva
for i=n-1:-1:1
b(i) = (b(i)-A(i,i+1:n)*b(i+1:n))/A(i,i);
end

end

5. Factorización LU
La matriz de coeficientes A de un sistema lineal Ax = b puede ser factorizado en el producto de
dos matrices triangulares. El resultado de esta factorización esta dada por el siguiente teorema.

Eliminación Gaussiana 6
 Análisis Numérico

Teorema.
Sea A una matriz no singular, y sean L y U definidas por
   
u11 u12 · · · u1n 1 0 ··· 0
 0 u22 · · · u2n   m21 1 ··· 0 
L= .
   
. .. . . ..   .. .. .. 
 . . . .   . . . 
0 0 · · · unn mn1 · · · mn,n−1 1

Si U es producida mediante elemininación Gausianna descrita anteriormente, entonces

LU = A.

Esta es llamada la factorización LU de A.

Podemos observar que los valores de la matriz triangular inferior corresponden a los valores mij
relacionados a los pivotes durante la eliminación Gaussiana.

La factorización LU nos da otra perspectiva de la eliminación Gaussiana. Resolver el sistema

Ax = b es equivalente a resolver LU x = b. Y este a su vez es equivalente a resolver los dos
sistemas lineales
Ly = b
Ux = y
Si conocemos L entonces podemos resolver el sistema Ly = b usando sustitución hacia ade-
lante. Una vez conociendo los valores de y resolvemos el segundo sistema U x = y usando
sustitución hacia atrás como lo hemos hecho anteriormente.

Eliminación Gaussiana 7