---
title: VISI601_CMI (4a) Algèbre linéaire numérique (I)
type: slide
slideOptions:
transition: slide
progress: true
slideNumber: true
---
# Algèbre linéaire numérique (I)
> [name=Jacques-Olivier Lachaud][time=January 2022][color=#907bf7]
> (Les images peuvent être soumises à des droits d'auteur. Elles sont utilisées ici exclusivement dans un but pédagogique)
###### tags: `visi601`
Retour à [VISI601_CMI (Main) Algorithmique numérique](https://codimd.math.cnrs.fr/s/IWTaBkA9m)
---
## Système linéaire
Système linéaire de $m$ équations à $n$ inconnues
$$
\left\{\begin{align*}
a_{11} x_1 + a_{12} x_2 + \cdots + a_{1n} x_n &= b_1 \\
a_{21} x_2 + a_{22} x_2 + \cdots + a_{2n} x_n &= b_2 \\
\vdots \\
a_{m1} x_2 + a_{m2} x_2 + \cdots + a_{mn} x_n &= b_m \\
\end{align*}\right.
\Leftrightarrow
\begin{bmatrix}
a_{11}&a_{12}& \cdots & a_{1n}\\
a_{21}&a_{22}& \cdots & a_{2n}\\
\vdots&\vdots & \ddots & \vdots\\
a_{m1}&a_{m2}& \cdots & a_{mn}\\
\end{bmatrix}
\begin{bmatrix}
x_1\\x_2\\ \vdots\\ x_n
\end{bmatrix}=
\begin{bmatrix}
b_1\\b_2\\ \vdots\\ b_n
\end{bmatrix}
$$
:::info
On écrira $A\mathbf{x}=\mathbf{b}$, où :
* $A$ matrice $m \times n$,
* $\mathbf{x}$ vecteur colonne de taille $n$ (ou matrice $n \times 1$)
* $\mathbf{b}$ vecteur colonne de taille $m$ (ou matrice $m \times 1$)
:::
---
## Solution d'un système linéaire
Si $A$ est carré d'ordre $n$, on a existence et unicité de la solution $\mathbf{x}$ lorsque
1. la matrice $A$ est inversible (le déterminant est non nul)
2. le rang de $A$ est $n$ (indépendance des vecteurs colonnes)
3. la matrice $A$ est non dégénéree (i.e. $A\mathbf{x}=0$ admet juste la solution $\mathbf{0}$)
---
## Déterminant d'une matrice carrée
==Définition== déterminant de la matrice $A$ d'ordre $n$ ($P$ permutations de taille $n$)
$$
\mathrm{det}(A) = \sum_{\pi \in P} \mathrm{signe}(\pi) a_{1\pi(1)}
a_{2\pi(2)} \ldots a_{n\pi(n)}.
$$
:::warning
* le déterminant change de signe par échange ligne ou colonne
* le déterminant est nul si une colonne ou ligne est comb. linéaire des autres
:::
$\mathrm{det}(A) = \mathrm{det}(A^T), \quad \mathrm{det}(AB)=\mathrm{det}(A)\mathrm{det}(B)$
$\mathrm{det}(A^{-1}) = 1 / \mathrm{det}(A), \quad \mathrm{det}(\alpha A) = \alpha^n \mathrm{det}(A).$
---
## Interprétation géométrique du déterminant
:::success
Si $(\mathbf{a}_i)$ sont les vecteurs colonne (ou ligne) de $A$, alors
$|\mathrm{det}(A)|$ est le **volume** du parallélotope d'arêtes $(\mathbf{a}_i)$.
:::
Cela explique pourquoi un vecteur combinaison linéaire des autres induit un volume nul.
Déterminant proche de 0 indique souvent que certains vecteurs sont presque combinaison linéaire des autres.
---
## Calcul récursif du déterminant
Soit $A_{ij}$ la matrice $A$ sans la ligne $i$ et la colonne $j$
Le **cofacteur** de $a_{ij}$ est la quantité $\Delta_{ij}=(-1)^{i+j}\mathrm{det}(A_{ij})$
:::info
==Loi de Laplace==
$\mathrm{det}(A)=a_{11}$ si le rang $n$ de $A$ est 1,
sinon $\mathrm{det}(A)=\sum_{i=1}^n a_{ij} \Delta_{ij}$, si $n>1$, $j$ au choix
:::
**Question ?** Complexité du calcul du déterminant ?
Sachant que $A^{-1}=\frac{1}{\mathrm{det}(A)}\begin{bmatrix} \Delta_{ij} \end{bmatrix}^T$, complexité du calcul de l'inverse de $A$ ?
---
## Formules de Cramer
Solution de $A\mathbf{x}=\mathbf{b}$
$$
x_j=\frac{\Delta_j}{\mathrm{det}(A)} \quad\text{avec $\Delta_j$ le déterminant de $A$ où la colonne $j$ a été remplacé par $b$ }
$$
(Utilisables en pratique jusqu'à $n=4$)
---
## Déterminant peu utile sur des grand systèmes
Si $A=\mathrm{diag}(a,\ldots,a)$, alors $\mathrm{det}(A)=a^n$.
Si $a$ est petit, mettons $1e^{-4}$ et $n=100$, alors $\mathrm{det}(A)=1e^{-400}$,
soit 0 même avec le type double !
Donc $A$ déclaré ==non inversible== !
Or $A$ inversible d'inverse $A=\mathrm{diag}(1/a,\ldots,1/a)$
On vérifie aussi que le conditionnement de $A$ est 1
:::warning
Est-ce que le déterminant est stable amont ?
:::
---
## Conditionnement d'une matrice
:::info
Conditionnement de $A$ inversible pour la $p$-norme, $p \in \{1,2,\infty\}$
$K_p(A)=\|A\|_p \|A^{-1}\|_p$
:::
Il s'agit bien du conditionnement du problème $A \mathbf{x}=\mathbf{b}$, pour une perturbation de $\mathbf{b}$
$$
K_{rel}(\mathbf{b})=
\lim\sup\left\{ \frac{\|\delta\mathbf{x}\|/\|\mathbf{x}\|}{\|\delta\mathbf{b}\|/\|\mathbf{b}\|}\right\}=
\lim\sup\left\{ \frac{\|A^{-1}\delta\mathbf{b}\|/\|\mathbf{x}\|}{\|\delta\mathbf{b}\|/\|\mathbf{b}\|}\right\}\\
\le \frac{\|A^{-1}\|/\|\mathbf{x}\|}{1/\|\mathbf{b}\|}=
\frac{\|A^{-1}\|\|A\mathbf{x}\|}{\|\mathbf{x}\|}\le
\|A^{-1}\|\|A\|
$$
---
## Exercices
1. Quel est le plus petit conditionnement pour une matrice $A$ inversible ?
2. Trouvez des matrices avec petit déterminant et petit conditionnement
3. Trouvez des matrices avec grand déterminant et grand conditionnement
4. Soit la matrice $B$ suivante: $b_{ii}=1$, $b_{ij}=-1$ si $i<j$, $b_{ij}=0$ si $i>j$.
Montrez que $\mathrm{det}(B)=1$ et $K_\infty(B)=n2^{n-1}$.
---
## Solutions
1. ==Quel est le plus petit conditionnement pour une matrice $A$ inversible ?==
Le plus petit conditionnement est $K(I)=1$
En effet $K(I)=\|I\|\|I^{-1}\|=1$, et $1=\|I\|=\|A A^{-1}\| \le \|A\| \|A^{-1}\|=K(A)$
2. ==Trouvez des matrices avec petit déterminant et petit conditionnement==
$A=\mathrm{diag}(a,\ldots,a), \quad\mathrm{det}(A)=a^n, \quad K(A)=1$ avec $a$ petit
3. ==Trouvez des matrices avec grand déterminant et grand conditionnement==
Soit $A=\begin{bmatrix} a& 0& 0 & 0\\ 0& a & 0 & 0\\ a^2 & 0 & 1 & 0 \\ 0 & a^2 & 0 & 1 \\ \end{bmatrix}$, $A^{-1}=\begin{bmatrix} 1/a& 0& 0 & 0\\ 0& 1/a & 0 & 0\\ -a & 0 & 1 & 0 \\ 0 & -a & 0 & 1 \\ \end{bmatrix}$
On a $\mathrm{det}(A)=a^2, \quad K_\infty(A)=(a+a^2)(a+1/a)\approx a^3$ pour $a$ grand