curs 6 metode numerice I VAL PROPRII MET PUTERII+ITERATIILOR
description
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