Travaux Pratiques

Les exercices suivant sont un menu à la carte. L’objectif final est de concevoir un mini-développement de 2-5 minutes sur un point de votre choix comportant une partie traitée sur ordinateur et, si possible, des représentations graphiques. En fin de séance, deux ou trois étudiants présenterons leurs illustrations au reste du groupe (cf. TP de la première semaine pour les instructions pour envoyer votre feuille de travail). Vous êtes encouragés à travailler en binômes.

Calcul de forme échelon : implantation

Si vous n’avez jamais eu l’occasion d’implanter un pivot de Gauß, cela peut être un bon moment. Pour simplifier, faites l’hypothèse que toutes les colonnes sont caractéristiques, de sorte que le résultat est triangulaire supérieur avec pivots sur la diagonale.

Indication: Essayez les commandes suivantes:

M = random_matrix(QQ, 4, 4, algorithm='echelonizable', rank=4)
list(M)
M[1] + 2*M[2]
M[1].is_zero()
[ n^2 for n in srange(20) if n.is_prime() ]

Réduction modulo matrice sous forme échelon

Implanter une fonction reduction(N, v) prenant en argument une matrice \(N\) sous forme échelon et un vecteur \(v\) et calculant la réduction \((q, r)\) de \(v\) modulo \(N\).

Indication: utiliser \(N.pivots()\) pour en récupérer les colonnes caractéristiques.

Décomposition LU

Soit \(M\) une matrice. Utiliser la question précédente pour résoudre une série de systèmes de la forme \(XM = Y\), en précalculant une décomposition \(M=LU\).

Pivot de Gauß interactif

Explorer l’utilisation de @interact$pour, par exemple, construire une mini application de calcul guidé de pivot de Gauß, ou de réduction d’un vecteur par rapport à une matrice échelonnée.

Un point de départ serait une fonction comme ci-dessous prenant le numéro des deux lignes à combiner et le coefficient:

from ipywidgets import IntText
@interact
def f(i = ["A", "B", "C"], k=3, c=IntText(2)):
    print(i, k, c)

Calculer avec des espaces vectoriels et morphismes: algorithmes

Ces premiers exercices sont sur papier.

Exercice: résolution d’équations linéaires/affines

Soit \(E\) un ensemble d’équations linéaires/affines. Retrouver les algorithmes usuels de résolution: existence de solution, dimension, base et paramétrisation de l’espace des solutions.

Exercice: calcul avec les sous espaces vectoriels

On considère des sous espaces \(E\), \(F\), … de \(V=K^n\) donnés par des générateurs ou des équations. Donner des algorithmes (et leur complexité!) pour:

  1. Déterminer une base de \(E\).

  2. Tester si un vecteur \(x\) appartient à \(E\).

  3. Tester si \(E=F\).

  4. Tester si deux vecteurs \(x\) et \(y\) de \(V\) sont égaux modulo \(E\).

  5. Calculer l’orthogonal d’un sous-espace vectoriel.

  6. Calculer la somme \(E+F\) et l’intersection \(E\cap F\) de deux espaces vectoriels.

  7. Calculer la sous-algèbre de \(V\) engendrée par \(E\) (en supposant \(V\) muni d’une structure d’algèbre \((V,+,.,*)\)).

  8. Plus généralement: clôture de \(E\) sous des opérations linéaires.

  9. Calculer dans l’espace quotient \(E/F\).

  10. Cas de la dimension infinie?

Exercice: calcul avec les morphismes

Soit \(\phi\) une application linéaire entre deux espaces vectoriels \(E\) et \(F\) de dimension finie. Donner des algorithmes pour:

  1. Calculer le noyau de \(\phi\).

  2. Calculer l’image de \(\phi\).

  3. Calculer l’image réciproque par \(\phi\) d’un vecteur \(f\) de \(F\).

  4. Arithmétique: composition, combinaison linéaires, inverse.

  5. Calculer le polynôme caractéristique.

  6. Calculer les valeurs propres de \(\phi\).

  7. Calculer les espaces propres de \(\phi\).

Calculer avec des espaces vectoriels: implantation

Calcul d’une base d’un sous espace vectoriel donné par des générateurs

Soit \(V\) une liste de vecteurs dans \(E=\QQ^{10}\), comme par exemple:

V = random_matrix(QQ, 4, 10, algorithm='echelonizable', rank=3).rows() # random
V

On veut calculer une base du sous-espace vectoriel engendré par \(V\). On peut l’obtenir simplement avec les outils déjà présents:

E = QQ^10
E.span(V)

Implanter votre propre fonction baseSEV(V) qui calcule une telle base en se ramenant à du calcul matriciel.

Indications:

  • Utiliser la méthode echelon_form des matrices.

Test d’appartenance d’un vecteur à un sous-espace vectoriel

Soit \(V\) une liste de vecteurs et \(u\) un autre vecteur. On veut tester si \(u\) est dans le sous espace vectoriel engendré par \(V\) :

u = E([1, 2, 5, 3, 0, 1, 6, 3, 0, 5])
u in V

Comme ci-dessus, implanter votre propre fonction appartient(V,u) qui se ramène à du calcul matriciel. On pourra par exemple supposer que \(V\) est sous forme échelon, et calculer la réduction de \(u\) par rapport à \(V\).

Test d’égalité de deux espaces vectoriels

Implanter votre propre fonction SEV_egaux(U, V) qui teste si deux listes deux vecteurs engendrent le même sous espace vectoriel.

Calcul de l’orthogonal d’un sous espace vectoriel

Implanter votre propre fonction SEV_orthogonal(V) pour calculer une base de l’orthogonal de \(\langle V\rangle\), c’est-à-dire l’ensemble des vecteurs \(u\) du dual de \(E\) tel que \(\langle u,v\rangle=0\).

Quel rapport avec la résolution d’équations?

Calcul de la somme et l’intersection de deux sous espace vectoriels

Implanter votre propre fonction SEV_somme(U, V) qui calcule une base de la somme des deux sous-espaces vectoriels \(\langle U\rangle\) et \(\langle V\rangle\).

De même implanter SEV_intersection(U,V) et SEV_en_somme_directe(U,V).

Algèbre linéaire, représentations des monoïdes et Chaînes de Markov

Voir: La bibliothèque de Tsetlin

Ce texte est à approcher comme les textes de l’agrégation: il s’agit d’un menu à la carte; vous pouvez choisir d’étudier certains points, pas tous, pas nécessairement dans l’ordre, et de façon plus ou moins fouillée. Vous pouvez aussi vous poser d’autres questions que celles indiquées plus bas.