Rezolvarea sistemelor - de informatica

Rezolvarea sistemelor

- Atestat de informatica -

Programul rezolva un sistem de maxim MAX ecuatii (constanta definita in program) cu MAX necunoscute, cu coeficienti reali.

Sunt definite mai multe variabile globale :

a[MAX][MAX] - matricea coeficientilor initiali

tm[MAX][MAX] - matricea in care returneaza functia convert

mat[MAX][MAX] - matrice suplimentara

n, m -nr de ecuatii / nr. de necunoscute

sol[MAX] vectorul cu solutiile in cazul unui sistem Cramer

rang - rangul matricei

x[MAX] si y[MAX] - specifica ce linii (x[]) si ce coloane(y[]) sunt folosite in anumite functii (ex. : determinant, reducerea la sistem cvasitriunghiular)

cX[MAX] si cY[MAX] - vectori de forma [0,1,1,] folositi la copierea unei matrici in tm, mai putin prima linie si prima coloana

Dupa citirea datelor sunt afisate sub forma de sistem de ecuatii. Seria de if().. else are rol in formatarea datelor pentru a aseza necunoscutele de acelasi fel pe aceeasi coloana

Functii definite in aplicatie :

min(a,b) - returneaza minimul dintre a si b

convert(B[][], v1[], n1, v2[], n2) - copiaza matricea B[][] in matricea tm, luand doar liniile marcate in v1[] cu un element nenul si coloanele marcate in v2[]. n1 este dimensiunea lui v1 (implicit nr. de linii ale matricii) si n2 este dimensiunea lui v2 (nr. de coloane). Matricea rezultata are n1' linii si n2' coloane, unde n1' respectiv n2' sunt numarul de elemente nenule din vectorii v1 respectiv v2. In cadrul functiei sunt definiti 2 vectorii x si y cu semnificatia x[i]=k (coloana i din matricea B devine coloana k din matricea tm) si la fel pentru y (linii).

Determinant (B[][],n1) - returneaza determinantul matricii patratice B de dimensiune n1. Daca n=2 se returneaza determinantul (b_0,0*b_1,1-b_0,1*b_1,0). Daca nu se calculeaza determinantul recursiv.

Se face produsul elementelor nenule de pe prima coloana in variabila det_temp;

Daca elementul din stanga-sus este 0 se inverseaza cu prima linia care nu incepe cu 0. Determinantul o sa aiba semnul minus. Daca nu exista nici o linia care sa nu inceapa cu 0 determinantul este 0;

Toate liniile care nu incep cu 0 sunt inmultite cu produsul obtinut/primul element de pe linie. Astfel prima coloana va contine elemente identice.

Toate valorile cu care au fost inmultite liniile sunt inmultite in det_temp2, pentru ca determinantul obtinut va trebui impartit prin aceasta valoare

Se scade prima linie din toate celelalte linii care nu incep deja cu 0. Acum prima coloana contine doar un element nenul (primul);

Determinantul este (B[0][0]/det_temp2)*determinant(matricea obtinta prin eliminarea primei linii si a primei coloane);

Aflarea rangului :

• Se cauta primul element nenul din matrice. Daca nu exista nici unul => sistemul are solutii in R^m. Daca se gaseste se marcheaza pozitia lui in vectorii x si y cu 2 (pozitie permanenta).
• Se cauta daca exista determinanti de rang 2, 3, .. min (m-1,n). (m-1 pt. Ca m include si termenul liber). Se aplica un algoritm Backtrack. Se cauta la fiecare pas o linie si o coloana nefolosite (x[i]=0, y[j]=0). Se marcheaza cu 1 (valoare temporar) si se verifica daca determinantul obtinut este nenul. Daca da se intrerupe cautarea (gata=1), se stocheaza noul rang se cauta un determinant mai mare.
• Daca la un pas nu s-a gasit nici un determinant nu se mai cauta un rang mai mare

Cazul 1 :    Sistem Cramer

Daca sunt n ecuatii si n necunoscute si rangul este n inseamna ca sistemul are solutie unica. Rezolvarea Cramer : se calculeaza determinantii caracteristici pentru fiecare necunoscuta. Solutia este detX/Determinantul sistemului

Cazul 2 : Teorema Rouche

Se calculeaza determinantii secundari obitnuti prin bordarea determinatului principal cu cate o linie din ecuatiile secundare si coloana solutiilor. Daca unul dintre acesti determinanti nu este 0 sistemul este incompatibil. Daca toti determinantii sunt nuli este un sistem compatibil cu n-rang necunoscute secundare.

Se rezolva dupa metoda lui Euler (reducere la sistem cvasitriunghiular)

Se copiaza ecuatiile principale in matricea tm. Cum in matricea tm se pot face inversiuni de ecuatii, ordinea ecuatiilor nu va mai corespunde cu cea din matricea a. Nici variabila nr. i din matrica a nu va fi neaparat variabila nr. i din tm, ci daca variabila i este principala ea va fi pe pozitia k (k=nr. de variabile principale din a PANA in i), iar daca este secundara va fi pe k (k = nr. de variabile principale + nr. de variabile secundare din a PANA in i). Din aceasta cauza conversiile intre matrici sunt mai anevoioase.

Cum sunt Rang ecuatii principale, trebuiesc facute Rang-1 transformari. Cum nu se stie daca neaparat primele ecuatii sunt ecuatii principale si daca primele variabile sunt variabile principale, se cauta pozitia variabilei principale I (i intre 0 si rang-2). Aceasta este salvata in co. In ecuatia i, variabila principala i trebuie sa aiba coeficient nenul. (tm[i][co]!=0). Daca nu, ecuatia i trebuie schimbata cu o alta ecuatia care nu are variabila i (de fapt co) cu coeficient nul. Daca nu exista nici o astfel de ecuatie se trece la urmatoarea variabila principala.

Acum stim sigur ca in ecuatia i variabila principala i nu are coeficient nul. Toata linia trebuie inmultita cu coeficientul variabilei i (de fapt co) din linia i / coeficientul variabilei i (co) din linia j. Astfel, de la ecuatia I pana la ultima, toate au acelasi coeficient pentru variabila i. Se scade linia i din fiecare linie de sub ea, astfel coeficientii vor fi 0 (mai putin pe linia i).

Dupa aceste transformari, sistemul va fi de genul (a_k,n+1 poate contine si parametrii)

a_1,1*X₁ + a_1,2*X₂+.+a_1,n*X_n = a_1,n+1

a_2,2*X₂+.+a_2,n*X_n = a_2,n+1

a_n,n*X_n = a _n,n+1

Se imparte ficare linie la primul coeficient nenul (adica linia i la coeficientul lui i). Sistemul va fi de forma

X₁ + a'_1,2*X₂+.+a'_1,n*X_n = a'_1,n+1

X₂+.+a'_2,n*X_n = a'_2,n+1

X_n = a' _n,n+1

Se formeaza structurile ajutatoare :

vect[MAX] cu semnificatia vect[i]=k => variabila principala i din matricea a se gaseste pe linia k din matricea tm. Daca i este variabila secundara vect[i] nu are sens

vect2[MAX] cu semnificatia vect2[i]=k => variabila secundara i din matricae a este parametrul nr. k. Vectorul este folosit pentru a lega logic afisarea

mat[MAX][MAX], cu semnificatia mat[i][] => Variabila principala i (din matricea tm. Daca i este din a trebuie folosit vect[i]) se scrie ca suma (de la prima variabila secundara la ultima, variabilele luate din a) din parametrul j (σ_vect2[j])*mat[i][j]. Adica mat[i][j]=k spune ca variabila principala i are in dezvoltarea sa pe variabila secundara j (parametrul vect2[j]) cu coeficientul k. Matricea este initial 0.

Explicitarea si afisare solutiilor in functie de parametrii :

Se iau toate varibilele, in oridine inversa pentru ca variabila principala i trebuie explicitata in functie de toate variabilele principale de la i la m-2 (m-1 este termenul liber). Fiecare principala variabila este explicata in functie de toate celelalte pana la m-1 (inclusiv termenul liber) - for(j=i+1;j<m;j++)

Daca variabila j este un principala (y[i]=2) se iau toate variabilele secundare (for(k=0;k<m;k++)), si se adauga in explicitarea variabilei i (vect[i] din mat) inmultite cu coeficientul variabilei j din ecuatia i trecuta in cealalta parte (-tm[vect[i]][j]). Adica in explicitarea variabilei i se adauga variabila j*(-coeficientul lui j). Daca j nu este principal, ea poate fi teremnul liber (j=m-1). Termenul liber se adauga neinmultit cu nimic (+tm[vect[i]][j]). Daca nu e nici termenul liber inseamna ca e un parametru si se adauga coeficientul lui j din ecuatia i din mat[vect[i]][j] (in dreptul parametrului j), cu semn schimbat.

Dupa aceste operatii fiecare variabila principala este definita ca un sir de coeficienti de variabile secundare. Pentru afisare se ia o variabila first=0 care spune daca a fost afisat ceva pe linia dezvoltarii variabilei principale i (pentru a nu se afisa 0*σ₁, etc, dar pentru a se afisa termenul liber daca acesta este 0 si i e independenta de parametrii). Pentru fiecare variabila, se verifica daca este principala sau secundara. Daca este secundara este afisat parametrul corespunzator _vect2[i]. Daca este o variabila principala se iau toate variabilele secundare (j) si se expliciteaza in functie de acestea. Este afisata dependenta de o variabila secundara doar daca aceasta nu are coeficient 0.