Cas d'utilisation des valeurs et vecteurs propres¶

In [1]:
import numpy as np
import numpy.linalg as lin

np.set_printoptions(precision=3, linewidth=150, suppress=True)

Fibonnacci¶

La suite de Fibonnacci est $x_n = x_{n-2} + x_{n-1}$ avec $x_0 = 1, x_1 = 1$.

Quelle est la complexité pour calculer $x_n$ ?

Comme on a 2 termes à droite du signe égal, écrivons Fibonnacci sous forme d'un système matriciel $2\times 2$ :

$ \begin{align} x_{n-1} &= x_{n-1} \\ x_n &= x_{n-2} + x_{n-1} \\ \end{align} $ ce qui donne $ \begin{bmatrix} x_{n-1}\\ x_n \\ \end{bmatrix}¶

\begin{bmatrix} 0 & 1 \\ 1 & 1 \\ \end{bmatrix} \begin{bmatrix} x_{n-2}\\ x_{n-1} \\ \end{bmatrix} $

Écrire la matrice F ci-dessous et vérifier que le 6e élément de la suite de Fibonacci est 8 en n'utilisant que la matrice F et les valeurs initiales de la suite. La fonction numpy.linalg.matrix_power pourra vous être utile.

In [ ]:
In [ ]:

Calculer n produits matriciels n'est pas rentable, par contre sachant que $F = P\, D\, P^{-1}$ avec

  • P la matrice des vecteurs propres
  • D la matrice diagonale des valeurs propres

on peut faire quelque chose car il va avoir des simplification lors du calcul de de $F^n$.

  • Ecrire la formule matriciel de la suite de Fibonnacci en fonction de P et D.
  • Expliquer pourquoi le calcul du n-ème élément de la suite peut se faire en temps constant.

Écrire la fonction fibo(n) qui calcule le n-ème élément de la suite de Fibonnacci en temps constant.

In [ ]:
In [ ]:

Vérifier que votre fonction est en temps constant en chronométrant fibo(5) et fibo(1000) avec la commande %timeit de Jupyter.

In [ ]:
In [ ]:

Google page rank¶

Soit N pages web numérotées qui font référence les unes aux autres. Disons que si la page 3 est référencée par les pages 8 9 et 13 j'écris $x_3 = x_8 + x_9 + x_{13}$. On voit qu'on peut écrire ces référencements dans une matrice avec le i-ième ligne qui décrit par qui est référencée la i-ème page web. Cette matrice a un 1 dans la j-ième colonne si la page j cite la page i et sinon un 0.

In [2]:
np.random.seed(42)
N = 8
A = np.random.randint(2,size=(N,N))
for i in range(len(A)):
    A[i,i] = 0   # on ne compte pas les auto-référencements
A
Out[2]:
array([[0, 1, 0, 0, 0, 1, 0, 0],
       [0, 0, 0, 0, 0, 0, 1, 0],
       [1, 1, 0, 0, 1, 0, 1, 1],
       [1, 1, 1, 0, 1, 1, 0, 0],
       [1, 1, 1, 0, 0, 0, 0, 0],
       [0, 0, 1, 1, 1, 0, 1, 0],
       [1, 1, 0, 1, 0, 1, 0, 1],
       [1, 0, 0, 0, 0, 0, 0, 0]])

Cet article indique que Google à l'époque de l'écriture de l'article (2001) basait son classement des pages web en utilisant les vecteurs propres de cette matrice (vous n'avez pas besoin de lire cet article pour faire l'exercice).

Approche itérative¶

Une bonne introduction qui va un peu plus loin peut-être trouvé ici.

Dans un premier temps on procède de la manière suivant pour trouver l'importance d'une page: Étant donné N page à évaluer

  • On initialise un vecteur v de taille N avec 1 partout -> Correspond à une distribution uniforme de l'importance initialement
  • On calcule le produit matrice vecteur A v
  • On normalise le résultat pour que la norme 1 soit égale au nombre de pages (N)
  • On répète ces étapes jusqu'à un point fixe

De cette manière l'entrée i du vecteur v correspond à l'importance de la page i -> Discutez pourquoi.

In [7]:
v = np.zeros((N,1))
vprime = np.ones((N,1))

while (np.absolute(np.max(vprime - v)) > 1e-5): # which norm is used here?
    v = vprime
    vprime = 
    vprime *= 
    print(vprime.T)

[[0.774 0.387 1.419 1.419 1.032 1.29  1.548 0.129]]
[[0.542 0.5   1.25  1.583 0.833 1.75  1.292 0.25 ]]
[[0.742 0.426 1.127 1.608 0.756 1.636 1.526 0.179]]
[[0.672 0.497 1.183 1.527 0.748 1.635 1.496 0.242]]
[[0.694 0.487 1.19  1.542 0.766 1.613 1.489 0.219]]
[[0.683 0.484 1.189 1.545 0.771 1.622 1.481 0.226]]
[[0.686 0.482 1.187 1.546 0.767 1.624 1.485 0.222]]
[[0.686 0.484 1.186 1.546 0.767 1.624 1.485 0.223]]
[[0.686 0.484 1.187 1.545 0.767 1.623 1.485 0.223]]
[[0.686 0.484 1.187 1.545 0.767 1.623 1.485 0.223]]
[[0.686 0.484 1.187 1.545 0.767 1.623 1.485 0.223]]
[[0.686 0.484 1.187 1.545 0.767 1.623 1.485 0.223]]
[[0.686 0.484 1.187 1.545 0.767 1.623 1.485 0.223]]
[[0.686 0.484 1.187 1.545 0.767 1.623 1.485 0.223]]

Un autre approche¶

Vous constatez que A.v = α * v pour une constante α. Est-ce que ça vous rappelle quelque chose ?

  • On considère que les composantes du premier vecteur propre représentent la valeur de chaque page. Calculez les valeurs des pages. Comparez avec le résultat obtenue auparavant.
  • Calculez le nombre de citations pour chaque page.
In [ ]:
In [ ]: