Metode numerice - aplicații

1. Metoda Gauss, cu pivotare parţială la fiecare etapă, pentru rezolvarea sistemelor de ecuaţii liniare

Prezentarea problemei

Se consideră sistemul liniar:

(1) A⋅x = t, unde: A ∈ Rnxn – matricea sistemului (1),

t ∈ Rn – termenul liber al sistemului (1).

Ne propunem să determinăm, dacă este posibil, x ∈ Rn, x – soluţia unică a sistemului (1).

Prezentarea metodei

Matricea extinsă, care caracterizează sistemul (1), o notăm (A ⎜t) şi elementele ei le notăm aij, 1 ≤ i ≤ n, 1 ≤ j ≤ n+1, unde ai,n+1 = ti, 1 ≤ i ≤ n. Metoda Gauss constă în prelucrarea matricei (A ⎜t) astfel încât, într-un număr finit de etape (şi anume n-1), matricea A să fie triangularizată superior, adică să obţinem matricea:

(2) ()()()()()()()()()()()()()()()()()nnnotn1n,nn1n,1nn1n,2n1n,1nn,nnn,1nn1n,1nnn,2n1n,2n22nn,1n1n,1n12n11t Aaaaaa000aa00aaa0aaaa=⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝⎛++−++−−−−−MLLMMMMLL, unde am notat (A| t) cu ()()()()⎟⎠⎞⎜⎝⎛=1ij11at A, 1 ≤ i ≤ n, 1 ≤ j ≤ n+1.

Observaţie. Matricea (2) caracterizează un sistem echivalent cu sistemul (1) (deci cu aceeaşi soluţie).

Astfel, presupunând ()0akkk≠, 1 ≤ k ≤ n-1, unde elementul se numeşte pivot, pentru a obţine, în final, matricea (2), se aplică formulele: ()kkka

8

(3) ()()()()()()⎪⎪⎪⎩⎪⎪⎪⎨⎧+≤≤+≤≤+⋅−≤≤+≤≤+≤≤≤≤=+.1nj1k,ni1k ,aaaa, ni1j ,kj1 , 0 ,1nji ,ki1 , aakkjkkkkikkijkij1kij

Componentele soluţiei sistemului (1) se obţin direct, prin substituţie inversă, pe baza formulelor:

(4) ()()()()()()⎪⎪⎪⎩⎪⎪⎪⎨⎧⎟⎟⎠⎞⎜⎜⎝⎛⋅−==≠=Σ+=++.a/xaax1, ..., 2,-n 1,-n ipentru , 0 a dacă , a/axniin1ijjnijn1n,iinnnnnnn1n,nn

Dacă (∃)1 ≤ k ≤ n-1 astfel încât ()kkka = 0, atunci pentru a putea aplica formulele (3) se recomandă o procedură de pivotare, de exemplu pivotarea parţială, care constă în:

- se caută în coloana k a pivotului, acel element ()kk,ika, k ≤ ik ≤ n, care are proprietatea:

(5) ()()kk,inikkk,iamaxak≤≤=.

În legătură cu procedura de pivotare parţială se mai impun următoarele observaţii:

1)

dacă ()kk,ika = 0, atunci sistemul (1) nu are soluţie unică;

2)

dacă ()kk,ika ≠ 0, şi ik ≠ k, atunci se permută (interschimbă) liniile k şi ik în matricea()()()kkt A după care se continuă cu aplicarea formulelor (3) şi, în final, (4).

Aplicaţii

1)

Matricea extinsă asociată sistemului (1) este:

9

⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛20260111100112331322

Procedura de pivotare parţială conduce la următoarele permutări de linii:

-

la etapa 1: linia 1 ↔ linia 2;

-

la etapa 2: linia 2 ↔ linia 3;

-

la etapa 3: nu se efectuează permutări.