Université Sidi Moham med Ben Abdella h Année univers itaire 2024-2025
Faculté des Sciences Dhar El Mahraz
Départ ement de Mathém atiques
SMA/S 6
TD- Progra mmatio n Mathém atique 2
Exerci ce l :
Soit le problem e d'optim isation sans contrai ntes suiyant :
min J(1:, y) == 3x2 + 3y2 .
(x,y)ER 2
1. Appliqu er deux it<;ration~ d(-' la UH~thode du gradien t à pas fixe eu
prenant . conune point de départ (xo, Yo) == (1, 1).
2. Appliqu er deux itératio ns de la 1néthod e du gradien t à P~"' optirna l en
prenan t co1nn1e point de départ (x 0 , y0 ) == (1, 1).
Exercice 2.. ()n con~üJ~rc la fonction ./: il1'.~ -4 LI{+, défi nie pour :c ·.::.. ( )' 1· 1:2)' par
(
q ' ') ')'.
./( .r) :--=: ( :r 1 - l J- + (:·r:- 2 ·- :T:'.l )"''.
1. Qul'I est k miJ1imurn de .J(:r) '! où l'St-il atteint •.
1
f;:I'"
'
0: 0 )1 t'St-il une direction de descente au point (0: l)t? t
2. L~ vecteur (ll. 1
~- Si oui. truu\·er le n1ininwr n de J dan~ cette direction.
Exercice 03
On veut résoudr e le systèn1e Ax == b, x E ]Rn ( avec A symétri que, définie, positive)
par une méthod e ---
de gradien t à pas constan t.
Soit x la solutio n de ce système.
On propos e l'algori thme suivant :
xo, ro == b - Ax0 ,
Xk+l = Xk + a:rk'
où Tk = b-Axk ,
a est un réel constan t.
a) Soit ek == Xk - x (pour A: > O); montre r que ek = (J - aA)ke 0 ,
(pour k > 0).
b) soient O < Àn < < ... < À1 les valeurs propres de A.
Àn-1
I\1ontrer que l'lgorithme converge si et seulen1ent si O < ü < l·
c) Montre r que le meilleur choix de a est : Oopt = À
1
!.-\n
et qu'alor s :
i 1
l ,./.,
Rx • 04
-"d. e:r:_c1ce
- J
Soit f (x 1' x 2 ) -_ X12 -x1x 2 + X22 -3x2 avec x == lx1 dans R2.
• . X2
On considère le pl'Oblème: min 2 /(x1 ,x2)
(.r1~2)=ll
s01't x (0) === (0) , Ja valeur de/.·en x< >est / (xC0 ) ) = O.
0
0
I. Calculer V/le gradient de/.
tion k.,
2 • ~n partant de x<0). appliquer la méthode du gradient conjugué (2 itérations). Pour _calculer ~(.c.~ à l'itéra
( ,
• lvJ( (l+J) ,tl
uru. Vérifier que le point
1v, If .
Calculer la valeur dé/ en chaque poin t parco
on pourra utiliser ~(k) -= J.:: (.r<•> .
trouvé à la 2~ itération est bien un point critique de f.
Exe rcic e 05
Soit f(x)= ½x' Ax+ b' x avec A=(
4 - J\
-1 2
1
(J ( Xt 2
}' b = 2' et x = x e R •
2
)"
1
= (11 1 ui).
La transposée d'un vecteur u = ( ::) est notée u
On veut résoudre le probl ème:
'·!-
2
(P) minin1iser f(x) s.c. x E R
0 ·.:(,:·..•:.
l) On considère le p~int x< ) =(~ }
Construire r(l) = r(o} +td(o ) avec t e R qui minim
ise J(x(o) + td(o)) où d(o) ={ ~) est la. d~ection opposée
au gradient de/au point r(o). @ · ·• :~
l) On va ici construire la direction suivante.
i) pour êtro conjuguée à d(o) par ra~~ rt à A.
a) Donner la relation que doit vérifier d(I) =(d
d2 ...,,~-,,.
~"".i.
b) 'i>onner la condition que doit yérifier d(I) = ( :;J pour être une direction de descente de/au point x(I).
Tenant compte de la relation trouvée à la question a), en
déduire que d2 doit être négatif.
c) Constnûre i 1) =(~) conjuguée à i 0) par rapport à A et telle que d 2 =: -2 .
+ rd(l)).
3) Construire x(i) =x<i) + td( ) avec te R qui minimise /~(t)
1
ier l'optin1alité de x(2) pour le problème (l>).
Est-il nécessaire de faire une itératio~ supplémentaire? Vérif
Exercice 6. Calculer
l' ,. > . !/ • .)
i' .i/ _I '
c1vec
. , , . n
/.>C le -k! ;;:- br~- t ~ Vtff ( t:,cf-}
~ [1, ;t)
0
V IX ~ 112l • j
oVJ"~~ ~ = f?c f~o )
t9A-'"'- €- E c~ :
"6 /;("
r--;;;;;~ aJ~ lj \ ô~ J l
Vf (tx d~ .:: (~ r ~
lt-o~ J !- .J \.ru ~ t,..
G -~J-0t ..-~, 1-v, f .If X, ........✓
a
\J- )< / y ~ t/li_ Y l'Jt.l,' { X= {Ûr ~)
1
.> =- { /2t- ~ ~(} ~~
~ .
L -= @
0
0
~~ o,., t · ~
_J~~ ~ [ 1..} : .1; /J. .:; /xô _ & iJ//;xo) -1
•
-=- ~ o - D;:t tJ (j /ho}:
1- o/ t x{
t
- o,.>L X /
-
-
- ,t -
~~ t
.l'i 'i; = lx1. - o_.1 i Vi (tx:1}
1
i) G. p. ~ .
h ~ +4-:;- kk _ tl< V f //$'k)
'
ijo ~ {:)
'
-~ i
1
'
l
--
IJ -~ J ~~ JR ~~ c~.lt p œ.. dJ(
J/-r· ( J, tr//;> ( O. (v )
•
l
-
-
•
fTI
\ , ~
"---1-
~
<l
D--
--...\
~
~
' l
,,
C)
1 '
~ 1f;(:t , J:i Q. i 0' \
) '; .t:J 1. - .1) :1 1:,(
~ /.t 1~ - "'1> ./.)
tl:-:-
1
{ -2 \
i
ô' 1
1
1
0
Vf=
1
\
1
\
\
\
\
0
\
0
\
"?/t
ô
,~
)/tt
.
•
f ( +l :::: ffI ;x. tel) A-.
-t .
~/2., ~ ~ 1-
-l l1.+lJ " ./ fi
tf l ~ l = 0
I
=) - { 1_ t ~ 6 = i) l- =- } .
C~ C l .,,.f i4 -: 1= 1 ~ 2 . ::: ~ 1 . +- L2 J_ 1. ,::;
,c
V t( ~,.\: "" q
.11 ~ - l>("-f 1
G ), -t b 1 -""> l> (i ~ -(. >_ ô )
r
-~
-i0
l-1 t J.-L)-t l-~~k't)
:; ;0
4-1:- - 1 ; ; 0 ~ 1: b :a- -¾
~
t ):I.A. -;
tf-11 J1
c.1 •
.: d i 1 ) IL/.1 ç..
C- c,.~ C cl { cf"'' \î A eto) ::: 0
Jt. 3
-~ ) 1 i( ¾ 1 c -t f 0 , 4 0< k - l }
D ~2_/ . if :; - 4-I ½ ~ -t ),
1
ri!
_,
-
1k +~.
)x h+t·-= ~ k ._. ~ (J:,t k -~ ).
1
~ ~+-<- _;-~ie - ~ l ss~ ~)
~
• :f 1i .-A'}
{l f. (- -l2 J~
3
li.Xi; - t ).
l IXk -~i :: ( t )~ L 60 -~ ) ~ /1 Ir:: -1
lf) 'Ao - l-) >-) ~ lj k : ~ ,.
L 'a,,_ - 1..l :: ,C (
