Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2013-09-17 20:09:11.
Revizia anterioară   Revizia următoare  

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 pentru a putea scrie fiecare necunoscută doar în funcţie de necunoscutele cu indici mai mari.

\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 fiecare necunoscută din ecuaţia în care necunoscutele cu indici mai mici au coeficientul 0:
\: 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}}

Acum că ştim să aflăm necunoscutele din forma triunghiulară a matricei ne mai rămâne doar să transformăm matricea.
Pentru a transforma matricea în formă triunghiulară vom aplica două operaţii:
L_{i} \longleftrightarrow L_{j} : interschimbarea a două linii
L_{j} \longleftarrow L_{j}+a*L_{i} unde L_{i} este o linie a matricei extinse.

De exemplu:

\begin{pmatrix} 2 & 1 & -1 & 8 \\ -3 & -1 & 2 & -11 \\ -2 & 1 & 2 & -3 \end{pmatrix} \longrightarrow \begin{pmatrix} 2 & 1 & -1 & 8 \\ 0 & \frac{1}{2} & \frac{1}{2} & 1 \\ 0 & 2 & 1 & 5 \end{pmatrix} \longrightarrow \begin{pmatrix} 2 & 1 & -1 & 8 \\ 0 & \frac{1}{2} & \frac{1}{2} & 1 \\ 0 & 0 & -1 & 1 \end{pmatrix}

Aplicaţii

The magic matrix
https://apps.topcoder.com/wiki/display/tc/TCO+2013+Round+2A#TheMagicMatrix
Go2
Gxor

Bibliografie

  • http://en.wikipedia.org/wiki/Gaussian_elimination
  • http://mathworld.wolfram.com/GaussianElimination.html