summaryrefslogtreecommitdiff
path: root/PVCM/cama/en/ma26 Vecteurs propres -- Exercices.ipynb
diff options
context:
space:
mode:
Diffstat (limited to 'PVCM/cama/en/ma26 Vecteurs propres -- Exercices.ipynb')
-rw-r--r--PVCM/cama/en/ma26 Vecteurs propres -- Exercices.ipynb305
1 files changed, 305 insertions, 0 deletions
diff --git a/PVCM/cama/en/ma26 Vecteurs propres -- Exercices.ipynb b/PVCM/cama/en/ma26 Vecteurs propres -- Exercices.ipynb
new file mode 100644
index 0000000..88d82df
--- /dev/null
+++ b/PVCM/cama/en/ma26 Vecteurs propres -- Exercices.ipynb
@@ -0,0 +1,305 @@
+{
+ "metadata": {
+ "kernelspec": {
+ "display_name": "Python 3 (ipykernel)",
+ "language": "python",
+ "name": "python3"
+ },
+ "language_info": {
+ "codemirror_mode": {
+ "name": "ipython",
+ "version": 3
+ },
+ "file_extension": ".py",
+ "mimetype": "text/x-python",
+ "name": "python",
+ "nbconvert_exporter": "python",
+ "pygments_lexer": "ipython3",
+ "version": "3.10.12"
+ }
+ },
+ "nbformat": 4,
+ "nbformat_minor": 4,
+ "cells": [
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "# Cas d'utilisation des valeurs et vecteurs propres"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 1,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "import numpy as np\n",
+ "import numpy.linalg as lin\n",
+ "\n",
+ "np.set_printoptions(precision=3, linewidth=150, suppress=True)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Fibonnacci\n",
+ "\n",
+ "La suite de Fibonnacci est $x_n = x_{n-2} + x_{n-1}$ avec $x_0 = 1, x_1 = 1$.\n",
+ "\n",
+ "Quelle est la complexité pour calculer $x_n$ ?\n",
+ "\n",
+ "\n",
+ "\n"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": []
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "Comme on a 2 termes à droite du signe égal, écrivons Fibonnacci sous forme d'un système matriciel $2\\times 2$ :\n",
+ "\n",
+ "$\n",
+ "\\begin{align}\n",
+ "x_{n-1} &= x_{n-1} \\\\\n",
+ "x_n &= x_{n-2} + x_{n-1} \\\\\n",
+ "\\end{align}\n",
+ "$\n",
+ "ce qui donne\n",
+ "$\n",
+ "\\begin{bmatrix}\n",
+ "x_{n-1}\\\\\n",
+ "x_n \\\\\n",
+ "\\end{bmatrix}\n",
+ "=\n",
+ "\\begin{bmatrix}\n",
+ "0 & 1 \\\\\n",
+ "1 & 1 \\\\\n",
+ "\\end{bmatrix}\n",
+ "\\begin{bmatrix}\n",
+ "x_{n-2}\\\\\n",
+ "x_{n-1} \\\\\n",
+ "\\end{bmatrix}\n",
+ "$\n",
+ "\n",
+ "É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 \n",
+ "la matrice F et les valeurs initiales de la suite. La fonction `numpy.linalg.matrix_power` pourra vous être utile."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {},
+ "outputs": [],
+ "source": []
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {},
+ "outputs": [],
+ "source": []
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "Calculer n produits matriciels n'est pas rentable, par contre sachant que\n",
+ "$F = P\\, D\\, P^{-1}$ avec\n",
+ "\n",
+ "* P la matrice des vecteurs propres\n",
+ "* D la matrice diagonale des valeurs propres\n",
+ "\n",
+ "on peut faire quelque chose car il va avoir des simplification lors du calcul de de $F^n$. \n",
+ "\n",
+ "* Ecrire la formule matriciel de la suite de Fibonnacci en fonction de P et D. \n",
+ "* Expliquer pourquoi le calcul du n-ème élément de la suite peut se faire en temps constant."
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": []
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "Écrire la fonction `fibo(n)` qui calcule le n-ème élément de la suite de Fibonnacci en temps constant."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {},
+ "outputs": [],
+ "source": []
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {},
+ "outputs": [],
+ "source": []
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "Vérifier que votre fonction est en temps constant en chronométrant `fibo(5)` et `fibo(1000)` avec la commande \n",
+ "`%timeit` de Jupyter."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {},
+ "outputs": [],
+ "source": []
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {},
+ "outputs": [],
+ "source": []
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Google page rank\n",
+ "\n",
+ "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\n",
+ "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\n",
+ "la j-ième colonne si la page j cite la page i et sinon un 0."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 2,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "array([[0, 1, 0, 0, 0, 1, 0, 0],\n",
+ " [0, 0, 0, 0, 0, 0, 1, 0],\n",
+ " [1, 1, 0, 0, 1, 0, 1, 1],\n",
+ " [1, 1, 1, 0, 1, 1, 0, 0],\n",
+ " [1, 1, 1, 0, 0, 0, 0, 0],\n",
+ " [0, 0, 1, 1, 1, 0, 1, 0],\n",
+ " [1, 1, 0, 1, 0, 1, 0, 1],\n",
+ " [1, 0, 0, 0, 0, 0, 0, 0]])"
+ ]
+ },
+ "execution_count": 2,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "np.random.seed(42)\n",
+ "N = 8\n",
+ "A = np.random.randint(2,size=(N,N))\n",
+ "for i in range(len(A)):\n",
+ " A[i,i] = 0 # on ne compte pas les auto-référencements\n",
+ "A"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "[Cet article](https://www.math.upenn.edu/~wilf/website/KendallWei.pdf) indique que Google à l'époque de l'écriture de l'article (2001) basait son classement des pages web \n",
+ "en utilisant les vecteurs propres de cette matrice (vous n'avez pas besoin de lire cet article pour faire l'exercice).\n"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Approche itérative\n",
+ "Une bonne introduction qui va un peu plus loin peut-être trouvé [ici](https://pi.math.cornell.edu/~mec/Winter2009/RalucaRemus/Lecture3/lecture3.html).\n",
+ "\n",
+ "Dans un premier temps on procède de la manière suivant pour trouver l'importance d'une page:\n",
+ "Étant donné N page à évaluer \n",
+ "* On initialise un vecteur __v__ de taille N avec 1 partout -> Correspond à une distribution uniforme de l'importance initialement\n",
+ "* On calcule le produit matrice vecteur A __v__\n",
+ "* On normalise le résultat pour que la norme 1 soit égale au nombre de pages (N)\n",
+ "* On répète ces étapes jusqu'à un point fixe\n",
+ "\n",
+ "De cette manière l'entrée i du vecteur __v__ correspond à l'importance de la page i -> Discutez pourquoi."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 7,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "[[0.774 0.387 1.419 1.419 1.032 1.29 1.548 0.129]]\n",
+ "[[0.542 0.5 1.25 1.583 0.833 1.75 1.292 0.25 ]]\n",
+ "[[0.742 0.426 1.127 1.608 0.756 1.636 1.526 0.179]]\n",
+ "[[0.672 0.497 1.183 1.527 0.748 1.635 1.496 0.242]]\n",
+ "[[0.694 0.487 1.19 1.542 0.766 1.613 1.489 0.219]]\n",
+ "[[0.683 0.484 1.189 1.545 0.771 1.622 1.481 0.226]]\n",
+ "[[0.686 0.482 1.187 1.546 0.767 1.624 1.485 0.222]]\n",
+ "[[0.686 0.484 1.186 1.546 0.767 1.624 1.485 0.223]]\n",
+ "[[0.686 0.484 1.187 1.545 0.767 1.623 1.485 0.223]]\n",
+ "[[0.686 0.484 1.187 1.545 0.767 1.623 1.485 0.223]]\n",
+ "[[0.686 0.484 1.187 1.545 0.767 1.623 1.485 0.223]]\n",
+ "[[0.686 0.484 1.187 1.545 0.767 1.623 1.485 0.223]]\n",
+ "[[0.686 0.484 1.187 1.545 0.767 1.623 1.485 0.223]]\n",
+ "[[0.686 0.484 1.187 1.545 0.767 1.623 1.485 0.223]]\n"
+ ]
+ }
+ ],
+ "source": [
+ "v = np.zeros((N,1))\n",
+ "vprime = np.ones((N,1))\n",
+ "\n",
+ "while (np.absolute(np.max(vprime - v)) > 1e-5): # which norm is used here?\n",
+ " v = vprime\n",
+ " vprime = \n",
+ " vprime *= \n",
+ " print(vprime.T)\n"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Un autre approche\n",
+ "\n",
+ "Vous constatez que A.__v__ = α * __v__ pour une constante α. Est-ce que ça vous rappelle quelque chose ?\n",
+ "\n",
+ "* 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.\n",
+ "* Calculez le nombre de citations pour chaque page."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {},
+ "outputs": [],
+ "source": []
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {},
+ "outputs": [],
+ "source": []
+ }
+ ]
+} \ No newline at end of file
generated by cgit v1.2.3 (git 2.39.1) at 2026-03-14 23:09:22 +0000