Algoritmul lui Gauss

Eliminare Gaussiana

h2. Date de ieşire

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

Î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 ≤ 100$
* $-100 ≤ A{~i,j~} ≤ 100$

* $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
table(example). |_. gauss.in |_. gauss.out |

| 2 1 -1 8

| 3 3
2 1 -1 8

-3 -1 2 -11
-2 1 2 -3

|2.0000 3.0000 -1.0000

|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$.

In continuare vom descrie algoritmul propriu zis. Pornim cu un indice pentru linii, sa-l notam $i$, si un indice pentru coloane, $j$, initializate initial cu $1$. Cautam pe coloana $j$, o linie $x$, $i ≤ x$ astfel incat $A{~x,j~} ≠ 0$

In continuare vom descrie algoritmul propriu-zis. Pornim cu un indice pentru linii, sa-l notam $i$, si un indice pentru coloane, $j$, initializate initial cu $1$. Cautam pe coloana $j$, o linie $x$, $i &le; x$ astfel incat $A{~x,j~} &ne; 0$. Daca aceasta linie nu exista, inseamna ca necunoscuta cu indicele $j$ este variabila libera, iar noi incrementam indicele $j$. Altfel, interschimbam liniile $i$ si $x$ si impartim toata ecuatia de pe linia $i$ la $A{~i,j~}$, pentru a face coeficientul A{~i,j~} egal cu $1$, usurand calculele urmatoare. In continuare vom scadea, din toate ecuatiile $u$, $i < u$, ecuatia $i$ inmultita cu o valoare $z{~u~}$, astfel incat toti coeficientii A{~u,j~} sa devina $0$. Avem astfel $A{~u,j~} - z{~u~} * A{~i,j~} = 0 => z{~u~} = A{~u,j~} / A{~i,j~}$, dar cum $A{~i,j~} = 1$, $z{~u~} = A{~u,j~}$. Aceasta reducere este necesara pentru respectarea conditiei $(1)$, avand in vedere ca nu putem avea $x &ne; i$ cu $p{~x~} = p{~i~}$. Incrementam pe $i$ si $j$ si reluam procedeul de la inceput. Algoritmul se incheie cand $i > N$ sau $j > M$. Complexitatea acestuia este $O(N^3^)$ ca timp si $O(N^2^)$ ca memorie.
 
Acum matricea respecta relatia $(1)$ si putem incepe sa calculam valorile necunoscutelor. Luam ecuatiile in ordine de la $N$ spre $1$, gasim pozitia $p{~i~}$, iar $x{~p{~i~}~}$ va fi dat de relatia $x{~p{~i~}~} = A{~i,M+1~} - A{~i,M~} * x{~M~} - A{~i,M-1~} * x{~M-1~} - ... - A{~i,p{~i~}+1~} * x{~p{~i~}+1~}$. Relatia $(1)$ ne garanteaza ca $x{~p{~i~}+1~}, x{~p{~i~}+2~}, ... , x{~M~}$ vor fi calculate anterior. Daca pe parcurs gasim o linie de forma $(0, 0, 0, ... , 0, X)$ (doar rezultatul ecuatiei este nenul), sistemul nu are solutie.
 
O implementare de $100$ de puncte gasiti 'aici':job_detail/608486?action=view-source. Acest algoritm poate fi aplicat cu succes pentru sisteme de ecuatii in care coeficientii, necunoscutele si rezultatele sunt doar $0$ si $1$, iar operatorul $+$ din ecuatii este inlocuit de $XOR$.
 
h3. Probleme propuse
 
* 'Flux':problema/flux
* 'Tunelul Groazei':problema/tunel
* 'Laser':problema/laser
* 'Color3':problema/color3
* 'Cracking RSA':http://acm.sgu.ru/problem.php?contest=0&problem=200
* 'Puzzle':http://acm.sgu.ru/problem.php?contest=0&problem=260
* 'To xor or not to xor':http://acm.sgu.ru/problem.php?contest=0&problem=275

== include(page="template/taskfooter" task_id="gauss") ==

5873