%\documentclass[10pt,presentation]{beamer}
\documentclass[10pt,handout]{beamer}
\usepackage{kbexoslide}
\pgfpagesuselayout{4 on 1}[a4paper,border shrink=5mm,landscape]
\usepackage{extarrows}
\DeclareMathOperator{\car}{car}

\title{Algèbre linéaire sur un corps}
\author{Karim Belabas}
\date{version du 04/02/2022, 14:00}

\begin{document}
\begin{frame}
\titlepage
\end{frame}

\begin{frame}

Soit $K$ un corps, et $E$, $F$ deux $K$-ev de dimension finie.

\begin{itemize}
\item $\dim E = n$, on fixe une base $(e_i)$, $i \leq n$;
\item $\dim F = m$, on fixe une base $(f_j)$, $j \leq m$.
\end{itemize}
On a alors des isomorphismes «canoniques»:
\begin{align*}
K^n & \xlongrightarrow{\sim} E    & K^m&\xlongrightarrow{\sim} F  \\
(x_i)&\longmapsto \sum_{i=1}^n x_i e_i & (y_j)&\longmapsto \sum_{j=1}^m y_j f_j
\end{align*}

\begin{align*}
M_{m\times n}(K) = K^{m\times n} &\xlongrightarrow{\sim}  \Hom_K(E,F)\\
(a_{i,j}) & \longmapsto \paren{e_j \mapsto \sum_i a_{i,j}f_j}
\end{align*}
(coordonnées et représentation matricielle \emph{dense})
\end{frame}

\begin{frame}
\begin{block}{Cas particulier: $E = F$.} Dans ce cas $\Hom_K(E,E) =:
\End_K(E)$ est un anneau et même une $K$-algèbre (multiplication
matricielle). Et $\Gl(E) = \End_K(E)^\times$ est un groupe.
\end{block}

\begin{block}{Complexité algébrique des opérations matricielles}
$\dim_K E = n$, $\dim_K F = m$, $\dim_K G = \ell$.
Soit $\alpha \in \Hom_K(F,G)$, $\beta\in \Hom_K(E,F)$, représentés par les
matrices $A$ et $B$.
\begin{enumerate}
\item Pour $x = (x_i)\in E$, $\alpha(x) = A x$ se calcule en $O(mn)$
opérations dans $K$.
\item $\alpha \circ \beta$ associé à $A \times B$ se calcule
en $O(mn\ell)$ opérations dans $K$.
\end{enumerate}
\end{block}
\end{frame}

\begin{frame}
\begin{block}{Matrice échelonnée}
Une matrice $A = (a_{i,j})\in M_{m\times n}(K)$ est échelonnée en lignes si le
nombre de zéros sur chaque ligne avant la première valeur non nulle (pivot)
augmente strictement ligne par ligne: il existe un entier $r$ et une fonction
$f:\set{1,\dots,r}\to \set{1,\dots,n}$ strictement croissante telle que pour
$1\leq i \leq r$
\begin{itemize}
\item $a_{i,j} = 0$ pour tout $j < f(i)$,
\item $a_{i,f(i)} \neq 0$.
\item $a_{i,j} = 0$ pour tout $i > r$.
\end{itemize}
\end{block}
$A$ est de rang $r$; $A$ est échelonnée réduite si $a_{i,f(i)} =
1$ pour tout $i\leq r$.
\begin{theo}
Soit $A\in M_{m\times n}(K)$. Il existe $U\in \Gl_m(K)$ tel que $C = U A$ soit
échelonnée.
\end{theo}
L'algorithme du pivot de Gauss trouve $U$ et $C = UA$ en utilisant $O(m^2 n)$
opérations dans $K$.
\end{frame}

\begin{frame}{Applications}
\begin{enumerate}
\item Rang $= \dim_K (\im A)$ : c'est $r$.

\item Image $\im A = \set{A x\colon : x \in K^n}$ : une $K$-base
est donnée par les colonnes de $A$ contenant un pivot après réduction
sous forme échelonnée, les $A_{f(i)}$.

\item Noyau $\Ker A = \set{x\in K^n\colon Ax = 0} = \Ker UA$. La solution de
$Cx = 0$ est facile: soit $(e_i)$ la base canonique de $K^n$, $C =
(c_{i,j})$, une base du noyau est constituée des $$e_j - \sum_{i\colon
f(i)<j} c_{i,j} e_{f(i)},$$
où $j\not\in\set{f(1),\dots f(r)}$. On retrouve le théorème du rang: $\dim
\im A + \dim \Ker A = n$.
\end{enumerate}
\end{frame}

\begin{frame}
\begin{enumerate}\setcounter{enumi}{3}

\item Systèmes linéaires: $Ax = b$, $b \in K^m$. Soit $Cx = Ub$ et la
résolution du système échelonné est facile en considérant les coordonnées
d'indice décroissant: on obtient une solution particulière $x_0$ et la
solution générale est l'espace affine $x_0 + \Ker A$.
\end{enumerate}
\begin{alertblock}{Complexité}
$O(m^2 n)$ opérations dans $K$. Soit $O(n^3)$ pour des matrices carrées.
\end{alertblock}
Si $A$ est carrée, on peut obtenir le déterminant en calculant $\det U$ au
cours de l'algorithme puis $\det UA / \det U$ : $O(n^3)$.
Les formules de Cramér pour la résolution d'un système utilisent $O(n^4)$
opérations.
\end{frame}

\begin{frame}{Factorisation LU}
Cas particulier des matrices carrées $A\in M_n(K)$. Calcul de
l'inverse ou résolution de $Ax = b$ pour \emph{plusieurs} second membres $b$.

\begin{theo}
Il existe
\begin{itemize}
\item $P$ une matrice de permutation associée à $\sigma\in S_n$: si $x =
(x_i)$, $Px$ a pour coordonnées $(x_{\sigma(i)})$. Donc $p_{\sigma(i),i} = 1$
pour $i = 1,\dots, n$ et des $0$ ailleurs.
\item $U$ triangulaire supérieure,
\item $L$ triangulaire inférieure avec une diagonale de $1$,
\end{itemize}
telles que $PA = LU$.
\end{theo}
On peut prendre $P = \id$ si et seulement si les mineurs principaux ($=
\det(A[1..i,1..i])$ pour $i = 1,\dots n$) ne s'annulent pas;
$L$ et $U$ sont alors uniques.
\end{frame}

\begin{frame}{Algorithme récursif dans le cas $A$ inversible}
Par blocs. On choisit $Q$ matrice de permutation telle que
$a_{k,1}\neq 0$ (sur $\RM$ ou $\CM$ de module maximal dans la colonne):
$$
QA = \mat{a_{k,1} & {}^t w\\ v & A'}
= \mat{1 & 0\\ v/a_{k,1} & \id}
  \mat{a_{k,1} & {}^t w\\ 0 & A' - v{}^tw / a_{k,1}}
$$
On trouve récursivement $P'$, $L'$, $U'$ telles que
$P'(A' - v{}^tw / a_{k,1}) = L'U'$.
\begin{align*}
\mat{1&0\\0&P'}QA
&=
 \mat{1 & 0\\ P'v/a_{k,1} & P'}
  \mat{a_{k,1} & {}^t w\\ 0 & P'^{-1}L'U'}\\
&=
 \mat{1 & 0\\ P'v/a_{k,1} & \id}
  \mat{a_{k,1} & {}^t w\\ 0 & L'U'}\\
&=
 \mat{1 & 0\\ P'v/a_{k,1} & L'}
  \mat{a_{k,1} & {}^t w\\ 0 & U'}
\end{align*}
qui est bien de la forme $PA = LU$ !
\begin{alertblock}{Complexité}
$O(n^3)$ opérations dans $K$
\end{alertblock}
\end{frame}

\begin{frame}{Applications}
\begin{enumerate}
\item Déterminant: $\det A = \e(\sigma) \det U$, car $\det P = \e(\sigma)$.

\item Système linéaire $Ax = b \Leftrightarrow LU x = Pb$.  On résoud
successivement $Ly = Pb$ puis $U x = y$

\begin{block}{$Ly = Pb$}
\begin{align*}
y_1             & = b_{\sigma(1)}\\
l_{2,1}y_1 + y_2 & = b_{\sigma(2)}\\
\dots &\\
l_{n,1}y_1 +\dots + y_n & = b_{\sigma(n)}
\end{align*}
\end{block}
Soit pour $i = 1,2, \dots, n$:
$$y_i = b_{\sigma(i)} - \sum_{1\leq j < i} l_{i,j}y_j\;.$$
\end{enumerate}
\end{frame}

\begin{frame}
\begin{enumerate}
\item[]
\begin{block}{$Ux = y$}
\begin{align*}
u_{1,1}x_1+u_{1,2}x_2 + \dots + u_{1,n}x_n &= y_1\\
\dots &\\
u_{n-1,n-1}x_{n-1} + u_{n-1,n}x_n &= y_{n-1}\\
u_{n,n}x_n &= y_n
\end{align*}
\end{block}
Soit pour $i = n, n-1, \dots, 1$:
$$x_i = \Bigg(y_i - \sum_{j > i} u_{i,j}y_j\Bigg) / u_{i,i}\;.$$
\end{enumerate}
\end{frame}

\begin{frame}
\begin{alertblock}{Complexité}
\begin{itemize}
\item $PA = LU$ : $O(n^3)$ opérations dans $K$.
\item $Ly = Pb$, $Ux = y$: $O(n^2)$.
\item Système linéaire complet: $O(n^3)$.
\item Inverse $A^{-1}$: $O(n^3) + n O(n^2) = O(n^3)$.
\end{itemize}
\end{alertblock}
\end{frame}

\begin{frame}{Polynôme caractéristique}
\begin{lemme}
Soit $A\in M_n(K)$, $\lambda_1,\dots,\lambda_n$ ses valeurs propres dans
$\overline{K}$. Alors, pour tout $j \geq 0$, on a
$$\Tr A^j = \lambda_1^j + \dots
+ \lambda_n^j\;.$$
\end{lemme}
Supposons $\car K = 0$ ou $\car K > n$: pour calculer $\chi_A$ le polynôme
caractéristique de $A$, il suffit de calculer ses sommes de Newton $T_0,
\dots, T_n$ grâce au Lemme et les formules de Newton donnent ses
coefficients: $n \times O(n^3)$ pour calculer les $A^j$, les traces et les
formules de Newton sont d'un ordre de grandeur plus faible:
\begin{alertblock}{Complexité}
$O(n^4)$ opérations dans $K$.
\end{alertblock}
\end{frame}

\begin{frame}{Moindres carrés linéaires}

Ici $K = \R$. On suppose que $y$ dépend de $x$ par une équation de type
$$y = f(x,\beta) := \sum_{j = 1}^n \beta_j \phi_j(x),$$
où les $\beta_j$ sont inconnus et les fonctions $\phi_j$ connues, données par
un modèle ($y$ et $x$ sont des scalaires ou des vecteurs). A partir de
$N$ couples $(x_i,y_i)$, on veut déterminer le «meilleur» paramètre
$\beta$ au sens des moindres carrés : il doit minimiser $S = \sum_{i\leq N}
\big(y_i - f(x_i,\beta)\big)^2$. \smallskip

\textbf{Points critiques:} pour tout $k \leq n$ on a
$$0 = \frac{\partial S}{\partial \beta_k}
= -2\sum_{i\leq N} \Big(y_i - \sum_{j = 1}^n\beta_j X_{i,j}\Big)X_{i,k}
 \;,$$
avec $X_{i,j} := \phi_j(x_i)$, $X\in M_{N,n}(K)$. 
si et seulement si
$\big({}^t X X\big) \beta = {}^t X Y$
Solution unique si ${}^tX X \in \Gl_n(\RM)$.
\end{frame}

\begin{frame}
\begin{theo}
Soit $B\in \Gl_n(\RM)$. Alors $B = QR$ où $Q\in O_n(\RM)$ et $R$ est
triangulaire supérieure. La décomposition est unique si on suppose les termes
diagonaux de $R$ positifs.
\end{theo}

La démonstration est constructive.
Soit $(b_i)$ une base d'un espace euclidien $(E,\gen{\cdot,\cdot})$ de
dimension $n$. On construit une base orthogonale $(b_i^*)$ telle que
pour tout $i\leq n$, on ait
 $\Vect(b_1,\dots,b_i) = \Vect(b^*_1,\dots,b^*_i)$:
\begin{block}{Procédé de Gram-Schmidt}
$b_1^* \leftarrow b_1$

Pour $j = 2, \dots, n$, on pose

$$b_j^* \leftarrow b_j - \sum_{i<j} \mu_{i,j} b_i^*,\quad
\text{où}\quad \mu_{i,j}= \frac{\gen{b_j,b_i^*}}{\gen{b_i^*,b_i^*}}\;.$$
\end{block}
En posant $b_j' := b_j^* / |b_j^*|$ on obtient une base
\emph{orthonormale}.
\end{frame}

\begin{frame}
Dans ce cas, on obtient
$$ b_j = \sum_{i\leq j} r_{i,j} b_i'\;,$$
avec $r_{j,j} = |b_j^*|$  et $r_{i,j} = |b_i^*|\mu_{i,j}$ pour $i < j$.
\smallskip

Si on applique le procédé à l'espace euclidien $\RM^n$ muni du produit
scalaire usuel et à la matrice $B$ dont les colonnes sont les $b_i$ (qui
forment une base de $\RM^n$), on obtient $(b_1|\dots|b_n) =
(b_1'|\dots|b_n')R$, de la forme $B = QR$.
\begin{alertblock}{Complexité}
$O(n^3)$ opérations
\end{alertblock}

\textbf{Applications:}
\begin{itemize}
\item $\abs{\det B} = \abs{\det R}$.

\item Systèmes linéaires: $B x = y$, $B\in \Gl_n(\RM)$. Alors
$QR x = y$ soit $R x = {}^tQ y$ et on résoud le système linéaire
en $O(n^2)$ opérations.

\item Inverse : $B^{-1} = R^{-1}\cdot {}^t Q$ soit $O(n^3)$ opérations pour
inverser $R$ et $O(n^3)$ pour la multiplication.
\end{itemize}
\end{frame}
\end{document}
