Centrale Maths 2 PC 2009

Thème de l'épreuve Méthode du gradient
Principaux outils utilisés algèbre linéaire, espaces vectoriels normés

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                    

Rapport du jury

(télécharger le PDF)
        

Énoncé obtenu par reconnaissance optique des caractères


- version du 17 mars 2009 9h38

MATHÉMATIQUES II

x  K n , f M (x) = Mx.
L'image de f M , (Im f M ) sera notée Im(M) et le noyau de f M , (Ker f M ) 
sera noté
Ker(M).
Pour toute matrice M de Mn (K), on note (M) le spectre de M, c'est-à-dire
l'ensemble de ses valeurs propres complexes. On note (M) le rayon spectral
de M, c'est-à-dire le plus grand module des valeurs propres de M.
On dira qu'une suite de K n (respectivement de Mn (K)) converge, ou est 
convergente, si elle converge pour une norme particulière de K n 
(respectivement de
Mn (K)). On sait qu'elle converge alors pour toute norme de K n (respectivement 
de Mn (K)) puisque ces espaces sont de dimension finie.
L'espace vectoriel R n est muni de son produit scalaire canonique, noté h , i. 
La
norme euclidienne associée est notée || ||.
Un endomorphisme symétrique f de R n est dit positif si, pour tout x de R n ,
h f (x), xi > 0.
Un endomorphisme symétrique est dit défini positif si, pour tout x de R n , x
non nul, h f (x), xi > 0.
On dit de même qu'une matrice symétrique M  Mn (R) est positive si 
l'endomorphisme de R n canoniquement associé à M est positif, et qu'elle est 
définie
positive si ce même endomorphisme est défini positif.

La notation K désigne indifféremment l'ensemble R des nombres réels ou 
l'ensemble C des nombres complexes.
n désigne un entier supérieur ou égal à 1.
On note Mn (K) l'ensemble des matrices carrées d'ordre n > 1 à coefficients
dans K. La matrice identité de Mn (K) est notée I.
Dans tout le problème, on identifie les deux espaces vectoriels Mn,1 (K) et K n 
,
c'est-à-dire qu'on identifie un vecteur de K n avec le vecteur colonne de ses
composantes dans la base canonique de K n . De la sorte, si M  Mn (K) et
x  K n , on peut former le produit Mx  K n , ce qui permet de définir 
l'endomorphisme f M canoniquement associé à M par :

Partie I - La fonctionnelle J

Filière

PC

appelée la fonctionnelle associée à A.

v  R n , J(v) =

1
hAv, vi - hb, vi.
2

I.C - On suppose dans cette question que la matrice A de Mn (R) est symétrique
positive et on définit l'application J de R n dans R :

d) Déterminer la nature géométrique de la surface  de R3 d'équation x3 = F(x1 , 
x2 ).
e) Déduire de la question précédente que la fonction F admet un minimum global
sur R2 , que l'on précisera.

c) En déduire que la fonction F admet un unique point critique sur R2 .

a) Justifier que la fonction F est de classe C1 sur R2 .
La fonction gradient de F (grad F) est notée F.
b) Prouver que :
 v  R2 , F(v) = Av - b.

Dans cette question, on pose A =

75
13 -4
. On définit la
et b =
-75
-4 7
fonction F sur R2 à valeurs dans R de la façon suivante :

1
x1
de R2 , F(v) = hAv, vi - hb, vi.
pour tout v =
x2
2

I.B - Cas particulier : n = 2

I.A - Question préliminaire
I.A.1) Montrer qu'une matrice symétrique M de Mn (R) est positive si et 
seulement si son spectre (M) est inclus dans R + , et qu'elle est définie 
positive si et
seulement si son spectre (M) est inclus dans R + \ {0}.

Page 1/4

Dans tout le problème, A  Mn (R) est une matrice symétrique, b  R n est un 
vecteur fixé, et l'on étudie des méthodes itératives pour approcher la ou les 
solutions
du système Ax = b.

·

·

·

·
·

·

Les calculatrices sont autorisées
Notations et objet du problème

Épreuve :

Concours Centrale - Supélec 2009

- version du 17 mars 2009 9h38

MATHÉMATIQUES II

x  K n , f M (x) = Mx.
L'image de f M , (Im f M ) sera notée Im(M) et le noyau de f M , (Ker f M ) 
sera noté
Ker(M).
Pour toute matrice M de Mn (K), on note (M) le spectre de M, c'est-à-dire
l'ensemble de ses valeurs propres complexes. On note (M) le rayon spectral
de M, c'est-à-dire le plus grand module des valeurs propres de M.
On dira qu'une suite de K n (respectivement de Mn (K)) converge, ou est 
convergente, si elle converge pour une norme particulière de K n 
(respectivement de
Mn (K)). On sait qu'elle converge alors pour toute norme de K n (respectivement 
de Mn (K)) puisque ces espaces sont de dimension finie.
L'espace vectoriel R n est muni de son produit scalaire canonique, noté h , i. 
La
norme euclidienne associée est notée || ||.
Un endomorphisme symétrique f de R n est dit positif si, pour tout x de R n ,
h f (x), xi > 0.
Un endomorphisme symétrique est dit défini positif si, pour tout x de R n , x
non nul, h f (x), xi > 0.
On dit de même qu'une matrice symétrique M  Mn (R) est positive si 
l'endomorphisme de R n canoniquement associé à M est positif, et qu'elle est 
définie
positive si ce même endomorphisme est défini positif.

La notation K désigne indifféremment l'ensemble R des nombres réels ou 
l'ensemble C des nombres complexes.
n désigne un entier supérieur ou égal à 1.
On note Mn (K) l'ensemble des matrices carrées d'ordre n > 1 à coefficients
dans K. La matrice identité de Mn (K) est notée I.
Dans tout le problème, on identifie les deux espaces vectoriels Mn,1 (K) et K n 
,
c'est-à-dire qu'on identifie un vecteur de K n avec le vecteur colonne de ses
composantes dans la base canonique de K n . De la sorte, si M  Mn (K) et
x  K n , on peut former le produit Mx  K n , ce qui permet de définir 
l'endomorphisme f M canoniquement associé à M par :

Partie I - La fonctionnelle J

Filière

PC

appelée la fonctionnelle associée à A.

v  R n , J(v) =

1
hAv, vi - hb, vi.
2

I.C - On suppose dans cette question que la matrice A de Mn (R) est symétrique
positive et on définit l'application J de R n dans R :

d) Déterminer la nature géométrique de la surface  de R3 d'équation x3 = F(x1 , 
x2 ).
e) Déduire de la question précédente que la fonction F admet un minimum global
sur R2 , que l'on précisera.

c) En déduire que la fonction F admet un unique point critique sur R2 .

a) Justifier que la fonction F est de classe C1 sur R2 .
La fonction gradient de F (grad F) est notée F.
b) Prouver que :
 v  R2 , F(v) = Av - b.

Dans cette question, on pose A =

75
13 -4
. On définit la
et b =
-75
-4 7
fonction F sur R2 à valeurs dans R de la façon suivante :

1
x1
de R2 , F(v) = hAv, vi - hb, vi.
pour tout v =
x2
2

I.B - Cas particulier : n = 2

I.A - Question préliminaire
I.A.1) Montrer qu'une matrice symétrique M de Mn (R) est positive si et 
seulement si son spectre (M) est inclus dans R + , et qu'elle est définie 
positive si et
seulement si son spectre (M) est inclus dans R + \ {0}.

Page 1/4

Dans tout le problème, A  Mn (R) est une matrice symétrique, b  R n est un 
vecteur fixé, et l'on étudie des méthodes itératives pour approcher la ou les 
solutions
du système Ax = b.

·

·

·

·
·

·

Les calculatrices sont autorisées
Notations et objet du problème

Épreuve :

Concours Centrale - Supélec 2009

- version du 17 mars 2009 9h38

MATHÉMATIQUES II

x  K n , f M (x) = Mx.
L'image de f M , (Im f M ) sera notée Im(M) et le noyau de f M , (Ker f M ) 
sera noté
Ker(M).
Pour toute matrice M de Mn (K), on note (M) le spectre de M, c'est-à-dire
l'ensemble de ses valeurs propres complexes. On note (M) le rayon spectral
de M, c'est-à-dire le plus grand module des valeurs propres de M.
On dira qu'une suite de K n (respectivement de Mn (K)) converge, ou est 
convergente, si elle converge pour une norme particulière de K n 
(respectivement de
Mn (K)). On sait qu'elle converge alors pour toute norme de K n (respectivement 
de Mn (K)) puisque ces espaces sont de dimension finie.
L'espace vectoriel R n est muni de son produit scalaire canonique, noté h , i. 
La
norme euclidienne associée est notée || ||.
Un endomorphisme symétrique f de R n est dit positif si, pour tout x de R n ,
h f (x), xi > 0.
Un endomorphisme symétrique est dit défini positif si, pour tout x de R n , x
non nul, h f (x), xi > 0.
On dit de même qu'une matrice symétrique M  Mn (R) est positive si 
l'endomorphisme de R n canoniquement associé à M est positif, et qu'elle est 
définie
positive si ce même endomorphisme est défini positif.

La notation K désigne indifféremment l'ensemble R des nombres réels ou 
l'ensemble C des nombres complexes.
n désigne un entier supérieur ou égal à 1.
On note Mn (K) l'ensemble des matrices carrées d'ordre n > 1 à coefficients
dans K. La matrice identité de Mn (K) est notée I.
Dans tout le problème, on identifie les deux espaces vectoriels Mn,1 (K) et K n 
,
c'est-à-dire qu'on identifie un vecteur de K n avec le vecteur colonne de ses
composantes dans la base canonique de K n . De la sorte, si M  Mn (K) et
x  K n , on peut former le produit Mx  K n , ce qui permet de définir 
l'endomorphisme f M canoniquement associé à M par :

Partie I - La fonctionnelle J

Filière

PC

appelée la fonctionnelle associée à A.

v  R n , J(v) =

1
hAv, vi - hb, vi.
2

I.C - On suppose dans cette question que la matrice A de Mn (R) est symétrique
positive et on définit l'application J de R n dans R :

d) Déterminer la nature géométrique de la surface  de R3 d'équation x3 = F(x1 , 
x2 ).
e) Déduire de la question précédente que la fonction F admet un minimum global
sur R2 , que l'on précisera.

c) En déduire que la fonction F admet un unique point critique sur R2 .

a) Justifier que la fonction F est de classe C1 sur R2 .
La fonction gradient de F (grad F) est notée F.
b) Prouver que :
 v  R2 , F(v) = Av - b.

Dans cette question, on pose A =

75
13 -4
. On définit la
et b =
-75
-4 7
fonction F sur R2 à valeurs dans R de la façon suivante :

1
x1
de R2 , F(v) = hAv, vi - hb, vi.
pour tout v =
x2
2

I.B - Cas particulier : n = 2

I.A - Question préliminaire
I.A.1) Montrer qu'une matrice symétrique M de Mn (R) est positive si et 
seulement si son spectre (M) est inclus dans R + , et qu'elle est définie 
positive si et
seulement si son spectre (M) est inclus dans R + \ {0}.

Page 1/4

Dans tout le problème, A  Mn (R) est une matrice symétrique, b  R n est un 
vecteur fixé, et l'on étudie des méthodes itératives pour approcher la ou les 
solutions
du système Ax = b.

·

·

·

·
·

·

Les calculatrices sont autorisées
Notations et objet du problème

Épreuve :

Concours Centrale - Supélec 2009

hAv, hi = hAh, vi.

Prouver que, pour tout couple (v, h) de vecteurs de R n , on a :

Partie II - Méthode du gradient à pas constant

Filière PC

16i6n

x  R n , x = (x1 , . . . , xn ), ||x|| = max |xi |.

On définit sur C n la norme || || par :

(Mx)
·
max
n
xC , x6=0 (x)

Soit N une norme subordonnée sur Mn (C).

j=1

Soit M une matrice de Mn (C) et  > 0 fixé.

II.A.5)

x 7 Mx + c.

Soit M  Mn (C) et c  C n . On définit l'application f de C n dans C n par :

a) Prouver l'existence d'une matrice P inversible et d'un réel  > 0 tel que :
N (P-1 P-1 MPP ) 6 (M) + .
b) En déduire qu'il existe une norme subordonnée N sur Mn (C) telle que :
N(M) 6 (M) + .

II.A.4)

a) Calculer P-1 MP .
b) En déduire que, pour tout  > 0, il existe  > 0 tel que N (P-1 MP ) 6 (M) + .

II.A.3) Soit M = (mij )16i,j6n une matrice triangulaire supérieure de Mn (C)
( c'est-à-dire mij = 0 si i > j).
Soit  un nombre réel strictement positif, et P la matrice diagonale diag(1, , · 
· · , n-1 ),
c'est-à-dire dont le i-ème coefficient diagonal est i-1 .

a) Montrer que :  A, B  Mn (C), N(AB) 6 N(A).N(B).
En déduire que :  n  N, N(An ) 6 (N(A))n .
b) Montrer que, pour tout M  Mn (C), (M) 6 N(M).

II.A.2)

n

 |mij |.
16i6n

Montrer que, pour toute matrice M = (mij )  Mn (C), N (M) = max

On note N la norme sur Mn (C) subordonnée à ||.|| .

II.A.1)

On dit que N est subordonnée à .

N(M) =

II.A - Normes matricielles et rayon spectral
Une norme N sur Mn (C) est dite subordonnée s'il existe une norme  sur C n telle
que, pour tout M  Mn (C),

Page 2/4

I.C.5) On suppose que la matrice A est symétrique positive, mais non inversible,
et que b appartient à Im(A). On note u0 un élément de R n tel que Au0 = b.
Déterminer l'ensemble des vecteurs v0 tels que J(v0 ) = inf n J(v) et préciser 
sa navR
ture géométrique.

pour tout couple (u, v) de vecteurs de R n .

||J(v) - J(u)|| 6 m||v - u||

hJ(v) - J(u), v - ui > ||v - u||2

I.C.4) On suppose encore que la matrice A est définie positive. Déterminer deux
constantes  > 0 et m > 0 en fonction du spectre de A telles que :

I.C.3) On suppose que la matrice A est symétrique définie positive.
a) Montrer qu'il existe un unique v0  R n tel que J(v0 ) = inf n J(v), et le 
détermivR
ner en fonction de A et b.
b) Soit v  R n et d  R n , d non nul.
Montrer qu'il existe un unique r  R tel que J(v - rd) = inf J(v - d).
R
Exprimer r en fonction de v, d et A.

J(v0 ) = 0.

En observant que J(v0 + th) > J(v0 ) pour tout h  R n et tout t  R, montrer que 
:

Quel est le signe de R(h) ?
b) On suppose qu'un vecteur v0  R n est tel que J(v) > J(v0 ) pour tout v  R n .

 v, h  R n , J(v + h) = J(v) + hJ(v), hi + R(h).

On pose J(v) = Av - b pour tout v  R n .
I.C.2)
a) Expliciter la fonction R : R n  R telle que

I.C.1)

MATHÉMATIQUES II

hAv, hi = hAh, vi.

Prouver que, pour tout couple (v, h) de vecteurs de R n , on a :

Partie II - Méthode du gradient à pas constant

Filière PC

16i6n

x  R n , x = (x1 , . . . , xn ), ||x|| = max |xi |.

On définit sur C n la norme || || par :

(Mx)
·
max
n
xC , x6=0 (x)

Soit N une norme subordonnée sur Mn (C).

j=1

Soit M une matrice de Mn (C) et  > 0 fixé.

II.A.5)

x 7 Mx + c.

Soit M  Mn (C) et c  C n . On définit l'application f de C n dans C n par :

a) Prouver l'existence d'une matrice P inversible et d'un réel  > 0 tel que :
N (P-1 P-1 MPP ) 6 (M) + .
b) En déduire qu'il existe une norme subordonnée N sur Mn (C) telle que :
N(M) 6 (M) + .

II.A.4)

a) Calculer P-1 MP .
b) En déduire que, pour tout  > 0, il existe  > 0 tel que N (P-1 MP ) 6 (M) + .

II.A.3) Soit M = (mij )16i,j6n une matrice triangulaire supérieure de Mn (C)
( c'est-à-dire mij = 0 si i > j).
Soit  un nombre réel strictement positif, et P la matrice diagonale diag(1, , · 
· · , n-1 ),
c'est-à-dire dont le i-ème coefficient diagonal est i-1 .

a) Montrer que :  A, B  Mn (C), N(AB) 6 N(A).N(B).
En déduire que :  n  N, N(An ) 6 (N(A))n .
b) Montrer que, pour tout M  Mn (C), (M) 6 N(M).

II.A.2)

n

 |mij |.
16i6n

Montrer que, pour toute matrice M = (mij )  Mn (C), N (M) = max

On note N la norme sur Mn (C) subordonnée à ||.|| .

II.A.1)

On dit que N est subordonnée à .

N(M) =

II.A - Normes matricielles et rayon spectral
Une norme N sur Mn (C) est dite subordonnée s'il existe une norme  sur C n telle
que, pour tout M  Mn (C),

Page 2/4

I.C.5) On suppose que la matrice A est symétrique positive, mais non inversible,
et que b appartient à Im(A). On note u0 un élément de R n tel que Au0 = b.
Déterminer l'ensemble des vecteurs v0 tels que J(v0 ) = inf n J(v) et préciser 
sa navR
ture géométrique.

pour tout couple (u, v) de vecteurs de R n .

||J(v) - J(u)|| 6 m||v - u||

hJ(v) - J(u), v - ui > ||v - u||2

I.C.4) On suppose encore que la matrice A est définie positive. Déterminer deux
constantes  > 0 et m > 0 en fonction du spectre de A telles que :

I.C.3) On suppose que la matrice A est symétrique définie positive.
a) Montrer qu'il existe un unique v0  R n tel que J(v0 ) = inf n J(v), et le 
détermivR
ner en fonction de A et b.
b) Soit v  R n et d  R n , d non nul.
Montrer qu'il existe un unique r  R tel que J(v - rd) = inf J(v - d).
R
Exprimer r en fonction de v, d et A.

J(v0 ) = 0.

En observant que J(v0 + th) > J(v0 ) pour tout h  R n et tout t  R, montrer que 
:

Quel est le signe de R(h) ?
b) On suppose qu'un vecteur v0  R n est tel que J(v) > J(v0 ) pour tout v  R n .

 v, h  R n , J(v + h) = J(v) + hJ(v), hi + R(h).

On pose J(v) = Av - b pour tout v  R n .
I.C.2)
a) Expliciter la fonction R : R n  R telle que

I.C.1)

MATHÉMATIQUES II

Filière PC

k+

k

- uk ||2 .
||u
2 k+1

k

k+
v0 ||2 . Prouver

Montrer que ||dk || 6 ||dk - dk+1 ||, puis que lim dk = 0.
III.A.5) Montrer que hJ(uk ), uk - v0 i > ||uk -
lim ||uk - v0 || = 0.

III.A.4)

III.A.3) Prouver que la suite (J(uk ))kN est convergente.
Montrer alors que lim ||uk+1 - uk || = 0.

J(uk ) - J(uk+1 ) >

finalement que

on choisit u0  R n et l'on pose d0 = J(u0 ) ;
en supposant uk déjà construit, on définit uk+1 en fonction de uk de la façon
suivante :
on pose dk = J(uk ) et on détermine rk  R tel que J(uk - rk dk ) = inf J(uk - 
dk )
R
(cf. I.C.3.b).
On pose alors uk+1 = uk - rk dk . La suite (uk )kN est donc bien définie, ainsi
que la suite (dk )kN .
III.A III.A.1) Montrer que, pour tout entier k, hdk+1 , dk i = 0.
III.A.2) Montrer qu'il existe  > 0 dépendant du spectre de A tel que :
·
·

Dans cette partie, A  Mn (R) est symétrique définie positive. On note v0  R n le
vecteur tel que Av0 = b.
On construit une suite (uk )kN par récurrence :

Partie III - Méthode du gradient à pas optimal

g) Quelle relation le vecteur u vérifie -t-il ?

f) En déduire que la suite (uk )kN est convergente dans le sous-espace Im(S-1 
A).
On note u sa limite. On peut donc écrire :
lim uk = u + w.

e) Dans cette question, on note id l'endomorphisme identité de l'espace Im(S-1 
A).
Montrer que le polynôme caractéristique de id - g est scindé sur R , et que le
rayon spectral de id - g est strictement inférieur à 1.

On note n la plus grande valeur propre de S-1 A, et l'on suppose, jusqu'à la 
fin de
2
cette partie, que 0 <  <
·.
n

Page 3/4

d) Montrer qu'on définit un automorphisme linéaire g de Im(S-1 A) en posant
g(x) = S-1 Ax pour tout x  Im(S-1 A).

c) Montrer que les valeurs propres complexes de la matrice S-1 A sont toutes 
réelles
positives ou nulles.
Il pourra être utile de montrer que pour toute matrice X de Mn,1 (C), X 6= 0, t 
XSX > 0 .

b) Pour tout k, uk s'écrit donc uk = w + uk avec uk  Im(S-1 A). Préciser 
l'application f : Im(S-1 A)  Im(S-1 A) telle que uk+1 = f (uk ) pour tout k.

pour tout k  N, u0  R n étant arbitrairement choisi.
a) Montrer que la composante du vecteur uk sur le sous-espace Ker(A), dans la 
décomposition R n = Im(S-1 A)  Ker(A), est indépendante de k ; on la note w.

uk+1 = uk - S-1 J(uk )

II.B.3) Montrer que, dans Im(S-1 A), le système linéaire Au = b possède une
unique solution notée u . Décrire l'ensemble des solutions dans R n .
II.B.4) Étant donné un nombre réel , on définit la suite récurrente

II.B.2) Montrer que les sous-espaces Im(S-1 A) et Ker(A) sont orthogonaux pour
le produit scalaire  défini à la question précédente.
En déduire qu'ils sont supplémentaires.

II.B.1) Montrer que l'application définie par (u, v) = hSu, vi, pour tout couple
(u, v) de vecteurs de R n , fournit un produit scalaire sur l'espace R n .

II.B - Méthode du gradient à pas constant
Soit A une matrice symétrique positive, mais pas nécessairement inversible, b un
vecteur appartenant à l'espace Im(A), et J la fonctionnelle associée à A.
On note x0 un élément de R n tel que b = Ax0
On désigne par S une matrice symétrique définie positive donnée.

Montrer l'équivalence des assertions (i) et (ii) ci-dessous :
(i) Pour tout x0  C n , la suite (xk )kN , définie par xk+1 = f (xk ), est 
convergente,
et sa limite est indépendante de x0 .
(ii) I - M est inversible et (M) < 1.
Il pourra être utile d'introduire un réel  > 0 et de choisir une norme 
subordonnée N sur
Mn (C) telle qu'on ait l'inégalité N(M) 6 (M) +  pour la matrice M considérée.

MATHÉMATIQUES II

Filière PC

k+

k

- uk ||2 .
||u
2 k+1

k

k+
v0 ||2 . Prouver

Montrer que ||dk || 6 ||dk - dk+1 ||, puis que lim dk = 0.
III.A.5) Montrer que hJ(uk ), uk - v0 i > ||uk -
lim ||uk - v0 || = 0.

III.A.4)

III.A.3) Prouver que la suite (J(uk ))kN est convergente.
Montrer alors que lim ||uk+1 - uk || = 0.

J(uk ) - J(uk+1 ) >

finalement que

on choisit u0  R n et l'on pose d0 = J(u0 ) ;
en supposant uk déjà construit, on définit uk+1 en fonction de uk de la façon
suivante :
on pose dk = J(uk ) et on détermine rk  R tel que J(uk - rk dk ) = inf J(uk - 
dk )
R
(cf. I.C.3.b).
On pose alors uk+1 = uk - rk dk . La suite (uk )kN est donc bien définie, ainsi
que la suite (dk )kN .
III.A III.A.1) Montrer que, pour tout entier k, hdk+1 , dk i = 0.
III.A.2) Montrer qu'il existe  > 0 dépendant du spectre de A tel que :
·
·

Dans cette partie, A  Mn (R) est symétrique définie positive. On note v0  R n le
vecteur tel que Av0 = b.
On construit une suite (uk )kN par récurrence :

Partie III - Méthode du gradient à pas optimal

g) Quelle relation le vecteur u vérifie -t-il ?

f) En déduire que la suite (uk )kN est convergente dans le sous-espace Im(S-1 
A).
On note u sa limite. On peut donc écrire :
lim uk = u + w.

e) Dans cette question, on note id l'endomorphisme identité de l'espace Im(S-1 
A).
Montrer que le polynôme caractéristique de id - g est scindé sur R , et que le
rayon spectral de id - g est strictement inférieur à 1.

On note n la plus grande valeur propre de S-1 A, et l'on suppose, jusqu'à la 
fin de
2
cette partie, que 0 <  <
·.
n

Page 3/4

d) Montrer qu'on définit un automorphisme linéaire g de Im(S-1 A) en posant
g(x) = S-1 Ax pour tout x  Im(S-1 A).

c) Montrer que les valeurs propres complexes de la matrice S-1 A sont toutes 
réelles
positives ou nulles.
Il pourra être utile de montrer que pour toute matrice X de Mn,1 (C), X 6= 0, t 
XSX > 0 .

b) Pour tout k, uk s'écrit donc uk = w + uk avec uk  Im(S-1 A). Préciser 
l'application f : Im(S-1 A)  Im(S-1 A) telle que uk+1 = f (uk ) pour tout k.

pour tout k  N, u0  R n étant arbitrairement choisi.
a) Montrer que la composante du vecteur uk sur le sous-espace Ker(A), dans la 
décomposition R n = Im(S-1 A)  Ker(A), est indépendante de k ; on la note w.

uk+1 = uk - S-1 J(uk )

II.B.3) Montrer que, dans Im(S-1 A), le système linéaire Au = b possède une
unique solution notée u . Décrire l'ensemble des solutions dans R n .
II.B.4) Étant donné un nombre réel , on définit la suite récurrente

II.B.2) Montrer que les sous-espaces Im(S-1 A) et Ker(A) sont orthogonaux pour
le produit scalaire  défini à la question précédente.
En déduire qu'ils sont supplémentaires.

II.B.1) Montrer que l'application définie par (u, v) = hSu, vi, pour tout couple
(u, v) de vecteurs de R n , fournit un produit scalaire sur l'espace R n .

II.B - Méthode du gradient à pas constant
Soit A une matrice symétrique positive, mais pas nécessairement inversible, b un
vecteur appartenant à l'espace Im(A), et J la fonctionnelle associée à A.
On note x0 un élément de R n tel que b = Ax0
On désigne par S une matrice symétrique définie positive donnée.

Montrer l'équivalence des assertions (i) et (ii) ci-dessous :
(i) Pour tout x0  C n , la suite (xk )kN , définie par xk+1 = f (xk ), est 
convergente,
et sa limite est indépendante de x0 .
(ii) I - M est inversible et (M) < 1.
Il pourra être utile d'introduire un réel  > 0 et de choisir une norme 
subordonnée N sur
Mn (C) telle qu'on ait l'inégalité N(M) 6 (M) +  pour la matrice M considérée.

MATHÉMATIQUES II

1 0
, et
0 c

· · · FIN · · ·

Page 4/4

III.B - Un exemple : n = 2, c > 0 est différent de 1, A est la matrice
 
x0
n'a aucune composante nulle. On construit la
b = 0. On suppose que u0 =
y0
 
xk
suite (uk ) par la méthode décrite dans cette partie. On note uk =
yk
III.B.1) Expliciter les composantes de uk+1 en fonction de celles de uk et de 
c. En
déduire que pour tout k  N, les deux composantes de uk sont différentes de 0.
III.B.2) Montrer que le produit des coefficients directeurs de uk+1 et uk est 
une
constante indépendante
  de k, que l'on déterminera. On rappelle que le coefficient
y
xk
est tk = k ·
directeur de uk =
yk
xk
III.B.3) Montrer que uk+2 et uk sont colinéaires, et calculer le coefficient de 
colinéarité. Illustrer géométriquement le comportement de la suite (uk ) pour c 
> 1.

MATHÉMATIQUES II

Filière PC

Extrait du corrigé obtenu par reconnaissance optique des caractères



Centrale Maths 2 PC 2009 -- Corrigé
Ce corrigé est proposé par Denis Conduché (ENS Ulm) ; il a été relu par Tristan
Poullaouec (ENS Cachan) et Benoît Chevalier (ENS Ulm).

L'épreuve se compose de trois parties. L'objectif est de minimiser une 
application
appelée fonctionnelle, notée J, par des méthodes de descente de gradient.
· Dans la première partie, on montre quelques résultats généraux sur la 
fonctionnelle J : Rn  R. On calcule entre autres son développement de Taylor à
l'ordre 2 et des encadrements. On traite aussi un exemple qui permet d'acquérir
un peu d'intuition géométrique pour la suite du problème.
· La deuxième partie commence par des rappels sur les normes subordonnées afin
d'étudier la convergence de la série géométrique dans l'algèbre des matrices.
Dans un deuxième temps, le sujet développe une méthode du gradient dite
« à pas constant ». Elle consiste, à partir d'un point u0 , J(u0 ) , en une 
descente
le long de l'hypersurface z = J(u), en zigzags, vers le minimum. À chaque étape,
on emprunte la ligne de plus grande pente sur une distance constante  appelée
le pas. La direction de cette ligne est donnée par l'opposé du gradient de J.
· La dernière partie s'intéresse à la méthode du gradient dite « à pas optimal 
» :
à chaque étape, le pas rk est optimisé pour atteindre un minimum de J sur
l'axe donné par le gradient. Cette méthode nécessite d'imposer une condition
supplémentaire sur la fonctionnelle J. En pratique, le défaut par rapport à la
méthode précédente est le coût ­ en complexité ­ de l'optimisation du pas.
Cette partie se termine par l'étude du cas de la dimension 2.
Le sujet utilise abondamment les propriétés des matrices symétriques. Les 
questions plus difficiles que la moyenne sont réparties dans tout l'énoncé. Il 
s'agit d'une
bonne occasion de travailler les fonctions de plusieurs variables dans un 
contexte appliqué, ce qui permet de s'aider de l'intuition et de bien 
comprendre à quoi servent
les outils conceptuels.
Signalons enfin que la méthode du gradient est un outil important en 
optimisation,
utilisé dans de nombreuses applications ; c'est par exemple ce qui sert à 
synchroniser
les horloges des antennes-relais en téléphonie mobile.

Les conseils du jury
Ce sujet porte essentiellement sur l'algèbre linéaire classique. Le rapport
du jury souligne que « certaines méthodes étaient assez voisines de celles
utilisées dans le cours » et qu'elles « paraissent familières même si elles ne 
sont
pas toujours entièrement maîtrisées en dehors de leurs applications les plus
classiques. » Ces remarques justifient à nouveau l'importance d'une parfaite
maîtrise du cours pour la préparation des concours. C'est un préalable à
l'acquisition d'« une bonne culture en algèbre linéaire », observée chez les
meilleurs candidats, ce qui leur permet de mieux « comprendre les finalités
et les méthodes de l'énoncé ».
Le jury s'étonne que les questions plus calculatoires « n'ont pas contribué
à repêcher les candidats » à cause de nombreuses erreurs de calcul. Il indique
que « si les calculateurs électroniques rendent des services inestimables aux
mathématiciens, il est clair que des calculs aussi brefs que ceux demandés
par l'énoncé doivent être réussis à la main. »

Indications
I. La fonctionnelle J
I.B.a
I.B.b
I.B.c
I.B.d
I.C.1
I.C.2.a
I.C.2.b
I.C.3.a
I.C.3.b
I.C.4
I.C.5

Une fonction polynomiale est C  .
Calculer les dérivées partielles.
La matrice A est inversible.
Étudier le signe des valeurs propres de A.
La matrice A est symétrique.
La matrice A est positive.
Utiliser le résultat obtenu à la question I.C.2.a, et étudier t 7 J(v0 + th),
trinôme en t.
Suivre la même méthode que pour la réponse à la question I.B.c.
J(v - rd) est un polynôme de degré 2 en r.
Une matrice symétrique réelle est diagonalisable dans une base orthonormée.
Utiliser le résultat de la question I.C.2.b et le fait que (Im A) = Ker A.

II. Méthode du gradient à pas constant
II.A.2.a Remarquer que (Mx) 6 N(M)(x).
II.A.2.b Utiliser l'inégalité précédente, avec x un vecteur propre pour la 
valeur propre
de module (M).
II.A.3.b Un choix judicieux de  transforme P-1
 MP en une matrice presque diagonale. Conclure en utilisant le résultat de la 
question II.A.1.
II.A.4.a Une matrice à coefficients complexes est trigonalisable.
II.A.4.b Noter que M est fixée. Utiliser les deux questions précédentes.
II.A.5 Toutes les normes sont équivalentes en dimension finie, et la série 
géométrique en M converge vers I - M.
II.B.2 La matrice A est symétrique.
II.B.3 Utiliser le résultat de la question précédente.
II.B.4.a Faire une récurrence : on ne rajoute que des éléments de Im S-1 A.
II.B.4.c Démontrer l'indication en décomposant X par ses parties réelle et 
imagit
naire. Puis, remarquer de même que X AX > 0 pour tout vecteur X 6= 0,
en particulier pour X vecteur propre complexe de S-1 A.
II.B.4.d Conséquence immédiate du résultat de la question II.B.3.
II.B.4.e Utiliser le résultat de la question II.B.4.c.
II.B.4.f Appliquer l'équivalence démontrée dans la question II.A.5.

III. Méthode du gradient à pas optimal
III.A.1 Exprimer dk+1 en fonction de dk et A.
III.A.2 Utiliser la formule donnée à la question I.C.2.a, puis la minoration 
trouvée
en I.C.4.
III.A.3 Une suite décroissante minorée converge.
III.A.4 Utiliser le théorème de Pythagore et la majoration trouvée en I.C.4.
III.A.5 Se souvenir que J(v0 ) = 0, et utiliser l'inégalité de Cauchy-Schwarz.

I. La fonctionnelle J
I.A.1 Soit M  Mn (R) une matrice symétrique positive. Soit   (M) une valeur
propre ­ a priori complexe ­ de M, et x  Cn un vecteur propre associé. Dans Cn
muni du produit hermitien canonique, il vient
kxk2 = hx | xi = hMx | xi = hx | Mxi = kxk2

Ainsi  =  et les valeurs propres de M sont réelles. Soit maintenant un vecteur
propre x  Rn réel associé à la valeur propre réelle . La matrice M est positive 
donc
hMx | xi = kxk2 > 0
et
>0
Réciproquement, supposons que M est une matrice symétrique de Mn (R) telle
que (M)  R+ . M est diagonalisable dans une base orthonormée (e1 , . P
. . , en ), où l'on
note i la valeur propre associée au vecteur propre ei . Pour tout x = xi ei  Rn 
,
n
n
n
P
P
P
hMx | xi = h xi i ei |
xj ej i =
i x2i > 0
i=1

j=1

i=1

alors la matrice M est positive. En conclusion,

Une matrice M symétrique réelle est positive si et seulement si (M)  R+ .

Le cas d'une matrice définie positive est identique, les inégalités larges 
devenant
strictes. Soit M symétrique réelle définie positive. Elle est en particulier 
positive,
donc, d'après l'encadré ci-dessus, (M)  R+ . De plus, elle est définie, si bien 
que
son noyau est réduit à {0} : 0 n'est pas valeur propre. Ainsi (M)  R+ .
Réciproquement, soit M symétriqueP
réelle telle que (M)  R+ . Avec les mêmes
notations que ci-dessus, pour tout x = xi ei  Rn non nul,
n
n
n
P
P
P
xj ej i =
i x2i > 0
hMx | xi = h xi i ei |
i=1

j=1

i=1

alors la matrice M est définie positive. En conclusion,

M symétrique réelle est définie positive si et seulement si (M)  R+ .
I.B.a La fonction F : (x1 , x2 ) 7 (13x21 - 8x1 x2 + 7x22 )/2 - 75x1 + 75x2 est 
polynomiale (de degré 2) en x1 et x2 , elle est donc de classe C  sur R2 . En 
particulier,
F est de classe C 1 sur R2 .
Pour montrer que la fonction F est polynomiale, il n'est pas nécessaire de 
calculer son expression dans une base : F est la somme d'une forme quadratique
et d'une forme linéaire. Elle est donc polynomiale, et continue.

F F
I.B.b Le gradient F de l'application F est défini par F = t
,
. Calcux1 x2
lons les dérivées partielles de F en x1 et x2 :
F
F
(x1 , x2 ) = 13x1 - 4x2 - 75
et
(x1 , x2 ) = -4x1 + 7x2 + 75
x1
x2

x1
13x1 - 4x2
De plus,
A
=
x2
-4x1 + 7x2
d'où

v  R2

F(v) = Av - b

Une méthode alternative consiste à utiliser la définition du gradient par une
formule intrinsèque, et non à l'aide de coordonnées. Le gradient en v  R2
de la fonction F est le vecteur F(v) qui vérifie, pour tout h  R2 , l'égalité
F(v + h) = F(v) + hF(v) | hi + o(khk)

1
hA(v + h) | v + hi - hb | v + hi
2
1
1
1
= F(v) + hAv | hi + hAh | vi + hAh | hi - hb | hi
2
2
2
1
(A symétrique)
F(v + h) = F(v) + hAv - b | hi + hAh | hi
2

Or F(v + h) =

et de plus
Ainsi,

|hAh | hi| 6 |||A|||khk2
v  R2

F(v) = Av - b

I.B.c Le vecteur v  R2 est un point critique de F si et seulement si F(v) = 0.
Or det A = 75 6= 0 ce qui prouve que A est inversible. La solution de l'équation
Av - b = 0 est alors v = A-1 b. En conclusion,
F admet un unique point critique sur R2 , v = A-1 b.
I.B.d La surface  est un paraboloïde, puisque F est de degré 2. Sa nature 
précise
dépend du signe des valeurs propres de A. Calculons le polynôme caractéristique 
de
la matrice A :
A () = 2 - (Tr A) + det A = 2 - 20 + 75 = ( - 5)( - 15)
Ainsi les valeurs propres de A sont toutes les deux strictement positives. Dans 
une
2
base adaptée, la forme réduite de la forme quadratique v 7 hAv | vi est donc x2
1 +x2 ,
si bien que, dans cette nouvelle base,

2 
2
b1
b2
b2 + b2
2

2

F(v) = x2
+
x
-
b
x
-
b
x
=
x
-
+
x
-
- 1
1
2
1
2
1 1
2 2
2
2
4
La surface  est un paraboloïde elliptique minoré.

Le rapport du jury constate que « la détermination des quadriques pose encore 
quelques difficultés aux candidats et, une fois celle-ci faite, la nomenclature 
est parfois mal connue (beaucoup de cylindres). » Un conseil : retenez
les noms des quadriques avec leur représentation graphique, qu'on retrouve à 
partir d'une équation réduite
Z
d'une quadrique  grâce aux lignes de niveau. Dans
cette question, on aboutit à une équation de la forme
Z = X2 + Y2 : l'ensemble des points de  de cote Z est
vide si Z < 0, est
 réduit à un point si Z = 0 et forme un
cercle de rayon Z si Z > 0. On reconnaît une « cuvette

de forme parabolique » appelée paraboloïde.
Z
O