Algoritmul lui Gauss

Eliminare Gaussiana

În fişierul de ieşire $gauss.out$ se vor afisa $M$ numere reale, cu precizia de 8 zecimale, reprezentand valorile sirului $x$, in cazul in care sistemul are solutie. In caz contrar, se va afisa mesajul $"Imposibil"$.

h2. Restricţii

h2. Restricţii şi precizări

* $1 ≤ N, M ≤ 300$
* $-1000 ≤ A{~i,j~} ≤ 1000$
* Solutia va fi considerata corecta daca, pentru fiecare $i$, $1 ≤ i ≤ N$, rezultatul expresiei $A{~i,1~} * x{~1~} + A{~i,2~} * x{~2~} + ... + A{~i,M~} * x{~M~}$ difera prin maxim $0.001$ de $A{~i,M+1~}$.

* Se recomandă afişarea rezultatului cu o precizie de $10^-10^$
* Dacă sunt mai multe soluţii posibile, oricare varianta corecta va fi acceptata.

h2. Exemplu

-2 1 2 -3
|2.00000000 3.00000000 -1.00000000
|

| 2 2
1 1 2
2 2 4
|0.50000000 1.50000000
|

h3. Explicatie

* $(-3) * 2 + (-1) * 3 + 2 * (-1) = -6 - 3 - 2 = -11$
* $(-2) * 2 + 1 * 3 + 2 * (-1) = -4 + 3 - 2 = -3$

Pentru exemplul 2 exista o infinitate de soluţii, o alta soluţie corecta este: $1.00000000 1.00000000$
 

h2. Indicatii de rezolvare
'Eliminarea Gaussiana':http://en.wikipedia.org/wiki/Gaussian_reduction este cel mai folosit algoritm pentru rezolvarea sistemelor de ecuatii liniare. Metoda reduce succesiv ecuatiile, lasand matricea initiala sub o forma din care vom putea afla usor valorile necunoscutelor. Astfel, notand cu $p{~i~}$ pozitia celui mai din stanga coeficient nenul de pe linia $i$, algoritmul garanteaza obtinerea urmatoarului sir de relatii: $p{~1~} < p{~2~} < ... < p{~N~} (1)$. Aceste pozitii vor fi chiar indicii necunoscutelor fixe, cele care pot lua o singura valoare pentru ca sistemul sa aiba in continuare solutie. Celelalte necunoscute, ale caror indici nu se regasesc printre aceste pozitii, pot lua orice valoare si se numesc variabile libere. Pentru a usura calculele, vom considera in continuare ca acestea iau valoarea $0$.