Clase 5: Método de Iteración Inversa¶

Bibliografía de la Clase:

Numerical Linear Algebra. L.N. Trefethen. Chapter 5, Lecture 27: Rayleigh Quotient, Inverse Iteration
Guía Profesor Luis Salinas

Introducción¶

Sea $A\in \mathbb{R}^{n\times n}$ tal que $A^T=A$ , i.e., $A$ es real y simétrica, de modo que sus $n$ valores propios $\lambda_j$ son reales y distintos, y el sistema de sus $n$ vectores propios $V_j$ constituye una base ortogonal de $\mathbb{R}^n$ .

Entonces, para todo $\mu \in \mathbb{R}$ que no es un valor propio de $A$ se tiene:

Los vectores propios de $(A-\mu I)$ y $(A-\mu I)^{-1}$ coinciden con los vectores propios de $A$ , y tienen valores propios $(\lambda_i - \mu)$ y $(\lambda_i - \mu)^{-1}$ , respectivamente.

Detalle¶

Si $x$ en un vector propio de la matriz $A$ , y $\lambda$ es su vector propio asociado. Para la matriz $(A -\mu I)$ se tiene:

$(A -\mu I) x= Ax - \mu I x = \lambda x - \mu x = (\lambda -\mu) x$

Por lo tanto $x$ es un vector propio de $(A -\mu I)$ , y $(\lambda -\mu)$ es su valor propio.

Ejemplo¶

$A=\begin{bmatrix} 2 &3 \\ 1 & 0\end{bmatrix}, \ \ t=2 A-tI = \begin{bmatrix} 0 &1 \\ 1 & -2\end{bmatrix} ,\ \ (A-tI)^{-1}=\begin{bmatrix} 0 &1 \\ 1/3 & 2/3\end{bmatrix}`$

Desarrollo¶

¿Cuáles son los valores propios y vectores propios de $A-tI$ , $(A-tI)^{-1}$ ?
- Utilizando alguno de los métodos conocidos para el cálculo de valores propios, se obtiene $\lambda_1=3$ y $\lambda_2=-1$ para la matriz $A$ .
- Por lo tanto, $1$ y $-3$ son los valores propios de $A-tI$ , $1$ y $-1/3$ son los valores propios de $(A-tI)^{-1}$ .
- Los vectores propios son iguales para las tres matrices.

Iteración Inversa¶

Nota

El algoritmo de Iteración inversa hace lo mismo que el Método de Potencias, pero usa la matriz $(A-\mu I)^{-1}$

Idea¶

Suponer que $\mu \not \in \sigma(A)$ es muy próximo a un valor propio $\lambda_k$ de $A$
$\sigma(A)$ es el spectrum o conjunto de los valores propios de $A$ .
Un vector arbitrario $v \in \mathbb{R}^n$ se puede expresar en términos de la base $\{ V_1,\dots, V_n\}$ :

$v= c_1 V_1 + c_2 V_2 + \dots + c_n V_n\;.$

$v^{(0)}= c_1 V_1 + c_2 V_2 + \dots + c_n V_n\;. (A-\mu I)^{-1} v^{(0)} = c_1 (\lambda_1 - \mu)^{-1} V_1 + c_2 (\lambda_2 - \mu)^{-1} V_2 + \dots + c_n (\lambda_n - \mu)^{-1} V_n \ldots (A-\mu I)^{-p} v^{(0)} = c_1 (\lambda_1 - \mu)^{-p} V_1 + c_2 (\lambda_2 - \mu)^{-p} V_2 + \dots + c_n (\lambda_n - \mu)^{-p} V_n$

Además (por el algoritmo, $v^{(1)} = (A-\mu I)^{-1} v^{(0)} / || (A-\mu I)^{-1} v^{(0)} || \ldots$ )

$v^{(k)}= \text{const.} (A-\mu I)^{-p} v^{(0)} v^{(k)}= \text{const.}[ c_1 (\lambda_1 - \mu)^{-p} V_1 + c_2 (\lambda_2 - \mu)^{-p} V_2 + \dots + c_n (\lambda_n - \mu)^{-p} V_n]$

Si $\mu \approx \lambda_k \Rightarrow c_k (\lambda_k-\mu)^{-p} V_k$ es dominante en la suma

$v^{(k)}= \text{const.} c_k (\lambda_k - \mu)^{-p} V_k$

Si $\mu$ es cercano a $\lambda_k \Rightarrow c_k (\lambda_k-\mu)^{-p} V_k$ es dominante en la suma
El algoritmo tiende al valor propio de $A$ , porque todas las matrices $(A - \mu I)^{-1}$ tienen los mismos vectores propios.

Ejemplo¶

Se tiene la matriz $A=\begin{bmatrix} 9 &1 \\ 1 &2 \end{bmatrix}$

Utilizando el siguiente código (simplificado) analice la salida del algoritmo utilizando como entrada:

$v=\begin{bmatrix} 1 \\ 1 \end{bmatrix}$ y $\mu=4$
$v=\begin{bmatrix} 1 \\ 1 \end{bmatrix}$ y $\mu=7$

function [lambda,v]= simpleInverseIteration(A,v,mu,steps)

v=v/norm(v);
n=size(A,1);

for i=1:steps
    A_new= A-mu*eye(n);
    w=A_new\v;
    
    v=w/norm(w);
    lambda=v'*A*v;
end

Teorema:

Suponer que $|\lambda_J|$ es el valor propio más cercano a $\mu$ y $|\lambda_K|$ es el segundo más cercano, es decir, $|\mu - \lambda_J| < |\mu - \lambda_K| \leq |\mu - \lambda_j| \forall j \neq J$ . Además, suponer que $q^Tv^{(0)} \neq 0$ . Entonces las iteraciones del algoritmo Iteración Inversa, satisface:

$||v^{(k)} - (\pm q_J)|| = \mathcal{O} \left ( \left | \frac{\mu - \lambda_J}{\mu - \lambda_K} \right|^{k} \right ) |\lambda^{(k)} - \lambda_J| = \mathcal{O} \left ( \left | \frac{\mu - \lambda_J}{\mu - \lambda_K} \right|^{2k} \right )$

cuando $k \rightarrow \infty$ .

Iteración del Cuociente de Rayleigh¶

Utilizando el cuociente de Rayleigh se obtiene la aproximación de un valor propio, a partir de un vector propio estimado
De la iteración inversa se obtiene un vector propio a partir de un valor propio estimado.
La combinación de ambas ideas da origen al algoritmo de Iteración del Cuociente de Rayleigh:

La convergencia de este algoritmo es mucho mejor: cada iteración triplica el número de digitos de la precisión.

Ejemplo

Se tiene la matriz $A=\begin{bmatrix} 2 &1 &1 \\ 1 &3 &1 \\ 1 &1 &4 \end{bmatrix}$ y $v^{(0)}=\frac{1}{\sqrt{3}}\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}`$
Encontrar el valor propio correspondiente al vector propio más cercano a $v^{(0)}$ .

function [lambda,v]= simpleRayleighIteration(A,v,steps)

v=v/norm(v);
lambda=v'*A*v;
n=size(A,1);

for i=1:steps
    A_new= A-lambda*eye(n);
    w=A_new\v;
    v=w/norm(w);
    lambda=v'*A*v;
end

Ejercicio Propuesto¶

Dada la matriz $A= \begin{bmatrix} 10 &1\\ 0 &1 \end{bmatrix}, \mu= 0$ y $v^{(0)}=\begin{bmatrix} 1 \\1\end{bmatrix},$ explique y desarrolle el algorimto de iteración inversa para encontrar un vector propio.

Clase 5: Método de Iteración Inversa¶