En el análisis numérico , la iteración inversa (también conocida como método de potencia inversa ) es un algoritmo de valor propio iterativo . Permite a uno encontrar un vector propio aproximado cuando ya se conoce una aproximación a un valor propio correspondiente . El método es conceptualmente similar al método de potencia . Parece haber sido desarrollado originalmente para calcular frecuencias de resonancia en el campo de la mecánica estructural. [1]
El algoritmo de iteración de potencia inversa comienza con una aproximación para el autovalor correspondiente al autovector deseado y un vector, ya sea un vector seleccionado al azar o una aproximación al autovector. El método es descrito por la iteración
dónde son algunas constantes generalmente elegidas como Dado que los vectores propios se definen hasta la multiplicación por constante, la elección de puede ser arbitrario en teoría; aspectos prácticos de la elección de se analizan a continuación.
En cada iteración, el vector se multiplica por la matriz y normalizado. Es exactamente la misma fórmula que en el método de potencia , excepto que reemplaza la matriz por Cuanto más cercana sea la aproximación al valor propio elegido, más rápido converge el algoritmo; Sin embargo, la elección incorrecta depuede conducir a una convergencia lenta oa la convergencia a un vector propio diferente al deseado. En la práctica, el método se utiliza cuando se conoce una buena aproximación para el valor propio y, por lo tanto, solo se necesitan unas pocas iteraciones (a menudo una sola).
Teoría y convergencia
La idea básica de la iteración de potencia es elegir un vector inicial(ya sea una aproximación de vector propio o un vector aleatorio ) y calcular iterativamente. Excepto por un conjunto de medida cero , para cualquier vector inicial, el resultado convergerá a un autovector correspondiente al autovalor dominante .
La iteración inversa hace lo mismo para la matriz. , por lo que converge al autovector correspondiente al autovalor dominante de la matriz . Los valores propios de esta matriz son dónde son valores propios de . El mayor de estos números corresponde al menor de Los vectores propios de y de son los mismos, ya que
Conclusión : el método converge al vector propio de la matriz correspondiente al valor propio más cercano a
En particular, tomando vemos eso converge al autovector correspondiente al autovalor de con el valor absoluto más pequeño [ aclaración necesaria ] .
Velocidad de convergencia
Analicemos la tasa de convergencia del método.
Se sabe que el método de potencia converge linealmente hasta el límite, más precisamente:
por lo tanto, para el método de iteración inversa, un resultado similar suena como:
Esta es una fórmula clave para comprender la convergencia del método. Demuestra que si se elige lo suficientemente cerca de algún valor propio , por ejemplo cada iteración mejorará la precisión veces. (Usamos eso para lo suficientemente pequeño "más cercano a "y" más cercano a "es el mismo.) Para lo suficientemente pequeño es aproximadamente lo mismo que . Por tanto, si uno es capaz de encontrar, tal que el será lo suficientemente pequeño, entonces muy pocas iteraciones pueden ser satisfactorias.
Complejidad
El algoritmo de iteración inversa requiere resolver un sistema lineal o calcular la matriz inversa. Para matrices no estructuradas (no dispersas, no Toeplitz, ...) esto requiere operaciones.
Opciones de implementación
El método está definido por la fórmula:
Sin embargo, existen múltiples opciones para su implementación.
Calcular matriz inversa o resolver sistema de ecuaciones lineales
Podemos reescribir la fórmula de la siguiente manera:
enfatizando que para encontrar la próxima aproximación podemos resolver un sistema de ecuaciones lineales. Hay dos opciones: se puede elegir un algoritmo que resuelva un sistema lineal, o se puede calcular el inversoy luego aplíquelo al vector. Ambas opciones tienen complejidad O (n 3 ) , el número exacto depende del método elegido.
La elección depende también del número de iteraciones. Ingenuamente, si en cada iteración se resuelve un sistema lineal, la complejidad será k * O (n 3 ) , donde k es el número de iteraciones; de manera similar, calcular la matriz inversa y aplicarla en cada iteración es de complejidad k * O (n 3 ) . Sin embargo, tenga en cuenta que si la estimación del valor propiopermanece constante, entonces podemos reducir la complejidad a O (n 3 ) + k * O (n 2 ) con cualquier método. Calcular la matriz inversa una vez y almacenarla para aplicarla en cada iteración es de complejidad O (n 3 ) + k * O (n 2 ) . Almacenar una descomposición LU dey el uso de la sustitución hacia adelante y hacia atrás para resolver el sistema de ecuaciones en cada iteración también es de complejidad O (n 3 ) + k * O (n 2 ) .
La inversión de la matriz generalmente tendrá un costo inicial mayor, pero un costo menor en cada iteración. Por el contrario, la resolución de sistemas de ecuaciones lineales generalmente tendrá un costo inicial menor, pero requerirá más operaciones para cada iteración.
Tridiagonalización, forma Hessenberg
Si es necesario realizar muchas iteraciones (o pocas iteraciones, pero para muchos vectores propios), entonces sería prudente llevar la matriz a la forma superior de Hessenberg primero (para la matriz simétrica, será la forma tridiagonal ). Que cuestaoperaciones aritméticas que utilizan una técnica basada en la reducción del amo de casa ), con una secuencia finita de transformaciones de semejanza ortogonal, algo así como una descomposición QR de dos lados. [2] [3] (Para la descomposición QR, las rotaciones de los jefes de hogar se multiplican solo a la izquierda, pero para el caso de Hessenberg se multiplican tanto a la izquierda como a la derecha). Para matrices simétricas, este procedimiento cuestaoperaciones aritméticas utilizando una técnica basada en la reducción de jefes de hogar. [2] [3]
Solución del sistema de ecuaciones lineales para los costos de la matriz tridiagonal operaciones, por lo que la complejidad crece como , dónde es el número de iteración, que es mejor que para la inversión directa. Sin embargo, para algunas iteraciones, esta transformación puede no ser práctica.
También la transformación a la forma de Hessenberg implica raíces cuadradas y la operación de división, que no son universalmente compatibles con el hardware.
Elección de la constante de normalización
En los procesadores de propósito general (por ejemplo, producidos por Intel), el tiempo de ejecución de la suma, multiplicación y división es aproximadamente igual. Pero en hardware integrado y / o de bajo consumo de energía ( procesadores de señales digitales , FPGA , ASIC ), la división puede no ser compatible con hardware y, por lo tanto, debe evitarse. Elegirpermite una división rápida sin soporte explícito de hardware, ya que la división por una potencia de 2 puede implementarse como un desplazamiento de bits (para aritmética de punto fijo ) o como una resta dedel exponente (para aritmética de punto flotante ).
Al implementar el algoritmo usando aritmética de punto fijo , la elección de la constantees especialmente importante. Los valores pequeños conducirán a un rápido crecimiento de la norma dey desbordar ; grandes valores de causará el vector tender hacia cero.
Uso
La aplicación principal del método es la situación en la que se encuentra una aproximación a un valor propio y se necesita encontrar el vector propio aproximado correspondiente. En tal situación, la iteración inversa es el principal y probablemente el único método a utilizar.
Métodos para encontrar valores propios aproximados
Por lo general, el método se usa en combinación con algún otro método que encuentra valores propios aproximados: el ejemplo estándar es el algoritmo de valor propio de bisección , otro ejemplo es la iteración del cociente de Rayleigh , que en realidad es la misma iteración inversa con la elección del valor propio aproximado como el Cociente de Rayleigh correspondiente al vector obtenido en el paso anterior de la iteración.
Hay algunas situaciones en las que el método se puede utilizar por sí solo, sin embargo, son bastante marginales.
Norma de matriz como aproximación al autovalor dominante
El autovalor dominante se puede estimar fácilmente para cualquier matriz. Para cualquier norma inducida es cierto que para cualquier valor propio . Entonces, tomando la norma de la matriz como un valor propio aproximado, se puede ver que el método convergerá al vector propio dominante.
Estimaciones basadas en estadísticas
En algunas aplicaciones en tiempo real, es necesario encontrar vectores propios para matrices con una velocidad de millones de matrices por segundo. En tales aplicaciones, normalmente las estadísticas de las matrices se conocen de antemano y se puede tomar como valor propio aproximado el valor propio medio para una muestra de matriz grande. Mejor, se puede calcular la razón media de los autovalores a la traza o la norma de la matriz y estimar el autovalor promedio como la traza o norma multiplicada por el valor promedio de esa razón. Claramente, un método de este tipo solo puede usarse con discreción y solo cuando una alta precisión no es crítica. Este enfoque de estimación de un valor propio promedio se puede combinar con otros métodos para evitar errores excesivamente grandes.
Ver también
Referencias
- ↑ Ernst Pohlhausen, Berechnung der Eigenschwingungen statisch-bestimmter Fachwerke , ZAMM - Zeitschrift für Angewandte Mathematik und Mechanik 1, 28-42 (1921).
- ^ a b Demmel, James W. (1997), Álgebra lineal numérica aplicada , Filadelfia, PA: Sociedad de matemáticas industriales y aplicadas , ISBN 0-89871-389-7, MR 1463942.
- ^ a b Lloyd N. Trefethen y David Bau, Álgebra lineal numérica (SIAM, 1997).