Upload
aposentoalto
View
244
Download
8
Embed Size (px)
Citation preview
1/44
JJIIAnt.
Cerrar
Metodos Matematicos de Especialidad
Ingenierıa Electrica
Valores y vectores propios1
Jose Luis de la Fuente O’[email protected]
Escuela Tecnica Superior de Ingenieros Industriales
Universidad Politecnica de Madrid
2/44
JJIIAnt.
Cerrar
Indice
1. Introducci on
2. Interpretaci on geom etrica
3. Propiedades de los subespacios propios
4. Propiedades de los valores propios
5. Tipos de matrices y valores propios
6. Lema de Schur y aplicaciones
7. Localizaci on de valores propios
3/44
JJIIAnt.
Cerrar
8. Obtenci on num erica
• Metodo de la iteraci on de potencia• Metodo de la iteraci on inversa• Iteraci on mediante cociente de Rayleigh• Deflaci on• Iteraci on simult anea• Iteraci on QR• Metodo de Jacobi• Comparaci on de los m etodos
9. Calculo de los valores singulares
4/44
JJIIAnt.
Cerrar
Introducci on• El estudio de los autovalores de sistemas surge por doquier en muchas
areas de la ciencia, ingenierıa, economıa. . .
• Analisis de estructuras
• Diseno de sistemas electronicos
• Analisis de sistemas electricos:
� Sincronismo del sistema productor
� Estabilidad del sistema ante perturbaciones
� Planificacion nuevo equipo
� Otros muchos
• Mercados financieros.
• Es tambien muy importante para analizar el comportamiento demetodos numericos.
5/44
JJIIAnt.
Cerrar
• En analisis de sistemas electricos de generacion, transporte y demandade energıa electrica, su papel es clave.
TurbinegovernorTorsion
Syn-chronousmaschineAVR
On-loadtapchanger
CurrenttransformerSaturationProtectivesystem
BreakerArcrestriking
External systemLineCableHVDCFACTS
ConverterVAR-LoadVAR-AdmittanceMotorLoad torque
GInter-
connectedSystem
SVC
M
6/44
JJIIAnt.
Cerrar
Travellingwavephenomena
Transientphenomena,Switchingovervoltages
Short-circuitphenomenaSSR-phenomena
Transientstability
Controlphenomenawith steamgenerators
Harmonics,Transformer-saturation
1 mHz1 Hz1 kHz1 MHz
1 ms1 µs 1 s 1 min 1 h
100 s1 s10 ms100 µs1 µs
electromagnetic electromechanical
Frequency range 1 Frequency range 2
Calculationtime steps
Process-times
Frequency
Phenomena
7/44
JJIIAnt.
Cerrar
Electromagnetic andelectromechanicalphenomena, completesolution
Electromechanicalphenomena,fundamentalfrequency
Small-signalcharacteristicsNetwork, machinesand control
Systemoscillationand -damping,Netreduction,Controller layout
Loadflow for specialrequirements, e.g.homogeneous multi-conductor system
LoadflowOperating point
System componentsLinearization
Coupling
Frequency rangeall system-variables Eigenvalue analysis
onlyLoadflow
Time rangeInstantaneous values
ns...µs...ms...s
Time rangeQuasi steady-state values
s...min
LoadflowInitial conditions
Simulation Models for System Components, Machines, Controllers and Control Units
Single line networkComplex admittances
only fundamental frequency
Network in RSTAdmittances by differential
equations non-linearities
3 Possible ways of simulation
8/44
JJIIAnt.
Cerrar
• Formulaci on del problema est andar :
Dada una matriz A, n × n, calcular un escalar λ y un vector x nocero tales que
Ax = λx.
• A λ se le denomina autovalor o valor propio y a x sucorrespondiente vector propio o autovector .
• Para que exista una solucion distinta de la trivial, x = 0, el valorpropio λ debera ser raız del polinomio de grado n, polinomiocaracterıstico :
det(A− λI) = 0.
• La teorıa y los algoritmos se aplican a matrices reales y complejas.
9/44
JJIIAnt.
Cerrar
Definicion 1 Se denominaespectrode la matrizA, Λ(A), al conjunto delos valores propios deA. Es decir,
Λ(A) = {λ ∈ C : det(A− λI) = 0}.
Definicion 2 Se denominaradio espectral, ρ(A), de una matrizA de ordenn, al valor maximo de los modulos de los valores propios de la matriz:
ρ(A) = max.λi ∈ Λ(A)
|λi|.
• El radio espectral de una matriz es el radio del menor cırculo del planocomplejo centrado en el origen que contiene a todos los valores propiosde la matriz.
10/44
JJIIAnt.
Cerrar
Interpretaci on geom etrica• Al aplicarsele a cualquier vector en la direcci on de alguno de los
vectores propios de A la transformacion que representa A, ese vectorse expande o encoge por un factor que determina el correspondientevalor propio .
ETSII-UPM
Interpretación geométricaPor lo general, el vector Ax no tiene la misma dirección que x.Los vectores propios son vectores que se transforman sin cambiar dedirección.El valor propio λ determina el cambio de longitud.
2x2 2 2λ=Ax x
1 1 1λ=Ax x
1x
xAx
• Los vectores propios se transforman sin cambiar de direccion.
• El valor propio λ determina el cambio de longitud.
11/44
JJIIAnt.
Cerrar
Ejemplos
• Si
A =
[1 00 2
]: λ1 = 1, x1 =
[10
], λ2 = 2, x2 =
[01
].
• Si
A =
[1,5 0,50,5 1,5
]: λ1 = 2, x1 =
[11
], λ2 = 1, x2 =
[−1
1
].
• Si
A =
[0 1
−1 0
]: λ1 = i, x1 =
[1i
], λ2 = −i, x2 =
[i1
],
donde i =√−1. u
12/44
JJIIAnt.
Cerrar
– Los vectores propios pertenecen al subespacio nulo de Ax− λI , esdecir ker(Ax− λI), y no estan unıvocamente determinados: Si v es unvector propio, αv tambien lo es.
– Siempre existen n valores propios de A: reales o complejos .
– No siempre existen n vectores propios.
– Los valores propios de multiplicidad m > 1 tienen un subespaciopropio asociado de dimension ≤ m.
• Todos los vectores de un subespacio propio son vectores propios.
– El problema de determinar los valores y vectores propios es unproblema no lineal en los valores propios λ y lineal en x.
13/44
JJIIAnt.
Cerrar
– El calculo num erico de los valores propios mediante la determinacionde las raıces del polinomio caracterıstico no es aconsejable por:
• El trabajo que comporta determinar los coeficientes del polinomio.
• El trabajo que lleva calcular las raıces del polinomio.
• La sensibilidad de los coeficientes del polinomio a errores deredondeo.
Ejemplo� Consideremos la matriz
A =
[1 εε 1
],
donde ε es cualquier numero menor que√
εmaq..� Los valores propios exactos de A son 1 + ε y 1− ε.
� El calculo mediante el polinomio caracterıstico darıa:
det(A− λI) = λ2 − 2λ + (1− ε2) = λ2 − 2λ + 1;
las raıces serıan (valores propios calculados) 1 y 1. u
14/44
JJIIAnt.
Cerrar
Indice
1. Introducci on
2. Interpretaci on geom etrica
3. Propiedades de los subespacios propios
4. Propiedades de los valores propios
5. Tipos de matrices y valores propios
6. Lema de Schur y aplicaciones
7. Localizaci on de valores propios
8. Obtenci on num erica
9. Calculo de los valores singulares
15/44
JJIIAnt.
Cerrar
Propiedades de los subespaciospropiosTeorema 1Los vectores propios de una matriz A asociados a un mis-mo valor propio λ forman un subespacio vectorial de Rn, denominadosubespacio propio.
I DEMOSTRACION. Si x1 y x2 son vectores propios asociados a un mismo valor propio λ,
A(ax1 + bx2) = aAx1 + bAx2 = λ(ax1 + bx2)
lo que demuestra que una combinacion lineal de vectores propios asociados con un mismo valor propio
es tambien vector propio.
Teorema 2Los subespacios propios correspondientes a valores propiosdistintos solo tienen en comun el vector nulo.
I DEMOSTRACION. Supongase que x pertenece a dos subespacios propios V1 y V2. Se cumplira que
Ax = λ1xAx = λ2x
}0 = (λ1 − λ2)x ⇒ x = 0.
Los vectores propios correspondientes a valores propios distintos son pues linealmente independientes.
16/44
JJIIAnt.
Cerrar
Propiedades de los valores propios
Definicion 3 Dos matricesn×n, A y B, se dicensemejantessi existe unamatriz invertibleP tal que
A = P −1BP .
Teorema 3Dos matrices semejantes tienen el mismo polinomio caracterısti-co y, por consiguiente, los mismos valores propios.
Definicion 4 Una matrizA se dicediagonalizable (por semejanza)si essemejante a una matriz diagonal.
Teorema 4 Una matriz A, n × n, es diagonalizable si y solo si tiene nvectores propios linealmente independientes.
17/44
JJIIAnt.
Cerrar
Teorema 5La suma de los valores propios de una matriz A es igual a latraza de la matriz, es decir,
λ1 + λ2 + · · · + λn =
n∑i=1
aii.
Teorema 6El producto de los valores propios de una matriz A es igual aldeterminante de la matriz.
Teorema 7Los valores propios de una matriz triangular son los coeficientesde su diagonal principal.
Teorema 8Una matriz A es singular si y solo si tiene un valor propio iguala cero.
18/44
JJIIAnt.
Cerrar
Teorema 9Si los valores propios de una matriz A son λi, 0 ≤ i ≤ n, losvalores propios de la matriz A− αI son
λi − α, 0 ≤ i ≤ n.
Los vectores propios de A y A− αI son identicos.
Teorema 10Los valores propios de las potencias de una matriz A son lascorrespondientes potencias; los vectores propios son los mismos.
I DEMOSTRACION. Si consideramos la definicion,
Ax = λx; A2x = λAx = λ2x; · · · Anx = λnx
S−1AS = Λ; S−1ASS−1AS = Λ2 ⇒ S−1A2S = Λ2.
Las potencias negativas tambien:
Ax = λx; A−1Ax = λA−1x ⇒ A−1x = λ−1x.
19/44
JJIIAnt.
Cerrar
Indice
1. Introducci on
2. Interpretaci on geom etrica
3. Propiedades de los subespacios propios
4. Propiedades de los valores propios
5. Tipos de matrices y valores propios
6. Lema de Schur y aplicaciones
7. Localizaci on de valores propios
8. Obtenci on num erica
9. Calculo de los valores singulares
20/44
JJIIAnt.
Cerrar
Tipos de matrices y valores propios– Ademas de las matrices mas habituales, en el calculo de sus valores y
vectores propios tienen una relevancia particular las siguientes matrices:
Ortogonales Recordemos que estas matrices son aquellas que tienencomo inversa su traspuesta.Ejemplo [
0 11 0
],
[−1 0
0 −1
],
[ √2/2
√2/2
−√
2/2√
2/2
].
• Todos los valores propios de una matriz ortogonal tienen modulounidad.
21/44
JJIIAnt.
Cerrar
Hermıticas Son una generalizacion de las matrices simetricas. Sonaquellas iguales a su traspuesta conjugada; es decir A = AH.Ejemplo La matriz [
1 1 + i1− i 2
]es hermıtica.
• Si una matriz es hermıtica, el producto xHAx es un numero real .• Los valores propios de una matriz hermıtica, en consecuencia,
son numeros reales .En efecto
Ax = λx; xHAx︸ ︷︷ ︸∈R
= λxHx = λ ||x||2︸ ︷︷ ︸∈R
.
22/44
JJIIAnt.
Cerrar
• En una matriz hermıtica los vectores propios correspondientesa dos valores propios distintos son ortogonales entre sı.En efecto,
Ax1 = λ1x1Ax2 = λ2x2
}xH
2 AHx1 = λ1xH2 x1
xH2 AHx1 = λ2x
H2 x1
}(λ1 − λ2)x
H2 x1 = 0.
Como los valores propios λ1 y λ2 son distintos,
xH2 x1 = 0.
• Si los vectores propios se normalizan xHx = 1, la matriz devectores propios S se convierte en una matriz ortogonal Q.
23/44
JJIIAnt.
Cerrar
Unitarias Son aquellas cuya inversa es su compleja conjugada; esdecir,
UHU = UUH = I.
Ejemplo La matriz [i√
2/2√
2/2−√
2/2 −i√
2/2
].
es unitaria.
• Las matrices unitarias son una extension de las matricesortogonales para el campo complejo.
• Una matriz unitaria no modifica ni los angulos ni las distancias:
(Ux)H
(Uy) = xHUHUy = xHy si y = x, ||Ux||2 = ||x||2.
• Todos los valores propios de una matriz unitaria tienen modulounidad.
24/44
JJIIAnt.
Cerrar
• Los vectores propios correspondientes a valores propios distintosson ortogonales entre sı.En efecto,
Ux1 = λ1x1Ux2 = λ2x2
}xH
2 UHx1 = λ1xH2 x1
xH2 UHx1 = λ2x
H2 x1
}(λ1 − λ2)x
H2 x1 = 0.
Como los valores propios son distintos, xH2 x1 = 0.
Normales Son aquellas que cumplen que
AAH = AHA.
Ejemplo 1 2 00 1 22 0 1
.
25/44
JJIIAnt.
Cerrar
Indice
1. Introducci on
2. Interpretaci on geom etrica
3. Propiedades de los subespacios propios
4. Propiedades de los valores propios
5. Tipos de matrices y valores propios
6. Lema de Schur y aplicaciones
7. Localizaci on de valores propios
8. Obtenci on num erica
9. Calculo de los valores singulares
26/44
JJIIAnt.
Cerrar
Lema de Schur y aplicaciones
Teorema 11Para cualquier A ∈ Cn×n, existe una matriz unitaria U tal que
UHAU = T ,
donde T es una matriz triangular superior.
Corolario 1 Si A ∈ Rn×n es simetrica, existe una matriz ortogonal U talque U TAU = D, donde D es una matriz diagonal.
Teorema 12Los valores propios de una matriz hermıtica definida positivason todos positivos.Recıprocamente, si todos los valores propios de una matriz son positivos,debe ser definida positiva.
27/44
JJIIAnt.
Cerrar
Teorema 13Forma canonica de Jordan Para una matriz A ∈ Cn×n, existeuna matriz T regular tal que
T −1AT = J =
J 1
· 0. . .
0 ·Jn
,
donde
J i =
λi 1
λi 1 0· ·· ·
0 · 1λi
es una matriz de Jordan y los λi son los valores propios de A.
28/44
JJIIAnt.
Cerrar
– Como resumen, la tabla que sigue expone las posibilidades de lastransformaciones por semejanza.
A T B = T −1AT
Valores propios distintos Regular Diagonal
Simetrica real Ortogonal Diagonal real
Hermıtica compleja Unitaria Diagonal real
Normal Unitaria Diagonal
Real cualquiera Ortogonal Triangular en bloques (real)
Cualquiera Unitaria Triangular superior (Schur)
Cualquiera Regular Casi diagonal (Jordan)
29/44
JJIIAnt.
Cerrar
Indice
1. Introducci on
2. Interpretaci on geom etrica
3. Propiedades de los subespacios propios
4. Propiedades de los valores propios
5. Tipos de matrices y valores propios
6. Lema de Schur y aplicaciones
7. Localizaci on de valores propios
8. Obtenci on num erica
9. Calculo de los valores singulares
30/44
JJIIAnt.
Cerrar
Localizaci on de valores propios– Si no se necesita calcular exactamente los valores propios , sino
saber grosso modo donde se encuentran en el plano complejo, existenvarias formas de hacerlo .
• La mas simple surge de la relacion
|λ| ≤ ||A||,
para cualquier norma matricial inducida por una norma vectorial.
� Los valores propios de una matriz se localizan en el planocomplejo, dentro del circulo centrado en el origen de radio||A||.
31/44
JJIIAnt.
Cerrar
Teorema 14Gershgorin Los valores propios de una matriz A ∈ Cn×n
se encuentran en la union de los n discos de Gershgorin, cada uno de loscuales k esta centrado en akk y tiene de radio
n∑j=1
j 6=k
|akj|.
I DEMOSTRACION. Sea λ un valor propio de A y x su vector propio asociado. De Ax = λx y(λI −A)x) = 0 se tiene que
(λ− akk)xk =n∑
j=1
j 6=k
akjxj , k = 1, . . . , n,
donde xk es el componente k-esimo del vector x.
I Si xi es el componente de x mas grande en valor absoluto, como |xj |/|xi| ≤ 1 para j 6= i, se tiene que
|λ− aii| ≤n∑
j=1
j 6=i
|aij ||xj ||xi|
≤n∑
j=1
j 6=i
|aij |.
Luego λ esta contenido en el disco {λ : |λ− aii| ≤ ri}.
32/44
JJIIAnt.
Cerrar
– El siguiente programa de Matlab calcula los cırculos o discos deGershgorin y los dibuja.
function [G,e] = gersh(A,noplot)%GERSH Discos de Gershgorin.% GERSH(A) dibuja los discos de Gershgorin de la% matriz cuadrada A.% Si [G, E] = GERSH(A, 1) no se dibujan% y devuelve datos en G y E (val. propios)..
if diff(size(A)), error(’Matriz no es cuadrada.’), end
n = length(A); m = 80; G = zeros(m,n);d = diag(A); r = sum(abs(A-diag(d))’)’;e = eig(A);
radvec = exp(i * linspace(0,2 * pi,m)’);
for j=1:nG(:,j) = d(j) * ones(m,1) + r(j) * radvec;
endif nargin < 2
ax = cpltaxes(G(:));for j=1:n
plot(real(G(:,j)), imag(G(:,j)),’-’) % Plot discos.hold on
endplot(real(e), imag(e), ’x’) % Plot val. prop.axis(ax)axis(’square’)hold off
end
33/44
JJIIAnt.
Cerrar
Ejemplo
– Calcular los discos de Gershgorin de la matriz
A =
1 2 33 4 91 1 1
.
– Los radios de los discos son
r1 = 5r2 = 12r3 = 2.
– Los valores propios son: 7,3067; −0,6533 + 0,3473i y −0,6533− 0,3473i
34/44
JJIIAnt.
Cerrar
– Con el programa anterior, se obtiene lo siguiente.
−5 0 5 10 15
−10
−5
0
5
10
35/44
JJIIAnt.
Cerrar
– Los graficos de los discos de Gershgorin de otras matrices curiosas sepueden ver en esta otra grafica.
−40 −30 −20 −10 0−20
−10
0
10
20gersh(gallery(’lesp’,12))
−5 0 5
−5
0
5
gersh(gallery(’hanowa’,10))
−0.2 0 0.2 0.4 0.6 0.8−0.5
0
0.5gersh(gallery(’ipjfact’,6,1))
−2 −1 0 1 2
−2
−1
0
1
2
gersh(gallery(’smoke’,16,1))
36/44
JJIIAnt.
Cerrar
Indice
1. Introducci on
2. Interpretaci on geom etrica
3. Propiedades de los subespacios propios
4. Propiedades de los valores propios
5. Tipos de matrices y valores propios
6. Lema de Schur y aplicaciones
7. Localizaci on de valores propios
8. Obtenci on num erica
9. Calculo de los valores singulares
37/44
JJIIAnt.
Cerrar
Obtenci on num erica– Todos los metodos que proponemos son iterativos
• Ninguno de ellos , en principio, es muy superior a los dem as.
Metodo de la iteraci on de potencia
– Calcula el valor propio de mayor valor absoluto –valor propiodominante– y su vector propio.
1. Parte de un vector inicial x0 de modulo unidad; Progresa mediante laformula de recurrencia
yk−1 = Axk−1, xk =yk−1
||yk−1||∞.
2. El vector xi converge al vector propio v1, correspondiente al valorpropio dominante λ1, al que converge ||yk−1||∞.
38/44
JJIIAnt.
Cerrar
– La velocidad de convergencia de este algoritmo depende de larelaci on |λ2/λ1|: a menor valor de esta, mayor velocidad deconvergencia.
Demostracion de la convergencia:
– Si se expresa
x0 =n∑
i=1
αivi,
donde los vi son los vectores propios de A, entonces
xk = Axk−1 = A2xk−2 = · · · = Akx0 =
= Akn∑
i=1
αivi =n∑
i=1
αiAkvi =
n∑i=1
λki αivi
= λk1
(α1v1 +
n∑i=2
(λi/λ1)kαivi
).
– Como |λi/λ1| < 1, para i > 1, las sucesivas potencias (λi/λ1)k → 0 dejando solo los
componentes correspondientes a v1.
39/44
JJIIAnt.
Cerrar
Ejemplo
– Calculemos el valor propio dominante de la matriz[1,5 0,50,5 1,5
]partiendo de xT
0 = [0, 1].
– Utilicemos una pequena sesion de Matlab como la que sigue:
>> x=[0;1];>> A=[1.5 0.5;0.5 1.5];>> for i=1:10v=A* xm=max(abs(v))x=v/maend
40/44
JJIIAnt.
Cerrar
– Los resultados que se obtienen (vector propio y valor propio) son los deesta tabla.
k xTk ||xk||∞
0 0,0 1,01 0,333 1,0 1,50002 0,600 1,0 1,66673 0,778 1,0 1,80004 0,882 1,0 1,88895 0,939 1,0 1,94126 0,969 1,0 1,96977 0,984 1,0 1,98468 0,992 1,0 1,9922
41/44
JJIIAnt.
Cerrar
– El comportamiento de las iteraciones se puede ver geometricamente enla figura.
Geometric Interpretation
Behavior of power iteration depicted geomet-
rically:
−1.0 −0.5 0.0 0.5 1.00.0
0.5
1.0
...................
...................
...................
...................
...................
...................
...................
...................
...................
...................
...................
...................
...................
...................
...................
...................
...................
...................
...................
...........................
..........................
.................................................................................................................................................................................................................................................................................................................................................................................................................................................
..........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
..............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
......................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
v2 v1
x0 x1 x2 x3 x4.............................................................................. ....................................................
..........................
..............................
..............................
..............................
.............................
..............................
..............................
.............................
..............................
..............................
................................
........................................................................................................
........................................................................................................
............................................................................................
Initial vector
x0 =
[0
1
]= 1
[1
1
]+ 1
[−1
1
]contains equal components in two eigenvectors
(shown by dashed arrows)
Repeated multiplication by A causes compo-
nent in first eigenvector (corresponding to larger
eigenvalue, 2) to dominate, and hence sequence
of vectors converges to that eigenvector
35
– El punto inicial
x0 =
[01
]= 1
[11
]+ 1
[−1
1
]es una combinacion lineal equicomponente de los dos vectores propiosv1 y v2.
– La multiplicacion sucesiva por A causa que el componente en el primervector propio (correspondiente al valor propio mayor, 2) sea el quedomine, por lo que la secuencia converge a ese vector propio. u
42/44
JJIIAnt.
Cerrar
– El metodo puede fallar por diversas razones:
• El vector de partida puede que tenga componente cero en el vectordominante v1.
� El error de redondeo en la practica puede que introduzca unpequeno componente, por lo que este peligro rara vez ocurre.
• Puede que haya mas de un valor propio con el mismo modulo(maximo), en cuyo caso las iteraciones puede que converjan a unacombinacion lineal de los correspondientes vectores propios.
� Este caso es bastante habitual pues esos dos valores propiospueden ser un par complejo conjugado.
• Para una matriz real y un punto de partida tambien real, puede quenunca se converja a un vector complejo.
43/44
JJIIAnt.
Cerrar
– Un programa de Matlab que implementa el metodo de la potencia es elque sigue.
function [lambda,V,cnt]= potencia(A,x,tol,max1)% Metodo de la potencia: Power methodif nargin<3
tol=sqrt(eps); max1=100;endlambda=0;cnt=0;err=1;while cnt<=max1 & err>tol
y=A* x;c1=max(abs(y));y=y/c1;dc=abs(lambda-c1); dv=norm(x-y);err=max(dc,dv);x=y; lambda=c1;cnt=cnt+1;
endV=x;
44/44
JJIIAnt.
Cerrar
Mejora del m etodo: desplazamiento
– Mediante un desplazamiento σ, A− σI , es posible hacer que∣∣∣∣λ2 − σ
λ1 − σ
∣∣∣∣ < ∣∣∣∣λ2
λ1
∣∣∣∣ ,y que, por lo tanto, la convergencia se acelere.
– La solucion real resultara de anadir σ al valor obtenido.
• En el ejemplo que venimos manejando, si se hace σ = 1, la relacionanterior se hace cero y el metodo converge en una iteracion.
– Desafortunadamente no siempre se puede escoger de antemano undesplazamiento tan bueno .