Questions du sujet
1. I.A.1) Calculer $u_n$ puis pour $k \in [[1, n-1]]$ exprimer $u_{n-k}$ en fonction de $u_n, u_{n-1}, …, u_{n-k+1}$. Ecrire l’algorithme de résolution du système (1). 2. I.A.2) Exprimer en fonction de $n$ le nombre d’additions, de multiplications et de divisions nécessaires à la résolution du système (1). 3. I.B.1) Soient $M$ une matrice de $\mathcal{M}_n$ et $P=MA$. Exprimer, pour tout entier $q$ de $[[1, n]]$, $L_q(P)$ en fonction des lignes $L_i(A)$ de la matrice $A$. 4. I.B.2) Pour un entier $k$ de $[[1, n-1]]$ et un vecteur $\beta = \transp{(\beta_{k+1}, …, \beta_n)} \in \mathbb{R}^{n-k}$, on note $F(k,\beta)$ la matrice de $\mathcal{M}_n$ qui réalise par le produit à gauche $P = F(k, \beta)A$ les combinaisons linéaires de lignes suivantes, en notant pour simplifier $L_i = L_i(A)$ et $L’_i = L_i(P)$ : \[ \forall i \in [[1, k]], L’_i = L_i \text{ et } \forall i \in [[k+1, n]], L’_i = L_i + \beta_i L_k. \] a) Montrer que $F(k,\beta)^{-1} = F(k, -\beta)$.\\ b) Montrer que si $P=F(k,\beta)A$ on a : $\forall q \in [[1,n]], D_q(P) = D_q(A)$.\\ c) Déterminer les coefficients $\varphi_{ij}$ de $F(k,\beta)$ pour tout couple $(i, j)$ d’entiers de $[[1, n]] \times [[1, n]]$. Montrer que $F(k, \beta) \in TI_n$. 5. I.B.3) a) Etant donnée une matrice $M = [m_{ij}]_{1\leq i,j\leq n}$ de $\mathcal{M}_n$, exprimer les vecteurs colonnes $C’_j$ du produit matriciel $MF(k, \beta)$ en fonction des colonnes $C_j$ de $M$.\\ b) Soit $q$ un entier de $[[1, n]]$ et pour tout entier $k$ de $[[1, q]]$, $\beta_k = \transp{(\beta_{k+1, k}, …, \beta_{n, k})}$ un vecteur de $\mathbb{R}^{n-k}$. On considère la matrice produit $P_q = F(1,\beta_1)\cdot F(2,\beta_2)\cdots F(q, \beta_q) = \prod_{k=1}^q F(k, \beta_k)$. On note $C_{qj}$ les vecteurs colonnes de la matrice $P_q$ et pour tout entier $k$ de $[[1, q]]$, $b_k=\transp{(0, …, 0, 1, \beta_{k+1,k}, …, \beta_{n,k})} \in \mathbb{R}^n$. Montrer par récurrence sur $q$ que : \[ \forall j \in [[q+1, n]], C_{qj} = \mathbf{e}_j \text{ et } \forall j \in [[1, q]], C_{qj} = b_j. \] En déduire que $P_q$ appartient à $TI_n$ et que $P_{n-1} = [b_1, …, b_{n-1}, \mathbf{e}_n]$.} 6. I.C.1) Montrer que $a^1_{11} \neq 0$. Déterminer $\beta_1 = \transp{(\beta_{21}, …, \beta_{n1})} \in \mathbb{R}^{n-1}$ pour que la première colonne de $A_2 = F(1, -\beta_1)A_1$ soit proportionnelle à $\mathbf{e}_1$. Que vaut la première ligne de $A_2$ ? 7. I.C.2) On pose $F_1 = F(1, -\beta_1)$.\\ a) Montrer par récurrence sur $k$ l’existence des suites de matrices $(F_{k-1})_{2\leq k\leq n}$, $(A_k)_{2\leq k\leq n}$ avec $F_{k-1} = F(k-1, -\beta_{k-1}), A_k = [a^k_{ij}]_{1\leq i,j\leq n} = F_{k-1}A_{k-1}$ et telles que : $\forall j \in [[1, k-1]], \forall i \in [[j+1, n]], a^k_{ij} = 0$ et $\forall m \in [[1, n]], D_m(A_k)\neq 0$.\\ Exprimer le vecteur $\beta_k$ à l’aide des coefficients de $A_k$.\\ b) Montrer que les lignes $1$ à $k$ de $A_k$ et $A_{k+1}$ sont identiques.\\ c) Pour $k\in [[1, n-1]]$, soit $N_k$ le nombre de multiplications nécessaires pour passer de $A_k$ à $A_{k+1}$. Calculer le nombre $N_k$. 8. I.C.3) a) Déduire des questions précédentes qu’il existe une matrice $L$ de $TI_n$ et une matrice $U$ de $TS_n$ telles que l’on ait $A = LU$.\\ b) Exprimer les coefficients $l_{ij}$ de $L$ pour $i > j$ et les coefficients $u_{ij}$ de $U$ pour $i \leq j$ en fonction des coefficients $a^k_{ij}$ des matrices $A_k$ (Utiliser (I.B.2a) et (I.C.2a)). 9. I.C.4) Montrer que les matrices $L$ et $U$ de la factorisation (5) sont uniques. 10. I.C.5) Ecrire dans le langage de son choix un programme réalisant la factorisation $A = LU$ qui n’utilise qu’un seul tableau carré encore nommé $A$ pour contenir toutes les itérations $A_k$. On prendra soin de commenter les principales lignes du programme. Comment aura-t-on en final les facteurs $L$ et $U$ à partir du tableau $A$ ?} 11. I.C.6) Soit $S_n$ le nombre de multiplications nécessaires à la factorisation $A = LU$. Calculer $S_n$. (Indication : utiliser la question I.C.2.c.) 12. II.A.1) On veut résoudre le système (1) en utilisant la factorisation (5). On fait toujours l’hypothèse que pour tout entier $k$ de $[[1, n]], D_k(A) \neq 0$. Sans compter les opérations nécessaires à la factorisation, montrer qu’il suffit de $n(n-1)$ multiplications pour résoudre le système (préciser la méthode utilisée). 13. II.A.2) En déduire une méthode pour inverser la matrice $A$ en utilisant la factorisation (5). Exprimer le nombre total de multiplications et divisions nécessaires à cette inversion, incluant cette fois-ci le calcul de la factorisation. En donner un équivalent lorsque $n \to \infty$. 14. II.B.1) On pose $\delta_k = D_k(A)$, $\delta_0 = 1$. On suppose que pour tout $k$ de $[[1, n]], \delta_k \neq 0$. Calculer $\delta_1$ puis, pour $k \in [[2, n]]$, exprimer $\delta_k$ en fonction de $\delta_{k-1}$ et de $\delta_{k-2}$. 15. II.B.2) Montrer que les matrices $L$ et $U$ de la factorisation (5) sont de la forme \[ L = \begin{pmatrix} 1 \\ l_{21} & 1 \\ l_{32} & 1 \\ \vdots & & \ddots \\ l_{n n-1} & 1 \end{pmatrix} \] avec pour tout $i$ de $[[2, n]], l_{i, i-1} = \dfrac{a_i\, \delta_{i-2}}{\delta_{i-1}}, \quad U = \begin{pmatrix} \dfrac{\delta_1}{\delta_0} & c_1 & & \\ & \dfrac{\delta_2}{\delta_1} & \ddots & \\ & & \ddots & c_{n-1} \\ & & & \dfrac{\delta_n}{\delta_{n-1}} \end{pmatrix} $. } 16. II.B.3) Ecrire un algorithme de résolution du système $A u = w$ en utilisant la factorisation précédente pour une matrice tridiagonale. Donner le nombre de multiplications, de divisions et d’additions nécessaires à cette résolution. 17. II.C.1) a) Montrer que pour chaque $v = \transp{(v_1,…, v_n)}$ de $\mathbb{R}^n$, on a $\langle A_n v, v \rangle = v_1^2 + v_n^2 + \sum_{i=2}^n (v_i- v_{i-1})^2$.\\ b) En déduire que la matrice $A_n$ est définie positive.\\ c) Montrer que pour chaque $k$ de $[[1, n]]$ la matrice $\Delta_k(A_n)$ est symétrique et définie positive. En déduire qu’il existe une factorisation $A_n = L_n U_n$ de la forme (5). 18. II.C.2) On reprend les notations de la question II.B. Expliciter et résoudre la récurrence sur $\delta_k$. En déduire l’expression des matrices $L_n$ et $U_n$. 19. II.C.3) On veut résoudre le système $A_n x = e_k$ pour un entier fixé $k \in [[1, n]]$.\\ a) Résoudre le système $L_n y = e_k$.\\ b) Résoudre le système $U_n x = y$.\\ (On montrera que : $x_i = \dfrac{i(n+1-k)}{n+1}$ si $i \leq k$ et $x_i = \dfrac{k(n+1-i)}{n+1}$ si $i > k$). 20. II.C.4) On pose $A_n^{-1} = [b_{ij}]_{1\leq j,k\leq n}$. Calculer $b_{ij}$ pour $(i,j)\in [[1, n]] \times [[1, n]]$.} 21. III.A.1) a) Exprimer $||Ax||_2$ en fonction de $B = {}^t\!A\,A$ et de $x$. En déduire que $B$ est une matrice symétrique positive. On note $sp(B) = \{\lambda_1(B), …, \lambda_n(B)\}$ le spectre de $B$, c’est-à-dire l’ensemble des valeurs propres de $B$ énoncées de sorte que $\lambda_1(B) \leq … \leq \lambda_n(B)$.\\ b) Montrer que $||A|| = \sqrt{\lambda_n(B)}$.\\ c) On suppose que $A$ est symétrique et on note $\rho(A) = \max_{\lambda \in sp(A)}|\lambda|$, où $sp(A)$ est l’ensemble des valeurs propres de $A$. Montrer que l’on a $||A|| = \rho(A)$. 22. III.A.2) On note $H$ une matrice de $\mathcal{M}_n$ et $c$ un vecteur de $\mathbb{R}^n$ tels que le système (1) peut se réécrire sous la forme $u = Hu + c$. Soit $U_0 \in \mathbb{R}^n$. On considère la suite vectorielle itérée $(U_k)_{k\in\mathbb{N}}$ définie par la relation de récurrence $U_{k+1} = HU_k + c$. Montrer que, si $||H|| <1$, la suite $(U_k)_{k\in\mathbb{N}}$ est convergente dans $\mathbb{R}^n$ de limite $u$, solution de l’équation. 23. III.A.3) Dans les questions qui suivent, on applique la méthode itérative ci-dessus au système $A_n u = w$ où $A_n$ est définie en II.C par (6). On décompose $A_n = 2I_n - M_n$.\\ a) Calculer les valeurs propres de $M_n$ (Indication : interpréter le système $M_n x = \lambda x$ comme une équation récurrente sur la suite $(x_k)_{0 \leq k \leq n+1}$ avec $x_0 = x_{n+1}=0$. (On constatera qu’il n’y a de solution non nulle que si $|\lambda| < 2$.)\\ b) En déduire qu’il existe une suite de réels $(\mu_n)_n$ telle que $\forall n \in \mathbb{N},\, \mu_n > 0,\, \lim_{n\to\infty} \mu_n = 0,\, ||M_n|| = 2 – \mu_n$.\\ c) Donner un équivalent de $\mu_n$ quand $n$ tend vers l’infini. 24. III.A.4) On considère la décomposition (8). On choisit la donnée initiale $U_0$ de sorte que $||U_0|| = 1$. On suppose en outre que $||w|| = 1$.\\ a) On choisit $H = M_n^2$. Expliciter le vecteur $c$ de manière à appliquer la méthode itérative puis donner l’expression complète de $U_k$ en fonction de $U_0$, de $c$ et des matrices $H_m$ pour $m \in [[1, k]]$.\\ b) Majorer l’erreur $\varepsilon_k = ||U_k – u||$ en fonction de $k,\, \mu_n$ et $||A_n^{-1}||$.\\ c) Montrer que $\lim_{n\to\infty} ||A_n^{-1}|| = +\infty$ et donner un équivalent de $||A_n^{-1}||$ pour $n$ tendant vers l’infini.\\ d) Déterminer un nombre d’itérations $k$ suffisant pour avoir $\varepsilon_k < 10^{-4}$. Donner un équivalent du nombre de multiplications pour obtenir cette approximation et comparer à la méthode de factorisation LU. Pour $n$ grand, quelle méthode est préférable ?}FAQ
Le sujet couvre des thèmes fondamentaux d’algèbre linéaire et d’analyse matricielle : systèmes linéaires, factorisation LU, matrices tridiagonales, études de la complexité algorithmique, propriétés de positivité, norme matricielle et valeurs propres, ainsi que des méthodes itératives pour la résolution de systèmes. Maîtriser ces notions est indispensable pour réussir les concours d’écoles d’ingénieurs tels que Centrale. Pour approfondir chaque type d’exercice, tu peux débloquer les corrigés sur Prépa Booster.
La factorisation LU (décomposition d’une matrice en un produit de matrices triangulaires inférieure et supérieure) est au cœur des stratégies de résolution efficace des systèmes linéaires. Elle permet aussi d’accélérer l’inversion matricielle et le calcul de déterminants. Au concours Centrale, on attend de toi que tu comprennes à la fois le principe, la mise en œuvre algorithmique et l’optimisation en nombre d’opérations. Pour voir des exemples corrigés détaillés pas à pas, n’hésite pas à débloquer les corrigés sur Prépa Booster.
Evaluer le nombre d’additions, multiplications ou divisions permet de comparer la performance des différentes méthodes de résolution, en vue de traiter des systèmes de grande taille. Cette analyse est cruciale pour l’algorithmique et l’optimisation, compétences clés en MP. Cela t’entraîne aussi à estimer la faisabilité des calculs en pratique, compétence attendue au concours.
Une matrice tridiagonale est une matrice carrée où seuls les coefficients diagonaux et ceux juste au-dessus et en dessous de la diagonale principale peuvent être non nuls. On en rencontre fréquemment dans la modélisation de problèmes physiques (différences finies, équations aux dérivées partielles, chaînes de Markov…). Sa structure permet des calculs rapides et de nombreux résultats élégants qui tombent dans les sujets de concours pour évaluer la maîtrise des méthodes numériques.
La résolution directe, comme la factorisation LU, donne la solution en un nombre fini d’étapes après transformation de la matrice initiale. La résolution itérative, elle, procède par approximations successives qui convergent vers la solution (méthodes type Jacobi, Gauss-Seidel, ou l’algorithme général de point fixe). Chaque a ses avantages : la méthode directe est plus adaptée aux matrices de petite à moyenne taille, tandis que l’itérative s’impose pour les grandes matrices creuses ou mal conditionnées.
Pour prouver qu’une matrice réelle symétrique est définie positive, on montre que pour tout vecteur non nul x, le produit scalaire ⟨Ax, x⟩ est strictement positif. Cela peut se faire soit par calcul direct, soit en exhibant une décomposition (type Cholesky) ou en utilisant la structure de la matrice (symétrie, connexions à des opérateurs positifs). Ce point apparaît régulièrement, car il garantit l’existence unique de solutions pour certains systèmes et permet d’affirmer la convergence des méthodes numériques.
Identifie tout de suite la nature de la matrice (pleine, tridiagonale, symétrique, définie positive…). Appuie-toi sur les invariants (déterminant, rang, structure) et garde en tête les méthodes de factorisation et de calcul de complexité. Lis attentivement chaque question pour anticiper la logique du barème et gagner du temps sur les calculs récurrents. Et si tu veux travailler sur des sujets types avec explications détaillées, pense à débloquer les corrigés pour bénéficier du meilleur accompagnement sur Prépa Booster.
La connaissance des normes et des valeurs propres te permet d’étudier la stabilité (convergence des algorithmes, conditionnement), d’optimiser l’itération (choisir un H tel que ||H||<1 garantit la convergence d’un schéma itératif), et de majorer les erreurs d’approximation. Ces outils sont fréquemment testés dans les derniers exercices de sujet type MP Centrale.
Surtout, ne panique pas. Repère la méthode classique associée au type de matrice : pour tridiagonale, pense à l’algorithme de Thomas ; pour matrices générales, retrace la factorisation LU. Si la question porte sur des calculs d’opérations, essaye de faire un schéma pour visualiser les étapes. Et passe à la suite si tu coinces, reviens-y plus tard : souvent, les questions suivantes ou précédentes apportent un indice ! Pour plus d’astuces méthodologiques, découvre le dashboard personnalisé après avoir débloqué les corrigés sur Prépa Booster.