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: 
# Trocar dúas filas entre si.
# Multiplicar todos os elementos dunha fila por unha constante non nula.
# 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**: Obter 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{alignat}{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{alignat}

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} \ne 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)} \ne 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)} \ne 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)} \ne 0 .

## Exemplo 
Resolver o sistema de ecuacións seguinte:
:\begin{alignat}{7}
2x &&\; + \;&& 1y             &&\; + \;&& -3z  &&\; = \;&& -1  \\
-1x &&\; + \;&& 3y             &&\; + \;&& 2z &&\; = \;&& 12 \\
3x &&\; + \;&& 1y &&\; +\;&& -3z  &&\; = \;&& 0 
\end{alignat}

**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 \ne 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} \ne 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{alignat}{7}
2x &&\; + \;&& y             &&\; - \;&& 3z  &&\; = \;&& -1  \\
 &&\;  \;&& \frac{7}{2}y             &&\; + \;&& \frac{1}{2} z &&\; = \;&& \frac{23}{2}  \\
 &&\;  \;&&  &&\; \;&& \frac{11}{7}z  &&\; = \;&& \frac{22}{7}
\end{alignat}

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} 

## Notas 
## 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.&nbsp;332-338.
* Lay, David C. *Álgebra Linear e súas aplicacións.* 2ª ed. Río de Janeiro: LTC, 1999. p.&nbsp;6-16.
* Pazos, Rubén Panta. *Método de Eliminación de Gauss.* Dispoñíbel en: . Consultado o 23 de maio de 2013.