Metode Numerice - Curs 4 PDF

METODE NUMERICE – curs 4 Cap. 2 Sisteme determinate de ecuaţii algebrice liniare 2.3 Rezolvarea sistemelor prin triangularizare cu pivotare parţială  se consideră sistemul de n ecuaţii algebrice liniare cu n necunoscute: 𝐴 ∙ 𝑥 = 𝑏, 𝐴 ∈ ℝ𝑛×𝑛 , 𝑏...

METODE NUMERICE – curs 4 Cap. 2 Sisteme determinate de ecuaţii algebrice liniare 2.3 Rezolvarea sistemelor prin triangularizare cu pivotare parţială  se consideră sistemul de n ecuaţii algebrice liniare cu n necunoscute: 𝐴 ∙ 𝑥 = 𝑏, 𝐴 ∈ ℝ𝑛×𝑛 , 𝑏 ∈ ℝ𝑛×1  problema de calcul  determinarea unei soluţii 𝑥 ∈ ℝ𝑛×1 care să verifice sistemul dat  principiu: 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 care are cea mai mare valoare în modul: | a [i k ],k | max{| a [i,kk] |}   k k k i  n  dacă 𝑖𝑘 ≠ 𝑘  se permută liniile k şi 𝑖𝑘 cu ajutorul matricii de permutare de linii 𝑃𝑘 k Ak = 0 Pk  A k A k 1  M k  (Pk  A k )  ik n | k |  i,k | 1, i  k  1,..., n Fig. 2.1 Principiul triangularizării cu pivotare parţială a unei matrice: pivotul se găseşte în coloana k, liniile k  n; k = 1, …, n - 1 METODE NUMERICE – curs 4  proprietăţi matrice de permutare de linii, Pk: det(Pk )  1; Pk  Pk1 Teoremă: Dacă matricea A este nesingulară, atunci există o matrice numită matrice generală de permutare de linii, astfel încât: P  A  L'  U în care U este o matrice superior triunghiulară şi Lˈ este o matrice inferior triunghiulară unitate cu elementele |ℓ𝑖,𝑗 | ≤ 1, 𝑖>𝑗  Demonstraţia  constructivă, constituind însuşi algoritmul de triangularizare cu pivotare parţială a unei matrici METODE NUMERICE – curs 4  algoritmul de triangularizare cu pivotare parţială: atribuie 𝐴1 ⟵ 𝐴 pentru 𝑘 = 1, 𝑛 − 1 execută [𝑘] [𝑘] [𝑘] determinare 𝜉𝑘 ← 𝑎𝑖𝑘 ,𝑘 unde 𝑎𝑖𝑘 ,𝑘 = max 𝑎𝑖,𝑘 𝑖=𝑘,𝑛 dacă (𝑖𝑘 ≠ 𝑘) atunci determină 𝑃𝑘 altfel atribuie 𝑃𝑘 ← 𝐼𝑛  calcul 𝑃𝑘 ∙ 𝐴𝑘 determinare matrice 𝑀𝑘 astfel încât 𝐴𝑘+1 = 𝑀𝑘 ∙ 𝑃𝑘 ∙ 𝐴𝑘 să aibă elementele: [𝑘+1] [𝑘+1] [𝑘] 𝑎𝑖,𝑘 = 0, 𝑖 = 𝑘 + 1, … , 𝑛 şi 𝑎𝑖,𝑗 = 𝑎𝑖,𝑗 , 𝑖 = 1, … , 𝑛; 𝑗 = 1, … , 𝑘 − 1 atribuie 𝐴𝑘+1 ⟵ 𝑀𝑘 ∙ 𝑃𝑘 ∙ 𝐴𝑘  atribuie 𝑈 ⟵ 𝐴𝑛  METODE NUMERICE – curs 4  tabloul general al transformărilor: M n 1  Pn 1    M 2  P2  M1  P1  A  U - folosind 𝑃𝑘 = 𝑃𝑘−1 (M n 1  Pn 1    M1  P1  P1  P2    Pn 1 )  (Pn 1    P2  P1 )  A  U −1 P 𝐿′ matrice generală de permutare de linii P  A  L'  U L'  Pn 1    P2  M11  P2  M 21    Pn 1  M n11 matrice inferior triunghiulară unitate având în fiecare coloană, sub diagonala principală, subvectori Gauss cu liniile permutate METODE NUMERICE – curs 4  etapele rezolvării sistemului 𝐴 ∙ 𝑥 = 𝑏, A ∈ ℝ𝑛×𝑛 , 𝑏 ∈ ℝ𝑛×1: a) factorizarea L_U a matricii A prin triangularizare cu pivotare parţială: P  A  L'  U b) calculul vectorului: 𝑐 = 𝑃 ∙ 𝑏 c) rezolvare sistem 𝐿′ ∙ 𝑦 = 𝑐 prin substituţie înainte d) Rezolvare sistem 𝑈 ∙ 𝑥 = 𝑦 prin substituţie inversă PAx Pb L'  U  x  P  b P  A  L'  U cPb L'  y  c yUx  Observaţie: 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, aceasta corespunde situaţiei când în aritmetica reală primele k coloane ale matricei A sunt liniar dependente.  METODE NUMERICE – curs 4 2.4 Aplicaţii ale descompunerilor L-U 2.4.1 Calculul determinantului  fie o matrice 𝐴 ∈ ℝ𝑛×𝑛  det 𝐴 =? a) calcul bazat pe factorizarea L-U prin triangularizare directă: 𝐴 = 𝐿 ∙ 𝑈 det(A)  det(L  U)  det(L)  det(U) L – inferior triunghiulară unitate ⇒ det 𝐿 = 1 U – superior triunghiulară ⇒ det 𝑈 = ς𝑛𝑖=1 𝑢𝑖,𝑖 , 𝑈 = 𝑢𝑖,𝑖 𝑖=1,…,𝑛 n det(A)   u i ,i i 1 METODE NUMERICE – curs 4 b) calcul bazat pe factorizarea L-U prin triangularizare cu pivotare parţială: P ∙ 𝐴 = 𝐿′ ∙ 𝑈 A  P 1  L'  U det(A)  det(P 1  L'  U)  det(P 1 )  det(L' )  det(U) 𝑛 𝑛 det 𝐴 = −1 𝑛𝑝ℓ ∙ ෑ 𝑢𝑖,𝑖 (−1)𝑛𝑝ℓ 1 ෑ 𝑢𝑖,𝑖 𝑖=1 𝑖=1 2.4.2 Calculul inversei unei matrici  fie o matrice 𝐴 ∈ ℝ𝑛×𝑛  𝐴−1 =?  acest tip de problemă se încadrează în problematica rezolvării ecuaţiilor matriciale de tipul: 𝐴 ∙ 𝑋 = 𝐵, în care 𝐵 = 𝐼𝑛 A 1  X  x 1  x k  xn  METODE NUMERICE – curs 4 a) calcul bazat pe factorizarea L-U prin triangularizare direct a.1) factorizarea 𝐴 = 𝐿 ∙ 𝑈; k a.2) rezolvare sisteme: 𝐴 ∙ 𝑥𝑘 = 𝑒𝑘 , 𝑒𝑘 = 0 ⋯ 0 1 0 ⋯ 0 𝑇 , 𝑘 = 1, 𝑛 - substituţia înainte: 𝐿 ∙ 𝑦𝑘 = 𝑒𝑘 - substituţia inversă: 𝑈 ∙ 𝑥𝑘 = 𝑦𝑘 b) calcul bazat pe triangularizarea cu pivotare parţială: b.1) factorizarea 𝑃 ∙ 𝐴 = 𝐿′ ∙ 𝑈; k b.2) rezolvare sisteme: 𝐴 ∙ 𝑥𝑘 = 𝑒𝑘 , 𝑒𝑘 = 0 ⋯ 0 1 0 ⋯ 0 𝑇 , 𝑘 = 1, 𝑛 - calcul 𝑐 = 𝑃 ∙ 𝑒𝑘 ; - substituţia înainte: 𝐿′ ∙ 𝑦𝑘 = 𝑐; - substituţia inversă: 𝑈 ∙ 𝑥𝑘 = 𝑦𝑘 Concluzie: Inversarea unei matrice necesită un număr mare de operaţii în virgulă mobile  în practică, nu se recomandă rezolvarea sistemelor prin metoda bazată pe calculul explicit al inversei matricei sistemului.  METODE NUMERICE – curs 4 2.4 Metode iterative 2.4.1 Principiul şi convergenţa metodelor iterative A  x  b, A   nn , b   n1 A - matrice nesingulară  Metodele iterative  construcţia unui şir de vectori convergent la soluţia sistemului:  x , x [k] , k  0,1,... [k] x lim x k   Relaţia de recurenţă: ANP N - matrice nesingulară ( N  P)  x  b  N  x  P  x  b  Nx [ k 1] Px [k]  b, k  0,1,...  [ k 1]  N 1  P  x  N 1  b, k  0,1,... [k] x Notaţie: G  N 1  P, G   nn  calculele se opresc la un index de iterare [s], când este îndeplinită condiţia: [s 1] x ||   impus [s ] || x  METODE NUMERICE – curs 4  G are valori proprii în general complexe, care formează mulţimea numită spectrul matricei G (G )  max{|  i (G ) |} - rază spectrală a matricei G 1i  n Teoremă: Condiţia necesară şi suficientă ca şirul de vectori să fie convergent către soluţia sistemului de ecuaţii este ca matricea G să aibă toate valorile proprii în modul subunitare sau, altfel spus, raza spectrală a matricei G să fie subunitară.  Observaţii:  Cu cât raza spectrală subunitară a matricei G este mai mică, cu atât viteza de convergenţă a şirului de vectori este mai mare  În practică, de multe ori, condiţia necesară şi suficientă prezentată anterior se înlocuieşte printr-o condiţie suficientă, dacă este posibil, şi anume: dacă || G ||   1 atunci (G )  1  norma matricială infinit n || G ||   max{ | g i , j |}  1 1i  n j1  METODE NUMERICE – curs 4  Se consideră: ALDU L - inferior triunghiulară cu diagonala principală nulă D - diagonală având elementele de pe diagonala principală egale cu elementele de pe diagonala principală a matricei A (se presupune nesingulară) U - superior triunghiulară cu diagonala principală nulă 2.4.2 Metoda Jacobi şi metoda Gauss-Seidel  metoda Jacobi N  D, P  (L  U) ⇒ D  x [ k 1]  (L  U)  x [ k ]  b, k  0,1,... ⇕ n a i ,i  x [i k 1]   a i , j  x [jk ]  b i , i  1,..., n j1 a i,i  0 j i ⇙ n x [i k 1]  (b i / a i ,i )   (a i , j / a i ,i )  x [jk ] , i  1,..., n j1 j i METODE NUMERICE – curs 4 1 1 0, i j G Jacobi  N  P  D  (L  U)  [g i , j ]1i , j n g i, j   a i , j / a i ,i , i  j  Condiţia suficientă care se impune pentru ca metoda Jacobi să fie convergentă este: n n max{ | g i , j |}  max{ | a i , j / a i ,i |}  1 1i  n j1 1i  n j1 j i ⇓ n n  | a i , j / a i ,i |  1  | a i ,i |  | a i , j | j1 j1 j i j i  A - matrice diagonal dominantă pe linii Propoziţie: Dacă matricea A este diagonal dominantă pe linii, atunci metoda Jacobi este convergentă, oricare ar fi estimaţia iniţială a soluţiei sistemului de ecuaţii.  CALCULNUMERICE METODE UMERIC ––curs curs44 Observaţie: | a i , j / a i ,i | 1 i  1,..., n , j  1,..., n , i  j sunt coeficienţii care multiplică componentele calculate la iteraţii anterioare, deci erorile ce le afectează sunt micşorate pe măsură ce procesul iterativ avansează A - diagonal dominantă pe linii ⇒ procedura este sigur stabilă numeric  metoda Gauss-Seidel N  L  D, P   U ⇒ (L  D)  x [ k 1]   U  x [ k ]  b, k  0,1,... ⇕ i n  a i , j  x [jk 1]    a i , j  x [jk ]  b i , i  1,..., n j1 ji 1 a i,i  0 ⇙ 𝑖−1 𝑛 [𝑘+1] 𝑏𝑖 𝑎𝑖,𝑗 𝑘+1 [𝑘] 𝑥𝑖 = −෍ ⋅ 𝑥𝑗 − ෍ (𝑎𝑖,𝑗 /𝑎𝑖,𝑖 ) ⋅ 𝑥𝑗 , 𝑖 = 1,... , 𝑛 𝑎𝑖,𝑖 𝑎𝑖,𝑖 𝑗=1 𝑗=𝑖+1 METODE NUMERICE – curs 4 Observaţie: Şi în cazul metodei Gauss-Seidel, dacă matricea A este diagonal dominantă pe linii, atunci metoda este convergentă  Între razele spectrale subunitare corespunzătoare celor două metode există relaţia: 𝜌𝐺2𝐽𝑎𝑐𝑜𝑏𝑖 ≅ 𝜌𝐺𝑎𝑢𝑠𝑠−𝑆𝑒𝑖𝑑𝑒𝑙 metoda Gauss-Seidel are o viteză de convergenţă mai mare