curs 6 metode numerice I VAL PROPRII MET PUTERII+ITERATIILOR

25
METODE NUMERICE PENTRU PROBLEMĂ DE VALORI PROPRII 1. Definiţii, proprietăţi. 2. Metoda puterii şi variante ale acesteia. Metoda iteraţiilor simultane. 3. Metoda Jacobi. 1. Valori şi vectori proprii 1.1 Valori şi vectori proprii. Polinom caracteristic. Subspaţiu propriu. Fie dată matricea A n × n , reală sau complexă. Definiţie Dacă vectorul x ≠ 0 şi scalarul λ satisfac relaţia Ax = λx, (1) atunci: λ se numeşte valoare proprie, iar x vectorul propriu asociat lui λ. Dacă x şi y sunt asociaţi cu λ, atunci şi αx + βy, α, β scalari, este asociat lui λ. Dacă P este o matrice n × n nesingulară, matricea A′ = P −1 AP se zice similară cu A. P se zice matrice de transformare. Propoziţie – Matricile similare au aceleaşi valori proprii. – Dacă x′ sunt vectorii proprii ai lui A’, vectorii proprii x ai lui A se găsesc din relatia x = Px′. (Într-adevăr: dacă Ax = λx, rezultă P −1 Ax = λP −1 x, sau P −1 AP(P −1 x) = λ(P −1 x); cu x′ = P −1 x, rezultă Ax′ = λx′.)

description

ds

Transcript of curs 6 metode numerice I VAL PROPRII MET PUTERII+ITERATIILOR

Microsoft Word - CURS 4 - partea I

METODE NUMERICE PENTRU PROBLEM DE VALORI PROPRII

1. Definiii, proprieti.

2. Metoda puterii i variante ale acesteia. Metoda iteraiilor simultane.

3. Metoda Jacobi.

1. Valori i vectori proprii

1.1 Valori i vectori proprii. Polinom caracteristic. Subspaiu propriu.

Fie dat matricea A n n , real sau complex.

DefiniieDac vectorul x 0 i scalarul satisfac relaia

Ax = x,

(1)

atunci: se numete valoare proprie, iar x vectorul propriu asociat lui . Dac x i y sunt asociai cu , atunci i x + y, , scalari, este asociat lui .

Dac P este o matrice n n nesingular, matricea

A = P1 APse zice similar cu A. P se zice matrice de transformare.

Propoziie Matricile similare au aceleai valori proprii.

Dac x sunt vectorii proprii ai lui A, vectorii proprii x ai lui A se gsesc din relatia x = Px.(ntr-adevr: dac Ax = x, rezult P1 Ax = P1x, sau P1 AP(P1 x) = (P1 x); cu x = P1x, rezult Ax = x.)

Mai multe metode numerice transform matricea A ntr-o matrice similar A, de o form mai simpl, determinnd valorile proprii i vectorii proprii ai matricii A; apoi, se determin vectorii proprii ai lui A, cu relatia de mai sus.

*************************************************************************************

Polinomul caracteristic

Relaia (1) este ecuaia din care se gsesc i x. Aceasta se mai scrie

(A I)x = 0

(2)unde I este matricea unitate. Explicit,

(2)Condiia ca (2) s aib soluii netriviale x, este det(A I) = 0 . Explicit,

(3)p() se zice polinomul caracteristic al matricii A, i p() = 0 ecuaia caracteristic.

Fie determinantul dezvoltat:

p( ) = (1)nn + c1n1 + + cn1 + cn

(3)Din (3, 3') i relaiile ntre coeficieni i rdcini, rezult urmtoarele proprieti ale coeficienilor i valorilor proprii:

1) Avem p(0) = cn, i din determinant p(0) = det(A); urmeazcn = det(A)

Pe de alt parte, 12 n = cn, i astfel 12 n = det(A).

2) Coeficientul lui n1 se gsete din termenul

(a11 ) (ann ) =

Astfel, rezult:

;1 + 2 + + n = .

se zice urma matricii A).

3) n general:

ci = (1)ni Suma minorilor principali de ordinul i ai matricii A.

Observaii1) Ordonarea valorilor proprii:

Valorile proprii se ordoneaz n irul 1, 2, , n. n acest ir, o rdcin multipl de ordinul r, se repet de r ori. Uzual, valorile proprii se indexeaz n ordinea descresctoare a modulului, adic |1| |2| |n|. Valoarea proprie 1 se zice dominant. Mulimea valorilor proprii se zice spectrul matricii A.

2) Vectorii proprii asociai unei valori proprii:

Dup determinarea valorilor proprii, vectorii proprii asociai cu i se gsesc punnd = i n (2'), i rezolvnd sistemul liniar i omogen (2').

Dac A este real: n general, i poate fi complex, i atunci vectorul propriu xi asociat cu i este complex. Dac A i i sunt reali, atunci vectorul propriu xi este real. Dac A este complex: n general, valorile proprii i vectorii proprii sunt mrimi complexe. n particular, unele dintre acestea pot fi i reale.Subspaiu propriu i dimensiunea acestuia

Sistemul (2') este omogen, astfel c dac x, y sunt soluii, atunci x + y sunt soluii.

Adic, lui i i este asociat un subspaiu liniar Si de soluii x. Se arat c:

Dimensiunea subspatiului Si este mai mic dect sau egal cu ordinul de multiplicitate a rdcinii i.Dac ri este ordinul de multiplicitate a rdcinii i i pi dimensiunea lui Si, avem pi ri. Adic, n Si exist cel mult ri vectori liniar independenti.

Dac pi < ri, valoarea i se zice defectiv; n acest caz, i matricea A se zice defectiv. (ri se mai zice multiplicitate algebric, iar pi multiplicitate geometric.)

3) Determinarea efectiv a sistemului propriu:

Pentru calculaia practic (n > 3 ), nu se recomand:

Calculul direct al valorilor proprii, prin rezolvarea ecuaiei caracteristice (3').

Aceasta, datorit faptului c problema calculului rdcinilor unui polinom este foarte sensibil la mici perturbaii n coeficieni (aceste perturbaii apar din erorile de rotunjire).

Calculul direct al vectorilor proprii, din sistemul (2').

Metode numerice pentru gsirea valorilor proprii i, i a vectorilor proprii asociati x(i), sunt prezentate n continuare.

Exemplul-1

Fie matricea:

Polinomul caracteristic este:

Sau cf. (3)

p() = 3 + c12 + c2 + c3 = 0, unde:

c3 = det(A) = 1 (1) 2 (2) + 3 (1) = 0

cl = (1)2(1 + 3 + 5) = 9

p() = 3 + 92 + 6 = 0

De unde:

= 0

2 9 6 = 0; = 0.623475383; 9.62347538

Ordonnd (descresctor, dup module):

l = 9.62347538

2 = 0.623475383

3 = 0

Vectorii proprii , i = 1, 2, 3 se determin din sistemul omogen

,n care se nlocuiete = i .

De exemplu, vectorul propriu nr. 1 se gsete din sistemul:

Una dintre coordonate rmne arbitrar: s alegem de ex. xl = 1, rezult2x2 + 3x3 = 8.62347538

4x2 4.62347538x3 = 3

Rezult (rezolvnd n simpl precizie):

Orice vector x(1) unde = real, face funcie de vector propriu nr. 1. Analog, se determin vectorii proprii nr. 2 si 3.

1.2. Matrici hermitiene i unitare

Operaia * aplicat unui vector sau unei matrici noteaz transpus-conjugata. Astfel:

Dac x este un vector, .

Dac A, este o matrice, A* = .

Explicit: A = [aij], A* = [], avem: .

n expresiile anterioare, bara noteaz conjugata: ; .

Pentru un vector real, sau o matrice real, operatia * revine la transpunere:

x* = xT;

A* = AT.

n particular, pentru un scalar, operaia revine la conjugare: .Matrici hermitiene:

Matricea A se zice hermitian, dac A* = A.

Exemplu de matrice hermitian:

.Remarcai c elementele diagonale sunt reale, iar elementele simetrice sunt conjugate.

O matrice real este hermitian, dac este simetric (AT = A).

O matrice hermitian se zice pozitiv definit, dac x 0 x*Ax > 0 (x* Ax este real).

n particular, o matrice real i simetric este pozitiv definit, dac: x 0 xTAx > 0.Matrici unitare:

Matricea U se zice unitar, dac U*U = I , unde I este matricea unitate;

echivalent, U1 = U*.

O matrice real este unitar dac UTU = I, sau U1 = UT (matrici ortogonale). Valorile proprii ale unei matrici unitare au modulul egal cu 1.

Exemplu de matrice unitar (real):

Matricea de rotatie a axelor n plan este unitar:

ntr-adevr, avem i se verific imediat c .Proprieti ale matricilor hermitiene (n particular, reale i simetrice):

P1. Dac A este hermitian, i are valorile proprii {i} distincte sau nu, atunci:

(a) Exist o matrice unitar U, astfel c U*AU este diagonal:

U*AU = diag(1, , n), (se zice c U diagonalizeaz pe A.)

(b) Exist n vectorii proprii liniar independenti care formeaz o baz ortonormat n Cn (acetia sunt coloanele lui U);

(c) Valorile proprii sunt reale.

n particular, pentru A real i simetric:

(a-1) Exist U unitar i real, astfel c UTAU = diag(1, , n).

(b-1) Exist n vectorii proprii liniar independenti; acetia formeaz o baz ortonormat n Rn (coloanele lui U);

(c-1) Valorile proprii sunt reale i vectorii proprii sunt reali .

Avem i proprietatea:

P1'. Dac A este hermitian (real i simetric) i pozitiv definit, atunci valorile proprii ale lui A sunt reale i pozitive .

1.3. Produs scalar i proprieti de ortogonalitate

1.3.1. Spaiu vectorial real VnFie x un vector din Vn, i x matricea coloan a coordonatelor sale ntr-o baz a lui Vn (xi R, ).

Dac matricea A real, este simetric i pozitiv definit, se definete produsul scalar n raport cu matricea A, prin:

A = xTAy = yTAxn particular, pentru A = I, acesta devine produsul scalar standard:

= xTy = yTxAvem: A = A; = .

Vectorii x i y se zic ortogonali (relativ la produsul scalar), dac A = 0, sau = 0 .

Astfel:

Vectorii x i y sunt ortogonali relativ la matricea A, dac xTAy = 0, sau yTAx = 0.

Vectorii sunt ortogonali, dac xTy = 0 , sau yTx = 0.

1.3.2. Spaiu vectorial complex VnFie x un vector din Vn, i x matricea coloan a coordonatelor ntr-o baz a lui Vn (xi C, ).

Dac A este o matrice hermitian i pozitiv definit, se definete produsul scalar n raport cu matricea A, prin:

A = xTA = y*ATx. (Ultima egalitate rezult din aceea c scalarul su s =A este egal cu transpusul su).

Produsul scalar definit de A = I este:

= xT = y*xAvem: i .

Ortogonalitatea a doi vectori se definete ca nainte, prin conditia A = 0, sau = 0.

Observaie: Dac avem A = 0, avem i A = 0.

Astfel:

Vectorii x, y sunt ortogonali n raport cu A, dac:

xTA = 0, sau y*ATx = 0.

Vectorii x, y sunt ortogonali,dac:

xT = 0, sau y*x = 0.

P2. Dac A este hermitian, atunci:

Vectorii proprii asociati la dou valori proprii distincte sunt ortogonali:

dac 1 2, atunci i . Avem i: .

(Dac A hermitian este i pozitiv definit, vectorii x1, x2 sunt ortogonali relativ la matricea AT.)

Dac A este real i simetric:

Vectorii proprii asociati la dou valori proprii distincte sunt ortogonali:

Avem i: .

(Dac A real i simetric, este i pozitiv definit, vectorii x1, x2 sunt ortogonali relativ la matricea A).1.4. Ctul Rayleigh

Fie A o matrice n n complex (sau real). Fie v Cn un vector arbitrar, i definim

(v) se numete ctul Rayleigh.

Proprietatea-1:

Dac x este vector propriu asociat cu , atunci (x) = .

Astfel, ctul Rayleigh poate fi utilizat pentru a gsi o aproximare a valorii proprii , dac se cunoate o aproximare v a vectorului propriu x: v x (v).

Proprietatea-2:

Dac matricea este hermitian, ctul Rayleigh este mrginit de valorile proprii extreme.

Valorile proprii sunt reale; fie acestea 1 2 n, atunci, avem:n (v) 1, pentru orice v Cn.*****************************************************************************2. Metoda puterii

2.1. Metoda puterii

Metoda puterii determin valoarea proprie dominant i vectorul propriu asociat, ale unei matrici A, reale sau complexe.

Aplicat la inversa A1 metoda determin valoarea proprie cea mai mic (n modul), i vectorul propriu asociat cu aceasta. Aceasta, conform propriettii:

Matricea A1 are ca valori proprii inversele valorilor proprii ale lui A i aceiai vectori proprii.

ntr-adevr: din Ax = x, nmultind la stnga cu A1, rezult x = A1x, sau . Explicit: A : {1, , n}; A1 : {1, , n}. Avem:

.Ipotezele metodei puterii:

Exist un set de n vectori proprii liniar independeni.

Exist o singur valoare proprie dominant 1:

|1| > |2| |n|.

(Remarcati c prima inegalitate este strict!)

Metoda:

Fie w(0) un vector iniial, ales arbitrar cu singura condiie ca s aib o component n direcia lui x(1). Pentru a ndeplini aceast cerin, unele coduri genereaz un vector aleator. (n fapt, w(0) este o aproximaie a vectorului propriu x(1); dac o astfel de aproximaie este cunoscut, atunci aceasta accelereaz iteraia de mai jos).

Dezvoltm

(a)Presupunem c a1 0 (condiia de mai sus), i formm irul de vectori

w(k+1) = Aw(k) = Ak+1w(0), k 0

Avem:

w(1) = Aw(0) = 1a1x(1) + 2a2x(2) + + nanx(n) =

n general,

(b)Cum |1| > |i| pentru i 2, urmeaz c rapoartele (i / 1) tind la 0 pentru k . Astfel, pentru k cresctor, vectorii w(k) se aliniaz din ce n ce mai mult la direcia vectorului propriu x(1). n consecint, pentru un k suficient de mare, avem

w(k) (1)ka1x(1).

S considerm de asemenea relaia w(k+1) (1)k +1a1x(1). Lund orice coordonat non-zero a lui w(k+1), w(k), s zicem cea de-a m-a coordonat, obinem

.Dezavantajul formulei precedente este c, coordonatele nenule ale lui w(k) devin fie foarte mici (|1| < 1), fie foarte mari (|1| > 1), odat cu creterea lui k. Aceasta se evit prin normalizarea (sau scalarea) lui w(k), la fiecare pas k. Normele utilizate sunt norma- i norma-2.

Astfel, algoritmul metodei este:

w(0) = Vector initial

, pentru k 0 Normalizare

, pentru k 0 IteraieTeste de oprire a iteratiei

1. Test de coliniaritate a doi vectori succesivi.

Vectorii z(k) i z(k+1) sunt coliniari, dac rapoartele sunt egale (coordonatele nenule sunt proporionale), sau . n practic, punem condiia |(i) (i0)| TOL, dac ; sau, s avem simultan, i . TOL este o toleran specificat; i0 este indicele unei coordonate fixate: este convenabil s lum i0 = imax = indicele coordonatei de modul maxim din z(k+1).

Se introduc atunci, factorii de coliniaritate prin vectorul colin(1 : n), definit astfel:

.

Testul este:

||colin colin(imax)|| TOL.Aceasta nseamn s avem , (pentru ).Observaie:Test pentru norma-2 (euclidian):

Dac, pentru normalizarea lui w(k), se utilizeaz norma-2, vectorii z(k) au norma-2 egal cu 1, i testul de coliniaritate poate lua forma||z(k+1) z(k)|| TOL.

O problem special apare pentru A real, dac valoarea proprie dominant este real i negativ, 1 < 0, i anume: din w(k) = A(k)z(0) = (1)k[a1x(1) + r(k)] i z(k) = w(k) / ||w(k)||, rezult c vectorul z(k) schimb de semn de la pasul k la pasul k + 1. (Valoarea proprie, dat de , nu este afectat.).

Testul de coliniaritate trebuie s in cont de aceasta. Astfel, definim,

Testul corect este

||dz||2 TOL.

2. Test asupra lui :

Iteraia se oprete prin condiia

unde TOL este o toleran.

3. Test de satisfacere a relaiei de definiie:

||Az z|| TOLPractic, z = z(k), Az(k) = w(k+1), i = (k+1). Definind

dif = w(k +1) (k +1)z(k),

se pune testul

|| dif || TOLObservaii:

n cod, dac valorile anterioare (k) sunt stocate n z0 i lambda0, iar valorile curente (k+1) n z i lambda, definiia lui dif devine

dif = z lambda*z0,

lund z nainte de normalizare.

Vectorul r = Az z se zice vectorul rezidual. Astfel, testul se mai scrie

|| r || TOL.

Note Testul propriu pentru metod este Testul 1, ntruct, n esen, metoda determin vectorul propriu nr. 1 i apoi determin 1 din acesta. Cu Testul 1, se obin vectori proprii mai precii dect cu Testul 2 (la aceeai toleran).

Testul 3 nu este specific metodei puterii, ci poate fi aplicat oricrei metode iterative pentru valori i vectori proprii. Codurile din Lapack (Bai et al.(2000)), utilizeaz Testul 3, cu TOL = M||, unde M este -main.

(n metodele din ANA: Testul 3 va fi utilizat numai la verificarea sistemului propriu. Face excepie metoda puterii, unde pentru studiu, se poate alege unul din Testele 1 3; alegerea se face printr-un cod.)

Convergena:

Convergena este liniar, iar rata convergenei este aproximativ |2 / 1|.

(Acest rezultat are loc n ipoteza metodei |1| > |2|, cu ipoteza suplimentar: pentru k k1, cantitile (i / 2)k, i 3, sunt neglijabile n raport cu (2 / 1)k).2.2. Metoda puterii inverse cu translaie (shift)

Fie matricea A, cu valorile proprii j, j = 1, n. Metoda gsete valoarea proprie i a lui A, cea mai apropiat de un numr dat s; adic, |i s| = minim.

Se consider matricea

B = A sIi presupunem c B este nesingular. Se verific imediat c valorile proprii ale lui B sunt j = j s. Cantitatea s zice deplasare sau translaie (shift).

Fie i = i s, valoarea proprie de modul minim a lui B, adic:

0 < |i| < < |j|, pentru j i.

Atunci, metoda puterii aplicat lui B1 produce valoarea proprie de modul maxim, fie aceasta i = 1 / i (i este valoarea dominant pentru B1). Avem i = 1 / i, i .Principala aplicaie a metodei este de a gsi vectorul propriu, dac este cunoscut o aproximaie bun a valorii proprii, s zicem . (Aceasta poate fi furnizat de o metod n care se determin numai valorile proprii nu i vectorii proprii.)

Se aplic metoda puterii inverse, cu deplasarea s = . Chiar dac este apropiat de (i, matricea B = A I este nc nesingular, i se obine o bun aproximaie a vectorului propriu x(i).

Metoda iteraiei inverse cu deplasare, este una dintre cele mai precise metode pentru calculul vectorilor proprii.

Algoritmul practic, este urmtorul:

Iteraia din metoda puterii, aplicat la matricea B1, este

w(k+1) = B1z(k).

n loc de a inversa B, calculm w(k+1) din sistemul liniar

Bw(k+1) = z(k),

prin descompunere LU. Factorizarea se face o singur dat, i sistemul se rezolv succesiv cu membrii drepi z(k), k 0.

2.3. Metoda iteraiilor simultane matrice hermitian.

Aceasta este o extindere a metodei puterii pentru o matrice A hermitian (n particular, real i simetric). O astfel de matrice, are valori proprii reale.

Presupunem, mai mult, c valorile proprii sunt de module distincte:

|(1| > |(2| > > |(n|.

n loc de un vector de start w(0), se utilizeaz o matrice de start , ale crei coloane sunt vectorii de start: W(0) = [w(0,1) | w(0,2) | | w(0,m)].

Dac matricea A este n n, W(0) este n m, unde m n. Vectorii de start w(0,j) trebuie s fie liniar independeni. Metoda de baz rmne nmulirea la stnga a lui W(0) cu matricea A, adic, W(k+1) = AW(k), k 0 . nainte de fiecare etap a iteraiei, matricea curent W este ortogonalizat prin procedeul Gram-Schmidt, astfel nct coloanele ei w(j) devin vectori ortonormai (ortogonali, i avnd norma euclidian unitar). Astfel, vectorii w(j) formeaz o baz ortonormat a sub-spaiului m-dimensional al lui Rn, sub-ntins de vectorii iniiali w(0,j). n cursul iteraiei, aceast baz se aliniaz din ce n ce mai mult la baza vectorilor proprii ai lui A, direcia w(j) direcia x(j), j 1. Valorile proprii se evalueaz prin ctul Rayleigh.

Iteraia se ncheie cnd se atinge o toleran convenabil, privitor la direciile a dou baze succesive {w(j)}. Dac matricea de start W(0) are m < n coloane, se obin primii m vectori proprii. Pentru m = n, adic W(0) este n n, se gsesc toi vectorii proprii.

Algoritmul:

Se cere un numr ne n de vectori proprii. W(0) i W sunt matrici n ne.

1. Se definete matricea W(0): dac o aproximare iniial a vectorilor proprii nu este cunoscut, se ia W(0) = [e(1) | e(2) | | e(ne)], adic, W(0) este format din primele ne coloane ale matricii unitate I. Pentru ne = n, W(0) = I.

2. Se aplic Gram-Schmidt la W(0) (cu excepia cazului n care aceasta este deja ortonormat). Se atribuie W = W(0).

3. Iniializare contor: iter = 0

4. Iteraii: iter = iter +1;

Atribuire: W(0) = W (W = matricea curent; W(0) = matricea anterioar.)

5. Se calculeaz W = AW(0).

6. Se calculeaz (j, j = , prin ctul Rayleigh:

Fie w(j) i w(0,j) a j-a coloan a lui W i W(0), respectiv; avem

(j =

(w(j) = Aw(0,j) Pasul 5; i = 1 Paii 2 i 4).7. Se aplic Gram-Schmidt la W, astfel c W devine ortonormat.

8. Se verific atingerea toleranei TOL:

Prin testul de coliniaritate 1.3, 1: se definete colin(n) pentru fiecare vector z = W((,je), i test_val =

(ntruct z sunt normalizati, testul se poate pune i sub forma din 1, Observaie.)

- Dac ||test_val|| TOL, ieire din iteraie.

- Altfel, G0T0 4.

Observaii( Se poate prescrie un numr limit de iteraii lnit: atunci, se adaug la Pasul 8 un test iter lnit.

( Pasul 6 se poate realiza numai o singur dat, dup ce s-a ieit din iteraie.

Observaii1. Valori proprii de acelai modulntruct metoda iteraiilor simultane este n esen metoda puterii, nu se obine convergen pentru vectorii proprii, dac exist valori proprii de modul egal.

2. Matrici non-hermitieneDac aplicm algoritmul de mai sus unei matrici non-hermitiene, nu vom obine convergen pentru vectorii proprii, cu excepia vectorului propriu corespunznd valorii dominante (1 (pentru care, metoda revine la metoda puterii). Aceasta se ntmpl deoarece ipoteza esenial a metodei este c vectorii proprii formeaz o baz ortogonal i procedeul Gram-Schmidt foreaz ca, la fiecare pas k, vectorii w(k,j) s fie ortogonali.

Totui, dac valorile proprii sunt de module distincte, atunci vectorii proprii sunt liniar independeni, i se obin aproximaii foarte bune pentru valorile proprii. Explicaia este c, procedeul Gram-Schmidt furnizeaz un set de vectori {w(j)} liniar independeni (ortonormai), iar valorile proprii sunt calculate cu ctul Rayleigh care d aproximaii bune ale valorilor proprii chiar cu aproximaii grosiere pentru vectorii proprii.

Valorile proprii gsite pot fi utilizate ulterior, n metoda puterii inverse cu translaie, pentru a obine vectorii proprii pentru valorile (i, i 2.

3. Metoda Jacobi matrice real simetricMetoda:

Metoda Jacobi este o metod convenabil pentru a gsi toate valorile proprii i vectorii proprii ai unei matrici reale i simetrice, de ordin moderat. Determinarea vectorilor proprii este opional.

Fie A o matrice real i simetric. Dac N este o matrice nesingular, atunci matricea este similar cu A, i are aceleai valori proprii (bara nu noteaz acum conjugata). Vectorii proprii x ai lui A, sunt legai de vectorii proprii x ai lui A, prin: . (Propozitia din 1.1).

S presupunem acum, c N este unitar, adic N1 = NT. Matricea devine .Notai c A este de asemenea simetric.

Diagonalizarea lui A:

S presupunem c N este aleas astfel nct s devin diagonal:

= NTAN = diag()

Pentru matricea , avem proprietile:

( Valorile proprii ale lui sunt elementele diagonale:

( Vectorii proprii ai lui sunt coloanele matricii unitate I:

(unde ).n consecin, rezult pentru A:

( Valorile proprii ale lui A se gsesc pe diagonala matricii .

( Vectorii proprii ai lui A sunt coloanele matricii N. Exemplu:

Diagonalizarea Jacobi:

Metoda Jacobi const n transformri unitare (sau, ortogonale) aplicate succesiv lui A, pn la obinerea unei forme aproape diagonale. Anume, dac Ni sunt matrici unitare, matricea A se transform cum urmeaz:

Dac matricea este aproape diagonal, adic elementele non-diagonale sunt aproximativ zero, lum

unde N = N1N2 Nk.Fiecare transformare Ni se alege astfel ca s elimine o pereche de elemente non-diagonale (s zicem apq i aqp la pasul i). O astfel de matrice are structura:

Elementele nescrise sunt zero (cu excepia diagonalei principale unde acestea sunt unu).

Transformrile Ni se aplic succesiv, fiecare dintre ele eliminnd elementul non-diagonal apq, de modul maxim. Principala proprietate a unei astfel de transformri este c produsul modific numai elementele lui A din liniile i coloanele p i q.Unghiul se alege astfel nct

Noile elemente diagonale, sunt date de formulele:

;

;

Observai( Transformrile Ni se aplic succesiv, fiecare dintre ele eliminnd elementul non-diagonal de mrime maxim.

( Elementele reduse la zero ntr-o transformare nu rmn zero la transformarea urmtoare. Dar, se poate arta c fiecare transformare reduce suma de ptrate a elementelor non-diagonale cu , adic, . Atfel, dup un anumit numr de transformri, aceast sum poate fi fcut mai mic dect o toleran aleas dinainte. Pentru alte detalii, v. Cap. 5 ( II, 2

Consideraii de programare

Stocajul matricii:

Se lucreaz cu triunghiul superior al lui A, astfel nct, dup diagonalizarea lui A, elementul (1, 1) contine (1, etc. Triunghiul superior este stocat n vectorul a(n*(n+1)/2), n ordinea coloanelor, adic:

a = [a11 | a12 a22 | a13 a23 a33 | | a1n a2n ann]

Adresa elementului (i, j) este dat de urmtoarea funcie:

Loca(i, j) = (j 1)*j / 2 + in particular, elementul diagonal (i, i) are adresa Loca(i, i) = (i + 1)*i / 2. Dup ce s-a efectuat o transformare, matricea curent A este stocat n acelai vector a.Strategia de eliminare

Aceasta este cutarea complet, adic: se caut n toat matricea A (concret, n vectorul a), elementul non-diagonal de modul maxim. (Pentru alte strategii, v. Numerical Analysis, Cap. 5 ( II, 2.)

Elementele non-diagonale se consider zero, dac sunt mai mici (n modul) dect o toleran TOL.

_1318140271.unknown

_1318144737.unknown

_1318145573.unknown

_1318232030.unknown

_1318234979.unknown

_1318235758.unknown

_1318236220.unknown

_1318236342.unknown

_1318236447.unknown

_1318237213.bin

_1318236423.unknown

_1318236262.unknown

_1318236328.unknown

_1318236138.unknown

_1318236178.unknown

_1318236053.unknown

_1318235379.unknown

_1318235556.unknown

_1318235589.unknown

_1318235452.unknown

_1318235100.unknown

_1318235347.unknown

_1318235007.unknown

_1318234588.unknown

_1318234665.unknown

_1318234842.unknown

_1318234901.unknown

_1318234753.unknown

_1318234807.unknown

_1318234650.unknown

_1318233919.unknown

_1318234521.unknown

_1318233578.unknown

_1318148022.unknown

_1318149344.unknown

_1318231969.unknown

_1318148689.unknown

_1318146065.unknown

_1318147851.unknown

_1318145634.unknown

_1318145112.unknown

_1318145458.unknown

_1318145481.unknown

_1318145136.unknown

_1318144944.unknown

_1318145096.unknown

_1318144850.unknown

_1318141169.unknown

_1318142469.unknown

_1318143885.unknown

_1318144673.unknown

_1318142560.unknown

_1318141791.unknown

_1318142097.unknown

_1318141687.unknown

_1318140787.unknown

_1318140975.unknown

_1318141057.unknown

_1318140816.unknown

_1318140533.unknown

_1318140786.unknown

_1318140439.unknown

_1318057301.unknown

_1318058112.unknown

_1318139960.unknown

_1318140194.unknown

_1318140224.unknown

_1318140049.unknown

_1318058237.unknown

_1318139458.unknown

_1318058178.unknown

_1318057529.unknown

_1318057658.unknown

_1318057723.unknown

_1318057570.unknown

_1318057436.unknown

_1318057473.unknown

_1318057383.unknown

_1318056228.unknown

_1318056824.unknown

_1318056991.unknown

_1318057171.unknown

_1318056901.unknown

_1318056542.unknown

_1318056728.unknown

_1318056285.unknown

_1318055070.unknown

_1318055178.unknown

_1318055458.unknown

_1318055132.unknown

_1318054304.unknown

_1318054905.unknown

_1302591943.unknown

_1318054086.unknown

_1301384659.unknown

_1300267613.unknown