Eliminare Gaussiană

(Categoria Algoritmi, Autor Petru Trîmbiţaş)

Descriere

Eliminarea Gaussiană este o metodă de rezolvare a ecuaţiilor matriciale de forma $Ax=b$ .
Să presupunem că avem următorul sistem:

$\begin{pmatrix} a_{11} & a_{12} & \ldots & a_{1n}\\ a_{21} & a_{22} & \ldots & a_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ a_{n1} & a_{n2} & \ldots & a_{nn} \end{pmatrix} * \begin{pmatrix} x_{1} \\ x_{2} \\ \vdots \\ x_{n} \end{pmatrix} = \begin{pmatrix} b_{1} \\ b_{2} \\ \vdots \\ b_{n} \end{pmatrix}$

Pentru a rezolva sistemul vom transforma toate elementele de sub diagonala principală a matricei extinse în 0.

$\begin{pmatrix} a_{11} & a_{12} & \ldots & a_{1n} & b_{1}\\ a_{21} & a_{22} & \ldots & a_{2n} & b_{2}\\ a_{31} & a_{32} & \ldots & a_{3n} & b_{3}\\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \ldots & a_{nn} & b_{n} \end{pmatrix} \rightarrow \begin{pmatrix} a_{11} & a_{12} & \ldots & a_{1n} & b_{1}\\ 0 & a'_{22} & \ldots & a'_{2n} & b'_{2}\\ 0 & 0 & \ldots & a'_{3n} & b'_{3}\\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \ldots & a'_{nn} & b'_{n} \end{pmatrix}$

Având matricea sub această formă putem să aflăm uşor necunoscutele:
$\: x_{n}=\frac{b'_{n}}{a'_{nn}}$
$x_{n-1}=\frac{b'_{n-1}-a'_{n-1n}*x_{n}}{a'_{n-1n-1}}$
$\vdots$
$x_{i}=\frac{b'_{i}-\sum\limits_{j=i+1}^n a'_{ij}*x_{j}}{a'_{ii}}$