DM 2023-24 : Gram-Schmidt & Bézier

DM 2023-24 : Gram-Schmidt & Bézier#

Exercice 1 : procédé d’orthogonalisation de Gram-Schmidt#

Dans cet exercice, vous allez programmer le procédé d’orthogonalisation de Gram-Schmidt.

Pour cela, étant donné \({\bf u}\) un vecteur de l’espace \(\mathbb{R}^m\), on définit d’abord l’application de projection sur la droite vectorielle engendrée par \({\bf u}\), par :

\[ {\rm proj}_{\bf u} : {\bf v} \mapsto \frac{\langle {\bf u}, {\bf v} \rangle}{ \lVert{\bf u}\rVert^2} \cdot {\bf u} \]

où \(\langle {\bf u}, {\bf v} \rangle\) représente le produit scalaire de \({\bf u}\) et \({\bf v}\), et où \(\lVert{\bf u}\rVert^2 = \langle {\bf u}, {\bf v} \rangle\) est la norme euclidienne au carré.

L” algorithme de Gram-Schmidt prend alors en entrée une famille libre \(({\bf u}_1, \dots, {\bf u}_n)\) de vecteurs de l’espace \(\mathbb{R}^m\), et opère les transformations suivantes :

  1. définir une liste vide res

  2. pour tout \(i\) entre \(1\) et \(n\) :

    1. définir \({\bf a}\) comme \({\bf u}_i\)

    2. pour tout élément \({\bf w}\) de la liste res :

      1. modifier \({\bf a}\) en \({\bf a} - {\rm proj}_{\bf w}({\bf u}_i)\)

      2. ajouter le vecteur \({\bf a}\) obtenu à la fin de la liste res

    3. retourner res

En sortie de l’algorithme, la liste obtenue est une famille libre de vecteurs \(2\) à \(2\) orthogonaux, et qui engendrent le même sous-espace vectoriel que les vecteurs de la liste donnée en entrée de l’algorithme.

Pour plus détails, voir le cours d’Algèbre linéaire 2 pour lequel cet algorithme est au programme, ou encore la page wikipedia https://fr.wikipedia.org/wiki/Algorithme_de_Gram-Schmidt.

Question 1.1. Écrire une fonction projection_orthogonale(u, v) qui prend en entrée deux vecteurs u et v appartenant au même espace vectoriel (avec u non-nul), et qui retourne la projection orthogonale de v sur la droite vectorielle engendrée par u.

# Votre réponse ici

Question 1.2. Écrire une fonction gram_schmidt(famille), qui prend en entrée famille, une liste non-vide de vecteurs (issus du même espace vectoriel) formant une famille libre, et qui retourne la famille orthogonalisée de Gram-Schmidt sous la forme d’une liste de vecteurs.

# Votre réponse ici

Question 1.3. Écrire une fonction est_orthogonale(famille), qui prend en entrée famille, une liste non-vide de vecteurs (issus du même espace vectoriel), et qui teste si la famille des vecteurs est orthogonale (c’est-à-dire si les vecteurs sont 2 à 2 orthogonaux).

# Votre réponse ici

Question 1.4. Écrire une fonction meme_espace(famille1, famille2), qui prend en entrée deux listes de vecteurs famille1 et famille2, et qui teste si ces listes engendrent le même sous-espace vectoriel.

Indication : on pourra agencer ces vecteurs dans 2 matrices, et calculer des sous-espaces vectoriels engendrés par ces 2 matrices.

# Votre réponse ici

Question 1.5. En utilisant les fonctions précédentes, tester sur plusieurs exemples la validité de la fonction gram_schmidt que vous avez programmée.

# Votre réponse ici

Exercice 2 : polynômes de Bernstein, courbes de Bézier, splines#

  1. Cet exercice est constitué de deux parties indépendantes : (i) les questions 1 à 3 qui concernent les polynômes, et (ii) les questions 4 à 8 qui concernent la création de courbes paramétrées appelées splines,

  2. Les questions 7 et 8 sont un peu plus difficiles, car elles manipulent des fonctions d’affichage de manière itérée.

Pour \(0 \le i \le n\), les polynômes de Bernstein \(B_{i,n}(X)\) sont définis par

\[ B_{i,n}(X) = \binom{n}{i} X^i (1-X)^{n-1} \]

Question 2.1. Déclarer dans une variable AA l’anneau des polynômes \(\mathbb{Q}[X]\), et dans une variable X la variable \(X\) associée à cet anneau.

# Votre réponse ici

Question 2.2. Écrire une fonction bernstein(i, n) qui calcule et retourne le polynôme \(B_{i,n}(X)\).

# Votre réponse ici

Question 2.3. Vérifier que pour \(N = 100\) et pour tout \(1 \le i \le n \le N\), l’équation

\[ B_{i,n}(X) = (1-X) B_{i,n-1}(X) + X B_{i-1,n-1}(X) \]

est bien satisfaite.

# Votre réponse ici

Les polynômes de Bernstein permettent de dessiner des courbes de classe \(C^1\) qui relient des points dans le plan. Ces courbes sont appelées des splines cubiques.

Un exemple d’une telle courbe est la suivante (en bleu) :

Image indisponible : voir sur la page web

En pratique, on construit des splines morceaux par morceaux en reliant les points par des courbes qui « se recollent bien » (de manière \(C^1\)). Ces morceaux de courbes sont appelées courbes de Bézier. En voici un exemple, puis une explication :

Image indisponible : voir sur la page web

Construction d’une courbe de Bézier. Considérons deux points du plan \({\bf A}\) et \({\bf D}\) (appelés points de passage, en rouge), ainsi que deux points du plan \({\bf B} \ne {\bf A}\) et \({\bf C} \ne {\bf D}\), en vert, appelés point de contrôle.

La courbe de Bézier (d’ordre 3) associée est une courbe paramétrée d’équation

\[ {\bf M}(t) = \binom{x(t)}{y(t)} = (1-t)^3 {\bf A} + 3t(1-t)^2 {\bf B} + 3t^2(1-t) {\bf C} + t^3 {\bf D} \]

où \(t\) parcourt le segment \([0,1]\).

Comme leurs noms l’indique :

  1. la courbe de Bézier passe par les points \({\bf A}\) et \({\bf D}\) (en \(t=0\) et en \(t=1\)) ;

  2. les tangentes à la courbe de Bézier sont contrôlées par les vecteurs \(\vec{\bf AB}\) et \(\vec{\bf CD}\).

Question 2.4. Déclarer une variable d’expression t, puis écrire une fonction courbe_bezier(A, B, C, D) qui prend en entrée deux points de passages A et D, deux points de contrôle B et C, et qui retourne la fonction \({\bf M}(t)\) comme décrite ci-dessus.

Remarque : il est tout à fait possible de multiplier une variable t par un vecteur.

# Votre réponse ici

Question 2.5. Tracé de la courbe de Bézier.

  1. Créer les vecteurs correspondant aux points du plan \({\bf A} = (0,0)\), \({\bf B} = (1,0)\), \({\bf C} = (5/4, 1/2)\) et \({\bf D} = (1,1)\).

  2. Calculer M, la fonction paramétrique associée à courbe de Bézier de points \({\bf A}\), \({\bf B}\), \({\bf C}\) et \({\bf D}\) (comme ci-dessus).

  3. Grâce aux fonctions d’affichage points et parametric_plot(M, (t,0,1)), afficher sur un même graphique :

    • en rouge les points \({\bf A}\) et \({\bf D}\)

    • en vert les points \({\bf B}\) et \({\bf C}\)

    • en bleu la courbe de Bézier associée à \({\bf A}\), \({\bf B}\), \({\bf C}\) et \({\bf D}\).

Indication : pour plus de lisibilité, retirer l’affichage des axes avec l’option axes=False de la méthode show()

# Votre réponse ici

Tracé de la spline. Avant de tracer une spline, nous allons d’abord essayer de tracer dans le plan les points de passage et les points de contrôles désirés.

Pour cela, nous allons avoir besoin de créer le point symétrique d’un point de contrôle par rapport à son point de passage.

Question 2.6. Écrire une fonction symetrique(centre, point), qui prend en entrée deux vecteurs du plan centre et point, et qui calcule le symétrique de point par rapport à centre.

# Votre réponse ici

Question 2.7. Écrire une fonction affiche_points(passage, controle), qui prend en entrée deux listes de vecteurs du plan passage et controle représentant les points de passage et de contrôle de la spline, et qui retourne un affichage de ces points sous la forme présentée en début d’exercice (les points rouges et verts, et les segments verts). Pour tracer un segment entre un point \(P\) et un point \(Q\), on utilisera la fonction d’affichage line([P, Q], color='green').

Pour tester on utilisera les points de passages :

\[ \big\{\; (0,0), (1,1), (2,2), (3,0)\; \big\} \]

et les points de contrôle

\[ \big\{\; (1,0), (3/4, 3/2), (3,5/3), (3,-1)\; \big\} \]
# Votre réponse ici

On a vu qu’une spline cubique est un raccordement de courbes de Bézier entre différents points.

Question 2.8. Écrire une fonction affiche_spline(passage, controle) qui affiche la spline voulue en « superposant » les affichages de différentes courbes de Bézier. On affichera également les points de passage et de contrôle, comme à la question précédente.

# Votre réponse ici
Contenu