cap tulo 10 el problema de valores propios - ehu.eus · en algebra lineal numerica se suele hablar...

Capıtulo 10

El problema de valorespropios

10.1. Introduccion

El objetivo de este capıtulo es estudiar los algoritmos mas importantes para calcularlos valores propios de matrices generales; es decir, matrices que no son simetricaso hermıticas. Los algoritmos que veremos aquı son aplicables tambien a matricessimetricas y hermıticas pero para estas hay, ademas, otros algoritmos especıficos.

En Algebra Lineal Numerica se suele hablar de algoritmos directos y de algoritmositerativos para distinguir entre los algoritmos que producen el resultado deseadotras un numero finito de iteraciones (algoritmos directos como los de Gauss o QR)y aquellos que tienen como objetivo la construccion de una sucesion de objetosque converge al resultado deseado. Como veremos enseguida hay una razon muypoderosa para que los algoritmos para el calculo de valores y vectores propios seandel segundo tipo. Y siendo las cosas ası se habla de metodos directos e iterativos para

227

228 El problema de valores propios

el calculo de valores y vectores propios con un significado diferente a los anteriores.Los primeros buscan obtener todos los valores propios y (opcionalmente) los vectorespropios; es decir, la forma de Schur de la matriz. Los metodos iterativos tratan decalcular un valor propio seleccionado y un vector propio, y de forma reiterada llegar aencontrar, si es posible, todos ellos. El algoritmo QR es el paradigma de los metodosdirectos y el Metodo de las Potencias el de los metodos iterativos. En este Capıtulotrataremos los metodos iterativos.

10.2. El metodo de las potencias

El objetivo del metodo de las potencias es calcular un vector propio de una matrizdada A P Fnˆn. Es extremadamente simple: Dado un vector no nulo x P Fn se cons-truye la sucesion tAkxu, k “ 1, 2, . . .. Esta sucesion de vectores puede no convergera un vector, pero frecuentemente la sucesion de los subespacios generados por suselementos,tă Akx ąu, sı. Recordemos que para cada valor propio no hay un vectorpropio determinado unıvocamente, sino todo un subespacio de ellos (exceptuandoel vector cero que no es un vector propio). Por lo tanto, lo que nos interesa es bus-car un subespacio propio de A y despues escoger un vector propio particular; porejemplo, un vector propio unitario. Ası pues, debemos estudiar la convergencia desubespacios y no de vectores propiamente.

10.2.1. Convergencia de subespacios

En primer lugar, al conjunto de subespacios de Fn de dimension d se le llama Grass-manniana o Variedad de Grassman, y se representa mediante el sımbolo GrdpFnq:

GrdpFnq “ tS Ă Fn : S subespacio de dimension du

Para poder hablar de convergencia de subespacios, debemos dotar a GrdpFnq de unaestructura topologica. Hay dos formas clasicas de hacerlo que producen la mismatopologıa: definir una distancia entre subespacios, llamada distancia “gap”, o identi-ficar el conjunto de subespacios de dimension d con un conjunto cociente de matricesy definir en este la topologıa cociente. Aunque la primera forma de proceder es masapropiada para el analisis numerico porque proporciona cotas cuantitativas en el

10.2 El metodo de las potencias 229

analisis del error, es tambien la mas larga. Como, ademas, no haremos un analisisdel error muy riguroso, adoptaremos la segunda aproximacion, que es mas rapida.

Dado un subespacio S de dimension d en Fn y dada una base tx1, . . . , xdu, llama-remos matriz base de S a la matriz X “ “

x1 ¨ ¨ ¨ xd‰. Las matrices base de los

subespacios de dimension d tienen la particularidad de ser matrices de tamano nˆdy de rango d. Y toda matriz con estas propiedades genera un subespacio de dimen-sion d. Pero puede haber mas de una matriz nˆ d de rango d que genere el mismosubespacio: todas las matrices base deben estar relacionadas mediante una matrizde cambio de base. Es decir, X1, X2 P Fnˆd generan el mismo subespacio de dimen-sion d si y solo si rangX1 “ rangX2 “ d y existe una matriz invertible P P Fdˆdtal que X1 “ X2P . Ahora bien, la relacion X1 „ X2 si y solo si existe P P Fdˆdtal que X1 “ X2P es una relacion de equivalencia en el conjunto Mn,dpFq de lasmatrices n ˆ d de rango d con elementos en F. Y cada subespacio de dimension dpuede identificarse con una clase de equivalencia. Ası, identificaremos

GrdpFnq ” Mn,dpFqGldpFq

dondeMn,dpFqGldpFq representa el conjunto de clases de equivalencia por la relacion que

acabamos de definir. En concecuencia, dada una matriz X PMn,dpFq denotaremospor ă X ąP GrdpFq el subespacio generado por las columnas de X.

Ahora, Mn,dpFq es un conjunto abierto de Fnˆd que podemos considerar dotado dela topologıa relativa. En este caso, U Ă Mn,dpFq es abierto en Mn,dpFq si lo esen Fnˆd. Con esta topologıa en Mn,dpFq podemos dotar a GrdpFnq de la topologıa

cociente enMn,dpFqGldpFq : Si

π : Mn,dpFq Ñ GrdpFnqX Ñ ă X ą

es la proyeccion canonica, U Ă GrdpFnq es abierto si y solo si π´1pUq es abierto enMn,dpFq. Ası pues, la topologıa de GrdpFnq es la topologıa mas fina que hace de πuna aplicacion continua. Tenemos ademas

Lema 10.1 π es una aplicacion abierta.

Demostracion.- Hay que probar que si U Ă Mn,dpFq es abierto entonces πpUqes abierto en GrdpFnq. Y, de acuerdo con la definicion de la topologıa definida


en GrdpFnq, esto significa que π´1pπpUqq es abierto en Mn,dpFq. Ahora bien, Y Pπ´1pπpUqq si y solo si ă Y ąP πpUq; y esto equivale a que ă Y ą“ă X ą paraalguna matriz X P U . Por lo tanto,

π´1pπpUqq “ tXP : X P U y P P GldpFquPara demostrar que π´1pπpUqq es abierto tenemos que ver que si X P π´1pπpUqqexiste un r ą 0 tal que si }X ´ Y } ă r entonces Y P π´1pπpUqq. Tomamos, comonorma, cualquier norma de matriz y sea X P π´1pπpUqq. Entonces XP P U paraalguna matriz P P GldpFq. Como U es abierto, existe s ą 0 tal que si }XP ´Z} ă sentonces Z P U . Sea

0 ă r ă s

}P }y supongamos }X ´ Y } ă r. Como }XP ´ Y P } ď }X ´ Y }}P } resulta que }XP ´Y P } ă s; por lo que Y P P U . Es decir, Y P π´1pπpUqq tal y como se deseabademostrar.

Hay algunas propiedades topologicas importantes de GrdpFnq que utilizaremos peroque no vamos a demostrar. Son las siguientes:

(i) Si ĂMn,dpFq es el subconjunto de Mn,dpFq de matrices cuyas columnas sonortonormales y UdpFq representa el grupo matrices unitarias (ortogonales si

F “ R) de tamano d ˆ d entonces Mn,dpFq{GldpFq y ĂMn,dpFq{UdpFq son

homeomorfos. Se entiende que ĂMn,dpFq esta dotado de la topologıa relativa

como subconjunto de Mn,dpFq y ĂMn,dpFq{UdpFq es el conjunto cociente declases de matrices con columnas ortonormales que son matriz base del mismoespacio vectorial. Es decir, Q1, Q2 P ĂMn,dpFq estan relacionadas si y solo si

existe U P UdpFq tal que Q2 “ Q1U . El espacio cociente ĂMn,dpFq{UdpFq sesupone dotado con la correspondiente topologıa cociente.

La prueba de que Mn,dpFq{GldpFq y ĂMn,dpFq{UdpFq son homeomorfos se puedeobtener como consecuencia de que los factores Q y R en la factorizacion QRde A (recordemos que por ser A de rango completo es unica) son funcionescontinuas de A.

(ii) Si V Ă ĂMn,dpFq entonces

rπ´1prπpVqq “ tQZ : Q P V y Z P UdpFqu,y se demuestra igual que en el Lema 10.1 que rπ es una aplicacion abierta.


(iii) Ya hemos dicho que a GrdpFnq se le puede dotar de una estructura de espaciometrico con la llamada metrica ”gap”. Somos ahora un poco mas precisos eneste punto: Dados dos subespacios S1, S2 P GrdpFnq se define la distancia gapentre S1 y S2 como

ΘpS1,S2q “ }P1 ´ P2}2siendo Pi la proyeccion ortogonal sobre Si. Esta definicion es una generalizacionde un hecho bastante natural para subespacios de dimension 1. Si dimS1 “dimS2 “ 1 entonces S1 “ă x ą y S2 “ă y ą, digamos, con x ‰ 0, y ‰ 0.En este caso resulta (aunque no es trivial demostrarlo) que }P1´P2}2 “ sen θsiendo θ el angulo agudo que forman x, y. Es claro que en este caso ΘpS1,S2q “sen θ define una metrica.

En cualquier caso, GrdpFnq con la topologıa derivada de la metrica gap y

los espacios cocientes Mn,dpFq{GldpFq y ĂMn,dpFq{UdpFq son homeomorfos. Lademostracion de este resultado tampoco es trivial.

(iv) Como todo espacio metrico es Hausdorff, GrdpFnq es Haussdorff.

(v) Se demuestra facilmente que ĂMn,dpFq es cerrado y acotado; por lo tanto com-pacto (por ser subespacio de Fnˆd y F “ R o C). Como la proyeccion canonica

rπ : ĂMn,dpFq Ñ ĂMn,dpFqUdpFq es continua, GrdpFnq es compacto.

El siguiente resultado muestra que la convergencia de sucesiones de subespaciospuede estudiarse a partir de la convergencia de matrices bases de los mismos.

Teorema 10.2 Sea tSkuk“0,1,2,... Ă GrdpFnq una sucesion de subespacios y S PGrdpFq. Sea X P Mn,dpFq una matriz base de S y, para k “ 0, 1, 2, . . . Xk unamatriz base de Sk. Entonces Sk Ñ S si y solo si para cada k “ 0, 1, 2, . . . existe unamatriz invertible dˆ d Pk tal que XkPk Ñ X.

Demostracion.- La demostracion es elemental. Supongamos Sk Ñ S y sea UX unentorno abierto de X. Como π es abierta VS “ πpUXq es un entorno abierto de S ycomo Sk Ñ S, existe un numero natural N tal que si k ě N entonces Sk P VS . Dadoque VS “ πpUXq, para cada k ě N existe una matriz Yk P UX tal que Sk “ă Yk ą.Es decir, para cada k ě N existe una matriz invertible Pk tal que XkPk P UX . Estosignifica que XkPk Ñ X.


El recıproco se demuestra igual. Si VS es un entorno abierto de S entonces UX “π´1pVSq es un entorno abierto de X. Si existen matrices invertibles Pk tales queXkPk Ñ X entonces existe un entero positivo N ą 0 tal que si k ě N se tiene queXkPk P UX pero VS “ πpUXq. Por lo tanto, para k ě N se tiene que Sk “ πpXkPkq PVS . Es decir, Sk Ñ S.

Usando que rπ es abierta, la demostracion del siguiente resultado es igual que la delTeorema 10.2

Teorema 10.3 Sea tSkuk“0,1,2,... Ă GrdpFnq una sucesion de subespacios y S PGrdpFq. Sea Q P ĂMn,dpFq una matriz base ortonormal de S y, para k “ 0, 1, 2, . . .Qk una matriz base ortonormal de Sk. Entonces Sk Ñ S si y solo si para cadak “ 0, 1, 2, . . . existe una matriz unitaria dˆ d Zk tal que QkZk Ñ Q.

Con estos resultados sobre convergencia de subespacios podemos probar el siguienteresultado fundamental:

Teorema 10.4 Sea X P Mn,dpFq y A P Fnˆn una matriz tal que rangpAkXq “ dpara todo k “ 1, 2, . . .. Si la sucesion de subespacios tă AkX ąu converge, lo hace aun subespacio S P GrdpFnq que es A-invariante.

Demostracion.- Supongamos que ă AkX ąÑ S. Como rangpAkXq “ d paracada k ě 0 el subespacio ă AkX ąP GrdpFnq. Ahora bien, GrdpFnq es un espaciocompacto y Hausdorff, por lo tanto cerrado. Si ă AkX ą converge debe hacerloa un subespacio de GrdpFnq. Veamos que, ademas, este debe ser A-invariante. Enefecto, como para k “ 0, 1, 2, . . . AkX es una matriz base de ă AkX ą aplicandoel Teorema 10.2, para cada k “ 0, 1, 2, . . . existe una matriz invertible Pk tal queAKXPk Ñ Y , donde Y es una matriz base de S. Dado que A es lineal, y por lotanto continua, ApAKXPkq Ñ AY . Aplicando de nuevo el Teorema 10.2 deducimosque ă Ak`1X ąÑă AY ą. Pero por hipotesis ă Ak`1X ąÑă Y ą. Como GrdpFqes Haussdorf, el lımite es unico. Por lo tanto, ă AY ą“ă Y ą“ S. Ahora es facildeducir que AS Ď S. En efecto, si x P S entonces x “ Y ξ y Ax “ AY ξ Pă AY ą“S.


10.2.2. El algoritmo del metodo de las potencias

Aplicamos el Teorema 10.4 al metodo de las potencias.

Corolario 10.5 Sea A P Fnˆn y x P Fn un vector no nulo. Si la sucesion de subes-pacios ă Akx ą converge a un subespacio ă y ą no nulo entonces y es un vectorpropio de A.

Demostracion.- En primer lugar, si ă Akx ąÑă y ą con y ‰ 0 entonces Akx ‰ 0para todo k “ 1, 2, . . .. Por el Teorema 10.4 ă y ą es A-invariante, lo cual significaque Ay Pă y ą. Es decir, Ay “ αy para algun α P F. Por lo tanto, y es un vectorpropio de A asociado al valor propio α.

Notese que de acuerdo con la demostracion del corolario, si A y x son reales yă Akx ą converge a un subespacio no nulo ă y ą entonces y es vector propio realasociado a un valor propio real.

De forma similar se demuestra

Corolario 10.6 Sea A P Fnˆn y q P Fn un vector unitario. Si la sucesion de subes-

pacios

⟨Akq

}Akq}2

⟩converge a un subespacio ă y ą no nulo entonces y es un vector

propio unitario de A.

Este resultado es la base del metodo de las potencias cuya primera version es lasiguiente:


Metodo de las Potencias (Primera Version)Dada A P Rnˆn

Paso 1: Elıjase x0 P Fnˆ1 (F “ R o C)

Paso 2: q0 “ x0

}x0}2Paso 2: for j “ 0, 1, 2, 3, . . . hasta convergencia

xj`1 “ Aqj

qj`1 “ xj`1

‖ xj`1 ‖(vector propio unitario aproximado)

λj`1 “ qj`1Aqj`1 (valor propio aproximado)

end for.

Antes de analizar la convergencia de este algoritmo conviene hacer algunas observa-ciones:

1. En primer lugar, el algoritmo construye la sucesion de vectores unitarios:q0, q1, q2, . . . donde

qi “ Aqi´1

}Aqi´1}2 , i “ 1, 2, . . .

Es muy facil ver que

qi “ Aiq0

}Aiq0}2 .

Es decir, el algoritmo construye la sucesion

"Akq0

}Akq0}2

*del Corolario 10.6. Por

lo tanto, si esta sucesion converge lo hace a un vector propio unitario de A. Noobstante, esta sucesion puede no converger y sin embargo sı hacerlo la sucesion

de subespacios

⟨Akq0

}Akq0}2

⟩. Esto es lo importante. En tal caso, de acuerdo con

el Corolario 10.6, obtendremos un subespacio propio de A como lımite.

2. Se usa provisionalmente la expresion “hasta convergencia” para indicar que,en caso de que la sucesion de subespacios converja, la rutina for se reali-zarıa un numero suficiente de veces. Mas adelante estudiaremos un criterio determinacion de esta rutina.


3. El algoritmo calcula vectores unitarios qj que cuando ă qj ąÑă q ą propor-cionan un vector propio unitario, q, de A. Por eso llamamos vectores propiosaproximados a los vectores qj.

4. Con cada vector qj se calcula qjAqj que es un numero en F. Si qj fuera unvector propio exacto entonces qjAqj serıa un valor propio exacto. En efecto:

Aqj “ λqj ñ q˚jAqj “ λq˚j qj “ λ

porque qj es unitario. Si qj es un vector proximo a un vector propio entoncesλj “ qjAqj es, por continuidad, un numero proximo a un valor propio de A.Por eso le llamamos ”valor propio aproximado”. Ademas, si A es real y x0 esreal, entonces todo se realiza en aritmetica real. Es decir, los vectores y valorespropios aproximados calculados son reales.

5. Aun cuando la sucesion qj no converja, si ă qj ą converge lo hace a un subes-pacio propio y los vectores qj seguiran siendo vectores propios aproximados.En consecuencia, si ă qj ą converge, la sucesion λj convergera a un valor pro-pio de A. Es decir, si el algoritmo converge (en el sentido que ă qj ą converge)se obtiene un vector propio unitario y un valor propio tan aproximados comose quiera (dentro de la aritmetica en punto flotante que se utilice) de A. Perodado que los vectores propios pueden cambiar de direccion, los criterios paraterminar el algoritmo deberan tener en cuenta tanto a los vectores propioscomo a los valores propios.

10.2.3. Analisis de la convergencia del metodo de las poten-cias

La cuestion ahora es establecer condiciones suficientes lo mas amplias posible sobreA y q para poder asegurar que qk converge. El siguiente teorema es el resultadofundamental:

Teorema 10.7 Sea q0 P Fn un vector unitario y A P Fnˆn una matriz diagonalizablecon λ1, . . . , λn como valores propios. Sea tv1, . . . , vnu una base de vectores propiosunitarios de A (Avi “ λivi y }vi}2 “ 1, i “ 1, . . . , n) y supongamos que q0 “α1v1 ` ¨ ¨ ¨ ` αnvn. Supongamos tambien que

|λ1| ą |λ2| ě |λ3| ě ¨ ¨ ¨ ě |λn| (10.1)


Entonces ă qj ąÑă v1 ą si y solo si α1 ‰ 0. Mas aun, en tal caso, para j “0, 1, 2, . . . existen numeros complejos zj de modulo 1 tales que

}zjqj ´ v1}2 “ O

˜ˇˇλ2

λ1

ˇˇj¸.

Recuerdese que la expresion }zjqj ´ v1}2 “ O

ˆˇˇλ2λ1

ˇˇj˙

significa que para j suficien-

temente grande existe una constante positiva K tal que

}zjqj ´ v1}2 ď K

ˇˇλ2

λ1

ˇˇj

.

Por lo tanto, la segunda parte del Teorema nos dice que, cuando hay convergencia,

esta se produce a la misma velocidad a la que la sucesion

"ˇˇλ2λ1

ˇˇj*

converge a 0.

Demostracion.- Es facil ver que si Avi “ λivi entonces Ajvi “ λjivi y, en conse-cuencia,

Ajq0 “ α1Ajv1 ` ¨ ¨ ¨ ` αnAjvn “ α1λ

j1v1 ` ¨ ¨ ¨ ` αnλjnvn.

Si α1 ‰ 0, como λ1 ‰ 0 porque |λ1| ą |λ2| ě 0, podemos definir βj “ }Ajq0}2α1λ

j1

. Ası

βj ‰ 0 y recordando que qj “ Ajq0

}Ajq0}2 tenemos que

βjqj “ v1 ` α2

α1

ˆλ2

λ1

˙j

v2 ` ¨ ¨ ¨ ` αnα1

ˆλnλ1

˙j

vn. (10.2)

Como por hipotesisˇˇλ2λ1

ˇˇ ă 1, tenemos que lım

jÑ8 βjqj “ v1. Por el Teorema 10.2

concluimos que ă qj ąÑă v1 ą.

Recıprocamente, supongamos ă qj ąÑă v1 ą. Por el Teorema 10.2 existen numerosβj tales que βjqj Ñ v1. Sea P la proyeccion sobre ă v1 ą a lo largo de ă v2, . . . , vn ą.Entonces P pβjqjq Ñ Pv1 “ v1. Pero

P pβjqjq “ βj}Ajq0}2P pA

jq0q “ βj}Ajq0}2P pα1λ

j1v1`α2λ

j2v2`¨ ¨ ¨`αnλjnvnq “

βj}Ajq0}2α1λ

j1v1.


Asıβj

}Ajq0}2α1λj1v1 Ñ v1. Como v1 ‰ 0 debe ser α1 ‰ 0. A la proyeccion sobre ă v1 ą

a lo largo de ă v2, . . . , vn ą se le llama proyeccion espectral sobre el subespaciopropio ă v1 ą.

Para demostrar la segunda parte del teorema partimos de la expresion (10.2) yponemos

xj “ α2

α1

ˆλ2

λ1

˙j

v2 ` α3

α1

ˆλ3

λ1

˙j

v3 ` ¨ ¨ ¨ ` αnα1

ˆλnλ1

˙j

vn.

Entonces, teniendo en cuenta que }vi}2 “ 1,

}xj}2 ďˇˇα2

α1

ˇˇˇˇλ2

λ1

ˇˇj

}v2}2 `ˇˇα3

α1

ˇˇˇˇλ3

λ1

ˇˇj

}v3}2 ` ¨ ¨ ¨ `ˇˇαnα1

ˇˇˇˇλnλ1

ˇˇj

}vn}2 “

“ˇˇλ2

λ1

ˇˇj˜ˇˇα2

α1

ˇˇ`

ˇˇα3

α1

ˇˇˇˇλ3

λ2

ˇˇj

` ¨ ¨ ¨ `ˇˇαnα1

ˇˇˇˇλnλ2

ˇˇj¸

La sucesion ˇˇα2

α1

ˇˇ`

ˇˇα3

α1

ˇˇˇˇλ3

λ2

ˇˇj

` ¨ ¨ ¨ `ˇˇαnα1

ˇˇˇˇλnλ2

ˇˇj

es monotona decreciente (o mejor, no creciente) y acotada superiormente. Sea Kuna cota superior (por ejemplo, K puede tomarse el elemento de la sucesion corres-pondiente a j “ 0). Ası

}xj}2 ď K

ˇˇλ2

λ1

ˇˇj

.

Por otra parte, como βjqj “ v1 ` xj y lımjÑ8xj “ 0 tenemos que lım

jÑ8 βjqj “ v1.

Ademas, la norma es una funcion continua, de modo que lımjÑ8 |βj| “ 1 dado que

}qj}2 “ }v1}2 “ 1. Mas aun,

||βj| ´ 1| “ˇˇ}Ajq0}2|α1λ

j1|´ 1

ˇˇ “ 1

|α1λj1|ˇ}Ajq0}2 ´ |α1λ

j1|ˇ “

“ 1

|α1λj1|ˇ}Ajq0}2 ´ }α1λ

j1v1}2

ˇ ď

ď 1

|α1λj1|}Ajq0 ´ α1λ

j1v1}2 “ }xj}2.

Ası, para j “ 0, 1, 2, . . .

1´ }xj}2 ď |βj| ď 1` }xj}2.


y como xj Ñ 0, para j suficientemente grande 1´}xj}2 ą 0. Supondremos de ahoraen adelante que j es suficientemente grande como para que se cumpla esta condicion.Ahora si zj “ βj

|βj | entonces |zj| “ 1 y

zjqj “ 1

|βj| pv1 ` xjq ď 1

1´ }xj}2 pv1 ` xjq “ˆ

1` }xj}21´ }xj}2

˙v1 ` 1

1´ }xj}2xj.

Por lo tanto, teniendo en cuenta que }v1}2 “ 1,

}zjqj ´ v1}2 ď 2}xj}21´ }xj}2

Para j suficientemente grande 1´ }xj}2 ě 12, por lo que

}zjqj ´ v1}2 ď 4}xj}2.

Finalmente, como }xj}2 ď K

ˇˇλ2

λ1

ˇˇj

, concluımos que

}zjqj ´ v1}2 ď 4K

ˇˇλ2

λ1

ˇˇj

para j suficientemente grande, tal y como se deseaba demostrar.

La condicion suficiente de convergencia del Teorema 10.7 requiere que la matrizA tenga un valor propio dominante en modulo y que para el vector inicial x0 lacomponente de este en la direccion del subespacio propio asociado a dicho valorpropio dominante sea no nula. Ambas condiciones son genericas (es decir, casi todaslas matrices y vectores las cumplen). Ya sabemos que el conjunto de las matrices quetienen valores propios distintos es abierto y denso, de modo que la condicion de tenerun valor propio dominante en modulo es generica salvo que la matriz sea real y tengavalores propios complejos. Esta situacion la analizamos enseguida. En el supuestode que la matriz dada tenga un valor propio dominante en modulo, la eleccion deun vector x0 que no tenga componente nula en la direccion del correspondientesubespacio propio no presenta problemas. Practicamente cualquier vector cumpleesta condicion. Pensemos, por ejemplo, en la siguiente situacion: sabemos que alguienha dibujado dos vectores linealmente independientes en R2 con origen en p0, 0q perodesconocemos que vectores son. ¿Que posibilidades tenemos de dar un vector que seacolineal con uno de ellos? Convendremos inmediatamente que es muy improbable


que escogido un vector al azar, este sea colineal con uno de los vectores dados. Dela misma forma, si escogemos x0 al azar es casi seguro que su componente en ladireccion del subespacio propio asociado al valor propio dominante sea no nula. Unabuena practica consiste en NO tomar x0 un vector con estructura (por ejemplo,x0 “ p1, 0, . . . , 0q) sino al azar.

Si la matriz tiene valores propios complejos aun cuando sus valores propios seandistintos pueden tener igual modulo. Esto es claro si la matriz es real con valorespropios complejos, pero puede suceder, incluso, con matrices complejas. Por ejemplo,la matriz

A =

1.0000 + 1.0000i 0 + 2.0000i 0

0 1.0000 - 1.0000i 0

0 - 1.0000i -3.0000 1.0000

tiene como valores propios:

>> eig(A)

ans =

1.0000

1.0000 + 1.0000i

1.0000 - 1.0000i

Aplicando el metodo de las potencias con vector

>> x0=rand(3,1)

x0 =

0.8147

0.9058

0.1270

produce 4 subsucesiones de “valores propios” que parecen estabilizarse en los valores

1.0000 - 0.6119i, 1.5931 - 0.2490i, 1.0000 - 0.1563i, 0.4069 - 0.2490i


Veamos que este no es un hecho casual. Supongamos que A es diagonalizable y que|λ1| “ |λ2| ą |λ3| ě ¨ ¨ ¨ . Supongamos tambien que λ1 ‰ λ2 y que las componentes, α1

y α2, de x en las direcciones de los vectores propios v1 y v2 no son cero. Supongamosfinalmente que λ1 “ eiθλ2, 0 ă θ ă 2π. Entonces

Akx “ λk2

˜eikθα1v1 ` α2v2 ` α3

ˆλ3

λ2

˙k

v3 ` ¨ ¨ ¨ ` αnˆλnλ2

˙k

vn

¸

Si existe un numero racional p “ t{s tal que θ “ 2πp

entonces hay t subsucesiones de ă Akx ą( que convergen a los subespacios generados por los vectores

e2ksπit α1v1 ` α2v2, k “ 1, . . . , t.

En el ejemplo de arriba 1` i “ e2πi4 p1´ iq, de modo que θ “ 2π

4y t “ 4.

Hay otros casos en los que no cumpliendose la condicion (10.1) todavıa se puedeasegurar la convergencia. Recordemos que A es diagonalizable y supongamos que λ1

es un valor propio semisimple pero λ1 “ λ2 “ ¨ ¨ ¨ “ λr ą |λr`1| ě ¨ ¨ ¨ con r ă no λ1 “ ¨ ¨ ¨ “ λn con |λn| ą 0 (el caso A diagonalizable y λi “ 0 para i “ 1, . . . , nimplica que A “ 0). En estas condiciones

Akx “ λk1

˜rÿ

i“1

αivi `nÿ

i“r`1

αi

ˆλiλ1

˙k

vi

¸

siendo x1 “ α1v1` ¨ ¨ ¨`αrvr la proyeccion de x sobre el subespacio ă v1, . . . .vr ą alo largo de ă vr`1, . . . , vn ą. Como el valor propio λ1 es semisimple de multiplicidadr, resulta que ă v1, . . . .vr ą“ Kerpλ1In ´ Aq. Por lo tanto, si la proyeccion de xsobre Kerpλ1In ´ Aq a lo largo de ă vr`1, . . . , vn ą no es cero, para k “ 0, 1, 2, . . .

existen escalares βk “ 1

λk1(notese que λ1 ‰ 0 porque o bien |λ1| ą ¨ ¨ ¨ ą |λn| ě 0

o λ1 “ ¨ ¨ ¨ “ λn con |λn| ą 0) tales que βkAkx Ñ

rři“1

αivi. Es decir, ă Akx ąÑărři“1

αivi ą. Perorři“1

αivi P Kerpλ1In ´ Aq, de modo que este es un vector propio de

A asociado al valor propio λ1.

Un ultimo aspecto a considerar es el de la velocidad de convergencia cuando estase da. Tal y como comentamos antes de la demostracion del Teorema 10.7, la se-gunda parte de este nos indica que cuando se dan las condiciones de convergencia,


la velocidad a la que los subespacios ă Ajx0 ą convergen al subespacio propio co-rrespondiente al valor propio de mayor modulo es aproximadamente la misma que

la velocidad de convergencia de la sucesion

ˇˇλ2

λ1

ˇˇj

. Si el cociente |λ2|{|λ1| es proximo

a 1 debemos esperar una convergencia lenta y cuanto mas pequeno sea esta razon,la convergencia sera mas rapida. En cualquier caso se trata de una razon de conver-gencia lineal porque depende del cociente |λ2|{|λ1| y no de su cuadrado, o su cubo,etc.

Cuando se pretende calcular un unico valor y vector propio, el metodo de las potenciapuede ser un primer algoritmo para conseguir en unas pocas iteraciones un vectory un valor propio aproximados que puedan servir como valores iniciales para otrosmetodos que convergen mas rapidamente.

10.2.4. Criterios de terminacion del algoritmo

Recordemos que al escribir el algoritmo fuimos muy imprecisos sobre cuando deberıaterminar. Decıamos que se ejecutarıa un bucle para calcular los sucesivos vectoresunitarios propios aproximados y los correspondientes valores propios aproximados“hasta la convergencia”(cuando la haya). Ahora vamos a ser mas precisos.

Un posible criterio de finalizacion del algoritmo podrıa ser cuando la distancia entredos subespacios proximos propios aproximados sea menor que una cantidad previa-mente especificada. Para ello bastarıa almacenar los vectores propios aproximadoscalculados en dos pasos sucesivos, digamos qj y qj`1, y calcular la distancia entreellos utilizando la metrica “gap”. Esto es sencillo porque sabemos que si Xj “ă qj ąy Xj`1 “ă qj`1 ą entonces

ΘpXj,Xj`1q “ }PXj ´ PXj`1}2

siendo PX la proyeccion ortogonal sobre X . Ahora bien como qj y qj`1 son unitarios

PXj “ qjq˚j y PXj`1

“ qj`1q˚j`1.

Ası pues, solo habrıa que modificar el algoritmo para que se ejecutara el calculo de qjhasta que }qjqj ´qj`1qj`1}2 fuera menor que una cantidad previamente especificada.

Nosotros, sin embargo, utilizaremos otro criterio para terminar el algoritmo de laspotencias y todos los que se derivan de el. Este criterio tiene su fundamento en elsiguiente resultado:


Proposicion 10.8 Sea A P Fnˆn, x P Cn un vector unitario y µ P C. Sea r “Ax´ µx. Existe una matriz E P Cnˆn tal que ‖ E ‖F“ }r}2 y pA` Eqx “ µx.

Podemos interpretar este resultado como una especie de “estabilidad hacia atras”.En efecto, esta proposicion dice que los valores-vectores propios aproximados de Ason valores-vectores propios exactos de matrices proximas a A. La demostracion sedeja como ejercicio.

Debe observarse que el error relativo de tomar A` E por A es

}E}F}A}F “

}r}2}A}F

El calculo del residuo r es muy facil en el proceso que define el algoritmo de laspotencias y consideraremos obtenida la convergencia cuando el error relativo }E}F

}A}Fsea menor que una cantidad predeterminada. Es decir, cuando hayamos calculadoun valor-vector propio exactos de una matriz rA tan proxima a A como necesitemos.

Dado que puede no haber convergencia, habra que tomar las precauciones necesariaspor si el error relativo nunca alcanza a ser menor que la cantidad prefijada.

En conclusion, fijaremos un ε ą 0 y un numero maximo de iteraciones y el algoritmoterminara cuando el error relativo sea menor que ε o cuando se sobrepase el numerode iteraciones maximo.

Con todo esto en mente, la version final del algoritmo de las potencias es la siguiente:

10.3 El metodo de iteracion inversa 243

Metodo de las Potencias (Version Final)Datos: A P Fnˆn, x0 P Fn, ε ą 0 e itermax

Objetivo: calcular un par pλ, xq valor-vector propio aproximado de A.El algoritmo devolvera, ademas, el numero de iteraciones iter realizadoası como el residuo en la ultima iteracion.

x “ x0

}x0}2res=1iter=0normA=}A}Fwhile res ą ε¨ normA e iter ă itermax

y “ Ax (siguiente potencia)λ “ x˚y (valor propio aproximado)res=}y ´ λx}2 (residuo)

x “ y

}y}2 (normalizacion)

iter=iter+1end while

10.3. El metodo de iteracion inversa

El objetivo del metodo de iteracion inversa es mejorar la velocidad de convergenciadel metodo de las potencias y posibilitar la obtencion de un valor-vector propioque no se tenga que corresponder necesariamente con el valor propio dominante. Separte de la siguiente observacion: si λ0 es un valor propio de A P Fnˆn y ppλq “pdλ

d ` pd´1λd´1 ` ¨ ¨ ¨ ` p1λ ` p0 es un polinomio cualquiera entonces ppλ0q es un

valor propio de la matriz

ppAq “ pdAd ` pd´1A

d´1 ` ¨ ¨ ¨ ` p1A` p0In.

En efecto, si v es un vector propio de A para λ0 entonces Av “ λ0v y Ajv “ λj0v.Por lo tanto

ppAqv “ pdAdv ` pd´1A

d´1v ` ¨ ¨ ¨ ` p1Av ` p0v ““ pdλ

d0v ` pd´1λ

d´10 v ` ¨ ¨ ¨ ` p1λ0v ` p0v “

“ ppλ0qv.


Es decir, v es tambien vector propio de ppAq para ppλ0q. Se prueba de forma similarque si ppAq es invertible entonces ppλ0q´1 es valor propio de ppAq´1 y v es vectorpropio de esta matriz para dicho valor propio:

ppAqv “ ppλ0qv ô v “ ppλ0qppAq´1v ô ppλ0q´1v “ ppAq´1v.

En particular si σ R ΛpAq entonces σIn ´ A es invertible y λ0 P ΛpAq si y solo si1

σ ´ λ0

P ΛppσIn ´ Aq´1q. Por lo tanto, si λ1,. . . ,λn son los valores propios de A

entonces los valores propios de pσIn ´ Aq´1 son

µ1 “ 1

σ ´ λ1

, . . . µn “ 1

σ ´ λn

El metodo de iteracion inversa es el metodo de las potencias aplicado a la matrizpσIn ´Aq´1 para algun numero σ. A este numero se le suele llamar desplazamientoo precondicionamiento y se suele usar para aumentar la velocidad de convergenciadel metodo de las potencias y para obtener un valor-propio particular de la matriz Acuando se tiene un cierto conocimiento de ellos. Veamos como se hace. Supongamosque por el medio que sea conocemos un valor propio aproximado rλ0 « λi de A (porejemplo con una o dos cifras decimales de precision) pero λi no tiene por que ser el

valor propio dominante de A. Tomamos σ “ rλ0 de modo que σ « λi y σ es muydiferente de los demas valores propios de A. Esto significa que

|µ1| “ˇˇ 1

σ ´ λi

ˇˇ ąą µj “

ˇˇ 1

σ ´ λj

ˇˇ

(ąą significa ”mucho mayor”) para todo valor propio λj de A distinto de λi. Siaplicamos el metodo de las potencias a pσIn ´ Aq´1 tenemos que si |µ2| ě |µ3| ě¨ ¨ ¨ ě |µn| entonces la velocidad de convergencia serıa del orden de

ˇˇµ2

µ1

ˇˇk

, tanto

mas grande cuanto mas proximo este σ a λi. En estas condiciones el metodo delas potencias aplicado directamente a pσIn ´ Aq´1 proporcionarıa, supuesto queconverja, un valor-vector propio de esta matriz; digamos, µ1 y v1. Pero, tal y comohemos visto mas arriba v1 serıa tambien un vector propio de A para λi y podemosusar este vector propio para calcular directamente el valor propio de A: λi “ v1Av1.En otras palabras, modificaremos el metodo de las potencias para, haciendo uso delos vectores propios unitarios aproximados qj, obtener valores propios aproximadosde A en la forma qjAqj.

10.3 El metodo de iteracion inversa 245

Hay otra modificacion en la implementacion del metodo de iteracion inversa respectodel de las potencias. El primer paso en el algoritmo del metodo de las potenciasconsiste en calcular qj`1 “ Aqj. Si lo aplicamos directamente a la matriz pσInÁq´1

habrıa que hacer qj`1 “ pσIn Áq´1qj. En vez de calcular la inversa, lo que se hacees resolver el sistema

pσIn ´ Aqqj`1 “ qj.

Ambas operaciones son teoricamente equivalentes pero la segunda requiere menosoperaciones. De hecho, genericamente σIn ´ A admite una descomposicion LU queconviene calcular de una vez por todas y usar solo sustituscion hacia delante y haciaatras para resolver el sistema pσIn ´ Aqqj`1 “ qj. En nuestra implementacion delalgoritmo, y puesto que practicaremos con MATLAB, dejaremos que sea este quiense encargue de resolver este sistema. Para ello usaremos la orden qj`1 “ pσInÁqzqj.Se podrıa argumentar que en cualquier caso la mariz σIn ´ A esta tanto mas cercade ser singular cuanto mas cerca σ de un valor propio exacto de A, y que esto haceque los errores de redondeo se magnifiquen tanto si se calcula la inversa como si seresuelve el sistema. En efecto es ası y a pesar de todo, el algoritmo converge. ¿Porque?

La respuesta a esta cuestion esta en el analisis del error en el algoritmo que se empleepara resolver los sistemas linales. Si este algoritmo es estable hacia atras (como porejemplo lo es para casi todas las matrices el de la eliminacion gaussiana), la solucioncalculada para el sistema (pσIn ´ Aqy “ x es la solucion exacta de algun sistemapσIn ´ A ` Eqy “ x conde el error relativo }E}F {}A}F es del orden del epsilon dela maquina. Si el valor-vector propio (“exacto”) que estamos buscando esta biencondicionado, sera muy parecido al de pσInÁÈq y la sucesion de valores-vectorspropios calculados seguira convergiendo hacia una valor-vector propio de σIn ´ A.

Dicho de otra manera mas intuitiva, la mayor parte de las veces la propagacion delerror juega a nuestro favor porque cuando σ esta muy cerca de un valor propio deA, el vector y se calcula, en efecto, de manera inexacta pero, tal y como vimos enla demostracion del Teorema 10.7,

pσIn ´ Aq´kq0 “ α1

pσ ´ λ1qk v1 ` α2

pσ ´ λ2qk v2 ` ¨ ¨ ¨ ` αnpσ ´ λnqk vn.

Esto significa que cuanto mas proximo este σ a λ1 mayor sera la componente depσInÁq´kq0 en la direccion de v1, de manera que los errores en el redondeo redundanen una potenciacion de la direccion en la que queremos que converjan los subespacios


propios aproximados. De hecho, si σ y λ1 son casi iguales, una sola iteracion nosproporciona un vector que es ya casi un vector propio porque la proyeccion espectralde este sobre el subespacio ă v2, . . . , vn ą es insignificante en comparacion con laproyeccion espectral sobre ă v1 ą.

En resumen, el algoritmo para el metodo de iteracion simultanea es el siguiente:

Metodo de Iteracion Inversa (Primera Version)Datos: A P Fnˆn, x0 P Fn, σ, ε ą 0 e itermax

Objetivo: calcular un par pλ, xq valor-vector propio aproximado de A.

x “ x0


y “ pσIn ´ Aqzx (ô pA´ σInqy “ x)

x “ y

}y}2 (vector propio unitario aproximado)

λ “ x˚Ax (valor propio aproximado)res=}λx´ Ax}2 (nuevo residuo)iter=iter+1

end while

Hay algunas mejoras que se pueden introducir en el algoritmo a fin optimizar elnumero de operaciones evitando sucesivas multiplicaciones de A por x, que es laparte mas costosa. Concretamente, en la notacion del algoritmo representamos conel mismo sımbolo x dos numeros diferentes en las dos primeras lıneas del buclewhile. Vamos a mantener el sımbolo x para el primero; i.e.

y “ pσIn ´ Aq´1x

y con px su actualizacion:

px “ y

}y}2 .De esta forma

pσIn ´ Aqpx “ pσIn ´ Aqy}y}2 “ x

}y}2 .

10.4 El metodo del cociente de Rayleigh 247

Pongamos w “ x

}y}2 . Entonces

λ “ px˚Apx “ σ ´ px˚pσIn ´ Aqpx “ σ ´ ρcon

ρ “ px˚pσIn ´ Aqpx “ px˚w.Finalmente el residuo es

r “ λpx´ Apx “ pσIn ´ Aqpx´ ρpx “ w ´ ρpx.

Con todo esto en mente el algoritmo de iteracion inversa queda como sigue:

Metodo de Iteracion Inversa (Version Final)Datos: A P Fnˆn, x0 P Fn, σ, ε ą 0 e itermax


x “ x0


y “ pσIn ´ Aqzxw “ x

}y}2x “ y

}y}2ρ “ x˚wλ “ σ ´ ρres=}w ´ ρx}2iter=iter+1

end while

10.4. El metodo del cociente de Rayleigh

El metodo del cociente de Rayleigh es exactamente igual que el de iteracion inversapero con un desplazamiento que varıa en cada iteracion. La cuestion es ¿como elegir


el desplazamiento para hacer que el residuo sea lo mas pequeno posible en cadaiteracion? La respuesta es sencilla porque se trata de calcular la solucion de unproblema de mınimos cuadrados lineal. Recordemos que el residuo es

r “ }λx´ Ax}

donde λ y x son el valor y vector unitario propios aproximados que se calculan encada iteracion. Puesto que λ es un valor propio aproximado (que esta variando encada iteracion) bien podemos hacer uso de el en cada iteracion. La pregunta es ¿cuales el valor de λ que hace mınimo el residuo? Nos preguntamos por el problema dehallar

mınαPF }αx´ Ax}2

Debe observarse que en este problema la matriz de coeficientes es x (n ˆ 1) y elvector de terminos independientes es Ax (tambien n ˆ 1). Recordemos que unaforma resolver el problema de mınimos cuadrados mınyPFn }By ´ c}2 con B P Fmˆny c P Fmˆ1 es resolviendo el sistema de ecuaciones normales: B˚By0 “ B˚c. Ennuestro caso el sistema de ecuaciones normales es

x˚xα0 “ x˚Ax

Por lo tanto

α0 “ x˚Axx˚x

es el numero que minimiza el residuo.

Definicion 10.9 Para A P Fnˆn se llama cociente de Rayleigh de A en x P Fn alnumero

Rpxq “ x˚Axx˚x

Ası pues, lo que hemos demostrado mas arriba es

Teorema 10.10 Si A P Fnˆn y x P Fn entonces el cociente de Rayleigh de A en xes el numero donde se alcanza el mınimo del residuo }αx´ Ax}2. Es decir

mınαPF }αx´ Ax}2 “ }Rpxqx´ Ax}2.

10.4 El metodo del cociente de Rayleigh 249

En la practica, el algoritmo del cociente de Rayleigh consiste en sustituir σ por λ enel algoritmo de iteracion inversa iniciando el primer desplazamiento con el cocientede Rayleigh de la matriz dada en el vector inicial elegido. Notese que puesto quelos vectores propios aproximados son unitarios, el denominador en el cociente deRayleigh es siempre 1.

Metodo del cociente de RayleighDatos: A P Fnˆn, x0 P Fn, ε ą 0 e itermax


x “ x0

}x0}2λ “ x˚Ax

res=1iter=0normA=}A}Fwhile res ą ε¨ normA e iter ă itermax

y “ pλIn ´ Aqzxw “ x

}y}2x “ y

}y}2ρ “ x˚wλ “ λ´ ρres=}w ´ ρx}2iter=iter+1

end while

Aunque en esta forma de implementar el algoritmo no lo parezca, resulta que λ “Rpxq en cada iteracion. Para verlo basta deshacer los cambios que hicimos en elalgoritmo de iteracion inversa. En efecto, al igual que en aquel caso denotamos conpx y pλ los valores actualizados y con x y λ los que entran en la iteracion. Debemosver que pλ “ Rppxq “ px˚Apx. Para ello, en la iteracion pλ “ λ´ ρ. Entonces

pλ “ λ´ ρ “ λ´ px˚w “ λ´ y˚

}y}2x

}y}2 “ λ´ y˚pλIn ´ Aqyy˚y

“

“ λ´ λy˚yy˚y

` y˚Ayy˚y

“ px˚Apx.


En los ejercicios veremos que, en general, la convergencia del metodo del cociente deRayleigh sigue siendo lineal, pero si la matriz es simetrica es, al menos, cuadratica.Ello es debido al siguiente resultado, que se conoce con el nombre de propiedadestacionaria de los vectores propios de las matrices simetricas.

Teorema 10.11 Sea A P Rnˆn una matriz simetrica. Entonces pλ0, x0q es un valor-vector propio de A si y solo si x0 es un punto estacionario o crıtico de Rpxq yRpx0q “ λ0. Esto es,

∇Rpx0q “ 0 y Rpx0q “ λ0

donde ∇Rpxq es el gradiente de Rpxq.

Demostracion: Debemos demostrar que pλ0, x0q es un valor-vector propio de A si

y solo siBRBxi px0q “ 0, i “ 1, . . . , n y Rpx0q “ λ0. En el caso real Rpxq “ xTAx

xTx.

Calculamos primeroBpxTAxqBxi y luego haremos lo mismo con xTx. En primer lugar

xTAx “nÿ

j,k“1

ajkxjxk,

ası que

BpxTAxqBxi “

nÿ

k“1

aikxk `nÿ

j“1

ajixj.

Como A es simetrica, aji “ aij y entonces

BpxTAxqBxi “ 2

nÿ

j“1

aijxj “ 2pAxqi

siendo pAxqi la i-esima componente del vector Ax.

De la misma forma xTx “nřj“1

x2j y

BpxTxqBxi “ 2xi.

10.5 El algoritmo QR con desplazamiento explıcito 251

Por lo tanto

BRBxi “ 2pxTxqpAxqi ´ 2pxTAxqxi

pxTxq2 “ 2

xTx

ˆpAxqi ´ xTAx

xTxxi

˙“

“ 2

xTxppAxqi ´Rpxqxiq “ 2

xTxpAx´Rpxqxqi

donde pAx ´ Rpxqxqiq es la i-esima componente del vector Ax ´ Rpxqx. Ahora esclaro que ∇Rpx0q “ 0 y Rpx0q “ λ0 si y solo si Ax0 ´ λ0x0 “ 0; i.e., pλ0, x0q es unvalor-vector propio de A.

Tal y como habıamos anunciado una consecuencia interesante de este Teorema es

Corolario 10.12 Si para una matriz simetrica A y un vector q0 el algoritmo delcociente de Rayleigh converge, lo hace, a partir de un cierto momento, cuadratica-mente.

Demostracion: Ya sabemos que si el algoritmo del cociente de Rayleigh converge, lohace a un valor-vector unitario propios, pλ0, x0q, de A. Es decir, el algoritmo produceuna secuencia pλk, αkqkq de valores-vectores propios aproximados de A que convergea pλ0, x0q. Pero λk “ Rpαkqkq y desarrolando Rpxq en serie de Taylor alrededor dex0 tenemos que

Rpxq ´Rpx0q “ ∇Rpx0qpx´ x0q `Op}x´ x0}2q “ Op}x´ x0}2qpor ser x0 un vector propio de A. Esto implica que para k suficientemente grandeRpαkqkq ´ Rpx0q “ Op}qk ´ x0}2q. Como ă qk ą converge a ă x0 ą linealmente(al menos), el residuo converge a cero, a partir de ese k suficientemente grande,cuadraticamente (al menos).

10.5. El algoritmo QR con desplazamiento explıci-

to

Todos los algoritmos tienen como objetivo ultimo reducir una matriz dada A PFnˆn, a una forma de Schur (real o compleja) para extraer de ahı la informacioncorrespondiente a los valores y vectores propios. La finalidad de los que hemos visto


hasta ahora era obtener un vector propio unitario (siempre que se den las condicionesapropiadas) y a partir de ahı, usando el cociente de Rayleigh, el correspondiente valorpropio. Este es el primer paso para obtener la forma de Schur compleja porque, taly como mostramos en la demostracion del Teorema de Schur, una vez obtenidos,

digamos pλ1, q1q, se puede construir una matriz unitaria, digamos Q “”q rQ

ı, para

la que

Q˚AQ “„λ1 b˚

0 B

.

A continuacion se aplica el algoritmo correspondiente a B y ası sucesivamente. Esteproceso de ir aplicando el algoritmo a matrices cada vez mas pequenas se llama de-flacion. Si se dan las condiciones apropiadas (valores propios con modulos diferentesy proyeccion espectral no nula sobre los correspondientes subespacios propios) el re-sultado de este proceso de deflacion es una matriz triangular superior unitariamentesemejante a A; i.e., una forma de Schur de A.

El algoritmo QR comparte el mismo objetivo: reducir A a una forma de Schur. Laforma en que este proceso se lleva a cabo, sin embargo, parece no tener nada quever con los algoritmos que hemos visto hasta ahora. Esta es la primera version delalgoritmo QR con desplazamiento explıcito:

Dada A P FnˆnA0 “ A

for k “ 0, 1, 2, . . . hasta convergenciaElıjase un desplazamiento σkCalculese la descomposicion QR de Ak ´ σkIn: Ak ´ σkIn “ QkRk

Reviertanse los factortes: Ak`1 “ RkQk ` σkInend for

En resumen, el algoritmo construye una sucesion de matrices tAku a partir de unadada A “ A0 calculando la factorizacion QR de Ak ´ σkIn (para un σk que se eligeexplıtamente en cada paso) y definiendo la siguiente matriz de la sucesion, Ak`1,multiplicando los factores Q y R al reves y anadiendo el desplazamiento. ¿Por quehacer tal cosa produce algo significativo en relacion con el calculo de los valores yvectores propios de A? La historia empieza con John Francis y Eva Kublanovskayaque lo desarrollaron independientemente hacia 1959 en Inglaterra y la extinta UnionSovietica. Se tardo muchos anos, sin embargo, en comprenderlo bien. La razon de por


que este algoritmo calcula valores y vectores propios de A es, esencialmente, porquees una forma elegante de implementar el algoritmo del cociente de Rayleigh y, cuandose toma desplazamiento σk “ 0 (algoritmo QR a secas, sin desplazamiento), entoncescalcula las mismas matrices que el algoritmo de iteracion simultanea (u ortogonal)que es una generalizacion del algoritmo de las potencias. En este curso solo veremosla relacion entre el algoritmo QR con desplazamiento explıcito y el del cociente deRayleigh. Pero antes de nada es importante observar que todas las matrices en lasucesion tAku que construye el algoritmo son unitariamente semejantes.

Lema 10.13 Las matrices Ak que construye el algoritmo QR con desplazamientoexplıcito son todas unitariamente semejantes.

Demostracion: Para un k “ 0, 1, 2, . . . arbitario, supongamos dada Ak y veamosque Ak`1 es unitariamente semejante a Ak. Esto demuestra que todas las matricesde la sucesion son unitariamente semejantes. Sea Ak´σkIn “ QkRk la factorizacionQR de Ak ´ σkIn.

Ak`1 “ RkQk ` σkIn “ QkpAk ´ σkInqQk ` σkIn pRk “ QkpAk ´ σkInq“ QkAkQk ´ σkQkQk ` σkIn “ QkAkQk,

por lo que Ak`1 y Ak son unitariamente semejantes.

Este Lema tiene una consecuencia importante: Para cada k “ 1, 2, . . .

Ak “ Q˚k´1Ak´1Qk´1 “ Q˚k´1Q˚k´2Ak´2Qk´2Qk´1 “ ¨ ¨ ¨ “ Q˚k´1 ¨ ¨ ¨Q˚0A0Q0 ¨ ¨ ¨Qk´1

Es decir, el algoritmo QR no solo proporciona una sucesion de matrices unitaria-mente semejantes a A sino que nos da tambien la matriz unitaria que conecta Acon cada una de las matrices de la sucesion: es el producto de los factores Q en lafactorizacion QR de Ak ´ σkIn. Si para algun valor de k la matriz Ak es (casi) unaforma de Schur de A tendremos ademas la matriz unitaria que convierte A en dicha(casi) forma de Schur.

10.5.1. El algoritmo QR y el cociente de Rayleigh

Para ver que el algoritmo QR converge en las mismas condiciones que el algoritmodel cociente de Rayleigh vamos a ver que ambos son esencialmente lo mismo. En


realidad el algoritmo QR aplica el metodo del cociente de Rayleigh para calcularvectores propios por la izquierda en vez de hacerlo para calcular vectores propiospor la derecha. ¿Como serıa el metodo del cociente de Rayleigh en este caso? Igualque el ya visto pero operando con vectores filas: Dada A, un vector fila inicial x0 elalgoritmo del cociente de Rayleigh consta de 4 pasos para j “ 1, 2, . . .:

1. Elegir un desplazamiento σj, que es el cociente de Rayleigh de la iteracionanterior,

2. Resolver el sistema yj pA´ σjInq “ xj´1,

3. Normalizar xj “ yj}yj}2 (vector propio aproximado por la izquierda), y

4. Calcular el nuevo cociente de Rayleigh λj “ xjAxj (nuevo valor propio apro-ximado)

Cuando el algoritmo converge lo hace a un valor-vector propio unitario por la iz-

quierda pλ, qq de A. Con este q podemos formar una matriz unitaria Q “”pQ q

ı

de forma que (vease la Seccion 9.4 del Capıtulo 9 sobre vectores propios por laizquierda)

Q˚AQ “„B b0 λ

Ahora procederıamos por deflacion aplicando el algoritmo por filas a B y ası suce-sivamente.

Supongamos ahora que hacemos una sola iteracion del algoritmo del cociente deRayleigh por filas con vector inicial x0 “ en. El desplazamiento inicial serıa

e˚nAen “ σ.

Sea q el vector unitario que obtenemos al aplicar esta iteracion (quitamos los subındi-ces porque solo hablamos de una iteracion y por comodidad):

q˚ “ enpA´ σInq´1

}enpA´ σInq´1}2 (10.3)

Analicemos una iteracion del algoritmo QR con el mismo desplazamiento σ “ enAen.Calculamos la descomposicion QR de A´ σIn:

A´ σIn “ QR.


EntoncesQ˚ “ RpA´ σInq´1

ye˚nQ

˚ “ e˚nRpA´ σInq´1 “ rnne˚npA´ σInq´1.

Ahora bien, enQ˚ es la ultima fila de Q˚. Denotemosla por rq˚. Este vector es unitario

y acabamos de ver querq˚ “ rnne

˚npA´ σInq´1.

De aquı deducimos (recordamos que los elementos diagonales de R son numerosreales positivos)

rnn “ 1

}enpA´ σInq´1}2 ,

y en consecuencia, comparando con (10.3)

q “ q.

En palabras: la ultima fila de la matriz Q en la factorizacion QR de A ´ σIn conσ “ enAen coincide con el vector propio por la izquierda unitario aproximado, q, deA que calcula el metodo del cociente de Rayleigh cuando se emplea en como vectorinicial en la primera iteracion . Es decir,

Q “”rQ q

ı(10.4)

El valor propio aproximado que nos proporciona el cociente de Rayleigh sera rλ “q˚Aq y el residuo (recordemos que estamos calculando vectores propios por la izquier-

da) r˚ “ q˚A ´ rλq˚. Estos calculos concluyen la iteracion del metodo del cocientede Rayleigh.

Respecto al algoritmo QR con desplazamiento, la segunda y ultima etapa consisteen calcular la siguiente matriz en la sucesion revirtiendo los factores Q y R de lafactorizacion QR de A y sumando el desplazamiento:

pA “ RQ` σIn “ Q˚pA´ σInqQ` σIn “ Q˚AQ.

Escribiendo Q como en (10.4)

pA “„ rQ˚q˚

A”rQ q

ı“«rQ˚A rQ rQ˚Aqq˚A rQ q˚Aq

ff


Ahora bien, q˚Aq “ rλ y q˚A “ r˚ ` rλq˚. Por ello, teniendo en cuenta que q esortogonal a todas las columnas de rQ,

q˚A rQ “ r˚ rQ` rλq˚ rQ “ r˚ rQy

}q˚A rQ}22 “ }r˚ rQ}22 “ r˚ rQ rQ˚r. (10.5)

Nuestro objetivo es demostrar que }q˚A rQ}2 “ }r˚}2. Para ello debemos recordar

el Teorema 10.10. De acuerdo con este Teorema, rλ es la solucion del problema demınimos cuadrados consistente en calcular el numero complejo, α, que hace mınimala distancia αq˚ ´ q˚A. Es decir,

}r˚}2 “ }rλq˚ ´ q˚A}2 “ mınαPC }αq

˚ ´ q˚A}2.Recordemos tambien (Teorema 8.3 del Capıtulo 7) que para el problema de mınimoscuadrados mın

yPCn }By´c}2, y0 es una solucion si y solo si By´c P pImBqK. En nuestro

caso, debe suceder que r˚ “ rλq˚ ´ q˚A P pIm q˚qK o equivalentemente q˚r “ 0. Es

decir, r P Im rQ. Con esto en mente, podemos demostrar que }q˚A rQ}2 “ }r˚}2. Enefecto, por (10.5)

}q˚A rQ}22 “ r˚ rQ rQ˚r,pero rQ rQ˚ es la proyeccion ortogonal sobre Im rQ y r P Im rQ; por lo tanto rQ rQ˚r “ ry }q˚A rQ}22 “ r˚r “ }r˚}22 tal y como deseabamos demostrar. En definitiva

pA “«rQ˚A rQ rQ˚Aqq˚A rQ rλ

ff

y }q˚A rQ}2 “ }r˚}2 siendo r “˚“ q˚A´ rλq˚ es el residuo del algoritmo del cocientede Rayleigh aplicado por filas a la matriz A con vector inicial en. En conclusion

Teorema 10.14 Para una matriz A P Fnˆn el algoritmo QR con desplazamientoexplıto σk “ enAken produce una sucesion de matrices tAkukě0 tales que si pa-

ra k “ 0, 1, 2, . . ., apkqn “

”apkqn1 ¨ ¨ ¨ a

pkqnn´1 a

pkqnn

ıes la ultima fila de Ak, Ak “

Qk´1Ak´1Qk´1 y qpk´1q˚n es la ultima fila de Qk´1 entonces papkqnn , qpk´1q˚

n q es el valor-vector propio unitario por la izquierda aproximados que produce el algoritmo delcociente de Rayleigh aplicado a Ak´1 con vector inicial en. Ademas la norma del

vector”apkqn1 ¨ ¨ ¨ a

pkqnn´1

ıes igual a la norma del residuo producido por el algoritmo

del cociente de Rayleigh.


Este resultado nos indica que si el algoritmo del cociente de Rayleigh converge parala matriz A con vector inicial en entonces usando como desplazamiento explıcito elelemento en la posicion pn, nq de la matriz obtenida en cada iteracion, el algoritmoQR con estos desplazamientos produce una sucesion de matrices que converge a unamatriz con la forma

„B c0 λ

siendo λ un valor propio de A. Ademas , el vector formado por los elementos dia-gonales de la ultima fila de la matriz producida en cada iteracion tiene la mismanorma que el residuo producido por el algoritmo del cociente de Rayleigh. Podemosusar como criterio para terminar el proceso iterativo que la norma de este vectorsea menor que una cantidad previamente especificada. Una vez obtenido un vectorsuficientemente pequeno sustituirıamos los elementos no diagonales de la ultima filapor cero y procederıamos a deflactar la matriz hasta obtener, si hay convergencia,una matriz en forma de Schur. El proceso, ademas, produce las matrices unitariasde paso.

El algoritmo en cada etapa serıa el siguiente:

Una etapa del algoritmo QRDatos: A P Fnˆn, ε ą 0 e itermax

Objetivo: Obtener una matriz T , semejante a A, cuyos elementos en la ultimafila sean todos cero excepto el de la diagonal, y la matriz unitaria de semejanzaQ.

normA=}A}FT “ A, Q “ Ind “ T pn, 1 : n´ 1q, iter=0while }d}2 ą ε¨ normA e iter ă itermax

s “ T pn, nq (desplazamiento)T ´ sIn “ Q1R1 (factorizacion QR de T ´ sIn)T “ R1Q1 ` sIn (revertimos los factores)d “ T pn, 1 : n´ 1q (nuevos elementos no diagonales)Q “ QQ1 (actualizamos la matriz unitaria de paso)iter=iter+1

end while


if iterăitermaxT pn, 1 : n´ 1q “ 0 (para que quede bonito)

end if

10.5.2. Analisis de la velocidad de convergencia del algorit-mo QR

Para analizar la velocidad de convergencia del algoritmo QR vamos a determinaruna cota de }apk`1q

n }2 en terminos de }apkqn }2. Para no arrastrar los subındices todo

el rato, vamos a poner A “ Ak y pA “ Ak`1. La notacion sera similar al referirnosa los diversos elementos y matrices relacionados con Ak y Ak`1. Ası, pondremosA´ σIn “ QR y pA´ σIn “ RQ.

Consideremos A, Q y R particionadas como sigue:

A´ σIn “„B ´ σIn´1 h

g˚ µ´ σ“„P fe˚ π

„S r0 ρ

“ QR. (10.6)

Entonces

pA´ σIn “„ pB ´ σIn´1

phpg˚ pµ´ σ

“„S r0 ρ

„P fe˚ π

. (10.7)

El objetivo es acotar pg en funcion de g.

En primer lugar, como Q es unitaria, la norma de cada una de sus filas y columnases 1. En particular, }e}22 ` |π|2 “ }f}22 ` |π|2, de donde concluimos que

}e}2 “ }f}2.Por otra parte, en (10.6)

g˚ “ e˚S.

Suponiendo que S es no singular y δ “ }S´1}2, tenemos que

}e}2 ď δ}g}2.Ahora como Q es unitaria, despejando R en (10.6) obtenemos

„S r0 ρ

“„P ˚ ef˚ π

„B ´ σIn´1 h

g˚ µ´ σ.


De aquı sacamos que ρ “ f˚h ` πpµ ´ σq. Como |π| ď 1, }e}2 “ }f}2, }e}2 ď δ}g}2y, por la desigualdad de Cauchy-Schwarz, |f˚h| ď }f}2}h}2:

|ρ| ď δ}g}2}h}2 ` |µ´ σ|.Finalmente de (10.7) obtenemos pg˚ “ ρe˚. Poniendo todo junto y teniendo en cuenta,otra vez, que }e}2 ď δ}g}2 concluımos

}pg}2 ď δ2}h}2}g}22 ` δ|µ´ σ|}g}2,o, con los subındices restaurados,

}gk`1}2 ď δ2k}hk}2}gk}22 ` δk|µk ´ σk|}gk}2.

Notemos finalmente que para todo k “ 1, 2, . . . }hk}2 ď }A}2. En efecto, todas lasmatrices Ak que se van construyendo mediante el algoritmo QR son unitariamentesemejantes (Ak`1 “ QkAkQk), de modo que }Ak}2 “ }A}2. Pero

}hk}22 ď }hk}22 ` |µ|2 “ }Aken}22 ď }Ak}22}en}22 “ }Ak}22.En conclusion, existe un numero real η ą 0 tal que }hk}2 ď η para todo k “ 1, 2, . . ..Entonces

}gk`1}2 ď ηδ2k}gk}22 ` δk|µk ´ σk|}gk}2. (10.8)

Lo primero que sugiere esta expresion es, tal y como ya hemos deducido al compararlos algoritmos QR y cociente de Rayleigh, que el desplazamiento apropiado en cadaiteracion es σk “ µk porque esta eleccion proporciona una cota de gk`1 en terminosdel cuadrado de }gk}2. En tal caso, la cota queda

}gk`1}2 ď ηδ2k}gk}22

Vamos a suponer que existe un numero real δ ą 0 tal que para todo k “ 1, 2, . . .

}S´1k }2 ď δ.

Se puede demostrar que, de hecho, esta propiedad es verdadera para valores de gksuficientemente pequenos.

En estas condiciones}gk`1}2 ď δ2η}gk}22.


Ası pues, cuando el algoritmo QR converge a un valor propio simple y }S´1k }2 ď δ

para todo k, la norma de gk`1 esta acotada por una cantidad que es proporcionalal cuadrado de la norma de gk. Se dice que la sucesion t}gk}2u converge cuadratica-mente, al menos, a cero.

Tal y como ya hemos dicho la condicion }S´1k }2 ď δ se cumple para valores de gk

suficientemente pequenos, ası que no podemos decir que la convergencia es siemprecuadratica. Al principio puede no serlo, pero llegara un momento en el que lo sera conseguridad. Se dice que la convergencia del algoritmo QR es localmente cuadratica.

La convergencia cuadratica es muy conveniente porque, una vez que empieza, esmuy rapida. Para hacernos una idea, si δ2η “ 1 y }g0}2 “ 10´1, entonces

}g1}2 ď 10´2

}g2}2 ď 10´4

}g3}2 ď 10´8

}g4}2 ď 10´16

Cuatro iteraciones bastan para reducir el error por debajo de la unidad de redondeopara la doble precision.

Si A fuera hermıtica, entonces tambien lo serıan cada una de las Ak (Recordemosque Ak “ Qk´1Ak´1Qk´1). En particular tendrıamos que hk “ gk, de modo quepodemos reemplazar η por }gk}2 y la acotacion serıa

}gk`1}2 ď δ2}gk}32.Este tipo de convergencia se llama cubica.

Observaciones 10.15 El analisis de la convergencia que hemos hecho es local; estoes, se supone que gk es suficientemente pequeno (o, equivalentemente, µk suficien-temente proximo a un valor propio). No hay teoremas para la convergencia globaldel algoritmo QR aplicables a cualquier matriz. El comportamiento tıpico del al-goritmo parece ser el siguiente: se consumen unas cuantas iteraciones en las que laconvergencia puede ser muy lenta o parecer, incluso, que no hay convergencia y enun momento dado empıeza la convergencia de manera muy rapida. Para el calculode los siguientes valores propios se necesitan cada vez menos iteraciones. La razonde esta ultima caracterıstica del comportamiento del algoritmo QR se puede expli-car, al menos parcialmente, por la relacion entre este algoritmo y el del metodo deiteracion ortogonal o simultanea que no abordaremos en este curso.

10.6 Consideraciones finales 261

10.6. Consideraciones finales

Hay muchas mas cosas que decir sobre el algoritmo QR. En particular, su relacioncon el algoritmo de iteracion simultanea, que es una generalizacion del metodo delas potencias, es muy importante porque sirve para establecer condiciones suficientesde convergencia. Otro aspecto importante es la relacion entre el algoritmo QR y lareduccion a forma Hessenberg y, en general, la implementacion practica del algoritmoQR (algoritmo QR con desplazamiento implıcito). Tambien es importante la eleccionde los desplazamientos y la reduccion a forma de Schur real cuando la matriz es real.Genericamente las matrices complejas tienen valores propios distintos en modulo,pero esto no es verdad para las matrices reales en las que cuando aparecen valorespropios complejos estos vienen conjugados a pares. Es por eso que la reduccion aforma de Schur real es tan importante para estas matrices.

De vez en cuando surgen tipos de matrices para las que el algoritmo QR con losdesplazamientos conocidos no converge. Lo habitual en tales casos es anadir nuevosdesplazamientos a la lista de los ya conocidos. Sin embargo, por ahora no hay unalgoritmo universal eficiente para todas las matrices.

Finalmente, los algoritmos para el calculo de los valores propios no terminan conel algoritmo QR aunque este sea el algoritmo de proposito general que mas se uti-liza. Para matrices con estructura existen algoritmos especiales. Por ejemplo, paramatrices simetricas o hermıticas que son unitariamente diagonalizables ademas delalgoritmo QR existen otros que aprovechan la estructura de estas matrices. Otrocaso es el de las matrices con muchos elementos iguales a cero (sparse matrices eningles). Los algoritmos para el calculo de valores propios han sido y sigue siendo uncampo de mucha actividad investigadora.

cap tulo 10 el problema de valores propios - ehu.eus · en algebra lineal numerica se suele hablar...

Documents