PDF de programación - Lección 11: Eliminación Gaussiana con Pivoteo y Matrices de Banda - Tutorial básico de MATLAB

Lección 11. Eliminación Gaussiana con Pivoteo
y Matrices de Banda

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

Septiembre de 2014

1Centro de Investigación en Matemáticas, Unidad Mérida.

En esta lección estudiaremos la necesidad del
pivoteo en la solución de sistemas lineales usando
eliminación Gausianna y conoceremos el caso
especial de las matrices triangulares.

Al final debemos de:

modificar nuestro algoritmo para considerar
el pivoteo.

resolver de manera eficiente los sistemas tri-
diagonales.

Análisis Numérico

Eliminación Gaussiana con Pivoteo

Muchas veces en el método de eliminación Gaussiana aparece el problema que el elemento de la
diagonal es cero. Es decir, 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. Lo que se hace es
intercambiar la fila k−ésima con alguna fila posterior para conseguir un elemento pivote que no sea
cero, este procedimiento es llamado eliminación Gaussiana con pivoteo parcial escalado; si esto no
puede hacerse, entonces la matriz de los coeficientes del sistema es singular y el sistema no tiene
solución única o no tiene solución.

1. Eliminación Gaussiana con Pivoteo Parcial Escalado
Tener un elemento pivote igual a cero no es el único problema que se tiene cuando se aplica elimina-
ción Gaussiana. El elemento pivote puede llegar a ser muy pequeño en magnitud comparado al resto
de los elementos en la fila pivote. Ésto puede incrementar dramáticamente los errores de redondeo,
lo cual puede resultar en un vector solución inexacto.

Ejemplo:
Los valores x1 = 10.00 y x2 = 1.00 son las soluciones del sistema

0.0002000x1 + 1.471x2 = 1.473
0.2346x1 − 1.317x2 = 1.029

En este ejemplo se utilizarán 4 dígitos con error de redondeo.
El multiplicador para este sistema es m21 = 0.2346

0.0002 = 1173.

Aplicando eliminación Gaussiana y realizando los redondeos apropiados resulta:

0.0002000x1 + 1.471x2 = 1.473
−1726x2 = −1727

Por lo tanto,

x2 =

= 1.001

−1727
−1726
1.473 − (1.471)(1.001)
1.473 − 1.472
0.0002000

0.0002000

x1 =

=
= 5.000

Notar que x2 es una aproximación cercana al valor exacto. Sin embargo, el error relativo en la solu-
ción calculada para x1 es muy grande: 50 %. La falla de la eliminación Gaussiana en este ejemplo,
radica en el hecho de que |a11| = 0.0002 es pequeño comparado a |a12|.

Una estrategia útil para evitar el problema de tener un elemento pivote cero o muy pequeño, es
usar eliminación Gaussiana con pivoteo parcial escalado. En este método, las ecuaciones del sistema
Ax = b se usan en orden indistinto y el elemento pivote se selecciona buscando el coeficiente más
grande (en valor absoluto) de xk. Se ilustrará el método resolviendo el siguiente ejemplo.

Pivoteo

3

Ejemplo:
Si aplicamos el método de pivoteo parcial al ejemplo anterior tenemos que el sistema

Análisis Numérico

es cambiado a

obteniendo el multiplicador

entonces

Así



−1.317
1.471

−1.317
1.471

1.029
1.473

1.029
1.473

0.2346
0.2346

0.0002000

0.0002000

0.0002000

= 0.0008

m21 =

0.2346

0.2346 −1.317

0.0000

1.472



1.029
1.473

x2 =

1.472
1.473

= 0.9993

x1 =

=

=

1.029 − (1.317)(0.9993)
0.2346
1.029 − 1.316

0.2346

2.345
0.2346

= 9.995

Como podemos observar ahora si obtenemos soluciones cercanas a nuestro valor real.

2.

Implementación del algoritmo en MATLAB

El siguiente código es una implementación del algoritmo de eliminación Gaussianna con pivoteo par-
cial.

En el siguiente programa, la instrucción max se usa para determinar el pivote en la estrategia de
pivoteo parcial. Una vez que se tiene la matriz U del sistema triangular equivalente. Finalmente se
puede usar el algoritmo de sustitución regresiva para obtener la solución.

% gauss_pivoteo_parcial.m
% Resuelve el sistem Ax=b usando eliminación Gausianna con pivoteo.

function x = gauss_pivoteo_parcial(A,b)

%____________________________
% Tamaño de la solucion
n = length(b);
x = zeros(n,1);
%____________________________
% Matriz fila temporal
tempA = zeros(1,n+1);
%____________________________
% PRIMER PASO: simplificacion
for j=1:n-1

Pivoteo

4

Análisis Numérico

%------------------------
% Pivoteo parcial
[colmax,index]= max(abs(Au(i:n,i)));
%------------------------
% Intercambio de filas i & index
tempA = A(j,:);
tempB = b(j);
A(j,j:n) = A(index,j:n);
b(j) = b(index)
A(index,j:n) = tempA;
b(index)
%------------------------
% Advertencia de matriz singular
if A(i,i)==0}

= tempB

disp('A es singular. Muchas soluciones o ninguna solución')}
break

end
%------------------------
% Ciclo sobre cada elemento abajo de a_jj
for i=j+1:n

m = -A(i,j)/A(j,j)
A(i,j+1:n) = A(i,j+1:n) + m*A(j,j+1:n);
b(i)

= b(i)

+ m*b(j);

end

end
%____________________________
% SEGUNDO PASO: sustitucion regresiva
for i=n-1:-1:1

x(i) = (b(i)-A(i,i+1:n)*b(i+1:n))/A(i,i);

end

end

3. Sistemas tridiagonales

Cuando los coeficientes de la matriz A tiene una forma especial, es poisble simplificar la eliminación
Gaussiana. Este es el caso de las matrices triadiagonales.

Un sistema Ax = f es llamado tridiagonal si la matriz tiene la forma



A =

b1
a2
0
...

0
0

c1
b2
a3
...
···
···

0
c2
b3
...
0
···

0
c3
...
an−1

0

···
···
···
...
bn−1
an

0
0
0

0

cn−1
bn



Esta es una matriz tridiagonal. Este tipo de sistemas suelen ser muy comunes al momentos de resolver
varios problemas en el área de análisis numérico.

Cuando la eliminación gaussiana es aplicada a este sistemna, la mayoria de los multiplicadores mij =
0 y la mayoria de los elementos de U son cero. Con esto en mente, se puede probar que la factorización

Pivoteo

5



L =

LU tiene la siguiente forma general

1
α2

1
α3

1
...

...
αn−1

1
αn

1

Análisis Numérico





U =

β1

c1
β2

c2
β3

c3
...



...
βn−1

cn−1
βn

en este caso el método de pivoteo no es usado. Multiplicando sucesivamente cada fila de L con las
diferentes columnas de U y adecuando los resultados a los correspondientes elementos de A tenemos
que

β1 = b1

α2β1 = a2, α2c1 + β2 = b2

αjβj−1 = aj, αjcj−1 + βj = bj

j = 3, ..., n

para la primera, segunda y j-ésima fila de LU. Las ecuaciones pueden ser fácilmente resultas para
los elementos αj y βj

β1 = b1

aj
βj−1

αj =
βj = bj − αjcj−1

j = 2, 3, ..., n

Entonces el systema de ecuaciones ha sido convertido en un par de ecuaciones triangulares

Realizando sustitución hacia adelante del sistema Lg = f obtenemos que

Lg = f

U x = g.

g1 = f1
gj = fj − αjgj−1

j = 2, 3, ..., n

y haciendo sustitución hacia atrás del sistema U x = g obtenemos que

xn =

xj =

gn
βn
gj − cjxj+1

βj

j = n − 1, ..., 1

Este procedimiente es extremadamente rápido, con unnúmero de operaciones de sólo 5n − 4 mul-
tiplicaciones y divisiones (en eliminación Gaussiana el número total de operaciones es alrededor de
3 n3). También para guardar la matriz A se necesita poca memoria dado que sólo las tres diagonales
1
son guardadas.

Pivoteo

6