Download cálculo de autovalores - Universitat Politècnica de Catalunya

1. INTRODUCCIÓN
Problema estándar
Problema generalizado
CÁLCULO DE AUTOVALORES
λ autovalor / valor propio
v autovector / vector propio
ÁLGEBRA LINEAL: los autovalores son las raíces del
polinomio característico
Laboratori de Càlcul Numèric (LaCàN)
Departament de Matemàtica Aplicada III
Universitat Politècnica de Catalunya (Barcelona)
http://www-lacan.upc.es
·2
Aplicaciones en ingeniería civil
Inconvenientes:
1. Cálculo de determinantes (∼n! operaciones), agrupación de
términos
2. Acumulación de errores de redondeo
3. No se aprovechan las cualidades de las matrices (simetría,
definición positiva, estructura especial...)
– Cálculo dinámico de estructuras: sismos, vibraciones,
viento...
– Análisis de pandeo
– Problemas de ondas: ingeniería marítima, problemas
medioambientales (contaminación acústica)
– Herramientas auxiliares para la resolución de sistemas de
ecuaciones: número de condición (si SDP máx λi / mín λi),
radio espectral (máx λi),
Necesidad de algoritmos alternativos
más eficientes
·3
·4
2. FUNDAMENTOS
En forma matricial
2.1 Problema estándar
Teorema 1 [Teorema espectral del álgebra]: Si
es
simétrica, entonces diagonaliza (con autovalores reales) en
una base ortonormal.
n autovectores
n autovalores
U es ortogonal
ortonormales
diagonalización de A
Si A es simétrica y definida positiva (SDP)
tales que
Si A es simétrica y semidefinida positiva
·5
2.2 Problema generalizado
·6
Se busca una solución de la forma
con φ vector de desplazamientos nodales constante (modo)
y ω frecuencia de vibración (frecuencia propia)
Aplicación: Análisis modal en dinámica estructural
x: desplazamientos
nodales
Sustituyendo en la ecuación de equilibrio
El desplazamiento en la viga se interpola a partir de los valores nodales
Ecuación de equilibrio (oscilaciones libres):
M: matriz de masa (SDP)
K: matriz de rigidez
·7
·8
¿Cómo son los autovalores del problema generalizado?
Teorema 2: si
son simétricas y M es definida
positiva, entonces existen n autovalores reales
simétricas ⇒ autovalores reales
Ejemplo:
y n autovectores
•
M-ortonormales:
• K-ortogonales:
con
los autovalores son
·9
· 10
2.3 Reducción del problema generalizado al
problema estándar
con
1. M invertible:
Aunque M y K sean simétricas, A* puede ser no simétrica.
Se conserva la simetría
Sólo es simétrica si K y M-1 conmutan 2. K y M simétricas, y M definida positiva:
•
Si M SDP descomposición de Cholesky
A*
Sin embargo, a veces no conviene transformar el problema.
Por ejemplo, si M y K son matrices en banda, L es en banda
pero L-1 es una matriz llena A* es llena. v* = λ v*
· 11
· 12
Demostración del Teorema 2
K y M simétricas, y M definida positiva A* real y
3.1 Deflación
simétrica
3. PROPIEDADES GENERALES
de matrices simétricas
PROBLEMA ESTÁNDAR:
Por el Teorema 1 (Teorema espectral del álgebra), A*
diagonaliza en una base ortonormal
• autovalores reales λi
• autovectores
ortonormales
Solución propia
La matriz
verifica
uk pasa a tener
autovalor 0
El problema generalizado tiene autovalores λi y
autovectores
que cumplen
• M-ortonormales:
Demostración:
• K-ortogonales:
· 13
· 14
3.2 Traslación
PROBLEMA GENERALIZADO:
PROBLEMA ESTÁNDAR:
con autovalores λi y autovectores ui
Solución propia
La matriz
verifica
autovalores
uk pasa a tener
autovalor 0
tiene los mismos autovectores ui, pero con
Demostración:
PROBLEMA GENERALIZADO:
Demostración: (ejercicio)
con
tiene los mismos autovectores ui, con autovalores
· 15
· 16
3.3 Cociente de Rayleigh
PROBLEMA ESTÁNDAR:
Demostración:
A real, simétrica
Cociente de Rayleigh
Expresión alternativa en la base de autovectores:
utilizando
· 17
Propiedades del cociente de Rayleigh
· 18
Demostración 1.
Caso 1: A definida positiva
1. a)
2. 3. Si
con
b)
· 19
· 20
Demostración 2.
Caso 2: A no definida definida positiva
Se considera p tal que
traslación
•
y la
El cociente de Rayleigh cumple
Demostración 3.
•
con
vamos a comprobar que
B tiene
autovalores
B definida positiva
(caso 1)
· 21
· 22
PROBLEMA GENERALIZADO:
=λiui
Cociente de Rayleigh
· 23
· 24
4. MÉTODOS DE ITERACIÓN VECTORIAL
(von Mises o de las potencias)
4.1 Método de iteración vectorial directa
Algoritmo IVD problema estándar
Dado v0 casi-arbitrario
La Iteración Vectorial Directa (IVD) proporciona el autovalor
dominante (el más alejado de cero) y el autovector asociado
Atención a la
nueva numeración
PROBLEMA ESTÁNDAR:
• vector inicial casi-arbitrario v0
• iteraciones
k = 0, 1, 2...
A real, simétrica
Autovalor dominante
(con su signo)
• Convergencia:
tal que
· 25
· 26
demostración convergencia IVD
Caso general: λn autovalor dominante con multiplicidad p
· 27
· 28
Observaciones
PROBLEMA GENERALIZADO:
Existen otras versiones del algoritmo. Los vectores se
pueden normalizar dividiendo por su norma, pero hay otras
opciones. Por ejemplo,
y utilizar IVD
• vector inicial casi-arbitrario v0
• iteraciones
El vector inicial no es totalmente arbitrario
Convergencia
• Convergencia:
tal que
· 29
· 30
Algoritmo
Algoritmo IVD problema generalizado
· 31
· 32
ωk+1
yk
ωk+1
yk
El algoritmo se simplifica
obviando el cálculo de vk
Algoritmo IVI problema estándar
4.2 Método de iteración vectorial inversa
La Iteración Vectorial Inversa (IVI) proporciona el autovalor
más cercano a cero (el mínimo en valor absoluto, con su
signo) y el autovector asociado
ωk+1
En la práctica no se
calcula A-1
PROBLEMA ESTÁNDAR:
tiene los mismo autovectores con autovalores
?
IVD con A-1
· 33
Observaciones
· 34
PROBLEMA GENERALIZADO:
La convergencia se puede acelerar con una traslación
IVI para
IVI para A

IVD para A-1
ωk+1
yk
Cálculo del autovalor más cercano a un valor dado (o del
autovector asociado a un autovalor conocido)
ωk+1
zk+1
· 35
· 36
Algoritmo
Algoritmo IVI problema generalizado
≈ λ1
?
(versión 1)
(versión 2)
· 37
5. OTROS MÉTODOS
Métodos de iteración polinómica
• iteración polinómica explícita
• iteración polinómica implícita
Métodos de ortogonalización
• descomposición en valores singulares (SVD)
• Jacobi
· 39
· 38