Eliminación de Gauss

A eliminación de Gauss é un algoritmo para resolver sistemas de ecuacións lineares. Este método consiste en aplicar sucesivas operacións elementais nun sistema linear, para o transformar nun sistema de máis fácil resolución que teña as mesmas solucións que o orixinal.

Tamén é chamado método de escalonamento e eliminación de Gauss-Jordan.

Algúns conceptos

Definición de matriz graduada

Unha matriz rectangular está na súa forma graduada cando  satisfai as seguintes condicións:

• Todas as filas non nulas están por riba de calquera fila composta só de ceros.
• O primeiro elemento non nulo de cada fila está nunha columna á dereita do primeiro non nulo da fila superior.
• Todos os elementos dunha columna abaixo do primeiro elemento non nulo son cero.

Exemplo

$\left[{\begin{array}{rrrr}2&-3&2&1\\0&1&-4&8\\0&0&0&35\end{array}}\right]$

Se unha matriz está na forma graduada reducida satisfai as seguintes características adicionais:

• O primeiro elemento non nulo ("pivote") de cada fila non nula é 1.
• Cada pivote 1 é o único elemento non nulo da súa columna.

Exemplo

$\left[{\begin{array}{rrrr}1&0&0&12\\0&1&0&16\\0&0&1&1\end{array}}\right]$

Operacións elementais de filas

Existen tres operacións básicas que poden ser aplicadas a calquera tipo de sistema linear, sen que se alteren as solucións dos mesmos:

1. Trocar dúas filas entre si.
2. Multiplicar todos os elementos dunha fila por unha constante non nula.
3. Sumar a unha fila un múltiplo doutra fila.

Usando esas operacións, unha matriz sempre pode ser transformada nunha matriz triangular superior (forma graduada) e, posteriormente, ser posta en forma graduada reducida. Esta forma final, á súa vez, é única e independente da secuencia de operacións de fila usadas, sendo máis fácil de resolver que a versión orixinal da matriz. Tamén cómpre resaltar que estas operacións elementais son reversibles, sendo posible retornar ao sistema inicial aplicando a secuencia de operacións novamente, mais na orde inversa.

Problema xeral

Deséxase, a partir da utilización de operacións de fila, converter unha matriz na súa forma graduada reducida, e así, resolver máis facilmente o sistema de ecuacións asociado a aquela matriz. Para este fin, emprégase o método de eliminación de Gauss, sendo este composto por dúas fases:

• Fase de eliminación: con obxectivo empregar operacións elementais na matriz aumentada, a fin de obter unha correspondente a un sistema triangular superior.
• Fase de substitución retrocedida: comézase resolvendo a última ecuación, da que a solución é substituída na penúltima, a cal se resolve na penúltima variable, e así consecutivamente, até obterse a solución final.

Algoritmo

Sexa $Ax=b$ un sistema linear. O método de eliminación de Gauss para encontrar a solución do sistema consiste nas seguintes etapas:

• Etapa 1: Ob${\displaystyle }$ter a matriz aumentada na forma ${\begin{bmatrix}A|b\end{bmatrix}}$
• Etapa 2:Transformar a matriz ampliada ${\begin{bmatrix}A|b\end{bmatrix}}$ nunha matriz ampliada da forma ${\begin{bmatrix}{\bar {A}}|{\bar {b}}\end{bmatrix}}$ onde ${\bar {A}}$ é unha matriz triangular superior.
• Etapa 3: Resolver o sistema linear ${\begin{bmatrix}{\bar {A}}|{\bar {b}}\end{bmatrix}}$ da segunta etapa por substitución regresiva.

Etapa 1

Considérese o sistema linear de 3 ecuacións seguinte:

${\begin{alignedat}{7}a_{11}x_{1}&&\;+\;&&a_{12}x_{2}&&\;+\;&&a_{13}x_{3}&&\;=\;&&b_{1}&\qquad (L_{1})\\a_{21}x_{1}&&\;+\;&&a_{22}x_{2}&&\;+\;&&a_{23}x_{3}&&\;=\;&&b_{2}&\qquad (L_{2})\\a_{31}x_{1}&&\;+\;&&a_{32}x_{2}&&\;+\;&&a_{33}x_{3}&&\;=\;&&b_{3}&\qquad (L_{3})\end{alignedat}}$

A matriz ampliada A do sistema é: ${\begin{bmatrix}A|b\end{bmatrix}}^{(0)}$ = $\left[{\begin{array}{ccc|c}a_{11}&a_{12}&a_{13}&b_{1}\\a_{21}&a_{22}&a_{23}&b_{2}\\a_{31}&a_{32}&a_{33}&b_{3}\end{array}}\right]$

Etapa 2

Fase 1

Deséxase facer ceros todos os elementos da primeira columna abaixo da diagonal principal. Así, sendo $a_{11}\neq 0$, defínense as constantes $k=a_{21}/a_{11}$ e $w=a_{31}/a_{11}$ e fanse as seguintes operacións lineares:

$L_{2}^{(1)}\leftarrow L_{2}-k.L_{1}$

$L_{3}^{(1)}\leftarrow L_{3}-w.L_{1}$

Obténdose:

${\begin{bmatrix}A|b\end{bmatrix}}^{(1)}$ = $\left[{\begin{array}{ccc|c}a_{11}^{(1)}&a_{12}^{(1)}&a_{13}^{(1)}&b_{1}^{(1)}\\0&a_{22}^{(1)}&a_{23}^{(1)}&b_{2}^{(1)}\\0&a_{32}^{(1)}&a_{33}^{(1)}&b_{3}^{(1)}\end{array}}\right]$

Fase 2

Agora, débense facer ceros todos os elementos da segunda columna abaixo da diagonal principal. Sendo o pivote o elemento $a_{22}^{(1)}$ e a fila pivote a segunda fila de ${\begin{bmatrix}A|b\end{bmatrix}}^{(1)}$, suponse $a_{22}^{(1)}\neq 0$, e defínese unha nova constante $v=a_{32}^{(1)}/a_{22}^{(1)}$. Realizando a operación

$L_{3}^{(2)}\leftarrow L_{3}^{(1)}-v.L_{2}^{(1)}$

obtense:

${\begin{bmatrix}A|b\end{bmatrix}}^{(2)}$ = $\left[{\begin{array}{ccc|c}a_{11}^{(2)}&a_{12}^{(2)}&a_{13}^{(2)}&b_{1}^{(2)}\\0&a_{22}^{(2)}&a_{23}^{(2)}&b_{2}^{(2)}\\0&0&a_{33}^{(2)}&b_{3}^{(2)}\end{array}}\right]$

• Nota: ${\begin{bmatrix}A|b\end{bmatrix}}^{(2)}$ é unha matriz ampliada con matriz $A$ triangular superior.

Etapa 3

Resólvese o sistema ${\begin{bmatrix}A|b\end{bmatrix}}^{(2)}$. Así: $x_{3}=b_{3}^{(2)}/a_{33}^{(2)}$ $\ ,\ a_{33}^{(2)}\neq 0$

$x_{2}=(b_{2}^{(2)}-(a_{23}^{(2)}x_{3}))/a_{22}^{(2)}$

$x_{1}=(b_{1}^{(2)}-(a_{12}^{(2)}x_{2})-a_{13}^{(2)}x_{3})/a_{11}^{(2)}$

Así, encóntrase a solución ${\begin{Bmatrix}x_{1},\ x_{2},\ x_{3}\end{Bmatrix}}$ do sistema ${\begin{bmatrix}A|b\end{bmatrix}}^{(2)}$, que é a mesma solución de ${\begin{bmatrix}A|b\end{bmatrix}}$.

• Observación: o método de eliminación de Gauss só poderá empregarse para resolver sistemas lineares asociados a matrices graduadas reducidas con elementos das súas diagonais principais non nulos, ou sexa, $a_{11}^{(1)},a_{22}^{(2)},a_{33}^{(3)},...,a_{nn}^{(n)}\neq 0$.

Exemplo

Resolver o sistema de ecuacións seguinte:

${\begin{alignedat}{7}2x&&\;+\;&&1y&&\;+\;&&-3z&&\;=\;&&-1\\-1x&&\;+\;&&3y&&\;+\;&&2z&&\;=\;&&12\\3x&&\;+\;&&1y&&\;+\;&&-3z&&\;=\;&&0\end{alignedat}}$

Etapa 1: definir a matriz aumentada $\left[{\begin{array}{ccc|c}2&1&-3&-1\\-1&3&2&12\\3&1&-3&0\end{array}}\right]$

Etapa 2:

Fase 1: facer ceros os elementos da primeira columna baixo a diagonal principal

Como $a_{11}=2\neq 0$, defínese $\ k={\frac {a_{21}}{a_{11}}}={\frac {-1}{2}}$ e $\ w={\frac {a_{31}}{a_{11}}}={\frac {3}{2}}$ e calcúlanse os novos elementos da segunda e da terceira fila:

$a_{22}^{(1)}=a_{22}-k.a_{12}=3-({\frac {-1}{2}}).1={\frac {7}{2}}$

$a_{23}^{(1)}=a_{23}-k.a_{13}=2-({\frac {-1}{2}}).(-3)={\frac {1}{2}}$

$b_{2}^{(1)}=b_{2}-k.b_{1}=12-({\frac {-1}{2}}).(-1)={\frac {23}{2}}$

$a_{32}^{(1)}=a_{32}-w.a_{12}=1-({\frac {3}{2}}).1={\frac {-1}{2}}$

$a_{33}^{(1)}=a_{33}-w.a_{13}=-3-({\frac {3}{2}}).(-3)={\frac {3}{2}}$

$b_{3}^{(1)}=b_{3}-w.b_{1}=0-({\frac {3}{2}}).(-1)={\frac {3}{2}}$

Desa forma, a matriz resultante da etapa 1 é:

$\left[{\begin{array}{ccc|c}2&1&-3&-1\\0&{\frac {7}{2}}&{\frac {1}{2}}&{\frac {23}{2}}\\0&{\frac {-1}{2}}&{\frac {3}{2}}&{\frac {3}{2}}\end{array}}\right]$

Fase 2: facer ceros os elementos da segunda columna baixo a diagonal principal

Como $a_{22}^{(1)}={\frac {7}{2}}\neq 0$, defínese unha nova constante $v={\frac {a_{32}^{(1)}}{a_{22}^{(1)}}}={\frac {-1}{7}}$ e determínase os novos elementos da terceira fila:

A nova matriz ampliada tras esta segunda fase é:

$a_{33}^{(2)}=a_{33}^{(1)}-v.a_{23}^{(1)}={\frac {3}{2}}-({\frac {-1}{7}}).{\frac {1}{2}}={\frac {11}{7}}$

$b_{3}^{(2)}=b_{3}^{(1)}-v.b_{2}^{(1)}={\frac {3}{2}}-({\frac {-1}{7}}).{\frac {23}{2}}={\frac {22}{7}}$

A nova matriz aumentada tras esta segunda fase é:

$\left[{\begin{array}{ccc|c}2&1&-3&-1\\0&{\frac {7}{2}}&{\frac {1}{2}}&{\frac {23}{2}}\\0&0&{\frac {11}{7}}&{\frac {22}{7}}\end{array}}\right]$

Etapa 3:

Téndose obtido o sistema:

${\begin{alignedat}{7}2x&&\;+\;&&y&&\;-\;&&3z&&\;=\;&&-1\\&&\;\;&&{\frac {7}{2}}y&&\;+\;&&{\frac {1}{2}}z&&\;=\;&&{\frac {23}{2}}\\&&\;\;&&&&\;\;&&{\frac {11}{7}}z&&\;=\;&&{\frac {22}{7}}\end{alignedat}}$

que é un sistema triangular, obtense a súa solución facilmente por substitución das variables.

Da última ecuación temos:

$z={\frac {\frac {22}{7}}{\frac {11}{7}}}=2$

Substituíndo o valor de $z$ na segunda ecuación:

${\frac {7}{2}}y+{\frac {1}{2}}.2={\frac {23}{2}}$

logo,

$y={\frac {{\frac {23}{2}}-1}{\frac {7}{2}}}=3$

Finalmente, substituíndo os valores z = 2 e y = 3 na primeira ecuación:

$2x+3-3.2=-1$

resolvendo,

$x={\frac {-1-3+6}{2}}=1$

• Así, a solución para o sistema linear é: ${\begin{Bmatrix}1,3,2\end{Bmatrix}}$

Véxase tamén

Bibliografía

• Burden, Richard L. ; Faires, J. Douglas. Análise Numérica. 8ª ed. São Paulo: Cengage Learning, 2008. p. 332-338.
• Lay, David C. Álgebra Linear e súas aplicacións. 2ª ed. Río de Janeiro: LTC, 1999. p. 6-16.
• Pazos, Rubén Panta. Método de Eliminación de Gauss. Dispoñíbel en: http://rpanta.con/downloads/material/Gauss_01. Consultado o 23 de maio de 2013.