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  M 1  P1  A = U - folosind 𝑃𝑘 = 𝑃𝑘−1 (M n −1  Pn −1    M 1  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: [k] x [k] , k = 0,1,... lim x = x , 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 ] [s −1] || x −x ||   impus  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