AMPLIACIÓ DE MÈTODES NUMÈRICS - VALORS I VECTORS PROPIS

Tema 3. VALORS I VECTORS PROPIS

Càlcul de determinants i del polinomi característic:

Definició 6: Per a tota matriu A de dimensió nxn, diem que el número λ (real o complexe) és un valor propi, associat a un vector propi, y, de dimensió n, si i solament si Ay=λy .

Teorema 30: Si y és un vector propi de A, i α és un número, aleshores αy és també un vector propi de A, amb el mateix valor propi associat.

Teorema 31: Si λ és un valor propi de A, aleshores A-λI és una matriu singular (no invertible).

Definició 7: Designarem per Π al conjunt de totes les permutacions p=Pu, on P siga una matriu de permutació de dimensió nxn i u=(1...n). Designarem per σ_p a la paritat de la permutació p, de manera que σ_p=1 si la corresponent matriu de permutació P és el producte d'un número par de matrius de permutació simples, i σ_p=-1 si la corresponent matriu de permutació P és el producte d'un número impar de matrius de permutació simples.

Definició 8: Per a cada matriu A de dimensió nxn definim el seu determinant com det(A)=Σ_pcΠ σ_pA_{1 p1}A_2
p2∙∙∙ A_{n pn}

Teorema -4: Una matriu A de dimensió nxn és regular si i solament si det(A)≠0 .

Teorema 32: λ és un valor propi de A si i solament si det(A-λI)=0 .

Teorema 33: det(A-λI) = Σ_pcΠ σ_p(Π_i≠piA_i
pi)(Π_i=pi(A_i
pi-λ)) .

Teorema 34: det(A-λI) és un polinomi de grau n en λ (que s'anomena polinomi característic d'A)..

Teorema 35: Si A és una matriu triangular superior o inferior, aleshores det(A)=Π_i=1...nA_ii .

Teorema 36: Si P és una matriu de permutació i p=Pu, aleshores det(P)=σ_p .

Teorema -5: Per a tot parell de matrius A, B de dimensió nxn, det(AB)=det(A)det(B) .

Teorema 37: Si A és una matriu regular, aleshores det(A)=σ_pΠ_i=1...nU_ii , amb PA=LU .

Algoritme 3: Per a l'obtenció del valors i vectors propis d'una matriu A de dimensió nxn:

Construcció del polinomi característic det(A-λI) utilitzant el teorema 37 mitjançant la descomposició LU de la matriu A-λI (es pot fer ús parcialment de l'algoritme 2).
Càlcul de les arrels λ (valors propis) del polinomi característic det(A-λI) pel mètode de Muller (algoritme 1).
Càlcul de les solucions no trivials (vectors propis) del sistema linial (A-λI)y=0 . Es pot fer:

Per eliminació gaussiana aplicant l'algoritme 2 al sistema Σ_j=1...n-m(A_ij-λδ_ij)y_j = b_i, amb b_i=Σ_j=n-m+1...n(λδ_ij-A_ij)y_j , on m és la multiplicitat del valor propi λ, i els valor de y_j per a j=n-m+1...n s'introdueixen arbitràriament.
Per iteració lineal de punt fixe amb y=Ay/λ .

Mètodes de la potència:

Definició 9: Direm que la matriu B és semblant a la matriu A si i solament si existeix una matriu regular C tal que B=C^-1AC .

Teorema 38: Si la matriu B és semblant a la matriu A, aleshores tenen els mateixos valors propis, & y és vector propi de B si i solament si Cy és vector propi de A.

Definició 10: Direm que una matriu A és diagonalitzable si i solament si és semblant a una matriu diagonal D=(D_iiδ_ij)_i,j=1...n .

Teorema 39: Si la matriu A és diagonalitzable i la matriu diagonal D=(D_iiδ_ij)_i,j=1...n és semblant a A de manera que A=CDC^-1, aleshores, per a tot k=1...n, D_kk és un valor propi de A associat a la corresponent columna de C, (C_ik)_i=1...n, que serà un vector propi de A .

Teorema 40: Si A és una matriu diagonalitzable con valors propis tals que |λ₁|>|λ₂|≥...≥|λ_n|, associats als vectors propis unitaris x₁,x₂...x_n (tals que ||x_i||₂=1 per a tot i=1...n), & x=Σ_i=1...nα_ix_i és un vector tal que α₁≠0, aleshores lim_k→∞A^kx/λ₁^k = α₁x₁ , essent |A^kx/λ₁^k-α₁x₁|=Θ(|λ₂/λ₁|^k) .

Teorema 41: Si y és un vector propi de A amb un valor propi associat λ & indiquem per y^T el vector transposat de y, de manera que y^Ty=Σ_i=1...ny_iy_i=(||y||₂)², aleshores λ=y^TAy/y^Ty=z^TAz (quocient de Rayleigh) tal que z=y/||y||₂ .

Teorema 42: Si λ₁ és l'únic valor propi d'A amb major valor absolut, associat a un vector propi unitari x₁, & x=Σ_i=1...nα_ix_i és un vector tal que α₁≠0, aleshores λ₁= lim_k→∞z^(k)TAz^(k) , on z^(k)=A^kx/||A^kx||₂ , & x₁=lim_k→∞z^(k) .

Algoritme 4: Per a aproximar el vector propi y amb el valor propi λ₁ associat amb màxim valor absolut:

Escollir un vector p⁽⁰⁾ i la tolerància ε . Prendre i=0 .
Calcular z⁽ⁱ⁾=p⁽ⁱ⁾/||p⁽ⁱ⁾||₂ .
Calcular p⁽ⁱ⁺¹⁾=Az⁽ⁱ⁾ .
Calcular λ⁽ⁱ⁾=(z⁽ⁱ⁾)^Tp⁽ⁱ⁺¹⁾ .
Si i>0, aleshores si |λ⁽ⁱ⁾-λ^(i-1)|<ε, aleshores prendre λ=λ⁽ⁱ⁾ & y=p⁽ⁱ⁺¹⁾ : fi
Prendre i=i+1 . Tornar al pas 2.

Teorema 43: Si A és una matriu regular, els valors propis de la seua matriu inversa A^-1 són els inversos dels valors propis de A.

Algoritme 5: Mètode de la potència inversa. Per a aproximar el vector propi y amb el valor propi λ_n associat amb mínim valor absolut s'utilitza l'algoritme 4, substituint el pas 3 per:

Obtenir p⁽ⁱ⁺¹⁾ tal que Ap⁽ⁱ⁺¹⁾=z⁽ⁱ⁾ mitjançant descomposició LU de la matriu A (es pot fer ús parcialment de l'algoritme 2).

Teorema 44: Si λ és un valor propi de A, aleshores λ-μ és un valor propi de A-μI .

Algoritme 6: Si coneguem μ tal que per a tot j≠i, |λ_i-μ|<|λ_j-μ|, aleshores per a aproximar el valor propi λ_i de A:

Prendrem A'=A-μI
Utilitzarem l'algoritme 5 (mètode de la potència inversa) amb la matriu A' per a aproximar el valor propi λ'_n de A' amb mínim valor absolut.
Prendrem λ_i=λ'_n+μ .

Definició 11: Anomenem discs de Gerschgorin d'una matriu A de dimensió nxn als conjunts D_i={xcC:|x-A_ii|≤Σ_j≠i|A_ij|} per a i=1...n.

Teorema 45: Si y≠0 és un vector propi de la matriu A de dimensió nxn & λ és el seu valor propi associat, aleshores, per a tot i=1...n, (λ-A_ii)y_i = Σ_j≠iA_ijy_j .

Teorema 46: Si y≠0 és un vector propi de la matriu A, λ és el seu valor propi associat & yi és un component de y amb màxim valor absolut (és a dir, per a tot j≠i, |yj|≤|yi|), aleshores λcD_i .

Teorema 47: Per a tota matriu A de dimensió nxn & per a tot i=1...n, si el disc de Gerschgorin D_i no s'intersecta amb cap altre, aleshores conté un únic i simple valor propi d'A, i podem utilitzar l'algoritme 6 amb μ=A_ii .

Deflació de matrius:

Definició 12: Direm que una matriu A és ortonormal si i solament si A^TA=AA^T=I .

Teorema 48: Si A és una matriu ortonormal de dimensió nxn, aleshores tant les seues fileres com les seues columnen formen una base ortonormal de Rⁿ .

Teorema 49: Si A és una matriu ortonormal de dimensió nxn & x és un vector unitari de dimensió n, aleshores Ax és també un vector unitari.

Teorema 50: Si λ és el valor propi de una matriu A de dimensió nxn associat al seu vector propi unitari y, P és una matriu ortonormal tal que Py=e₁=(δ_i1)_i=1...n=[1,0,...,0] & A'=PAP^T, aleshores λ és un valor propi de A' associat al seu vector propi e₁ & per tant, per a tot i=1...n, A'_i1=λδ_i1 & la matriu (A'_ij)_i,j=2...n de dimensió (n-1)x(n-1) té com a valors propis els valors propis de A excepte λ .

Definició 13: Anomenarem matriu de Householder associada al vector v≠0 a P=I-2vv^T/(v^Tv) .

Teorema 51: tota matriu de Householder és simètrica i ortonormal, és a dir, P^T=P & PP=I .

Teorema 52: Si y és un vector unitari & P és la matriu de Householder associada a v=y±e₁ , aleshores Py = -±e₁ (per a obtenir una millor aproximació convé escollir entre el doble signe de v el signe de y₁, de manera que |v₁|=|y₁|+1 ; en cas que el signe de y₁ fora positiu & per tant v=y+e₁, haurem de prendre P=2vv^T/(v^Tv)-I si volem obtenir Py=e₁ ).

Algoritme 7: Per a obtenir tots els valors propis d'una matriu A de dimensió nxn per deflació:

Prendre i=1, A⁽⁰⁾=A .
Aplicar el mètode de la potència directa per a obtenir el valor propi λ_i amb màxim valor absolut de la matriu A⁽ⁱ⁾, associat a un vector propi unitari y_i (algoritme 4).
D'acord amb el teorema 52, obtenir una matriu ortogonal P tal que Py_i=e_i =(δ_ji)_j=1...n .
Calcular A'=PA⁽ⁱ⁾P^T . Prendre A⁽ⁱ⁺¹⁾=(A'_jk)_j,k=i+1...n . Si i=n-1, prendre λ_n=A'_nn : fi.
Prendre i=i+1. Tornar al pas 2.

Reducció de matrius:

Teorema 53: Si H és la matriu de Householder associada a v=x±||x||₂e₁ , aleshores Hx=-±||x||₂e₁ (per a obtenir una millor aproximació convé escollir entre el doble signe de v el signe de x₁).

Teorema 54: Si A és una matriu dimensió nxn & Ĥ és una matriu de Householder de dimensió (n-1)x(n-1) tal que (Ĥ[A₂₁...A_n1])_i=0 per a tot i=3...n, aleshores prenent H=[(1,0),(0,Ĥ)] podem obtenir altra matriu semblant B=HAH tal que B_i1=0 per a tot i=3...n .

Definició 14: Direm que B és una matriu de Hessenberg superior si i solament si B_ij=0 per a tot i,j tal que i>j+1 .

Algoritme 8: Per a transformar una matriu A de dimensió nxn en una matriu B semblant de Hessenberg superior:

Prendre i=1, A⁽⁰⁾=A .
Prendre x=[A^(i-1)_ji]_j=i+1...n .
Calcular v=x+signe(x_i+1)||x||₂e_i+1 .
Calcular Ĥ = I-2vv^T/(v^Tv) . Calcular H tal que H_jk=δ_jk si j,k=1...i, H_jk=Ĥ_jk si j,k=i+1...n, H_jk=H_kj=0 si j=1...i, k=i+1...n .
Calcular A⁽ⁱ⁾=HA^(i-1)H .
Si i=n-2, prendre B=A⁽ⁱ⁾ : fi
Prendre i=i+1. Tornar al pas 2.

Definició 15: Direm que B és una matriu tridiagonal si i solament si, per a tot i,j, Bij=0 si j>i+1 o i>j+1 .

Algoritme 9: Per a transformar una matriu simètrica A de dimensió nxn en una matriu B semblant tridiagonal:

Prendre i=1, A⁽⁰⁾=A .
Prendre Ã=(A^(i-1)_jk)_j,k=i+1...n, x=[A^(i-1)_ji]_j=i+1...n .
Calcular v=x+signe(x_i+1)||x||₂e_i+1 .
Calcular w = -2Ã^Tv/(v^Tv) .
Calcular ĤÃ = Ã + vw^T .
Calcular w = -2ĤÃv/(v^Tv) .
Calcular ĤÃĤ = (Ĥ(ĤÃ)^T)^T = ((ĤÃ)^T+vw^T)^T .
Prendre A⁽ⁱ⁾_i+1,i = A⁽ⁱ⁾_i,i+1 = - signe(x_i+1)||x||₂ , (A⁽ⁱ⁾_jk)_j,k=i+1...n = ((ĤÃĤ)_jk)_j,k=i+1...n , A⁽ⁱ⁾_ii=A^(i-1)_ii, A⁽ⁱ⁾_k,j=A⁽ⁱ⁾_j,k=A^(i-1)_j+1,j per a tot j=1...i-1, k=1...n, A⁽ⁱ⁾_ji=A⁽ⁱ⁾_ij=0 per a tot j=i+2...n .
Si i=n-2, prendre B=A⁽ⁱ⁾ amb B_jj=A_jj per a tot j=1...i & B_jk=0 si j>k+1 o k>j+1 : fi
Prendre i=i+1. Tornar al pas 2.