El cálculo de valores propios es fundamental para varias aplicaciones. El algoritmo PageRank de Google usa vectores propios dominantes para clasificar páginas, los vectores propios nos dicen direcciones de dispersión de datos, podemos rotar imágenes, codificar información, encontrar invarianzas en operadores, etc.
El primer algoritmo a revisar es Power Iteration. La tarea principal es encontrar para una matriz $A \in \mathbb{R}^{n\times n}$ su vector propio dominante y su valor propio asociado, denominados $\mathbf{v}_1$ y $\lambda_1$ respectivamente. ¿Cómo podemos lograr esto?. La idea base radica en la sucesiva potenciación de la matriz $A$ por algún vector $\mathbf{x}_0$, cuyo resultado apuntará cada vez más en la dirección del vector propio dominante.
In [3]:
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
In [4]:
def power_iteration(A, x0, n_iter=100):
# Check if x0 is given as input
if not x0:
x0 = np.random.rand(A.shape[0])
for i in range(n_iter):
u = A.dot(x0)
u / np.linalg.norm(u)
return u
Notar que en cada paso el método normaliza por la norma del vector $\mathbf{u}$, esto permite acotar el resultado y que no crezca demasiado. A su vez el método nos permitirá estimar el valor propio asociado al vector propio dominante. A continuación la demostración del método.
El presente notebook ha sido creado para el curso ILI286 - Computación Científica 2, del Departamento de Informática, Universidad Técnica Federico Santa María. El material ha sido creado por Alejandro Sazo (asazo@alumnos.inf.utfsm.cl) y Claudio Torres (ctorres@inf.utfsm.cl). En caso de encontrar un error, por favor no dude en contactar al email especificado. Puede encontrar la última versión del código en https://github.com/asazo/CC2
In [ ]: