Cibernetică

Tema 1 - Posibilitatea rezolvarii sistemelor liniare cu ajutorul mediilor de programare -

Sisteme de ecuatii liniare

1. Metode de rezolvare a sistemelor liniare

Rezolvarea sistemelor cu un mare numar de ecuatii liniare reprezinta unul din domeniile in care calculatoarele numerice si-au dovedit din plin eficienta. Problema rezolvarii sistemelor de ecuatii liniare este foarte des intalnita in simularea numerica. Enumeram cateva situatii: interpolare cu functii spline cubice, rezolvarea sistemelor de ecuatii neliniare cu ajutorul metodelor iterative care au la baza liniarizarea ecuatiilor, discretizarea ecuatiilor diferentiale ordinare cu conditii la limita, discretizarea ecuatiilor cu derivate partiale. In mod corespunzator, a trebuit sa fie puse la punct procedee numerice adecvate, atat pentru reducerea numarului mare de operatii, cat si pentru reducerea erorilor de calcul care cresc cu dimensiunile sistemului de ecuatii.

In cazul general, problema care trebuie rezolvata poate fi scrisa sub forma

Ax = b

Sistemul admite solutia unica x=Rn daca matricea este inversabila, caz în care solutia se exprima sub forma:

x = A-1.b

Metodele de rezolvare:

a) Metode exacte sau directe - care furnizeaza solutia exacta a sistemului daca se neglijeaza erorile de rotunjire.

b) Metode aproximative sau iterative - care construiesc un sir, convergent catre solutia exacta a sistemului.

2. Metode exacte

Metodele directe aduc sistemul prin transformari de echivalenta, la un sistem particular (diagonal, triunghiular, etc), care se rezolva cu mijloace elementare. Metodele exacte se bazeaza pe factorizare gaussiana sau factorizare ortogonala. Complexitatea metodelor exacte este O(n3), motiv care le restrânge aplicabilitatea la rezolvarea sistemelor de ordin nu prea mare (n<1000)

2.1. Metoda eliminarii a lui Gauss

Metoda consta in eliminarea succesiva a necunoscutelor intr-o maniera care

conduce la un numar de operatii mult mai redus decat procedeul care ar utiliza

regula lui Cramer si calculul determinantilor corespunzatori. Vom observa ca,

in operatia de eliminare, nu este necesar sa transcriem si necunoscutele; este

suficient sa operam doar cu coeficientii matricei sistemului si cu termenii liberi.

Sa consideram un sistem de n ecuatii liniare cu n necunoscute scris sub forma

Ax = b

unde A este o matrice patrata, nesingulara (detA 6= 0), de dimensiuni n × n,

iar x si b sunt vectori coloana de dimensiune n.

Metoda eliminarii a lui Gauss consta in a obtine zerouri succesiv, intai pe prima

coloana (sub coeficientul a1,1), apoi pe a doua coloana (sub coeficientul a2,2)

s.a.m.d., pe ultima linie a matricei A ramanand doar coeficientul an,n (evident

modificat de operatiile de eliminare anterioare). Aceasta revine la a reduce matricea A la o matrice superior triunghiulara, care mai apoi se rezolva cu un efort mic de calcul.