Metoda Numerică - Ecuații Algebrice Liniare

<p>Multiplicarea matricelor 𝑀𝑘^−1 cu 𝑘 = 1, ⋯ , n − 1. (D)</p> Signup and view all the answers

<p>Un element nul, care apare datorită zerorizării liniilor 𝑘 + 1, ⋯ , 𝑛. (D)</p> Signup and view all the answers

<p>A rezolva sisteme liniare de ecuații în mod eficient. (C)</p> Signup and view all the answers

<p>O factorizare a matricei în două matrice triunghiulare. (D)</p> Signup and view all the answers

<p>Substituția înainte pentru L ∙ y = b. (B)</p> Signup and view all the answers

<p>Trebuie să fie pozitiv definită. (D)</p> Signup and view all the answers

<p>3n^3 (D)</p> Signup and view all the answers

<p>A = L ∙ U. (D)</p> Signup and view all the answers

<p>Transformarea sistemului într-un sistem echivalent ușor de rezolvat (B)</p> Signup and view all the answers

<p>O matrice superior triunghiulară (B), O matrice inferior triunghiulară (C)</p> Signup and view all the answers

<p>Să fie nesingulare (B)</p> Signup and view all the answers

<p>Când acestea devin convergente la o soluție (C)</p> Signup and view all the answers

<p>Triunghiulară inferioară (A)</p> Signup and view all the answers

<p>O matrice diagonală (D)</p> Signup and view all the answers

<p>Eliminarea gaussiană (A)</p> Signup and view all the answers

<p>Când variația între soluțiile succesive devine mai mică decât un $ ext{ε}$ impus (A)</p> Signup and view all the answers

<p>Transformă matricea $A_k$ în matricea $A_{k+1}$. (D)</p> Signup and view all the answers

<p>$M_k = I_n - m_k imes e_k$ (C)</p> Signup and view all the answers

<p>Elementele sub diagonala principală sunt zerorizate. (B)</p> Signup and view all the answers

<p>$m_k = egin{bmatrix} 0 \ au_k \ 0 \ au_{n,k} \ 0 \ 0 \ au_{k+1,k} \ au_{n,k} \ 0 \\ au_j \\ 0 \ 0 \\ au_i \ 0 \ 0 \\ au_n \\ 0 \ 0 \ 0 \\ 0 \ 0 igr]$ (A)</p> Signup and view all the answers

<p>$n - 1$ (D)</p> Signup and view all the answers

<p>Sunt inferioare triunghiulare și nesingulare. (A)</p> Signup and view all the answers

<p>Vectorul obținut are anumite componente egale cu zero. (B)</p> Signup and view all the answers

<p>O constantă mică sau foarte mică care indică toleranța erorilor. (A)</p> Signup and view all the answers

<p>Transformarea produce valori zero în anumite coloane. (A)</p> Signup and view all the answers

<p>Matricea inițială A are submatricea principală singulară. (C)</p> Signup and view all the answers

<p>Pivotul să fie mai mare decât 𝜖. (D)</p> Signup and view all the answers

<p>Raportul componentelor vectorului 𝜉. (B)</p> Signup and view all the answers

<p>Matricea are un determinant diferit de zero. (D)</p> Signup and view all the answers

<p>Un pas de calcul pentru obținerea vectorului x. (A)</p> Signup and view all the answers

<p>Este instabilă numeric, amplificând erorile. (D)</p> Signup and view all the answers

<p>Ajută la stabilizarea algoritmului de triangularizare. (B)</p> Signup and view all the answers

<p>Primele k coloane ale matricei A sunt liniar dependente. (A)</p> Signup and view all the answers

<p>Permută liniile matricei A pentru a îmbunătăți stabilitatea. (C)</p> Signup and view all the answers

<p>P * A = L' * U (B)</p> Signup and view all the answers

<p>Se caută maximul pe coloana k de la rândul k la rândul n. (B)</p> Signup and view all the answers

<p>Matricea inferior triunghiulară unitate. (B)</p> Signup and view all the answers

<p>Factorizarea matricei $A$ în $L' ullet U$. (A)</p> Signup and view all the answers

<p>O matrice cu rândurile ordonate după un anumit criteriu. (A)</p> Signup and view all the answers

<p>Este formată din permutarea liniilor matricei originale. (C)</p> Signup and view all the answers

<p>Elementul maxim din coloana k. (C)</p> Signup and view all the answers

<p>Triangularizare LU. (C)</p> Signup and view all the answers

Signup and view all the answers

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.