Scribd
Importer
7 vues2 pages

Méthodes d'optimisation numérique en M1

Le document traite de l'optimisation numérique à travers plusieurs exercices, notamment l'application de la méthode du gradient pour résoudre des systèmes linéaires, l'inversion de matrices par la méthode de Newton, et l'approche de moindres carrés pour ajuster une parabole à des données. Il aborde également des concepts de convergence et de conditions d'optimalité, ainsi que des exercices pratiques pour développer des algorithmes en MatLab. Enfin, il propose des méthodes de calcul et des tests numériques pour évaluer les performances des algorithmes.

Transféré par

beckerrolandh
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
7 vues2 pages

Méthodes d'optimisation numérique en M1

Le document traite de l'optimisation numérique à travers plusieurs exercices, notamment l'application de la méthode du gradient pour résoudre des systèmes linéaires, l'inversion de matrices par la méthode de Newton, et l'approche de moindres carrés pour ajuster une parabole à des données. Il aborde également des concepts de convergence et de conditions d'optimalité, ainsi que des exercices pratiques pour développer des algorithmes en MatLab. Enfin, il propose des méthodes de calcul et des tests numériques pour évaluer les performances des algorithmes.

Transféré par

beckerrolandh
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Master MMS M1 TD No.

2 11 février 2008
Optimisation numérique
R. Becker et R. Luce

Exercice n◦ 1 Méthode de gradient


Soit A ∈ Rn×n symétrique définie positive et b ∈ Rn . Pour la résolution de Ax = b on applique
l’algorithme du gradient avec pas constant (de longueur t) à une fonction quadratique f que l’on
précisera.
1. Ecrire l’algorithme.
2. Soit x∗ la solution et ek := x∗ − xk . Démontrer que ek = (I − tA)k e0 .
3. Soient 0 < λ1 ≤ λ2 ≤ . . . ≤ λn les valeurs propres de A. Montrer que l’algorithme converge
si et seulement si 0 < t < 2/λn .
4. Montrer que le meilleur choix est t∗ = 2/(λn +λ1 ) et alors que ρ(I −t∗ A) = (λn −λ1 )/(λn +λ1 ).
2
(On pourra étudier la quantité sup 1− λ1 +λn .)
λ1 ≤λ≤λn

Exercice n◦ 2 Newton pour l’inversion d’une matrice


On considère A ∈ Rn×n une matrice régulière.
On cherche son inverse par la méthode de Newton appliquée à la fonction f (X) = A − X −1 .
i) Montrer que l’itération de newton vérifie Xn+1 = 2Xn − Xn AXn ;
ii) Montrer que si kI − X0 Ak2 < 1 alors l’algorithme converge.
On pourra montrer que I −Xn+1 A = (I −Xn A)2 , et en déduire une majoration de kI −Xn Ak2
en fonction de kI − X0 Ak2 .
iii) Montrer que la méthode converge en partant de X0 := AT /T r(AT A).
iv) Si on connaı̂t ρ(A), comment choisir simplement X0 ?

Exercice n◦ 3
Soit A ∈ Rn×n symétrique définie. Montrer qu’il existe γ > 0 tel que

xT Ax ≥ γ |x|2 ∀x ∈ Rn . (1)

Exercice n◦ 4
Soit F : Rn → Rn différentiable. On partition pour 0 < k < n les variables indépendantes comme
(x1 , . . . , xk , . . . , xn ) = (y, z) ∈ Rk × Rn−k . De la même façon on écrit F (x) = (G(x), H(x)) =
(G(y, z), H(y, z)).

1
Une variante de la méthode de Newton pour la résolution du system F (x) = 0 est:
−1
∂G(y k , z k )

y k+1 = yk − G(y k , z k )
∂y
−1
∂H(y k+1 , z k )

z k+1 = zk − H(y k+1 , z k )
∂z

Montrer que si les composantes de F sont affine-linéaire, cette méthode est la méthode de Gauß-
Seidel par bloc. Quand est-ce que la méthode est bien défine ? Comparer la méthode avec Newton.
Laquelle est plus rapide ?

Exercice n◦ 5 Lissage
On se propose d’approcher un nuage de points donnés par les couples de rééls (xi , yi )1≤i≤N par une
parabole de la forme y = f (x) = a + bx + cx2 , où les paramètres a, b, c sont à déterminer.
1. Exprimer le problème sous forme de problème de minimisation au sens des moindres carrés.

2. Ce problème de minimisation a-t-il une solution ? Si oui, est-elle unique ?


3. Ecrire le système d’optimalité.
4. Proposer un méthode de calcul.

Exercice n◦ 6 TP 1
(Le but de cettes suite d’exercices est de développer une collection de fonctions d’optimisation en
MatLab, qui servira à tester les algorithmes du cours numériquement).
Partie 1
1. Programmer l’algorithme du gradient (on considère g comme entrée du programme),
2. Tester votre programme sur différentes fonctions (cf A.N.F).

3. Comparer les résultats obtenus avec ceux obtenus par la méthodes de Newton et la variante
vues en A.N.F
Partie 2
Programmer la méthode de l’exercice 2.
On définira l’erreur par en = kI − Xn Ak2
Tester numériquement la méthode pour des tailles n diverses: n = 2, 10, 50, 100. (On pourra
commancer par n = 2 et A = [2 − 1; −12], puis A = rand(2, 2)).
Peut-on toujours obtenir kI − Xn Ak2 = 0 à la précision machine près ?

Vous aimerez peut-être aussi