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