User Tools

Site Tools


chicoutimi_2016:calcul_matriciel

Visual Analytics Course

Instructor: Guy Melançon (email: Guy dot Melancon at labri dot fr)

Chicoutimi Summer 2016 roadmap / May 3, 3pm course

Calcul matriciel, graphes et chemins

On reprend ici des éléments du calcul matriciel qui sont utiles pour le cours.

Nous n'aborderons qu'un ensemble minimal des propriétés du calcul matriciel. Essentiellement, nous soulignons ici combien le produit de matrice répond au calcul de parcours dans un graphe.

Une matrice sur est un tableau noté . Remarquez que, les lignes et colonnes étant toutes deux associées aux éléments de , la matrice est carrée. On pourrait aussi considérer des matrices de forme plus générale .

On peut aussi voir la matrice comme un opérateur qui prend en entrée un vecteur et retourne un vecteur . Le calcul se fait en multipliant chaque ligne de la matrice par le vecteur , retournant ainsi les coordonnées du nouveau vecteur :

qu'on écrit sous forme abrégée .

On peut aussi multiplier deux matrices, et former le produit dont les tailles sont compatibles ( de taille et de taille ). Nous rencontrerons le plus souvent des matrices carrées de même taille.

Considérons le cas où mes valeurs sont toutes soit 0, soit 1. Si on considère les lignes et colonnes comme étant associées à des sommets d'un graphe, on peut associer la présence des 0 et des 1 dans la matrice aux arêtes du graphe. Inversement, état donnée un graphe, on peut décrire sa structure (ses liens) à l'aide d'une matrice q'on appelle la matrice d'adjacence du graphe. Le lien entre graphe et calcul matriciel tient dans l'observation suivante:

Les entrées de la matrice produit donnent le nombre de chemins de longueur 2 entre les sommets du graphe associé à . Plus généralement, les entrées calculent le nombre de chemins de longueur dans le graphe.

On peut aussi considérer des matrices dont les arêtes ont des poids (des valeurs numériques). La matrice contient alors des nombres plutôt que des valeurs binaires 0, 1. Le cas où la somme des entrées de chaque ligne de la matrice est égale à 1 est intéressant. On peut alors penser aux poids d'une arête comme à la probabilité de passer du sommet au sommet avec probabilité .

Chaque sommet du graphe (orienté, pondéré) représente un état du système. Les arcs du graphe sont pondérés, le poids pouvant être considérés comme la probabilité de réaliser la transition .

Si maintenant on pense à un vecteur comme donnant la probabilité de se trouver sur un état , alors le vecteur donne la probabilité de se trouver sur le sommet venant d'un sommet (où l'on pouvait se trouver selon la distribution de probabilité ).

Comme précédemment, on peut multiplier la matrice par elle-même et obtenir la matrice où . Encore une fois, ce calcul s'interprète naturellement en terme de chemins dans le graphe. La valeur cumule les probabilité d'aller de à en passant par un état transitoire .

Plus généralement, si on se donne un vecteur (de probabilités) , on peut calculer la suite

Le vecteur contient alors les probabilités de se trouver sur chacun des sommets du graphe, après avoir traversé un chemin de longueur – étant donné des probabilités de se trouver sur chacun de ces sommets au départ. On prendra le plus souvent le vecteur de probabilité uniforme; mais on peut montrer que le vecteur résultant existe et ne dépend pas du choix de .

Ce calcul, et son interprétation, passe aux ordres supérieurs. Les valeurs de la matrice donne les probabilités de passer d'un état à un état en suivant un chemin de longueur dans le graphe.

Exercice -- Matrice et graphe

Soit la matrice:

Représentez graphiquement le graphe correspondant.

Vecteurs propres et valeurs propres

On a mentionné qu'une matrice carrée peut être vue comme un opérateur agissant sur les vecteurs .

Parmi tous les vecteurs, certains ont un rôle particuliers, ce sont ceux qui sont invariants sous l'effet de la matrice. ON les appelles les vecteurs propres:

dont l'effet de correspond à une homothétie (pas de changement de direction, seulement un étirement ou compression du vecteur). La valeur scalaire est appelée une valeur propre associée au vecteur propre .

Ces vecteurs et valeurs propres jouent un rôle dans le calcul de différentes statistiques sur les graphes comme nous le verrons.

Dans la plupart des cas (tous, en réalité), nous considérerons des matrices dont les entrées (poids des arêtes) sont tous positifs. Dans ce cas, on peut montrer (c'est le théorème de Perron-Frobenius) que la matrice admet toujours une valeur propre réelle et positive et que les coordonnées du vecteur propre sont toutes positives aussi; que la valeur propre est la valeur maximum (pour être précis: de module maximum, car certaines valeurs propres peuvent être des nombres complexes, puisque les valeurs propres sont des solutions d'une équation polynomiale dérivées de la matrice).

/net/html/perso/melancon/Visual_Analytics_Course/data/pages/chicoutimi_2016/calcul_matriciel.txt · Last modified: 2016/05/07 15:06 by melancon