Centrale Maths 2 MP 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 - 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