ELIMINACIÓN
GAUSSIANA
Eliminación gaussiana.
La eliminación gaussiana es una herramienta eficaz para los sistemas de
ecuaciones lineales con un tamaño razonable.
Un sistema de dos ecuaciones con dos incógnitas puede considerarse en términos
del álgebra o bien de la geometría. Desde el punto de vista geométrico, cada
ecuación lineal representa una recta en el plano 𝑥𝑦, en el que las rectas se cruzan
satisface ambas ecuaciones y es la solución que se está buscando.
El punto de vista geométrico es muy útil para visualizar las soluciones de los
sistemas, pero para calcular la solución con una gran precisión es necesario
regresar al álgebra. El método conocido como la eliminación gaussiana es una
manera eficaz de resolver 𝑛 ecuaciones con 𝑛 incógnitas.
Eliminación gaussiana simple.
Se iniciará con la descripción de la forma más sencilla de la eliminación gaussiana. De
hecho, es tan sencilla que no se garantiza llegar hasta su terminación, y mucho menos
encontrar una solución precisa.
Existen tres operaciones útiles que pueden aplicarse a un sistema de ecuaciones
lineales para generar un sistema equivalente, es decir, un sistema que tenga las
mismas soluciones. Estas operaciones son las siguientes:
1. Intercambiar una ecuación por otra.
2. Sumar o restar un múltiplo de una ecuación de otra.
3. Multiplicar una ecuación por una constante diferente de cero.
Ejemplo.
Considere el sistema
𝑥+𝑦 =3
3𝑥 − 4𝑦 = 2
Solución:
es posible restar 3 veces la primera ecuación de la segunda a fin de eliminar la variable
𝑥 de la segunda ecuación. Si se resta 3[𝑥 + 𝑦 = 3] de la segunda ecuación, queda el
sistema:
𝑥+𝑦 =3
−7𝑦 = −7
A partir de la ecuación inferior, puede “resolverse hacia atrás" hasta encontrar una
solución completa, como en
−7𝑦 = −7 → 𝑦=1
y
𝑥+𝑦 =3 → 𝑥+ 1 =3 → 𝑥=2
Por lo tanto, la solución es 𝑥, 𝑦 = 2, 1 .
El mismo trabajo de eliminación puede hacerse en ausencia de variables al escribir el
sistema en forma de tabla:
La ventaja de la forma de tabla es que, durante la eliminación, las variables se ocultan.
Cuando el arreglo cuadrado del lado izquierdo de la tabla es “triangular”, es posible
resolver hacia atrás para obtener la solución, comenzando en la parte inferior.
Ejemplo.
Aplique la eliminación gaussiana en forma de tabla para el sistema de tres ecuaciones
con tres incógnitas:
𝑥 + 2𝑦 − 𝑧 = 3
2𝑥 + 𝑦 − 2𝑧 = 3
−3𝑥 + 𝑦 + 𝑧 = −6
Lo anterior se escribe en forma de tabla como
1 2 −1 3
2 1 −2 3
−3 1 1 −6
Se requieren dos pasos para eliminar la columna 1:
y un paso más para eliminar la columna 2 :
De regreso a las ecuaciones
𝑥 + 2𝑦 − 𝑧 = 3
−3𝑦 = −3
−2𝑧 = −4
De regreso a las ecuaciones
𝑥 = 3 − 2𝑦 + 𝑧
−3𝑦 = −3
−2𝑧 = −4
y resolver para 𝑧, 𝑦 y 𝑥, en ese orden. La parte final se denomina sustitución hacia
atrás o resolviendo hacia atrás porque, después de la eliminación, las ecuaciones se
resuelven con facilidad de abajo hada arriba. La solución es 𝑥 = 3, 𝑦 = 1, 𝑧 = 2.
Conteo de operaciones.
Lema.
Para cualquier entero positivo 𝑛,
! !"#
(a) 1 + 2 + 3 + 4 + ⋯ + 𝑛 = $ y
(b) 1$ + 2$ + 3$ + 4$ + ⋯ + 𝑛$ = 𝑛(𝑛 + 1)(2𝑛 + 1)/6
La forma general de la tabla para 𝑛 ecuaciones con 𝑛 incógnitas es
Para llevar a cabo la etapa de eliminación, es necesario poner ceros en el triángulo
inferior, utilizando las operaciones por renglón permitidas.
El paso de eliminación puede escribirse como el ciclo
for 𝑗 = 1 ∶ 𝑛 − 1
eliminate colum 𝑗
end
donde, “eliminate column j (eliminar la columna j), significa “usar operaciones por
renglón para poner un cero en cada lugar por debajo de la diagonal principal, que son
los lugares 𝑎%"# , 𝑎%"$ , … , 𝑎!% . Por ejemplo, para realizar la eliminación en la columna 1,
deben ponerse ceros en 𝑎$# , … , 𝑎!# . Esto puede escribirse como el siguiente ciclo
dentro del ciclo anterior:
for 𝑗 = 1 ∶ 𝑛 − 1
for 𝑖 = 𝑗 + 1 ∶ 𝑛
eliminate entry 𝑎 𝑖, 𝑗
end
end
Lo que resta es Henar el paso interior del doble ciclo, para aplicar una operación por
renglón que convierta la entrada 𝑎&% en cero. Por ejemplo, la primera entrada a eliminar
es la entrada 𝑎$# . Para lograr esto, se resta 𝑎$# /𝑎## veces el renglón 1 del renglón 2,
suponiendo que 𝑎## ≠ 0. Es decir, los dos primeros renglones cambian de
a
Si se cuentan las operaciones, esto requiere una división (para encontrar el
multiplicador 𝑎$# /𝑎## ), además de 𝑛 multiplicaciones y 𝑛 sumas. La operación por
renglón usada para eliminar la entrada 𝑎&# de la primera columna, es decir,
requiere un número similar de operaciones.
El procedimiento antes descrito se realiza mientras el número 𝑎## es diferente de
cero. Este número y los demás 𝑎&& que a la larga se convierten en divisores en la
eliminación gaussiana, se denominan pivotes. Un pivote igual a cero hará que el
algoritmo se detenga, como se ha explicado hasta ahora. Observe que la
eliminación de cada entrada 𝑎&# en la primera columna utiliza una división, 𝑛
multiplicaciones y 𝑛 adiciones/sustracciones, o 2𝑛 + 1 operaciones en total. La
colocación de ceros en la primera columna requiere una repetición de estas 2𝑛 +
1 operaciones un total de 𝑛 − 1 veces. Después de eliminar la primera columna, se
utiliza el pivote 𝑎$$ para eliminar la segunda columna de la misma manera y
después de eso las columnas restantes. Por ejemplo, la operación por renglón
usada para eliminar la entrada 𝑎&% es
En la notación empleada aquí, 𝑎$$ por ejemplo, se refiere al número modificado en
esa posición después de la eliminación de la columna 1. que no es el 𝑎$$ original.
La operación por renglón para eliminar 𝑎&% requiere una división, 𝑛 − 𝑗 +
1 multiplicaciones, y 𝑛 − 𝑗 + 1 sumas/restas.
Al insertar este paso en el mismo ciclo doble, resulta
Ahora son necesarios dos comentarios sobre este fragmento de código: en primer
lugar, cuando se pide al índice 𝑘 que pase de 𝑗 a 𝑛 se coloca un cero en la
ubicación 𝑎&% ; sin embargo, al pasar de 𝑗 + 1 a 𝑛 es una codificación más eficiente.
Ésta no pondrá un cero en la entrada 𝑎&% , ¡que era la entrada que se trataba de
eliminar! Aunque esto parece ser un error, observe que nunca se regresa a esta
entrada en el resto de la eliminación gaussiana o en el proceso de sustitución hacia
atrás. Así que en realidad la colocación de un cero en esa posición representa un
paso perdido desde el punto de vista de la eficiencia. En segundo lugar, se pide
que el código se detenga, con el comando error de Matlab , si se encuentra un
pivote cero. Como se mencionó esta posibilidad se considerará con mayor
seriedad cuando se analicen los intercambios de renglón.
Puede hacerse un conteo total de operaciones para el paso de eliminación de la
eliminación gaussiana. La eliminación de cada 𝑎&% requiere el siguiente número de
operaciones, incluyendo las divisiones, las multiplicaciones y las sumas/restas:
Resulta conveniente sumar las operaciones en orden inverso a cómo se aplican.
Empezando por la derecha, la suma total de las operaciones es
Conteo de operaciones para el paso de
eliminación en la eliminación gaussiana.
El naso de eliminación para un sistema de n ecuaciones con n variables puede
$ # (
completarse en 𝑛' + 𝑛$ − 𝑛 operaciones.
' $ )
En general, el conteo exacto de operaciones es menos importante que las estimaciones
del orden de magnitud, puesto que los detalles de la implementación en los diferentes
procesadores de computadora difieren. El punto principal es que el número de
operaciones es proporcional al tiempo de ejecución del algoritmo. Con frecuencia se
hace la aproximación de eliminación, que es una aproximación razonablemente exacta
cuando n es grande.
Después de completar la eliminación, la tabla es triangular superior:
En forma de ecuación,
donde, de nuevo, las 𝑎&% se refieren a las entradas modificadas, no a las originales.
Para completar el cálculo de la solución 𝑥 debe llevarse a cabo el paso de sustitución
hada atrás, que es tan sólo una reescritura:
Debido a la forma triangular de los coeficientes diferentes de cero en las ecuaciones,
se comienza desde abajo y se avanza hacia la ecuación superior. De esta manera, cada
𝑥& requerida se conoce cuando es necesaria para calcular la siguiente 𝑥& . Al contar las
operaciones se tiene
Ejercicios.
Resuelva los siguientes sistemas de ecuaciones.
𝑥# − 2𝑥$ + 3𝑥' = 11
4𝑥# + 𝑥$ − 𝑥' = 4
2𝑥# − 𝑥$ + 3𝑥' = 10
3𝑥# + 6𝑥$ − 6𝑥' = 9
2𝑥# − 5𝑥$ + 4𝑥' = 6
5𝑥# + 28𝑥$ − 26𝑥' = −8
𝑥# + 2𝑥$ + 3𝑥' = 9
4𝑥# + 5𝑥$ + 6𝑥' = 24
3𝑥# + 𝑥$ − 2𝑥' = 4
