Centrale Maths 2 MP 2008

Thème de l'épreuve Factorisation LU
Principaux outils utilisés raisonnement par récurrence, algèbre linéaire, calcul matriciel
Mots clefs factorisation LU, calcul matriciel

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 27 fevrier 2008 9h57

MATHÉMATIQUES II

k=1

k=1

(1)

MP

Partie I - Methode de Gauss et factorisation

Filière

avec P = (pij )16i,j6n ).

j=1

I.B - Matrices d'elimination de Gauss
La matrice A de Mn est de nouveau quelconque avec det A 6= 0.
Etant donne M = [mij ]1i,jn  Mn , on note pour tout entier q de [[1, n]], q (M )
la sous-matrice de M definie par q (M )=[mij ]16i,j6q element de Mq , et on note
Dq (M ) = det q (M ) (D1 (M ),...,Dn (M ) sont appeles les mineurs principaux de
M ).
Par ailleurs, on note Li (M ) le iieme vecteur ligne de la matrice M et defini 
par
Li (M ) = (mi1 , mi2 , ...., min ). On note aussi Cj (M ) le j ieme vecteur 
colonne de M
defini par Cj (M ) = t (m1j , m2j , ..., mnj ). On dira aussi dans la suite les 
lignes Li de
M et les colonnes Cj de M .
I.B.1) Soient M une matrice de Mn et P = M A. Exprimer, pour tout entier q de
[[1, n]], Lq (P ) en fonction des lignes Li (A) de la matrice A.
n
X
(On pourra, si l'on veut, utiliser la decomposition de Lq (P ) sous la forme
pqj Eqj

I.A - Resolution d'un systeme triangulaire
On suppose dans cette question que A  T S n .
I.A.1) Calculer un puis pour k  [[1, n-1]] exprimer un-k en fonction de un , 
un-1 ,
..., un-k+1 . Ecrire l'algorithme de resolution du systeme (1).
I.A.2) Exprimer en fonction de n le nombre d'additions, de multiplications et de
divisions necessaires a la resolution du systeme (1).

(1) admette une unique solution u = t (u1 , ..., un )  Rn .

Le but de cette partie est de representer matriciellement la methode de Gauss 
pour
la resolution du systeme (1).
On note T S n  Mn l'ensemble des matrices M = [mij ]1i,jn triangulaires 
superieures (c'est-a-dire mij = 0 pour i > j) et T I n  Mn l'ensemble des 
matrice
triangulaires inferieures a diagonale unite (c'est-a-dire mii = 1 et mij = 0 
pour
i < j). Dans toute cette partie, on suppose que det(A) 6= 0, de sorte que le 
systeme

Page 1/4

ou w = t (w1 , ...., wn )  Rn est donne, et u = t (u1 , ..., un ) est 
l'inconnue. L'objet du
probleme est l'etude de quelques methodes de resolution de ce systeme lineaire. 
On
n
n
X
n(n + 1) X 2 n(n + 1)(2n + 1)
rappelle que
,
.
k=
k =
2
6

Au = w,

Soit A = [aij ]1i,jn  Mn . On considere le systeme lineaire

· Etant donne t (1 , 2 , ...., n )  Rn , on note D = diag(1 , 2 , ...., n )  Mn 
la
matrice diagonale telle que, pour tout i de [[1, n]], dii = i .
On note In = diag(1, 1, ...., 1) la matrice de l'identite.

[[p, q]] = {k  N, p 6 k 6 q}.

· Pour tout couple d'entiers p, q tels que p 6 q, on note :

k=1

ou jk = 1 si j = k et 0 sinon.
· Pour tout couple (p, q) d'entiers strictement positifs, on note Mp,q l'espace
vectoriel des matrices a p lignes et q colonnes, a coefficients reels.
· Pour toute matrice M de Mp,q , on note t M sa matrice transposee.
· L'espace Rn est identifie a l'espace Mn,1 . On note B = (e1 , ..., en ) la 
base canonique de Rn . Ainsi, pour tout entier k compris entre 1 et n, ek = t 
(0, ..., 0, 1, 0..., 0)
ou 1 est en k ieme position.
On munit Rn de sa structure euclidienne canonique.
Pour tout couple (u, v) de vecteurs de Rn , u = t (u1 , ..., un ) et v = t (v1 
, ..., vn ),
n
X
uk vk leur produit scalaire.
on note hu, vi = t u.v =

Notations
· Dans tout le probleme n est un entier superieur a 2, Mn est l'ensemble des
matrices carrees a n lignes, a coefficients reels.
· On note (Eij , 1 6 i 6 n, 1 6 j 6 n) la base canonique de Mn . Ainsi, pour 
tout
couple (i, j) d'entiers compris entre 1 et n, tous les coefficients de la 
matrice Eij
sont nuls sauf le coefficient d'indices (i, j) qui vaut 1. On rappelle le 
resultat
suivant :
i, j, k, l  {1, ..., n}, Eij Ekl = jk Eil

Épreuve :

Concours Centrale - Supélec 2008

- version du 27 fevrier 2008 9h57

MATHÉMATIQUES II

k=1

k=1

(1)

MP

Partie I - Methode de Gauss et factorisation

Filière

avec P = (pij )16i,j6n ).

j=1

I.B - Matrices d'elimination de Gauss
La matrice A de Mn est de nouveau quelconque avec det A 6= 0.
Etant donne M = [mij ]1i,jn  Mn , on note pour tout entier q de [[1, n]], q (M )
la sous-matrice de M definie par q (M )=[mij ]16i,j6q element de Mq , et on note
Dq (M ) = det q (M ) (D1 (M ),...,Dn (M ) sont appeles les mineurs principaux de
M ).
Par ailleurs, on note Li (M ) le iieme vecteur ligne de la matrice M et defini 
par
Li (M ) = (mi1 , mi2 , ...., min ). On note aussi Cj (M ) le j ieme vecteur 
colonne de M
defini par Cj (M ) = t (m1j , m2j , ..., mnj ). On dira aussi dans la suite les 
lignes Li de
M et les colonnes Cj de M .
I.B.1) Soient M une matrice de Mn et P = M A. Exprimer, pour tout entier q de
[[1, n]], Lq (P ) en fonction des lignes Li (A) de la matrice A.
n
X
(On pourra, si l'on veut, utiliser la decomposition de Lq (P ) sous la forme
pqj Eqj

I.A - Resolution d'un systeme triangulaire
On suppose dans cette question que A  T S n .
I.A.1) Calculer un puis pour k  [[1, n-1]] exprimer un-k en fonction de un , 
un-1 ,
..., un-k+1 . Ecrire l'algorithme de resolution du systeme (1).
I.A.2) Exprimer en fonction de n le nombre d'additions, de multiplications et de
divisions necessaires a la resolution du systeme (1).

(1) admette une unique solution u = t (u1 , ..., un )  Rn .

Le but de cette partie est de representer matriciellement la methode de Gauss 
pour
la resolution du systeme (1).
On note T S n  Mn l'ensemble des matrices M = [mij ]1i,jn triangulaires 
superieures (c'est-a-dire mij = 0 pour i > j) et T I n  Mn l'ensemble des 
matrice
triangulaires inferieures a diagonale unite (c'est-a-dire mii = 1 et mij = 0 
pour
i < j). Dans toute cette partie, on suppose que det(A) 6= 0, de sorte que le 
systeme

Page 1/4

ou w = t (w1 , ...., wn )  Rn est donne, et u = t (u1 , ..., un ) est 
l'inconnue. L'objet du
probleme est l'etude de quelques methodes de resolution de ce systeme lineaire. 
On
n
n
X
n(n + 1) X 2 n(n + 1)(2n + 1)
rappelle que
,
.
k=
k =
2
6

Au = w,

Soit A = [aij ]1i,jn  Mn . On considere le systeme lineaire

· Etant donne t (1 , 2 , ...., n )  Rn , on note D = diag(1 , 2 , ...., n )  Mn 
la
matrice diagonale telle que, pour tout i de [[1, n]], dii = i .
On note In = diag(1, 1, ...., 1) la matrice de l'identite.

[[p, q]] = {k  N, p 6 k 6 q}.

· Pour tout couple d'entiers p, q tels que p 6 q, on note :

k=1

ou jk = 1 si j = k et 0 sinon.
· Pour tout couple (p, q) d'entiers strictement positifs, on note Mp,q l'espace
vectoriel des matrices a p lignes et q colonnes, a coefficients reels.
· Pour toute matrice M de Mp,q , on note t M sa matrice transposee.
· L'espace Rn est identifie a l'espace Mn,1 . On note B = (e1 , ..., en ) la 
base canonique de Rn . Ainsi, pour tout entier k compris entre 1 et n, ek = t 
(0, ..., 0, 1, 0..., 0)
ou 1 est en k ieme position.
On munit Rn de sa structure euclidienne canonique.
Pour tout couple (u, v) de vecteurs de Rn , u = t (u1 , ..., un ) et v = t (v1 
, ..., vn ),
n
X
uk vk leur produit scalaire.
on note hu, vi = t u.v =

Notations
· Dans tout le probleme n est un entier superieur a 2, Mn est l'ensemble des
matrices carrees a n lignes, a coefficients reels.
· On note (Eij , 1 6 i 6 n, 1 6 j 6 n) la base canonique de Mn . Ainsi, pour 
tout
couple (i, j) d'entiers compris entre 1 et n, tous les coefficients de la 
matrice Eij
sont nuls sauf le coefficient d'indices (i, j) qui vaut 1. On rappelle le 
resultat
suivant :
i, j, k, l  {1, ..., n}, Eij Ekl = jk Eil

Épreuve :

Concours Centrale - Supélec 2008

- version du 27 fevrier 2008 9h57

MATHÉMATIQUES II

k=1

k=1

(1)

MP

Partie I - Methode de Gauss et factorisation

Filière

avec P = (pij )16i,j6n ).

j=1

I.B - Matrices d'elimination de Gauss
La matrice A de Mn est de nouveau quelconque avec det A 6= 0.
Etant donne M = [mij ]1i,jn  Mn , on note pour tout entier q de [[1, n]], q (M )
la sous-matrice de M definie par q (M )=[mij ]16i,j6q element de Mq , et on note
Dq (M ) = det q (M ) (D1 (M ),...,Dn (M ) sont appeles les mineurs principaux de
M ).
Par ailleurs, on note Li (M ) le iieme vecteur ligne de la matrice M et defini 
par
Li (M ) = (mi1 , mi2 , ...., min ). On note aussi Cj (M ) le j ieme vecteur 
colonne de M
defini par Cj (M ) = t (m1j , m2j , ..., mnj ). On dira aussi dans la suite les 
lignes Li de
M et les colonnes Cj de M .
I.B.1) Soient M une matrice de Mn et P = M A. Exprimer, pour tout entier q de
[[1, n]], Lq (P ) en fonction des lignes Li (A) de la matrice A.
n
X
(On pourra, si l'on veut, utiliser la decomposition de Lq (P ) sous la forme
pqj Eqj

I.A - Resolution d'un systeme triangulaire
On suppose dans cette question que A  T S n .
I.A.1) Calculer un puis pour k  [[1, n-1]] exprimer un-k en fonction de un , 
un-1 ,
..., un-k+1 . Ecrire l'algorithme de resolution du systeme (1).
I.A.2) Exprimer en fonction de n le nombre d'additions, de multiplications et de
divisions necessaires a la resolution du systeme (1).

(1) admette une unique solution u = t (u1 , ..., un )  Rn .

Le but de cette partie est de representer matriciellement la methode de Gauss 
pour
la resolution du systeme (1).
On note T S n  Mn l'ensemble des matrices M = [mij ]1i,jn triangulaires 
superieures (c'est-a-dire mij = 0 pour i > j) et T I n  Mn l'ensemble des 
matrice
triangulaires inferieures a diagonale unite (c'est-a-dire mii = 1 et mij = 0 
pour
i < j). Dans toute cette partie, on suppose que det(A) 6= 0, de sorte que le 
systeme

Page 1/4

ou w = t (w1 , ...., wn )  Rn est donne, et u = t (u1 , ..., un ) est 
l'inconnue. L'objet du
probleme est l'etude de quelques methodes de resolution de ce systeme lineaire. 
On
n
n
X
n(n + 1) X 2 n(n + 1)(2n + 1)
rappelle que
,
.
k=
k =
2
6

Au = w,

Soit A = [aij ]1i,jn  Mn . On considere le systeme lineaire

· Etant donne t (1 , 2 , ...., n )  Rn , on note D = diag(1 , 2 , ...., n )  Mn 
la
matrice diagonale telle que, pour tout i de [[1, n]], dii = i .
On note In = diag(1, 1, ...., 1) la matrice de l'identite.

[[p, q]] = {k  N, p 6 k 6 q}.

· Pour tout couple d'entiers p, q tels que p 6 q, on note :

k=1

ou jk = 1 si j = k et 0 sinon.
· Pour tout couple (p, q) d'entiers strictement positifs, on note Mp,q l'espace
vectoriel des matrices a p lignes et q colonnes, a coefficients reels.
· Pour toute matrice M de Mp,q , on note t M sa matrice transposee.
· L'espace Rn est identifie a l'espace Mn,1 . On note B = (e1 , ..., en ) la 
base canonique de Rn . Ainsi, pour tout entier k compris entre 1 et n, ek = t 
(0, ..., 0, 1, 0..., 0)
ou 1 est en k ieme position.
On munit Rn de sa structure euclidienne canonique.
Pour tout couple (u, v) de vecteurs de Rn , u = t (u1 , ..., un ) et v = t (v1 
, ..., vn ),
n
X
uk vk leur produit scalaire.
on note hu, vi = t u.v =

Notations
· Dans tout le probleme n est un entier superieur a 2, Mn est l'ensemble des
matrices carrees a n lignes, a coefficients reels.
· On note (Eij , 1 6 i 6 n, 1 6 j 6 n) la base canonique de Mn . Ainsi, pour 
tout
couple (i, j) d'entiers compris entre 1 et n, tous les coefficients de la 
matrice Eij
sont nuls sauf le coefficient d'indices (i, j) qui vaut 1. On rappelle le 
resultat
suivant :
i, j, k, l  {1, ..., n}, Eij Ekl = jk Eil

Épreuve :

Concours Centrale - Supélec 2008

Li = Li
(2)

k=1

F (k, k ).

(3)

Cjq = ej

et  j  [[1, q]],

Cjq = bj .

m  [[1, n]],

Dm (Ak ) 6= 0. (4)

(5)

Dans cette partie, on applique a certains exemples la factorisation vue en 
Partie I.
Par commodite d'ecriture, lorsque l'on represente une matrice, les espaces 
laisses
vides sont remplis de 0 qui ne sont pas systematiquement ecrits.

Partie II - Applications et cas particuliers

b) Exprimer les coefficients lij de L pour i > j et les coefficients uij de U 
pour i 6 j
en fonction des coefficients akij des matrices Ak (Utiliser (I.B.2a) et 
(I.C.2a)).
I.C.4) Montrer que les matrices L et U de la factorisation (5) sont uniques.
I.C.5) Ecrire dans le langage de son choix un programme realisant la 
factorisation
A = LU qui n'utilise qu'un seul tableau carre encore nomme A pour contenir 
toutes
les iterations Ak . On prendra soin de commenter les principales lignes du 
programme.
Comment aura-t-on en final les facteurs L et U a partir du tableau A ?
I.C.6) Soit Sn le nombre de multiplications necessaires a la factorisation A = 
LU .
Calculer Sn (Indication : utiliser la question I.C.2.c. )

A = LU.

Exprimer le vecteur k a l'aide des coefficients de Ak .
b) Montrer que les lignes 1 a k de Ak et Ak+1 sont identiques.
c) Pour k  [[1, n - 1]], soit Nk le nombre de multiplications necessaires pour 
passer
de Ak a Ak+1 . Calculer le nombre Nk .
I.C.3)
a) Deduire des questions precedentes qu'il existe une matrice L de T I n et une
matrice U de T S n telles que l'on ait

j  [[1, k - 1]], i  [[j + 1, n]], akij = 0 et

et telles que :

I.C.2) On pose F1 = F (1, -1 ).
a) Montrer par recurrence sur k l'existence des suites de matrices (Fk-1 )26k6n 
, (Ak )26k6n
avec
Ak = [akij ]16i,j6n = Fk-1 Ak-1
Fk-1 = F (k - 1, -k-1 )

Filière MP

II.A - Application a la resolution de systemes lineaires
II.A.1) On veut resoudre le systeme (1) en utilisant la factorisation (5). On 
fait
I.C.1) Montrer que a111 6= 0. Determiner 1 = t (21 , ...., n1 )  Rn-1 pour que
toujours l'hypothese que pour tout entier k de [[1, n]], Dk (A) 6= 0.
la premiere colonne de A2 = F (1, -1 )A1 soit proportionnelle a e1 . Que vaut la
Sans compter les operations necessaires a la factorisation, montrer qu'il 
suffit de
premiere ligne de A2 ?
n(n - 1) multiplications pour resoudre le systeme (preciser la methode 
utilisee).
Page 2/4

I.C - Factorisation de A
Dans cette question, on suppose que pour chaque k  [[1, n]], k (A) est 
inversible.
On note A1 = A = [a1ij ]16i,j6n la matrice initiale.

En deduire que Pq appartient a T I n et que Pn-1 = [b1 , ..., bn-1 , en ].

 j  [[q + 1, n]],

Montrer par recurrence sur q que :

On note Cjq les vecteurs colonnes de la matrice Pq et pour tout entier k de 
[[1, q]],
bk = t (0, ..., 0, 1, k+1,k , ..., n,k )  Rn .

Pq = F (1, 1 ).F (2, 2 )...F (q, q ) =

q
Y

b) Soit q un entier de [[1, n]] et pour tout entier k de [[1, q]], k = t (k+1,k 
, ..., n,k )
un vecteur de Rn-k . On considere la matrice produit

I.B.3)
a) Etant donnee une matrice M = [mij ]1i,jn de Mn , exprimer les vecteurs 
colonnes Cj du produit matriciel M F (k, ) en fonction des colonnes Cj de M .

c) Determiner les coefficients ij de F (k, ) pour tout couple (i, j) d'entiers 
de
[[1, n]] × [[1, n]]. Montrer que F (k, )  T I n .

q  [[1, n]],

Li = Li + i Lk .

Dq (P ) = Dq (A).

et i  [[k + 1, n]],

a) Montrer que F (k, )-1 = F (k, -).
b) Montrer que si P = F (k, )A on a :

i  [[1, k]],

I.B.2) Pour un entier k de [[1, n - 1]] et un vecteur  = t (k+1 , ..., n )  
Rn-k , on
note F (k, ) la matrice de Mn qui realise par le produit a gauche P = F (k, )A 
les
combinaisons lineaires de lignes suivantes, en notant pour simplifier Li = Li 
(A) et
Li = Li (P ) :

MATHÉMATIQUES II

Li = Li
(2)

k=1

F (k, k ).

(3)

Cjq = ej

et  j  [[1, q]],

Cjq = bj .

m  [[1, n]],

Dm (Ak ) 6= 0. (4)

(5)

Dans cette partie, on applique a certains exemples la factorisation vue en 
Partie I.
Par commodite d'ecriture, lorsque l'on represente une matrice, les espaces 
laisses
vides sont remplis de 0 qui ne sont pas systematiquement ecrits.

Partie II - Applications et cas particuliers

b) Exprimer les coefficients lij de L pour i > j et les coefficients uij de U 
pour i 6 j
en fonction des coefficients akij des matrices Ak (Utiliser (I.B.2a) et 
(I.C.2a)).
I.C.4) Montrer que les matrices L et U de la factorisation (5) sont uniques.
I.C.5) Ecrire dans le langage de son choix un programme realisant la 
factorisation
A = LU qui n'utilise qu'un seul tableau carre encore nomme A pour contenir 
toutes
les iterations Ak . On prendra soin de commenter les principales lignes du 
programme.
Comment aura-t-on en final les facteurs L et U a partir du tableau A ?
I.C.6) Soit Sn le nombre de multiplications necessaires a la factorisation A = 
LU .
Calculer Sn (Indication : utiliser la question I.C.2.c. )

A = LU.

Exprimer le vecteur k a l'aide des coefficients de Ak .
b) Montrer que les lignes 1 a k de Ak et Ak+1 sont identiques.
c) Pour k  [[1, n - 1]], soit Nk le nombre de multiplications necessaires pour 
passer
de Ak a Ak+1 . Calculer le nombre Nk .
I.C.3)
a) Deduire des questions precedentes qu'il existe une matrice L de T I n et une
matrice U de T S n telles que l'on ait

j  [[1, k - 1]], i  [[j + 1, n]], akij = 0 et

et telles que :

I.C.2) On pose F1 = F (1, -1 ).
a) Montrer par recurrence sur k l'existence des suites de matrices (Fk-1 )26k6n 
, (Ak )26k6n
avec
Ak = [akij ]16i,j6n = Fk-1 Ak-1
Fk-1 = F (k - 1, -k-1 )

Filière MP

II.A - Application a la resolution de systemes lineaires
II.A.1) On veut resoudre le systeme (1) en utilisant la factorisation (5). On 
fait
I.C.1) Montrer que a111 6= 0. Determiner 1 = t (21 , ...., n1 )  Rn-1 pour que
toujours l'hypothese que pour tout entier k de [[1, n]], Dk (A) 6= 0.
la premiere colonne de A2 = F (1, -1 )A1 soit proportionnelle a e1 . Que vaut la
Sans compter les operations necessaires a la factorisation, montrer qu'il 
suffit de
premiere ligne de A2 ?
n(n - 1) multiplications pour resoudre le systeme (preciser la methode 
utilisee).
Page 2/4

I.C - Factorisation de A
Dans cette question, on suppose que pour chaque k  [[1, n]], k (A) est 
inversible.
On note A1 = A = [a1ij ]16i,j6n la matrice initiale.

En deduire que Pq appartient a T I n et que Pn-1 = [b1 , ..., bn-1 , en ].

 j  [[q + 1, n]],

Montrer par recurrence sur q que :

On note Cjq les vecteurs colonnes de la matrice Pq et pour tout entier k de 
[[1, q]],
bk = t (0, ..., 0, 1, k+1,k , ..., n,k )  Rn .

Pq = F (1, 1 ).F (2, 2 )...F (q, q ) =

q
Y

b) Soit q un entier de [[1, n]] et pour tout entier k de [[1, q]], k = t (k+1,k 
, ..., n,k )
un vecteur de Rn-k . On considere la matrice produit

I.B.3)
a) Etant donnee une matrice M = [mij ]1i,jn de Mn , exprimer les vecteurs 
colonnes Cj du produit matriciel M F (k, ) en fonction des colonnes Cj de M .

c) Determiner les coefficients ij de F (k, ) pour tout couple (i, j) d'entiers 
de
[[1, n]] × [[1, n]]. Montrer que F (k, )  T I n .

q  [[1, n]],

Li = Li + i Lk .

Dq (P ) = Dq (A).

et i  [[k + 1, n]],

a) Montrer que F (k, )-1 = F (k, -).
b) Montrer que si P = F (k, )A on a :

i  [[1, k]],

I.B.2) Pour un entier k de [[1, n - 1]] et un vecteur  = t (k+1 , ..., n )  
Rn-k , on
note F (k, ) la matrice de Mn qui realise par le produit a gauche P = F (k, )A 
les
combinaisons lineaires de lignes suivantes, en notant pour simplifier Li = Li 
(A) et
Li = Li (P ) :

MATHÉMATIQUES II

II.B.3)

2
1

c1

3
2

c2

·

·

i-2
,
i-1

·

·
·

·
cn-1
n
n-1

.

Filière MP

i=2

n
X

(vi - vi-1 )2 .

(6)

II.C.4)

On pose A-1
n = [bij ]1j,kn . Calculer bij pour (i, j)  [[1, n]] × [[1, n]].

II.C.3) On veut resoudre le systeme An x = ek pour un entier fixe k  [[1, n]].
a) Resoudre le systeme Ln y = ek .
b) Resoudre le systeme Un x = y.
i(n + 1 - k)
k(n + 1 - i)
(On montrera que : xi =
si i 6 k et xi =
si i > k).
n+1
n+1

II.C.2) On reprend les notations de la question II.B. Expliciter et resoudre la
recurrence sur k . En deduire l'expression des matrices Ln et Un .

b) En deduire que la matrice An est definie positive.
c) Montrer que pour chaque k de [[1, n]] la matrice k (An ) est symetrique et 
definie
positive. En deduire qu'il existe une factorisation An = Ln Un de la forme (5).

< An v, v >= v12 + vn2 +

II.C.1)
a) Montrer que pour chaque v = t (v1 , ...., vn ) de Rn , on a

 i  [[2, n - 1]], ai i+1 = ai i-1 = -1, a1 2 = an n-1 = -1

tous les autres coefficients etant nuls, c'est-a-dire

2 -1
 -1
2 -1

·
·
·

·
· ·
An = 

·
·
·

-1
2 -1
-1
2

 i  [[1, n]], aii = 2,

II.C - Etude d'un exemple
Soit An = [aij ]16i,j6n  Mn , symetrique et tridiagonale definie par

factorisation precedente pour une matrice tridiagonale. Donner le nombre de 
multiplications, de divisions et d'additions necessaires a cette resolution.

Ecrire un algorithme de resolution du systeme Au = w en utilisant la
Page 3/4

1
 0

U =

avec pour tout i de [[2, n]], li,i-1 = ai

II.B.1) On pose k = Dk (A), 0 = 1. On suppose que pour tout k de [[1, n]], k 6= 
0.
Calculer 1 puis, pour k  [[2, n]], exprimer k en fonction de k-1 et de k-2 .
II.B.2) Montrer que les matrices L et U de la factorisation (5) sont de la forme

1

 l21 1

l32 1

· ·
L=

· ·

1
lnn-1 1

II.B - Etude du cas tridiagonal
On suppose la matrice A tridiagonale, c'est-a-dire de la forme

b1 c1
 a2 b2 c2

·
·
·

·
·
·
A=

·
·
·

an-1 bn-1 cn-1
an
bn

II.A.2) En deduire une methode pour inverser la matrice A en utilisant la 
factorisation (5). Exprimer le nombre total de multiplications et divisions 
necessaires a cette
inversion, incluant cette fois-ci le calcul de la factorisation. En donne un 
equivalent
lorsque n  .

MATHÉMATIQUES II

II.B.3)

2
1

c1

3
2

c2

·

·

i-2
,
i-1

·

·
·

·
cn-1
n
n-1

.

Filière MP

i=2

n
X

(vi - vi-1 )2 .

(6)

II.C.4)

On pose A-1
n = [bij ]1j,kn . Calculer bij pour (i, j)  [[1, n]] × [[1, n]].

II.C.3) On veut resoudre le systeme An x = ek pour un entier fixe k  [[1, n]].
a) Resoudre le systeme Ln y = ek .
b) Resoudre le systeme Un x = y.
i(n + 1 - k)
k(n + 1 - i)
(On montrera que : xi =
si i 6 k et xi =
si i > k).
n+1
n+1

II.C.2) On reprend les notations de la question II.B. Expliciter et resoudre la
recurrence sur k . En deduire l'expression des matrices Ln et Un .

b) En deduire que la matrice An est definie positive.
c) Montrer que pour chaque k de [[1, n]] la matrice k (An ) est symetrique et 
definie
positive. En deduire qu'il existe une factorisation An = Ln Un de la forme (5).

< An v, v >= v12 + vn2 +

II.C.1)
a) Montrer que pour chaque v = t (v1 , ...., vn ) de Rn , on a

 i  [[2, n - 1]], ai i+1 = ai i-1 = -1, a1 2 = an n-1 = -1

tous les autres coefficients etant nuls, c'est-a-dire

2 -1
 -1
2 -1

·
·
·

·
· ·
An = 

·
·
·

-1
2 -1
-1
2

 i  [[1, n]], aii = 2,

II.C - Etude d'un exemple
Soit An = [aij ]16i,j6n  Mn , symetrique et tridiagonale definie par

factorisation precedente pour une matrice tridiagonale. Donner le nombre de 
multiplications, de divisions et d'additions necessaires a cette resolution.

Ecrire un algorithme de resolution du systeme Au = w en utilisant la
Page 3/4

1
 0

U =

avec pour tout i de [[2, n]], li,i-1 = ai

II.B.1) On pose k = Dk (A), 0 = 1. On suppose que pour tout k de [[1, n]], k 6= 
0.
Calculer 1 puis, pour k  [[2, n]], exprimer k en fonction de k-1 et de k-2 .
II.B.2) Montrer que les matrices L et U de la factorisation (5) sont de la forme

1

 l21 1

l32 1

· ·
L=

· ·

1
lnn-1 1

II.B - Etude du cas tridiagonal
On suppose la matrice A tridiagonale, c'est-a-dire de la forme

b1 c1
 a2 b2 c2

·
·
·

·
·
·
A=

·
·
·

an-1 bn-1 cn-1
an
bn

II.A.2) En deduire une methode pour inverser la matrice A en utilisant la 
factorisation (5). Exprimer le nombre total de multiplications et divisions 
necessaires a cette
inversion, incluant cette fois-ci le calcul de la factorisation. En donne un 
equivalent
lorsque n  .

MATHÉMATIQUES II

(7)

(8)

lim µn = 0,

n

||Mn || = 2 - µn .

c) Donner un equivalent de µn quand n tend vers l'infini.

 n  N , µn > 0,

Filière MP

· · · FIN · · ·

III.A.4) On considere la decomposition (8). On choisit la donnee initiale U0 de
sorte que ||U0 || = 1. On suppose en outre que ||w|| = 1.
Mn
a) On choisit H =
. Expliciter le vecteur c de maniere a appliquer la methode
2
iterative puis donner l'expression complete de Uk en fonction de U0 , de c et 
des
matrices H m pour m  [[1, k]].
b) Majorer l'erreur k = ||Uk - u|| en fonction de k, µn et ||A-1
n ||.
-1
||
=
+
et
donner
un
equivalent
de
||A
c) Montrer que lim ||A-1
n
n || pour n tendant
n
vers l'infini.
d) Determiner un nombre d'iterations k suffisant pour avoir k < 10-4 . Donner un
equivalent du nombre de multiplications pour obtenir cette approximation et 
comparer a la methode de factorisation LU . Pour n grand, quelle methode est 
preferable ?

Page 4/4

a) Calculer les valeurs propres de Mn (Indication : interpreter le systeme Mn x 
= x
comme une equation recurrente sur la suite (xk )06k6n+1 avec x0 = xn+1 = 0. (On
constatera qu'il n'y a de solution non nulle que si || < 2).
b) En deduire qu'il existe une suite de reels (µn )nN telle que

An = 2In - Mn .

III.A.3) Dans les questions qui suivent, on applique la methode iterative 
ci-dessus
au systeme An u = w ou An est definie en II.C par (6). On decompose An en

Soit U0  Rn . On considere la suite vectorielle iteree (Uk )kN definie par la 
relation
de recurrrence Uk+1 = HUk + c. Montrer que, si ||H|| < 1, la suite (Uk )kN est
convergente dans Rn de limite u, solution de l'equation (7).

u = Hu + c

III.A.2) On note H une matrice de Mn et c un vecteur de Rn tels que le systeme
(1) peut se reecrire sous la forme

III.A.1)
a) Exprimer ||Ax||2 en fonction de B = t A.A et de x. En deduire que B est une
matrice symetrique positive.
On note sp(B) = {1 (B), ..., n (B)} le spectre de B, c'est-a-dire l'ensemble des
valeurs propres de B enoncees de sorte que 1 (B)  ...  n (B).
p
b) Montrer que ||A|| = n (B).
c) On suppose que A est symetrique et on note (A) = max ||, ou sp(A) est
sp(A)
l'ensemble des valeurs propres de A. Montrer que l'on a ||A|| = (A).

||x||=1

matricielle subordonnee de A  Mn est definie par ||A|| = sup ||Ax||.

k=1

III.A Soit A = [aij ]1i,jn une matrice inversible de Mn . On etudie ici une 
methode
iterative de resolution du systeme (1). On utilise la norme euclidienne sur Rn 
, definie
n
X
x2k , avec x = t (x1 , ..., xn )  Rn . On rappelle que la norme
par ||x||2 =< x, x >=

Partie III - Une methode iterative

MATHÉMATIQUES II

(7)

(8)

lim µn = 0,

n

||Mn || = 2 - µn .

c) Donner un equivalent de µn quand n tend vers l'infini.

 n  N , µn > 0,

Filière MP

· · · FIN · · ·

III.A.4) On considere la decomposition (8). On choisit la donnee initiale U0 de
sorte que ||U0 || = 1. On suppose en outre que ||w|| = 1.
Mn
a) On choisit H =
. Expliciter le vecteur c de maniere a appliquer la methode
2
iterative puis donner l'expression complete de Uk en fonction de U0 , de c et 
des
matrices H m pour m  [[1, k]].
b) Majorer l'erreur k = ||Uk - u|| en fonction de k, µn et ||A-1
n ||.
-1
||
=
+
et
donner
un
equivalent
de
||A
c) Montrer que lim ||A-1
n
n || pour n tendant
n
vers l'infini.
d) Determiner un nombre d'iterations k suffisant pour avoir k < 10-4 . Donner un
equivalent du nombre de multiplications pour obtenir cette approximation et 
comparer a la methode de factorisation LU . Pour n grand, quelle methode est 
preferable ?

Page 4/4

a) Calculer les valeurs propres de Mn (Indication : interpreter le systeme Mn x 
= x
comme une equation recurrente sur la suite (xk )06k6n+1 avec x0 = xn+1 = 0. (On
constatera qu'il n'y a de solution non nulle que si || < 2).
b) En deduire qu'il existe une suite de reels (µn )nN telle que

An = 2In - Mn .

III.A.3) Dans les questions qui suivent, on applique la methode iterative 
ci-dessus
au systeme An u = w ou An est definie en II.C par (6). On decompose An en

Soit U0  Rn . On considere la suite vectorielle iteree (Uk )kN definie par la 
relation
de recurrrence Uk+1 = HUk + c. Montrer que, si ||H|| < 1, la suite (Uk )kN est
convergente dans Rn de limite u, solution de l'equation (7).

u = Hu + c

III.A.2) On note H une matrice de Mn et c un vecteur de Rn tels que le systeme
(1) peut se reecrire sous la forme

III.A.1)
a) Exprimer ||Ax||2 en fonction de B = t A.A et de x. En deduire que B est une
matrice symetrique positive.
On note sp(B) = {1 (B), ..., n (B)} le spectre de B, c'est-a-dire l'ensemble des
valeurs propres de B enoncees de sorte que 1 (B)  ...  n (B).
p
b) Montrer que ||A|| = n (B).
c) On suppose que A est symetrique et on note (A) = max ||, ou sp(A) est
sp(A)
l'ensemble des valeurs propres de A. Montrer que l'on a ||A|| = (A).

||x||=1

matricielle subordonnee de A  Mn est definie par ||A|| = sup ||Ax||.

k=1

III.A Soit A = [aij ]1i,jn une matrice inversible de Mn . On etudie ici une 
methode
iterative de resolution du systeme (1). On utilise la norme euclidienne sur Rn 
, definie
n
X
x2k , avec x = t (x1 , ..., xn )  Rn . On rappelle que la norme
par ||x||2 =< x, x >=

Partie III - Une methode iterative

MATHÉMATIQUES II

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



Centrale Maths 2 MP 2008 -- Corrigé
Ce corrigé est proposé par Chloé Dousset (ENS Cachan) ; il a été relu par Serge
Bouju (Professeur en CPGE) et Benoît Chevalier (ENS Ulm).

L'objet de ce problème est de prouver que sous certaines conditions, une 
matrice A
peut être décomposée sous la forme A = LU avec L triangulaire inférieure à 
diagonale
unité et U triangulaire supérieure. C'est la « factorisation LU », dont le nom 
provient
de l'anglais Lower (inférieur) et Upper (supérieur).
L'épreuve est divisée en trois parties. Les deux premières sont reliées, la 
deuxième
utilisant les résultats de la première dans un cas particulier. La troisième 
partie est
indépendante.
· Dans la première partie, l'objectif est de prouver que toute matrice de Mn (C)
est trigonalisable et d'expliciter le procédé de factorisation LU permettant 
d'obtenir cette trigonalisation.
· Dans la deuxième partie, on applique les résultats précédents au cas 
particulier
d'une matrice tridiagonale. On explicite d'abord la factorisation LU dans ce
cas puis on l'utilise sur un exemple pour inverser une matrice.
· Dans la dernière partie, on cherche à résoudre l'équation d'inconnue u dans 
Rn ,
u = Hu + c
où c est un vecteur de R et H une matrice, par une méthode itérative dont
il faut montrer la convergence et trouver la vitesse par des calculs 
d'équivalents.
Notons que la question III.A.3 est très classique. Elle était déjà présente 
dans la
troisième partie du sujet de Mathématiques 2 de l'École Polytechnique en 2005.
n

Cette épreuve comporte plusieurs spécificités :
· Conformément à l'évolution souhaitée par le jury du concours Centrale-Supélec,
elle comporte beaucoup de questions sur le programme d'informatique (tronc
commun), demandant notamment d'écrire des algorithmes et de calculer le
nombre d'opérations effectuées.
· Elle ne comporte pas de géométrie, contredisant ainsi la notice officielle du
concours qui stipule que « l'une des deux épreuves comporte de la géométrie
ou de la géométrie différentielle ».
Enfin, ce sujet permet de s'exercer au calcul matriciel. En particulier, un 
grand
nombre de questions nécessitent le calcul formel du produit de deux matrices.

Indications
I.

Méthode de Gauss et factorisation

I.A.1
I.B.1
I.B.2.a
I.B.2.b

Écrire le système, partir de la dernière ligne puis remonter ligne par ligne.
Écrire les coefficients de la ligne Lq (P) et faire apparaître les lignes de A.
Soit on explicite F (k, ), soit on étudie l'action de F (k, ) F (k, -).
Le déterminant d'une matrice est inchangé lorsque l'on ajoute à une ligne
une combinaison linéaire des autres lignes.
I.B.2.c Expliciter F (k, ).
I.B.3.b Montrer par récurrence la propriété
H(q) : j  [[ q + 1 ; n ]] Cqj = ej

et

j  [[ 1 ; q ]]

Cqj = bj

pour tout q  [[ 1 ; n ]]
I.C.1-2 On demande ici d'expliciter la méthode du pivot de Gauss.
I.C.3.a Reprendre les questions précédentes et utiliser la stabilité de T I n 
par multiplication.
I.C.3.b Calculer F (k, k ) F (k + 1, k+1 ).
I.C.4 Regrouper les matrices triangulaires supérieures d'un côté et les matrices
triangulaires inférieures à diagonale unité de l'autre, puis utiliser le fait 
que
T I n  T Sn = {In }.
II.

Applications et cas particuliers

II.A.2 Résoudre le système Au = w avec w = ej .
II.B.1 Développer le déterminant suivant la dernière ligne.
II.B.2 Multiplier les deux matrices fournies par l'énoncé puis utiliser 
l'unicité pour
conclure.
II.C.1.a Ce simple calcul est beaucoup plus élégant si on introduit v0 = vn+1 = 
0.
II.C.1.b Prouver que hAn v, vi > 0 pour tout vecteur v et que ce produit 
scalaire est
nul si et seulement si le vecteur v est nul.
II.C.2 Introduire le polynôme associé à la récurrence linéaire d'ordre deux.
II.C.3.b Raisonner par récurrence sur les n - k dernières coordonnées de x puis 
sur
les k premières.
II.C.4. Utiliser la question précédente ainsi que la question II.A.2.
III.

Une méthode itérative

III.A.1.b Utiliser une base orthonormale de diagonalisation de B.
III.A.1.c Utiliser une base orthonormale de diagonalisation de A.
k
III.A.2. Montrer que kUk+1 - Uk k 6 kHk kU1 - U0 k et en déduire que la série de
terme général Uk+1 - Uk converge.
III.A.3.a Introduire le polynôme associé à la relation de récurrence et 
utiliser le fait
que x0 = xn+1 = 0.
III.A.4.a Raisonner par récurrence.
III.A.4.c Faire le lien entre les valeurs propres de An -1 et celles de An .

Les conseils du jury
Le rapport du jury souligne que la première partie du sujet, « bien que très
proche du cours et ne présentant aucune difficulté particulière, a été ressentie
comme trop lointaine par de nombreux candidats qui, de ce fait, l'ont délaissée 
pour passer rapidement aux deux suivantes ». D'autres y ont « glané
l'essentiel de leurs points mais au prix de calculs laborieux ». Dans cette
partie, « les algorithmes demandés ont été très souvent ignorés » alors que
leur « caractère rémunérateur » n'est pas à minimiser. La deuxième partie
« ne requérait que les bases du calcul matriciel » à l'exception « d'un détour
par la notion de matrice définie positive, dont l'assimilation a d'ailleurs 
laissé
aux correcteurs une impression mitigée ». La dernière partie demandait « une
bonne compréhension des notions de Topologie ». De façon générale, le jury
rappelle que « le programme des épreuves de Mathématiques est la réunion de
ceux des deux années de classes préparatoires et que toute stratégie contraire
[...] est éminemment risquée ».

I. Méthode de Gauss et factorisation
I.A.1 Le système étudié est

a1,1 a1,2 · · ·
a1,n-1
 0
a
2,2

 ..
..
..
 .
.
.

 .
.
.. a
 ..
n-1,n-1
0
··· ···
0

a1,n
a2,n
..
.
an-1,n
an,n

u1

  u2
 .
 .
 .

un-1

un

w1
w2
..
.

=
 
  wn-1
wn

Grâce à la dernière ligne, on obtient an,n un = wn . De plus, det (A) =
ce qui implique an,n 6= 0 et permet d'obtenir un = wn /an,n .

n
Q

ai,i 6= 0,

i=1

Cette question est très facile, la seule subtilité consiste à justifier que l'on
peut diviser par an,n .
On va maintenant « remonter » le système. Pour cela, on écrit la (n - k) e ligne
n
P

an-k,j uj = wn-k

j=n-k

On en déduit que

an-k,n-k un-k = wn-k -

n
P

an-k,j uj

j=n-k+1

et comme précédemment, on utilise le fait que an-k,n-k 6= 0 pour obtenir
!
n
P
1
un-k =
wn-k -
an-k,j uj
an-k,n-k
j=n-k+1

L'algorithme de résolution du système est donc
wn
;
un :=
an,n
Pour k allant de 1 à n - 1 faire
n
P
S :=
an-k,j uj ;
j=n-k+1

1

un-k := (wn-k - S) ×

an-k,n-k

;

I.A.2 La première ligne du code nécessite une division et chaque itération 
utilise une
n
P
soustraction (équivalente à une addition), une division et le calcul de
an-k,j uj .
j=n-k+1

Cette somme est obtenue grâce à k multiplications et à k - 1 additions. Le 
nombre
total d'opérations nécessaires à la résolution du système est donc

Nmultiplication
Ndivision

n-1
P

n(n - 1)
2
k=1
n-1
P
n(n - 1)
k=
=
2
k=1
= 1 + (n - 1) = n

Naddition =

k=

I.B.1 Soit q  [[ 1 ; n ]]. Considérons la ligne Lq (P) = (pq,j )16j6n .
n
P
On a pq,j =
mq,i ai,j et, par conséquent
i=1

(pq,j )16j6n =

c'est-à-dire

n
P

mq,i ai,j

i=1

Lq (P) =

=

16j6n

n
P

n
P

i=1

mq,i (ai,j )16j6n

mq,i Li (A)

i=1

I.B.2.a Ici, il y a deux possibilités : soit on calcule directement d'abord F 
(k, )
puis le produit F (k, ) F (k, -), et alors on entame sérieusement la question 
I.B.2.c ;
soit on démontre le résultat sans se servir de la formule explicite de F (k, ).
Première méthode. On cherche des coefficients (q,i )16q,i6n tels que
(
n
P
Lq si 1 6 q 6 k

Lq =
q,i Li =
pour toute matrice A
Lq + q Lk si k + 1 6 q 6 n
i=1

On en déduit, soit par identification, soit en prenant A = Ei,j , que q,i = i,q
si 1 6 i 6 k, et q,i = i,q + q i,k si k + 1 6 i 6 n, soit

1

..

.

1

F (k, ) = 

.
.

.
k+1

..
..

.
.
n
1