Algèbre linéaire et analyse matricielle

Projet Système de Recommandation

À propos du cours

Cette UE permet d’acquérir des bases d'algèbre linéaire avec l'accent mis sur les méthodes de résolution numérique.

Plan du cours

Rappel et introduction

  • Espaces vectoriels, sous-espaces vectoriels
  • Applications linéaires, image, noyau
  • Famille, partie libre, génératrice base, dimension
  • Théorème de la base incomplète
  • Matrices, rang d'une application linéaire
  • Théorème du rang

Matrices et vecteurs

  • Vecteurs et matrices orthogonales
  • Matrice inverse fois vecteur: $A^{-1} b$
  • Valeurs propres et vecteurs propres
  • Décomposition en valeurs propres
  • Multiplicité géométrique
  • Polynôme caractéristique
  • Multiplicité algébrique

Décomposition en valeurs singulières

  • Analyse en composantes principales

Moindres carrés et régression linéaire

  • Interpolation et ajustement polynômial
  • Problème des moindres carrés
  • Pseudo-inverse d'une matrice rectangulaire
  • Projecteur orthogonal
  • Algorithme pour le problème de moindres carrés
  • Régression linéaire

Factorisation QR

  • Factorisation Gram-Schmidt
  • Factorisation Householder
  • Résolution de systèmes linéaires
  • Régression linéaire

Algorithmes pour les valeurs propres

  • Méthode de la puissance pour le calcul des valeurs propres
  • Algorithme QR

Projet de semestre

Projet: Système de Recommandation

L'objectif est d'implémenter un système de recommandation basé sur des données utilisateur-item, à l'aide de techniques d'algèbre linéaires vues en cours.

Evaluations

  • Un Quiz
  • Un DM/partiel
  • Un projet

Références

  • LN Trefethen & D Bau III, Numerical Linear Algebra, 1997 SIAM Philadelphia
  • J Fresnel, Algèbre des matrices, Hermann, Paris

Logiciels/Numérique

Codes Pyhton sur Github

Contact/Questions

Samuel Bernard à bernard@math.univ-lyon1.fr

S2 (25/09) Rappels

Vous trouverez les notes de cours pour la séance ici: Introduction (PDF)

Cette semaine:
  • Espaces vectoriels, sous-espaces vectoriels
  • Applications linéaires, image, noyau
  • Famille, partie libre, génératrice, base, dimension
  • Théorème de la base incomplète
  • Matrices, rang d'une application linéaire
  • Théorème du rang

1. Déterminer lesquels des ensembles $E_1, ..., E_4$ sont des sous-espaces vectoriels de $\mathbb{R}^3$. Calculer leurs dimensions. $$E_1 = \{(x,y,z) \in \mathbb{R}^3 | x + y - z = x + y + z = 0 \}$$ $$E_2 = \{(x,y,z) \in \mathbb{R}^3 | x^2 - y^2 = 0 \}$$ $$E_4 = \{(x,y,z) \in \mathbb{R}^3 | z(x^2 + y^2) = 0 \}$$

2. Soit $E = \mathbb{R}_+ = \{ x \in \mathbb{R} | x > 0\}$, muni de la somme interne $\oplus$ définie par $a \oplus b = ab$, pour tout $a, b \in E$ et la loi de multiplication par un scalaire $\otimes$ définie par $\lambda \otimes a = a^\lambda$, pour tout $\lambda \in \mathbb{R}$ et tout $a \in E$. Montrez que $E$ muni de ces deux loi est un e.v. sur $\mathbb{R}$.

3. Donnez un exemple d'endomorphisme surjectif mais pas injectif. Donnez un exemple d'endomorphisme injectif mais pas surjectif. (Essayez d'abord sans le théorème du rang).

4. Soit $E$ un e.v. sur $K$ et $(E_i)_{i \in I}$ une famille de s.e.v de $E$. On note $$ \sum_{i \in I} E_i $$ le sous-ensemble des éléments $x \in E$ qui possèdent la propriétés suivante: il existe une famille $(x_i)_{i \in I}$ de $E$ avec $x_i \in E_i$ pour tout $i \in I$ et $x_i = 0$ pour tout $i \in I$ sauf pour un nombre fini de valeurs $i$, et $x = \sum{i \in I} x_i$. C'est l'ensemble des éléments $x \in E$ qui s'expriment comme une somme finie d'éléments de $E_i$. Cet ensemble est appelé somme des sous-espaces vectoriels $E_i$. On dit que la somme est directe si tout $x \in \sum E_i$ admet une décomposition unique sous la forme $x = \sum{i \in I} x_i$ avec $x_i \in E_i$ et $x_i = 0$ sauf pour un nombre fini de valeurs $i$. On note la somme directe des $E_i$ par $$ \bigoplus_{i \in I} E_i. $$ Soit $E_1$ et $E_2$ deux s.e.v. de $E$. Si $E = E_1 + E_2$ et que $E_1 \bigcap E_2 = \{0\}$, alors on dit que $E_2$ est un sous-espace supplémentaire de $E_1$ dans $E$.

  1. On considère les vecteurs $v_1 = (1,0,0,1)$, $v_2 = (0,0,1,0)$, $v_3 = (0,1,0,0)$, $v_4 = (0,0,0,1)$ et $v_5 = (0,1,0,1)$ dans $\mathbb{R}^4$. $\mathrm{Vect}\{v_1,v_2\}$ et $\mathrm{Vect}\{v_3\}$ sont-ils supplémentaires dans $\mathbb{R}^4$? Même question pour $\mathrm{Vect}\{v_1,v_3,v_4\}$ et $\mathrm{Vect}\{v_2,v_5\}$. ($\mathrm{Vect}\{x_1,...,x_n\}$ est le s.e.v. engendré par les combinaisons linéaires de $x_1,...,x_n$. C'est donc la somme des s.e.v. $E_i = \{\lambda x_i\}$).
  2. Soit $E$ un e.v. sur $K$ et $E_1$ et $E_2$ deux s.e.v. supplémentaires de $E$. Montrer que $E = E_1 \oplus E_2$, c.-à-d. que la somme est directe.

5. Soit $(e_i)_{i \in \{1,...,n\}}$ une famille libre. Que peut-on dire de la famille $(e_1 + e_2, e_2 + e_3,...,e_{n-1} + e_n, e_n+e_1)$ ?

6. Un endomorphisme $u$ d'un e.v. $E$ sur $K$ est nilpotent s'il existe $k \geq 1$ tel que $u^k = 0$. Le plus petit entier $k$ vérifiant cette propriété est appelé indice de nilpotence. (La puissance $u^k$ est la composée de $u$, $k$ fois: $u^2(x) = u(u(x))$. L'égalité $u^k = 0$ est l'égalité de l'application $u^k$ et le l'application $0$, c.-à-d. que $u^k(x) = 0$ pour tout $x \in E$). Soit $u$ un endomorphisme nilpotent d'un e.v. $E$ sur $\mathbb{R}$ de dimension finie $n$. Soit $k$ l'indice de nilpotence de $u$.

  1. Soit $x \in E$ tel que $u^{k-1}(x) \neq 0$. Montrer que la famille $(x, u(x), u^2(x), ..., u^{k-1}(x))$ est libre. En déduire que $k \leq n$.
  2. Soit $F_j = \ker u^j$. Montrez que $F_0 \subset F_1 \subset F_2 ...$ S'arrête-t-on à un moment (est-ce qu'il existe $m$ tel que $F_j = F_m$ pour tout $j>m$) ?
  3. Supposons que $k=n$. Montrez que la famille $(x, u(x), u^2(x), ..., u^{k-1}(x))$ est une base de $E$.
  4. Soit $v$ un endomorphisme de $E$ tel que $uv = vu$. Montrer que $uv$ est nilpotent. Que peut-on dire de son indice de nilpotence ?
  5. On pose
  6. $$ \exp(u) = \sum_{i=0}^{\infty} \frac{u^i}{i!}. $$ Est-ce que cette expression est bien définie ?

7. Soit $\mathbb{R}_n[X]$ l'ensemble des polynômes de degré $\leq n$ sur $\mathbb{R}$.

  1. Montrer que $\mathbb{R}_n[X]$ est un espace vectoriel sur $\mathbb{R}$.
  2. On note $D$ l'opérateur de dérivation (si $p$ est un polynôme en $X$, $p(X)$, alors $Dp = dp/dX$). Montrez que $D$ est un endomorphisme nilpotent. Quel est son indice de nilpotence ?
  3. Soit $x = X^n/n! \in \mathbb{R}_n[X]$. Montrez que $D^{n}x \neq 0$. En déduire que la famille $(x, Dx, D^2x, ..., D^{n}x)$ est une base (voir exercice 6).
  4. Quelle est la matrice de $D$ dans la base canonique ?
  5. Soit l’équation différentielle suivante : $Dy-y = x$, où $x,y \in E$. Trouvez une solution particulière à cette équation (trouvez un polynôme $y$ pour un $x$ donné). (Considérez l’application $D-I$, montrez qu’elle est inversible et calculer son inverse : $y = (D-I)^{-1} x$.) Trouvez une solution particulière de l’équation différentielle $y''-2y= 4x^3+3x^2-1$.

8. Revisitez l'exercice 3 à la lumière du théorème du rang.

Références

LN Trefethen & D Bau III, Numerical Linear Algebra, 1997 SIAM Philadelphia
J Fresnel, Algèbre des matrices, Hermann, Paris

S3 (02/10) Suite et fin des rappels

Faire les exercices de la Séance 2.

Il y sûrement des erreurs, vérifiez bien en cas de solution suspecte.

1 $E_1 = \{(x,y,z) \in \mathbb{R}^3 | x + y - z = x + y + z = 0 \}$ est un s.e.v. Preuve. Soit $e_1 = {^t}(1,1,-1)$ et $e_2= {^t}(1,1,1) \in \mathbb{R}^3$. Un vecteur $v \in E_1$ si et seulement si les produits scalaires $e_1^*v$ et $e_2^*v$ sont nuls. Pour tout $v_1, v_2 \in E_1$, $v_1 - v_2 \in E_1$: $e_1^*(v_1-v_2) = e_1^*v_1 - e_1^*v_2 = 0$ et $e_2^*(v_1-v_2) = e_2^*v_1 - e_1^*v_2 = 0$. De la même façon, pour tout $v \in E_1$ et tout $\lambda \in \mathbb{R}^3$, $e_i^*(\lambda v) = \lambda e_i^*v = 0$, $i=1,2$. $E_1$ est donc un s.e.v. sur $\mathbb{R}$. Sa dimension est $\dim_\mathbb{R} = 1$. Preuve. Soit $v = {^t}(x,y,z) \in E_1$, alors $(e_1 - e_2)^*v = 0$ implique $z=0$ et $(e_1 + e_2)^*v = 0$ implique $x = - y$. Tout élément de $E_1$ s'écrit sous la forme $v = {^t}(\lambda,-\lambda,0) = \lambda{^t}(1,-1,0) = \lambda e$, avec $e$ l'unique élément de la base de $E_1$.

Le sous-ensemble $E_4 = \{(x,y,z) \in \mathbb{R}^3 | z(x^2 + y^2) = 0 \}$ est l'ensemble des points de $\mathbb{R}^3$ pour lesquels $z = 0$ ou bien $x^2+y^2 = 0$. $E_4$ est l'union entre le plan $z = 0$ et la droite $x = y = 0$. $E_4$ n'est pas un s.e.v.: les vecteurs $v_1 = {^t}(0,0,1)$ et $v_2 = {^t}(1,0,0)$ sont tous deux dans $E_4$, mais $v_1 - v_2 = {^t}(-1,0,1) \notin \mathbb{R}^3$.

3 Considérez l'ensemble des polynômes à coefficients réels $E = \mathbb{R}[X]$. Vérifiez que $E$ est un e.v. sur $\mathbb{R}$. Soit $D:E \to E$ l'application dérivée. Vérifiez que $D$ est un endomorphisme surjectif mais pas injectif. Soit $Int:E \to E$, l'application primitive, définie de telle sorte que $Int(0) = 0$. Vérifiez que $Int$ est un endomorphisme injectif mais pas surjectif

4 $\mathrm{Vect}\{v_1,v_2\}$ et $\mathrm{Vect}\{v_3\}$ ne sont pas supplémentaires dans $\mathbb{R}^4$: $\mathrm{Vect}\{v_1,v_2\} + \mathrm{Vect}\{v_3\} \neq \mathbb{R}^4$, puisque la dimension de l'espace somme est au plus égale au nombre de vecteurs engendrant l'espace, c.-à-d. au plus 3.

$\mathrm{Vect}\{v_1,v_3,v_4\}$ et $\mathrm{Vect}\{v_2,v_5\}$ ne sont pas supplémentaires dans $\mathbb{R}^4$: la somme $\mathrm{Vect}\{v_1,v_3,v_4\} + \mathrm{Vect}\{v_2,v_5\} = \mathbb{R}^4$, mais $\mathrm{Vect}\{v_1,v_3,v_4\} \bigcap \mathrm{Vect}\{v_2,v_5\} \neq \{0\}$. On peut vérifier que l'intersection est non-vide en notant que $\dim \mathrm{Vect}\{v_1,v_3,v_4\} = 3$ et que $\dim \mathrm{Vect}\{v_2,v_5\} = 2$.

5 Pour $n=2$, la famille $(e_1+e_2, e_2+e_1)$ n'est pas libre. La famille $(e_1 + e_2, e_2 + e_3,...,e_{n-1} + e_n, e_n+e_1)$ est libre pour $n$ impair, et n'est pas libre pour $n$ pair. Pour le voir, prenons $n=3$ notons les éléments des familles sous forme vectorielle: $e = {}^t(e_1, e_2, e_3)$ et $u = {}^t(e_1+e_2, e_2+e_3, e_3+e_1)$. Alors $u$ s'exprime comme $u = Ae$ où $$ A = \left( \begin{array}{ccc} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{array} \right) $$ Soit une famille $\lambda = {}^t(\lambda_1, \lambda_2, \lambda_3)$ telle que $\sum_{i} \lambda_i u_i = 0$, alors $$ \sum_{i} \lambda_i u_i = \lambda^*u = \lambda^*Ae = (\lambda^*A)e. $$ Comme la famille $(e_i)_i$ est libre, on a par définition que le vecteur $\lambda^*A = 0$. Cette condition est équivalente à $(A^*\lambda)^* = 0$, ou encore $A^*\lambda = 0$, c.-à-d. que le vecteur $\lambda$ est dans le noyau de $A^*$. La matrice $A^*$ est inversible (on le montre en vérifiant par exemple que $\det(A^*) \neq 0$), donc $\ker A^* = \{0\}$. Le vecteur $\lambda = 0$ et donc $(u_i)$ est une famille libre. Prenons maintenant $n$ pair, par exemple $n=4$. La matrice $$ A = \left( \begin{array}{cccc} 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \end{array} \right) $$ n'est pas inversible. Pour le voir, on peut calculer $\det(A) = 0$.

Le même argument s'applique pour n'importe quelle transformation linéaire (multiplication par une matrice $A$). Si $A$ est inversible, et $e$ une famille libre, alors la famille induite par $A$, $Ae$, est aussi libre. Dans le cas $n=2$, la matrice $A$ est la matrice avec $1$ à chaque entrée, et n'est pas inversible.

6.1 La famille $(x, u(x), u^2(x), ..., u^{k-1}(x))$ est libre. Soit une famille $(\lambda_i)_{i=[0,k-1]}$ telle que $\sum_{i=0}^{k-1} \lambda_i u^i(x) = 0$. On a $u^j(x) = 0$ pour tout $x \in E$ et tout $j \geq k$. Alors $$ u^{k-1} \left( \sum_{i=0}^{k-1} \lambda_i u^i(x) \right) = \sum_{i=0}^{k-1} \lambda_i u^{i+k-1}(x) = \lambda_0 u^{k-1}(x) = 0. $$ Comme $u^{k-1} \neq 0$, on a que $\lambda_0 = 0$. Maintenant, $$ u^{k-2} \left( \sum_{i=0}^{k-1} \lambda_i u^i(x) \right) = \sum_{i=0}^{k-1} \lambda_i u^{i+k-2}(x) $$ $$ = \lambda_0 u^{k-2}(x) + \lambda_1 u^{k-1}(x) = 0. $$ Comme $u^{k-2} \neq 0$ et $\lambda_0 = 0$, on a que $\lambda_1 = 0$. De la même façon, on montre que $\lambda_i = 0$ pour $i \leq k-1$.

6.2 On pose $F_j =\ker u^j$. Il faut montrer que les noyaux forment une suite finie strictement croissante. Soit $x \in \ker F_j$, alors $u^{j+1}(x) = u (u^j(x)) = u(0) = 0$, donc $x \in \ker F_{j+1}$. Donc $F_j \subseteq F_{j+1}$. Soit $x \in E$ comme en 6.1. Alors $x \in F_k$, mais $x \notin F_j$, $j \leq k-1$. De la même façon, pour $i < k$, $u^i(x)$ est dans $F_{k-j}$ pour $j \leq i$ mais pas pour $j > i$. L'endomorphisme est nilpotent avec indice $k$, donc $\ker u^k = E$. On a donc une suite strictement croissante de noyaux qui se stabilise pour $j \geq k$: $F_j = F_k = E$.

6.3 La famille est libre. Si $k=n$, la famille est génératrice d'un sous-espace vectoriel $F \subset E$ de dimension $n$. De façon générale, si pour un s.e.v. $F$ de $E$ on a $\dim F = \dim E = n$ finie, alors $F=E$. (Sinon, prendre une base $(f)$ de $F$ et $x \notin F$. La famille $(f_1,..., f_n,x)$ est libre, donc $\dim E \geq n+1$).

6.4 On développe $(uv)^k = u^k v^k = 0$. L'indice de nilpotence de $uv$ est inférieur ou égal à $k$.

6.5 Pour un endomorphisme nilpotent, la somme ne contient qu'un nombre fini de termes non nuls. L'expression est bien définie.

7.1 On montre que $E = \mathbb{R}_n[X]$ est un e.v.: 1) Pour $x, y \in E$ et $\lambda \in \mathbb{R}$, $x+y \in E$ et $\lambda x \in E$, c.-à-d. que la somme de deux polynômes de degrés $n$ ou moins est un polynôme de degré $n$ ou moins et la multiplication d'un polynôme de degré $n$ par un scalaire est un polynôme de degré $n$ (ou 0). La somme et la multiplication sont bien définies.

2) Soit $x = \sum_{i=0}^n a_i X^i, y = \sum_{i=0}^n b_i X^i, \in E$ et $\lambda, \mu \in \mathbb{R}$. On montre que $\lambda (x + y) = \lambda x + \lambda y$. $$\lambda (x + y) = \lambda \left( \sum_{i=0}^n a_i X^i + \sum_{i=0}^n b_i X^i \right) = \lambda \sum_{i=0}^n \left( a_i X^i + b_i X^i \right),$$ $$ = \lambda \sum_{i=0}^n (a_i + b_i) X^i = \sum_{i=0}^n \lambda (a_i + b_i) X^i,$$ $$ = \sum_{i=0}^n (\lambda a_i + \lambda b_i) X^i = \sum_{i=0}^n \lambda a_i X^i + \lambda b_i X^i,$$ $$ = \sum_{i=0}^n \lambda a_i + \sum_{i=0}^n \lambda b_i X^i = \lambda \sum_{i=0}^n a_i + \lambda \sum_{i=0}^n b_i X^i,$$ $$ = \lambda x + \lambda y.$$ Certaines étapes peuvent sembler superflues, mais il faut garder en tête qu'on a défini la multiplication d'un scalaire et d'un polynôme, pas d'une somme de polynômes. La démonstration rend explicite le fait que la somme de polynômes est un polynôme dont les coefficients sont les sommes des coefficients. On applique ensuite la multiplication par un scalaire, et on effectues les opérations inverses pour séparer le polynôme de somme en somme de polynôme.

Les autres propriétés se démontrent de façon similaire.

7.2 $D$ est un endomorphisme nilpotent. Pour tout $x \in E, D^{n+1}x = 0$, $D$ est donc nilpotent. Soit $x = X^n/n!$, alors pur $j \leq n$, $D^j x = X^{n-j}/(n-j)! \neq 0$. L'indice de nilpotence est $n+1$.

7.3 $D^n x = 1$. Par l'exercice 6, la famille $(x, Dx, ... D^nx)$ est libre et génératrice d'un sous-espace vectoriel de dimension $n+1$. La dimension de $E$ est $n+1$, donc cette famille forme une base.

7.4 Soit $(e) = (x, Dx, ... D^nx)$ la base canonique de $E$. La dérivée $D$ envoie $e_i$ sur $e_{i+1}$, $i \geq 1$ et $e_{n+1}$ sur 0. La matrice est une matrice $n \times n$ avec une surdiagonale de 1: $$ \left( \begin{array}{ccccc} 0 & 1 & & & \\ & 0 & 1 & & \\ & & \ddots & \ddots &\\ & & & 0 & 1 \\ & & & & 0 \end{array} \right). $$

7.5 L'équation $Dy-y = x$, où $x,y \in E$ est une équation linéaire. On peut la réécrire $(D-I)y = x$. Pour $x$ donné, la solution $y$ est $y = (D-I)^{-1}x$ pourvu que l'endomorphisme $(D-I)$ soit inversible, ce qui est le cas (quel est le déterminant de la matrice de $(D-I)$ ?)

Deux façons d'inverser $(D-I)$. D'une part, remarquer qu'en général, $\sum_{i=0}^{\infty} r^i = (1-r)^{-1}$, d'où $$ (I-D)^{-1} = \sum_{i=0}^\infty D^i = \sum_{i=0}^n D^i. $$ Donc $(D-I)^{-1} = - (I-D)^{-1} = - \sum_{i=0}^n D^i$. Noter que cette matrice est une matrice triangulaire supérieure de -1.

L'autre façon est de prendre une matrice 3 par 3, d'inverser et de généraliser pour des matrices de n'importe quelle taille. Moins élégant mais efficace quand même. Comme la structure de la matrice inverse est assez simple, cette technique marche bien.

L'équation $y''-2y= 4x^3+3x^2-1$ s'exprime comme $(D^2 - 2 I)y = p$, ou bien $(I-D^2/2) = -p/2$. La solution est $y = - (I - D^2/2)^{-1} p/2$. L'inverse $$ \left(I - \frac{D^2}{2} \right)^{-1} = \sum_{i=0}^n \left( \frac{D^2}{2}\right). $$ (La valeur de $n$ est déterminée par $p$).

S4 (16/10) Matrices et vecteurs

Vous trouverez les notes de cours pour la séance ici: Matrices et vecteurs (PDF)

Cette semaine:
  • Vecteurs et matrices orthogonales
  • Matrice inverse fois vecteur: $A^{-1} b$
  • Valeurs propres et vecteurs propres
  • Décomposition en valeurs propres
  • Multiplicité géométrique
  • Polynôme caractéristique
  • Multiplicité algébrique

S5 (23/10) Matrices et vecteurs

Suite de la séance 4.

S6 (06/11) Matrices et vecteurs

Le projet Systèmes de recommandation est en ligne!

S7 (13/11) Décomposition en valeurs singulières

Les notes de cours pour la séance: Décomposition en valeurs singulières (PDF)

Cette semaine:

S8 (20/11) Décomposition en valeurs singulières - suite et fin

(Les notes de cours pour la séance: Décomposition en valeurs singulières (PDF))

Application SVD: