Pas optimal dans la méthode gradient constant
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.
$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.
Réponses
-
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 !
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.2K Toutes les catégories
- 9 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 65 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 69 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 314 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 773 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres