Metode Numerice - Curs 1

O metodă numerică pentru găsirea inversei unei matrice A care presupune factorizarea ei în două matrice triunghiulare: L (inferioară) și U (superioară).

Un set de metode numerice folosite pentru a aproxima soluția unui sistem de ecuații liniare prin construirea unei secvențe de vectori care converg la soluția exactă.

Un pas din metoda iterativă care calculează o nouă aproximație a soluției sistemului bazându-se pe aproximația anterioară.

Matricea din descompunerea matricei inițiale (A) care corespunde părții iterate a metodei.

Matricea din descompunerea matricei inițiale (A) care corespunde părții neiterate a metodei.

Un vector format din toate elementele nule, cu excepția elementului de pe poziția k, care are valoarea 1.

Metoda de rezolvare a sistemelor de ecuații care implică substituția înainte (în matricea L) și substituția inversă (în matricea U).

O metodă numerică pentru găsirea soluției unui sistem de ecuații liniare prin aproximarea iterativă, utilizând o relație de recurență.

Matricea obținută din descompunerea matricei inițiale (A) care corespunde părții iterate din metoda Jacobi, folosind doar diagonala matricei A.

Matricea obținută din descompunerea matricei inițiale (A) care corespunde părții neiterate din metoda Jacobi, având valori zero pe diagonala principală.

Condiția suficientă pentru ca metoda Jacobi să fie convergentă, adică să convergă către soluția exactă a sistemului de ecuații.

O matrice în care elementul de pe diagonala principală are modulul mai mare decât suma modulelor celorlalte elemente de pe aceeași linie.

O proprietate a matricei A cu care, dacă este îndeplinită, metoda Jacobi este garantată a fi convergentă, indiferent de estimația inițială a soluției.

Relația de recurență care este utilizată în metoda Jacobi pentru a calcula o nouă aproximație a soluției sistemului de ecuații.

Un set de vectori liniar independenți care generează întregul spațiu vectorial.

Mulțimea tuturor vectorilor care pot fi obținuți prin aplicarea transformării liniare reprezentate de matricea A.

Mulțimea tuturor vectorilor care, atunci când se aplică transformării liniare reprezentate de matricea A, obțin vectorul nul.

Procesul de descompunere a unei matrice A în produsul a trei matrice: o matrice ortogonală U, o matrice diagonală  (care conține valorile singulare) și o matrice ortogonală V.

Valorile singulare ale matricii A sunt rădăcinile pătrate ale valorilor proprii ale matricei A^T * A.

O metodă numerică pentru calcularea descompunerii valorilor singulare (SVD) a unei matrice.

Transformarea unei matrice în formă superior bidiagonală prin aplicarea unor transformări ortogonale.

Zerorizarea elementelor de pe prima supradiagonală a formei superior bidiagonale, folosind matrici de rotație plană Givens.

Numărul de valori singulare nenule ale unei matrice.

O soluție a unui sistem de ecuații liniare care minimizează eroarea pătratică.

Un sistem de ecuații liniare care are matricea coeficienților de rang complet și există o soluție unică.

O metodă de rezolvare a sistemelor de ecuații liniare care minimizează eroarea pătratică între soluția obținută și soluția exactă.

Blocurile diagonale de ordinul întâi ale matricii S reprezintă valorile proprii reale ale matricii A şi ale matricii S. Blocurile diagonale de ordinul doi conțin valori proprii complex conjugate.

Metoda QR este o metodă numerică de găsire a formei canonice Schur a unei matrice prin crearea unui șir de matrici ortogonale asemenea, care converge la forma canonică Schur.

Şirul de matrici {A k }k ≥ 0, unde A 0 = A, este definit cu scopul de a obține forma canonică Schur prin iterații.

O etapă din algoritmul QR care presupune descompunerea matricii A k -  k * I n în produsul a două matrici: una ortogonală (Q k ) și una superior triunghiulară (R k ).

Matricea Q k din pasul QR cu deplasare explicită este o matrice ortogonală, cu rol de a asigura ortogonalitatea transformărilor între matrici.

Matricea R k din pasul QR cu deplasare explicită este o matrice superior triunghiulară, care simplifică operațiile de calcul prin structura sa specială.

Un scalar ce reprezintă o deplasare aplicată matricii A k în pasul QR, având rolul de a accelera convergența algoritmului.

Matricele din şirul QR sunt ortogonale între ele, asigurând că forma canonică Schur este o reprezentare similară a matricei inițiale.

Prima fază a algoritmului QR cu deplasare explicită, având scopul de transforma matricea A la forma superior Hessenberg (H).

A doua fază a algoritmului QR, având scopul de a aplica algoritmul QR propriu-zis pe matricea H obținută în faza 1 pentru a obține forma canonică Schur.

O matrice particulară, de tipul superior Hessenberg, care are elemente zero sub subdiagonala principală.

O matrice particulară, cu elemente zero sub diagonala principală, exceptand elementele de pe sub-diagonala principală.

Matricea Householder (U k + 1 ) este o matrice ortogonală folosită pentru a anula elementele de sub sub-diagonala principală a matricei A.

O procedura directă de aducere a matricei A la forma superior Hessenberg prin anularea succesiva a elementelor de sub sub-diagonala principală.

Urmărirea etapelor necesare pentru a obține forma canonică Schur a matricei inițiale A prin intermediul algoritmului QR.

Valorile singulare ale matricei A sunt reprezentate de 1 ,  ,  p    , iar forma canonică diagonală a matricei A este    mn.

Descompunerea valorilor singulare (SVD) a unei matrice A se referă la reprezentarea sa ca produs a trei matrice: U,  și V. U și V sunt matrice ortogonale, iar  este o matrice diagonală cu valorile singulare ale lui A pe diagonala principală. Această descompunere este unică, iar  este formată din valorile singulare ale matricii in ordine descrescătoare dinspre stânga spre dreapta.

Orice matrice poate fi reprezentată ca produsul a două matrice ortogonale și o matrice pseudo-diagonală. Cu alte cuvinte, o matrice poate fi transformată într-o formă diagonală prin înmulțirea la stânga și la dreapta cu matrice ortogonale.

Forma canonică diagonală () a matricei A poate avea o structură diferită în funcție de relația dintre m (numărul de linii) și n (numărul de coloane) ale matricei A, precum și de rangul (r) al matricei. De exemplu, când m ≥ n și rang(A) = r = p = n, matricea  va avea forma  1        , 1  diag{1 ,  ,  n } 0 ( m  n )n   . Alte situații se pot produce când m < n sau rang(A) < p.

O matrice de rang complet are un rang egal cu numărul de linii sau de coloane, în timp ce o matrice deficitară de rang are un rang mai mic decât numărul de linii sau de coloane.

Rangul matricei A este egal cu rangul matricei , care este egal cu r. Acest lucru se datorează faptului că rangul unei matrice este definit ca numărul de coloane liniar independente. Matricea  are r valori singulare nenule, deci rangul ei este r.

Descompunerea în valori singulare poate fi scrisă sub forma: A  V  U  . Vectorii coloană ai lui V se numesc vectori singulari la dreapta, iar vectorii coloană ai lui U se numesc vectori singulari la stânga.

Vectorul singular la dreapta (vi) este un vector care, atunci când este înmulțit cu matricea A, rezultă un vector singular la stânga (ui) înmulțit cu valoarea singulară (i). Invers, atunci când vectorul singular la stânga (ui) este înmulțit cu matricea A (transpus), rezultă vectorul singular la dreapta (vi) înmulțit cu valoarea singulară (i)

Coloane matricei V sunt vectorii singulari la dreapta (vi) ai matricei A. Un vector singular la dreapta reprezintă o direcție în spațiul coloanelor matricei A, iar dimensiunea sa este dată de valoarea singulară asociată.

Coloane matricei U sunt vectorii singulari la stânga (ui) ai matricei A. Aceștia reprezintă direcții în spațiul rândurilor matricei A, iar dimensiunile lor sunt determinate de valorile singulare asociate.