clase_valvec_2_05
TRANSCRIPT
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 1/45
1/45
Ant.
Cerrar
Metodos Matematicos de Especialidad
Ingenierıa Electrica
Valores y vectores propios
2
Jose Luis de la Fuente O’[email protected]
Escuela Tecnica Superior de Ingenieros Industriales
Universidad Politecnica de Madrid
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 2/45
2/45
Ant.
Cerrar
Indice
1. Introduccion
2. Interpretacion geometrica3. 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. Localizacion de valores propios
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 3/45
3/45
Ant.
Cerrar
8. Obtencion numerica• Metodo de la iteracion de potencia
• Metodo de la iteracion inversa
• Iteracion mediante cociente de Rayleigh
• Deflacion• Iteracion simultanea
• Iteracion QR
• Metodo de Jacobi
•Comparacion de los metodos
9. Calculo de los valores singulares
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 4/45
4/45
Ant.
Cerrar
Metodo de la iteracion inversa
– Si en vez del valor propio de mayor magnitud, se necesita el mas
pequeno, se puede hacer uso de que los valores propios de A−1
sonlos recıprocos de A.
– El esquema iterativo serıa el que sigue.
x0 = punto de partida arbitrariofor k = 1, 2, . . .
Resolver Ayk = xk−1xk =
yk
||yk||∞end
Para resolver el sistema de ecuaciones bastarıa con factorizar la matrizA una sola vez.
– Se obtiene el valor propio dominante de A−1: el de menor en modulo
de A.
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 5/45
5/45
Ant.
Cerrar
Ejemplo (continuacion)
– Aplicando el metodo de la iteracion inversa al problema que manejamos,se obtienen los resultados de la tabla.
k xT
k||yk||∞
0 0,000 1,01 -0,333 1,0 0,7502 -0,600 1,0 0,8333 -0,778 1,0 0,9004 -0,882 1,0 0,9445 -0,939 1,0 0,971
6 -0,969 1,0 0,985
– Converge al valor propio 1 y vector propio [−1, 1]T . u
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 6/45
6/45
Ant.
Cerrar
– Un programa de Matlab que implementa el metodo de la iteracioninversa es el que sigue.
function [lambda,V,cnt]= ItInversa(A,x,tol,max1)
% Metodo de la iteracion inversa
if 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;
end
V=x;
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 7/45
7/45
Ant.
Cerrar
Mejora del metodo: desplazamiento
– El desplazamiento es particularmente util en el caso de la iteracioninversa.
– El valor propio de menor magnitud de A− σI sera λ− σ, si λ es elvalor propio de A mas proximo a σ.
• Con una eleccion apropiada de σ se puede calcular cualquier valorpropio de A que este proximo a esa σ.
• Si el desplazamiento esta proximo a un valor propio, la convergenciaes muy rapida.
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 8/45
8/45
Ant.
Cerrar
Iteracion mediante cociente de Rayleigh
Definicion 1 El cociente de Rayleigh de un vector x ∈ R es el escalar
r(x) =
xT Ax
xT x .
– Dadou —un vector propio aproximado de una matriz A ∈ Rn×n —, eldeterminar la mejor estimacion del correspondiente valor propio λ se
puede considerar como un problema de mınimos cuadrados n × 1como el siguiente:xλ ∼= Ax.
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 9/45
9/45
Ant.
Cerrar
– A partir de las ecuaciones normales de este problema,xT xλ = xT Ax, la solucion es
λ =xT Ax
xT x .
– El cociente de Rayleigh puede utilizarse para acelerar laconvergencia de los metodos iterativos que hemos visto, pues en
una iteracion k ese cociente da una mejor aproximacion al valor propioque la que se tenga en ese momento.
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 10/45
10/45
Ant.
Cerrar
– El esquema iterativo del metodo de la iteracion inversa condesplazamiento, utilizando como desplazamiento el valor delcociente de Rayleigh, es el que sigue.
x0 = punto de partida arbitrariofor k = 1, 2, . . .
σk =xT k−1Axk−1xT k
−1xk−1
Resolver (A− σkI )yk = xk−1
xk =yk
||yk||∞end
– El cociente de Rayleigh tambien se puede aplicar a vectores complejosreemplazando el traspuesto de x por su traspuesto conjugado; es decir,
xH Ax
xH x.
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 11/45
11/45
Ant.
Cerrar
Ejemplo (continuacion)
– Aplicando el metodo de la iteracion de potencia con el cociente deRayleigh al problema que manejamos, se obtienen los resultados de latabla.
k xT
k||yk||∞ xT
kAxk/xT
kxk
0 0,000 1,01 0,333 1,0 0,150 1,500
2 0,600 1,0 1,667 1,800
3 0,778 1,0 1,800 1,941
4 0,882 1,0 1,889 1,985
5 0,939 1,0 1,941 1,996
6 0,969 1,0 1,970 1,999
– Observese que las iteraciones convergen mas rapidamente que en loscasos anteriores.
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 12/45
12/45
Ant.
Cerrar
– Utilizando un punto de partida aleatorio, con el mismo problema y elultimo algoritmo, ocurrirıa lo que sigue.
k xT
k σk
0 0,807 0,397 1,896
1 0,924 1,000 1,998
2 1,000 1,000 2,000
u
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 13/45
13/45
Ant.
Cerrar
– El programa de Matlab que implementa el metodo de la iteracion inversacon desplazamiento, usando para este el cociente de Rayleigh es el quesigue (utilizado para el ejemplo anterior).
function [lambda,V,cnt]= ItInvRayleigh(A,x,tol,max1)
% Metodo de la iteracion inversa
if nargin<3
tol=0.000001; max1=10;
end
lambda=0;cnt=0;err=1;n=length(A);x=rand(n,1);
format longwhile err>tol
sigma=(x’*A*x)/(x’*x);
y=(A-sigma*eye(n))\x;
y=y/norm(y,inf);
err=norm(abs(y-x),inf);
x=y;
cnt=cnt+1;end
y=A*x;
[xk k]=max(abs(x));
lambda=y(k)/x(k);
V=x;
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 14/45
14/45
Ant.
Cerrar
Deflacion
– Idea basica: Calculados un valor y un vector propios mediante laestrategia de la potencia, los demas se pueden obtener mediantedeflacion:
Quitando los conocidos y actuando como cuando, una vez cono-cida una de las raıces, λ1, de un polinomio en λ, este se dividepor λ− λ1, obteniendose otro de grado n − 1.
Opcion a Si H es una matriz regular —de Householder, por ej.— tal queHx = αe1, la transformacion de semejanza que determina H transforma A de la siguiente forma,
HAH −1
= λ1 b
T
0 B
,
donde B es una matriz de orden n − 1 cuyos valores propios sonλ2, . . . , λn.
Despues se trabaja con B para calcular el siguiente valor propio λ2,
etc.
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 15/45
15/45
Ant.
Cerrar
Ademas, si y2 es un vector propio de B asociado a λ2, el vector
x2 = H −1
αy2
, donde α =
bT y2
λ2
−λ1
,
es el vector propio correspondiente a λ2 en la matriz original A,supuesto λ1 = λ2.
Opcion b Alternativamente se podrıa escoger cualquier u1 tal queuT 1x1 = λ1, lo que harıa que la matriz A
−x1u
T 1
tuviese como
valores propios 0, λ2, . . . , λn.• Los posibles vectores u1 serıan:
u1 = λ1x1, si A es simetrica y ||x1||2 = 1.
u1 = λ1y1, donde y1 es el vector propio izquierdocorrespondiente; es decir, AT y1 = λ1y1, con yT
1x1 = 1.
u1 = AT ek, si x1 esta normalizado, con ||x1||∞ = 1, y elcomponente k-esimo de x1 es 1.
Las dificultades numericas de esta forma de actuar segun avanzael proceso son importantes.
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 16/45
16/45
Ant.
Cerrar
Iteracion simultanea
– Su idea basica para calcular simultaneamente varios valores y vectorespropios es muy simple: en vez de usar un unico x0 de partida, utilizaruna matriz X 0, n × p, de rango p, y hacer
X k = AX k−1.
– El esquema del algoritmo es el de la tabla que sigue.
X 0 = matriz n × p de rango pfor k = 1, 2, . . .
X k = AX k−1
end
– El subespacio Im(X k) converge al subespacio de los vectores propiosde A correspondientes a los p mayores valores propios de A, supuesto
|λ p|
>|λ p+1
|.
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 17/45
17/45
Ant.
Cerrar
– Las importantes dificultades numericas de esta estrategia sesoslayan calculando en cada iteracion la factorizacion QR deX k, yortonormalizando ası las columnas de X k.
•En vez de X k se usarıa Q como base del subespacio Im(X k).
– El esquema resultante – metodo de la iteracion ortogonal – serıa elque sigue. La matriz Qk es n × p y R k, p× p.
X 0 = matriz n × p de rango pfor k = 1, 2, . . .
Calcular la factorizacion QR de X k−1QkR k = X k−1X k = AQk
end
– Se puede comprobar que las iteraciones convergen a una matriztriangular en bloques en la que el primer bloque serıa triangular si los
modulos de los distintos valores propios de A son distintos.
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 18/45
18/45
Ant.
Cerrar
– La version en Matlab para calcular los 5 valores propios masimportantes de una matriz generada aleatoriamente es el que sigue.
function [i,r]=ValItOrt(A)
% r maximos valores propios por iteracion ortogonal
n=length(A); r=5;
tol=1e-06;
A=A’*A; B=A; i=0;
disp(’Metodo de la iteracion ortogonal QR’);
Q=eye(n,r); R=eye(r); Z=zeros(size(Q)); vprn=1; vpr=0; err=1;
while i<200 & err>tol
vpr=vprn;
Z=A*Q;
[Q,R]=qr(Z,0);
vprn=min(diag(R));
i=i+1;
err=abs((vprn-vpr)/vprn);
end
if i==100 disp(’No ha habido convergencia’);
else disp(’Valores propios maximos: ’);
end
format long
r=diag(R)
disp(’Valores calculados con eig()’);
disp(-sort(eig(-B)));
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 19/45
19/45
Ant.
Cerrar
– Si se ejecuta este archivo, se obtienen los resultados que siguen.
>> [i,r]=ValItOrt(a)
Metodo de la iteracion ortogonal QR
Valores propios maximos:
r =
1.0e+002 *1.04491609655094
0.04617888873738
0.03715854886704
0.03626236219115
0.02565733377033
Valores calculados con eig()
1.0e+002 *1.04491609655094
0.046178888737380.03715864118473
0.03626227210019
0.02565762257408
0.02459086560907
0.02227113766204
0.01897771907175
0.01823167147015
0.01050117260179
0.00898193588574
0.006912019464340.00517201234107
0.00335425439442
0.00262229621638
0.00168109615293
0.00058498291002
0.00056899283926
0.00019955545195
0.00010655004923
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 20/45
20/45
Ant.
Cerrar
Iteracion QR
– Si en la iteracion ortogonal p = n, se pueden calcular todos los valorespropios de A, ası como los correspondientes vectores propios.
• Si se parte de X 0 = I , las matrices
Ak = QH k AQk
generadas por el metodo de la iteracion ortogonal convergeran auna matriz triangular, o triangular por bloques, en la que estentodos los valores propios de A.
– El metodo de la iteracion QR realiza el calculo de las matrices Ak sinrealizar explıcitamente el producto de matrices anterior.
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 21/45
21/45
Ant.
Cerrar
– Partiendo deA0 = A, en la iteracion numero k se calcula lafactorizacion QR de Ak−1,es decir,
QkR k = Ak−1.A partir de aquı,
Ak = QH k Ak−1Qk = QH
k (QkR k)Qk = R kQk,
por lo que cualquier Ak se puede obtener a partir del calculo delproducto inverso R kQk.
1. Los coeficientes en la diagonal principal de Ak, o en los bloquesdiagonales, convergen a los valores propios de A.
2. Las columnas de Qk
forman una base ortonormal del subespacioIm(Ak).
3. Si A es simetrica, las iteraciones conservan la simetrıa y Ak
converge a una matriz triangular y simetrica: por consiguientediagonal.
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 22/45
22/45
Ant.
Cerrar
Iteracion QR con desplazamiento
– La velocidad de convergencia se puede aumentar si se incorporan losdesplazamientos:
QkR k = Ak−1 − σkI
Ak = R kQk + σkI ,
donde σk es una aproximacion de un valor propio.
• Como desplazamiento se puede tomar el valor del coeficiente ak−1nn
de Ak−1, que deberıa ser una buena aproximacion de λn.
•Si el bloque diagonal 2
×2 mas abajo no es diagonal (lo que indica
la existencia de valores propios complejos), habrıa que calcular losvalores propios de esa submatriz para aplicar el desplazamientocorrespondiente.
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 23/45
23/45
Ant.
Cerrar
– El siguiente programa de Matlab implementa el metodo de la iteracionQR con desplazamiento para matrices simetricas.
function [lambda]= IteracionQR(A,tol)
% Metodo de la iteracion QR con desplazamiento
if nargin<2
tol=sqrt(eps)*norm(A);
endlambda=0;n=length(A);
for k=n:-1:2
while norm(A(k,1:k-1),inf) > tol
sigma=A(k,k);
[Q,R]=qr(A(1:k,1:k)-sigma*eye(k,k));
A(1:k,1:k)=R*Q+sigma*eye(k,k);
end
end
lambda=diag(A);
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 24/45
24/45
Ant.
Cerrar
Transformaciones preliminares
– La factorizacion QR de una matriz n × n que hay que realizar en cada
iteracion del metodo anterior requiere O(n3
) operaciones.
– Se podrıan reducir mucho si la matriz de partida fuese lo mas parecidaposible a una triangular.
Definicion 2 Una matriz de Hessenberg es una matriz triangular exceptopor una subdiagonal inmediatamente adyacente a la diagonal principal.
@ @
@ @
@ @
@ @
0
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 25/45
25/45
Ant.
Cerrar
– Cualquier matriz se puede reducir a la forma de Hessenbergmediante transformaciones ortogonales: por ejemplo de Householder.
•Si la matriz original es simetrica, la de Hessenberg obtenida serıa
tridiagonal.
– La forma de Hessenberg se conserva durante las iteraciones de unprocedimiento QR .
– Ventajas de transformar a Hessenberg:
• El trabajo por iteracion del metodo QR se reduce a O(n2), en vez deO(n3), para una matriz general, o O(n) para una matriz simetrica.
• Se necesitaran menos iteraciones por tratarse de una matriz casitriangular (o diagonal) desde el principio.
• Si hay elementos distintos de cero en la subdiagonal, la matriz deHessenberg es triangular en bloques y podrıa “trocearse” enpequenos subproblemas.
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 26/45
26/45
Ant.
Cerrar
– Teniendo en cuenta estas consideraciones, el metodo se implementa endos fases:
matriz simetrica 1a fase−−−−→ tridiagonal 2a fase−−−−→ diagonal
o
matriz general 1a fase
−−−−→Hessenberg 2a fase
−−−−→triangular
– El trabajo necesario para implementar todo el proceso iterativo –elpreliminar y el iterativo– se indica en la tabla que sigue.
Matriz simetrica Matriz general
4
3n3 para valores propios solo 10n3 para valores propios solo
9n3 valores y vectores propios 25n3 valores y vectores propios
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 27/45
27/45
Ant.
Cerrar
– De esta tabla cabe apuntar las siguientes consideraciones:
• Para matrices grandes, el metodo es prohibitivo.
•Si solo se necesitan unos pocos valores y vectores propios,especialmente para n grandes, el metodo no saca partido de ello.
• Requiere mucha memoria de ordenador, aunque la matriz seagrande y dispersa.
•Las transformaciones de semejanza introducen muchos elementos
no nulos por lo que se destruye la estructura de dispersidad.
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 28/45
28/45
Ant.
Cerrar
function D=It_QR_2(A,epsilon)
%Input Iteracion QR de una matriz simetrica
% tridiagonal
[n,n]=size(A);
B=house(A);
m=n;
D=zeros(n,1);
while (m>1)
while (abs(B(m,m-1))>=epsilon)
%Calcular desplazamiento
S=eig(B(m-1:m,m-1:m));
[j,k]=min([abs(B(m,m) *[1 1]’-S)]);
[Q,U]=qr(B-S(k)*eye(m));
B=U*Q+S(k)*eye(m);
end
A(1:m,1:m)=B;
m=m-1;
B=A(1:m,1:m);
end
D=sort(diag(A));
function T=house (A)[n,n]=size(A);
for k=1:n-2
s=norm(A(k+1:n,k));
if (A(k+1,k)<0)
s=-s;
end
r=sqrt(2*s*(A(k+1,k)+s));
W(1:k)=zeros(1,k);
W(k+1)=(A(k+1,k)+s)/r;
W(k+2:n)=A(k+2:n,k)’/r;
V(1:k)=zeros(1,k);
V(k+1:n)=A(k+1:n,k+1:n) *W(k+1:n)’;
c=W(k+1:n)*V(k+1:n)’;
Q(1:k)=zeros(1,k);
Q(k+1:n)=V(k+1:n)-c *W(k+1:n);
A(k+2:n,k)=zeros(n-k-1,1);
A(k,k+2:n)=zeros(1,n-k-1);
A(k+1,k)=-s;
A(k,k+1)=-s;
A(k+1:n,k+1:n)=A(k+1:n,k+1:n) ...
-2*W(k+1:n)’*Q(k+1:n)-2*Q(k+1:n)’*W(k+1:n);end
T=A;
– La ejecucion de este programa para una matriz 10× 10, simetrica,
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 29/45
29/45
Ant.
Cerrar
j p g p , ,generada aleatoriamente es la que sigue.
>> It_QR_2(A1)
ans =
0.01431999891591
0.04920529275253
0.17542171790536
0.28137578750760
0.53137970612468
0.66204600561851
1.31506994446549
1.90188902890340
2.24267984943143
24.95918482130558>> eig(A1)
ans =
0.01431999891591
0.04920529275254
0.17542171790536
0.28137578750761
0.531379706124680.66204600561851
1.31506994446549
1.90188902890340
2.24267984943143
24.95918482130557
>>
Metodo de Jacobi
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 30/45
30/45
Ant.
Cerrar
Metodo de Jacobi
– El de Jacobi es uno de los metodos mas antiguos para el calculo de losvalores propios de una matriz simetrica o compleja hermıtica.
– Utiliza transformaciones de semejanza basadas en rotaciones sobreplanos (como las de Givens, recordemos) para hacer cero pares deelementos simetricos de la matriz.
– Partiendo deA0, cada iteracion tiene la forma
Ak+1 = J T kAkJ k,
donde cada matriz J k se escoge de tal manera que, por ejemplo,
J T
AJ = c
−s
s c a b
b d c s
−s c
=
c2a − 2csb + s2d c2b + cs(a− d)− s2b
c2b + cs(a− d) − s2b c2d + 2csb + s2a
sea diagonal.
– Para ello:
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 31/45
31/45
Ant.
Cerrar
• Haciendoc2b + cs(a
−d)
−s2b = 0
y dividiendo ambos lados por c2b, se obtiene que
1 +s
c
(a− d)
b− s2
c2= 0.
•Haciendo t = s/c se obtiene la ecuacion cuadratica
1 + t(a− d)
b− t2 = 0
en t, la tangente del angulo de rotacion.
• Obtenida t se calculan c = 1/√1 + t2
y s = c · t.
– Aplicando sistematicamente estas transformaciones se va consiguiendoque todos los coeficientes de la matriz que no estan en la diagonalprincipal se hagan cero o casi cero (dentro de la tolerancia maq.).
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 32/45
32/45
Ant.
Cerrar
– Existen dos formas de implementar el metodo:Clasico En cada paso se hace cero el mayor elemento en valor
absoluto que no este en la diagonal principal.La velocidad de convergencia es lineal aunque en la practica tiendea la cuadratica.
Cıclico Se hacen barridos por filas para anular sucesivamente todos loselementos fuera de la diagonal.Tiene convergencia cuadratica.
– Al metodo de Jacobi lo superan en prestaciones otros de los expuestos.
– Es difıcil generalizar para matrices no simetricas.
Ejemplo
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 33/45
33/45
Ant.
Cerrar
j p
– Sea
A0 =
1 0 2
0 2 12 1 1
.
Apliquemos el metodo de Jacobi.
– Anulemos inicialmente los coeficientes (1, 3) y (3, 1). Para ello,
apliquemosles la rotacion
J 0 =
0,707 0 −0,707
0 1 00,707 0 0,707
obteniendose
A1 = J T 0A0J 0 =
3 0,707 0
0,707 2 0,7070 0,707 −1
.
– A continuacion, anulemos (1, 2) y (2, 1) mediante la rotacion
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 34/45
34/45
Ant.
Cerrar
J 1 =
0,888 −0,460 00,460 0,888 0
0 0 1
obteniendose
A2 = J T 1A1J 1 =
3,366 0 0,325
0 1,634 0,6280,325 0,628 −1
.
– Luego, anulamos el (3, 2) y el (2, 3) usando la rotacion
J 2 =
1 0 00 0,975 −0,2260 0,226 0,975
para obtener
A3 = J T 2A2J 2 =
3,366 0,0735 0,317
0,0735 1,780 00,317 0 1,145
.
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 35/45
35/45
Ant.
Cerrar
– Comenzando un nuevo “barrido”, hagamos cero los coeficientes (1, 3) y(3, 1). Usaremos la rotacion
J 3 =
0,998 0 −0,070
0 1 00,070 0 0,998
obteniendose
A4 = J T 3A3J 3 =
3,388 0,0733 0
0,0733 1,780 0,00510 0,0051 −1,167
.
– El proceso continuarıa hasta llegar a conseguir los valores propiosdeseados. u
function [V,D]=Jacobi_val_1(A)
% C´l l d l t i d t i i ´t i
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 36/45
36/45
Ant.
Cerrar
% Calculo de valores y vectores propios de una matriz simetrica
tol=sqrt(eps);
D=A;
[n,n]=size(A);
V=eye(n);
state=1;
%Calcular fila p y columna q del elemento de mayor valor
% no en la diagonal de A
[m1 p]=max(abs(D-diag(diag(D))));
[m2 q]=max(m1);
p=p(q);
while (state==1)
%Se hacen cero Dpq y Dqp
t=D(p,q)/(D(q,q)-D(p,p));
c=1/sqrt(tˆ2+1);
s=c*t;
J=[c s;-s c];
D([p q],:)=J’*D([p q],:);
D(:,[p q])=D(:,[p q])*J;
V(:,[p q])=V(:,[p q])*J;
[m1 p]=max(abs(D-diag(diag(D))));
[m2 q]=max(m1);
p=p(q);
if (abs(D(p,q))<tol*sqrt(sum(diag(D).ˆ2)/n))
state=0;
end
end
D=sort(diag(D));
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 37/45
37/45
Ant.
Cerrar
– Si usamos el programa para resolver el ejemplo hecho a mano, se
obtiene la salida que sigue.
[v d]=Jacobi_val_1(Aeje)
v =
0.73923873953921 -0.42713229146437 0.52065736483112
0.23319197840754 0.88765033546558 0.39711255728600
-0.63178128111781 -0.17214786532587 0.75578933922945d =
-0.70927535943692
1.80606343352537
3.90321192591156
– Como se puede ver, con las pocas iteraciones que hacıamos a mano laaproximacion a los valores propios reales es muy rapida.
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 38/45
38/45
Ant.
Cerrar
Comparacion de los metodos
Calculo de todos los valores propios y vectorespropios
Matrices generales reales o complejas. Reduccion preliminar a formade Hessenberg seguida de iteracion QR.
Matrices reales simetricas o complejas hermıticas. Reduccionpreliminar a matriz tridiagonal seguida de iteracion QR.
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 39/45
39/45
Ant.
Cerrar
Calculo de algunos valores y vectores propios
Matrices simetricas de tama ˜ no moderado. Reduccion preliminar a
matriz tridiagonal seguida de iteraci´on inversa.
Matrices de gran tama ˜ no. Metodo con iteracion de Arnoldi paramatrices generales.Lanczos para matrices simetricas o complejas hermıticas.Tambien algunas veces iteracion simultanea ortogonal.
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 40/45
40/45
Ant.
Cerrar
Indice
1. Introduccion
2. Interpretacion geometrica
3. Propiedades de los subespacios propios
4. Propiedades de los valores propios5. Tipos de matrices y valores propios
6. Lema de Schur y aplicaciones
7. Localizacion de valores propios
8. Obtencion numerica
9. Calculo de los valores singulares
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 41/45
41/45
Ant.
Cerrar
Calculo de los valores singulares
– El calculo de los valores singulares de una matriz —recordemos: raıcescuadradas no negativas de los valores propios de AT A — se puedellevar a cabo a partir de las ideas expuestas hasta este punto.
– No obstante existen algoritmos muy eficaces especıficos basados eniteraciones QR directamente en la matriz A.
Algoritmo de Golub y Reinsch. Primera fase
– Consiste en reducir la matriz A a una triangular superior bidiagonalmediante transformaciones ortogonales de Householder.
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 42/45
42/45
Ant.
Cerrar
– Es decir, hacer
Q
T
BAΠB = B = B1
0
,
donde
B =
d1 f 2
d2 f 3 0. . . . . .
0 . . . f ndn
0
, (1)
QB = Q1 · · ·Qn ∈ Rm×m y ΠB = Π1 · · ·Πn−2 ∈ Rn×n.
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 43/45
43/45
Ant.
Cerrar
– El esquema que se seguirıa con una matriz A6×4 sera el de la figura.
××××××××××××××××××××××××
×××××××××××××××××××0
0000
×××××××××××××××××0
0000
0 0 ×××××××××××××0
0000
0000
0 0
- - -
Q1 Π1 Q2
××××××
××××××00
000
00
00
0 00
××××××
×××00
000
00
00
00
0
0 00
××××××
×00
000
00
00
00
0
00
0 00
- - -
Π2 Q3 Q4
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 44/45
44/45
Ant.
Cerrar
Segunda fase
– Una vez bidiagonalizada la matrizA, se hacen cero los elementos queno estan en la diagonal principal mediante un algoritmo que obtenga
QT S B1ΠS = Σ = diag(σ1, . . . , σn),
donde QS ∈ Rn×n y ΠS ∈ Rn×n son matrices ortogonales.
– La descomposicion en valores singulares de la matriz A sera
A = U Σ0V T ,
donde U = QB diag(QS , I m−n) y V = ΠBΠS .
– Ese algoritmo procede iterativamente haciendo
B UTB V k 1 2
5/13/2018 Clase_valvec_2_05 - slidepdf.com
http://slidepdf.com/reader/full/clasevalvec205 45/45
45/45
Ant.
Cerrar
Bk+1 = U T kBkV k, k = 1, 2, . . . ,
donde U k y V k son matrices ortogonales, de tal forma queΣ = lım
k→∞Bk.
– El esquema que se sigue es este.
13 3212 21
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
∗ ∗ ∗ ∗ ∗ + ∗ ∗ ∗ ∗ ∗ ∗ + ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ + ∗ ∗ ∗ ∗ ∗ ∗ + ∗ ∗ ∗ ∗
∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗
→ → → →BG G BBG G B
43 35 5424
0 0
0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0
∗ ∗ ∗
∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ + ∗ ∗ ∗ ∗
+ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ + ∗ ∗
→ → → →G B BG G BBG
– Se verifica que los elementos no nulos encima de la diagonal principaltienden a hacerse cero (desde el n-1 hasta el primero) y los de ladiagonal a los valores singulares como se quiere.