Post on 02-Jun-2020
transcript
El método es utilizado para determinar el autovalor dominante de una matriz.
Tambieén es posible hacer una aproximacioón a su autovector asociado.
Utilizando la matriz inversa, se puede obtener el autovalor de míónimo moó dulo y su autovector asociado.
A su vez, con otras variaciones se pueden obtener otros autovalores.
Dada una matriz A, la matriz debe ser:
•De coeficientes reales o, si tiene coeficientes complejos, debe ser hermíótica.
•Debe tener una base de autovectores linealmente independiente (ser diagonalizable).*
Supongo que tiene un autovalor dominante.
|λ1|>|λ
2|≥.....≥|λ
n-1|≥|λ
n|
*Tambieén se puede realizar el método con matrices no diagonalizables usando la forma de Jordan.
Sea la base de autovectores linealmente independiente: {v(0),v(1),v(2),....,v(n)}Sea x
0 un vector cualquiera de ℝn (oó ℭn)
entonces
x0=∑β
jv(j) j=1,...,n si multiplico por A
Ax0=∑β
jAv(j)=∑β
jλjv(j) si multiplico por A
A2x0=∑β
jAλ
jv(j)=∑β
j(λ
j)2v(j) luego...
Ak x0=∑β
j(λ
j)kv(j) Tengo una sucesioón
xk=Ax
k-1 k=1,2,3....,n
despejando λ1 obtengo
xk=Akx
0=(λ
1)k(∑β
j(λ
j/λ
1)kv(j))
Como tengo que |λ1|>|λ
i| ∀i 1<i≤n
, líóm(λj/λ
1)k=0 y,
k→∞ líóm Akx0 =líóm (λ
1)kβ
1v(1)
, k→∞ k→∞
(A condicioó n de que β1≠0) luego
(1/λ1)kx
k=β
1v(1)+O(|λ
2/λ
1|k) (1)
El radio de convergencia es lineal yEs igual a |λ
2|/|λ
1| , x
k converge al autovector
asociado a λ1
Para asegurarnos que la sucesioón converja a un líómite finito distinto de 0, debemos normalizar el vector inicial x
0
Asó asumimos que ||x
0||∞=1, x
k=Ax
k-1 , μ
k=||x
k||∞ ,
xk=xk/μ
k k=1,2,3,....,n
Y xk=(1/γ
k)Akx
o donde γ
k=μ
1·μ
2·μ
3· ··· ·μ
k
Asó xk converge a un vector v(1) normalizado,
,luego por (1)xk=λ
1xk-1+O(|λ
2/λ
1|k) (2)
Y el líóm μk=|λ
1|
, k→∞
la convergencia es lenta cuando |λ2|≈|λ
1|
Puede acelerarse con métodos de extrapolacioón.
En el caso de una matriz hermíótica, como es simétrica y sus autovalores son reales, puedo elegir los autovectores reales y ortogonales.
Luego por (2), el cociente de Rayleigh ρ seraóρ(x
k-1)=(x
k-1)TAx
k-1=(x
k-1)Tx
Converge dos veces maó s raó pido junto con μk
λ1=ρ(x
k-1)+O(|λ
2/λ
1|2k)
Si la matriz tiene su autovalor dominante repetido, el método tambieén es aplicable, siempre que la matriz sea diagonalizable.SI r es la multiplicidad geométrica de λ
1 entonces
|λ1|=...=|λ
r|>|λ
r+1|≥|λ
n|
Y el método convergeraó un sólo vector del espacio propio de λ
1 que dependeraó del vector
inicial dado.
El método se aplica para matrices no diagona-lizables, mientras el autovalor dominante sea uónico (multiplicidad geométrica 1), puedo obtener una buena aproximacioó n de un autector asociado al autovalor dominante.
Sea A=VJV-1
Donde la primea columna de V corresponde al autovector asociado al vector dominante,como es uónico, el primer bloque de Jordan es la matriz 1x1 [λ
1]
El vector inicial b0 puede ser escrito como
combinacioó n lineal de los vectores columna de V: b
0=c
1v1+c
2v2+...+c
nvn
con c1≠0
Asumo, bk=Akb
0/||Akb
0|| luego
Luego, [(1/c1)V((1/λ
1)J)k]∑c
jej→ v
1(∑c
jej)=0 si k→∞
, y φ→v1
entoncesbk→(λ
1/|λ
1|)k(c
1/|c
1|)(v
1/||v
1||)
Donde bk es un autovector de A para un k grande
bk=(VJV-1)kb
0/||(VJV-1)kb
0|| = (VJkV-1)b
0/||(VJkV-1)b
0|| =
=(VJkV-1)(∑civi)/||(VJkV-1)(∑c
ivi)||= VJk(∑c
iei)/||VJk(∑c
iei)||=
=(λ1/|λ
1|)k(c
1/|c
1|)(φ/||φ||)
Donde φ=v1+(1/c
1)V(J/λ
1)k(∑c
jej) y j=2,3,....,n
La expresioón se simplifica si k→∞
El método de la potencia inversaAplicando el método de la potencia a la matriz (A-pI) se determina el autovalor maó s cercano a p y se calcula su autovector. SI se elije p correctamente, el método converge al autovalor de menor moó dulo.
El método converge mucho maó s raó pido, ya que los autocalores de mi matriz seraó n
(λ1-p),(λ
2-p),....,(λ
n-p) y debo elegir p tal que
λ1-p sea el autovalor dominante y |λ
1-p|/|λ
2-p|
sea mucho menor a |λ1|/|λ
2|
Luego, el método converge a λ1-p y determino λ
1
Aplicaciones:Centralidad de autovaloresLa centralidad en un grafo se refiere a una medida posible de un veértice en dicho grafo, que determina la importancia de eéste.
En eéste caso, se mide utilizando el valor y vector propio de la matriz de adyacencia del grafo.
Éste tipo de centralidad se utiliza en algoritmos de redes sociales.
Aplicaciones:matriz de covarianciaEn estadíóstica, se llama matriz de covariancia a la matriz que calcula la covariancia de los elementos de un vector. Obteniendo el autovalor y el autovector dominantes se puede determinar la direccioón principal del graófico de los datos.
Aplicaciones:Mecaónica Cuaó nticaEn mecaónica
cuaó ntica las ecuaciones de onda son ecuaciones de autovalores, en el caso de la ecuacioón de Schroö dinger, los autovalores representan la energíóa del sistema, y su autovalor míónimo determina el “ground state”.
El programaEn el programa debo ingresar la dimensioón, la matriz, el vector inicial, una cota del error y un nuómero maó ximo de iteraciones.Me devuelve el mayor autovalor, el autovector asociado, un mensje con las iteraciones utilizadas o un cartel del error si mi vector inicial no tiene componente en el autovector asociado al autovalor dominante. Utilizo las subrutinas:
Mi maó s profundo agradecimiento a:
•Richard L. Burden y J. Douglas Faires, autores de “Anaó lisis numeérico” 7ma edicioó n.
•Germund Dahlquist y Åke Bjoö rk, autores de “Numerical methods in scientific computing”vol 2• Wikipedia, por todas sus definiciones.
• A cienciaexplicada.com por sus ejemplos.
• A ustedes por escuchar el coloquio.