Aplicații ale algebrei liniare în C++

1. Considerente generale

Pornim de la o matrice A pătratică, nesingulară şi b vector nenul.

Ideea metodei este de a elimina succesiv necunoscutele astfel încât matricea coeficienţilor A să fie adusă în formă superior triunghiulară.

O matrice este superior triunghiulară dacă , pentru i>j.

O matrice este inferior triunghiulară dacă , pentru i<j.

Pas 1.

Eliminarea necunoscutei din ecuaţiile de rang 2,3,...,n astfel încât prima coloană a matricei coeficienţilor A să fie adusă în formă superior triunghiulară.

Pas 2.

Eliminarea necunoscutei din ecuaţiile de rang 3,...,n astfel încât a doua coloană a matricei coeficienţilor A să fie adusă în formă superior triunghiulară, fără a afecta forma primei coloane a matricei A.

...

Pas k. ( )

Eliminarea nescunoscutei din ecuaţiile de rang p+1,...,n astfel încât matricea coeficienţilor A să fie adusă în formă superior triunghiulară, fără a afecta forma coloanelor 1,...,p-1.

Înainte de primul pas, sistemul are următoarea formă:

Pasul 1. Eliminăm necunoscuta din ecuaţiile de rang 2,3,...,n astfel încât să anulăm ( ), în felul următor.

Păstrăm prima ecuaţie, iar ecuaţiile i, le transformăm astfel:

sau , . Deci rezultă .

Pasul 2.

Eliminăm necunoscuta din ecuaţiile de rang 3,...,n astfel încât ( obţinut la pasul 1) să devină 0, pentru .

După pasul 1, sistemul devine:

Păstrăm primele două ecuaţii neschimbate şi se transformă ecuaţiile i, astfel:

Deci =0, .

Pasul p ( ).

Eliminăm necunoscuta din ecuaţiile de rang p+1,...,n astfel încât să aducem coloanele p în formă superior triunghiulară.

Păstrăm primele p ecuaţii şi transformăm ecuaţiile i, .

.

Algoritmul are n-1 paşi. Pentru a putea aplica acest algoritm, avem nevoie ca:

Aceste elemente se numesc pivoţi.

Pentru a evita împărţirea la 0 sau la numere foarte mici se introduce pivotarea parţială.

Pivotarea parţială înseamnă schimbarea ordinii ecuaţiilor sistemului astfel încât pivotul la pasul p să fie cel mai mare coeficient al necunoscutei .

Astfel:

Pasul 1.

Vom calcula întâi maximul dintre coeficienţii lui în modul.