\( %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Mes commandes %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\multirows}[3]{\multirow{#1}{#2}{$#3$}}%pour rester en mode math \renewcommand{\arraystretch}{1.3}%pour augmenter la taille des case \newcommand{\point}[1]{\marginnote{\small\vspace*{-1em} #1}}%pour indiquer les points ou le temps \newcommand{\dpl}[1]{\displaystyle{#1}}%megamode \newcommand{\A}{\mathscr{A}} \newcommand{\LN}{\mathscr{N}} \newcommand{\LL}{\mathscr{L}} \newcommand{\K}{\mathbb{K}} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\M}{\mathcal{M}} \newcommand{\D}{\mathbb{D}} \newcommand{\E}{\mathcal{E}} \renewcommand{\P}{\mathcal{P}} \newcommand{\G}{\mathcal{G}} \newcommand{\Kk}{\mathcal{K}} \newcommand{\Cc}{\mathcal{C}} \newcommand{\Zz}{\mathcal{Z}} \newcommand{\Ss}{\mathcal{S}} \newcommand{\B}{\mathbb{B}} \newcommand{\inde}{\bot\!\!\!\bot} \newcommand{\Proba}{\mathbb{P}} \newcommand{\Esp}[1]{\dpl{\mathbb{E}\left(#1\right)}} \newcommand{\Var}[1]{\dpl{\mathbb{V}\left(#1\right)}} \newcommand{\Cov}[1]{\dpl{Cov\left(#1\right)}} \newcommand{\base}{\mathcal{B}} \newcommand{\Som}{\textbf{Som}} \newcommand{\Chain}{\textbf{Chain}} \newcommand{\Ar}{\textbf{Ar}} \newcommand{\Arc}{\textbf{Arc}} \newcommand{\Min}{\text{Min}} \newcommand{\Max}{\text{Max}} \newcommand{\Ker}{\text{Ker}} \renewcommand{\Im}{\text{Im}} \newcommand{\Sup}{\text{Sup}} \newcommand{\Inf}{\text{Inf}} \renewcommand{\det}{\texttt{det}} \newcommand{\GL}{\text{GL}} \newcommand{\crossmark}{\text{\ding{55}}} \renewcommand{\checkmark}{\text{\ding{51}}} \newcommand{\Card}{\sharp} \newcommand{\Surligne}[2]{\text{\colorbox{#1}{ #2 }}} \newcommand{\SurligneMM}[2]{\text{\colorbox{#1}{ #2 }}} \newcommand{\norm}[1]{\left\lVert#1\right\rVert} \renewcommand{\lim}[1]{\underset{#1}{lim}\,} \newcommand{\nonor}[1]{\left|#1\right|} \newcommand{\Un}{1\!\!1} \newcommand{\sepon}{\setlength{\columnseprule}{0.5pt}} \newcommand{\sepoff}{\setlength{\columnseprule}{0pt}} \newcommand{\flux}{Flux} \newcommand{\Cpp}{\texttt{C++\ }} \newcommand{\Python}{\texttt{Python\ }} %\newcommand{\comb}[2]{\begin{pmatrix} #1\\ #2\end{pmatrix}} \newcommand{\comb}[2]{C_{#1}^{#2}} \newcommand{\arrang}[2]{A_{#1}^{#2}} \newcommand{\supp}[1]{Supp\left(#1\right)} \newcommand{\BB}{\mathcal{B}} \newcommand{\arc}[1]{\overset{\rotatebox{90}{)}}{#1}} \newcommand{\modpi}{\equiv_{2\pi}} \renewcommand{\Re}{Re} \renewcommand{\Im}{Im} \renewcommand{\bar}[1]{\overline{#1}} \newcommand{\mat}{\mathcal{M}} \newcommand{\und}[1]{{\mathbf{\color{red}\underline{#1}}}} \newcommand{\rdots}{\text{\reflectbox{$\ddots$}}} \newcommand{\Compa}{Compa} \newcommand{\dint}{\dpl{\int}} \newcommand{\intEFF}[2]{\left[\!\left[#1 ; #2\right]\!\right]} \newcommand{\intEFO}[2]{\left[\!\left[#1 ; #2\right[\!\right[} \newcommand{\intEOF}[2]{\left]\!\left]#1 ; #2\right]\!\right]} \newcommand{\intEOO}[2]{\left]\!\left]#1 ; #2\right[\!\right[} \newcommand{\ou}{\vee} \newcommand{\et}{\wedge} \newcommand{\non}{\neg} \newcommand{\implique}{\Rightarrow} \newcommand{\equivalent}{\Leftrightarrow} \newcommand{\Ab}{\overline{A}} \newcommand{\Bb}{\overline{B}} \newcommand{\Cb}{\overline{C}} \newcommand{\Cl}{\texttt{Cl}} \newcommand{\ab}{\overline{a}} \newcommand{\bb}{\overline{b}} \newcommand{\cb}{\overline{c}} \newcommand{\Rel}{\mathcal{R}} \newcommand{\superepsilon}{\varepsilon\!\!\varepsilon} \newcommand{\supere}{e\!\!e} \makeatletter \newenvironment{console}{\noindent\color{white}\begin{lrbox}{\@tempboxa}\begin{minipage}{\columnwidth} \ttfamily \bfseries\vspace*{0.5cm}} {\vspace*{0.5cm}\end{minipage}\end{lrbox}\colorbox{black}{\usebox{\@tempboxa}} } \makeatother \def\ie{\textit{i.e. }} \def\cf{\textit{c.f. }} \def\vide{ { $ {\text{ }} $ } } %Commande pour les vecteurs \newcommand{\grad}{\overrightarrow{Grad}} \newcommand{\Vv}{\overrightarrow{v}} \newcommand{\Vu}{\overrightarrow{u}} \newcommand{\Vw}{\overrightarrow{w}} \newcommand{\Vup}{\overrightarrow{u'}} \newcommand{\Zero}{\overrightarrow{0}} \newcommand{\Vx}{\overrightarrow{x}} \newcommand{\Vy}{\overrightarrow{y}} \newcommand{\Vz}{\overrightarrow{z}} \newcommand{\Vt}{\overrightarrow{t}} \newcommand{\Va}{\overrightarrow{a}} \newcommand{\Vb}{\overrightarrow{b}} \newcommand{\Vc}{\overrightarrow{c}} \newcommand{\Vd}{\overrightarrow{d}} \newcommand{\Ve}[1]{\overrightarrow{e_{#1}}} \newcommand{\Vf}[1]{\overrightarrow{f_{#1}}} \newcommand{\Vn}{\overrightarrow{0}} \newcommand{\Mat}{Mat} \newcommand{\Pass}{Pass} \newcommand{\mkF}{\mathfrak{F}} \renewcommand{\sp}{Sp} \newcommand{\Co}{Co} \newcommand{\vect}[1]{\texttt{Vect}\dpl{\left( #1\right)}} \newcommand{\prodscal}[2]{\dpl{\left\langle #1\left|\vphantom{#1 #2}\right. #2\right\rangle}} \newcommand{\trans}[1]{{\vphantom{#1}}^{t}{#1}} \newcommand{\ortho}[1]{{#1}^{\bot}} \newcommand{\oplusbot}{\overset{\bot}{\oplus}} \SelectTips{cm}{12}%Change le bout des flèches dans un xymatrix \newcommand{\pourDES}[8]{ \begin{itemize} \item Pour la ligne : le premier et dernier caractère forment $#1#2$ soit $#4$ en base 10. \item Pour la colonne : les autres caractères du bloc forment $#3$ soit $#5$ en base 10. \item A l'intersection de la ligne $#4+1$ et de la colonne $#5+1$ de $S_{#8}$ se trouve l'entier $#6$ qui, codé sur $4$ bits, est \textbf{\texttt{$#7$}}. \end{itemize} } \)

Si l'on reprend le problème précédent, nous avions fait naitre un système \[\left\{ \begin{array}{rcl} t+c&=&1000\\ t&=&10+c \end{array} \right.\] Assez souvent en mathématique, on cherche à résoudre des équations. Lorsqu'on est confronté à résoudre plusieurs équations simultanément on parle de système de plusieurs équations à plusieurs inconnues. Dans notre exemple nous avions un système de deux équations à deux inconnues. Il est d'accoutumé en mathématique d'aligner les variables. Ainsi on préférera écrire le système précédent de la manière suivante : \[\left\{ \begin{array}{rcl} t+c&=&1000\\ t-c&=&10 \end{array} \right.\]

Définition


Un système linéaire réel de \( n\) équations à \( p\) inconnues est la donnée de :
\( \bullet\)
des variables, communément noté \( x_j\) pour \( j\in \{1, \ldots, p\}\) ,

\( \bullet\)
des \( a_{i, j}\in \R\) pour \( i\in \{1, \ldots n\}\) et \( j\in \{1, \ldots, p\}\) ,

\( \bullet\)
des \( b_i\in \R\) pour \( i\in \{1, \ldots n\}\) ,
tel que pour tout \( i\in \{1, \ldots n\}\) , \[\sum_{j=1}^pa_{i, j}x_j=b_i\]
Le cœur de notre cours sera de se donner des outils qui permettent de résoudre les systèmes linéaires1. Nous en avons rappeler un.

La substitution

La méthode de la substitution, comme son nom l'indique, consiste à substituer une variable par les autres. Prenons un exemple un peu plus sophistiqué et considérons le système suivant \[ \left\{ \begin{array}{ccccccl} x&+&y&+&z&=&3\\ &&y&-&z&=&0\\ x&+&y&-&z&=&1 \end{array} \right. \]
Première méthode.
On peut, dans la seconde ligne, extraire l'information : \( y=z\) . On peut alors substituer \( z\) par \( y\) dans la troisième ligne pour arriver à \( x+y-y=1\) soit \( x=1\) . Puisque \( x=1\) et \( y=z\) , on peut se rabattre sur la première ligne et obtenir \( 1+y+y=3\) soit \( y=1\) et donc \( z=1\) .

Seconde méthode.
On peut dans la dernière ligne substituer \( z=x+y-1\) et substituer dans la seconde ligne pour arriver à \( y-(x+y-1)=0\) soit \( -x+1=0\) et donc \( x=1\) . Avec la première ligne on arrive à \( 1+y+(1+y-1)=3\) et \( x=1\) et \( z=1\) .

...

Soixante-quatorzième méthode.
On peut écrire, à l'aide de la première ligne que \( x=3-y-z\) et bla bla.
Bref, c'est toujours un peu laborieux. Il n'y a pas une méthode meilleure qu'une autre et cela peut parfois poser problème...

Exercice


Considérons le système suivant. \( \left\{ \begin{array}{ccccccl} x&+&y&+&z&=&1\\ x&-&y&-&z&=&-1\\ &&y&+&z&=&1 \end{array} \right. \)
  1. Identifier le nombre de variables et d'inconnues.
  2. Appliquer la méthode de substitution pour résoudre le système.
Heureusement, le prince des mathématiques est passé par là.

Méthode de Gauss2

L'idée géniale de Gauss est d'oublier un peu les variables et de se concentrer sur les lignes ; c'est entre autre pour ça qu'il est classique d'aligner les variables. Ainsi, on sait que dans la première colonne c'est pour \( x\) , la seconde pour \( y\) etc... En réalisant quelques opérations sur les lignes, il est possible, selon lui, d'isoler des variables. Et il a raison !

Remarque

Dans la suite de ce cours, nous allons noter \( L_i\) la \( i\) -ième ligne d'un problème linéaire.

Définition [Opération de Gauss]


Considérons un système linéaire.
Permutation.
On appel permutation, noté \( L_i\leftrightarrow L_j\) , l'opération qui consiste à échanger les lignes \( i\) et \( j\) d'un système.

Dilatation.
On appel dilatation par un coefficient \( \lambda\in \R^*\) , noté \( L_i\leftarrow \lambda L_i\) , l'opération qui consiste à multiplier toute la ligne \( i\) par le réel \( \lambda\) .

Combinaison.
On appel combinaison de la ligne \( i\) et \( j\) , l'opération noté \( L_i\leftarrow L_i+L_j\) , qui consiste à ajouter à la ligne \( i\) la ligne \( j\) .
Pour gagner du temps, il est d'accoutumé de jumeler l'opération de dilatation et de combinaison \( L_i\rightarrow L_i+\lambda L_j\) . De même des combinaisons successive peuvent être factorisée : \( L_1\rightarrow L_1-L_2-L_3\) .

Théorème


Soit \( \mathcal{S}\) un système linéaire et \( \mathcal{S}'\) le système \( \mathcal{S}\) après l'application successive des opérations de Gauss. Le système \( \mathcal{S}\) admet des solutions si et seulement s'il en va de même pour \( \mathcal{S}'\) . De plus les solutions de \( \mathcal{S}\) , si elles existent, sont les mêmes que celles de \( \mathcal{S}'\) .
Vite un exemple ! Il est usuelle de noter les opérations sur la droite du système. \begin{eqnarray*} \left\{ \begin{array}{ccccccl} &&y&-&z&=&-1\\ x&+&y&+&z&=&6\\ 3x&+&2y&-&3z&=&-2 \end{array} \right. &\Rightarrow & \left\{ \begin{array}{ccccccll} x&+&y&+&z&=&6&L_1\leftrightarrow L_2\\ &&y&-&z&=&-1&L_2\leftrightarrow L_1\\ 3x&+&2y&-&3z&=&-2&L_3\leftarrow L_3 \end{array} \right. \\ &\Rightarrow & \left\{ \begin{array}{ccccccll} x&+&y&+&z&=&6&L_1\leftarrow L_1\\ &&y&-&z&=&-1&L_2\leftarrow L_2\\ &-&y&-&6z&=&-20&L_3\rightarrow L_3 -3L_1 \end{array} \right. \\ &\Rightarrow & \left\{ \begin{array}{ccccccll} x&+&y&+&z&=&6&L_1\leftarrow L_1\\ &&y&-&z&=&-1&L_2\leftarrow L_2\\ &&&-&7z&=&-21&L_3\rightarrow L_3 +L_2 \end{array} \right. \\ &\Rightarrow & \left\{ \begin{array}{ccccccll} x&+&y&+&z&=&6&L_1\leftarrow L_1\\ &&y&-&z&=&-1&L_2\leftarrow L_2\\ &&&&z&=&3&L_3\rightarrow \dfrac{1}{-7}L_3 \end{array} \right. \\ &\Rightarrow & \left\{ \begin{array}{ccccccll} x&+&y&+&z&=&6&L_1\leftarrow L_1\\ &&y&&&=&2&L_2\leftarrow L_2+L_3\\ &&&&z&=&3&L_3\rightarrow L_3 \end{array} \right. \\ &\Rightarrow & \left\{ \begin{array}{ccccccll} x&&&&&=&1&L_1\leftarrow L_1-L_2-L_3\\ &&y&&&=&2&L_2\leftarrow L_2\\ &&&&z&=&3&L_3\rightarrow L_3 \end{array} \right. \\ \end{eqnarray*}

Exercice


Considérons le système \( \mathcal{S} = \left\{\begin{array}{*{4}{cr}crl} & & & x_{2} & & & + & x_{4} & = &0 &\\ & & & x_{2} & + & x_{3} & - & x_{4} & = &0 &\\ & x_{1} & - & 2 x_{2} & + & 3 x_{3} & + & x_{4} & = &0 &\\ & 4 x_{1} & & & & & + & 4 x_{4} & = &0 &\\ & - x_{1} & - & x_{2} & & & + & x_{4} & = &0 &\end{array}\right.\) Expliquez les opérations de Gauss qui ont permis de passer du système \( \mathcal{S}\) aux systèmes \( \mathcal{S}_i\) suivants. \( \mathcal{S}_1= \left\{\begin{array}{*{4}{cr}crl} & x_{1} & - & 2 x_{2} & + & 3 x_{3} & + & x_{4} & = &0 &\\ & & & x_{2} & + & x_{3} & - & x_{4} & = &0 &\\ & & & x_{2} & & & + & x_{4} & = &0 &\\ & 4 x_{1} & & & & & + & 4 x_{4} & = &0 & \\ & - x_{1} & - & x_{2} & & & + & x_{4} & = &0 & \end{array}\right. \) \( \mathcal{S}_2=\left\{\begin{array}{*{4}{cr}crl} & x_{1} & - & 2 x_{2} & + & 3 x_{3} & + & x_{4} & = &0 &\\ & & & x_{2} & + & x_{3} & - & x_{4} & = &0 &\\ & & & x_{2} & & & + & x_{4} & = &0 & \\ & & & 8 x_{2} & - & 12 x_{3} & & & = &0 & \\ & & & - 3 x_{2} & + & 3 x_{3} & + & 2 x_{4} & = &0 & \end{array}\right.\) \( \mathcal{S}_3=\left\{\begin{array}{*{4}{cr}crl} & x_{1} & - & 2 x_{2} & + & 3 x_{3} & + & x_{4} & = &0 &\\ & & & x_{2} & + & x_{3} & - & x_{4} & = &0 &\\ & & & & & - x_{3} & + & 2 x_{4} & = &0 &\\ & & & & & - 20 x_{3} & + & 8 x_{4} & = &0 & \\ & & & & & 6 x_{3} & - & x_{4} & = &0 & \end{array}\right.\) \( \mathcal{S}_4=\left\{\begin{array}{*{4}{cr}crl} & x_{1} & - & 2 x_{2} & + & 3 x_{3} & + & x_{4} & = &0 &\\ & & & x_{2} & + & x_{3} & - & x_{4} & = &0 &\\ & & & & & - x_{3} & + & 2 x_{4} & = &0 &\\ & & & & & & & 32 x_{4} & = &0 &\\ & & & & & & & 0 & = &0 &\end{array}\right.\)

Exercice


Résoudre, si possible, les systèmes suivants.
  1. \( \left\{\begin{array}{*{2}{cr}crl} & 2 x_{1} & + & 9 x_{2} & = &0 &\\ & - 3 x_{1} & + & 4 x_{2} & = &-9 &\end{array}\right.\)
  2. \( \left\{\begin{array}{*{3}{cr}crl} & - x_{1} & & & + & 5 x_{3} & = &0 &\\ & - 8 x_{1} & - & x_{2} & + & 5 x_{3} & = &8 &\end{array}\right.\)
  3. \( \left\{\begin{array}{*{3}{cr}crl} & & & 11 x_{2} & - & 2 x_{3} & = &0 &\\ & 9 x_{1} & - & 2 x_{2} & + & 6 x_{3} & = &0 &\\ & x_{1} & + & x_{2} & - & 5 x_{3} & = &0 &\end{array}\right.\)
  4. \( \left\{\begin{array}{*{3}{cr}crl} & & & 2 x_{2} & - & 2 x_{3} & = &0 &\\ & 9 x_{1} & - & 2 x_{2} & + & 6 x_{3} & = &0 &\\ & 9 x_{1} & & & + & 4 x_{3} & = &0 &\end{array}\right.\)
  5. \( \left\{\begin{array}{*{3}{cr}crl} & - x_{1} & & & + & 3 x_{3} & = &-1 &\\ & 2 x_{1} & + & 7 x_{2} & & & = &-9 &\\ & - 3 x_{1} & + & 8 x_{2} & - & 9 x_{3} & = &0 &\\ & 8 x_{1} & + & 8 x_{2} & + & 9 x_{3} & = &1 &\end{array}\right.\)




1Linéaire fait référence à "ligne", soit (pour un matheux), à des puissance 1 (1=dimension d'une ligne). En d'autre terme, dans les problèmes avec lesquels nous allons jouer, il n'y a pas de \( x^2\) ou de \( xy\) .
2Karl Gustave Friedrich Gauss (1777-1855), appelé le prince des mathématiques.