valores y vectores propiosuniversidad politécnica de madrid–escuela técnica superior de...

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

1/95Universidad Politécnica de Madrid–Escuela Técnica Superior de Ingenieros IndustrialesGrado en Ingeniería en Tecnologías Industriales-3º

Matemáticas de Especialidad–Ingeniería Eléctrica

Valores y vectores propiosValores singulares

José Luis de la Fuente O’[email protected]@upm.es

Clase_valvec.pdf

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

2/95Índice

� Cuestiones teóricas de valores y vectores propios

� Localización de valores propios

� Obtención numérica de valores y vectores propios� Método de Jacobi� Método de la iteración de potencia� Método de la iteración inversa� Iteración mediante cociente de Rayleigh� Deflación� Iteración simultánea� Iteración QR� Subespacios de Krylov� Comparación de los métodos

� Cálculo de valores singulares

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

3/95

� Los valores y vectores propios adquieren una relevancia destacada para analizarasuntos con oscilación y resonancia. Su conocimiento es básico en:

� Sistemas eléctricos de corriente alterna.

� Modos de vibración natural de estructuras.

� Instrumentos musicales.

� Mecánica cuántica.

� Lasers.

� Resonancia Magnética Nuclear (NMR).

� : : :

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

4/95

� Su cálculo e interpretación es esencial para el análisis de sistemas de generación,transporte y demanda de energía eléctrica.

TurbinegovernorTorsion

Syn-chronousmaschineAVR

On-loadtapchanger

CurrenttransformerSaturationProtectivesystem

BreakerArcrestriking

External systemLineCableHVDCFACTS

ConverterVAR-LoadVAR-AdmittanceMotorLoad torque

GInter-

connectedSystem

SVC

M 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

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

5/95

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

NORMALIZED RIGHT EIGENVECTOR (MODE SHAPE)

SIGMA OMEGA ZETA FACO (RAD/SEC) (%) (HZ)-0,087 4,566 -1,9

ELECTRIC MACHINES

SYNCHRONOUS MACHINES18 items

COMPONENT NAME

1 DACOLOUA 2X150 MVA

2 MILLOA 2x 18 MVA

3 LOSQUI 2X 18+14+Adong

4 TEHUSEQUEL+JALA+BANELVOL

5 FALALFAL 2X95 MVA

6 TOLIZASAV, ZALSAV 10+3X32

7 PELRA 5X76 MVA

8 NASVENTA AT 18 KV

9 NASVENTA AT 19.2 KV

10 CAREN 2X58.8 MVA

11 ENCHEPHEHU 2X283 MVA

12 BUNCOL 2X240 MVA

13 CURAMACHI 2X53 MVA

14 COANTU 2X160 MVA

15 ROTOREL 4X105 MVA

16 NICOREA 5X21.5 MVA

17 QUEPAN 500 MVA

18 TILLARNUCA 2X68 MVA

0,19

0,45

0,43

0,15

0,16

0,14

0,37

0,63

1,00

0,63

0,18

0,06

0,05

0,04

0,06

0,06

0,22

0,37

0,56

0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

MODE OBSERVABILITY OF DEVIATION VARIABLESMOTOR SPEED

PYParLub the dynamic system and

observe the mode different devices.

MODE DISTRIBUTION ON COMPLEX S-PLANE

COMPLEX S-PLANE

17 out of 206 solved modes are selectedall the selected modes are inside the displayed range

SELECTED MODESMACHINE SWING MODES

SIGMA OMEGA ZETA FREQ (rad/sec) (%) (Hz)

1 -4,053 12,991 -29,8 2,060

2 -1,217 11,754 -10,3 1,071

3 -2,520 11,450 -21,5 1,022

4 -0,053 10,022 -0,5 1,595

5 -1,110 9,072 -11,2 1,571

6 -1,285 9,388 -13,6 1,494

7 -1,104 9,359 -12,6 1,490

8 -1,992 9,233 -21,1 1,469

9 -0,900 9,146 -9,0 1,456

10 -2,079 8,942 -22,9 1,407

11 -1,207 8,700 -14,5 1,399

12 -0,550 8,440 -6,6 1,343

13 -1,137 7,062 -14,3 1,251

14 -0,503 7,033 -7,1 1,119

15 -0,383 6,310 -6,1 1,004

16 -0,200 5,718 -4,9 0,910

17 -0,007 4,566 -1,09 0,727 0

0,5

1

1,5

2

Hz14

13

12

11

10

9

8

7

6

5

4

3

2

1

0

-6 -5 -4 -3 -2 -1 0 1



ELECTRIC MACHINES


COMPONENT NAME


2 MILLOA 2x 18 MVA



5 FALALFAL 2X95 MVA


7 PELRA 5X76 MVA

8 NASVENTA AT 18 KV


10 CAREN 2X58.8 MVA


12 BUNCOL 2X240 MVA


14 COANTU 2X160 MVA



17 QUEPAN 500 MVA


18

1716

1

23

89

Augmented state equations:

State equation:

Sparsity-basedstorageandmatrixcomputation

R L P U

From the time domain subprogram of NETOMAC®

QR transformation(Dimentioned maximum

800 dynamic order)

Power methodof implicit

inverse iteration

Transfer functionbased dominant

pole method

Legend:R: Right eigenvector (observability information)L: Left eigenvector (controllability information)P: Participation factorsU: Transfer function residuesU1: Mode activities in unit impulse responseU2: Mode activities in unit step response

Linearmodelof adynamicpowersystem

Eigen-systemsolution

Eigenvalueanalysis&transferfunctionanalysis

U1 U2

Activities ofone mode on

different devices

Activities ofdifferent modeson one device

G(jw):Frequencyresponse

y(t):Unit impulse/step

response

Overviewof

modes

Eigenvalues and associated eigenvectors

System’s working point at t0, t>t0

4

32

1



ELECTRIC MACHINES


COMPONENT NAME


2 MILLOA 2x 18 MVA



5 FALALFAL 2X95 MVA


7 PELRA 5X76 MVA

8 NASVENTA AT 18 KV


10 CAREN 2X58.8 MVA


12 BUNCOL 2X240 MVA


14 COANTU 2X160 MVA



17 QUEPAN 500 MVA


0,19

0,45

0,43

0,15

0,16

0,14

0,37

0,63

1,00

0,63

0,18

0,06

0,05

0,04

0,06

0,06

0,22

0,37

0,56

0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

FREQUENCY RESPONSE OF TRANSFER FUNCTION

Y(s) NASVENTA AT 16 KV ROTOR SPEED

PV

V(s) NASVENTA AT 18 KV

MECHANICAL TORQUE pusMVA

0(s)=

NYQUIST DIAGRAMM

0,91 Hz

MAGNITUDE SCALE : 6.31 (x18-4)

x

0

Axx x

z

Axz bx

Azx Azz bz

u

x xA

1 2 3 4

9 NETOMACeigenvaluecalculation mode

Mode distribution(Eigenvalues)

Phasor-Diagram Bar diagram Nyquist-Diagram12

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

6/95

� Caso histórico

� Hundimiento del Puente Tacoma 1, Washington, EE.UU.

� Hundimiento del Puente Tacoma 2, Washington, EE.UU.

� Hoy

http://www.youtube.com/watch?v=3mclp9QmCGs

http://www.youtube.com/watch?v=j-zczJXSxnw

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

7/95Aspectos teóricos y algunas propiedades delos valores y vectores propios

� En general, los vectores propios de un operador matemático1 lineal T son losvectores no nulos que cuando son transformados por el operador dan lugar a unmúltiplo escalar de sí mismos2: T .v/ D �v. Ese escalar, �, se denomina valorpropio.

� La formulación de su cálculo en el caso habitual de que ese operador locaracterice una matriz,

Dada una matriz A 2 Cn�n, calcular un escalar � y un x ¤ 0 tales queAx D �x:

El escalar � es un valor propio de A y x su correspondiente vector propio.1Transformación lineal u aplicación lineal de un espacio vectorial V en si mismo. Ej. la ecuación de Schrödinger

H E D E E .2No cambian su dirección.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

8/95� Para que exista una solución distinta de la trivial x D 0 el valor propio � deberáser raíz del polinomio característico de grado n asociado a A, es decir,

det.A � �I/ D 0:Lo que es igual a �n � g1�n�1 C g2�n�2 � � � � C .�1/ngn D 0:

� Igual que cualquier matriz tiene asociado un polinomio característico, cualquierpolinomio tiene asociado una matriz compañera. La matriz compañera de unpolinomio mónico p.t/ D c0 C c1t C � � � C cn�1tn�1 C tn es

C .p/ D

2640 0 : : : 0 �c0

1 0 : : : 0 �c1

0 1 : : : 0 �c2::::::: : :

::::::

0 0 : : : 1 �cn�1

375 :

Los valores propios de esta matriz C .p/ son las raíces del polinomio p.t/.

� El polinomio mínimo q.t/ de la matriz A es el polinomio mónico único de gradomínimo tal que q.A/ D 0.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

9/95

� Los vectores propios de A pertenecen al subespacio nulo de Ax � �I ,ker.Ax � �I/, y no están unívocamente determinados: Si v es un vectorpropio, ˛v también lo es.

� Siempre existen n valores propios de A 2 Cn�n, reales o complejos. No siempreexisten n vectores propios.

� La multiplicidad algebraica del valor propio � de A es la multiplicidad de la raízcorrespondiente del polinomio característico asociado a A.

� La multiplicidad geométrica de � es el número de vectores propios linealmenteindependientes que se corresponden con �.

Teorema La multiplicidad geométrica de un valor propio es menor o igual que sumultiplicidad algebraica.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

10/95� Por ejemplo, si A D I , � D 1 es un valor propio con multiplicidad algebraica ygeométrica n. El polinomio característico de A es p.z/ D .z � 1/n y ei 2 Cn,i D 1; : : : ; n, sus vectores propios.

� Si el valor propio � tiene una multiplicidad geométrica menor que la algebraica,se dice defectuoso. Se dice que una matriz es defectuosa si tiene al menos unvalor propio defectuoso. La matriz

A D"2 1 00 2 10 0 2

#

tiene un valor propio de multiplicidad algebraica 3 y multiplicidad geométrica 1.

>> A=[2 1 0;0 2 1;0 0 2];>> [V D]=eig(A)V =

1.0000 -1.0000 1.00000 0.0000 -0.00000 0 0.0000

D =2 0 00 2 00 0 2

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

11/95� Si una matriz A 2 Cn�n no es defectuosa dispone de n vectores propioslinealmente independientes.

� Si V 2 Cn�n tiene como vectores columna los n vectores propios de A yD D diag.�1; : : : ; �n/, entonces Avi D �ivi , i D 1; : : : ; n, es equivalente aAV D V D. Si A no es defectuosa,

A D V DV �1

que es la descomposición en valores propios de A: o A diagonalizada por V .

Definición Una matriz A se dice diagonalizable por semejanza si es semejante a unamatriz diagonal.

Teorema Una matriz A 2 Cn�n es diagonalizable si y sólo si tiene n vectores propioslinealmente independientes.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

12/95

Definición Dos matrices A;B 2 Cn�n se dicen semejantes si existe una matriz inver-tible P tal que A D P�1BP .

Teorema Dos matrices semejantes tienen el mismo polinomio característico y, porconsiguiente, los mismos valores propios.

Definición El espectro �.A/ de A es el conjunto de sus valores propios:�.A/ D f� 2 C W det.A � �I/ D 0g:

Definición El radio espectral, �.A/, de la matriz A es el valor máximo de los módulosde sus valores propios: �.A/ D max.�i2�.A/ j�i j:Es el radio del menor círculo del plano complejo centrado en el origen que contiene todossus valores propios.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

13/95

� Al aplicársele a cualquier vector la transformación que representa A, ese vectortiende3 a orientarse hacia la dirección del vector propio dominante de A.

� Ejemplo Estudiemos la matriz A D � 1;8 0;80;2 1;2

�cuyos valores propios son

�1 D 2 y �2 D 1. El vector propio correspondiente a �1 es�41

�. Si se multiplica

A y sus potencias por el vector x D � �0;51

�el resultado es el de la figura.

k Ak

c1 1

Ak 1 ! 1 c1 ¤ 0

A D!1:8 :8

:2 1:2

"1 D

!4

1

"D!!:5

1

"A

!1 D 2 1

k D 0; : : : ; 8 Ak Ak

k

A D!1:8 :8

:2 1:2

"!!:51

"D!!:11:1

"

A2 D A.A / D!1:8 :8

:2 1:2

"!!:11:1

"D!:7

1:3

"

A3 D A.A2 / D!1:8 :8

:2 1:2

"!:7

1:3

"D!2:3

1:7

"

k

Ak!!:51

" !!:11:1

" !:7

1:3

" !2:3

1:7

" !5:5

2:5

" !11:9

4:1

" !24:7

7:3

" !50:3

13:7

" !101:5

26:5

"

A ; : : : ; A4

1

Ak 1 k !1

1

A4x

A3xA2x

Ax

x

10x1

x2

v1

41

A A2 ; : : : ; A7

.!1/!kAk c1 1

c1 ¤ 0 Ak !1Ak f kg

1

v1Espacio de

3Si ese vector está en la dirección de alguno de los vectores propios de A, se expande o contrae por un factorque determina el correspondiente valor propio

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

14/95

Otros ejemplos

� Ejemplo del apéndice "Definiciones, : : :

� Si A D�1 0

0 2

�, �1 D 1; x1 D

�1

0

�; �2 D 2 y x2 D

�0

1

�:

� Si A D�1;5 0;5

0;5 1;5

�, �1 D 2; x1 D

�1

1

�; �2 D 1 y x2 D

��11

�:

� Si A D�0 1

�1 0�, �1 D i; x1 D

�1

i

�; �2 D �i y x2 D

�i

1

�, donde i D p�1.

http://upload.wikimedia.org/wikipedia/commons/0/06/Eigenvectors.gif

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

15/95

Teorema La suma de los valores propios de A es igual a su traza:

�1 C �2 C � � � C �n DnXiD1

ai i .

Teorema El producto de los valores propios de A es igual a su determinante.

Teorema Los valores propios de una matriz triangular son los coeficientes de su diagonalprincipal.

Teorema Una matriz es singular si y sólo si tiene un valor propio igual a 0.

Teorema Si los valores propios de una matriz A son �i , 1 � i � n, los de A � ˛Ison �i � ˛; 1 � i � n. Sus vectores propios son idénticos.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

16/95

Teorema Los valores propios de las potencias de A son las potencias de los de A; losvectores propios son los mismos.

I Demostración. Si consideramos la definición,Ax D �xI A2x D �Ax D �2xI � � � Anx D �nx

S�1AS D �I S�1ASS�1AS D �2 ) S�1A2S D �2:

Las potencias negativas también:Ax D �xI A�1Ax D �A�1x ) A�1x D ��1x:

Corolario Los valores propios de A�1 son los recíprocos de los de A.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

17/95

� Los valores propios de multiplicidad m > 1 tienen un subespacio propioasociado de dimensión � m. Ese subespacio es invariante4 por lo que:

� Todos los vectores de un subespacio propio son vectores propios.

� Los subespacios propios correspondientes a valores propios distintos sólotienen en común el vector nulo.

4Si para todo vector w 2 W se cumple que f .w/ 2 W .

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

18/95� El problema de calcular los valores y vectores propios es en general unproblema no lineal en los valores propios � y lineal en los vectores x.

� El cálculo de los valores propios por las raíces del polinomio característicono es aconsejable por:

� El trabajo de determinar los coeficientes y raíces del polinomio.

� La sensibilidad a errores de redondeo de los coeficientes del polinomio(recordemos los polinomios de Wilkinson).

Ejemplo Consideremos la matriz�1 �� 1

�, donde � es cualquier número menor

que p�m Kaq:.� Los valores propios exactos de A son 1C � y 1 � �.� El cálculo mediante el polinomio característico haría

det.A � �I/ D �2 � 2�C .1 � �2/ D �2 � 2�C 1Ilas raíces serían (valores propios calculados) 1 y 1. u

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

19/95Valores propios de matrices destacadas

Ortogonales Recordemos que estas matrices son aquellas que tienencomo inversa su traspuesta: QQT D I .� Ejemplo �

0 1

1 0

�;

��1 0

0 �1�;

� p2=2p2=2

�p2=2p2=2�:

� Todos los valores propios de una matriz ortogonal tienen módulo unidad.

Hermíticas Son aquellas matrices iguales a su traspuesta conjugada:A D AH :

Son una generalización de las matrices simétricas al campo complejo.

� Ejemplo La matriz �1 1C i

1 � i 2

�:

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

20/95

� Si A es hermítica, el producto xHAx es un número real.� Los valores propios de una matriz hermítica, en consecuencia, sonnúmeros reales. En efecto

AxD�xI xHAx̃2R

D �xHx D � jjxjj22̃R

� En una matriz hermítica los vectores propios correspondientes a dosvalores propios distintos son ortogonales entre sí. En efecto,

Ax1 D �1x1Ax2 D �2x2

�xH2 A

Hx1 D �1xH2 x1xH2 A

Hx1 D �2xH2 x1

�.�1 � �2/xH2 x1 D 0:

Como los valores propios �1 y �2 son distintos,

xH2 x1 D 0:Si los vectores propios se normalizan, xHx D 1, la matriz de vectorespropios se convierte en una matriz ortogonal.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

21/95

Unitarias Son matrices cuya inversa es su compleja conjugada:UHU D UUH D I :

� Ejemplo La matriz �ip2=2

p2=2

�p2=2 �ip2=2�:

� Las matrices unitarias son una extensión de las matrices ortogonales alcampo complejo. Todos los valores propios tienen módulo unidad.� Una matriz unitaria no modifica ni los ángulos ni las normas:

.Ux/H .Uy/DxHUHUyDxHysi y D x; jjUxjj2 D jjxjj2:

Normales Son las matrices que cumplen que AAH D AHA:

� Ejemplo

241 2 00 1 2

2 0 1

35 ;

�i 0

0 3 � 5i�:

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

22/95

Triangularización de Schur Issai Schur, Alemania, 1875-1941.

Teorema Triangularización de Schur Para cualquierA 2 Cn�n existe una matriz unitariaU y una triangular superior T tales que

UHAU D T :Los valores propios de A son entonces los coeficientes de la diagonal principal de T .

Teorema Para cualquier matriz hermítica A 2 Cn�n existe una unitaria U tal queUHAU D D,

donde D es una matriz diagonal.

1. Los valores propios de A son números reales.

2. Se pueden obtener vectores propios de A que sean ortonormales.

Corolario Si A 2 Rn�n es simétrica, existe una matriz ortogonal Q y una diagonal Dtales queQTAQ D D.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

23/95Teorema Los valores propios de una matriz hermítica definida positiva son todos po-sitivos.Recíprocamente, si todos los valores propios de una matriz son positivos, debe ser definidapositiva.

Teorema Forma canónica de Jordan Para una matriz A 2 Cn�n existe una matriz Tregular tal que

T �1AT D J D

2664J1 � 0

: : :0 �

Jn

3775 ;

donde

Ji D

2664�i 1�i 1 0� �� 0 � 1

�i

3775

es una matriz de Jordan y los �i son los valores propios de A.

Marie Ennemond Camille Jordan, Francia, 1838-1922.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

24/95

� Tabla que resume las posibles transformaciones por semejanza.

A T B D T �1ATValores propios distintos Regular DiagonalSimétrica real Ortogonal Diagonal realHermítica compleja Unitaria Diagonal realNormal Unitaria DiagonalReal cualquiera Ortogonal Triangular en bloques (real)Cualquiera Unitaria Triangular superior (Schur)Cualquiera Regular Casi diagonal (Jordan)

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

25/95

Localización de valores propios

� Si no se necesita calcular el valor numérico exacto de los valores propios, sinoconocer grosso modo dónde se encuentran en el plano complejo, existen variasformas de hacerlo.

� La más simple surge de tomar normas en la expresión Av D �v:j�jjjvjj D jj�vjj D jjAvjj � jjAjjjjvjj ) j�j � jjAjj;

para cualquier norma matricial inducida por una norma vectorial. Porconsiguiente:

� Los valores propios de una matriz se localizan en el plano complejo, dentrodel circulo centrado en el origen de radio jjAjj.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

26/95

Semyon Aranovich Ger̆sgorin,Rusia, 1901-1933.

Teorema Ger̆sgorin Los valores propios de una matriz A 2 Cn�n se encuentran en launión de los n discos de Gershgorin, cada uno de los cuales está centrado en akk, k D1; : : : ; n, y tiene de radio

rk DnX

jD1

j¤k

jakj j

I Demostración. Sea � un valor propio de A y x su vector propio asociado. De Ax D �x y .�I �A/x D 0 se tiene que

.� � akk/xk DnX

j D1

j¤k

akjxj ; k D 1; : : : ; n;

donde xk es el componente k-ésimo del vector x.Si xi es el coeficiente de x más grande en valor absoluto, como jxj j=jxi j � 1 para j ¤ i , se tiene que

j� � ai i j �nX

j D1

j¤i

jaij j jxj jjxi j�

nXj D1

j¤i

jaij j:

Luego � está contenido en el disco f� W j� � ai i j � rig.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

27/95

� El siguiente programa de Matlab calcula los círculos o discos de Gershgorin ylos dibuja.

function C = Gershgorin(A)%% Se dibujan los círculos de Gershgorin de la matriz A.[m n] = size(A);d = diag(A); cx = real(d); cy = imag(d);B = A - diag(d);r = sum(abs(B’)); % Suma filas de A sin diagonalC = [cx cy r(:)];t = 0:pi/100:2*pi; c = cos(t); s = sin(t);[v d] = eig(A); % eig calcula los valores propios de Ad = diag(d); % En d valores propiosu1 = real(d); v1 = imag(d);hold on, grid on, axis equalxlabel(’Re’), ylabel(’Im’)h1_line = plot(u1,v1,’or’);set(h1_line,’LineWidth’,1.5)for i=1:n % Se dibujan los círculos de Gershgorin

x = zeros(1,length(t)); y = zeros(1,length(t));x = cx(i)+r(i)*c; y = cy(i)+r(i)*s;h2_line = plot(x,y);set(h2_line,’LineWidth’,1.2)

endhold offtitle(’Círculos de Gershgorin y valores propios de la matriz’)

end

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

28/95� Ejemplo Calcular los discos de Gershgorin de la matriz

A D"1 2 3

3 4 9

1 1 1

#:

Los radios de los discos son r1 D 5, r2 D 12 y r3 D 2.

� Los valores propios son: 7;3067; �0;6533C 0;3473i y �0;6533 � 0;3473i .Con el programa anterior, se obtiene lo siguiente.

-10 -5 0 5 10 15

Re

-10

-5

0

5

10

Im

Círculos de Gerschgorin y valores propios de la matriz

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

29/95

� Los gráficos de los discos de Gershgorin de otras matrices curiosas se puedenver en esta otra gráfica.

−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))

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

30/95

Índice� Introducción teórica


� Obtención numérica de los valores y vectores propios

�Método de Jacobi�Método de la iteración de potencia�Método de la iteración inversa� Iteración mediante cociente de Rayleigh� Deflación� Iteración simultánea� Iteración QR� Subespacios de Krylov


h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

31/95

Obtención numérica

Método de Jacobi Carl Gustav Jacobi, Alemania(Prusia), 1804-1851.

� Es un método formulado en 1846 para el cálculo de los valores y vectorespropios de una matriz simétrica o compleja hermítica.

� Utiliza transformaciones por semejanza basadas en rotaciones, idénticas a las deGivens, para hacer cero pares de elementos simétricamente dispuestos respectoa la diagonal principal.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

32/95

� Partiendo de A0 D A, cada iteración conforma una transformación

AkC1 D J Tk AkJk;

donde cada matriz Jk Dhc s�s c

ise calcula de tal manera que

hc �ss c

i happ apq

apq aqq

i hc s

�s c

iDh

c2app � 2csapq C s2aqq apq.c2 � s2/C cs.app � aqq/

apq.c2 � s2/C cs.app � aqq/ c2aqq C 2csapq C s2app

i

sea diagonal.

� Para lograrlo, apq.c2 � s2/C cs.app � aqq/ ha de ser cero. Haciendo

� D aqq � app2apq

y t D s=c; tangente del ángulo de rotación

se obtiene la ecuación de segundo grado

t2 C 2� t � 1 D 0:

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

33/95� De las dos posibles raíces,

t D �� ˙p1C �2;

se escoge la más pequeña para que j� j � �=4. Luego se obtienenc D 1=p1C t2 y s D c � t .

� En Matlab:

function J=Jac_Rot(A,b,d)% Cálculo de la rotación de Jacobi para anular un coef. de A de coordenadas (b,d)if A(b,d)~=0

tau=(A(d,d)-A(b,b))/2/A(b,d);if tau>=0

t=1/(tau+sqrt(1+tau^2));else t=-1/(-tau+sqrt(1+tau^2)); endc=1/sqrt(1+t^2);s=c*t;

elsec=1; s=0;

endJ=[c s; -s c]; % Igual que Givens

end

� Mediante unos “barridos” que apliquen sistemáticamente estas transformacionesa todos los coeficientes que no estén en la diagonal principal de la matriz quetengan un valor mayor que una tolerancia se conseguirá ir convirtiendo la matrizen una diagonal.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

34/95

� La convergencia del proceso es cuadrática.

� El proceso termina cuando off .A/ Dvuuuut

nXiD1

nXjD1j¤i

a2ij > tol � kAkF .

� Ejemplo Sea A0 Dh1 0 20 2 12 1 1

i. Apliquémosle el método de Jacobi.

� Anulemos para empezar los coeficientes .1; 3/ y .3; 1/. Con ese fin, definamosla rotación

J0 D"0;707 0 �0;7070 1 0

0;707 0 0;707

#

y hagamos

A1 D J T0 A0J0 D"

3 0;707 0

0;707 2 0;707

0 0;707 �1

#:

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

35/95

� A continuación, anulemos .1; 2/ y .2; 1/ mediante la rotación

J1 D"0;888 �0;460 00;460 0;888 0

0 0 1

#

y hagamos

A2 D J T1 A1J1 D"3;366 0 0;325

0 1;634 0;628

0;325 0;628 �1

#:

� Luego anulamos el .3; 2/ y el .2; 3/ usando la rotación

J2 D"1 0 0

0 0;975 �0;2260 0;226 0;975

#

y haciendo

A3 D J T2 A2J2 D"3;366 0;0735 0;317

0;0735 1;780 0

0;317 0 �1;145

#:

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

36/95

� Comenzando un nuevo “barrido”, hagamos cero los coeficientes .1; 3/ y .3; 1/.Usaremos la rotación

J3 D"0;998 0 �0;0700 1 0

0;070 0 0;998

#

y luego

A4 D J T3 A3J3 D"3;388 0;0733 0

0;0733 1;780 0;0051

0 0;0051 �1;167

#:

� El proceso continuaría hasta llegar a conseguir una aproximación a los valorespropios deseados. u

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

37/95

� El programa para poder calcular una rotación de Jacobi 2� 2 y aplicarla luego ala matriz original completa, pre y post multiplicándola, es este.

function J=jacrot(A,i,j)% Transf. de Jacobi del coeficiente (i,j) y (j,i) de An=length(A);J1=Jac_Rot(A,i,j); J=eye(n); % Calcula qué rotación 2x2 elemental aplicarJ([i j],[i j])=J1([1 2],[1 2]); % Se adapta a la propia A

end

function J=Jac_Rot(A,b,d)% Cálculo de rotación de Jacobi 2x2 en la matriz A.if A(b,d)~=0

tau=(A(d,d)-A(b,b))/2/A(b,d);if tau>=0

t=1/(tau+sqrt(1+tau^2));else t=-1/(-tau+sqrt(1+tau^2)); endc=1/sqrt(1+t^2);s=c*t;

elsec=1; s=0;

endJ=[c s; -s c]; % Igual que Givens

end

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

38/95Ejemplo con Matlab

>> A=rand(4);>> A=A+A’A =

1.7818 1.1086 1.3615 0.33521.1086 0.5150 1.0842 0.50541.3615 1.0842 1.8585 0.96600.3352 0.5054 0.9660 0.9466

>> % Anulemos el coeficiente (1,2)>> J=jacrot(A,1,2); A=J’*A*JA =

2.4252 0.0000 1.7218 0.54360.0000 -0.1284 0.2544 0.26881.7218 0.2544 1.8585 0.96600.5436 0.2688 0.9660 0.9466

>> % Ahora el (1,3)>> J=jacrot(A,1,3); A=J’*A*JA =

3.8868 0.1646 0.0000 1.03960.1646 -0.1284 0.1939 0.26880.0000 0.1939 0.3969 0.38471.0396 0.2688 0.3847 0.9466

>> % El (1,2) se ha hecho distinto de cero; el (1,4)>> J=jacrot(A,1,4); A=J’*A*JA =

4.2172 0.2383 0.1165 00.2383 -0.1284 0.1939 0.20630.1165 0.1939 0.3969 0.3666

-0.0000 0.2063 0.3666 0.6161

>> % Ahora el (2,3)>> J=jacrot(A,2,3); A=J’*A*JA =

4.2172 0.1899 0.1852 00.1899 -0.1922 -0.0000 0.08140.1852 -0.0000 0.4607 0.4127

-0.0000 0.0814 0.4127 0.6161>> % El (2,4)>> J=jacrot(A,2,4); A=J’*A*JA =

4.2172 0.1890 0.1852 0.01880.1890 -0.2003 -0.0409 -0.00000.1852 -0.0409 0.4607 0.41070.0188 0.0000 0.4107 0.6243

>> % El (3,4)>> J=jacrot(A,3,4); A=J’*A*JA =

4.2172 0.1890 0.1312 0.13200.1890 -0.2003 -0.0316 -0.02600.1312 -0.0316 0.1237 0.00000.1320 -0.0260 -0.0000 0.9612

>> % Después de un barrido el valor de off(A) se ha reducido>> off(A)ans =

0.2845>> % Desde>> of1of1 =

3.1996>> % Otro barrido>> J=jacrot(A,1,2); A=J’*A*JA =

4.3202 -0.0000 0.1580 0.0270-0.0000 -1.3369 -0.0502 0.02300.1580 -0.0502 -0.5132 00.0270 0.0230 -0.0000 -0.7836

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

39/95

>> J=jacrot(A,1,3); A=J’*A*JA =

4.3254 -0.0016 -0.0000 0.0270-0.0016 -1.3369 -0.0501 0.0230-0.0000 -0.0501 -0.5183 -0.00090.0270 0.0230 -0.0009 -0.7836


4.3255 -0.0015 -0.0000 -0.0000-0.0015 -1.3369 -0.0501 0.0230-0.0000 -0.0501 -0.5183 -0.00090.0000 0.0230 -0.0009 -0.7838


4.3255 -0.0015 0.0001 -0.0000-0.0015 -1.3400 0.0000 0.02290.0001 -0.0000 -0.5153 -0.00230.0000 0.0229 -0.0023 -0.7838


4.3255 -0.0015 0.0001 -0.0001-0.0015 -1.3409 0.0001 00.0001 0.0001 -0.5153 -0.0023

-0.0001 -0.0000 -0.0023 -0.7828>> J=jacrot(A,3,4); A=J’*A*JA =

4.3255 -0.0015 0.0001 -0.0001-0.0015 -1.3409 0.0001 0.00000.0001 0.0001 -0.5152 0

-0.0001 0.0000 -0.0000 -0.7829>> eig(A) % Casi ha convergido en dos barridosans =

4.3255-1.3409-0.5152-0.7829

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

40/95

� Programa completo de Matlab para realizar el proceso.

function [V D it]=Jacobi_val_12_2(A)% Cálculo por Jacobi de valores y vectores propios de una MATRIZ SIMÉTRICA Atol=sqrt(eps)*norm(A,’fro’); D=A; n=length(A); V=eye(n);[m1 p]=max(triu(abs(D),1)); % En (p,q) elemento mayor valor no en diagonal[~, q]=max(m1); % Posición fila máximo valor no cero en L(A)p=p(q); it=0; % Posición columna máximo anteriorwhile off(D)>tol % Procesos iterativo; necesita rutina off

J=Jac_Rot(D,p,q); % Se hacen cero Dpq y Dqp (p debe ser < q)D([p q],:)=J’*D([p q],:);D(:,[p q])=D(:,[p q])*J;V(:,[p q])=V(:,[p q])*J;[m1 p]=max(triu(abs(D),1));[~, q]=max(m1);p=p(q);it=it+1;

end[D I]=sort(diag(D)); V=V(:,I);

end

function a=off(A)% Calcula off de la matriz cuadrada A: raiz cuadrada de la suma% de los cuadrados de los coeficientes de A no en la% diagonal principal; también sqrt(sum(sum(triu(a.^2,1)))).n=length(A); a=0;for k=1:n-1

a=a+sum(A(k,k+1:n).^2);enda=sqrt(a);

end

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

41/95� Para el ejemplo hecho a mano, se obtiene este resultado.

>> A=[1 0 2;0 2 1;2 1 1];>> [v d it]=Jacobi_val_12_2(A)v =

0.6611 -0.4973 0.56180.2261 0.8460 0.4828

-0.7154 -0.1922 0.6718d =

-1.16421.77293.3914

it =8

>> [V D]=eig(A)V =

-0.6611 -0.4973 -0.5618-0.2261 0.8460 -0.48280.7154 -0.1922 -0.6718

D =-1.1642 0 0

0 1.7729 00 0 3.3914

La aproximación que hicimos iterando unpar de “barridos” era bastante buena.

Para la matriz de la sesión interactiva anterior.

>> [v d it]=Jacobi_val_12_2(A)v =

-0.3673 0.3703 -0.6272 0.57850.9032 0.1289 -0.0831 0.4009

-0.1590 -0.7022 0.2688 0.6399-0.1549 0.5944 0.7263 0.3086

d =-0.21340.12380.95694.2346

it =16

>> A*v-v*diag(d)ans =

1.0e-010 *-0.0096 0.3780 0.0061 0.2292-0.0034 0.2318 0.0042 0.08120.0183 0.4117 0.0067 -0.4444

-0.0155 0.2006 0.0032 0.3862

>> [v d]=eig(A)v =

0.3673 -0.3703 0.6272 0.5785-0.9032 -0.1289 0.0831 0.40090.1590 0.7022 -0.2688 0.63990.1549 -0.5944 -0.7263 0.3086

d =-0.2134 0 0 0

0 0.1238 0 00 0 0.9569 00 0 0 4.2346

>> A*v-v*dans =

1.0e-014 *-0.0222 -0.0444 -0.0333 -0.0444-0.0056 0.0097 -0.0305 -0.0444-0.0479 0.0180 -0.0444 -0.1332-0.0069 -0.0083 -0.0111 0

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

42/95Método de la iteración de la potencia

� Su objetivo es calcular el valor propio dominante y su vector propio asociado.

� Se basa en que al aplicarle a cualquier vector la transformación que representauna matriz A, ese vector tiende a orientarse hacia la dirección del vector propiodominante de A. Recordad.

� Partiendo de un x0 de módulo unidad, opera mediante una iteración de puntofijo de fórmula de recurrencia

yk�1 D Axk�1; donde xk D yk�1jjyk�1jj1

:

La magnitud jjyk�1jj1 converge al valor propio dominante, �1, y el vector xi lohace al vector propio dominante, v1.

� Su convergencia está ligada a j�2=�1j : a menor valor mejor convergencia.

http://upload.wikimedia.org/wikipedia/commons/0/06/Eigenvectors.gif

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

43/95� Ejemplo Partiendo de xT0 D Œ0; 1� calculemos el valor propio dominante de�1;5 0;5

0;5 1;5

�:

Utilicemos una pequeña sesión de Matlab como esta

>> x=[0;1];>> A=[1.5 0.5;0.5 1.5];>> for i=1:10v=A*xm=max(abs(v))x=v/mend

Los resultados son estos.

k xTk

jjxkjj10 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,99229 0,996 1,0 1,996110 0,998 1,0 1,9981

>> x=[0;1];A=[1.5 0.5;0.5 1.5];for i=1:10v=A*x, m=max(abs(v)), x=v/mendv =

0.50001.5000

m =1.5000

x =0.33331.0000

v =1.00001.6667

m =1.6667

x =0.60001.0000...

v =1.99421.9981

m =1.9981

x =0.99801.0000

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

44/95

� El comportamiento de las iteraciones es el de la 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

...................

...................

...................

...................

...................

...................

...................

...................

...................

...................

...................

...................

...................

...................

...................

...................

...................

...................

...................

...........................

..........................

.................................................................................................................................................................................................................................................................................................................................................................................................................................................

..........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

..............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

......................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

v 2 v 1

x 0 x 1 x 2 x 3 x 4.............................................................................. ....................................................

..........................

..............................

..............................

..............................

.............................

..............................

..............................

.............................

..............................

..............................

................................

........................................................................................................

........................................................................................................

............................................................................................

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 largereigenvalue, 2) to dominate, and hence sequenceof vectors converges to that eigenvector

35

� El punto inicial

x0 D�0

1

�D 1

�1

1

�C 1

��11

�

es una combinación lineal de los dos vectores propios v1 y v2.

� La multiplicación sucesiva por A causa que el coeficiente en el primer vectorpropio sea el que domine, por lo que la sucesión converge a ese vector propio.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

45/95

� El método puede fallar por diversas razones:

1. Porque haya más de un valor propio con el mismo módulo, en cuyo caso lasiteraciones puede que converjan a una combinación lineal de loscorrespondientes vectores propios.� Este caso es bastante habitual pues esos dos valores propios pueden serun par complejo conjugado.

2. El vector de partida puede que tenga coeficiente cero en el valor propiodominante.� El error de redondeo en la práctica puede que introduzca un pequeñovalor, por lo que este peligro rara vez ocurre.

3. Para una matriz real y un punto de partida también real, puede que nuncase converja a un vector complejo.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

46/95

� Un programa de Matlab para el método de la potencia.

function [lambda,V,cnt]= potencia(A,x,tol,max1)% Método de la potencia para la obtención de un valor% y un vector propios de Aif nargin<4 max1=100; end, if nargin<3 tol=eps; endif nargin<2 n=length(A); x=rand(n,1); endlambda=0;cnt=0;err=1;while cnt<=max1 & err>tol

y=A*x;c1=norm(y,inf);y=y/c1;dc=abs(lambda-c1); dv=norm(x-y); err=max(dc,dv);x=y; lambda=c1;cnt=cnt+1;

endV=x/norm(x);

end

>> [l,v,cnt]=potencia(b,[0;1])l =

2.00000000000000v =

0.707106781186550.70710678118655

cnt =53

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

47/95

Mejora del método: desplazamiento

� Mediante un desplazamiento � ,

A � �I ;es posible hacer que ˇ̌

ˇ̌�2 � ��1 � �

ˇ̌ˇ̌�

ˇ̌ˇ̌�2�1

ˇ̌ˇ̌ ;

y que, por lo tanto, la velocidad de convergencia aumente.La solución del problema original resultará de añadir � al valor obtenido.

� En el ejemplo que estamos utilizando, si se hace � D 1, la relación anterior sehace cero y el método converge en una iteración.(Desafortunadamente, no siempre se puede escoger un desplazamiento tanbueno.)

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

48/95

Método de la iteración inversa

� Si en vez del valor propio de mayor magnitud, se necesita el más pequeño, sepuede hacer uso de la propiedad de que los valores propios de A�1 son losrecíprocos de A.

� El esquema iterativo sería el que sigue.

Dado un punto de partida x0

for k D 1, 2, : : :Resolver Ayk D xk�1

xk D yk

jjykjj1end

Para resolver el sistema se factorizaría A una sola vez.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

49/95� Aplicando el método de la iteración inversa a la matrizh

1;5 0;50;5 1;5

i;

se obtienen los resultados de la tabla.

k xTk

jjykjj10 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,9716 -0,969 1,0 0,985

>> x=[0;1];A=[1.5 0.5;0.5 1.5];for i=1:6v=A\x, m=max(abs(v)), x=v/mendv =

-0.25000.7500

m =0.7500

x =-0.33331.0000

.

.v =

-0.83330.9444

m =0.9444

x =-0.88241.0000

v =-0.91180.9706

m =0.9706

x =-0.93941.0000

v =-0.95450.9848

m =0.9848

x =-0.96921.0000

Converge al valor propio 1 y vector propio Œ�1; 1�T .

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

50/95

� En Matlab la iteración sería así.

function [lambda,V,cnt]= ItInversa_2(A,x,tol,max1)% Método de la potencia inversa para la obtención% de un valor y vector propio de Aif nargin<4 max1=110; end, if nargin<3 tol=eps; endif nargin<2 n=length(A); x=rand(n,1); endlambda=0;cnt=0;err=1;[l,u,p]=lu(A);while cnt<=max1 & err>tol

z=l\(p*x);y=u\z;c1=norm(y,inf);y=y/c1;dc=abs(lambda-c1); dv=norm(x-y); err=max(dc,dv);x=y; lambda=c1;cnt=cnt+1;

endV=x/norm(x);

end

>> A=[1.5 0.5;0.5 1.5];>> [lambda,V,cnt]=ItInversa(A,[0;1])lambda =

1.0000V =

-0.70710.7071

cnt =55

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

51/95

Mejora del método: desplazamiento

� El desplazamiento es particularmente útil en el caso de la iteración inversa.

� Si � es el valor propio de A más próximo a � , el valor propio de menormagnitud de A � �I será � � � .� Con una elección apropiada de � se puede calcular cualquier valor propio deA que esté próximo a esa � .

� Si el desplazamiento está próximo a un valor propio, la convergencia es muyrápida.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

52/95Iteración mediante cociente de Rayleigh

John William Strutt, Lord Rayleigh, Reino Unido, 1842-1919.

Definición El cociente de Rayleigh de un vector x 2 Rn es el escalar r.x/ D xTAxxTx .

� Dada una matriz A 2 Rn�n y uno de sus vectores propios, x, la mejorestimación del correspondiente valor propio � se puede considerar un problemade mínimos cuadrados n � 1 como este: x� � Ax.

� De sus ecuaciones normales, xTx� D xTAx, la solución que se obtiene es

� D xTAx

xTx:

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

53/95

� El cociente de Rayleigh puede utilizarse como desplazamiento para acelerar laconvergencia de los métodos iterativos que hemos visto. El algoritmo de laiteración inversa quedaría así.

Dado un punto de partida x0

for k D 1, 2, : : :

�k DxT

k�1Axk�1

xTk�1xk�1

Resolver .A � �kI/yk D xk�1

xk D yk

jjykjj2end

� El versión del cociente de Rayleigh para vectores complejos es xHAxxHx .

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

54/95Ejemplo (continuación)

� El método de la iteración de potencia con cociente de Rayleigh aplicado paso apaso al problema que estudiamos:

k xTk

jjykjj1 xTkAxk=x

Tkxk

0 0,000 1,01 0,333 1,0 0,150 1,5002 0,600 1,0 1,667 1,8003 0,778 1,0 1,800 1,9414 0,882 1,0 1,889 1,9855 0,939 1,0 1,941 1,9966 0,969 1,0 1,970 1,999

Partiendo de un puntoaleatorio:

k xTk

�k

0 0,807 0,397 1,8961 0,924 1,000 1,9982 1,000 1,000 2,000

� En Matlab:function [lambda,V,cnt]= ItInvRayleigh_2(A,x,max1)% Método de la iteración inversa con cociente de Rayleighif nargin<2, n=length(A); max1=10; x=ones(n,1); endlambda=0; cnt=0; err=1; n=length(A);if norm(x)>1 x=x/norm(x); endtol=n*norm(A,1)*eps;sigma=x’*A*x;while err>tol

y=(A-sigma*eye(n))\x;x=y/norm(y);sigma=x’*A*x;err=norm(A*x-sigma*x,1);cnt=cnt+1;

endlambda=sigma;V=x;

end

>> A=[1.5 0.5;0.5 1.5];>> [lambda,V,cnt]=ItInvRayleigh_2(A,[0.5;0.55])lambda =

2.0000V =

0.70710.7071

cnt =3

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

55/95

Deflación

� Idea: Calculados un valor y un vector propios, obtener otros por deflación: Comocuando una vez conocida una de las raíces, x1, de un polinomio de grado n éstese divide por x � x1 obteniéndose otro de grado n � 1.

� Si x es el vector propio asociado al valor propio dominante de A, �1, y H esuna matriz de Householder, tal que Hx D ˛e1, la transformación de semejanzaque define consigue transformar A así

A1 D HAH �1 D��1 b

T

0 A2

�;

donde A2 es una matriz de orden n � 1 cuyos valores propios son �2; : : : ; �n,los restantes de A.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

56/95� Luego, trabajando con A2 y calculado �2, si y2 es un vector propio asociado, elvector

x2 D H �1�˛

y2

�; donde ˛ D bTy2

�2 � �1 ;

es el vector propio correspondiente a �2 en la matriz original A, supuesto�1 ¤ �2.Este método funciona bien para calcular algunos valores y vectores propios.

� En Matlab:

function [l2 v2 B] = defl_1(A, v1)% B resulta de A por deflación de vec. propio v1.% Calcula el valor propio l2 y vec. propio v2.n = length(A);v1 = Housv(v1);C = Houspre(v1,A);B = zeros(n,n);for i=1:n

B(:,i)=Housmvp(v1,C(i,:));endl1 = B(1,1);b = B(1,2:n);B = B(2:n,2:n);[l2 y] = ItInvRayleigh_2(B);if l1~=l2

a = b*y/(l2-l1);v2 = Housmvp(v1,[a;y]);

elsev2 = v1;

endend

+

function u = Housv(x)% Transformación de Householder del vector x.m = max(abs(x));u = x/m;if u(1) == 0, su = 1; else su = sign(u(1)); endu(1) = u(1)+su*norm(u);u = u/norm(u);u = u(:);

end

function P = Houspre(u, A)% Producto P = H*A, donde H is una transformación de Householder% definida por el vector u.n = length(A);v = u/norm(u); v = v(:);P = zeros(n,n);for j=1:n

aj = A(:,j);P(:,j)=aj-2*(v’*aj)*v;

endend

function p = Housmvp(u, x)% Producto p = H*x, donde H es la transformación de Householder% definida por u.u = u(:); x = x(:);v = u/norm(u);p = x - 2*(v’*x)*v;

end

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

57/95

� Utilicémoslo:

>> A=ones(5)+diag(ones(5,1)) % Generamos una matriz dadaA =

2 1 1 1 11 2 1 1 11 1 2 1 11 1 1 2 11 1 1 1 2

>> [lambda,V]= ItInvRayleigh_2(A) % Cal. valor y vector propio dominanteslambda =

6V =

0.447213595499900.447213595500020.447213595499820.447213595500010.44721359550003

>> [l2,v2]=defl_1(A,V) % Defl para obtener otro par val. Al2 =

1v2 =

-0.894427190999920.223606797749980.223606797749980.223606797749980.22360679774998

>> [norm(A*V-lambda*V);norm(A*v2-l2*v2)] % Comprobar resultadosans =

1.0e-015 *0.44410.6497

>> format short>> [l,v]=eig(A) % Comprobar con rutina Matlab eigl =

0.8333 -0.1667 -0.1667 0.2236 0.4472-0.1667 0.8333 -0.1667 0.2236 0.4472-0.1667 -0.1667 0.8333 0.2236 0.4472-0.5000 -0.5000 -0.5000 0.2236 0.4472

0 0 0 -0.8944 0.4472v =

1 0 0 0 00 1 0 0 00 0 1 0 00 0 0 1 00 0 0 0 6

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

58/95

Iteración simultánea o de subespacio

� Para obtener varios valores/vectores propios, apliquemos la iteración de lapotencia a los p vectores linealmente independientes que forman X 0; es decir:

X0 D matriz n � p de rango pfor k D 1, 2, : : :

Xk D AXk�1

end

� La Im��Akx1 Akx2 : : : Akxp

��converge al subespacio invariante de los

vectores propios de A correspondientes a sus p mayores valores propios:j�1j > � � � j�pj > j�pC1j � j�pC2j:

� La velocidad de convergencia es O.�pC1=�p/.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

59/95

� Para optimizar prestaciones y conseguir una buena ortogonalidad se usa lafactorización QR de Xk, ortonormalizando así las columnas de Xk. Seobtendría una Q como base de Im.Xk/.

X0 D matriz n � p de rango pfor k D 1, 2, : : :

QkRk D Xk�1

Xk D AQk

end

� Las iteraciones convergen a una matriz triangular, si sólo hay valores propiosreales, o a una triangular en bloques 2�2 en la diagonal principal cuando hayavalores propios complejos conjugados.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

60/95

Sesión en Matlab para matriz simétrica

>> A=randn(5); A=A*A’A =

2.8486 -2.5688 0.1741 3.5081 -0.1959-2.5688 2.8789 -0.3177 -4.0552 -2.20330.1741 -0.3177 2.3957 1.4227 -2.34863.5081 -4.0552 1.4227 6.2012 2.7463

-0.1959 -2.2033 -2.3486 2.7463 19.4886>> A0=A;>> % Hagamos ahora 10 iteraciones de la iteración ortogonal>> for i=1:10, [Q R]=qr(A); A=R*Q; end>> AA =

20.8010 -0.0997 0.0000 0.0000 0.0000-0.0997 10.6605 0.0000 0.0000 0.00000.0000 0.0000 2.2265 0.0000 0.00000.0000 -0.0000 0.0000 0.1085 0.0000

-0.0000 -0.0000 0.0000 0.0000 0.0165

>> % Otras 5 iteraciones más>> for i=1:5, [Q R]=qr(A); A=R*Q; end>> AA =

20.8020 -0.0035 0.0000 0.0000 0.0000-0.0035 10.6595 0.0000 0.0000 0.00000.0000 0.0000 2.2265 0.0000 0.00000.0000 -0.0000 0.0000 0.1085 0.0000

-0.0000 -0.0000 0.0000 0.0000 0.0165>> % Mejora; hagamos 10 más>> for i=1:10, [Q R]=qr(A); A=R*Q; end>> AA =

20.8020 -0.0000 0.0000 0.0000 0.0000-0.0000 10.6595 -0.0000 0.0000 0.00000.0000 0.0000 2.2265 0.0000 0.00000.0000 -0.0000 0.0000 0.1085 -0.0000

-0.0000 -0.0000 0.0000 0.0000 0.0165>> % Comparemos todos con los de la matriz original>> eig(A0)ans =

0.01650.10852.2265

10.659520.8020

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

61/95� IterSimul obtiene los r valores propios máximos de A simétrica.

function [i r1]=IterSimul(A,r)% Máximos valores propios de A (simétrica); itera. simultánea% ortogonaln=length(A); if nargin<2, r=5; endtol=sqrt(eps); B=A; i=0; itmax=400;Q=eye(n,r); R=eye(r); vprn=1; err=1;while i<itmax && err>tol

vpr=vprn;Z=A*Q;[Q,R]=qr(Z,0); % QR reducida de n x rvprn=min(diag(R));i=i+1;err=abs((vprn-vpr)/vprn);

endformat longr1=diag(R); % fprintf(’%i Valores propios máximos:\n’,r);disp(’Valores calculados con eig()’);disp(-sort(eig(-B)));

end

>> A=rand(20); A=A*A’;>> [i r]=IterSimul(A,6)Valores calculados con eig()

1.0e+002 *1.0062942304134850.0528048946290750.0395165837813990.0321918014629250.0311573239654770.0268066648060720.0225976063483680.0198277556760600.0136855894058130.0122172635607200.0097913358279200.0050481878099200.0042821453421960.0034600643129450.0024365877675340.0017132724895060.0011681376916970.0006056142545680.0002387296193830.000012007660353

i =44

r =1.0e+002 *1.0062942304134840.0528048946290540.0395165836950560.0320536449889880.0312916161595570.026806665421155

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

62/95Iteración QR� Propuesta por John G.F. Francis y Vera Kublanovskaya.

474 G. GOLUB AND F. UHLIG

family until his death. At first, Kantorovich’s group developed analytic computational tools in Prorabfor algebraic and trigonometric polynomials, for integer arithmetic and series, etc. When Vera joined,her task was to select and classify matrix operations that are useful in numerical linear algebra. Linearalgebra subroutines were included in Prorab much later. This experience brought Vera close to numericalalgebra and computation. In 1972 she obtained her secondary doctorate (Habilitation). More extendedbiographies of Vera’s life, achievements and long and productive career are available in Golub et al.(1990) and Konkova et al. (2003), for example.

Vera Kublanovskaya in August 2008

In the Russian literature the QR algorithm was initially called the method of one-sided rotations. VeraKublanovskaya started to develop her version of the QR algorithm in 1958 after reading Rutishauser’sLR algorithm paper (Rutishauser, 1958). She represented a matrix A = L · Q as the product of a lowertriangular matrix L and an orthogonal matrix Q that she suggested to compute as the product ofelementary rotations or reflections. Her eigenvalue algorithm factors A = A1 = L1 · Q1, reverseorder multiplies A2 = Q1 · L1 and then factors A2 again as A2 = L2 · Q2, etc. In 1959 she performednumerical experiments with her LQ decomposition-based algorithm on an electromechanic ‘Mercedes’calculator in low dimensions by hand since linear algebra computer codes had not been developed yetin Prorab. Vera’s hand computations indicated that her explicit factorization—reverse-order multiplyalgorithm— is convergent. However, D. K. Faddeev feared that the obtained results may only have beenaccidental. Vera’s QR-like algorithm was briefly mentioned in 1960 in the first edition of a monograph

at UniversitÃ

di Bologna - S

istema B

ibliotecario d'Ateneo on M

arch 30, 2010 http://im

ajna.oxfordjournals.orgD

ownloaded from

John G.F. Francis, Reino Unido 1934 y VeraKublanovskaya, Rusia 1920-2012.

� Generalizando la iteración simultánea (ortogonal) se pueden calcular todos losvalores propios de A, así como los correspondientes vectores propios.

A0 D AIU 0 D Ifor k D 1, 2, : : :

Qk�1Rk�1 D Ak�1, obtener factorización QRAk D Rk�1Qk�1; U k D U k�1Qk�1

end

Las Ak convergerán a una matriz triangular, si todos los valores propios sonreales, o con bloques 2�2 en la diagonal, si hay valores propios complejos.U k convergerá a los vectores propios.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

63/95

� Las matrices Ak son ortogonalmente semejantes a las anteriores del proceso y aA:

A1 DR0Q0 D QT0A0Q0 pues R0 D QT

0A0

A2 DR1Q1 D QT1A1Q1 D QT

1

�QT0A0Q0

�Q1 D

.Q0Q1/T A0 .Q0Q1/

Es decir, todas las Ak tendrán los valores propios de A D A0.

� Las columnas de Qk forman una base ortonormal del subespacio Im.Ak/.

� Si A es simétrica, las iteraciones conservan la simetría y las Ak convergerán auna matriz triangular y simétrica: diagonal.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

64/95� Trabajemos un poco “a mano” con el algoritmo.

D = diag([4 3 2 1]);rand(’seed’,0); format short eS=rand(4); S = (S - .5)*2; % Se perturba un pocoA = S*D/S % A_0 = A = S*D*S^{-1}for i=1:6

[Q R] = qr(A); A = R*Q % Iteración QRend

A =4.1475e+00 -7.7246e-01 -7.3819e-01 -4.1172e+00

-4.9214e-03 3.2731e+00 -1.8990e-01 1.9440e+006.2706e-01 -1.9699e-01 2.2190e+00 -6.0845e-011.5691e-01 -4.1310e-01 -6.3508e-01 3.6039e-01

A =3.9304e+00 -2.7682e-01 1.5214e-01 4.4847e+004.0097e-02 3.0595e+00 -6.9040e-01 -2.1283e+003.5144e-01 -3.8535e-02 2.3156e+00 -4.8346e-01

-2.7163e-02 8.4395e-02 1.9457e-01 6.9447e-01A =

3.9287e+00 -1.6932e-01 4.1119e-01 -4.4113e+00-1.6308e-02 3.0078e+00 -8.8862e-01 2.1571e+002.1041e-01 -3.4259e-02 2.2044e+00 1.0227e+005.9415e-03 -2.3299e-02 -8.1008e-02 8.5905e-01

A =3.9514e+00 -1.3627e-01 4.9740e-01 4.3484e+00

-5.7605e-02 2.9981e+00 -9.6432e-01 -2.1072e+001.1812e-01 -2.7149e-02 2.1181e+00 -1.3251e+00

-1.4093e-03 7.1443e-03 3.8096e-02 9.3241e-01A =

3.9696e+00 -1.1610e-01 5.3907e-01 -4.3288e+00-7.1970e-02 2.9977e+00 -9.8790e-01 2.0192e+006.3115e-02 -1.8643e-02 2.0658e+00 1.4919e+003.4472e-04 -2.2854e-03 -1.8738e-02 9.6688e-01

A =3.9817e+00 -9.8200e-02 5.6721e-01 4.3356e+00

-6.9838e-02 2.9984e+00 -9.9032e-01 -1.9242e+003.2744e-02 -1.2095e-02 2.0362e+00 -1.5816e+00

-8.5395e-05 7.4567e-04 9.3684e-03 9.8360e-01

¿Alguna conclusión en térmi-nos de convergencia; trabajo?

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

65/95

Iteración QR con desplazamiento

� La velocidad de convergencia se puede aumentar con desplazamientos:

Qk�1Rk�1 DAk�1 � �k�1IAk DRk�1Qk�1 C �k�1I :

El desplazamiento �k�1 debe ser una buena aproximación de un valor propio.

� Desplazamientos más usados:

� Rayleigh. El valor de ann de Ak�1: buena aproximación a priori de �n.

� Wilkinson. Del bloque diagonal inferior 2�2 de Ak�1 (si no es diagonal), elvalor propio de esa submatriz que esté más cerca de ann.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

66/95

� Este script de Matlab es el método de la iteración QR con desplazamientode Rayleigh para matrices con valores propios reales: simétricas, hermíticas, etc.

function [lambda itt]= IteracionQR(A,tol)% Método de la iteración QR con desplazamiento% para matrices con valores propios realesif nargin<2, tol=eps*norm(A); endlambda=0; n=length(A); it=0;for k=n:-1:2 % Hasta aislar lambda_k en a(k,k)

while norm(A(k,1:k-1),inf) > tolsigma=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);it=it+1;

endendlambda=sort(diag(A)); if nargout==2, itt=it; end

end

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

67/95

� Ejemplos

>> ab=ones(5)+eye(5)ab =

2 1 1 1 11 2 1 1 11 1 2 1 11 1 1 2 11 1 1 1 2

>> [lambda it]=IteracionQR(ab)lambda =

1.00001.00001.00001.00006.0000

it =4

>> a=rand(20);>> [lambda it]=IteracionQR(a’*a)lambda =

0.00100.01750.11070.14960.22320.41240.78610.81320.94301.27651.41531.79301.91232.29062.69552.97323.71144.90375.3983

100.1106it =

48

>> eig(a’*a)ans =

0.00100.01750.11070.14960.22320.41240.78610.81320.94301.27651.41531.79301.91232.29062.69552.97323.71144.90375.3983

100.1106

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

68/95Sesión en Matlab para matriz sin estructura especial

>> A=randn(5)A =

0.1303 1.0169 -0.2750 0.7688 0.2815-0.3857 0.5583 0.2378 -0.2941 1.2163-0.5498 -0.1324 0.3125 0.8049 -0.24010.2869 -1.1517 -0.0024 -1.7196 -0.4955

-0.3503 0.4211 0.9847 -0.6632 -1.3721>> A=hess(A) % VEREMOS por quéA =

0.1303 -0.1471 1.0342 -0.5765 -0.59710.8100 0.6165 -0.1303 0.5381 0.9983

0 -1.0393 0.3560 0.3942 0.63860 0 1.3485 -1.9025 -0.06700 0 0 0.4372 -1.2908

>> A0=A;

>> % Hagamos ahora 10 iteraciones de la iteración QR>> for i=1:10, [Q R]=qr(A); A=R*Q; end>> AA =

-1.9640 -1.2063 -0.1339 0.3196 -0.31040.1231 0.3343 -0.7129 1.0207 -0.4763

0 -1.5358 -0.9798 -0.1630 -0.87360 0 1.1031 0.6130 0.25230 0 0 0.0000 -0.0941

>> % Otras 10 iteraciones más>> for i=1:10, [Q R]=qr(A); A=R*Q; end>> AA =

-1.6585 -0.7415 0.3436 -0.8538 0.10630.1202 -2.0481 -0.4571 -0.6504 -1.0568

0 -0.0322 0.6956 -0.7333 -0.14720 0 1.0035 1.0146 -0.01130 0 0 0.0000 -0.0941

>> % Mejora; hagamos 50 más>> for i=1:50, [Q R]=qr(A); A=R*Q; end>> AA =

-1.7423 -0.7746 -0.7995 -0.5685 -0.02970.0805 -1.9665 -0.6724 0.2789 -1.0632

0 -0.0000 1.0634 -0.8844 -0.05610 0 0.8436 0.6489 0.12470 0 0 0.0000 -0.0941

>> % Mejora, aunque no suficientemente; otras 50>> for i=1:50, [Q R]=qr(A); A=R*Q; end>> AA =

-1.8095 -0.7895 -0.9613 0.3250 -0.12980.0657 -1.8993 -0.1186 0.6697 -1.0556

0 -0.0000 0.7945 -1.0629 0.06120 0 0.6651 0.9179 0.12230 0 0 0.0000 -0.0941

>> % Intentemos unas 50 últimas>> for i=1:50, [Q R]=qr(A); A=R*Q; end>> AA =

-1.8704 -0.7919 -0.1944 1.0214 -0.21760.0632 -1.8384 0.5215 0.3733 -1.0411

0 -0.0000 0.7034 -0.7224 0.13610 0 1.0056 1.0089 0.01340 0 0 0.0000 -0.0941

>> % Hay dos bloques 2x2 en la diagonal>> % El último parece claro que es -0.0941

>> % Calculemos los valores propios de esos bloques>> eig(A(1:2,1:2))ans =

-1.8544 + 0.2232i-1.8544 - 0.2232i

>> eig(A(3:4,3:4))ans =

0.8562 + 0.8385i0.8562 - 0.8385i

>> % Comparemos todos con los de la matriz original>> eig(A0)ans =

0.8562 + 0.8385i0.8562 - 0.8385i

-0.0941-1.8544 + 0.2232i-1.8544 - 0.2232i

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

69/95Iteración QR con doble desplazamiento

� Si hay valores propios complejos, se incorpora el doble desplazamiento paratratar los bloques 2�2 irreducibles de la diagonal principal.

� Se usan los dos valores propios, � y N� , de la submatriz 2�2 del bloque inferior,

Qk�1Rk�1 D Ak�1 � �k�1IAk D Rk�1Qk�1 C �k�1I

QkRk D Ak � N�k�1IAkC1 D RkQk C N�k�1I

haciendo así un paso doble con desplazamiento en dos etapas.

� Este doble paso se puede simplificar si M D .Ak�1 � �k�1I/ .Ak�1 � N�k�1I/D .Qk�1Qk/ .RkRk�1/

D A2k�1 � sAk�1 C tI ;

siendo s la traza del bloque diagonal inferior 2�2 de Ak�1 y t su determinante.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

70/95� Si se factorizase la matriz así, M D QR, mediante una sencilla manipulaciónalgebraica resultaría que AkC1 D QTMQ, por lo que teóricamente, en lo quese denomina doble desplazamiento implícito, se evitaría un paso.

� Calcular M requiere O.n3/ operaciones y su factorización ulterior QR esbastante inestable.

� Con los años, los diferentes enfoques de esta variante han convergido en unaestrategia de doble desplazamiento implícito tipo Francis, formulada en 1961por John G.F. Francis.

John G.F. Francis, Reino Unido 1934

� Dado el coste O.n3/, y su complejidad, hay que preparar el problema antes deusar este método.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

71/95Algoritmo QR: Transformaciones preliminares

Definición Una matriz de Hessenberg es una matriz triangular excepto por una sub-diagonal adyacente a la diagonal principal.

@@

@@

@@

@

0

� Cualquier matriz se puede reducir a la forma de Hessenberg mediantetransformaciones de Householder o Givens.

� Si la matriz original es simétrica, al reducirla a la forma de Hessenberg seobtendrá una tridiagonal.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

72/95

� Si se parte de una matriz con la forma de Hessenberg, el algoritmo QR másactual necesita un número de operaciones O.n2/, implementándose en dos fases:

Matriz 1ª fase 2ª fase

Simétrica a tridiagonal a diagonal

General a Hessenberg a triangular

� El trabajo necesario total de todo el proceso QR, preliminar más iterativo, es elque sigue.

Matriz simétrica Matriz general4

3n3 para valores propios sólo 10n3 para valores propios sólo

9n3 valores y vectores propios 25n3 valores y vectores propios

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

73/95

� Un conjunto de rutinas sencillas para reducir cualquier matriz, mediantetransformaciones de Householder, a la forma de Hessenberg seria este.

function [A V] = Hessred(A)% Reducción de A a Hessenberg con Householder% En V vectores de transf. sucesivas de Householder[m,n] =size(A);if A == triu(A,-1), V = eye(m); return, endV = [];for k=1:m-2

x = A(k+1:m,k); v = Housv(x);A(k+1:m,k:m)=A(k+1:m,k:m)-2*v*(v’*A(k+1:m,k:m));A(1:m,k+1:m)=A(1:m,k+1:m)-2*(A(1:m,k+1:m)*v)*v’;v = [zeros(k,1);v]; V = [V v];

endend

function u = Housv(x)% Transf. Householder del x; vector en u.m = max(abs(x));u = x/m;if u(1) == 0, su = 1; else su = sign(u(1)); endu(1) = u(1)+su*norm(u);u = u/norm(u); u = u(:);

end

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

74/95

� Consideraciones finales en torno al algoritmo o método QR:

� Para matrices muy grandes, el algoritmo es costosísimo.

� Si sólo se necesitan unos pocos valores y vectores propios, especialmentepara n grandes, el método no saca partido de ello.

� Requiere mucha memoria de ordenador, aunque la matriz sea grande ydispersa.

� Las transformaciones por semejanza introducen muchos elementos no nulospor lo que se destruye una posible estructura de dispersidad.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

75/95

� Este es un programa del algoritmo QR para matrices simétricas con reduccióninicial a forma Hessenberg y desplazamiento sencillo de Wilkinson. Se pruebacon una matriz 20 � 20, simétrica, generada aleatoriamente.

function [D itt]=It_QR_3(A)% Iteración QR con despla. de Wilkinson para una matriz simétrican=length(A); tol=off(A)*1.e-8; k=n; D=zeros(n,1); it=0;A=Hessred(A); % Reducir a Hessenbergwhile k>1

while abs(A(k,k-1))>tol%Calcular desplazamiento Wilkinsons=eig2x2(A(k-1:k,k-1:k));[i j]=min(abs(A(k,k)*[1 1]’-s)); % Mejor desp. Wilkinson[Q R]=qr(A(1:k,1:k)-s(j)*eye(k));A(1:k,1:k)=R*Q+s(j)*eye(k); it=it+1;

endk=k-1;

endD=sort(diag(A),’ascend’); if nargout==2, itt=it; end

end

function [L]=eig2x2(a)tra=a(2,2)+a(1,1);sqtd=sqrt(tra*tra-4*(a(2,2)*a(1,1)-a(1,2)*a(2,1)));L(1)=(tra+sqtd)/2;L(2)=(tra-sqtd)/2;L=L(:);

end

>> A=rand(20);>> A=(A+A’)/2;>> [D it]=It_QR_3(A)D =

10.53611.58831.52001.12851.05680.94980.64480.51560.24130.1139

-0.0201-0.1461-0.4263-0.6220-0.6692-0.8182-0.8895-1.0250-1.2618-1.2714

it =36

>> eig(A)ans =

-1.2714-1.2618-1.0250-0.8895-0.8182-0.6692-0.6220-0.4263-0.1461-0.02010.11390.24130.51560.64480.94981.05681.12851.52001.5883

10.5361

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

76/95function [T it itd t] = qrstep_Francis_Bindel(H)% Computes eigenvalues of A using a implicit double-shift QR method% as Cornell’s Bindel notes (CS 620).%% Output: TT, vector containing eigenvalues; it, simple iterations;% itd, double iterations.global itr itcn = length(H); T=zeros(n,1);tol = norm(H,’fro’)*1e-8;

H=hess(H); % Reduce A to Hessenberg formitr=0; itc=0; t=cputime;while n > 2

if abs(H(n,n-1)) < tol*(abs(H(n-1,n-1))+abs(H(n,n)))H(n,n-1) = 0; T(n)=H(n,n); % Deflate 1x1 blockn = n-1;

elseif abs(H(n-1,n-2)) < tol*(abs(H(n-2,n-2))+abs(H(n-1,n-1)))H(n-1,n-2) = 0; T(n-1:n)=eig2x2(H(n-1:n,n-1:n)); % Deflate 2x2 blockn = n-2;

elseH(1:n,1:n) = qrstep(H(1:n,1:n)); % Main body

endendT(1:2)=eig2x2(H(1:2,1:2)); T=sort(T,’descend’); t=cputime-t; it=itr; itd=itc;

end

function [NH] = qrstep(H)% Compute double-shift poly and initial column of H^2 + b*H + c*I[b c] = qrpoly(H);C1 = H(1:3,1:2)*H(1:2,1);C1(1:2) = C1(1:2) + b*H(1:2,1);C1(1) = C1(1) + c;% Apply a similarity associated with the first step of QR on Cv = Housv(C1);H(1:3,:) = H(1:3,:)-2*v*(v’*H(1:3,:));H(:,1:3) = H(:,1:3)-(H(:,1:3)*(2*v))*v’;% Do "bulge chasing" to return to Hessenberg formn = length(H);for j=1:n-2

k = min(j+3,n);v = Housv(H(j+1:k,j)); % Find W=I-2vv’ to put zeros below H(j+1,j), H=WHW’H(j+1:k,:) = H(j+1:k,:)-2*v*(v’*H(j+1:k,:));H(:,j+1:k) = H(:,j+1:k)-(H(:,j+1:k)*(2*v))*v’;H(k,j) = 0;

endNH=triu(H,-1);

end

function [b c] = qrpoly(H)% Compute b and c of z^2+b*z+c = (z-sigma)(z-conj(sigma))% where sigma is the Wilkinson double shift: eigenvalue of% the 2x2 trailing submatrix closest to H(n,n)global itr itcHH = H(end-1:end,end-1:end);traHH = HH(1,1)+HH(2,2);detHH = HH(1,1)*HH(2,2)-HH(1,2)*HH(2,1);

if traHH^2 > 4*detHH % Real eigenvalues% Use as double shift the eigenvalue closer to H(n,n)lambdaHH(1) = (traHH + sqrt(traHH^2-4*detHH))/2;lambdaHH(2) = (traHH - sqrt(traHH^2-4*detHH))/2;if abs(lambdaHH(1)-H(end,end))<abs(lambdaHH(2)-H(end,end))

lambdaHH(2) = lambdaHH(1);else

lambdaHH(1) = lambdaHH(2);end% z^2+bz+c=(z-lambda_1)(z-lambda_1)|(z-lambda_2)(z-lambda_2)b = -lambdaHH(1)-lambdaHH(2);c = lambdaHH(1)*lambdaHH(2);itr=itr+1;

else % In the complex case, we want the char poly for HHb = -traHH;c = detHH;itc = itc+1;

endend

Algoritmo QR para matrices generales, con reduccióninicial a Hessenberg, y doble desplazamiento implícitotipo Francis.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

77/95

� Los resultadospara una matriz25 � 25 y otra de1000 � 1000 sonestos.

>> [T it itd t]=qrstep_Francis_Bindel(A)T =

-6.07705.28045.01903.2085 + 3.6195i3.2085 - 3.6195i0.0031 + 4.4372i0.0031 - 4.4372i

-4.2104 + 0.7456i-4.2104 - 0.7456i-1.3585 + 3.9497i-1.3585 - 3.9497i1.2975 + 3.8800i1.2975 - 3.8800i

-2.4416 + 2.7407i-2.4416 - 2.7407i2.8787 + 0.7120i2.8787 - 0.7120i

-1.0840 + 1.8066i-1.0840 - 1.8066i-1.2594 + 0.9430i-1.2594 - 0.9430i-0.3809 + 0.9062i-0.3809 - 0.9062i0.6323

-0.1911it =

7itd =

27t =

0.0624

>> sort(eig(A),’descend’)ans =

-6.07705.28045.01903.2085 + 3.6195i3.2085 - 3.6195i0.0031 + 4.4372i0.0031 - 4.4372i

-4.2104 + 0.7456i-4.2104 - 0.7456i-1.3585 + 3.9497i-1.3585 - 3.9497i1.2975 + 3.8800i1.2975 - 3.8800i

-2.4416 + 2.7407i-2.4416 - 2.7407i2.8787 + 0.7120i2.8787 - 0.7120i

-1.0840 + 1.8066i-1.0840 - 1.8066i-1.2594 + 0.9430i-1.2594 - 0.9430i-0.3809 + 0.9062i-0.3809 - 0.9062i0.6323

-0.1911

>> A=rand(1000);>> A = (A - .5)*2;>> [T it itd t]=qrstep_Francis_Bindel(A)T =

7.123846740573868 +17.026981501328613i7.123846740573868 -17.026981501328613i16.624570346272108 + 7.937272245254786i16.624570346272108 - 7.937272245254786i

-16.089705600685924 + 8.930438288025009i-16.089705600685924 - 8.930438288025009i-10.166595375856957 +15.258792634828080i-10.166595375856957 -15.258792634828080i17.167325994176007 + 6.377944580510263i17.167325994176007 - 6.377944580510263i18.249349262178139 + 0.000000000000000i7.805032835495162 +16.405785237414399i7.805032835495162 -16.405785237414399i-8.822496260367785 +15.869321050483862i-8.822496260367785 -15.869321050483862i16.001083815170652 + 8.555659101012008i16.001083815170652 - 8.555659101012008i-3.803035356678313 +17.729394693350987i-3.803035356678313 -17.729394693350987i4.837154691757405 +17.460853314474601i4.837154691757405 -17.460853314474601i

-17.976118771479754 + 2.032262837884847i-17.976118771479754 - 2.032262837884847i

.

.

.-1.748103565292426 - 1.443294519531504i-2.229777171574543 + 0.000000000000000i2.124127007088685 + 0.000000000000000i-2.000980926645378 + 0.000000000000000i-0.267964043130730 + 1.702030627215852i-0.267964043130730 - 1.702030627215852i1.251743319582046 + 0.303853777326017i1.251743319582046 - 0.303853777326017i-0.989726686530990 + 0.000000000000000i0.222221915982704 + 0.687550759680182i0.222221915982704 - 0.687550759680182i

it =93

itd =1116

t =41.563322418069106

>> tic, [V S U]=eig(A); tocElapsed time is 1.323848 seconds.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

78/95

Subespacios de Krylov Alekxey Krylov, Rusia 1863-1945.

� Recordamos que, para A 2 Cn�n y 0 ¤ b 2 Cn�1, al subespacio

Kj D Genfb;Ab : : :Aj�1bgse le denomina subespacio de Krylov.

� Los métodos que trabajan en los sucesivos subespacios de Krylov que se creansólo llevan a cabo multiplicaciones de matrices por vectores y van reduciendo lamatriz a forma Hessenberg.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

79/95

� Si A tiene n valores propios distintos, �1; : : : ; �n, con vectores propiosasociados x1; : : : ;xn ortonormales (base ortonormal de Rn), cualquier vectorde Rn se puede escribir como combinación lineal de esos vectores propios; enparticular, uno b D c1x1 C c2x2 C � � � C cnxn.

� La matriz de Krylov, Kj D�b Ab : : : Aj�1b

�, de dimensión n � j , se puede

escribir

Kj D Œc1x1 c2x2 � � � cnxn�n�n

266641 �1 � � � �j�11

1 �2 � � � �j�12::::::: : :

:::

1 �n � � � �j�1n

37775n�j

:

� Cuando j D n, la5 matriz Cn D K�1n AKn es tipo Hessenberg:@

@@

@@

0

5De hecho Cn es la matrix compañera de A.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

80/95

� La matriz de Krylov Kn suele estar mal condicionada. Para obtener una buenabase de Im.Kn/ se utiliza la factorización QnRn D Kn de tal forma que

Cn D K�1n AKn D R�1QHn AQnRn! QH

n AQn D RnCnR�1n � H (matriz de Hessenberg):

� Si se igualan las columnas k de la expresión anterior escrita AQn D QnH setiene que

Aqk D h1kq1 C � � � C hkkqk C hkC1;kqkC1expresión que relaciona el vector qkC1 con los anteriores q1; : : : ; qk.

� Si se premultiplica por qHj , teniendo en cuenta la ortonormalidad,

hjk D qHj Aqk; j D 1; : : : ; k:

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

81/95� Estas expresiones dan lugar a la ya estudiada iteración de Arnoldi. Obtiene unamatriz unitaria Qn y una Hessenberg Hn, columna a columna, haciendo sóloproductos de A por vectores y productos interiores de estos.

� Ortogonalización de Apor Iteración de Arnoldi

Dado x0 cualquieraq1 D x0= kx0k2for k D 1; 2; : : :uk D Aqkfor j D 1 to k

hjk D qHj ukuk D uk � hjkqj

endhkC1;k D kukk2if hkC1;k D 0 stopqkC1 D uk=hkC1;k

end

Según progresa el algoritmo, en la iteración k, si Qk DŒq1; : : : ; qk�, la matriz Hk D QH

k AQk es Hessenberg ysus valores propios, denominados valores de Ritz, por

Walther Ritz, Suiza, 1878-1909,

son muy buenas aproximaciones de los valores propios de A.Si y es un vector propio de Hk, Qky es un aproximación deun vector propio de A.

� Si se requieren con precisión los valores propios de Hk se pueden calcular porotro método –por ejemplo la iteración QR–, siendo una tarea menor si k � n.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

82/95� El coste en cálculos de la iteración de Arnoldi es elevado: cada nuevo qk sedebe ortogonalizar respecto a todos los vectores columna de Qk, por lo que sereinicializa periódicamente desde un nuevo vector escogido adecuadamente.

� Si A es simétrica o hermítica se utiliza la iteración de Lanczos que consigue unamatriz tridiagonal.

� Ortogonalización de Apor Iteración de Lanczos

q0 D 0; ˇ0 D 0 y x0 (cualquiera)

q1 D x0= kx0k2for k D 1; 2; : : :uk D Aqk˛k D qHk ukuk D uk � ˇk�1qk�1 � ˛kqkˇk D kukk2if ˇk D 0 stopqkC1 D uk=ˇk

end

Cornelius Lanczos (KornelLowy), Hungría, 1893-1974.

Si ˇk D 0 los valores de Ritz son los valores propios exactos de A.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

83/95� En Matlab:

function [U H flag] = arnoldi_W(A,ns,x)% Realiza ns iteraciones de Arnoldi con reortogonalización en A partiendo de x%% Si flag == 0, las columnas de U son ortonormales, H(ns+1,ns) matriz Hessenberg y% A*U(:,1:ns) = U(:,1:ns+1)*H.%% Si flag == j > 0, se ha obtenido subespacio invariante en j iter. y% A*U(:,1:j) = U(:,1:j)*H(1:j,1:j).%flag = 0;H = zeros(ns+1,ns); n = size(A,1);U = zeros(n,ns+1); U(:,1) = x/norm(x); delta = zeros(ns+1,1);for jj = 1:ns

U(:,jj+1) = A*U(:,jj); % sólo se usa A aquíH(1:jj,jj) = U(:,1:jj)’*U(:,jj+1);U(:,jj+1) = U(:,jj+1) - U(:,1:jj)*H(1:jj,jj); % ortogonalizadelta(1:jj) = U(:,1:jj)’*U(:,jj+1);U(:,jj+1) = U(:,jj+1) - U(:,1:jj)*delta(1:jj); % reortogonalizaH(1:jj,jj) = H(1:jj,jj) + delta(1:jj);H(jj+1,jj) = norm(U(:,jj+1));if H(jj+1,jj) == 0, flag = jj; return, endU(:,jj+1) = U(:,jj+1)/H(jj+1,jj);

endend

% arngo.m: script que demuestra las prestaciones de arnoldi_W%load west0479, A = west0479; % Matriz dispersa 479x479n = size(A,1); ns = 30; % 30 iteraciones de Arnoldirandn(’state’,321) % mismo vector aleatorio cada vezx = randn(n,1); tic % vector de partida aleatorio[U,H,flag] = arnoldi_W(A,ns,x);if flag == 0

residual = norm(A*U(:,1:ns)-U*H) % comprobaciones precisión y ortogonalidadorthocheck = norm(eye(ns+1)-U’*U)ritz = eig(H(1:ns,1:ns),’nobalance’), toc, tic % valores de Ritz y tiemposlam = eig(full(A)); % cálculo de todos los val. propios de Atoc, figure(1)plot(real(lam),imag(lam),’r+’,real(ritz),imag(ritz),’bo’)

end

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

84/95

� El resultado del ejemplo arngo.m con 30 iteraciones de Arnoldi es este. Lascrucecitas rojas son los valores propios auténticos; los círculos azules los valoresde Ritz que los aproximan.

−150 −100 −50 0 50 100 150−2000

−1500

−1000

−500

0

500

1000

1500

2000 >> arngoresidual =

8.432475148361903e-013orthocheck =

1.251900907447703e-015ritz =

1.0e+003 *0.000009213557470 + 1.700662320900872i0.000009213557470 - 1.700662320900872i

-0.100885103219523 + 0.066606248354400i-0.100885103219523 - 0.066606248354400i-0.007240150911503 + 0.120672187071397i-0.007240150911503 - 0.120672187071397i0.108125258880896 + 0.054065937658482i0.108125258880896 - 0.054065937658482i

-0.023312919813425 + 0.070655152714405i-0.023312919813425 - 0.070655152714405i0.059637449793072 + 0.043628336812077i0.059637449793072 - 0.043628336812077i0.0746972816947410.046089595120268 + 0.039266047684087i0.046089595120268 - 0.039266047684087i0.049326743009009 + 0.013259039094298i0.049326743009009 - 0.013259039094298i0.030463628327965 + 0.041942531078661i0.030463628327965 - 0.041942531078661i0.009119356708959 + 0.046886492625578i0.009119356708959 - 0.046886492625578i

-0.013773203484211 + 0.046711009454001i-0.013773203484211 - 0.046711009454001i-0.034755988534576 + 0.042746123558990i-0.034755988534576 - 0.042746123558990i-0.040459377125795 + 0.030311689517999i-0.040459377125795 - 0.030311689517999i-0.074653210517090-0.047756691067739 + 0.011809670790806i-0.047756691067739 - 0.011809670790806iElapsed time is 0.076879 seconds.Elapsed time is 0.226753 seconds.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

85/95

Comparación de los métodosCálculo de todos los valores propios y vectores propios

Matrices generales reales o complejas. Reducción preliminar a forma deHessenberg seguida de iteración QR.

Matrices reales simétricas o complejas hermíticas. Reducciónpreliminar a matriz tridiagonal seguida de iteración QR.

Cálculo de algunos valores y vectores propios

Matrices simétricas de tamaño moderado. Reducción preliminar amatriz tridiagonal seguida de iteración inversa.

Matrices de gran tamaño. Método con iteración de Arnoldi para matricesgenerales.Lanczos para matrices simétricas o complejas hermíticas.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

86/95

Índice

� Introducción teórica


� Obtención numérica


h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

87/95

Cálculo de los valores singulares

� El cálculo de los valores singulares de una matriz A,

las raíces cuadradas no negativas de los valores propios de ATA

se pueden obtener aplicando a ATA alguno de los métodos expuestos paraobtener los valores propios de matrices simétricas.

� Existen no obstante algoritmos más especializados basados en iteraciones QRde la matriz A. Veamos uno.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

88/95Algoritmo de Golub y Reinsch

Primera fase: Bidiagonalización Gene Howard Golub,EE.UU. 1932-2007.

� Consiste en transformar A 2 Cm�n en triangular superior bidiagonal contransformaciones de Householder. Es decir, hacer

QBA˘B D B D�B10

�,

donde

B D

266666664

d1 f2d2 f3 0: : : : : :

0: : : fndn

0

377777775

9>>>>=>>>>;n

m � n

y QB D Qn � � �Q1 2 Rm�m, ˘B D ˘ 1 � � �˘ n�2 2 Rn�n.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

89/95� El esquema operativo que se sigue con una matriz A6�4 es este:

��

��00000

��00000

0 0 ��00000

0000

0 0

- - - - - -Q1 ˘ 1 Q2 ˘ 2 Q3 Q4

��00000

0000

0 00

��00000

0000

000

0 00

��0

00000

0000

000

00

0 00

� Esta rutina de Matlab consigue el resultado.

function [Q1 A P1]= bidiag(A)% Se bidiagonaliza A por Householder.[m,n] = size(A); Q1=eye(m); P1=eye(n);for k = 1:min(m,n)

% Introduce ceros debajo de la diagonal en la columna k.u = A(:,k); u(1:k-1) = 0; sigma = norm(u);if sigma ~= 0

if u(k) ~= 0, sigma = sign(u(k))*sigma; endu(k) = u(k) + sigma; rho = 1/(sigma’*u(k));v = rho*(u’*A); q1=rho*(u’*Q1);A = A - u*v; Q1 = Q1 - u*q1;A(k+1:m,k) = 0;

end% Introduce zeros a la derecha de la supradiagonal en la fila k.u = A(k,:); u(1:k) = 0; sigma = norm(u);if sigma ~= 0

if u(k+1) ~= 0, sigma = sign(u(k+1))*sigma; endu(k+1) = u(k+1) + sigma; rho = 1/(sigma’*u(k+1));v = rho*(A*u’); p1=rho*(P1*u’);A = A - v*u; P1 = P1 - p1*u;A(k,k+2:n) = 0;

endend

end

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

90/95Algoritmo de Golub y Reinsch. Segunda fase

� Ya A bidiagonal, se diagonaliza mediante un algoritmo iterativo haciendo

BkC1 D U TkBkV k; k D 1; 2; : : : ;

con U k y V k ortogonales, y tal que lKımk!1Bk D ˙ D diag.�1; : : : ; �n/.

� La descomposición en valores singulares será A D U �˙0

�V T , donde

U D QB diag.U k; Im�n/škD:::;2;1

y V D ˘B V k’kD1;2:::

.

� En la figura se esquematiza6 cómo se hace.

ETSII-UPM

Cálculo práctico de la SVD (3)SVD de una matriz bidiagonal B, de tamaño n×n:

Se puede aplicar el método QR con desplazamiento a la matriz T=BTB.También se pueden aplicar una serie (teóricamente infinita) de rotaciones deGivens a B para hacerla diagonal:

Se comprueba que los elementos de la supra-diagonal tienden a cero (desde eln-1 hasta el primero) y los de la diagonal a los valores singulares.La convergencia puede ser acelerada utilizando desplazamiento.

13 3212 21

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 00 0 0 0 0 0 0 0 0 0 0 0 0 00 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 0

∗ ∗ ∗ ∗ ∗ + ∗ ∗ ∗ ∗ ∗ ∗ + ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ + ∗ ∗ ∗ ∗ ∗ ∗ + ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗

→ → → →BG G BBG G B

43 35 5424

0 00 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 00 0 0 0 0 0 0 0 0 0 00 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

ETSII-UPM

Cálculo práctico de la SVD (3)SVD de una matriz bidiagonal B, de tamaño n×n:

Se puede aplicar el método QR con desplazamiento a la matriz T=BTB.También se pueden aplicar una serie (teóricamente infinita) de rotaciones deGivens a B para hacerla diagonal:

Se comprueba que los elementos de la supra-diagonal tienden a cero (desde eln-1 hasta el primero) y los de la diagonal a los valores singulares.La convergencia puede ser acelerada utilizando desplazamiento.

13 3212 21

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 00 0 0 0 0 0 0 0 0 0 0 0 0 00 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 0

∗ ∗ ∗ ∗ ∗ + ∗ ∗ ∗ ∗ ∗ ∗ + ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ + ∗ ∗ ∗ ∗ ∗ ∗ + ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗

→ → → →BG G BBG G B

43 35 5424

0 00 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 00 0 0 0 0 0 0 0 0 0 00 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

6Recordemos las ideas el algoritmo de Jacobi para el cálculo de los valores propios de matrices simétricas,pues se hace algo parecido.

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

91/95

� Código de Matlab:

function [S U V it t t1 F]=svd_GolRein_1(A)% Se calcula al descomposición en valores singulares, [U S V]=U*S*V=A,% de una matriz cualquiera m x n.% Sigue casi exactamente el "paper" de Golub y Reinsch, "Singular Value% Decomposition and Least Squares Solutions", Numeri. Math., 14, 1970.[m n]=size(A); tol=norm(A,’fro’)*sqrt(eps); itr=0; tic;if n>m, A=A’; [m n]=size(A); itr=1; end % Necesario m>=n

% Bidiagonaliza A por Householder: U*B_n*V’ = A[U B_n V] = bidiag_Hansen(A); t1=toc; tic;q=B_n(:,1); e=[0; B_n(1:n-1,2)]; U1=eye(m); V1=eye(n);k=n; it=0;while k>0 % Bucle principal proceso itera.

caso=1;for l=k:-1:1

if abs(e(l)) <=tol, e(l)=0; caso=0; break, endif abs(q(l-1))<=tol, q(l-1)=0; break, end

endif caso

c=0; s=1; l1=l-1; % Cancelación columna l-1: Givensfor i=l:k

f=s*e(i); e(i)=c*e(i);if abs(f)<=tol, break, endg=q(i); h=sqrt(f*f+g*g); c=g/h; s=-f/h; q(i)=h;U1(:,[l1 i])=U1(:,[l1 i])*[c -s;s c];

endendz=q(k); % Comprobar convergenciaif l==k

if z<0, q(k)=-z; V1(:,k)=-V1(:,k); endk=k-1; continue

endx=q(l); y=q(k-1); g=e(k-1); h=e(k); % Cálculo desplazami. con 2x2f=((y-z)*(y+z)+(g-h)*(g+h))/(2*h*y); g=sqrt(f*f+1);f=((x-z)*(x+z)+h*(y/(f+(sign(f)+(f==0))*g)-h))/x;

c=1; s=1; % Comienzo iteración QRfor i=l+1:k

g=e(i); y=q(i); h=s*g; g=c*g;e(i-1)=sqrt(f*f+h*h); z=e(i-1); c=f/z; s=h/z;f=x*c+g*s; g=-x*s+g*c; h=y*s; y=y*c;V1(:,[i-1 i])=V1(:,[i-1 i])*[c -s;s c];q(i-1)=sqrt(f*f+h*h); z=q(i-1); c=f/z; s=h/z;f=c*g+s*y; x=-s*g+c*y;U1(:,[i-1 i])=U1(:,[i-1 i])*[c -s;s c];

ende(l)=0; e(k)=f; q(k)=x;it=it+1;

endU=U*U1; V=V1’*V’;S=zeros(m,n); % Valores singulares en S y salida resul.for i=1:n

ssn=q(i); S(i,i)=abs(ssn); if ssn<0, V(i,:)=-V(i,:); end,end[q ix]=sort(diag(S),’descend’);for i=1:n, S(i,i)=q(i); end % Valores sing. en S de + a -ix1=1:m; P1=eye(m); ix1(1:n)=ix; P1=P1(:,ix1); U=U*P1; V=V(ix,:);F=max(max(U*S*V-A)); t=toc; % Chequeo precisión resultadosif itr==1, S=S’; Te=U; U=V’; V=Te’; end % Si m<n, trasponer resultadosif nargout==1, S=diag(S); endend

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

92/95� Utilicemos el algoritmo en una pequeña sesión de Matlab.

>> A=[1 2 3;3 4 5;6 7 8];>> [S U V]=svd_GolRein_1(A)S =

14.5576 0 00 1.0372 00 0 0.0000

U =-0.2500 -0.8371 -0.4867-0.4852 -0.3267 0.8111-0.8379 0.4389 -0.3244

V =-0.4625 -0.5706 -0.67860.7870 0.0882 -0.61060.4082 -0.8165 0.4082

>> U*S*Vans =

1.0000 2.0000 3.00003.0000 4.0000 5.00006.0000 7.0000 8.0000

>> A=[1 2 3;3 4 5;6 7 8];>> [V S U]=svd(A)V =

-0.2500 -0.8371 -0.4867-0.4852 -0.3267 0.8111-0.8379 0.4389 -0.3244

S =14.5576 0 0

0 1.0372 00 0 0.0000

U =-0.4625 0.7870 0.4082-0.5706 0.0882 -0.8165-0.6786 -0.6106 0.4082

>> V*S*U’ans =

1.0000 2.0000 3.00003.0000 4.0000 5.00006.0000 7.0000 8.0000

� Tiempos y precisión

>> A=rand(1000);>> A = (A - .5)*2;

>> tic, [S U V]=svd_GolRein_1(A); tocElapsed time is 13.971564 seconds.

>> tic, [V S U]=svd(A); tocElapsed time is 0.315793 seconds.>> norm(diag(S-S1))

ans =1.1278e-08

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

93/95

� Para una matriz complicada como M D�1 0 0 0 20 0 3 0 00 0 0 0 00 4 0 0 0

�:

>> M=[1 0 0 0 2;0 0 3 0 0;0 0 0 0 0;0 4 0 0 0]M =

1 0 0 0 20 0 3 0 00 0 0 0 00 4 0 0 0

>> [S U V]=svd_GolRein_1(M)S =

4.0000 0 0 0 00 3.0000 0 0 00 0 2.2361 0 00 0 0 0 0

U =0 0 -1 00 -1 0 00 0 0 11 0 0 0

V =0 1.0000 0 0 00 0 -1.0000 0 0

-0.4472 0 0 0 -0.89440 0 0 1.0000 00 0 0 0 1.0000

>> [U S V]=svd(M)U =

0 0 1 00 1 0 00 0 0 -11 0 0 0

S =4.0000 0 0 0 0

0 3.0000 0 0 00 0 2.2361 0 00 0 0 0 0

V =0 0 0.4472 0 -0.8944

1.0000 0 0 0 00 1.0000 0 0 00 0 0 1.0000 00 0 0.8944 0 0.4472

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

94/95

Algoritmo de Jacobi

� Las raíces cuadradas no negativas de los valores propios de AAT son los valoressingulares de A. Utilicemos Jacobi para calcular aquellos valores propios.

>> A=[1 2 3;3 4 5;6 7 8];>> [V D it]=Jacobi_val_12(A’*A)V =

0.7870 0.4082 -0.46250.0882 -0.8165 -0.5706

-0.6106 0.4082 -0.6786D =

0.00001.0759

211.9241it =

6>> sqrt(D)ans =

0.00001.0372

14.5576

>> A=[1 2 3;3 4 5;6 7 8];>> [V S U]=svd(A)V =

-0.2500 -0.8371 -0.4867-0.4852 -0.3267 0.8111-0.8379 0.4389 -0.3244

S =14.5576 0 0

0 1.0372 00 0 0.0000

U =-0.4625 0.7870 0.4082-0.5706 0.0882 -0.8165-0.6786 -0.6106 0.4082

>> V*S*U’ans =

1.0000 2.0000 3.00003.0000 4.0000 5.00006.0000 7.0000 8.0000

Con la matriz M :

>> [V D it]=Jacobi_val_12(M’*M)V =0.4472 0 0 0 -0.8944

0 1.0000 0 0 00 0 1.0000 0 00 0 0 1.0000 0

0.8944 0 0 0 0.4472D =

0059

16it =

1>> sqrt(D)ans =

00

2.23613.00004.0000

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

95/95

� Algo más sofisticado, aunque en lo esencial igual:

function [U S V] = svd_J(A,tol)% SVDJ Singular value decomposition using Jacobi algorithm.if nargin == 1, tol = eps; end % Tolerancia por defecto[M,N] = size(A); K = min(M,N); % K es el número de valores singularesOn = 0;for c=A, On=On + sum(abs(c).^2); endOn=On./N; % Suma coef.^2/NPrevious_Off = Inf; V = eye(N);while trueR = 0; % Contar las rotacionesfor r = 1:N - 1

for c = r + 1:N% Calculate the three elements of the implicit matrix B that are% needed to calculate a Jacobi rotation. Since B is Hermitian, the% fourth element (b_cr) is not needed.b_rr = sum(abs(A(:,r)).^2); % Real value.b_cc = sum(abs(A(:,c)).^2); % Real value.b_rc = A(:,r)’ * A(:,c); % Same type as A.% Calculate a Jacobi rotation (four elements of G). The two values% that we calculate are a real value, C = cos(theta) and S, a value% of the same type as A, such that |S| = sin(theta).m = abs(b_rc);if m ~= 0 % If the off-diagonal element is zero, we don’t rotate.

tau = (b_cc - b_rr)/(2*m); % tau is real and will be zero if% the two on-diagonal elements are% equal. In this case G will be an% identity matrix, and there is no% point in further calculating it.

if tau ~= 0R = R + 1; % Count the rotation we are about to perform.t = sign(tau)./(abs(tau) + sqrt(1+tau.^ 2));C = 1./sqrt(1 + t.^ 2);S = (b_rc.* t.* C)./ m;% Initialize the rotation matrix, which is the same size as the% implicit matrix B.% We have to create an identity matrix here of the same type as A,% that is, quaternion if A is a quaternion, double if A is double.% To do this we use a function handle (q.v.) constructed from the% class type of A. This was done before the loop, since the type% of A is invariant.G = eye(N); G(r,r) = C; G(c,c) = C; G(r,c) = S; G(c,r) =-conj(S);A = A * G;V = V * G;

endend

endend

if R == 0, error(’No rotations performed during sweep.’), end% Calculate the sum of the off-diagonal elements of the matrix B.B = A’ * A;Off = sum(sum(abs(triu(B,1))))/(N.^2); % Normalise by the matrix size!if (Off/On) < tol, break; end % Off-diagonal sum is small enough to stop.if Previous_Off < Off

warning(’QTFM:information’, ...’Terminating sweeps: off diagonal sum increased on last sweep.’)

break;endPrevious_Off = Off;end% Extract and sort the singular values. The vector T may be longer than the% number of singular values (K) in cases where A is not square.[T,IX] = sort(sqrt(abs(diag(B))),’descend’);if nargout == 0 || nargout == 1 % .. only the singular values are needed.

U = T(1:K);endif nargout == 3 % .. the singular vectors and singular values are needed.

A = A(:, IX); % Map the columns of A and V into the same order as theV = V(:, IX); % singular values, using the sort indices in IX.% Construct the left singular vectors. These are in A but we need% to divide each column by the corresponding singular value. This% calculation is done by replicating T to make a matrix which can% then be divided into A element-by-element (vectorized division).U = A./ repmat(T’,M,1);S = diag(T); % Construct a diagonal matrix of singular values from

% the vector T, because when there are three output% parameters, S is required to be a matrix.

endend

valores y vectores propiosuniversidad politécnica de madrid–escuela técnica superior de...

Documents