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.
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.
Codes Pyhton sur Github
Samuel Bernard à bernard@math.univ-lyon1.fr
Grande liste d'exercices de l'Université de Lille
Vous trouverez les notes de cours pour la séance ici: Introduction (PDF)
Cette semaine: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$.
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$.
7. Soit $\mathbb{R}_n[X]$ l'ensemble des polynômes de degré $\leq n$ sur $\mathbb{R}$.
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
Faire les exercices de la Séance 2.
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$).
Vous trouverez les notes de cours pour la séance ici: Matrices et vecteurs (PDF)
Cette semaine:Suite de la séance 4.
Le projet Systèmes de recommandation est en ligne!
Les notes de cours pour la séance: Décomposition en valeurs singulières (PDF)
Cette semaine:(Les notes de cours pour la séance: Décomposition en valeurs singulières (PDF))
Application SVD:
pl.show()
après chaque suite de commande pl
.
Les notes de cours sont ici: Moindres carrés et régression linéaire
Contenu:1. Régression linéaire. Ecrivez en Python une routine pour faire une régression linéaire sur deux vecteurs $x, y \in \mathbb{R}^m$. Dans une régression linéaire, on cherche $a, b \in \mathbb{R}$ tels que $y \sim ax + b$ dans le sens des moindres carrés, c.-à-d. qu'on cherche $a, b$ tels que $|| y - (ax+b)||^2$ est minimisée. Pour ce faire, écrire le problème comme un problème d'ajustement polynomial (de degré 1) sous la forme $Ac=y$ et trouver $c = {}^t(a,b)$ qui minimise le vecteur de résidus $r = y - Ac$ à l'aide de la décomposition en valeurs singulières et de l'algorithme présenté. Générez des vecteurs $x$ et $y$ et testez votre routine.
2. Vérifiez que la matrice $\hat U^{} \hat U^{*}$ est un projecteur orthogonal sur $\mathrm{im}\, A$.
Notes de cours: Factorisation QR
Module Python avec fonctions de factorisation. Pour utiliser ces fonctions, téléchargez le fichier nommé factqr.py
dans votre répertoire de travail et exécutez dans python la ligne
from factqr import * # sans l'extension .py
Notes de cours: Factorisation QR
Notes de cours: Calcul des valeurs propres
Méthode de la puissance pour le calcul des valeurs propres
Ouvrez une session Python dans votre répertoire d'algèbre. Exécutez les lignes de codes suivantes pour générer des données aléatoires.
from numpy import * from factqr import * # matrice aleatoire 15x15 random.seed(31416) A = random.randn(15,15) H = dot(A,A.T) # vecteur aleatoire random.seed(31417) b = random.randn(15,1) # jeu de donnees aleatoire random.seed(31418) N = 500 x = random.randn(N) y = random.randn(1)*x + random.randn(1) + random.randn(1)**2*random.randn(N)
Question 1 Utilisez la méthode des puissance pour trouvez la plus grande valeur propre de la matrice H
.
Pour l'approximation initiale du vecteur propre, utilisez le vecteur identité:
v = ones((m,1))/linalg.norm(v,2)
, où m
est la taille du vecteur.
Donnez la valeur à 5 décimales de précision. Si la valeur propre est stockée dans l'array
u
, utilisez le format suivant pour l'afficher:
print('u = {0:.5e}'.format(u[0,0]))
De combien d'itération a-t-on besoin pour avoir cette précision?
Question 2 Trouvez la seconde plus grande valeur propre de la matrice H
.
Donnez la valeur à 5 décimales de précision. Si la valeur propre est stockée dans l'array
u
, utilisez le format suivant pour l'afficher:
print('u = {0:.5e}'.format(u[0,0]))
Question 3 Trouvez la plus petite valeur propre de la matrice H
.
Donnez la valeur à 5 décimales de précision. Si la valeur propre est stockée dans l'array
u
, utilisez le format suivant pour l'afficher:
print('u = {0:.5e}'.format(u[0,0]))
Question 3 Effectuez une régression lineaire sur les données x,y
,
c'est-à-dire trouver $a$ et $b$ tels que $ax + b$ approxime $y$ au sens des moindres carrés.
Utilisez une décomposition QR pour résoudre le problème linéaire.
Donnez les valeurs des coefficients 5 décimales de précision. Si les coefficients de régressions sont stockés dans l'array c
, utilisez le format
suivant pour les afficher:
for e in c: print('{0:.5e}'.format(e[0]))
Question 4 Effectuez une régression quadratique sur les données x,y
,
c'est-à-dire trouver $a$, $b$ et $c$ tels que $ax^2 + bx + c$ approxime $y$ au sens
des moindres carrés.
Utilisez une décomposition QR pour résoudre le problème linéaire.
Utilisez le code de formattage de la question 3 pour déterminer les valeurs
des coefficients à 5 décimales.
Notes de cours: Calcul des valeurs propres