Iteración inversa

En el análisis numérico , la iteración inversa (también conocida como método de potencia inversa ) es un algoritmo iterativo de valor propio . Permite 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 del valor propio correspondiente al vector propio deseado y un vector , ya sea un vector seleccionado aleatoriamente o una aproximación al vector propio. El método se describe mediante la iteración ${\displaystyle \mu }$ ${\displaystyle b_{0}}$

$${\displaystyle b_{k+1}={\frac {(A-\mu I)^{-1}b_{k}}{C_{k}}},}$$

donde se eligen algunas constantes generalmente como Dado que los vectores propios se definen hasta la multiplicación por una constante, la elección de puede ser arbitraria en teoría; los aspectos prácticos de la elección de se analizan a continuación. ${\displaystyle C_{k}}$ ${\displaystyle C_{k}=\|(A-\mu I)^{-1}b_{k}\|.}$ ${\displaystyle C_{k}}$ ${\displaystyle C_{k}}$

En cada iteración, el vector se multiplica por la matriz y se normaliza. Es exactamente la misma fórmula que en el método de potencia , excepto que se reemplaza la matriz por Cuanto más cercana se elija la aproximación al valor propio, más rápido convergerá el algoritmo; sin embargo, la elección incorrecta de puede conducir a una convergencia lenta o a la convergencia a un vector propio distinto del 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 (con frecuencia, solo una). ${\displaystyle b_{k}}$ ${\displaystyle (A-\mu I)^{-1}}$ ${\displaystyle A}$ ${\displaystyle (A-\mu I)^{-1}.}$ ${\displaystyle \mu }$ ${\displaystyle \mu }$

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 . A excepción de un conjunto de medida cero , para cualquier vector inicial, el resultado convergerá a un vector propio correspondiente al valor propio dominante . ${\displaystyle b}$ ${\displaystyle Ab,A^{2}b,A^{3}b,...}$

La iteración inversa hace lo mismo para la matriz , por lo que converge al vector propio correspondiente al valor propio dominante de la matriz . Los valores propios de esta matriz son donde son los valores propios de . El mayor de estos números corresponde al menor de Los vectores propios de y de son los mismos, ya que ${\displaystyle (A-\mu I)^{-1}}$ ${\displaystyle (A-\mu I)^{-1}}$ ${\displaystyle (\lambda _{1}-\mu )^{-1},...,(\lambda _{n}-\mu )^{-1},}$ ${\displaystyle \lambda _{i}}$ ${\displaystyle A}$ ${\displaystyle (\lambda _{1}-\mu ),...,(\lambda _{n}-\mu ).}$ ${\displaystyle A}$ ${\displaystyle (A-\mu I)^{-1}}$

$${\displaystyle Av=\lambda v\Leftrightarrow (A-\mu I)v=\lambda v-\mu v\Leftrightarrow (\lambda -\mu )^{-1}v=(A-\mu I)^{-1}v}$$

Conclusión : El método converge al vector propio de la matriz correspondiente al valor propio más cercano a ${\displaystyle A}$ ${\displaystyle \mu .}$

En particular, tomando vemos que converge al vector propio correspondiente al valor propio de con la mayor magnitud y por lo tanto se puede utilizar para determinar el valor propio de la magnitud más pequeña de ya que están inversamente relacionados. ${\displaystyle \mu =0}$ ${\displaystyle (A)^{-1}b_{k}}$ ${\displaystyle A^{-1}}$ ${\displaystyle {\frac {1}{\lambda _{N}}}}$ ${\displaystyle A}$

Velocidad de convergencia

Analicemos la tasa de convergencia del método.

Se sabe que el método de potencia converge linealmente al límite, más precisamente:

$${\displaystyle \mathrm {Distance} (b^{\mathrm {ideal} },b_{\mathrm {Power~Method} }^{k})=O\left(\left|{\frac {\lambda _{\mathrm {subdominant} }}{\lambda _{\mathrm {dominant} }}}\right|^{k}\right),}$$

Por lo tanto, para el método de iteración inversa, el resultado es similar:

$${\displaystyle \mathrm {Distance} (b^{\mathrm {ideal} },b_{\mathrm {Inverse~iteration} }^{k})=O\left(\left|{\frac {\mu -\lambda _{\mathrm {closest~to~} \mu }}{\mu -\lambda _{\mathrm {second~closest~to~} \mu }}}\right|^{k}\right).}$$

Esta es una fórmula clave para entender la convergencia del método. Muestra que si se elige lo suficientemente cerca de algún valor propio , por ejemplo, cada iteración mejorará los tiempos de precisión. (Usamos que para lo suficientemente pequeño, "más cercano a " y "más cercano a " es lo mismo). Para lo suficientemente pequeño, es aproximadamente lo mismo que . Por lo tanto, si uno es capaz de encontrar , de modo que el sea lo suficientemente pequeño, entonces muy pocas iteraciones pueden ser satisfactorias. ${\displaystyle \mu }$ ${\displaystyle \lambda }$ ${\displaystyle \mu -\lambda =\epsilon }$ ${\displaystyle |\epsilon |/|\lambda +\epsilon -\lambda _{\mathrm {closest~to~} \lambda }|}$ ${\displaystyle \epsilon }$ ${\displaystyle \mu }$ ${\displaystyle \lambda }$ ${\displaystyle |\epsilon |}$ ${\displaystyle |\epsilon |/|\lambda -\lambda _{{\text{closest to }}\lambda }|}$ ${\displaystyle \mu }$ ${\displaystyle \epsilon }$

Complejidad

El algoritmo de iteración inversa requiere la resolución de un sistema lineal o el cálculo de la matriz inversa. Para matrices no estructuradas (no dispersas, no Toeplitz, etc.) esto requiere operaciones. ${\displaystyle O(n^{3})}$

Opciones de implementación

El método está definido por la fórmula:

$${\displaystyle b_{k+1}={\frac {(A-\mu I)^{-1}b_{k}}{C_{k}}},}$$

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: $${\displaystyle (A-\mu I)b_{k+1}={\frac {b_{k}}{C_{k}}},}$$

Destacando que para encontrar la siguiente 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 la inversa y luego aplicarla al vector. Ambas opciones tienen complejidad O ( n ³ ), el número exacto depende del método elegido. ${\displaystyle b_{k+1}}$ ${\displaystyle (A-\mu I)^{-1}}$

La elección depende también del número de iteraciones. Ingenuamente, si en cada iteración uno resuelve un sistema lineal, la complejidad será k  O ( n ³ ), donde k es el número de iteraciones; de manera similar, calcular la matriz inversa y aplicarla en cada iteración tiene una complejidad k  O ( n ³ ). Sin embargo, tenga en cuenta que si la estimación del valor propio permanece constante, entonces podemos reducir la complejidad a O ( n ³ ) + k O ( n ² ) con cualquiera de los métodos. Calcular la matriz inversa una vez y almacenarla para aplicarla en cada iteración tiene una complejidad O ( n ³ ) + k O ( n ² ). Almacenar una descomposición LU y usar sustitución hacia adelante y hacia atrás para resolver el sistema de ecuaciones en cada iteración también tiene una complejidad O ( n ³ ) + k O ( n ² ). ${\displaystyle \mu }$   ${\displaystyle (A-\mu I)}$ 

La inversión de la matriz suele tener un mayor coste inicial, pero un menor coste en cada iteración. Por el contrario, la resolución de sistemas de ecuaciones lineales suele tener un coste inicial menor, pero requiere más operaciones en cada iteración.

Tridiagonalización,Forma de Hessenberg

Si es necesario realizar muchas iteraciones (o pocas iteraciones, pero para muchos vectores propios), entonces podría ser prudente llevar la matriz a la forma superior de Hessenberg primero (para matrices simétricas esto será la forma tridiagonal ). Lo que cuesta operaciones aritméticas utilizando una técnica basada en la reducción de Householder ), con una secuencia finita de transformadas de similitud ortogonales, algo así como una descomposición QR de dos lados. ^{[2] [3]} (Para la descomposición QR, las rotaciones de Householder 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 cuesta operaciones aritméticas utilizando una técnica basada en la reducción de Householder. ^{[2] [3]} ${\textstyle {\frac {10}{3}}n^{3}+O(n^{2})}$ ${\textstyle {\frac {4}{3}}n^{3}+O(n^{2})}$

La solución del sistema de ecuaciones lineales para la matriz tridiagonal cuesta operaciones, por lo que la complejidad crece como , donde es el número de iteraciones, lo cual es mejor que para la inversión directa. Sin embargo, para pocas iteraciones tal transformación puede no ser práctica. ${\displaystyle O(n)}$ ${\displaystyle O(n^{3})+kO(n)}$ ${\displaystyle k}$

Además, 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ónC- k

En los procesadores de propósito general (por ejemplo, los fabricados por Intel), el tiempo de ejecución de la suma, la multiplicación y la división es aproximadamente igual. Pero en hardware integrado o de bajo consumo de energía ( procesadores de señal digital , FPGA , ASIC ), la división puede no ser compatible con el hardware, por lo que se debe evitar. La elección permite una división rápida sin soporte explícito del hardware, ya que la división por una potencia de 2 se puede implementar como un desplazamiento de bits (para aritmética de punto fijo ) o una resta del exponente (para aritmética de punto flotante ). ${\displaystyle C_{k}=2^{n_{k}}}$ ${\displaystyle k}$

Al implementar el algoritmo utilizando aritmética de punto fijo , la elección de la constante es especialmente importante. Los valores pequeños conducirán a un crecimiento rápido de la norma de y a un desbordamiento ; los valores grandes de harán que el vector tienda a cero. ${\displaystyle C_{k}}$ ${\displaystyle b_{k}}$ ${\displaystyle C_{k}}$ ${\displaystyle b_{k}}$

Uso

La principal aplicación 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 método principal y probablemente el único que se puede utilizar.

Métodos para encontrar valores propios aproximados

Normalmente, el método se utiliza 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 puede utilizarse por sí solo, aunque son bastante marginales.

Norma de matriz como aproximación a ladominantevalor propio

El valor propio dominante se puede estimar fácilmente para cualquier matriz. Para cualquier norma inducida es cierto que para cualquier valor propio . Por lo tanto, si se toma la norma de la matriz como un valor propio aproximado, se puede ver que el método convergerá al vector propio dominante. ${\displaystyle \left\|A\right\|\geq |\lambda |,}$ ${\displaystyle \lambda }$

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 de una muestra de matriz grande. Mejor aún, se puede calcular la relación media de los valores propios con la traza o la norma de la matriz y estimar el valor propio medio como la traza o la norma multiplicada por el valor medio de esa relación. Es evidente que un método de este tipo sólo se puede utilizar con discreción y sólo cuando no es fundamental una alta precisión. Este enfoque de estimación de un valor propio medio se puede combinar con otros métodos para evitar errores excesivamente grandes.

Véase también

• Iteración de potencia
• Iteración del cociente de Rayleigh
• Lista de algoritmos de valores propios

Referencias

1. Ernst Pohlhausen, Berechnung der Eigenschwingungen statisch-bestimmter Fachwerke , ZAMM - Zeitschrift für Angewandte Mathematik und Mechanik 1, 28-42 (1921).
2. Demmel, James W. (1997), Álgebra lineal numérica aplicada , Filadelfia, PA: Sociedad de Matemáticas Industriales y Aplicadas , ISBN 0-89871-389-7, Sr.  1463942.
3. Lloyd N. Trefethen y David Bau, Álgebra lineal numérica (SIAM, 1997).