Mines Maths 2 MP 2003

Thème de l'épreuve Méthodes analytiques pour la résolution d'une équation linéaire A.x=b .
Principaux outils utilisés algèbre bilinéaire, analyse réelle
Mots clefs point selle, optimisation, algorithme du gradient, algorithme d'Uzawa, analyse numérique

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


ÉCOLE NATIONALE DES PONTS ET CHAUS SÉES
ÉCOLES NATIONALES SUPÉROEURES DE L' AÉRÇNAUTÏQUE ET DE L ESPACE,
DE TECHNIQUES AVANCÉES, DES TELECOMMUNICATIONS,
DES MINES DE PARIS, DES MINES DE SAINT--ETIENNE, DES MINES DE NANCY,
DES TELECOMMUNICAIIONS DE BRETAGNE.
ÉCOLE POLYTECHNIQUE (Filière TSI).

CONCOURS D'ADMISSION 2003

ÉPREUVE DE MATHÉMATIQUES
DEUXIEME EPREUVE
Filière MP
(Durée de l'épreuve : 4 heures)
(L'usage d'ordinateur ou de calculette est interdit).

Sujet mis àla disposition des concours :
Cycle International, ENSTIM, ENSAE (Statistique), INT , TPE--BNP.

Les candidats sont priés de mentionner de façon apparente sur la première page 
de la copie:
MATHÉMATIQUES 2-F111ere MP

Cet énoncé comporte 6 pages de texte.

Si, au Cours de l'épreuve, un candidat repère ce qui lui semble être une erreur 
d'énoncé, il le *
signale sur sa copie et poursuit sa composition en expliquant les raisons des 
initiatives qu'il est
amené à prendre.

L'objet du problème est l'étude de méthodes analytiques (méthodes du gradient, 
du
Lagrangien) pour résoudre l'équation linéaire A.x = b oùA est une matrice 
symétrique positive,
inversible, b un vecteur donné de R" et x un vecteur inconnu de R" ou d'un 
sous--espace vectoriel
F de R".

Dans tout le problème, l'entier n est un entier naturel supérieur ou égal à 2 
(n 2 2) ; la base
canonique de R" est notée el, ez, ..., e,, ; le produit scalaire de deux 
vecteurs x et y de R" est noté *
(x | y). La norme d'un vecteur x est notée ||): II.

Les matrices considérées sont réelles ; l'espace vectoriel des matrices carrées 
réelles d'ordre n
est noté M ,,(R). Il est admis que l'application qui, à une matrice M de M 
,,(R), associe la borne
supérieure N (M) des normes des images parM des vecteurs unitaires de R" est 
une norme :

N(M) =5up llM--xll-
nxn=l

Une matrice symétrique A est dite positive lorsque, pour tout vecteur x de R", 
le produit
scalaire des vecteurs A.x et x est positif ou nul (A.): | x) 2 O.

Première partie

Le but de cette partie est la résolution de l'équation A.): = b où A est une 
matrice carrée
d'ordre n symétrique positive et inversible, b un vecteur donné de R" et x un 
vecteur inconnu.

Résultats préliminaires :

Soit M une matrice carrée symétrique d'ordre n.

1. Démontrer qu'il existe un plus grand réel p et un plus petit réel q tels 
que, pour tout vecteur
x de R", le produit scalaire (M.): | x) vérifie l'encadrement suivant :

p ||x||2 S (Mx | x) 5 q lle2.
Préciser ces deux réels p et q en fonction des valeurs propres de la matn'ce M.

2. Montrer que, pour que cette matrice M soit inversible et positive, il faut 
et il suffit que toutes
ses valeurs propres soient strictement positives.

3. Démontrer que la norme N (M) d'une matrice M symétrique est égale àla plus 
grande valeur
absolue des valeurs propres À,-- (1 5 i 5 n) de la matriceM :

N (!'/I) =5"P Mil--

1_<_iSn

Étant donnés la matrice carrée, d'ordre n, symétrique positive A et le vecteur 
b, soit a un réel
strictement positif strictement majoré par 2/2... (0 < a < 2/À,,) où A,, est la 
plus grande valeur
propre de la matrice A ; soit (x" ) keN la suite définie par un premier vecteur 
x° choisi arbitrairement

dans R" et par la relation de récurrence suivante : pour tout entier naturel k,
):"+1 = x" + a (b ----A.x").

Étude de la suite (x" ) keN :
4. Démontrer que la suite (x" ) keN
IR", solution de l'équafimA.x : b .

est une suite convergente de limite le vecteur 2 de l'espace

Soit f la fonction réelle, définie dans IR", par la relation :

f(x) = --â--Ax1+'Byl : b.

21. Soient xl un vecteur du sous--espace vectoriel F et y1 un vecteur de R". 
Démontrer qu'une
condition nécessaire et suffisante pour que le couple (xl , y1 ) soit un point 
selle du Lagrangien L

est que le vecteur xl réalise le minimum de la restriction de la fonction f à F 
et que les vecteurs x1
et y1 vérifient la relation suivante :

Ax1 + tBy1 = b.

La suite logique est la recherche d'un point selle du Lagrangien L.

Algorithme d'Uzawa : soit toujours (x*, y*) un point selle, supposé exister ; 
étant donnés
un vecteur y° arbitraire de R", une suite (pm )...ä de réels, qui seront 
précisés plus loin, soient
(x'" )meN et (y'" )mËN les deux suites de vecteurs définies par les conditions 
suivantes :

. Pour tout entier naturel m, le vecteur x'" est le vecteur qui rend minimum la 
fonction
x +--» L (x, y'" )
. Pour tout entier naturel m, le vecteur y'"+1 est défini par la relation 
suivante :

ym+l =ym +Pm me_

Existence des deux suites (x'" )meN et (y"' )meN :

22. Démontrer que les conditions énoncées permettent de déterminer tous les 
termes de ces
deux suites (x'" )mGN et @" )...N et que les vecteurs de ces suites vérifient, 
pour tout entier naturel
m, les relations suivantes :

A(x'" --x*) + 'B(y"' --y*) = O,
ym+l _y* =ym _y* +])": B(xm _x*)_
où x* et y* sont les deux vecteurs d'un point selle de L.

23. En déduire l'égalité ci--dessous :

"ÿ"... --y* Il2 = Il)!" --y* Il2 --2 Pm (A(x"' --x*) | (x"' --x*)) + (m»)2 
IIB(X'" --x*) "2-

Convergence de la suite numérique de terme général Hy'" -- y* || 2, m & N :
24. Un résultat préliminaire : démontrer l'existence d'une matrice carrée 
d'ordre n symétrique
positive inversible, notée A ", telle que :

(Al/Z)2 =A.

Soit C la matrice définie par la relation suivante
C : A""2.'B.B...»4""2

où la matrice A'"2 est la matrice inverse de la matrice A 1/2.

25. Démontrer que la matrice C est une matrice symétrique positive. Établir 
qu'il existe une
constante v telle que, pour tout vecteur u de R", l'inégalité ci--dessous soit 
vraie :

"Eu"2 5 v (Au | u).

Soient a et B deux réels tels que le segment [a, fl] soit contenu dans 
l'intervalle ouvert
]0, 2/v [, (0 < a < 5 < 2/v). La suite des réels p... est supposée vérifier 
pour tout entier naturel m
l'inégalité suivante :

aSpm_<_fl.

26. Démontrer que la suite de tenue général ||y'" --- y* || 2, m G N est 
monotone décroissante ;
utiliser, pour simplifier, la suite (um) dont le terme général est définie par 
la relation suivante :

me"-N

Convergence de la suite (x'" )meN :

27. En déduire la convergence et la limite de la suite (x")

meN '

FIN DU PROBLÈME

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



Mines Maths 2 MP 2003 -- Corrigé
Ce corrigé est proposé par Antoine Gloria (École Polytechnique) ; il a été relu 
par
Céline Chevalier (ENS Ulm) et Thomas Chomette (ENS Ulm).

Ce sujet propose une introduction aux bases de l'analyse numérique et du calcul 
scientifique enseignés dans les cursus de mathématiques appliquées des écoles
d'ingénieur.
Il fait appel à de bonnes connaissances en algèbre bilinéaire et à une certaine
aisance dans le calcul. Il y a beaucoup de raisonnements par contraposée et 
certaines
questions requièrent des résultats d'analyse sur les fonctions continues.
Plutôt longue et exigeante sur la rédaction, cette épreuve nécessite des calculs
réfléchis, parfois délicats et dont les méthodes sont assez générales.
Dans la première partie, on s'attache à caractériser le minimum d'une fonction
quadratique à plusieurs variables et à rechercher ce minimum à l'aide de 
l'inversion
d'un système matriciel. La méthode du gradient est étudiée à cet effet.
La seconde partie propose d'autres méthodes pour caracteriser le minimum d'une
fonction convexe (méthode de point selle) et pour le déterminer (algorithme 
d'Uzawa).

Indications
Première partie
1-2-3 Diagonaliser la matrice M.
4 Procéder par récurrence sur xk - z en utilisant A.z = b, puis se servir de la
question 3 en faisant apparaître la norme de In - A.
5 Utiliser la symétrie de A.
7 Travailler dans une base où A est diagonale.
9 Raisonner par condition nécessaire et suffisante ainsi que par contraposée.
11 Construire une suite décroissante à l'aide de la question 10.
Seconde partie
12 Utiliser la question 1 et l'inégalité de Cauchy-Schwarz.
14 Découper l'espace en deux parties : l'une où f est « grande » et l'autre où f
atteint ses bornes (un compact).
15 Raisonner par l'absurde en supposant l'existence de deux vecteurs distincts.
16 Raisonner par l'absurde en supposant qu'il existe u  F tel que (g(y) | u) 6= 
0,
prendre v = µu, avec µ bien choisi pour obtenir une contradiction entre 
l'hypothèse et le caractère minimal.
17 x  F donc (A.x - b | x) = 0.
18 Lire la remarque du corrigé précédant la question sur les bornes inférieures 
et
supérieures.

19 Montrer que Sup Infn L(x, y) > L(x , y ) > Infn Sup L(x, y) .
yRn

xR

xR

yRn

20 Faire intervenir y-y1. Pour démontrer la deuxième équivalence, faire 
apparaître
A.x1 + t B.y1 - b dans le membre de gauche et s'inspirer de la question 16.
21 Remarquer que si x  F, L(x, y) = f (x).
22 Utiliser les résultats d'existence et d'unicité du minimum d'une fonction 
quadratique obtenus dans la première partie.
23 Exprimer le carré scalaire de y m+1 - y  .
24 Diagonaliser la matrice A.
25 Démontrer que la matrice A-1/2 est symétrique. Utiliser le vecteur v  Rn
défini par u = A-1/2 .v.
26 Utiliser les questions 23 et 25.
27 Utiliser la question 26 pour démontrer la convergence de la série de terme
général kum k2 .

Première partie
Résultats préliminaires
1 M est une matrice symétrique réelle, elle est donc diagonalisable sur R dans 
une
base orthonormale (e
ej )j=1,...,n , avec une matrice de passage orthogonale O (qui vérifie
t
O = O-1 ). O est la matrice formée des coordonnées des vecteurs (e
ej )j=1,...,n dans
la base canonique.
On a ainsi M = ODO-1 , avec

1 0 · · · 0
 0 2 · · · 0 

D= .
.. . .
. 
 ..
. .. 
.
0

0

· · · n

où (j )j=1,...,n sont les valeurs propres de M comptées avec leur multiplicité.
Pour x  Rn , on note (e
xj )j=1,...,n ses coordonnées dans la base (e
ej )j=1,...,n , soit
x=

n
P

xi ei =

i=1

n
P

i=1

x
ei eei

En utilisant la linéarité de M, la bilinéarité du produit scalaire et le 
caractère
orthonormal de la base (e
ej )j=1,...,n , il vient
P

n
n
P
(M.x | x) =
M.(e
xi eei )|
x
ej e
ej
i=1

=

=
(M.x | x) =

n
P

i,j=1
n
P

i,j=1
n
P

i=1

j=1

(i x
ei eei | x
ej eej )

i x
ei x
ej (e
ei | eej )

i x
ei 2

Notons 1 et n respectivement la plus petite et la plus grande valeur propre de 
M.
On obtient, d'une part,
(M.x | x) =

n
P

i=1

i x
ei 2

n
P

6 n

i=1

(M.x | x) 6 n kxk
et d'autre part,

(M.x | x) =

n
P

i=1

> 1

x
ei 2

2

i x
ei 2

n
P

i=1

x
ei 2

(M.x | x) > 1 kxk2
De plus, (M.x1 | x1 ) = 1 et (M.xn | xn ) = n .

On en déduit l'existence et l'unicité des réels p et q :
p = 1

et

q = n

2 Montrons qu'une condition nécessaire et suffisante pour que M soit positive 
au sens
des matrices symétriques est que ses valeurs propres soient toutes positives.
Rappelons que 1 est la plus petite valeur propre de M. Si 1 > 0, d'après la
question précédente,
x  Rn

(M.x | x) > 0

Réciproquement, un raisonnement par contraposée montre que, si 1 < 0,
alors (M.e
e1 | ee1 ) = 1 < 0 où ee1 est un vecteur propre (de la base orthonormale)
associé à 1 . M n'est par conséquent pas positive.
Pour que M soit inversible, il faut et suffit que son déterminant soit non nul,
c'est-à-dire que ses valeurs propres soient toutes non nulles.
M est symétrique, positive et inversible si et seulement si
toutes ses valeurs propres sont strictement positives.
3 Soit x  Rn tel que kxk = 1 ; notons x =

n
P

i=1
2

kM.xk

=
=

n
P

i=1
n
P

i=1

n
P

i x
ei eei .

i 2 x
ei 2

6 ( Sup (i 2 ))
i=1,...,n

j=1

n
P

i=1

kM.xk2 6 Sup (i 2 )
i=1,...,n

donc

x
ei eei , avec

n
P

i=1

j x
ej eej

!

x
ei 2 = 1. On a

x
ei 2

Sup kM.xk 6 Sup |i |
kxk=1

i=1,...,n

Par un calcul analogue, en prenant x = eei le vecteur propre associé à la valeur
propre de plus grande valeur absolue, on obtient l'inégalité dans l'autre sens, 
de sorte
que finalement,
N(M) =

Sup |i |

i=1,...,n

Ces résultats préliminaires, qui serviront à plusieurs reprises, sont des 
applications directes du cours d'algèbre linéaire et bilinéaire de la filière 
MP.
Le même genre d'application directe du cours est demandé aux questions 24
et 25. Il est toujours profitable de lire l'énoncé en entier pour ne pas oublier
de traiter les questions faciles placées en fin d'épreuve.