PDF de programación - Lección 10: Eliminación Gaussiana - Tutorial básico de MATLAB

Lección 10. Eliminación Gaussiana

MIGUEL ANGEL UH ZAPATA1
Análisis Numérico I
Facultad de Matemáticas, UADY

Septiembre 2014

1Centro 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
A + 2B + 4C = −1
1
A + 3B + 9C =

en (1, 1)
en (2,−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
0
2B + 8C =

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
4

2C =

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

a21 a22
...
...
an1 an2

[A | B] =



··· a1n
··· a2n
...
··· ann

b1
b2
...
bn

(1)

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

multiplicamos m21 = −
multiplicamos m31 = −
multiplicamos m41 = −



Análisis Numérico

por la primera línea y sumar la segunda línea

por la primera línea y sumar la tercera línea

por la primera línea y sumar la cuarta línea

a21
a31
a41

a11

a11

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
5
1
2 3
−1 1 −5
3
7 −2
3 1



 x1

x2
x3
x4

 =

 10

31
−2
18



Solución:

Primero consideremos la matriz en
su forma aumentada eliminando las
variables

Eliminando todos los elementos de-
bajo de a11 = 1

Eliminando todos los elementos de-
bajo de a22 = −1

Eliminando todos los elementos de-
bajo de a33 = −2

1
1
10
1
2 3
5
31
−1 1 −5
3 −2
7 −2
3 1
18

10
1
1
1
1 −3
0 −1
11
2 −4
8
4
0
0 −2
4 −5 −12

 1 1
 1
 1 1
 1 1

1
3

1
10
0 1 −1
11
0 0 −2 −2 −14
10
0 0

1

2

1
3

1
10
0 1 −1
11
0 0 −2 −2 −14
0 −1 −4
0 0






Eliminación Gaussiana

5

Ahora podemos aplicar el método de
sustitución hacia atrás dado que te-
nemos una matriz triangular supe-
rior. La solución es

x =



 1

2
3
4

Análisis Numérico

x4 = (−4)/(−1) = 4
x3 = (−14 + 2x4)/(−2) = 3
x2 = 11 + x3 − 3x4 = 2
x1 = 10 − x2 − x3 − x4 = 1

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

for i=j+1:n

% Para cada columna j<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)

+ A(i,j)*b(j);

= b(i)

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

Teorema.
Sea A una matriz no singular, y sean L y U definidas por

 u11 u12

u22
...
0

0
...
0

L =



··· u1n
··· u2n
...
...
··· unn

 1

m21
...
mn1

Análisis Numérico



···
···

0
0
0
1
...
...
··· mn,n−1 1

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

Esta es llamada la factorización LU de A.

LU = 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

U x = 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