Triangularizare Ortogonală Matematică

În algoritmul Gaussian, în loc să verificăm direct dacă pivotul este zero, verificăm dacă valoarea sa absolută este mai mică decât o constantă ɛ, numită epsilonul-mașină.

Dacă pivotul este mai mic sau egal cu ɛ, eliminarea Gaussiană eșuează. Aceasta înseamnă că matricea inițială are o submatrice singulară.

Matricea 𝑀𝑘 lasă nemodificate primele k - 1 coloane ale matricei 𝐴𝑘. Acestea sunt reprezentate de vectorii c j (A k ), cu j < k.

Matricea 𝑀𝑘 transformă coloana k a matricei 𝐴𝑘 zerorizând liniile k + 1, ⋯ , n. Aceasta se aplică la coloana k din 𝐴𝑘.

Vectorul 𝜂 ≠ 𝜉 este o combinație liniară a liniilor matricei A. 𝑀𝑘 transformă vectorul 𝜂, afectând doar componentele k + 1, ⋯ , n.

Reprezintă mulţimea valorilor proprii ale matricei G, care pot fi numere complexe.

Reprezintă valoarea absolută maximă a valorilor proprii |λi(G)| ale matricei G.

Condiţia necesară şi suficientă ca şirul de vectori x[k] să convergă către soluţia sistemului de ecuaţii este ca raza spectrală a matricei G să fie subunitară.

Reprezintă o normă matricială infinit, definită ca maximul sumei valorilor absolute de pe fiecare linie a matricei G.

O condiţie suficientă pentru ca raza spectrală a matricei G să fie subunitară este ca norma matricială infinit ||G||∞ să fie subunitară.

Metode iterative de rezolvare a sistemelor de ecuaţii liniare, bazate pe descompunerea matricei A în matrice triunghiulare L, D şi U.

Metoda Jacobi se bazează pe descompunerea matricei A ca suma dintre matricele L, D şi U, unde D este matricea diagonală a matricei A.

Metoda Gauss-Seidel este o metodă similară cu metoda Jacobi, dar foloseşte valorile calculate anterior pentru x[k+1] în calculul curent, ceea ce poate accelera convergenţa.

O matrice pătratică, unde elementele diagonalei principale sunt mai mari decât suma valorilor absolute a elementelor din fiecare linie a matricei.

Ecuația care exprimă condiția suficientă pentru convergența metodei Jacobi. Această condiție spune că suma modulelor elementelor din afara diagonalei principale, divizată la elementul diagonalei principale, trebuie să fie strict mai mică de 1, pentru fiecare linie a matricei.

Forma explicită a ecuației pentru calcularea celei de-a i-a necunoscute în pasul k+1, utilizând doar valorile necunoscutelor din pasul k.

În metoda Jacobi, o estimare inițială a soluției sistemului de ecuații liniare.

O matrice care rezultă din descompunerea matricei A în suma de trei matrice: D, L și U. Matricea D este o matrice diagonală, matricea L este o matrice triunghiulară inferioară cu elementele de pe diagonala principală egale cu 0, iar matricea U este o matrice triunghiulară superioară cu elementele de pe diagonala principală egale cu 0.

Pentru a demonstra convergența metodei Jacobi, este necesar ca matricea A să îndeplinească condiția de diagonală dominantă pe linii.

O afirmație care spune că dacă matricea A este diagonal dominantă pe linii, atunci metoda Jacobi este convergentă indiferent de ce estimare inițială se alege pentru a începe iterațiile. Această proprietate face metoda Jacobi o alegere atractivă pentru rezolvarea sistemelor de ecuații liniare.

Matricea A are rangul r, ceea ce înseamnă că are r coloane liniar independente, cu r fiind minimul dintre numărul de linii (m) și numărul de coloane (n) ale matricei.

Matricea A are un rang mai mic decât minimul dintre numărul de linii și numărul de coloane. Aceasta înseamnă că există cel puțin o relație liniară între coloanele matricei.

Matricea A are un rang egal cu minimul dintre numărul de linii și numărul de coloane. Aceasta înseamnă că toate coloanele sunt liniar independente.

O matrice diagonală cu elementele nenule 1, 2, ..., p, unde 1 ≥ 2 ≥ ... ≥ p ≥ 0.

O descompunere a unei matrice A în produsul a trei matrici: o matrice ortogonală U, o matrice pseudo-diagonală  și transpusa unei matrici ortogonale V.

Valorile singulare ale matricei A, ordonate descrescător. Ele reprezintă rădăcinile pătrate ale valorilor proprii ale matricei A * A^T.

Un vector propriu al matricei A * A^T corespunzător valorii proprii i^2.

Un vector propriu al matricei A^T * A corespunzător aceleiași valori proprii i^2.

O matrice Q se numește ortogonală dacă satisface una din relațiile: QT  Q  Im sau Q T  Q 1. Aceasta implică faptul că transpusa lui Q este inversa lui Q, iar produsul scalar al oricăror două coloane distincte din Q este 0, iar norma euclidiană a fiecărei coloane este 1.

O matrice Householder este o matrice ortogonală care se obține dintr-o matrice identică prin scăderea unei matrici formate prin produsul dintre un vector Householder și transpusa acestuia, împărțit la norma sa pătrată. Vectorul Householder este un vector non-nul cu o singură componentă ne-nulă.

Un vector Householder este un vector non-nul cu o singură componentă ne-nulă. Se folosește la construirea unei matrici Householder.

Procedura de triangularizare ortogonală a matricei A este o metodă de a găsi o descompunere a A în produsul dintre o matrice ortogonală și o matrice triunghiulară superioară.

Factorizarea QR a unei matrice A este o descompunere a matricei A în produsul dintre o matrice Q ortogonală și o matrice R triunghiulară superioară. Această descompunere se obține prin triangularizare ortogonală.

Algoritmul de triangularizare ortogonală a matricii A implică transformarea matricei prin multiplicarea cu o serie de matrici Householder astfel încât să se obțină o matrice triunghiulară superioară. Matricea Householder se obține prin calculul vectorului Householder.

În algoritmul de triangularizare ortogonală, se determină matricele Householder U k, care transformă coloana k a matricei Ak într-o coloană cu componentele de la k + 1 la m egale cu zero. Această transformare se realizează prin multiplicarea matricii Ak cu matricea Uk.

Vectorul  este o coloană a matricei Ak. Se calculează norma sa pătrată, notată cu  k, pentru a determina vectorul Householder u k. Vectorul u k se obține prin componentele lui , cu excepția componentei k, care se calculează ca suma componentei k din  și  k.

În algoritmul de triangularizare ortogonală, se atribuie matricei Ak o nouă matrice A k 1, care este o coloană vectorilor Householder, obținută prin multiplicarea A k cu matricea Householder U k. Această operație se execută pentru fiecare coloană a matricii inițiale A.

Matricea R este o matrice triunghiulară superioară, obținută prin aplicarea mai multor matrici Householder asupra matricei inițiale A. Matricea R are o structură specifică, cu componentele de sub diagonala principală egale cu zero.

Valorile singulare ale unei matrice A (notate cu 1, ..., p) sunt valorile proprii ale matricei A^TA.

Forma canonică diagonală a unei matrice A (notată cu ) este o matrice diagonală cu elementele de pe diagonala principală egale cu valorile singulare ale lui A.

Orice matrice este ortogonal echivalentă bilateral cu o matrice (pseudo)diagonală. Aceasta înseamnă că există două matrici ortogonale U și V astfel încât A = UV^T.

Rangul unei matrice A este egal cu numărul valorilor singulare nenule ale lui A.

Vectorii singulari la dreapta ai matricei A sunt coloanele matricei V. Vectorii singulari la stânga ai matricei A sunt coloanele matricei U.

Pentru orice valoare singulară _i, vectorul singular la stânga u_i se obține prin aplicarea matricei A asupra vectorului singular la dreapta v_i, apoi prin normalizarea rezultatului.

Vectorii singulari la dreapta formează o bază ortonormală pentru spațiul liniar al coloanelor matricei A.

Vectorii singulari la stânga formează o bază ortonormală pentru spațiul liniar al liniilor matricei A.

Decompunerea valorilor singulare (SVD) este un instrument util pentru analiza și manipulare matricială. Este utilizat în multe domenii, cum ar fi procesarea imaginilor, analiza datelor și învățarea automată.