Optimisation Numérique : Gradient conjugué.

[robertu]

Bonjour !
J'ai un problème concernant le méthode du gradient conjugué. En effet je dois montrer que lorsque je double la valeur du paramètre beta le nombre d'itération dans mon algorithme est divisé par sqrt(2)

En gros j'ai tracé sur un graphe la courbe de log norm(r(beta)) en fonction du nombre d'itération et je dois trouver le coefficient directeur de cette droite. Après avoir cherché sur le net au sujet de la vitesse de convergence il apparait que je vais avoir besoin de calculer les valeurs propre de mon opérateur A. Chose que je ne sais pas faire. (Je travail sur des matrices 1024x1024).

Rappel : le gradient conjugué permet de résoudre min;)(x)= 0.5x'Ax;)b'x.ou A est un opérateur , b et x des matrices 1024x1024.

D'avance merci.

[Mathusalem]

Bonjour !
J'ai un problème concernant le méthode du gradient conjugué. En effet je dois montrer que lorsque je double la valeur du paramètre beta le nombre d'itération dans mon algorithme est divisé par sqrt(2)

En gros j'ai tracé sur un graphe la courbe de log norm(r(beta)) en fonction du nombre d'itération et je dois trouver le coefficient directeur de cette droite. Après avoir cherché sur le net au sujet de la vitesse de convergence il apparait que je vais avoir besoin de calculer les valeurs propre de mon opérateur A. Chose que je ne sais pas faire. (Je travail sur des matrices 1024x1024).

Rappel : le gradient conjugué permet de résoudre min;)(x)= 0.5x'Ax;)b'x.ou A est un opérateur , b et x des matrices 1024x1024.

D'avance merci.

Plusieurs truc que je capte pas :

Le nombre d'itérations devrait déjà être optimalement bon avec le paramètre beta classique. Je vois pas pourquoi le doubler te donnerait une convergence plus rapide

Mais soit :
La deuxième chose que je capte pas, c'est qu'avec n'importe quel logiciel de calcul (Matlab?) tu peux demander un polyfit de degré 1, c'est-à-dire qu'il te calque une droite sur ton nuage de points.
Et tu auras une pente assez fiable (regarder le facteur R^2 du fit) qui sera la puissance de ta convergence

La troisième chose :

Tu bosses avec des matrices symetriques définies positives, donc trouver les valeurs propres devrait être assez simple. Un truc qui me vient à l'esprit c'est de créer une base de Lanczos pour que ta matrice soit tridiagonale, et après t'as le choix, décompo LU, etc... Mais je dis pas que c'est ce qu'il y a de plus efficace pour calculer les valeurs propres.
EDIT : La matrice tridiagonale que t'obtiens en faisant ça n'aura pas exactement les mêmes valeurs propres que la matrice de départ, mais ça devrait être suffisamment précis.

[geegee]

Bonjour !
J'ai un problème concernant le méthode du gradient conjugué. En effet je dois montrer que lorsque je double la valeur du paramètre beta le nombre d'itération dans mon algorithme est divisé par sqrt(2)

En gros j'ai tracé sur un graphe la courbe de log norm(r(beta)) en fonction du nombre d'itération et je dois trouver le coefficient directeur de cette droite. Après avoir cherché sur le net au sujet de la vitesse de convergence il apparait que je vais avoir besoin de calculer les valeurs propre de mon opérateur A. Chose que je ne sais pas faire. (Je travail sur des matrices 1024x1024).

Rappel : le gradient conjugué permet de résoudre min;)(x)= 0.5x'Ax;)b'x.ou A est un opérateur , b et x des matrices 1024x1024.

D'avance merci.

Bonjour,

Peut etre que excel pourrait le réaliser :
http://www.commentfaiton.com/fiche/voir/16534/comment-calculer-le-determinant-d-une-matrice-avec-excel

[robertu]

Bonjour,

Peut etre que excel pourrait le réaliser :
http://www.commentfaiton.com/fiche/voir/16534/comment-calculer-le-determinant-d-une-matrice-avec-excel

En fait le problème c'est que je dois le prouver de manière analytique. Je dois donc en fait réussir à savoir quelle influence a la paramètre beta sur les valeurs propre de A