Le trafic routier
Trouver x 1 , x 2 , … , x 5 x_1,x_2,\ldots,x_5 x 1 , x 2 , … , x 5
En A : x 2 + x 4 ⏞ entrant = 300 + x 3 ⏞ sortant En B : 100 + 400 = x 4 + x 5 En C : 300 + 500 = x 1 + x 2 En D : x 1 + x 5 = 600 \begin{alignedat}{2} &\text{En }A: \overbrace{x_2+x_4}^{\text{entrant}}&&=\overbrace{300+x_3}^{\text{sortant}}\\ &\text{En }B: 100+400&&=x_4+x_5\\ &\text{En }C: 300+500&&=x_1+x_2\\ &\text{En }D: x_1+x_5&&=600\\ \end{alignedat} En A : x 2 + x 4 entrant En B : 1 0 0 + 4 0 0 En C : 3 0 0 + 5 0 0 En D : x 1 + x 5 = 3 0 0 + x 3 sortant = x 4 + x 5 = x 1 + x 2 = 6 0 0
Existe-t-il x 1 , x 2 , … , x 5 x_1,x_2,\ldots,x_5 x 1 , x 2 , … , x 5 tels que les quatre contraintes soient satisfaites ?
Si oui, est-ce que x i x_i x i est positif pour tous les i = 1 , 2 , … , 5 i=1,2,\ldots,5 i = 1 , 2 , … , 5 ?
Existe-t-il une infinité de solutions ?
Une équation linéaire en x 1 , x 2 , … , x n ( ∈ R ) x_1,x_2,\ldots,x_n (\in\R) x 1 , x 2 , … , x n ( ∈ R ) est une relation de la forme
a 1 x 1 + a 2 x 2 + … + a n x n = b \boxed{a_1x_1+a_2x_2+\ldots+a_nx_n=b} a 1 x 1 + a 2 x 2 + … + a n x n = b
où les a 1 , a 2 , … , a n , b a_1,a_2,\ldots,a_n,b a 1 , a 2 , … , a n , b sont des constantes fixées.
Un système linéaire est une famille d'équations linéaires
( ∗ ) { a 11 x 1 + a 12 x 2 + a 13 x 3 + … + a 1 n x n = b 1 a 21 x 1 + a 22 x 2 + a 23 x 3 + … + a 2 n x n = b 2 ⋮ a m 1 x 1 + a m 2 x 2 + a m 3 x 3 + … + a m n x n = b m (*) \begin{cases} a_{11}x_1+a_{12}x_2+a_{13}x_3+\ldots+a_{1n}x_n &= b_1 \\ a_{21}x_1+a_{22}x_2+a_{23}x_3+\ldots+a_{2n}x_n &= b_2 \\ \vdots \\ a_{m1}x_1+a_{m2}x_2+a_{m3}x_3+\ldots+a_{mn}x_n &= b_m \\ \end{cases} ( ∗ ) ⎩ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎧ a 1 1 x 1 + a 1 2 x 2 + a 1 3 x 3 + … + a 1 n x n a 2 1 x 1 + a 2 2 x 2 + a 2 3 x 3 + … + a 2 n x n ⋮ a m 1 x 1 + a m 2 x 2 + a m 3 x 3 + … + a m n x n = b 1 = b 2 = b m
Il s'agit d'un système "m m m xn n n ", où m m m correspond au nombre d'équations et n n n au nombre de variables.
Les réels a i j ( 1 ⩽ i ⩽ m , 1 ⩽ j ⩽ n ) a_{ij}(1\leqslant i\leqslant m,1\leqslant j\leqslant n) a i j ( 1 ⩽ i ⩽ m , 1 ⩽ j ⩽ n ) sont les coefficients du système.
Résoudre ( ∗ ) (*) ( ∗ ) , c'est décrire toutes les listes ( x 1 , x 2 , … , x n ) (x_1,x_2,\ldots,x_n) ( x 1 , x 2 , … , x n ) (s'il y en en a !), qui satisfont les m m m relations de ( ∗ ) (*) ( ∗ ) .
( m = 2 , n = 2 ) (m=2,n=2) ( m = 2 , n = 2 )
( ∗ ) { x 1 − x 2 = − 1 droite α 2 x 1 + 3 x 2 = 8 droite β (*) \begin{cases} x_1-x_2 &= -1 &&\color{Blue}\text{droite }\alpha\\ 2x_1+3x_2 &= 8 &&\color{red}\text{droite }\beta \end{cases} ( ∗ ) { x 1 − x 2 2 x 1 + 3 x 2 = − 1 = 8 droite α droite β
( m = 2 , n = 2 ) (m=2,n=2) ( m = 2 , n = 2 )
( ∗ ) { x 1 − x 2 = − 1 droite α 2 x 1 − 2 x 2 = − 2 droite β (*) \begin{cases} x_1-x_2 &= -1 &&\color{Blue}\text{droite }\alpha\\ 2x_1-2x_2 &= -2 &&\color{red}\text{droite }\beta \end{cases} ( ∗ ) { x 1 − x 2 2 x 1 − 2 x 2 = − 1 = − 2 droite α droite β
( m = 2 , n = 2 ) (m=2,n=2) ( m = 2 , n = 2 )
( ∗ ) { x 1 − x 2 = − 1 droite α x 1 − x 2 = 0 droite β (*) \begin{cases} x_1-x_2 &= -1 &&\color{Blue}\text{droite }\alpha\\ x_1-x_2 &= 0 &&\color{red}\text{droite }\beta \end{cases} ( ∗ ) { x 1 − x 2 x 1 − x 2 = − 1 = 0 droite α droite β
( m = 2 , n = 3 ) (m=2,n=3) ( m = 2 , n = 3 )
( ∗ ) { x 1 + x 2 + x 3 = 1 plan α 2 x 1 − x 2 = 0 plan β (*) \begin{cases} x_1+x_2+x_3 &= 1 &&\color{Blue}\text{plan }\alpha\\ 2x_1-x_2 &= 0 &&\color{red}\text{plan }\beta \end{cases} ( ∗ ) { x 1 + x 2 + x 3 2 x 1 − x 2 = 1 = 0 plan α plan β
( m = 2 , n = 3 ) (m=2,n=3) ( m = 2 , n = 3 )
( ∗ ) { x 1 + x 2 + x 3 = 1 plan α x 1 + x 2 + x 3 = 7 plan β (*) \begin{cases} x_1+x_2+x_3 &= 1 &&\color{Blue}\text{plan }\alpha\\ x_1+x_2+x_3 &= 7 &&\color{red}\text{plan }\beta \end{cases} ( ∗ ) { x 1 + x 2 + x 3 x 1 + x 2 + x 3 = 1 = 7 plan α plan β
( m = 3 , n = 3 ) (m=3,n=3) ( m = 3 , n = 3 )
( ∗ ) { x 1 + x 2 + x 3 = 1 2 x 1 − x 2 = 0 x 1 − 3 x 3 = 0 (*) \begin{cases} x_1+x_2+x_3 &&= 1 \\ 2x_1-x_2 &&= 0 \\ x_1-3x_3 &&= 0 \end{cases} ( ∗ ) ⎩ ⎪ ⎪ ⎨ ⎪ ⎪ ⎧ x 1 + x 2 + x 3 2 x 1 − x 2 x 1 − 3 x 3 = 1 = 0 = 0
→ unique solution ! \rightarrow \text{unique solution !} → unique solution !
Tout système linéaire m × n m\times n m × n (du type ( ∗ ) (*) ( ∗ ) vu plus haut) possède
Soit aucune solution,
Soit exactement une solution,
Soit une infinité de solutions.
Compatibilité et incompatibilité
Le premier cas, lorsqu'il n'y a aucune solution, les équations sont dites "incompatible". Lorsqu'il y a au moins une solution, à savoir dans les deux autres cas, les équations sont dites "compatibles"
Supposons que le système
( ∗ ) { a 11 x 1 + a 12 x 2 + a 13 x 3 + … + a 1 n x n = b 1 a 21 x 1 + a 22 x 2 + a 23 x 3 + … + a 2 n x n = b 2 ⋮ a m 1 x 1 + a m 2 x 2 + a m 3 x 3 + … + a m n x n = b m (*) \begin{cases} a_{11}x_1+a_{12}x_2+a_{13}x_3+\ldots+a_{1n}x_n &= b_1 \\ a_{21}x_1+a_{22}x_2+a_{23}x_3+\ldots+a_{2n}x_n &= b_2 \\ \vdots \\ a_{m1}x_1+a_{m2}x_2+a_{m3}x_3+\ldots+a_{mn}x_n &= b_m \\ \end{cases} ( ∗ ) ⎩ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎧ a 1 1 x 1 + a 1 2 x 2 + a 1 3 x 3 + … + a 1 n x n a 2 1 x 1 + a 2 2 x 2 + a 2 3 x 3 + … + a 2 n x n ⋮ a m 1 x 1 + a m 2 x 2 + a m 3 x 3 + … + a m n x n = b 1 = b 2 = b m
possède deux solutions distinctes (c'est-à-dire qu'il existe au moins un k ∈ { 1 , 2 , … , n } k\in \{ 1,2,\ldots,n \} k ∈ { 1 , 2 , … , n } tel que x k ≠ y k x_k≠y_k x k = y k ), que l'on note ( x 1 , x 2 , … , x n ) (x_1,x_2,\ldots,x_n) ( x 1 , x 2 , … , x n ) et ( y 1 , y 2 , … , y n ) (y_1,y_2,\ldots,y_n) ( y 1 , y 2 , … , y n ) .
On a donc
∀ j = 1 , 2 , … , m a j 1 x 1 + a j 2 x 2 + … + a j n x n a j 1 y 1 + a j 2 y 2 + … + a j n y n \begin{aligned} \forall j=1,2,\ldots,m\\&&a_{j1}x_1+a_{j2}x_2+\ldots + a_{jn}x_n\\ &&a_{j1}y_1+a_{j2}y_2+\ldots + a_{jn}y_n \end{aligned} ∀ j = 1 , 2 , … , m a j 1 x 1 + a j 2 x 2 + … + a j n x n a j 1 y 1 + a j 2 y 2 + … + a j n y n
Soit ( z 1 , z 2 , … , z n ) (z_1,z_2,\ldots,z_n) ( z 1 , z 2 , … , z n ) définie comme suit :
∀ k = 1 , 2 , … , m z k ≔ x k + t ( y k − x k ) o u ˋ t ∈ R ∗ est fix e ˊ , arbitraire. \begin{aligned} &\forall k=1,2,\ldots,m\\ &\boxed{z_k\coloneqq x_k+t(y_k-x_k)}\\ &\text{ où }t\in\R^* \text{ est fixé, arbitraire.} \end{aligned} ∀ k = 1 , 2 , … , m z k : = x k + t ( y k − x k ) o u ˋ t ∈ R ∗ est fix e ˊ , arbitraire.
Notation : le signe ≔ \coloneqq : = signifie "est défini par".
Remarque : si t ≠ 0 t≠0 t = 0 et t ≠ 1 t≠1 t = 1 , ( z 1 , z 2 , … , z n ) (z_1,z_2,\ldots,z_n) ( z 1 , z 2 , … , z n ) est distincte de ( x 1 , x 2 , … , x n ) (x_1,x_2,\ldots,x_n) ( x 1 , x 2 , … , x n ) et ( y 1 , y 2 , … , y n ) (y_1,y_2,\ldots,y_n) ( y 1 , y 2 , … , y n ) !
( z 1 , z 2 , … , z n ) (z_1,z_2,\ldots,z_n) ( z 1 , z 2 , … , z n ) est aussi solution de ( ∗ ) (*) ( ∗ ) .
∀ j = 1 , 2 , … , m \forall j = 1,2,\ldots,m ∀ j = 1 , 2 , … , m on calcule :
a j 1 z 1 ⏟ α + a j 2 z 2 ⏟ β + … + a j k z k + … + a j n z n ⏟ γ = a j 1 ( x 1 + t ( y 1 ‾ − x 1 ‾ ) ) ⏟ α + a j 2 ( x 2 + t ( y 2 ‾ − x 2 ‾ ) ) ⏟ β + … + a j n ( x n + t ( y n ‾ − x n ‾ ) ) ⏟ γ \begin{aligned} &a_{j1}\underbrace{z_1}_{\alpha}+a_{j2}\underbrace{z_2}_{\beta}+\ldots + a_{jk}z_k+\ldots + a_{jn}\underbrace{z_n}_{\gamma}\\ =&\color{blue}{a_{j1}}\color{black}\underbrace{(\color{blue}x_1\color{black} +\color{green}\underline{\color{black}t(y_1}\color{red}\overline{\color{black}-x_1}\color{black}))}_{\alpha} +\color{blue}a_{j2}\color{black}\underbrace{(\color{blue}x_2\color{black} +\color{green}\underline{\color{black}t(y_2}\color{red}\overline{\color{black}-x_2}\color{black}))}_{\beta}+\ldots +\color{blue}a_{jn}\color{black}\underbrace{(\color{blue}x_n\color{black} +\color{green}\underline{\color{black}t(y_n}\color{red}\overline{\color{black}-x_n}\color{black}))}_{\gamma}\\ \end{aligned} = a j 1 α z 1 + a j 2 β z 2 + … + a j k z k + … + a j n γ z n a j 1 α ( x 1 + t ( y 1 − x 1 ) ) + a j 2 β ( x 2 + t ( y 2 − x 2 ) ) + … + a j n γ ( x n + t ( y n − x n ) )
On réarange les termes pour obtenir
= ( a j 1 x 1 + … + a j n x n ) + t ( a j 1 y 1 + … + a j n y n ) − t ( a j 1 x 1 + … + a j n x n ) \begin{aligned} =&\color{blue}(a_{j1}x_1+\ldots + a_{jn}x_n)\color{black} \color{green}+t(a_{j1}y_1+\ldots + a_{jn}y_n) \color{red}-t(a_{j1}x_1+\ldots+a_{jn}x_n)\\ \end{aligned} = ( a j 1 x 1 + … + a j n x n ) + t ( a j 1 y 1 + … + a j n y n ) − t ( a j 1 x 1 + … + a j n x n )
Constat
( a j 1 x 1 + … + a j n x n ) = b j car ( x 1 , x 2 , … x n ) est solution. ( a j 1 y 1 + … + a j n y n ) = b j car ( y 1 , y 2 , … y n ) est solution. ( a j 1 x 1 + … + a j n x n ) = b j . \begin{aligned} &\color{blue}(a_{j1}x_1+\ldots + a_{jn}x_n)=b_j\text{ car }(x_1,x_2,\ldots x_n) \text{ est solution.}\\ &\color{green}(a_{j1}y_1+\ldots + a_{jn}y_n)= b_j\text{ car }(y_1,y_2,\ldots y_n) \text{ est solution.}\\ &\color{red}(a_{j1}x_1+\ldots+a_{jn}x_n)=b_j. \end{aligned} ( a j 1 x 1 + … + a j n x n ) = b j car ( x 1 , x 2 , … x n ) est solution. ( a j 1 y 1 + … + a j n y n ) = b j car ( y 1 , y 2 , … y n ) est solution. ( a j 1 x 1 + … + a j n x n ) = b j .
= b j + t b j − t b j = b j ⇒ Donc ( z 1 , z 2 , … , z n ) est solution de ( ∗ ) . Comme t ∈ R est arbitraire, on peut donc construire une infinit e ˊ de solutions pour ( ∗ ) . □ \begin{aligned} &=b_j+tb_j-tb_j\\ &=b_j\\ &\Rightarrow\text{ Donc }(z_1,z_2,\ldots,z_n)\text{ est solution de }(*). \end{aligned} \\ \begin{array}{r} \begin{aligned} &\text{Comme } t\in\R \text{ est arbitraire, on peut donc construire une infinité de} \\ &\text{solutions pour }(*). \end{aligned} \\ \square \end{array} = b j + t b j − t b j = b j ⇒ Donc ( z 1 , z 2 , … , z n ) est solution de ( ∗ ) . Comme t ∈ R est arbitraire, on peut donc construire une infinit e ˊ de solutions pour ( ∗ ) . □
Notation : "□ \square □ " signifie "C.Q.F.D."
Remarque : géométriquement, voici ce que l'on a fait :
Soit un système m × n m \times n m × n
( ∗ ) { a 11 x 1 + a 12 x 2 + a 13 x 3 + … + a 1 n x n = b 1 a 21 x 1 + a 22 x 2 + a 23 x 3 + … + a 2 n x n = b 2 ⋮ a m 1 x 1 + a m 2 x 2 + a m 3 x 3 + … + a m n x n = b m (*) \begin{cases} a_{11}x_1+a_{12}x_2+a_{13}x_3+\ldots+a_{1n}x_n &= b_1 \\ a_{21}x_1+a_{22}x_2+a_{23}x_3+\ldots+a_{2n}x_n &= b_2 \\ \vdots \\ a_{m1}x_1+a_{m2}x_2+a_{m3}x_3+\ldots+a_{mn}x_n &= b_m \\ \end{cases} ( ∗ ) ⎩ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎧ a 1 1 x 1 + a 1 2 x 2 + a 1 3 x 3 + … + a 1 n x n a 2 1 x 1 + a 2 2 x 2 + a 2 3 x 3 + … + a 2 n x n ⋮ a m 1 x 1 + a m 2 x 2 + a m 3 x 3 + … + a m n x n = b 1 = b 2 = b m
Définir un algorithme qui fonctionne toujours :
“ { a i j } + { b j } " ⟹ { 0 solution ? 1 solution ? ∞ solutions ? \text{\textquotedblleft}\{a_{ij}\} + \{b_{j}\}" \implies \begin{cases} 0 &\text{solution ?}\\ 1 &\text{solution ?}\\ \infty &\text{solutions ?} \end{cases} “ { a i j } + { b j } " ⟹ ⎩ ⎪ ⎪ ⎨ ⎪ ⎪ ⎧ 0 1 ∞ solution ? solution ? solutions ?
Les systèmes "triangulaires" sont très simples à résoudre (même si m m m et n n n sont grands). Par exemple :
{ x 1 − x 2 + 2 x 3 = 4 L 1 x 2 − 3 x 3 = − 5 L 2 5 x 3 = 10 L 3 \begin{cases} \begin{alignedat}{2} x_1-x_2+2x_3 &=4 \qquad && L_1 \\ x_2-3x_3 &=-5 && L_2\\ 5x_3&=10 && L_3\\ \end{alignedat} \end{cases} ⎩ ⎪ ⎪ ⎨ ⎪ ⎪ ⎧ x 1 − x 2 + 2 x 3 x 2 − 3 x 3 5 x 3 = 4 = − 5 = 1 0 L 1 L 2 L 3
De L 3 L_3 L 3 , on tire : x 3 x_3 x 3 = 2 → \rightarrow → Injecte dans L 2 L_2 L 2 : x 2 = − 5 + 3 x 3 = 1 x_2 = -5 + 3x_3 = 1 x 2 = − 5 + 3 x 3 = 1 → \rightarrow → x 1 = 4 + x 2 − 2 x 3 = 1 x_1 = 4+x_2-2x_3 =1 x 1 = 4 + x 2 − 2 x 3 = 1 . → \rightarrow → Unique solution : ( x 1 , x 2 , x 3 ) = ( 1 , 1 , 2 ) (x_1,x_2,x_3) = (1,1,2) ( x 1 , x 2 , x 3 ) = ( 1 , 1 , 2 ) .
Pour le cas général, on essaiera de se ramener à un système aussi "triangulaire que possible".
Deux systèmes m × n m\times n m × n , ( ∗ ) (*) ( ∗ ) et ( ∗ ) ′ (*)' ( ∗ ) ′ , sont dits équivalents s'ils possèdent le même ensemble de solutions.
Un système ( ∗ ) ~ \tilde{(*)} ( ∗ ) ~ est obtenu à partir d'un système ( ∗ ) (*) ( ∗ ) par une transformation élémentaire :
de Type I si ( ∗ ) ~ \tilde{(*)} ( ∗ ) ~ s'obtient à partir de ( ∗ ) (*) ( ∗ ) en échangeant deux lignes.
Notation : si on échange la ligne i i i avec la ligne j j j L i ⟷ L j \boxed{L_i \longleftrightarrow L_j } L i ⟷ L j
de Type II si ( ∗ ) ~ \tilde{(*)} ( ∗ ) ~ est obtenu à partir de ( ∗ ) (*) ( ∗ ) en multipliant une ligne de ( ∗ ) (*) ( ∗ ) par un scalaire (une constante sans dimensions) non-nul .
Notation : si on multiplie la ligne i i i par λ ∈ R \lambda \in \mathbb{R} λ ∈ R L i ← λ L i \boxed{L_i\leftarrow \lambda L_i} L i ← λ L i
de Type III si ( ∗ ) ~ \tilde{(*)} ( ∗ ) ~ est obtenu à partir de ( ∗ ) (*) ( ∗ ) en remplaçant une ligne de ( ∗ ) (*) ( ∗ ) par elles-même plus un multiple d'une autre ligne. non-nul .
Notation : L i ← L i + λ L j \boxed{L_i\leftarrow L_i + \lambda L_j} L i ← L i + λ L j
Si ( ∗ ) ′ (*)' ( ∗ ) ′ est obtenu à partir de ( ∗ ) (*) ( ∗ ) par un suite finie de transformations élémentaires, alors ( ∗ ) ′ (*)' ( ∗ ) ′ et ( ∗ ) (*) ( ∗ ) sont éqivalents.
( ∗ ) { 2 x 1 − 3 x 2 + 5 x 3 = 8 x 1 + x 2 − 3 x 3 = − 7 4 x 1 + 2 x 2 + 2 x 3 = 0 ↓ ( L 1 ⟷ L 2 ) { x 1 + x 2 − 3 x 3 = − 7 2 x 1 − 3 x 2 + 5 x 3 = 8 4 x 1 + 2 x 2 + 2 x 3 = 0 ↓ ( L 3 ← 1 2 L 3 ) { x 1 + x 2 − 3 x 3 = − 7 2 x 1 − 3 x 2 + 5 x 3 = 8 2 x 1 + x 2 + x 3 = 0 ↓ ( L 2 ← L 2 − 2 L 1 ) { x 1 + x 2 − 3 x 3 = − 7 − 5 x 2 + 11 x 3 = 22 2 x 1 + x 2 + x 3 = 0 ↓ ( L 2 ← L 3 − 2 L 1 ) { x 1 + x 2 − 3 x 3 = − 7 − 5 x 2 + 11 x 3 = 22 − x 2 + 7 x 3 = 14 ↓ ( L 2 ⟷ L 3 ) { x 1 + x 2 − 3 x 3 = − 7 − x 2 + 7 x 3 = 14 − 5 x 2 + 11 x 3 = 22 ↓ ( L 2 ← L 3 − 5 L 2 ) ( ∗ ) ′ { x 1 + x 2 − 3 x 3 = − 7 − x 2 + 7 x 3 = 14 − 5 x 2 + 11 x 3 = 22 \begin{array}{rcl} (*)&\begin{cases} \begin{alignedat}{2} 2x_1&-3x_2&+5x_3 &=8 \\ x_1&+x_2&-3x_3 &=-7\\ 4x_1&+2x_2&+2x_3&=0 \\ \end{alignedat} \end{cases}&\\ & & \darr (L_1 \longleftrightarrow L_2)\\ &\begin{cases} \begin{alignedat}{2} x_1&+x_2&-3x_3 &=-7 \\ 2x_1&-3x_2&+5x_3 &=8\\ 4x_1&+2x_2&+2x_3&=0 \\ \end{alignedat} \end{cases}&\\ & & \darr (L_3 \leftarrow \frac{1}{2} L_3)\\ &\begin{cases} \begin{alignedat}{2} x_1&+x_2&-3x_3 &=-7 \\ 2x_1&-3x_2&+5x_3 &=8\\ 2x_1&+x_2&+x_3&=0 \\ \end{alignedat} \end{cases}&\\ & & \darr (L_2 \leftarrow L_2 - 2L_1)\\ &\begin{cases} \begin{alignedat}{2} x_1&+x_2&-3x_3 &=-7 \\ &-5x_2&+11x_3 &=22\\ 2x_1&+x_2&+x_3&=0 \\ \end{alignedat} \end{cases}&\\ & & \darr (L_2 \leftarrow L_3 - 2L_1)\\ &\begin{cases} \begin{alignedat}{2} x_1&+x_2&-3x_3 &=-7 \\ &-5x_2&+11x_3 &=22\\ &-x_2&+7x_3&=14 \\ \end{alignedat} \end{cases}&\\ & & \darr (L_2 \longleftrightarrow L_3)\\ &\begin{cases} \begin{alignedat}{2} x_1&+x_2&-3x_3 &=-7 \\ &-x_2&+7x_3&=14 \\ &-5x_2&+11x_3 &=22\\ \end{alignedat} \end{cases}&\\ & & \darr (L_2 \leftarrow L_3-5L_2)\\ (*)'&\begin{cases} \begin{alignedat}{2} x_1&+x_2&-3x_3 &=-7 \\ &-x_2&+7x_3&=14 \\ &-5x_2&+11x_3 &=22\\ \end{alignedat} \end{cases}& \end{array} ( ∗ ) ( ∗ ) ′ ⎩ ⎪ ⎪ ⎨ ⎪ ⎪ ⎧ 2 x 1 x 1 4 x 1 − 3 x 2 + x 2 + 2 x 2 + 5 x 3 − 3 x 3 + 2 x 3 = 8 = − 7 = 0 ⎩ ⎪ ⎪ ⎨ ⎪ ⎪ ⎧ x 1 2 x 1 4 x 1 + x 2 − 3 x 2 + 2 x 2 − 3 x 3 + 5 x 3 + 2 x 3 = − 7 = 8 = 0 ⎩ ⎪ ⎪ ⎨ ⎪ ⎪ ⎧ x 1 2 x 1 2 x 1 + x 2 − 3 x 2 + x 2 − 3 x 3 + 5 x 3 + x 3 = − 7 = 8 = 0 ⎩ ⎪ ⎪ ⎨ ⎪ ⎪ ⎧ x 1 2 x 1 + x 2 − 5 x 2 + x 2 − 3 x 3 + 1 1 x 3 + x 3 = − 7 = 2 2 = 0 ⎩ ⎪ ⎪ ⎨ ⎪ ⎪ ⎧ x 1 + x 2 − 5 x 2 − x 2 − 3 x 3 + 1 1 x 3 + 7 x 3 = − 7 = 2 2 = 1 4 ⎩ ⎪ ⎪ ⎨ ⎪ ⎪ ⎧ x 1 + x 2 − x 2 − 5 x 2 − 3 x 3 + 7 x 3 + 1 1 x 3 = − 7 = 1 4 = 2 2 ⎩ ⎪ ⎪ ⎨ ⎪ ⎪ ⎧ x 1 + x 2 − x 2 − 5 x 2 − 3 x 3 + 7 x 3 + 1 1 x 3 = − 7 = 1 4 = 2 2 ↓ ( L 1 ⟷ L 2 ) ↓ ( L 3 ← 2 1 L 3 ) ↓ ( L 2 ← L 2 − 2 L 1 ) ↓ ( L 2 ← L 3 − 2 L 1 ) ↓ ( L 2 ⟷ L 3 ) ↓ ( L 2 ← L 3 − 5 L 2 )
En procédant comme avant, on trouve l'unique solution: ( − 1 , 0 , 2 ) ← (-1,0,2)\leftarrow ( − 1 , 0 , 2 ) ← solution de ( ∗ ) ′ (*)' ( ∗ ) ′ . Par la propostion, c'est également la solution de ( ∗ ) (*) ( ∗ ) .
{ x 1 + x 2 − 2 x 3 = 1 − 2 x 1 + x 2 + x 3 = 4 ↓ ( L 1 ← L 2 + 2 L 1 ) { x 1 + x 2 − 2 x 3 = 1 3 x 2 − 3 x 3 = 6 ↓ ( L 1 ← L 2 3 ) { x 1 + x 2 − 2 x 3 = 1 x 2 − x 3 = 2 ↓ ( L 1 ← L 1 + 2 x 3 ) ( L 2 ← L 2 + x 3 ) { x 1 + x 2 = 1 + 2 x 3 x 2 = 2 + x 3 \begin{array}{ll} \begin{cases} \begin{alignedat}{3} x_1&+x_2&-2x_3 &=1 \\ -2x_1&+x_2&+x_3 &=4\\ \end{alignedat} \end{cases}&\\ &\darr (L_1 \leftarrow L_2+2L_1)\\ \begin{cases} \begin{alignedat}{3} x_1&+x_2&-2x_3 &=1 \\ & 3x_2&-3x_3 &=6\\ \end{alignedat} \end{cases}&\\ &\darr (L_1 \leftarrow \frac{L_2}{3})\\ \begin{cases} \begin{alignedat}{3} x_1&+x_2&-2x_3 &=1 \\ &x_2&-x_3 &=2\\ \end{alignedat} \end{cases}&\\ &\darr \begin{array}{l} (L_1 \leftarrow L_1 + 2x_3)\\ (L_2 \leftarrow L_2 + x_3) \end{array}\\ \begin{cases} \begin{alignedat}{3} x_1&+x_2 &=1 &+2x_3 \\ &x_2&=2 &+x_3 \\ \end{alignedat} \end{cases} \end{array} { x 1 − 2 x 1 + x 2 + x 2 − 2 x 3 + x 3 = 1 = 4 { x 1 + x 2 3 x 2 − 2 x 3 − 3 x 3 = 1 = 6 { x 1 + x 2 x 2 − 2 x 3 − x 3 = 1 = 2 { x 1 + x 2 x 2 = 1 = 2 + 2 x 3 + x 3 ↓ ( L 1 ← L 2 + 2 L 1 ) ↓ ( L 1 ← 3 L 2 ) ↓ ( L 1 ← L 1 + 2 x 3 ) ( L 2 ← L 2 + x 3 )
On remarque qu'on peut faire un choix : on peut choisir x 3 x_3 x 3 , puis résoudre un système en {}x 1 x_1 x 1 ,x 2 x_2 x 2 , où x 1 x_1 x 1 et x 2 x_2 x 2 vont dépendre de x 3 x_3 x 3 .
On appelle x 3 x_3 x 3 une variable libre (ou "paramètre").
Notation : si x 3 x_3 x 3 = t ∈ R \in \mathbb{R} ∈ R , toute solution de ( ∗ ) (*) ( ∗ ) est de la forme ( x 1 , x 2 , x 3 ) (x_1,x_2,x_3) ( x 1 , x 2 , x 3 ) , où
x 1 = − 1 + t x 2 = 2 + t x 3 = t \boxed{\begin{aligned} x_1 & = -1 + t \\ x_2 & = 2 + t \\ x_3 & = t \end{aligned}} x 1 x 2 x 3 = − 1 + t = 2 + t = t
( ∗ ) { a 11 x 1 + a 12 x 2 + a 13 x 3 + … + a 1 n x n = b 1 a 21 x 1 + a 22 x 2 + a 23 x 3 + … + a 2 n x n = b 2 ⋮ a m 1 x 1 + a m 2 x 2 + a m 3 x 3 + … + a m n x n = b m (*) \begin{cases} a_{11}x_1+a_{12}x_2+a_{13}x_3+\ldots+a_{1n}x_n &= b_1 \\ a_{21}x_1+a_{22}x_2+a_{23}x_3+\ldots+a_{2n}x_n &= b_2 \\ \vdots \\ a_{m1}x_1+a_{m2}x_2+a_{m3}x_3+\ldots+a_{mn}x_n &= b_m \\ \end{cases} ( ∗ ) ⎩ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎧ a 1 1 x 1 + a 1 2 x 2 + a 1 3 x 3 + … + a 1 n x n a 2 1 x 1 + a 2 2 x 2 + a 2 3 x 3 + … + a 2 n x n ⋮ a m 1 x 1 + a m 2 x 2 + a m 3 x 3 + … + a m n x n = b 1 = b 2 = b m
j i [ a 11 ⋯ a 1 n ⋮ a i j ⋮ a m 1 ⋯ a m n ] tableau m × n \begin{array}{cc} & \color{blue}j \\ \color{orange}i & \begin{bmatrix} a_{11} & \cdots & a_{1n} \\ \vdots & a_{\color{orange}i\color{blue}j} & \vdots \\ a_{m1} & \cdots & a_{mn} \end{bmatrix} \end{array} \quad\text{tableau $m \times n$} i j ⎣ ⎢ ⎢ ⎡ a 1 1 ⋮ a m 1 ⋯ a i j ⋯ a 1 n ⋮ a m n ⎦ ⎥ ⎥ ⎤ tableau m × n
[ a 11 ⋯ a 1 n b 1 ⋮ ⋮ ⋮ a m 1 ⋯ a m n b m ] tableau m × ( n + 1 ) \left[\begin{array}{ccc:c} a_{11}&\cdots&a_{1n}&b_{1} \\ \vdots & &\vdots&\vdots \\ a_{m1}&\cdots&a_{mn}&b_{m} \\ \end{array}\right] \quad\text{tableau $m \times (n+1)$} ⎣ ⎢ ⎢ ⎡ a 1 1 ⋮ a m 1 ⋯ ⋯ a 1 n ⋮ a m n b 1 ⋮ b m ⎦ ⎥ ⎥ ⎤ tableau m × ( n + 1 )
Le coefficient principal d'une ligne (non-nulle) est le premier coeficient a i j a_{ij} a i j non-nul rencontré en partant depuis la gauche.
Une matrice est échalonnée si
toutes les lignes nulles sont tout en bas,
sur chaque ligne non-nulle, le coefficient principal est strictement à droite du coefficient princpal de laligne du dessus.
( 1 2 3 0 4 5 0 6 7 ) ← n’est pas e ˊ chelonn e ˊ e \begin{pmatrix} \color{blue}1 & 2 & 3 \\ 0 & \color{blue}4 & 5 \\ 0 & \color{blue}6 & 7 \end{pmatrix} \text{$\leftarrow$ n'est pas échelonnée} ⎝ ⎜ ⎛ 1 0 0 2 4 6 3 5 7 ⎠ ⎟ ⎞ ← n’est pas e ˊ chelonn e ˊ e
( 3 1 2 0 7 0 0 4 3 1 0 0 0 0 0 ) ← est e ˊ chelonn e ˊ e \begin{pmatrix} \color{blue}3 & 1 & 2 & 0 & 7 \\ 0 & 0 & \color{blue}4 & 3 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ \end{pmatrix} \text{$\leftarrow$est échelonnée}\\ ⎝ ⎜ ⎛ 3 0 0 1 0 0 2 4 0 0 3 0 7 1 0 ⎠ ⎟ ⎞ ← est e ˊ chelonn e ˊ e
Les coefficients principaux sont en bleu.
Une matrice est échelonnée réduite si elle est échelonnée, et si de plus
( 1 9 0 4 0 0 17 0 0 1 2 0 0 9 0 0 0 0 1 0 2 0 0 0 0 0 1 0 ) ← est e ˊ chelonn e ˊ e r e ˊ duite \begin{pmatrix} \color{blue}1 & 9 & 0 & 4 & 0 & 0 & 17 \\ 0 & 0 & \color{blue}1 & 2 & 0 & 0 & 9 \\ 0 & 0 & 0 & 0 & \color{blue}1 & 0 & 2 \\ 0 & 0 & 0 & 0 & 0 & \color{blue}1 & 0 \end{pmatrix} \text{$\leftarrow$ est échelonnée réduite} ⎝ ⎜ ⎜ ⎜ ⎛ 1 0 0 0 9 0 0 0 0 1 0 0 4 2 0 0 0 0 1 0 0 0 0 1 1 7 9 2 0 ⎠ ⎟ ⎟ ⎟ ⎞ ← est e ˊ chelonn e ˊ e r e ˊ duite
Toute matrice m × n m \times n m × n peut se transformer en vue matrice échelonnée , à l'aide d'une suite finie d'opérations élémentaires. (Le résultat peut dépendre du choix des opérations.)
Toute matrice m \times n peut se transformer en vue matrice échelonnée réduite , à l'aide d'une suite finie d'opérations élémentaires. (Le résultat ne dépend pas du choix des opérations.)
( ∗ ) { 3 x 1 − 3 x 2 − 2 x 3 = − 1 4 x 1 − x 2 + 3 x 3 = − 1 x 1 + 2 x 2 + 2 x 3 = 3 ↓ (matrice augment e ˊ e) M = [ 3 − 3 − 2 − 1 4 − 1 3 − 1 1 2 2 3 ] ↓ (comme avant) [ 1 2 2 3 0 − 9 − 5 − 13 0 0 − 3 3 ] C’est une version e ˊ chelonn e ˊ e. ↓ L 3 ← L 3 − 3 [ 1 2 2 3 0 − 9 − 5 − 13 0 0 1 − 1 ] ↓ L 2 ← L 2 + 5 L 3 [ 1 2 2 3 0 − 9 0 − 18 0 0 1 − 1 ] ↓ L 2 ← L 2 − 9 [ 1 2 2 3 0 1 0 2 0 0 1 − 1 ] ↓ L 1 ← L 1 − 2 L 3 [ 1 2 0 5 0 1 0 2 0 0 1 − 1 ] ↓ L 1 ← L 1 − 2 L 2 [ 1 0 0 1 0 1 0 2 0 0 1 − 1 ] C’est la r e ˊ duite de M ↓ L 1 ← L 1 − 2 L 2 ( ∗ ) ′ { x 1 = 1 x 2 = 2 x 3 = − 1 \begin{array}{rll} (*)&\begin{cases} \begin{alignedat}{2} 3x_1&-3x_2&-2x_3 &=-1 \\ 4x_1&-x_2&+3x_3 &=-1\\ x_1&+2x_2&+2x_3&=3 \\ \end{alignedat} \end{cases}&\\ & &\downarrow \text {(matrice augmentée)}\\ M = & \left[\begin{array}{rrr:r} 3 &-3 &-2 &-1 \\ 4 &-1 & 3 &-1 \\ 1 & 2 & 2 & 3 \\ \end{array}\right]&\\ & & \downarrow \text{(comme avant)}\\ & \left[\begin{array}{rrr:r} 1 & 2 & 2 &3 \\ 0 &-9 &-5 &-13 \\ 0 & 0 & -3 & 3 \\ \end{array}\right] &\text{C'est \textbf{une} version échelonnée.}\\ & & \downarrow L_3 \leftarrow \frac{L_3}{-3}\\ & \left[\begin{array}{rrr:r} 1 & 2 & 2 &3 \\ 0 &-9 &-5 &-13 \\ 0 & 0 & 1 & -1 \\ \end{array}\right] &\\ & & \downarrow L_2 \leftarrow L_2 + 5L_3\\ & \left[\begin{array}{rrr:r} 1 & 2 & 2 &3 \\ 0 &-9 & 0 &-18 \\ 0 & 0 & 1 & -1 \\ \end{array}\right] &\\ & & \downarrow L_2 \leftarrow \frac{L_2}{-9}\\ & \left[\begin{array}{rrr:r} 1 & 2 & 2 & 3 \\ 0 & 1 & 0 & 2 \\ 0 & 0 & 1 & -1 \\ \end{array}\right] &\\ & & \downarrow L_1 \leftarrow L_1-2L_3\\ & \left[\begin{array}{rrr:r} 1 & 2 & 0 & 5 \\ 0 & 1 & 0 & 2 \\ 0 & 0 & 1 & -1 \\ \end{array}\right] &\\ & & \downarrow L_1 \leftarrow L_1-2L_2\\ & \left[\begin{array}{rrr:r} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 2 \\ 0 & 0 & 1 & -1 \\ \end{array}\right] & \text{C'est \textbf{la} réduite de M}\\ & & \downarrow L_1 \leftarrow L_1-2L_2\\ (*)'&\begin{cases} \begin{alignedat}{3} x_1& & &=1 \\ &x_2& &=2\\ & &x_3&=-1 \\ \end{alignedat} \end{cases}& \end{array} ( ∗ ) M = ( ∗ ) ′ ⎩ ⎪ ⎪ ⎨ ⎪ ⎪ ⎧ 3 x 1 4 x 1 x 1 − 3 x 2 − x 2 + 2 x 2 − 2 x 3 + 3 x 3 + 2 x 3 = − 1 = − 1 = 3 ⎣ ⎢ ⎡ 3 4 1 − 3 − 1 2 − 2 3 2 − 1 − 1 3 ⎦ ⎥ ⎤ ⎣ ⎢ ⎡ 1 0 0 2 − 9 0 2 − 5 − 3 3 − 1 3 3 ⎦ ⎥ ⎤ ⎣ ⎢ ⎡ 1 0 0 2 − 9 0 2 − 5 1 3 − 1 3 − 1 ⎦ ⎥ ⎤ ⎣ ⎢ ⎡ 1 0 0 2 − 9 0 2 0 1 3 − 1 8 − 1 ⎦ ⎥ ⎤ ⎣ ⎢ ⎡ 1 0 0 2 1 0 2 0 1 3 2 − 1 ⎦ ⎥ ⎤ ⎣ ⎢ ⎡ 1 0 0 2 1 0 0 0 1 5 2 − 1 ⎦ ⎥ ⎤ ⎣ ⎢ ⎡ 1 0 0 0 1 0 0 0 1 1 2 − 1 ⎦ ⎥ ⎤ ⎩ ⎪ ⎪ ⎨ ⎪ ⎪ ⎧ x 1 x 2 x 3 = 1 = 2 = − 1 ↓ (matrice augment e ˊ e) ↓ (comme avant) C’est une version e ˊ chelonn e ˊ e. ↓ L 3 ← − 3 L 3 ↓ L 2 ← L 2 + 5 L 3 ↓ L 2 ← − 9 L 2 ↓ L 1 ← L 1 − 2 L 3 ↓ L 1 ← L 1 − 2 L 2 C’est la r e ˊ duite de M ↓ L 1 ← L 1 − 2 L 2
( ∗ ) { x 1 + x 2 = 5 2 x 1 + 2 x 2 = 11 ↓ (matrice augment e ˊ e) [ 1 1 5 2 2 11 ] ↓ (r e ˊ duction) [ 1 1 5 0 0 1 ] ↓ (syst e ˋ me d’ e ˊ quations) ( ∗ ) { x 1 + x 2 = 5 0 x 1 + 0 x 2 = 1 \begin{array}{rll} (*)&\begin{cases} \begin{alignedat}{2} x_1&+x_2 &= 5 \\ 2x_1&+2x_2 &= 11 \\ \end{alignedat} \end{cases}&\\ & &\downarrow \text {(matrice augmentée)}\\ & \left[\begin{array}{cc:c} 1 & 1 & 5 \\ 2 & 2 & 11 \\ \end{array}\right]&\\ & &\downarrow \text {(réduction)}\\ & \left[\begin{array}{cc:c} 1 & 1 & 5 \\ 0 & 0 & 1 \\ \end{array}\right]&\\ & &\downarrow \text {(système d'équations)}\\ (*)&\begin{cases} \begin{alignedat}{2} x_1&+x_2 &= 5 \\ 0x_1&+0x_2 &= 1 \\ \end{alignedat} \end{cases}&\\ \end{array} ( ∗ ) ( ∗ ) { x 1 2 x 1 + x 2 + 2 x 2 = 5 = 1 1 [ 1 2 1 2 5 1 1 ] [ 1 0 1 0 5 1 ] { x 1 0 x 1 + x 2 + 0 x 2 = 5 = 1 ↓ (matrice augment e ˊ e) ↓ (r e ˊ duction) ↓ (syst e ˋ me d’ e ˊ quations)
( ∗ ) ′ (*)' ( ∗ ) ′ n'as pas de solution, donc ( ∗ ) (*) ( ∗ ) n'en a pas non plus.
[ 0 3 − 6 6 4 − 5 3 − 7 8 − 5 8 9 3 − 9 12 − 9 6 15 ] ↓ (r e ˊ duction a ˋ faire en exercice) [ 1 0 − 2 3 0 − 24 0 1 − 2 2 0 − 7 0 0 0 0 1 4 ] ↓ (syst e ˋ me d’ e ˊ quaitons) { x 1 − x 3 + 3 x 4 = − 24 x 2 − 2 x 3 + 2 x 4 = − 7 x 5 = 4 ↓ { x 1 = − 24 + x 3 − 3 x 4 x 2 = − 7 + 2 x 3 − 2 x 4 x 5 = 4 \begin{array}{ll} \left[\begin{array}{rrrrr:r} 0 & 3 & -6 & 6 & 4 &-5 \\ 3 & -7 & 8 & -5 & 8 & 9 \\ 3 & -9 & 12 & -9 & 6 &15 \\ \end{array}\right]&\\ &\downarrow \text {(réduction à faire en exercice)}\\ \left[\begin{array}{rrrrr:r} 1 & 0 & -2 & 3 & 0 &-24 \\ 0 & 1 & -2 & 2 & 0 & -7 \\ 0 & 0 & 0 & 0 & 1 &4 \\ \end{array}\right]&\\ &\downarrow \text {(système d'équaitons)}\\ \begin{cases} \begin{alignedat}{5} x_1& &-x_3 &+3x_4 & &= -24 \\ & x_2 &-2x_3 &+2x_4 & &= -7 \\ & & & & x_5 & = 4 \end{alignedat} \end{cases}&\\ &\downarrow \text {}\\ \begin{cases} \begin{alignedat}{3} x_1&= -24 &+x_3 &-3x_4\\ x_2 &= -7 & +2x_3 &-2x_4 \\ x_5 & = 4 \end{alignedat} \end{cases}& \end{array} ⎣ ⎢ ⎡ 0 3 3 3 − 7 − 9 − 6 8 1 2 6 − 5 − 9 4 8 6 − 5 9 1 5 ⎦ ⎥ ⎤ ⎣ ⎢ ⎡ 1 0 0 0 1 0 − 2 − 2 0 3 2 0 0 0 1 − 2 4 − 7 4 ⎦ ⎥ ⎤ ⎩ ⎪ ⎪ ⎨ ⎪ ⎪ ⎧ x 1 x 2 − x 3 − 2 x 3 + 3 x 4 + 2 x 4 x 5 = − 2 4 = − 7 = 4 ⎩ ⎪ ⎪ ⎨ ⎪ ⎪ ⎧ x 1 x 2 x 5 = − 2 4 = − 7 = 4 + x 3 + 2 x 3 − 3 x 4 − 2 x 4 ↓ (r e ˊ duction a ˋ faire en exercice) ↓ (syst e ˋ me d’ e ˊ quaitons) ↓
⟹ x 3 , x 4 \implies x_3, x_4 ⟹ x 3 , x 4 sont libres et les autres sont liées (à x 3 x_3 x 3 et x 4 x_4 x 4 )