Travail d'Analyse Numérique 2008

Enoncé du projet

Le travail s’effectue par groupes de deux. Un rapport écrit est à remettre pour le 17 novembre. Il comprendra au maximum 7 pages, plus éventuellement le code MatLab en annexe. L’évaluation orale aura lieu la semaine du 24 novembre. On vous y demandera d’effectuer une démonstration du code réalisé.

Pour toute question relative au travail, vous pouvez me contacter à l'adresse poirrier montefiore.ulg.ac.be , ou vous rendre à mon bureau (B28/R74).

Questions fréquentes

A. Exemple de l'énoncé

Les valeurs de PageRank données dans l'exemple de l'énoncé ne sont pas des valeurs réelles.

B. Matrice d'adjacence modifiée, précision pour le point 4

Si un document i ne comprend aucun lien sortant, on considère qu'il contient exactement un lien vers tous les autres. Or, comme les boucles ne sont pas comptées (point 3),
Aii = 0
Après normalisation des lignes (point 2), il vient
Aij = 1/(N-1), i != j

C. Propriétés de la matrice d'adjacence modifiée, en résumé

1. Les éléments diagonaux sont nuls:
Aii = 0
2. Pour toute ligne, la somme des éléments vaut 1:
Ai0 + Ai1 + ... + Ai(N-1) = 1
3. Si une page i ne comporte aucun lien sortant, i.e. si
Aij = 0, i != j
alors
Aij = 1/(N-1), i != j

D. Comment charger une matrice d'adjacence récupérée depuis ce site?

On vous fournit un script MatLab, qu'il suffit d'exécuter. Ceci chargera la matrice dans une variable nommée "m".

E. Comment exécuter un script MatLab

Si vous avez enregistré le fichier sous le nom "nom_de_fichier.m", placez-vous dans son répertoire, et entrez la commande "nom_de_fichier".

F. Non-convergence de la méthode de la puissance?

Il y a plusieurs conditions pour la convergence de la méthode de la puissance (cfr. cours §5.4.1 page 108). Si elles ne sont pas toutes respectées, rien ne garantit l'obtention du vecteur propre recherché.

Même dans ce cas, votre fonction devra fournir un résultat, éventuellement erroné, mais elle devra s'arrêter. Si vous êtes confrontés à cette situation, vous devrez, si possible, en indiquer la cause dans le rapport écrit (i.e. la condition de convergence qui n'est pas respectée).

G. Facteur d'amortissement

Le facteur d'amortissement d représentant une probabilité, il est compris entre 0 et 1.

A la question 7b, le facteur d'amortissement est fixé, vous pouvez le choisir arbitrairement.

H. Question 6: la méthode de la puissance est plus rapide que eigs

Dans certains cas, il est possible que les performances de la fonction que vous avez implémentée pour la question 5 soient comparables à celles de la fonction eigs. Dans ce cas, donnez vos résultats, en temps de calcul, mais aussi en précision sur les vecteurs obtenus.

I. Comment masquer les informations affichées par la fonction eigs?

Ceci n'est absolument pas nécessaire pour le travail. Mais pour information, voici la marche à suivre.

Le quatrième argument de eigs permet d'accéder aux options, notamment la quantité d'affichage:

opts.disp = 0;

[resultat] = eigs(matrice, 1, 'LM', opts);

où "resultat" et "matrice" dépendent de votre code. Le 1 signifie que l'on cherche un seul vecteur propre (et une valeur propre). 'LM' signifie qu'on s'intéresse à la plus grande valeur propre. La variable "opts" contient des options avancées, notamment les options d'affichage ("disp" pour "display").

Vous pouvez en outre créer une fonction d'encapsulation pour simplifier le code, par exemple:

function [v d] = eigs1(m)

  opts.disp = 0;
  [v d] = eigs(m, 1, 'LM', opts);

end

J. Question 7

A la question 7, on vous demande d'implémenter des méthodes numériques dans MatLab. Vous devez donc considérer le calcul du PageRank comme une fonction vectorielle r(A, d), dont on connaît les valeurs numériques, mais pas nécessairement l'expression analytique.

Pour le point b, on considère que la matrice trouvée en fin de calcul (matrice d'adjacence ou d'adjacence modifiée peu importe) peut comporter des éléments réels (non entiers). Cependant ceux-ci doivent être positifs ou nuls.