{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "44f5a9f6",
   "metadata": {},
   "source": [
    "# DM 2023-24 : Gram-Schmidt & Bézier\n",
    "\n",
    "\n",
    "## Exercice 1 : procédé d'orthogonalisation de Gram-Schmidt\n",
    "\n",
    "Dans cet exercice, vous allez programmer le **procédé d'orthogonalisation de Gram-Schmidt**.\n",
    "\n",
    "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 :\n",
    "\n",
    "$$\n",
    "    {\\rm proj}_{\\bf u} : {\\bf v} \\mapsto \\frac{\\langle {\\bf u}, {\\bf v} \\rangle}{ \\lVert{\\bf u}\\rVert^2} \\cdot {\\bf u}\n",
    "    $$\n",
    "    \n",
    "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é.\n",
    "    \n",
    "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 :\n",
    "1. définir une liste vide `res`\n",
    "1. pour tout $i$ entre $1$ et $n$ :\n",
    "   1. définir ${\\bf a}$ comme ${\\bf u}_i$\n",
    "   1. pour tout élément ${\\bf w}$ de la liste `res` :\n",
    "      1. modifier ${\\bf a}$ en ${\\bf a} - {\\rm proj}_{\\bf w}({\\bf u}_i)$ \n",
    "      1. ajouter le vecteur ${\\bf a}$ obtenu à la fin de la liste `res`\n",
    "   1. retourner `res`\n",
    "    \n",
    "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.\n",
    "    \n",
    "*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.*\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "**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`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f2ab5416",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6aa96adb",
   "metadata": {},
   "source": [
    "**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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "21945e71",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5c4e51ab",
   "metadata": {},
   "source": [
    "**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)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7aa33844",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1d15e34b",
   "metadata": {},
   "source": [
    "**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.\n",
    "\n",
    "*Indication : on pourra agencer ces vecteurs dans 2 matrices, et calculer des sous-espaces vectoriels engendrés par ces 2 matrices.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4a436026",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "caeaa260",
   "metadata": {},
   "source": [
    "**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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e1f70269",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "665773bc",
   "metadata": {},
   "source": [
    "## Exercice 2 : polynômes de Bernstein, courbes de Bézier, splines\n",
    "\n",
    "\n",
    "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*,\n",
    "2. Les questions 7 et 8 sont un peu plus difficiles, car elles manipulent des fonctions d'affichage de manière itérée.\n",
    "\n",
    "Pour $0 \\le i \\le n$, les polynômes de Bernstein $B_{i,n}(X)$ sont définis par\n",
    "\n",
    "$$\n",
    "B_{i,n}(X) = \\binom{n}{i} X^i (1-X)^{n-1}\n",
    "$$\n",
    "\n",
    "\n",
    "**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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "828dc33a",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8dd3cfda",
   "metadata": {},
   "source": [
    "**Question 2.2.** Écrire une fonction `bernstein(i, n)` qui calcule et retourne le polynôme $B_{i,n}(X)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8b2701d6",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "785ebadf",
   "metadata": {},
   "source": [
    "**Question 2.3.** Vérifier que pour $N = 100$ et pour tout $1 \\le i \\le n \\le N$, l'équation\n",
    "\n",
    "$$\n",
    "B_{i,n}(X) = (1-X) B_{i,n-1}(X) + X B_{i-1,n-1}(X)\n",
    "$$\n",
    "\n",
    "est bien satisfaite."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "80f0e615",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0535d960",
   "metadata": {},
   "source": [
    "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**.\n",
    "\n",
    "Un exemple d'une telle courbe est la suivante (en bleu) :\n",
    "\n",
    "![Image indisponible : voir sur la page web](./img/spline.png)\n",
    "\n",
    "\n",
    "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 :\n",
    "\n",
    "![Image indisponible : voir sur la page web](./img/bezier.png)\n",
    "\n",
    "\n",
    "**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.\n",
    "\n",
    "La **courbe de Bézier** (d'ordre 3) associée est une courbe paramétrée d'équation\n",
    "\n",
    "$$\n",
    "{\\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}\n",
    "$$\n",
    "\n",
    "où $t$ parcourt le segment $[0,1]$.\n",
    "\n",
    "Comme leurs noms l'indique :\n",
    "1. la courbe de Bézier passe par les points ${\\bf A}$ et ${\\bf D}$ (en $t=0$ et en $t=1$) ;\n",
    "1. les tangentes à la courbe de Bézier sont contrôlées par les vecteurs $\\vec{\\bf AB}$ et $\\vec{\\bf CD}$.\n",
    "\n",
    "\n",
    "**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.\n",
    "\n",
    "*Remarque : il est tout à fait possible de multiplier une variable `t` par un vecteur.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c64dc3ea",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "101b33a7",
   "metadata": {},
   "source": [
    "**Question 2.5.** Tracé de la courbe de Bézier. \n",
    "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)$.\n",
    "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).\n",
    "3. Grâce aux fonctions d'affichage `points` et `parametric_plot(M, (t,0,1))`, afficher sur un même graphique :\n",
    "    - en rouge les points ${\\bf A}$ et ${\\bf D}$\n",
    "    - en vert les points ${\\bf B}$ et ${\\bf C}$\n",
    "    - en bleu la courbe de Bézier associée à ${\\bf A}$, ${\\bf B}$, ${\\bf C}$ et ${\\bf D}$.\n",
    "    \n",
    "*Indication : pour plus de lisibilité, retirer l'affichage des axes avec l'option `axes=False` de la méthode `show()`*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9b261781",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "241ec73d",
   "metadata": {},
   "source": [
    "**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. \n",
    "\n",
    "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.\n",
    "\n",
    "**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`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ea65d277",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "41d78654",
   "metadata": {},
   "source": [
    "**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')`.\n",
    "\n",
    "Pour tester on utilisera les points de passages :\n",
    "\n",
    "$$\n",
    "\\big\\{\\; (0,0), (1,1), (2,2), (3,0)\\; \\big\\}\n",
    "$$\n",
    "\n",
    "et les points de contrôle\n",
    "\n",
    "$$\n",
    "\\big\\{\\; (1,0), (3/4, 3/2), (3,5/3), (3,-1)\\; \\big\\}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3d24af22",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d0180008",
   "metadata": {},
   "source": [
    "On a vu qu'une **spline cubique** est un raccordement de courbes de Bézier entre différents points.\n",
    "\n",
    "**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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "941fba5f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Sagemath",
   "language": "python",
   "name": "sagemath"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}