Pas optimal dans la méthode gradient constant

llorteLEG · May 2021

Bonjour ! Je cherche à trouver le pas optimal dans un algorithme du gradient à pas fixe pour une fonctionnelle donnée :
$J = \frac 12 x^TAx - b^Tx$ avec $A$ définie positive.
À trouver le meilleur pas de l'algorithme $x_{n+1} = x_n - \tau \nabla J(x_n)$.

J'ai l'impression que je trouve des sources contradictoires sur le net...
Si je note $\lambda_1$ et $\lambda_p$ les plus grandes et plus petites valeurs propres de $A$ je trouve des sources contradictoires sur le net.

Ici page 2 : Cours 1 ils me disent que $\quad \tau = \frac{2}{\lambda_1 + \lambda_p}$

Dans un autre cours ils disent :

Soit $\quad\tau = \lambda_1/\lambda_p^2$

Où est mon erreur ? Merci d'avance.

Borelline · May 2021

Bonjour !
Un peu de calcul :
Dans le cours $2$, on obtient la borne : $\sqrt{1- \frac{\lambda_1^2}{\lambda_p^2}} = \sqrt{1- x^2}$, $x = \frac{\lambda_1}{\lambda_p}$
Dans le cours $1$, la borne est obtenue en imposant $\rho(A- \tau I_n) < 1$ et la borne est donc : $\rho(A- \tau I_n) = \max(|1-\tau \lambda_1|,|1-\tau \lambda_p|) = \frac{\lambda_p-\lambda_1}{\lambda_p+\lambda_1} = \frac{1-x}{1+x}$

Faisons maintenant le rapport des deux : $(\sqrt{1- x^2})/\left(\frac{1-x}{1+x}\right) = (1+x)\sqrt{\frac{1+x}{1-x}} \geq 1$ donc le cours $1$ gagne !

Pas optimal dans la méthode gradient constant

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 3