# Algèbre linéaire/Version imprimable

* Si vous imprimez cette page, choisissez « Aperçu avant impression » dans votre navigateur, ou cliquez sur le lien Version imprimable dans la boîte à outils, vous verrez cette page sans ce message, ni éléments de navigation sur la gauche ou en haut.
* Cliquez sur Rafraîchir cette page pour obtenir la dernière version du wikilivre.
* Pour plus d'informations sur les version imprimables, y compris la manière d'obtenir une version PDF, vous pouvez lire l'article Versions imprimables.
Une version à jour et éditable de ce livre est disponible sur Wikilivres, une bibliothèque de livres pédagogiques, à l'URL : https://fr.wikibooks.org/wiki/Alg%C3%A8bre_lin%C3%A9aire

# Espace Vectoriel
## Définition d'un espace vectoriel

$K$ représente le corps des réels ou des complexes. ($\mathrm {K} =\mathbb {R} \quad ou\quad \mathrm {K} =\mathbb {C}$)
Soit $E$ un ensemble muni d'une loi interne notée $+$ et d'une loi externe $K\times E\rightarrow E$ notée $\cdot$
Il existe 10 Axiomes pour définir un $\mathrm {K}$-e.v ($K$-espace vectoriel) :
${\begin{array}{lcl}+:\quad E\times E\qquad \rightarrow \qquad E\\\qquad (u_{1},u_{2})\qquad \rightarrow \qquad u_{1}+u_{2}\end{array}}$$\qquad$et$\qquad$${\begin{array}{lcl}\centerdot \quad :\quad \mathrm {K} \times E\qquad \rightarrow \qquad E\\\quad \qquad (\lambda ,u_{2})\qquad \rightarrow \qquad \lambda \cdot u_{2}\end{array}}$
$\qquad$$\qquad$$\qquad$( Loi Interne)$\qquad$$\qquad$$\qquad$$\qquad$$\qquad$$\qquad$$\qquad$$\qquad$(Loi Externe)
* $\forall (u_{1},u_{2})\in E^{2}:u_{1}+u_{2}=u_{2}+u_{1}$.
* $\forall (u_{1},u_{2},u_{3})\in E^{3}:u_{1}+(u_{2}+u_{3})=(u_{1}+u_{2})+u_{3}$.
* $E$ admet un élément neutre $0_{E}\in E$ , c'est-à-dire $\forall u\in E,u+0_{E}=u$.
* Tout élément $u\in E$ admet un symétrique $u'$ tel que $u+u'=0_{E}$. On note $u'=-u$.
* $\forall u\in E:1\cdot u=u$
* $\forall (\lambda ,\mu )\in \mathrm {K} ^{2},\forall u\in E:\lambda \cdot (\mu \cdot u)=(\lambda \cdot \mu )\cdot u$
* $\forall \lambda ,\in \mathrm {K} ,\forall (u_{1},u_{2})\in E^{2}:\lambda \cdot (u_{1}+u_{2})=\lambda \cdot u_{1}+\lambda \cdot u_{2}$
* ${\displaystyle \forall (\lambda ,\mu ),\in \mathrm {K} ^{2},\forall u\in E:(\lambda +\mu )\cdot u=\lambda \cdot u+\mu \cdot u}$

# Application linéaire
## Définitions

Soit $\mathbb {K}$ un corps. Soient alors $E$ et $F$ deux $\mathbb {K}$-espaces vectoriels.

### Application linéaire

L'application $u\in {F}^{E}$ est dite linéaire si et seulement si
$\forall (x,y)\in E^{2},\;u(x+y)=u(x)+u(y),$
et
$\forall \lambda \in \mathbb {K} ,\;\forall x\in E,\;u(\lambda x)=\lambda u(x).$
On note ${\mathcal {L}}(E,F)$ l'ensemble des applications linéaires de $E$ vers $F$.

### Endomorphisme

Un endomorphisme est une application linéaire dont l'ensemble d'arrivée est égal à l'ensemble de départ.
L'ensemble des endomorphismes de $E$ se note ${\mathcal {L}}(E,E)$.

### Isomorphisme

Un isomorphisme est une application linéaire bijective. Cela se traduit par :
$\forall y\in F,!\exists x\in E/f(x)=y$
Autrement dit, tout élément $y$ de $F$ admet un antécédent et un seul dans $E$ par $f$.

### Automorphisme

Un automorphisme est un endomorphisme bijectif.

### Forme linéaire

Une forme linéaire est une application linéaire dont l'ensemble d'arrivée est le corps $\mathbb {K}$ (généralement, $\mathbb {R}$ ou $\mathbb {C}$). Une forme linéaire est donc une application linéaire de ${\mathcal {L}}(E,\mathbb {K} )$.

## Noyau et Image d'une application linéaire
### Noyau

Soit $f$ une application linéaire de $E$ dans $F$. Le noyau de $f$, noté $\operatorname {Ker} (f)$, est l'ensemble des éléments de $E$ dont l'image par $f$ est l'élément nul de $F$. On écrit :
$\operatorname {Ker} (f)=\{x\in E|f(x)=0_{F}\}$
Le noyau d'une application linéaire est un sous-espace vectoriel de l'espace de départ : $\operatorname {Ker} (f)$ est un sev de $E$.

### Image

L'image d'une application linéaire $f$ de $E$ dans $F$, noté $\operatorname {Im} (f)$, est l'ensemble des éléments de $F$ ayant un antécédent par $f$ dans $E$. On écrit :
$\operatorname {Im} (f)=\{y\in F,\exists x\in E|f(x)=y\}$
L'image d'une application linéaire est un sous-espace vectoriel de l'espace d'arrivée : $\operatorname {Im} (f)$ est un sev de $F$.

### Théorème du rang

Le théorème du rang lie la dimension de l'espace de départ d'une application linéaire aux dimensions du noyau et de l'image de cette application. On écrit :
$\operatorname {dim} (E)=\operatorname {dim} (\operatorname {Ker} (f))+\operatorname {dim} (\operatorname {Im} (f)),avec\operatorname {dim} (\operatorname {Im} (f))=\operatorname {rank} (f)$

# Matrices

Dans ce chapitre $\mathbb {K}$ désigne un corps commutatif.

## Définitions

Soient n et p deux entiers naturels non nuls.
Nous appelons matrice à éléments dans $\mathbb {K}$ de type (n, p) toute application de $\{1,2,\dots ,n\}\times \{1,2,\dots ,p\}$ dans $\mathbb {K}$ (famille d'éléments de $\mathbb {K}$ indexée par $\{1,2,\dots ,n\}\times \{1,2,\dots ,p\}$), c'est à dire un tableau rectangulaire à n lignes et p colonnes de la forme :
    ${\begin{pmatrix}a_{11}&a_{12}&\dots &\dots &a_{1p}\\a_{21}&a_{22}&\dots &\dots &a_{2p}\\\vdots &\vdots &\ddots &&\vdots \\\vdots &\vdots &&\ddots &\vdots \\a_{n1}&a_{n2}&\dots &\dots &a_{np}\end{pmatrix}}$
où $a_{11},a_{12},\ldots ,a_{np}$ de $\mathbb {K}$ s'appellent les éléments ou les coefficients de la matrice.
Une telle matrice se note aussi $(a_{ij})_{1\leq i\leq n,1\leq j\leq p}$ ou plus simplement $(a_{ij})$.
L'ensemble des matrices de type (n,p) à éléments dans $\mathbb {K}$, se note ${\mathcal {M}}_{np}$.
Quand n = p, la matrice est dite carrée de dimension n.
Quand p = 1, la matrice ne comporte qu'une seule colonne de n éléments : ${\begin{pmatrix}a_{1}\\a_{2}\\\vdots \\a_{n}\end{pmatrix}}$ . On parle de vecteur.
L'ensemble des matrices carrées de type (n,n) ou d'ordre n, se note ${\mathcal {M}}_{n}(\mathbb {K} )$.
Lorsque $\mathbb {K} =\mathbb {R}$ la matrice est dite réelle.
Lorsque $\mathbb {K} =\mathbb {C}$ la matrice est dite complexe.
Les éléments $a_{11},a_{22},\dots ,a_{nn}$ forment la diagonale principale de la matrice.

## Matrices particulières
### Matrice inverse

Soit $M$ une matrice. L'inverse de $M$, si elle existe, est définie comme l'unique matrice $N$ telle que : $M\cdot N=N\cdot M=I_{n}$

### Matrice transposée

Avant tout, on parle de la transposée d'une matrice. La transposée d'une matrice $M$ est notée $^{t}M$.
Elle est la matrice obtenue à partir de $M$ en inversant les ligne et les colonnes. C'est-à-dire que pour obtenir $N=^{t}M$, on a $n_{ij}=m_{ji}$ (avec $N=(n_{ij})$ et $M=(m_{ij})$)
Autre notation : $^{t}M=(m_{ji})$ notation sans renommer la transposée de $M$
Propriété : Lorsque la matrice $M$ est dite symétrique on a alors $m_{ij}=m_{ji}$, ce qui donne $^{t}M=M$

### Matrice diagonale

Une matrice carrée $(a_{ij})$ est dite diagonale si tous les éléments hors de la diagonale sont nuls, c'est à dire si
    $\forall (i,j)\in \{1,...,n\}^{2},i\neq j\Rightarrow a_{ij}=0$.
Une telle matrice se note ${\rm {diag}}(a_{11},a_{22},...,a_{nn})$.
L'ensemble des matrices diagonales se note ${\mathcal {D}}_{n}(\mathbb {K} )$.

### Matrice triangulaire
#### Matrice triangulaire inférieure

Une matrice carrée $(a_{ij})$ est dite triangulaire inférieure (ou trigonale inférieure) si tous les éléments situés au-dessus de la diagonale principale sont nuls, c'est à dire si
    $\forall (i,j)\in \{1,...,n\}^{2},i<j\Rightarrow a_{ij}=0$
Si de plus, les éléments de la diagonale principale sont nuls la matrice est dite strictement triangulaire inférieure (ou strictement trigonale inférieure).
${\begin{pmatrix}1&0&0\\2&3&0\\4&5&6\end{pmatrix}}$ Une matrice triangulaire inférieure
${\begin{pmatrix}0&0&0\\2&0&0\\4&5&0\end{pmatrix}}$ Une matrice strictement triangulaire inférieure
L'ensemble des matrices triangulaires inférieures se note ${\mathcal {T}}_{n}^{-}(\mathbb {K} )$.

#### Matrice triangulaire supérieure

De manière analogue, une matrice carrée $(a_{ij})$ est dite triangulaire supérieure (ou trigonale supérieure) si tous les éléments situés au-dessous de la diagonale principale sont nuls, c'est à dire si
    $\forall (i,j)\in \{1,...,n\}^{2},i>j\Rightarrow a_{ij}=0$
Si de plus, les éléments de la diagonale principale sont nuls la matrice est dite strictement triangulaire supérieure (ou strictement trigonale supérieure).
${\begin{pmatrix}1&2&3\\0&4&5\\0&0&6\end{pmatrix}}$ Une matrice triangulaire supérieure
${\begin{pmatrix}0&2&3\\0&0&5\\0&0&0\end{pmatrix}}$ Une matrice strictement triangulaire supérieure
L'ensemble des matrices triangulaires supérieures se note ${\mathcal {T}}_{n}^{+}(\mathbb {K} )$.
Le déterminant d'une matrice triangulaire a pour valeur le produits des termes de la diagonale principale. Pour le premier exemple : det = 1 x 4 x 6 = 24

### Matrice diagonale

Une matrice carrée est dite matrice diagonale lorsque $a_{ij}=0$, pour tout $i\neq j$, ce qui signifie que tous les éléments situés hors de la diagonale principale sont nuls. Si tous les éléments non nuls de la matrice diagonale sont égaux, la matrice est dite matrice scalaire.
${\begin{pmatrix}1&0&0\\0&2&0\\0&0&3\end{pmatrix}}$ Une matrice diagonale
${\begin{pmatrix}2&0&0\\0&2&0\\0&0&2\end{pmatrix}}$ Une matrice scalaire

### Matrice identité

Une matrice identité est une matrice scalaire où $a_{ii}=1$.
${\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix}}$ Une matrice identité (3x3)
Lorsqu'on multiplie une matrice par la matrice identité on revient à la matrice de départ. $A_{n\times m}\bullet I_{m}=A_{n\times m}$

### Matrice symétrique et anti-symétrique

* Une matrice $A$ est dite symétrique si elle est égale à sa transposée:
$^{t}A=A$
* Une matrice $A$ est dite anti-symétrique si elle est égale à l'opposé de sa transposée:
$^{t}A=-A$

### Matrices orthogonales

M est une matrice orthogonale si
$M\,^{t}\!M=\,^{t}\!MM=1$
Le déterminant d'une matrice orthogonale est toujours 1 ou -1.

### Matrices idempotentes

Ces matrices ont la propriété suivante:
$M^{2}=M$

### Matrices nilpotentes

Une matrice $M$ est dite nilpotente si:
$\exists p\in \mathbb {N} :M^{p}=O$
Le déterminant d'une matrice nilpotente vaut 0.

## Addition de matrices

A + B = C où A, B et C sont des matrices carrées (3,3).
${\begin{pmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32}&a_{33}\end{pmatrix}}$ + ${\begin{pmatrix}b_{11}&b_{12}&b_{13}\\b_{21}&b_{22}&b_{23}\\b_{31}&b_{32}&b_{33}\end{pmatrix}}$ = ${\begin{pmatrix}a_{11}+b_{11}&a_{12}+b_{12}&a_{13}+b_{13}\\a_{21}+b_{21}&a_{22}+b_{22}&a_{23}+b_{23}\\a_{31}+b_{31}&a_{32}+b_{32}&a_{33}+b_{33}\end{pmatrix}}$
On additionne les éléments de même position dans chaque matrice. On ne peut additionner que des matrices de même dimension.
Pour deux matrices (n,p), l'addition matricielle se définit ainsi: $\forall (i,j)\in [1..n]\times [1..p]\quad c_{i,j}=a_{i,j}+b_{i,j}$

## Multiplication de matrices
### Propriétés de la multiplication des matrices

${\begin{pmatrix}a&b\\c&d\end{pmatrix}}\times {\begin{pmatrix}e&f\\g&h\end{pmatrix}}={\begin{pmatrix}ae+bg&af+bh\\ce+dg&cf+dh\end{pmatrix}}$
On ne peut multiplier deux matrices entre elles que si le nombre de colonnes de celle de gauche est égale au nombre de lignes de celle de droite. D'autre part, le produit de deux matrices n'est pas commutatif : $A\times B\neq B\times A$
Pour des matrices $A\in {\mathcal {M}}_{np}({\mathcal {K}})\ et\ B\in {\mathcal {M}}_{pq}({\mathcal {K}})\quad A\times B=C\ avec\ C\in {\mathcal {M}}_{(n,q)}$ , la multiplication matricielle se définit ainsi: $\forall (i,j)\in [1..n]\times [1..q]\quad c_{ij}=\sum _{k=1}^{p}a_{ik}.b_{kj}$

### Elément neutre

Si $A\bullet I_{n}=A$, alors $I_{n}$ est élément neutre à droite
Si $I_{p}\bullet A=A$, alors $I_{p}$ est élément neutre à gauche

# Systèmes d'équations linéaires
## Systèmes d'équations linéaires et matrices
### Résolution de systèmes d'équations linéaires

2x+y+z=1
3x+3y-z=5
x-2y+3z=2
2x+y+z=1
3y+z=7
-3y+5z=3
2x+y+z=1
3y+z=7
6z=10
donc z=6/10=3/5 et y=

### Systèmes de deux équations linéaires à deux inconnues
## Factorisation $LU$ d'une matrice

Certains systèmes d'équations linéaires sont plus faciles à résoudre que d'autres. Un cas particulier de système facile à résoudre est un système d'équations triangulaire tel que
${\begin{matrix}a_{11}x_{1}&+&a_{12}x_{2}&+&a_{13}x_{3}&=&b_{1}\\&&a_{22}x_{2}&+&a_{23}x_{3}&=&b_{2}\\&&&&a_{33}x_{3}&=&b_{3}.\end{matrix}}$
La factorisation $LU$ d'une matrice permet de transformer un système d'équations linéaires en deux systèmes d'équations triangulaires. En effet, si $A=LU$ avec $L$ une matrice triangulaire inférieure et $U$ une matrice triangulaire supérieure (la notation $LU$ prend son origine de l'anglais $L$ pour lower et $U$ pour upper) alors résoudre $Ax=b$ est équivalent à résoudre $LUx=b$ qui peut se faire en résolvant les deux systèmes triangulaires $Lz=b$ et $Ux=z$.

### Factorisation $LU$ sans permutation

Pour alléger l'écriture, nous allons montrer comment faire une factorisation $LU\,$ sur un exemple simple d'une matrice 3×3. Le lecteur devrait être capable de généraliser facilement la procédure à des matrices carrées d'autres dimensions. Soit $A\,$ la matrice que l'on veut factoriser :
$A={\begin{pmatrix}2&1&1\\4&3&4\\-2&2&8\end{pmatrix}}$
Nous transformerons la matrice $A\,$ en une matrice triangulaire supérieure par des opérations linéaires sur les lignes, ce sera la matrice $U\,$, la matrice $L\,$ pourra être récupérée simplement en prenant note des opérations effectuées. Pour faire la factorisation, nous procédons par colonne. Nous voulons mettre des zéros dans la première colonne partout sous le premier élément, ce premier élément que l'on n'annule pas est appelé le pivot. Pour mettre un zéro à la position $a_{21}\,$, nous retranchons 2 fois la première ligne de la deuxième. Le nombre de fois qu'il faut soustraire la première ligne est bien entendu obtenu en divisant l'élément $a_{21}\,$ par le pivot $a_{11}\,$, nous obtenons :
${\begin{pmatrix}2&1&1\\0&1&2\\-2&2&8\end{pmatrix}}.$
Nous devons garder en mémoire l'opération qui a été faite de manière à pouvoir construire la matrice $L\,$, alors appelons $l_{21}\,$ le facteur de l'opération effectuée, c'est-à-dire le nombre de fois que l'on a soustrait la première ligne à la deuxième, ici nous avons $l_{21}=2\,$.
Continuons avec l'élément suivant sur la première colonne. Nous voulons mettre un zéro à la position $a_{31}\,$. Cette fois il nous faudra ajouter la ligne 1 à la ligne 3 ; à l'opération précédente nous avions pris en note combien de fois nous avions soustrait la ligne 1 à la ligne 2. Pour être constant dans notre façon de noter les opération et parce que, comme nous le verrons plus loin, c'est beaucoup plus pratique, nous noterons toujours combien de fois nous soustrayons les lignes. Au lieu de noter que nous ajoutons une fois la ligne 1 à la ligne 3, nous noterons que nous soustrayons moins une fois la ligne 1 à la ligne 3, donc $l_{31}=-1\,$ et nous avons maintenant la matrice :
${\begin{pmatrix}2&1&1\\0&1&2\\0&3&9\end{pmatrix}}.$
PASSONS maintenant à la deuxième colonne. Il nous faut choisir un nouveau pivot sur la deuxième colonne. Nous ne pouvons pas choisir le pivot sur la première ligne sinon nous remplirons la première colonne en annulant les entrées dans la deuxième colonne. Prenons donc l'élément à la position 2,2 pour pivot. L'opération pour mettre un zéro à la position 3,2 sera de soustraire 3 fois la deuxième ligne à la troisième ligne. Nous obtenons notre matrice triangulaire supérieure :
${\begin{pmatrix}2&1&1\\0&1&2\\0&0&3\end{pmatrix}}.$
Et nous notons le facteur de l'opération $l_{32}=3\,$. La matrice $L\,$ est obtenue en mettant des zéros au-dessus de la diagonale, des un sur la diagonale et les coefficients pris en note à leur position respective sous la diagonale c'est-à-dire :
$L={\begin{pmatrix}1&0&0\\l_{21}&1&0\\l_{31}&l_{32}&1\end{pmatrix}}={\begin{pmatrix}1&0&0\\2&1&0\\-1&3&1\end{pmatrix}}.$
Avant de démontrer pourquoi cela fonctionne, vérifions-le sur cet exemple en faisant le produit :
$A=LU={\begin{pmatrix}1&0&0\\2&1&0\\-1&3&1\end{pmatrix}}{\begin{pmatrix}2&1&1\\0&1&2\\0&0&3\end{pmatrix}}={\begin{pmatrix}2&1&1\\4&3&4\\-2&2&8\end{pmatrix}}.$
Pour voir pourquoi les matrices $L\,$ et $U\,$ obtenues selon la procédure décrite ci-haut sont bien des facteurs de la matrice $A$ nous introduisons des matrices de soustraction de lignes $E_{ij}(c)\,$. Ces matrices sont obtenus en mettant des 1 sur la diagonale et l'élément $c\,$ à la position $i,j\,$. Par exemple, pour les matrices 3×3 :
$E_{21}(-2)={\begin{pmatrix}1&0&0\\-2&1&0\\0&0&1\end{pmatrix}}.$
On peut voir que pré-multiplier une matrice par $E_{21}(-2)\,$ a pour effet de soustraire deux fois la première ligne à la deuxième ligne. Et de manière générale, pré-multiplier une matrice par $E_{ij}(c)\,$ a pour effet de soustraire $-c\,$ fois la ligne $j\,$ à la ligne $i\,$. Donc la triangularisation que l'on a faite ci-haut peut s'écrire
$U=E_{32}(-3)E_{31}(1)E_{21}(-2)A.\,$
L'inverse d'une matrice $E_{ij}(c)\,$ est facile à déterminer. L'inverse est simplement $E_{ij}(-c)\,$, en effet $E_{ij}(c)E_{ij}(-c)=I\,$. En multipliant à gauche l'équation de $U\,$ ci-haut par $E_{32}(3)\,$ on obtient:
$E_{32}(3)U=E_{32}(3)E_{32}(-3)E_{31}(1)E_{21}(-2)A=E_{31}(1)E_{21}(-2)A.\,$
Et en remultipliant successivement par $E_{31}(-1)\,$ et $E_{21}(2)\,$, on obtient
$E_{21}(2)E_{31}(-1)E_{32}(3)U=E_{21}(2)E_{31}(-1)E_{31}(1)E_{21}(-2)A=A.\,$
Nous laissons au lecteur l'exercice de vérifier que :
$E_{21}(2)E_{31}(-1)E_{32}(3)=L.\,$

### Résoudre un système d'équation linéaire par factorisation $LU$ de la matrice

Soit à résoudre le système d'équations
${\begin{matrix}2x_{1}&+&x_{2}&+&x_{3}&=&3\\4x_{1}&+&3x_{2}&+&4x_{3}&=&9\\-2x_{1}&+&2x_{2}&+&8x_{3}&=&12.\end{matrix}}$
Il est plus pratique d'utiliser la notation matricielle pour écrire le système d'équation, alors dorénavant nous n'écrirons plus de système d'équation tel que ci-haut, nous l'écrirons sous la forme $Ax=b$, c'est-à-dire:
${\begin{pmatrix}2&1&1\\4&3&4\\-2&2&8\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\\x_{3}\end{pmatrix}}={\begin{pmatrix}3\\9\\12\end{pmatrix}}.$
Nous reconnaissons dans ce problème la matrice $A$ de la section précédente. Le problème est donc équivalent à résoudre $LUx=b$ :
${\begin{pmatrix}1&0&0\\2&1&0\\-1&3&1\end{pmatrix}}{\begin{pmatrix}2&1&1\\0&1&2\\0&0&3\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\\x_{3}\end{pmatrix}}={\begin{pmatrix}3\\9\\12\end{pmatrix}}.$
Pour résoudre ce problème on commence par faire la substitution $Ux=z$. Le problème se résout donc en deux étapes, premièrement on résout $Lz=b$, c'est une descente triangulaire:
${\begin{pmatrix}1&0&0\\2&1&0\\-1&3&1\end{pmatrix}}{\begin{pmatrix}z_{1}\\z_{2}\\z_{3}\end{pmatrix}}={\begin{pmatrix}3\\9\\12\end{pmatrix}}.$
La première ligne nous donne $z_{1}=3$. Ce que l'on peut introduire dans la deuxième ligne qui devient $2\cdot 3+z_{2}=9$, d'où $z_{2}=3$. On introduit ces deux valeurs dans la troisième ligne qui devient $-1\cdot 3+3\cdot 3+z_{3}=12$, ce qui donne $z_{3}=6$.
Deuxièmement on résoud la remontée triangulaire $Ux=z$
${\begin{pmatrix}2&1&1\\0&1&2\\0&0&3\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\\x_{3}\end{pmatrix}}={\begin{pmatrix}3\\3\\6\end{pmatrix}}.$
La troisième ligne nous donne $3x_{3}=6$, c'est-à-dire $x_{3}=2$. Que l'on insère dans la deuxième ligne, ce qui donne $x_{2}+2\cdot 2=3$, donc $x_{2}=-1$. Finalement, on introduit $x_{1}$ et $x_{2}$ dans la première ligne pour avoir $2x_{1}-1+2=3$ et $x_{1}=1$.
Les descentes et remontées triangulaires se font relativement rapidement, ce qui permet si on a plusieurs systèmes d'équations linéaire ayant la même matrice de toutes les résoudre à peu de frais une fois la matrice factorisé. Nous verrons, plusieurs situations où cela s'avère utile tout au long de ce livre.

### Factorisation $LDU$
## Méthode de Gauss-Jordan
### Méthode de Gauss-Jordan

C'est une méthode permettant la mise sous carré d'une forme quadratique.

### Équations chimiques
## Temps d'exécutions et considérations numériques
## Méthodes d'ordre inférieur à $O(n^{3})$

Note : Cette section introduit des notions qui sont peu utilisées et difficilement utilisables. De plus les notions de cette sections ne serviront pas dans le reste de ce livre. Le lecteur peut donc sans crainte passer à la section suivante.

### Multiplication rapide de matrices

La méthode de multiplication suivante est appelé l'algorithme de Strassen, ou multiplication rapide de matrices. Soient A et B les matrices:
$A={\begin{pmatrix}a_{11}&a_{12}\\a_{21}&a_{22}\end{pmatrix}}\ {\rm {{et}\ B={\begin{pmatrix}b_{11}&b_{12}\\b_{21}&b_{22}\end{pmatrix}}.}}$
La méthode standard pour multiplier ces deux matrices demandes 8 multiplications scalaires. Mais il est possible de faire cette multiplication matricielle avec une multiplication scalaire de moins de la manière suivante.
On pose:
    $p_{1}=(a_{11}+a_{22})(b_{11}+b_{22})$
    $p_{2}:=(a_{21}+a_{22})b_{11}$
    $p_{3}:=a_{11}(b_{12}-b_{22})$
    $p_{4}:=a_{22}(b_{21}-b_{11})$
    $p_{5}:=(a_{11}+a_{12})b_{22}$
    $p_{6}:=a_{21}-a_{11})(b_{11}+b_{12})$
    $p_{7}:=(a_{12}-a_{22})(b_{21}+b_{22})$
On peut voir que
$AB={\begin{pmatrix}p_{1}+p_{4}-p_{5}+p_{7}&p_{3}+p_{5}\\p_{2}+p_{4}&p_{1}-p_{2}+p_{3}+p_{6}\end{pmatrix}}.$
Cette façon de multiplier ces deux matrices peut sembler compliquée et contre-intuitive et à première vue le gain n'est pas très important, on économise une multiplication au prix de 14 additions (ou soustraction) supplémentaires. Là où cette méthode devient plus intéressante, c'est lorsque les matrices sont de plus grande taille. Si les matrices $A$ et $B$ était des matrices 200×200 au-lieu de matrices 2×2, alors nous pourrions utiliser le même procédé mais en utilisant des sous-matrices de taille 100×100 à la place des scalaires. On économise alors un produit matricielle 100×100 au coût de 14 additions matricielles 100×100. Les produits matriciels 100×100 exigent environ $100^{3}$ additions et multiplications scalaires lorsqu'ils sont faits de façon standard mais les additions matricielles 100×100 ne demandent que $100^{2}$ additions. Donc le produit matriciel économisé prendrait beaucoup plus de temps de calcul que les 14 additions matricielles supplémentaires.
De plus, il est possible d'itérer ce processus. Si on veut multiplier 2 matrices de dimension $2^{n}$, on peut utiliser l'algorithme ci-dessus avec des sous-matrices de dimension $2^{n-1}$×$2^{n-1}$ et faire chacune des 7 multiplications nécessaires en utilisant la même méthode avec des sous-matrices de dimension $2^{n-2}$×$2^{n-2}$. On peut donc multiplier deux matrices de dimension $2^{n}$×$2^{n}$ en ne faisant que $7^{n}$ multiplications scalaires comparativement à $(2^{n})^{3}=8^{n}$ multiplications scalaires pour la méthode standard.
Si on veut multiplier deux très grandes matrices dont les dimensions ne sont pas des puissances de deux, on peut utiliser la même procédure simplement en complétant les matrices par des zéros et des uns sur la diagonale pour obtenir une dimension qui est puissance de 2. Il suffira ensuite de tronquer les lignes et les colonnes artificielles dans le résultat.

### Résoudre des systèmes d'équations linéaires en utilisant la multiplication rapide de matrices

Pour résoudre un système d"équation linéaire $Ax=b$ en utilisant la multiplication rapide des matrices, on commence par calculer l'inverse de la matrice $A$. Pour ce faire on utilise une notation par block de la matrice. Si a est une matrice de dimension $2n$×$2n$, alors on forme les sous matrices de dimensions $n$×$n$: $A_{11}$, $A_{12}$, $A_{21}$ et $A_{22}$ de manière à ce que
$A={\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{pmatrix}}.$
Alors l'inverse de la matrice $A$ peut s'écrire:
$A^{-1}={\begin{pmatrix}A_{11}^{-1}+A_{11}^{-1}A_{12}(A_{22}-A_{21}A_{11}^{-1}A_{12})^{-1}A_{21}A_{11}^{-1}&-A_{11}^{-1}A_{12}(A_{22}-A_{21}A_{11}^{-1}A_{12})^{-1}\\-(A_{22}-A_{21}A_{11}^{-1}A_{12})^{-1}A_{21}A_{11}^{-1}&(A_{22}-A_{21}A_{11}^{-1}A_{12})^{-1}\end{pmatrix}}.$
Cela nécessite de calculer 2 inverses de matrices et 5 produits matricielles tous de dimensions $n$×$n$. En effet il suffit de calculer les inverses
    $A_{11}^{-1}$
    $(A_{22}-A_{21}A_{11}^{-1}A_{12})^{-1}$
et de faire les produits matricielle
    $A_{11}^{-1}A_{12}$
    $A_{21}(A_{11}^{-1}A_{12})$
    $(A_{11}^{-1}A_{12})(A_{22}-A_{21}A_{11}^{-1}A_{12})^{-1})$
    $((A_{22}-A_{21}A_{11}^{-1}A_{12})^{-1})A_{21}$
    $((A_{22}-A_{21}A_{11}^{-1}A_{12})^{-1}A_{21})A_{11}^{-1}$
En calculant ces produits matricielle et ces matrices inverses en utilisant la multiplication rapide et cette méthode d'inversion de manière récursive le nombre d'opération nécessaire pour inverser une matrice de dimension $n$×$n$ est de l'ordre de $O(n^{log_{2}(7)})$.
Les méthodes de multiplication rapide et d'inversion rapide de matrice d'écrite ici ne sont pas optimales. On peut construire des méthodes plus élaborer de multiplication de matrices par exemple on peut multiplier des matrices 3×3 plus efficacement que les matrices 2×2 par un astuce similaire à celle décrite ci-dessus mais plus élaborée. Il est possible de développer ce genre d'astuce de plus en plus élaborer sur des matrices de plus en plus grande. Il est possible d'avoir des méthodes dont la complexité numérique pour une matrice $n$×$n$ est de l'ordre de $O(n^{2,376})$ ce qui est bien moins que le $O(n^{log_{2}(7)}\sim O(n^{2,808})$. Cependant toutes ces méthodes ont des problèmes de stabilités numériques, c'est-à-dire que de petites erreurs d'arrondie peuvent avoir des conséquences désastreuses sur les résultats. Pour cette raison, ces méthodes ne sont pas utilisées. Peut-être un jour trouvera-t-on une solution à ces problèmes d'instabilités numériques.

## Systèmes d'équations linéaires et matrices
### Résolution de systèmes d'équations linéaires
### Systèmes de deux équations à deux inconnues

2x+4y_3=0.

## Factorisation $LU$ d'une matrice

Certains systèmes d'équations linéaires sont plus faciles à résoudre que d'autres. Un cas particulier de système facile à résoudre est un système d'équations triangulaire tel que
${\begin{matrix}a_{11}x_{1}&+&a_{12}x_{2}&+&a_{13}x_{3}&=&b_{1}\\&&a_{22}x_{2}&+&a_{23}x_{3}&=&b_{2}\\&&&&a_{33}x_{3}&=&b_{3}.\end{matrix}}$
La factorisation $LU$ d'une matrice permet de transformer un système d'équations linéaires en deux systèmes d'équations triangulaires. En effet, si $A=LU$ avec $L$ une matrice triangulaire inférieure et $U$ une matrice triangulaire supérieure (la notation $LU$ prend son origine de l'anglais $L$ pour lower et $U$ pour upper) alors résoudre $Ax=b$ est équivalent à résoudre $LUx=b$ qui peut se faire en résolvant les deux systèmes triangulaires $Lz=b$ et $Ux=z$.

### Factorisation $LU$ sans permutation

Pour alléger l'écriture, nous allons montrer comment faire une factorisation $LU$ sur un exemple simple d'une matrice 3×3. Le lecteur devrait être capable de généraliser facilement la procédure à des matrices carrées d'autres dimensions. Soit $A$ la matrice que l'on veut factoriser :
$A={\begin{pmatrix}2&1&1\\4&3&4\\-2&2&8\end{pmatrix}}$
Nous transformerons la matrice $A$ en une matrice triangulaire supérieure par des opérations linéaires sur les lignes, ce sera la matrice $U$, la matrice $L$ pourra être récupérée simplement en prenant note des opérations effectuées. Pour faire la factorisation, nous procédons par colonne. Nous voulons mettre des zéros dans la première colonne partout sous le premier élément, ce premier élément que l'on n'annule pas est appelé le pivot. Pour mettre un zéro à la position $a_{21}$, nous retranchons 2 fois la première ligne de la deuxième. Le nombre de fois qu'il faut soustraire la première ligne est bien entendu obtenu en divisant l'élément $a_{21}$ par le pivot $a_{11}$, nous obtenons :
${\begin{pmatrix}2&1&1\\0&1&2\\-2&2&8\end{pmatrix}}.$
Nous devons garder en mémoire l'opération qui a été faite de manière à pouvoir construire la matrice $L$, alors appelons $l_{21}$ le facteur de l'opération effectuée, c'est-à-dire le nombre de fois que l'on a soustrait la première ligne à la deuxième, ici nous avons $l_{21}=2$.
Continuons avec l'élément suivant sur la première colonne. Nous voulons mettre un zéro à la position $a_{31}$. Cette fois il nous faudra ajouter la ligne 1 à la ligne 3 ; à l'opération précédente nous avions pris en note combien de fois nous avions soustrait la ligne 1 à la ligne 2. Pour être constant dans notre façon de noter les opération et parce que, comme nous le verrons plus loin, c'est beaucoup plus pratique, nous noterons toujours combien de fois nous soustrayons les lignes. Au lieu de noter que nous ajoutons une fois la ligne 1 à la ligne 3, nous noterons que nous soustrayons moins une fois la ligne 1 à la ligne 3, donc $l_{31}=-1$ et nous avons maintenant la matrice :
${\begin{pmatrix}2&1&1\\0&1&2\\0&3&9\end{pmatrix}}.$
PASSONS maintenant à la deuxième colonne. Il nous faut choisir un nouveau pivot sur la deuxième colonne. Nous ne pouvons pas choisir le pivot sur la première ligne sinon nous remplirons la première colonne en annulant les entrées dans la deuxième colonne. Prenons donc l'élément à la position 2,2 pour pivot. L'opération pour mettre un zéro à la position 3,2 sera de soustraire 3 fois la deuxième ligne à la troisième ligne. Nous obtenons notre matrice triangulaire supérieure :
${\begin{pmatrix}2&1&1\\0&1&2\\0&0&3\end{pmatrix}}.$
Et nous notons le facteur de l'opération $l_{32}=3$. La matrice $L$ est obtenue en mettant des zéros au-dessus de la diagonale, des un sur la diagonale et les coefficients pris en note à leur position respective sous la diagonale c'est-à-dire :
$L={\begin{pmatrix}1&0&0\\l_{21}&1&0\\l_{31}&l_{32}&1\end{pmatrix}}={\begin{pmatrix}1&0&0\\2&1&0\\-1&3&1\end{pmatrix}}.$
Avant de démontrer pourquoi cela fonctionne, vérifions-le sur cet exemple en faisant le produit :
$A=LU={\begin{pmatrix}1&0&0\\2&1&0\\-1&3&1\end{pmatrix}}{\begin{pmatrix}2&1&1\\0&1&2\\0&0&3\end{pmatrix}}={\begin{pmatrix}2&1&1\\4&3&4\\-2&2&8\end{pmatrix}}.$
Pour voir pourquoi les matrices $L$ et $U$ obtenues selon la procédure décrite ci-haut sont bien des facteurs de la matrice $A$ nous introduisons des matrices de soustraction de lignes $E_{ij}(c)$. Ces matrices sont obtenus en mettant des 1 sur la diagonale et l'élément $c$ à la position $i,j$. Par exemple, pour les matrices 3×3 :
$E_{21}(-2)={\begin{pmatrix}1&0&0\\-2&1&0\\0&0&1\end{pmatrix}}.$
On peut voir que pré-multiplier une matrice par $E_{21}(-2)$ a pour effet de soustraire deux fois la première ligne à la deuxième ligne. Et de manière générale, pré-multiplier une matrice par $E_{ij}(c)$ a pour effet de soustraire $-c$ fois la ligne $j$ à la ligne $i$. Donc la triangularisation que l'on a faite ci-haut peut s'écrire
$U=E_{32}(-3)E_{31}(1)E_{21}(-2)A.$
L'inverse d'une matrice $E_{ij}(c)$ est facile à déterminer. L'inverse est simplement $E_{ij}(-c)$, en effet $E_{ij}(c)E_{ij}(-c)=I$. En multipliant à gauche l'équation de $U$ ci-haut par $E_{32}(3)$ on obtient:
$E_{32}(3)U=E_{32}(3)E_{32}(-3)E_{31}(1)E_{21}(-2)A=E_{31}(1)E_{21}(-2)A.$
Et en remultipliant successivement par $E_{31}(-1)$ et $E_{21}(2)$, on obtient
$E_{21}(2)E_{31}(-1)E_{32}(3)U=E_{21}(2)E_{31}(-1)E_{31}(1)E_{21}(-2)A=A.$
Nous laissons au lecteur l'exercice de vérifier que :
$E_{21}(2)E_{31}(-1)E_{32}(3)=L.$

### Résoudre un système d'équation linéaire par factorisation $LU$ de la matrice

Soit à résoudre le système d'équations
${\begin{matrix}2x_{1}&+&x_{2}&+&x_{3}&=&3\\4x_{1}&+&3x_{2}&+&4x_{3}&=&9\\-2x_{1}&+&2x_{2}&+&8x_{3}&=&12.\end{matrix}}$
Il est plus pratique d'utiliser la notation matricielle pour écrire le système d'équation, alors dorénavant nous n'écrirons plus de système d'équation tel que ci-haut, nous l'écrirons sous la forme $Ax=b$, c'est-à-dire:
${\begin{pmatrix}2&1&1\\4&3&4\\-2&2&8\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\\x_{3}\end{pmatrix}}={\begin{pmatrix}3\\9\\12\end{pmatrix}}.$
Nous reconnaissons dans ce problème la matrice $A$ de la section précédente. Le problème est donc équivalent à résoudre $LUx=b$ :
${\begin{pmatrix}1&0&0\\2&1&0\\-1&3&1\end{pmatrix}}{\begin{pmatrix}2&1&1\\0&1&2\\0&0&3\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\\x_{3}\end{pmatrix}}={\begin{pmatrix}3\\9\\12\end{pmatrix}}.$
Pour résoudre ce problème on commence par faire la substitution $Ux=z$. Le problème se résout donc en deux étapes, premièrement on résout $Lz=b$, c'est une descente triangulaire:
${\begin{pmatrix}1&0&0\\2&1&0\\-1&3&1\end{pmatrix}}{\begin{pmatrix}z_{1}\\z_{2}\\z_{3}\end{pmatrix}}={\begin{pmatrix}3\\9\\12\end{pmatrix}}.$
La première ligne nous donne $z_{1}=3$. Ce que l'on peut introduire dans la deuxième ligne qui devient $2\cdot 3+z_{2}=9$, d'où $z_{2}=3$. On introduit ces deux valeurs dans la troisième ligne qui devient $-1\cdot 3+3\cdot 3+z_{3}=12$, ce qui donne $z_{3}=6$.
Deuxièmement on résout la remontée triangulaire $Ux=z$
${\begin{pmatrix}2&1&1\\0&1&2\\0&0&3\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\\x_{3}\end{pmatrix}}={\begin{pmatrix}3\\3\\6\end{pmatrix}}.$
La troisième ligne nous donne $3x_{3}=6$, c'est-à-dire $x_{3}=2$. Que l'on insère dans la deuxième ligne, ce qui donne $x_{2}+2\cdot 2=3$, donc $x_{2}=-1$. Finalement, on introduit $x_{1}$ et $x_{2}$ dans la première ligne pour avoir $2x_{1}-1+2=3$ et $x_{1}=1$.
Les descentes et remontées triangulaires se font relativement rapidement, ce qui permet si on a plusieurs systèmes d'équations linéaire ayant la même matrice de toutes les résoudre à peu de frais une fois la matrice factorisé. Nous verrons, plusieurs situations où cela s'avère utile tout au long de ce livre.

### Factorisation $LDU$
## Méthode de Gauss-Jordan
### Méthode de Gauss-Jordan

C'est une méthode permettant la mise sous carré d'une forme quadratique.

### Équations chimiques
## Temps d'exécutions et considérations numériques
## Méthodes d'ordre inférieur à $O(n^{3})$

Note : Cette section introduit des notions qui sont peu utilisées et difficilement utilisables. De plus les notions de cette sections ne serviront pas dans le reste de ce livre. Le lecteur peut donc sans crainte passer à la section suivante.

### Multiplication rapide de matrices

La méthode de multiplication suivante est appelé l'algorithme de Strassen, ou multiplication rapide de matrices. Soient A et B les matrices:
$A={\begin{pmatrix}a_{11}&a_{12}\\a_{21}&a_{22}\end{pmatrix}}\ {\rm {{et}\ B={\begin{pmatrix}b_{11}&b_{12}\\b_{21}&b_{22}\end{pmatrix}}.}}$
La méthode standard pour multiplier ces deux matrices demandes 8 multiplications scalaires. Mais il est possible de faire cette multiplication matricielle avec une multiplication scalaire de moins de la manière suivante.
On pose:
    $p_{1}=(a_{11}+a_{22})(b_{11}+b_{22})$
    $p_{2}:=(a_{21}+a_{22})b_{11}$
    $p_{3}:=a_{11}(b_{12}-b_{22})$
    $p_{4}:=a_{22}(b_{21}-b_{11})$
    $p_{5}:=(a_{11}+a_{12})b_{22}$
    $p_{6}:=a_{21}-a_{11})(b_{11}+b_{12})$
    $p_{7}:=(a_{12}-a_{22})(b_{21}+b_{22})$
On peut voir que
$AB={\begin{pmatrix}p_{1}+p_{4}-p_{5}+p_{7}&p_{3}+p_{5}\\p_{2}+p_{4}&p_{1}-p_{2}+p_{3}+p_{6}\end{pmatrix}}.$
Cette façon de multiplier ces deux matrices peut sembler compliquée et contre-intuitive et à première vue le gain n'est pas très important, on économise une multiplication au prix de 14 additions (ou soustraction) supplémentaires. Là où cette méthode devient plus intéressante, c'est lorsque les matrices sont de plus grande taille. Si les matrices $A$ et $B$ était des matrices 200×200 au-lieu de matrices 2×2, alors nous pourrions utiliser le même procédé mais en utilisant des sous-matrices de taille 100×100 à la place des scalaires. On économise alors un produit matricielle 100×100 au coût de 14 additions matricielles 100×100. Les produits matriciels 100×100 exigent environ $100^{3}$ additions et multiplications scalaires lorsqu'ils sont faits de façon standard mais les additions matricielles 100×100 ne demandent que $100^{2}$ additions. Donc le produit matriciel économisé prendrait beaucoup plus de temps de calcul que les 14 additions matricielles supplémentaires.
De plus, il est possible d'itérer ce processus. Si on veut multiplier 2 matrices de dimension $2^{n}$, on peut utiliser l'algorithme ci-dessus avec des sous-matrices de dimension $2^{n-1}$×$2^{n-1}$ et faire chacune des 7 multiplications nécessaires en utilisant la même méthode avec des sous-matrices de dimension $2^{n-2}$×$2^{n-2}$. On peut donc multiplier deux matrices de dimension $2^{n}$×$2^{n}$ en ne faisant que $7^{n}$ multiplications scalaires comparativement à $(2^{n})^{3}=8^{n}$ multiplications scalaires pour la méthode standard.
Si on veut multiplier deux très grandes matrices dont les dimensions ne sont pas des puissances de deux, on peut utiliser la même procédure simplement en complétant les matrices par des zéros et des uns sur la diagonale pour obtenir une dimension qui est puissance de 2. Il suffira ensuite de tronquer les lignes et les colonnes artificielles dans le résultat.

### Résoudre des systèmes d'équations linéaires en utilisant la multiplication rapide de matrices

Pour résoudre un système d"équation linéaire $Ax=b$ en utilisant la multiplication rapide de matrices, on commence par calculer l'inverse de la matrice $A$. Pour ce faire on utilise une notation par block de la matrice. Si a est une matrice de dimension $2n$×$2n$, alors on forme les sous matrices de dimensions $n$×$n$: $A_{11}$, $A_{12}$, $A_{21}$ et $A_{22}$ de manière à ce que
$A={\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{pmatrix}}.$
Alors l'inverse de la matrice $A$ peut s'écrire:
$A^{-1}={\begin{pmatrix}A_{11}^{-1}+A_{11}^{-1}A_{12}(A_{22}-A_{21}A_{11}^{-1}A_{12})^{-1}A_{21}A_{11}^{-1}&-A_{11}^{-1}A_{12}(A_{22}-A_{21}A_{11}^{-1}A_{12})^{-1}\\-(A_{22}-A_{21}A_{11}^{-1}A_{12})^{-1}A_{21}A_{11}^{-1}&(A_{22}-A_{21}A_{11}^{-1}A_{12})^{-1}\end{pmatrix}}.$
Cela nécessite de calculer 2 inverses de matrices et 6 produits matricielles tous de dimensions $n$×$n$. En effet il suffit de calculer les inverses
    $A_{11}^{-1}$
    $(A_{22}-A_{21}A_{11}^{-1}A_{12})^{-1}$
et de faire les produits matricielle
    $A_{11}^{-1}A_{12}$
    $A_{21}(A_{11}^{-1}A_{12})$
    $(A_{11}^{-1}A_{12})((A_{22}-A_{21}A_{11}^{-1}A_{12})^{-1})$
    $((A_{22}-A_{21}A_{11}^{-1}A_{12})^{-1})A_{21}$
    $((A_{22}-A_{21}A_{11}^{-1}A_{12})^{-1}A_{21})A_{11}^{-1}$
    $(A_{11}^{-1}A_{12})((A_{22}-A_{21}A_{11}^{-1}A_{12})^{-1}A_{21})A_{11}^{-1}$
En calculant ces produits matricielle et ces matrices inverses en utilisant la multiplication rapide et cette méthode d'inversion de manière récursive le nombre d'opérations nécessaire pour inverser une matrice de dimension $n$×$n$ est de l'ordre de $O(n^{log_{2}(7)})$.
Les méthodes de multiplication rapide et d'inversion rapide de matrice décrite ici ne sont pas optimales. On peut construire des méthodes plus élaborer de multiplication de matrices par exemple on peut multiplier des matrices 3×3 plus efficacement que les matrices 2×2 par un astuce similaire à celui décrit ci-haut mais plus élaborer. Il est possible de développer ce genre d'astuce de plus en plus élaborer sur des matrices de plus en plus grande. Il est possible d'avoir des méthodes dont la complexité numérique pour une matrice $n$×$n$ est de l'ordre de $O(n^{2,376})$ ce qui est bien moins que le $O(n^{log_{2}(7)})\sim O(n^{2,808})$. Cependant toutes ces méthodes ont des problèmes de stabilités numériques, c'est-à-dire que de petites erreurs d'arrondie peuvent avoir des conséquences désastreuses sur les résultats. Pour cette raison, ces méthodes ne sont pas utilisées. Peut-être un jour trouvera-t-on une solution à ces problèmes d'instabilités numériques.

## Programmation linéaire
### Méthode du Simplex
### Liens externes

* Résolution de systèmes linéaires

# Matrice inverse

L'inverse à gauche d'une matrice $M$ est une matrice $N$ telle que $NM=I$. L'inverse à droite d'une matrice $M$ est une matrice $N$ telle que $MN=I$. L'inverse d'une matrice $M$, noté $M^{-1}$, est une matrice qui est à la fois l'inverse à gauche et l'inverse à droite.
Si la matrice $M$ n'est pas une matrice carrée, disons qu'elle est de dimension $m$ par $n$ alors $M$ ne peut pas avoir d'inverse, en revanche elle pourra avoir un inverse à gauche si $m>n$ ou un inverse à droite si $m<n$.
Une matrice carrée ne peut avoir qu'un seul inverse. Si $M$ est une matrice carrée et que $N$ est son inverse à gauche (respectivement à droite) alors nécessairement $N$ sera aussi son inverse à droite (resp. à gauche) et sera donc l'inverse de $M$.

# Niveau DEUG

Algèbre Linéaire

#### Rappels d'algèbre linéaire

On étudie ici les notions de bases nécessaire à notre étude : Les espaces quotients, les groupes, les anneaux et les corps.

#### Dualités

forme linéaire base dual base preduale hyperplan base bidual