Metoda Gauss

Metoda Gauss

se foloseste la rezolvarea sistemelor de n ecuatii liniare cu n necunoscute.

Se considera un sistem de n ecuatii liniare cu n necunoscute x1, x2, , xn, care poate fi scris astfel:

care poate fi reprezentata sub forma: Ax=b, unde A=(a_ij) _{n -} matrice , x,b IR^{n -} vectori, det A 0.

Daca vom completa matricea cu o coloana alcatuita din termenii liberi al sistemului, vom capata o matrice noua, care poarta denumirea de matrice extinsa a sistemului

unde coeficientii liberi b_i se noteaza prin a_in+1 (i=1,2,.n)

In memoria calculatorului matricea extinsa se pastreaza in forma unui tablou bidimensional de numere reale.

Calculul solutiei sistemului prin metoda Gauss se efectuiaza in doua etape:

Etapa mersului direct.

(eliminarea succesiva a necunoscutelor prin transformari echivalente a sistemului aducindu-l la o forma cu matricea superior triunghiulara).

Etapa mersului invers.

(se calculeaza necunoscutele)

Algoritmul etapei mersului direct

Pasul 1. Ca scop se pune eliminarea necunoscutei x₁ din ecuatiile cu numerele

i = 2, ., n. Presupunem ca coeficientul a₁₁ 0. In caz contrar trebuie sa alegem din ecuatiile plasate mai jos acea ecuatie la care a_i1 0, si sa schimbam cu locurile prima ecuatie si ecuatia i. La toti pasii care urmeaza aceasta operatie se repeta, in caz de necesitate.

Vom calcula c_i1 = a_i1/a₁₁ (i = 2, 3, ., n) si vom scadea consecutiv din ecuatiile 2, 3, , n prima ecuatie inmultita respectiv la c₂₁, c₃₁, ., c_n1. Aceste operatii transforma in zero coeficientii pe linga x₁ in toate ecuatiile cu exceptia primei. Ca rezultat capatam un sistem echivalent de ecuatii

c₁₁x₁ + c₁₂x₂ + c₁₃x₃ + . + c_1nx_n - c_1n+1= 0 ,

a₂₂⁽¹⁾x₂ + a₂₃⁽¹⁾x₃ + . + a_2n⁽¹⁾x_n - a_2n+1⁽¹⁾ = 0 ,

a₃₂⁽¹⁾x₂ + a₃₃⁽¹⁾x₃ + . + a_3n⁽¹⁾x_n - a_3n+1⁽¹⁾ = 0,

. . . . . . . . . . . . . . .

a_n2⁽¹⁾x₂ + a_n3⁽¹⁾x₃ + . + a_nn⁽¹⁾x_n - a_nn+1⁽¹⁾ = 0 .

in care a_ij⁽¹⁾ se calculeaza asa: a_ij⁽¹⁾ = a_ij − c_i1a_1j  

Iteram procesul, eliminind necunoscutele x_i   din ecuatiile i+1, . ,n(i=2,.,n-1)

Vom descrie pasul k.

Pasul k. In conditia ca a_kk^(k-1) 0 calculam c_ik = a_ik^(k-1) / a_kk^(k-1) (i = k + 1, ., n)

si scadem din ecuatiile (k + 1), ., n ecuatia k obtinuta la pasul precedent si inmultita respectiv la c_k+1,k, c_k+2,k, ., c_nk.

Dupa pasul (n - 1) de eliminari obtinem urmatorul sistem de ecuatii:

a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + . + a_1nx_n - a_1n+1 = 0,

a₂₂⁽¹⁾x₂ + a₂₃⁽¹⁾x₃ + . + a_2n⁽¹⁾x_n - a_2n+1⁽¹⁾ = 0,

a₃₃⁽²⁾x₃ + . + a_3n⁽²⁾x_n - a_3n+1⁽²⁾ = 0,

. . . . . . . . . . . . . . . . . . . .

a_nn^(n-1)x_n - a_nn+1^(n-1)

cu matricea extinsa A ^n-1) de coeficienti superior triunghiulara.

Algoritmul etapei inverse

Din ultima ecuatie a sistemului calculam x_n. Substituim x_n prin valoarea gasita in toate ecuatiile incepind cu a (n-1) pina la prima si calculam consecutiv x_n-1, x_n-2, ., x₁. Necunoscutele se calculeaza dupa urmatoarele formule:

x_n = a_nn+1^(n-1) / a_nn^(n-1),

x_k = (a_nn+1^(k-1) - a_k,k+1^(k-1)x_k+1 - . - a_kn^(k-1)x_n) / a_kk^(k-1), (k = n - 1, ., 1).