METODE NUMERICE PENTRU REZOLVAREA SISTEMELOR DE ECUATII ALGEBRICE LINIARE.

Metode de rezolvare numerica a sistemelor algebrice liniare

Modelarea numerica a proceselor tehnologice de multe ori duce la obtinerea unor sisteme de ecuatii liniare. Procedeul Kramer, care permite obtinerea solutiei sistemului prin raportul determinatilor, devine inutil daca numarul de ecuatii si necunoscute creste

( n >10 ), deoarece numarul necesar de operatii aritmetice are o valoare fantastica n!n.

In acest caz rezolvare sistemelor liniare se face folosind anumite metode specifice, care pot fi clasificate ca:

metode directe ;

- metode indirecte (sau iterative).

Metodele directe se utilizeaza pentru rezolvarea sistemelor liniare de ordinul n < 10³. Metodele indirecte se utilizeaza pentru rezolvarea sistemelor liniare de pana la ordinul n = 10⁶.

NOTA. Ca regula , pentru rezolvarea sistemelor de ecuatii liniare, se aplica metode iterative.

1.1. Metoda eliminarii Gauss

Metoda eliminarii Gauss este cea mai simpla metoda directa, care cere circa (2/3)·n³ de operatii aritmetice. Metoda are la baza ideea transformarii matricei date A intr-o matrice superior triunghiulara prin eliminarea consecutiva a necunoscutelor si apoi rezolvarea ecuatiilor, folosind procedeul de substituire inversa .

Descrierea metodei

Se considera un sistem de n ecuatii liniare, de forma:

(1)

care scris mai scurt va avea forma

, (2)

unde :

i = 1,2,3,.., n este numarul ecuatiei;

j = 1,2,3, , n reprezinta numarul necunoscutei

Acest sistem in forma matriceala se noteaza:

A·x = b , (3)

la care:   

A se numeste matricea coeficientilor ,

x - vectorul variabilelor necunoscute,

b - vectorul termenelor liberi.

Daca matricea A este superior triunghiulara, adica toate elementele situate sub diagonala principala sunt nule :

(coeficientii a_ij = 0, la i > j), atunci rezolvarea sistemului se poate face usor prin procedeul de eliminare inversa.

Daca toate elemente din matricea superior triunghiulara A de pe diagonala principala sunt diferite de zero (a_ii 0) atunci sistemul de ecuatii dat ( 1) va capata forma :

(4)

Se observa ca ultima ecuatie contine numai necunoscuta x_n, atunci considerand

a_n,n 0 , se obtine

x_n = b_n/a_n,n (5)

Substituind aceasta valoare in penultima ecuatie rezulta ecuatia :

a_n-1,n-1 x_n- + a_n-1,n b_n /a_nn = b_n- (6)

din care vom avea necunoscuta x_n-1 ( avand in vedere ca a_n-1,n-1

(7)

Introducand valorile cunoscute pentru x_n si x_n-1 in ecuatia imediat anterioara rezulta necunoscuta x_n- Daca procedura se repeta pana la prima ecuatia va rezulta prima necunoscuta x₁.

Problema care nu a fost deocamdata clarificata este de a gasi procedeul prin care un sistem de ecuatii liniare structurat arbitrar sa fie transformat intr-o forma cu matricea superior triunghiulara, pentru putea aplica procedeul de substituire inversa examinat anterior.

Se considera un sistem cu n ecuatii liniare (1) scris in forma (2). Notand termeni liberi se obtine:

, (8) la care i = 1,2,3,.., n este numarul ecuatiei; j = 1,2,3, , n reprezinta numarul necunoscutei.

Presupunem, ca in prima ecuatie

(9)

primul coeficient a₁₁ ≠ 0 (in cazul contrar se face renumerarea necunoscutelor). Eliminam din aceasta ecuatie coeficientul din fata primei necunoscute x₁ impartind-o cu a₁₁ . Notand , iar se obtine:

, (10)

Multiplicand ecuatia (10) consecutiv cu a_i1, unde i=2,,n , si scazand-o din ecuatia i se elimina prima variabila x₁ din toate ecuatiile sistemului (8) in afara de prima ecuatie. Atunci aceste ecuatii vor capata forma :

, i= 2,3, ., n (11)

unde :

, m=2,3,.,n si l=2,3,., n+1 (12) La fel se procedeaza cu sistemul obtinut (11).

Eseu: Sistemul periodic al elementelor Referat: Repartitia unei substante intre doi solventi nemiscibili (Legea de distributie a lui Nernst)

Dupa eliminarea necunoscutei x_k-1, restul ecuatiilor va forma sistemul :

, (13) unde: i= k , k+1,,n; j=i+1.

Eliminand elemente ale coloanei k, se obtine sistemul de ecuatii cu coeficientii :

m=k+1,,n ; l=k+1,,n+1 (14)

Eliminarea necunoscutelor duce la sistemul (4) cu matricea superior triunghiulara, care scris mai scurt are forma :

, (15)

unde: i=1,2,, n.

Cu aceasta se incheie eliminarea Gauss si dupa aceasta, pentru determinarea necunoscutelor se aplica eliminarea inversa. Pentru aceasta se utilizeaza formula (15) transcrisa in forma (16), considerand i= n, n-1, n-2, , 2, 1 :

(16)

NOTA. Eliminarea Gauss prevede divizarea ecuatiilor pe elemente diagonale. Daca un coeficient diagonal este nul sau foarte mic dupa valoarea lui absoluta, eroarea de calcul

devine inadmisibil de mare. De aceea, inainte de aplicarea eliminarii, sistemul trebuie rearanjat astfel incat elementele diagonale sa fie dominante in valoarea absoluta.

Aplicatia 1. Exemplu de folosirea eliminarii gaussiene si a eliminarei inverse

Se considera ca analiza poceselui de amestecare a trei substante fluide cu trei concentratii volumice diferite a condus la urmatorul sistem de ecuatii :

Se cere deteminarea concentratiilor volumice initiale x₁, x₂ si x₃ .

Rezolvare

Sa notam coeficientii : a₁₁ =2, a₁₂ =3, a₁₃ =-1, a₂₁ =4, a₂₂ =4 , a₂₃ =-3, a₃₁ =-2, a₃₂ =3, a₃₃ =-1 si termenii liberi cu b₁=5 , b₂= 3 , b₃=1.

1. Ca sa eliminam pe x₁ din ecuatia (b), inmultim ecuatia (a) cu coeficientul

- a₂₁/a₁₁ = - 42 si adunam rezultatul la ecuatia (b).

Se obtine ecuatia :

-2·x₂ - x₃ = -7 (b')

De asemenea, inmultim ecuatia (a) cu multiplicatorul -a₃₁/a₁₁= -(-22) si rezultatul obtinut se aduna la ecuatia (c).

Se obtine o noua ecuatie :

6·x₂ - 2·x₃ = 6 (c')

3. Acum se va elimina necunoscuta x₂ din ecuatia (c'). Pentru aceasta, se inmulteste ecuatia (b') cu multiplicatorul -6(-2) si rezultatul obtinut se aduna la ecuatia (c') .

Rezulta :

- 5 = - 15 (c')

Cu aceasta, noul sistem de ecuatii devine superior triunghiular :

,

sau in forma generalizata :

Rezolvarea sistemului transformat se face folosind procedeul de eliminare inversa :

x = b₂ /a₂₂ =

x = (b₂ - a₂₃·x₃) /a₂₂

x = (b₁ - a₁₂·x₂ - a₁₃·x₃ )/a₁₁

1. Metoda iteratiilor simple Iacobi

Se considera un sistem cu n ecuatii liniare :

Considerand ca sistemul examinat este astfel structurat incat elementele diagonale

a_i,i ( i=1,2,,n) sunt dominante in valoarea absoluta, rearanjam sistemul eliminand variabile x_i din termeni care contin coeficientii a_ii de la fiecare rand in felul urmator :

(17)

Daca in partea dreapta a sistemului (17) se introduce o solutie initiala x_i⁽⁰ (care de cele mai multe ori se ia egala cu zero x_i⁽⁰⁾=0 ), prin rezolvarea sistemului (17) se obtine prima solutie aproximativa x_i⁽¹⁾ . Introducand noua solutie obtinuta in partea dreapta a sistemului se obtine a doua solutie aproximativa x_i⁽²⁾.

Continuand acest proces penrtu pasul k+1 se obtine solutia :

, (18)

unde i = 1,2, ...,n ; j = 1,2, ...,n

O conditie suficienta pentru convergenta procesului iterativ este ca :

, (19) NOTA. Daca conditie de convergenta este satisfacuta, atunci si solutia cautata va converge spre solutia reala, indiferent de valoarea aproximatiei initiale x_0.

Aplicatia Utilizarea metodei Iacobi (iteratiilor simple)

Se considera sistemul de ecuatii liniare :

Se cere rezolvarea lui cu precizia ε =10^-4 .

Rezolvare

Rearanjam ecuatiile in asa fel incat fiecare necunoscuta sa aiba cel mai mare coeficient :

Rezolvam fiecare ecuatie fata de necunoscuta respectiva :

Alegem ca o solutie initiala :

Rezulta prima solutie aproximativa:

Introducem valorile obtinute pentru in partea dreapta a sistemului, rezultand o noua solutie :

Dupam inlocuirea in partea dreapta a sistemului , rezulta o noua solutie, etc.

Din valorile numerice putem alcatuiun tabel :

Tabelul 1

Din tabelul se vede ca dupa a 7S iteratia solutii nu se mai schimba.

Raspuns:

1.3. Metoda iterativa Gauss - Seidel

In acest caz, trecerea sistemului de ecuatii (17) de la iteratia (k) spre (k+1) nu se mai face simultan pentru toate ecuatiile,ci prin utiizarea solutiilor obtinute din ecuatii precedente. Pentru sistemul examinat iteratia (k+1) se realizeaza prin relatia:

(19)

NOTA. Avantajul esential al acestei metode il constituie cresterea vitezei de convergenta, datorita reducerii numarului total de iteratii necesare.

Aplicatia 3. Utilizarea metodei iterative Gauss-Seidel.

Vom rezolva acelasi sistem din Aplicatia 2 , pentru a arata rapiditatea convergentei solutiei numerice la utilizarea metodei Gauss-Seidel. Deci , avem :

Rezolvare

Considerand solutia initiala in prima ecuatie si se obtine solutia :

Dupa aceasta se rezolva a doua ecuatie introducand si :

Considerand noile solutii: si , se rezolva a treia ecuatia:

A doua iteratie se incepe prin introducerea solutiilor si in prima ecuatie , rezulta :

Introducand si rezulta :

In fine, cu noi solutii si se obtine :

Procedand in mod asemanator se obtin rezultatele prezentate mai jos in tabelul 2 :

Tabelul 2

Din tabelul se vede ca dupa a 5- a iteratie solutii nu se mai schimba.

Raspuns: