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