Transformari elementare

Cheia pentru rezolvarea unui sistem de ecuatii liniare sunt transformarile elementare care pastreaza aceeasi multime de solutii, dar care transforma sistemul de ecuatii intr-o forma mai simpla:

• Schimbarea a doua ecuatii (randurile din matricea reprezinta sistemul de ecuatii)

• Inmultirea unei ecuatii (rand) cu o constanta  λ ∈ R \ {0}

• Adunarea a doua ecuatii (randuri)

Exemplu:
Pentru a ∈ R, cautam toate solutiile urmatorului sistem de ecuatii:

$$ \begin{aligned} -2x_1 + 4x_2 - 2x_3 - x_4 + 4x_5 &= -3 \\ 4x_1 - 8x_2 + 3x_3 - 3x_4 + x_5 &= 2 \\ x_1 - 2x_2 + x_3 - x_4 + x_5 &= 0 \\ x_1 - 2x_2 - 3x_4 + 4x_5 &= a \end{aligned} $$

Incepem prin a converti acest sistem de ecuatii in notatia matriceala compacta Ax = b. Nu mai mentionam variabilele x explicit si construim matricea extinsa (in forma [A | b])

$$ \left[ \begin{array}{rrrrr|r} -2 & 4 & -2 & -1 & 4 & -3 \\ 4 & -8 & 3 & -3 & 1 & 2 \\ 1 & -2 & 1 & -1 & 1 & 0 \\ 1 & -2 & 0 & -3 & 4 & a \end{array} \right] \begin{array}{l} \text{Swap with } R_3 \\ \\ \text{Swap with } R_1 \\ \end{array} $$

unde am folosit linia verticala pentru a separa partea stanga de partea dreapta. Folosim ⇝ pentru a indica o transformare a matricei extinse folosind transformari elementare.

Schimbarea Randurilor 1 si 3 duce la

$$ \left[ \begin{array}{rrrrr|r} 1 & -2 & 1 & -1 & 1 & 0 \\ 4 & -8 & 3 & -3 & 1 & 2 \\ -2 & 4 & -2 & -1 & 4 & -3 \\ 1 & -2 & 0 & -3 & 4 & a \end{array} \right] \begin{array}{l} \\ -4R_1 \\ +2R_1 \\ -R_1 \end{array} $$

Cand aplicam acum transformarile indicate (de exemplu, scadem de patru ori Randul 1 din Randul 2), obtinem

$$ \left[ \begin{array}{rrrrr|r} 1 & -2 & 1 & -1 & 1 & 0 \\ 0 & 0 & -1 & 1 & -3 & 2 \\ 0 & 0 & 0 & -3 & 6 & -3 \\ 0 & 0 & -1 & -2 & 3 & a \end{array} \right] \begin{array}{l} \\ \\ \\ -R_2 - R_3 \end{array} $$ $$ \leadsto \left[ \begin{array}{rrrrr|r} 1 & -2 & 1 & -1 & 1 & 0 \\ 0 & 0 & -1 & 1 & -3 & 2 \\ 0 & 0 & 0 & -3 & 6 & -3 \\ 0 & 0 & 0 & 0 & 0 & a+1 \end{array} \right] \begin{array}{l} \\ \cdot (-1) \\ \cdot (-\frac{1}{3}) \\ \\ \end{array} $$ $$ \leadsto \left[ \begin{array}{rrrrr|r} 1 & -2 & 1 & -1 & 1 & 0 \\ 0 & 0 & 1 & -1 & 3 & -2 \\ 0 & 0 & 0 & 1 & -2 & 1 \\ 0 & 0 & 0 & 0 & 0 & a+1 \end{array} \right] $$

Aceasta matrice (extinsa) este intr-o forma convenabila, forma-echelon pe randuri (REF). Revenind de la aceasta notatie compacta la notatia explicita cu variabilele pe care le cautam, obtinem

$$ \begin{aligned} x_1 - 2x_2 + x_3 - x_4 + x_5 &= 0 \\ x_3 - x_4 + 3x_5 &= -2 \\ x_4 - 2x_5 &= 1 \\ 0 &= a+1 \end{aligned} $$

Doar pentru a = -1 sistemul poate fi rezolvat. O solutie particulara este:

$$ \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{bmatrix} = \begin{bmatrix} 2 \\ 0 \\ -1 \\ 1 \\ 0 \end{bmatrix} $$

Solutia generala, care cuprinde multimea tuturor solutiilor posibile, este

$$ \left\{ \mathbf{x} \in \mathbb{R}^5 : \mathbf{x} = \begin{bmatrix} 2 \\ 0 \\ -1 \\ 1 \\ 0 \end{bmatrix} + \lambda_1 \begin{bmatrix} 2 \\ 1 \\ 0 \\ 0 \\ 0 \end{bmatrix} + \lambda_2 \begin{bmatrix} 2 \\ 0 \\ -1 \\ 2 \\ 1 \end{bmatrix} , \lambda_1, \lambda_2 \in \mathbb{R} \right\} $$

In cele ce urmeaza, vom detalia o modalitate constructiva de a obtine o solutie particulara si generala a unui sistem de ecuatii liniare.

Observatie (Pivoti si Structura in Scara). Coeficientul principal al unui rand (primul numar diferit de zero din stanga) se numeste pivot si se afla intotdeauna strict la dreapta pivotului randului de deasupra sa. Prin urmare, orice sistem de ecuatii in forma-echelon pe randuri are intotdeauna o structura "in scara".

Definitie Forma-Echelon pe Randuri. O matrice este in forma-echelon pe randuri daca:

• Toate randurile care contin doar zero-uri se afla la baza (partea de jos) matricei; in mod corespunzator, toate randurile care contin cel putin un element diferit de zero se afla deasupra randurilor care contin doar zero-uri.

• Privind doar randurile nenule, primul numar nenul din stanga (numit si pivot sau coeficient principal) se afla intotdeauna strict la dreapta pivotului randului de deasupra sa.

Observatie (Variabile de Baza si Variabile Libere). Variabilele corespunzatoare pivotilor in forma-echelon pe randuri se numesc variabile de baza, iar celelalte variabile sunt variabile libere. De exemplu, in sistemul rezolvat anterior, x₁, x₃, x₄ sunt variabile de baza, in timp ce x₂, x₅ sunt variabile libere.

Observatie (Obtinerea unei Solutii Particulare). Forma-echelon pe randuri ne face viata mai usoara atunci cand trebuie sa determinam o solutie particulara. Pentru a face acest lucru, exprimam partea dreapta a sistemului de ecuatii folosind coloanele pivot, astfel incat \(\mathbf{b} = \sum_{i=1}^{P} \lambda_i \mathbf{p}_i\), unde \(\mathbf{p}_i\), \(i=1,\dots,P\), sunt coloanele pivot. \(\lambda_i\) sunt determinate cel mai usor daca incepem cu coloana pivot din dreapta si lucram spre stanga. In exemplul precedent, am incerca sa gasim \(\lambda_1, \lambda_2, \lambda_3\) astfel incat

$$ \lambda_1 \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix} + \lambda_2 \begin{bmatrix} 1 \\ 1 \\ 0 \\ 0 \end{bmatrix} + \lambda_3 \begin{bmatrix} -1 \\ -1 \\ 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 0 \\ -2 \\ 1 \\ 0 \end{bmatrix} $$

De aici, gasim relativ direct ca λ₃ = 1, λ₂ = -1, λ₁ = 2. Cand punem totul impreuna, nu trebuie sa uitam coloanele non-pivot pentru care am setat implicit coeficientii la 0. Prin urmare, obtinem solutia particulara x = [2, 0, -1, 1, 0]^T.

Observatie (Forma-Echelon Redusa pe Randuri). Un sistem de ecuatii este in forma-echelon redusa pe randuri (numita si forma-echelon pe randuri redusa sau forma canonica pe randuri) daca:

• Este in forma-echelon pe randuri.

• Fiecare pivot este 1.

• Pivotul este singura intrare diferita de zero din coloana sa.

Forma-echelon redusa pe randuri va juca un rol important mai tarziu deoarece ne permite sa determinam solutia generala a unui sistem de ecuatii liniare intr-un mod direct.

Observatie (Eliminarea Gaussiana). Eliminarea Gaussiana este un algoritm care efectueaza transformari elementare pentru a aduce un sistem de ecuatii liniare in forma-echelon redusa pe randuri.

Exemplu (Reducere la Forma-Echelon)
Verificati ca urmatoarea matrice este in forma-echelon redusa pe randuri (pivotii sunt cei care au valoarea 1):

$$ A = \begin{bmatrix} 1 & 3 & 0 & 0 & 3 \\ 0 & 0 & 1 & 0 & 9 \\ 0 & 0 & 0 & 1 & -4 \end{bmatrix} $$

Ideea cheie pentru gasirea solutiilor lui Ax=0 este sa ne uitam la coloanele fara pivot, pe care va trebui sa le exprimam ca o combinatie (liniara) a coloanelor pivot. Forma eșalon redusa pe linii face acest lucru relativ simplu, si exprimam coloanele fara pivot in termeni de sume si multipli ai coloanelor pivot care se afla la stanga lor: a doua coloana este de 3 ori prima coloana (putem ignora coloanele pivot din dreapta celei de-a doua coloane). Prin urmare, pentru a obtine 0, trebuie sa scadem a doua coloana din 3 x prima coloana. Acum ne uitam la coloana a cincea care este a doua coloana non-pivot. A cincea coloana poate sa fie exprimata ca de 3 ori prima coloana pivot, de 9 ori a doua coloana si de -4 ori a treia coloana pivot. Trebuie sa tinem evidenta indicilor coloanelor pivot si sa traducem aceasta in de 3 ori prima coloana, de 0 ori a doua coloana (care este o coloana fara pivot), de 9 ori a treia coloana (care este a doua noastra coloana pivot), si de -4 ori a patra coloana (care este a treia coloana pivot). Apoi trebuie sa scadem coloana a cincea pentru a obtine 0. In cele din urma, inca rezolvam un sistem de ecuatii omogen.
Pe scurt, toate solutiile lui Ax = 0, x ∈ R⁵ sunt date de:

$$ \left\{ \mathbf{x} \in \mathbb{R}^5 : \mathbf{x} = \lambda_1 \begin{pmatrix} 3 \\ -1 \\ 0 \\ 0 \\ 0 \end{pmatrix} + \lambda_2 \begin{pmatrix} 3 \\ 0 \\ 9 \\ -4 \\ -1 \end{pmatrix}, \lambda_1, \lambda_2 \in \mathbb{R} \right\} $$