Post on 02-May-2018
CÁLCULO DE AUTOVALORESCÁLCULO DE AUTOVALORES
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
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
1. INTRODUCCIÓN1. INTRODUCCIÓN
�Problema estándar
�Problema generalizado
λ autovalor / valor propio
v autovector / vector propio
· 2
v autovector / vector propio
ÁLGEBRA LINEAL: los autovalores son las raíces del polinomio característico
Inconvenientes:1. Cálculo de determinantes (∼n! operaciones), agrupación de
términos2. Acumulación de errores de redondeo3. No se aprovechan las cualidades de las matrices (simetría,
definición positiva, estructura especial...)
· 3
Necesidad de algoritmos alternativos Necesidad de algoritmos alternativos más eficientesmás eficientes
Aplicaciones en ingeniería civilAplicaciones en ingeniería civil
– Cálculo dinámico de estructuras: sismos, vibraciones, viento...
– Análisis de pandeo
– Problemas de ondas: ingeniería marítima, problemas
· 4
– 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),
2.1 Problema estándar
Teorema 1 [Teorema espectral del álgebra]: Si es simétrica, entonces diagonaliza (con autovalores reales) en una base ortonormal.
2. FUNDAMENTOS2. FUNDAMENTOS
· 5
n autovectores ortonormales
n autovalores tales que
� En forma matricial
· 6
� U es ortogonal diagonalización de A
Si A es simétrica y definida positiva (SDP)
Si A es simétrica y semidefinida positiva
2.2 Problema generalizado2.2 Problema generalizado
Aplicación: Análisis modal en dinámica estructural
xx: desplazamientos : desplazamientos nodalesnodales
· 7
El desplazamiento en la viga se interpola a partir de los valores nodales
Ecuación de equilibrio (oscilaciones libres):
nodalesnodales
MM: matriz de masa (SDP): matriz de masa (SDP)KK: matriz de rigidez: matriz de rigidez
Se busca una solución de la forma con φ vector de desplazamientos nodales constante (modo) y ω frecuencia de vibración (frecuencia propia)
· 8
Sustituyendo en la ecuación de equilibrio
¿Cómo son los autovalores del problema generalizado?¿Cómo son los autovalores del problema generalizado?
� simétricas ⇒⇒⇒⇒ autovalores reales
Ejemplo:
· 9
con
los autovalores son
Teorema 2: si son simétricas y M es definida positiva, entonces existen n autovalores reales
y n autovectores
• M-ortonormales:
• K-ortogonales:
· 10
• K-ortogonales:
2.3 Reducción del problema generalizado al problema estándar
2.3 Reducción del problema generalizado al problema estándar
1. M invertible:
Aunque M y K sean simétricas, A* puede ser no simétrica.
· 11
Aunque M y K sean simétricas, A* puede ser no simétrica.
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*A* v*v* v*v*= = λλλλλλλλ
con
Se conserva la simetría
· 12
Se conserva la simetrí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. ����
Demostración del Teorema 2Demostración del Teorema 2
� K y M simétricas, y M definida positiva � A* real y simétrica
� Por el Teorema 1 (Teorema espectral del álgebra), A* diagonaliza en una base ortonormal• autovalores reales λi
• autovectores ortonormales
· 13
� El problema generalizado tiene autovalores λi y autovectores que cumplen• M-ortonormales:
• K-ortogonales:
3. PROPIEDADES GENERALES de matrices simétricas
3. PROPIEDADES GENERALES de matrices simétricas
PROBLEMA ESTÁNDAR:
La matriz verifica
Solución propiaSolución propia
3.1 Deflación3.1 Deflación
· 14
Demostración:
uukk pasa a tener pasa a tener autovalor 0autovalor 0
� PROBLEMA GENERALIZADO:
La matriz verifica
Solución propiaSolución propia
uukk pasa a tener pasa a tener
· 15
Demostración: (ejercicio)
uukk pasa a tener pasa a tener autovalor 0autovalor 0
3.2 Traslación3.2 Traslación
� PROBLEMA ESTÁNDAR:con autovalores λi y autovectores ui
tiene los mismos autovectores ui, pero con autovalores
· 16
Demostración:
� PROBLEMA GENERALIZADO:
con tiene los mismos autovectores ui, con autovalores
3.3 Cociente de Rayleigh3.3 Cociente de Rayleigh
� PROBLEMA ESTÁNDAR: A real, simétrica
Expresión alternativa en la base de autovectores:
Cociente de RayleighCociente de Rayleigh
· 17
Expresión alternativa en la base de autovectores:
Demostración:
· 18
utilizando
Propiedades del cociente de RayleighPropiedades del cociente de Rayleigh
1. -
2. -
3. Si con
· 19
3. Si con
Demostración 1.Demostración 1.
Caso 1: A definida positiva
a)
· 20
b)
Caso 2: A no definida definida positiva
Se considera p tal que y la traslación
• El cociente de Rayleigh cumple
· 21
• B tiene autovalores
B definida positiva B definida positiva (caso 1)(caso 1)
Demostración 2.Demostración 2.
Demostración 3.Demostración 3.
· 22
convamos a comprobar que
==λλiiuu
ii
· 23
� PROBLEMA GENERALIZADO:
· 24
Cociente de RayleighCociente de Rayleigh
4. MÉTODOS DE ITERACIÓN VECTORIAL (von Mises o de las potencias)
4. MÉTODOS DE ITERACIÓN VECTORIAL (von Mises o de las potencias)
4.1 Método de iteración vectorial directaLa Iteración Vectorial Directa (IVD) proporciona el autovalordominante (el más alejado de cero) y el autovector asociado
� PROBLEMA ESTÁNDAR: A real, simétrica
Atención a la Atención a la nueva numeraciónnueva numeración
· 25
� PROBLEMA ESTÁNDAR: A real, simétrica• vector inicial casi-arbitrario v0
• iteraciones
• Convergencia: tal que
Autovalor dominante (con su signo)
Algoritmo IVD problema estándarAlgoritmo IVD problema estándar
Dado v0 casi-arbitrario
k = 0, 1, 2...k = 0, 1, 2...
· 26
k = 0, 1, 2...k = 0, 1, 2...
demostración convergencia IVDdemostración convergencia IVD
· 27
Caso general: λn autovalor dominante con multiplicidad p
· 28
ObservacionesObservaciones
� Existen otras versiones del algoritmo. Los vectores se pueden normalizar dividiendo por su norma, pero hay otras opciones. Por ejemplo,
· 29
� El vector inicial no es totalmente arbitrario
� Convergencia
� PROBLEMA GENERALIZADO:
• vector inicial casi-arbitrario v0
• iteraciones
y utilizar IVD
· 30
• Convergencia: tal que
AlgoritmoAlgoritmo
yykk
ωωk+1k+1
· 31
yykkωωk+1k+1
El algoritmo se simplifica obviando el cálculo de vk
Algoritmo IVD problema generalizadoAlgoritmo IVD problema generalizado
· 32
4.2 Método de iteración vectorial inversaLa Iteración Vectorial Inversa (IVI) proporciona el autovalormás cercano a cero (el mínimo en valor absoluto, con su signo) y el autovector asociado
� PROBLEMA ESTÁNDAR:
· 33
tiene los mismo autovectores con autovalores
IVD con AIVD con A--11
Algoritmo IVI problema estándarAlgoritmo IVI problema estándar
ωωk+1k+1
En la práctica no se calcula A-1
· 34
calcula A-1
??
� La convergencia se puede acelerar con una traslación
ObservacionesObservaciones
IVI paraIVI para
· 35
� Cálculo del autovalor más cercano a un valor dado (o del autovector asociado a un autovalor conocido)
� PROBLEMA GENERALIZADO:
IVI para A � IVD para A-1
yykk
ωωk+1k+1
· 36
yykk
zzk+1k+1
ωωk+1k+1
AlgoritmoAlgoritmo
· 37
(versión 1)(versión 1)(versión 2)(versión 2)
Algoritmo IVI problema generalizadoAlgoritmo IVI problema generalizado
· 38
≈ ≈ λλ11 ??
5. OTROS MÉTODOS5. 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
• Jacobi