Metoda Numerică - Ecuații Algebrice Liniare

O metodă de descompunere a unei matrice în produsul a două matrici: o matrice inferioară triunghiulară (L) și o matrice superioară triunghiulară (U).

Un algoritm pentru descompunerea unei matrice în forma L-U. Se bazează pe transformări de asemănare pentru a aduce matricea la forma superior triunghiulară.

Metoda de rezolvare a unui sistem liniar folosind descompunerea L-U. Implică două etape: substituția înainte (rezolvarea sistemului cu matricea L) și substituția inversă (rezolvarea sistemului cu matricea U).

O formă specială de descompunere L-U pentru matrici simetrice și pozitiv definite. Matricea A este descompusă în produsul matricei inferioare triunghiulare (L) și a transpusei sale (L^T).

Un algoritm pentru descompunerea unei matrice simetrice și pozitiv definite în forma Cholesky. Reprezintă un caz special al descompunerii L-U.

Un algoritm folosit pentru a transforma o matrice în formă triunghiulară superioară prin eliminarea elementelor de sub diagonala principală.

Un pas din algoritmul de triangularizare directă, unde elementele de sub diagonala principală din coloana k sunt zerorizate. Operația se repetă pentru fiecare coloană, cu excepția ultimei.

O matrice care elimină elementele de sub diagonala principală din coloana k a matricei originale. Utilizează multiplicatori pentru a determina elementele matricii.

Un vector care conține multiplicatorii utilizați în matricea 𝑀𝑘 pentru a zeroriza elementele de sub diagonala principală.

O coloană a matricei originale, utilizată pentru a determina multiplicatorii din 𝑚𝑘. Notația indică coloana k din matricea 𝐴𝑘.

O metodă numerică pentru rezolvarea sistemelor de ecuații liniare determinante care implică transformarea sistemului într-o formă echivalentă, mai ușor de rezolvat.

O metodă numerică pentru rezolvarea sistemelor de ecuații liniare determinate care implică construirea unei aproximări succesive a soluției, convergând către soluția exactă.

O matrice cu elemente nenule doar pe diagonala principală și dedesubt.

O matrice cu elemente nenule doar pe diagonala principală și deasupra.

O matrice cu elemente nenule doar pe diagonala principală.

O metodă numerică care transformă un sistem de ecuații liniare într-o formă echivalentă, unde matricea coeficienților este triunghiulară superior.

O submatrice formată din primele n-1 linii și n-1 coloane ale matricei A.

O submatrice care este inversabilă (are determinant diferit de 0).

Matricea 𝑀𝑘 transformă coloana k a matricei 𝐴𝑘 zerorizând liniile 𝑘 + 1, ⋯ , 𝑛.

Matricea 𝑀𝑘 lasă nemodificate primele k – 1 coloane ale matricei 𝐴𝑘.

Matricea 𝑀𝑘 transformă coloanele 𝑘 + 1, ⋯ , 𝑛 ale matricei 𝐴𝑘 în liniile 𝑘 + 1, ⋯ , 𝑛.

Matricea L este o matrice inferior triunghiulară unitate, în care elementele sub diagonala principală sunt subvectorii Gauss.

Relația dintre matricele A, L și U: A = L  U

L = M 1−1  M −21    M −n1−1 = I n +  m k  e k T, k =1

Factorizarea LU transformă matricea A într-o matrice superior triunghiulară U

Matrici triunghiulare inferioare, cu elemente diagonale principale egale cu 1, nesingulare, cu inversa calculata prin formula: M^(-1)_k = I_n + m_k * e^T_k

Aplicarea matricei M_k asupra vectorului 𝜉 modifică componentele vectorului, eliminând elementele de sub pivotul de pe coloana k

Multimplicatorii Gauss, 𝜇_i,k, se calculează ca raportul dintre elementul de pe linia i și elementul de pe linia pivot, k.

Eliminarea Gauss transformă vectorul 𝜉 [ξ1 ... ξk ... ξn]T într-un vector cu toate elementele nule de sub pivot: [ξ1 ... ξk 0 ... 0]T

În calculele pe calculator, se verifică dacă valoarea absolută a pivotului este mai mare decât un epsilon (ε), o valoare mică care reprezintă eroarea de rotunjire

Eșecul eliminării Gauss se datorează faptului că submatricea principală de ordin k a matricei A este singulară, deci descompunerea LU nu există

Transformarea M_k modifică elementele de pe liniile k+1,...,n din vectorul , scăzând un multiplu al elementului de pe linia k

Eliminarea Gauss transformă un sistem de ecuații liniare într-un sistem echivalent superior triunghiular, permiţând rezolvarea prin substituţie înapoi.

Prima etapă în rezolvarea unui sistem de ecuații liniare A ∙ x = b este substituția înainte aplicată sistemului de ecuații L ∙ y = b, obținând y = L⁻¹ ∙ b = Mₙ⁻¹ ∙ ⋯ ∙ M₂ ∙ M₁ ∙ b.

În triangularizarea simplă, elementele matricei A sunt modificate conform relației: a[ijk+1] = a[ijk] − 𝜇ik ∙ a[kjk], i = k + 1,..., n; j = k,..., n. Multiplicatorii 𝜇𝑖𝑘 pot avea orice valoare. Dacă aceștia sunt mari sau foarte mari, pot apărea fenomene de omitere catastrofală și/sau de neutralizare a termenilor, amplificând erorile prezente în termenii 𝑎𝑘𝑗. Astfel, triangularizarea simplă este instabilă numeric.

Stabilizarea algoritmului de triangularizare se realizează prin folosirea multiplicatorilor Gauss cu modul subunitar.

În algoritmul de triangularizare cu pivotare parțială, la pasul k se caută pivotul printre elementele din coloana k, pornind de la elementul de pe diagonala principală în jos, alegându-se elementul cu cea mai mare valoare în modul: |a[ikk],k| = max{|a[i,kk]} = k, k  i  n. Dacă 𝑖𝑘 ≠ 𝑘, se permută liniile k și 𝑖𝑘 cu ajutorul matricei de permutare de linii Pk.

Matricea de permutare de linii Pk are proprietatea: det(Pk) = −1; Pk = Pk⁻¹.

Matricea A este nesingulară, atunci există o matrice, numită matrice generală de permutare de linii, astfel încât: P ∙ A = L' ∙ U, unde U este o matrice superior triunghiulară, iar L' este o matrice inferior triunghiulară unitate, având elementele |l i, j | 1, i  j.

Algoritmul de triangularizare cu pivotare parțială se bazează pe iterații succesive, unde la fiecare pas se caută pivotul, se permută liniile (dacă e necesar) și se determină matricea Mk pentru a transforma matricea A în A(k+1) cu elementele a[i,k] = 0 pentru i = k+1,..., n. La final, obținem matricea U ca matrice A(n).

Transformarea generală care se aplică matricei A este: M n −1  Pn −1  ⋯  M 2  P2  M 1  P1  A = U. Folosind proprietatea 𝑃𝑘 = 𝑃𝑘−1, obținem: L' = Pn −1  ⋯  P2  M1⁻¹  P2  M −2¹  ⋯  Pn −1  M −n¹⁻¹, care reprezintă o matrice inferior triunghiulară unitate.

Rezolvarea sistemului A ∙ x = b se face in 4 etape: 1) Factorizarea L_U a matricei A (P ∙ A = L' ∙ U); 2) Calculul vectorului c = P ∙ b; 3) Rezolvarea sistemului L' ∙ y = c prin substituție înainte; 4) Rezolvarea sistemului U ∙ x = y prin substituție inversă.

Dacă algoritmul de triangularizare cu pivotare parțială eşuează, în sensul că pivotul găsit la o anumită etapă [k] este nul sau foarte mic în modul, înseamnă că primele k coloane ale matricei A sunt liniar dependente.

Matricea L' este o matrice inferioară triunghiulară unitate, având pe fiecare coloană, sub diagonala principală, subvectori Gauss cu liniile permutate.

Prin aplicarea triangularizării cu pivotare parțială, se reduce riscul de propagare a erorilor, asigurând o rezolvare stabilă numeric a sistemului de ecuații liniare.

Triangularizarea cu pivotare parțială este o metodă robustă și eficientă de rezolvare a sistemelor de ecuații liniare, asigurând o soluție numeric stabilă prin selectarea pivotului optim.

Substituția înapoi se aplică sistemului U ∙ x = y, unde y este soluția sistemului L' ∙ y = c. Se începe cu a găsi x(n) (ultima variabilă), utilizând ultimele ecuații din sistem și se calculează în ordine inversă până se obține x(1)

Triangularizarea cu pivotare parțială transformă sistemul A ∙ x = b într-un sistem echivalent, L' ∙ U ∙ x = P ∙ b, unde L' este o matrice inferioară triunghiulară unitate, U este o matrice superioară triunghiulară, iar P este matricea de permutare de linii.