{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "9fa57edc",
   "metadata": {},
   "source": [
    "# Feuille d'exercices 8\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "```{admonition} Objectifs\n",
    "* Polynômes\n",
    "* Réduction matricielle\n",
    "```\n",
    "\n",
    "\n",
    "## Exercice 1 : Manipulation de polynômes\n",
    "\n",
    "\n",
    "**Question 1 :** Effectuer les opérations suivantes :\n",
    "1. Créer l'anneau de polynômes $\\mathbb{Q}[X]$ et nommer `X` la variable correspondante\n",
    "1. Créer les polynômes $P(X) = 2X^4 - \\frac{1}{2}X - \\frac{3}{2}$ et $Q(X) = X^2 - 3X + 2$.\n",
    "1. Calculer $S(X) = -2 P(X) + Q(2X^2+1)$.\n",
    "1. Calculer $R(X) = {\\rm pgcd}(P(X), Q(X))$.\n",
    "1. Vérifier que $P(X)$ est bien divisible par $R(X)$, et calculer le quotient correspondant."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3e32d8d0",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7004d7d3",
   "metadata": {},
   "source": [
    "**Question 2 :** Dérivées successives d'un polynôme aléatoire.\n",
    "1. En utilisant la méthode `.random_element()` de l'anneau de polynômes, construire un polynôme aléatoire $P(X)$ à coefficients entiers.\n",
    "1. Obtenir le degré $d$ de $P(X)$.\n",
    "1. Vérifier, à l'aide d'une boucle, que la dérivée $d$-ème de $P(X)$ est égale au polynôme constant $(d!) \\times a$, où $a$ est le coefficient dominant du polynôme $P(X)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a3f4ec56",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "29176d3f",
   "metadata": {},
   "source": [
    "## Exercice 2 : autour du polynôme caractéristique d'une matrice\n",
    "\n",
    "\n",
    "**Question 1 :** Construire la matrice ${\\bf M}$ suivante, puis calculer son polynôme caractéristique $P(X)$.\n",
    "\n",
    "$$\n",
    "{\\bf M} = \\left(\\begin{array}{rrr}\n",
    "-1 & 0 & 0 \\\\\n",
    "-2 & 1 & 4 \\\\\n",
    "-8 & 0 & 3\n",
    "\\end{array}\\right)\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "136fa4c1",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f6276481",
   "metadata": {},
   "source": [
    "**Question 2 :** Calculer les valeurs propres de la matrice ${\\bf M}$ (avec la méthode `eigenvalues`), puis vérifier que le polynôme caractéristique s'annule sur ces valeurs propres."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5f09ff95",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f101b4c5",
   "metadata": {},
   "source": [
    "**Question 3 :** Vérifier que, si $\\lambda$ est une des valeurs propres de ${\\bf M}$, alors le rang de ${\\bf M} - \\lambda {\\bf I_3}$ est $2$, où ${\\bf I_3}$ est la matrice identité."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e18e39c7",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7979de3f",
   "metadata": {},
   "source": [
    "**Question 4 :** Vérifier que $P({\\bf M}) = {\\bf 0}$. Autrement dit, vérifier que si $P(X)$ s'écrit $a_2 X^2 + a_1 X + a_0$, alors la matrice $a_2 {\\bf M}^2 + a_1 {\\bf M} + a_0 {\\bf I_3}$ est égale à la matrice nulle. \n",
    "\n",
    "**Remarque .** On dit alors que $P$ est un polynôme annulateur de la matrice ${\\bf M}$. Le polynôme caractéristique est toujours un polynôme annulateur de sa matrice : c'est l'objet du [théorème de Cayley--Hamilton](https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_de_Cayley-Hamilton)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "02373fee",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2fa3030e",
   "metadata": {},
   "source": [
    "## Exercice 3 : racines de polynômes\n",
    "\n",
    "**Question 1 :** Construire le polynôme\n",
    "\n",
    "$$\n",
    "    P(X) = 2X^{6} - 3X^{5} - 13X^{4} + 29X^{3} - 27X^{2} + 32X - 12\n",
    "$$\n",
    "\n",
    "en tant que polynôme à coefficients entiers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c131f3f8",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3e96e882",
   "metadata": {},
   "source": [
    "On peut obtenir les racines d'un polynôme dans une structure algébrique autre que celle de ses coefficients, en spécifiant la structure en paramètre de la méthode `roots`. Par exemple, `P.roots(RR)` donne les racines de `P` dans le corps de nombres flottants.\n",
    " \n",
    "**Question 2 :** Quelles sont les racines de $P$ dans :\n",
    "- l'anneau des entiers ?\n",
    "- le corps des rationnels ?\n",
    "- le anneau des éléments \"symboliques\" (qui contient le nombre complexe $i$), représenté par la variable `SR` ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4c3dfa1a",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bcafe75e",
   "metadata": {},
   "source": [
    "**Question 3 :** Vérifier que $P(X) = \\alpha \\prod_{i=1}^k (X - x_i)^{m_i}$, où :\n",
    "- $\\alpha$ est le coefficient dominant de $P$,\n",
    "- les $(x_i)$ sont les racines de $P$ dans le corps des nombres complexes `CC`,\n",
    "- les $(m_i)$ sont les multiplicités de ces racines."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9c5654cd",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7f090157",
   "metadata": {},
   "source": [
    "## Exercice 4 : interpolation de Lagrange\n",
    "\n",
    "\n",
    "Soient $x_0, x_1, \\dots, x_{n-1}$ des éléments $2$ à $2$ distincts d'un corps (rationnels ou complexes par exemple), et $y_0, y_1, \\dots, y_{n-1}$ d'autres éléments de ce même corps (cette fois, pas nécessairement distincts). Le **problème de l'interpolation** consiste à calculer un polynôme $P(X)$ de degré $\\le n-1$ tel que\n",
    "\n",
    "$$\n",
    "    P(x_i) = y_i, \\quad \\forall i \\in \\{0, \\dots, n-1 \\}.\n",
    "$$\n",
    "\n",
    "Pour cela, il existe plusieurs méthodes, la plus connue étant la méthode de Lagrange.\n",
    "\n",
    "Pour $0 \\le i \\le n-1$, on définit le $i$-ème polynôme de Lagrange associé au vecteur $\\mathbf{x} = (x_0, \\dots, x_{n-1})$ comme le polynôme :\n",
    "\n",
    "$$\n",
    "    L_i(X) = \\prod_{j \\in \\{0, \\dots, n-1\\} \\setminus \\{ i \\}} \\frac{X - x_j}{x_i - x_j}.\n",
    "$$\n",
    "\n",
    "**Question 1 :** Écrire une fonction `polynome_lagrange(R, vec_x, i)` qui prend en entrée un anneau de polynômes `R`, une liste de points d'évaluation `vec_x` de longueur $n$ et un entier `i` entre $0$ et $n-1$, et qui calcule $L_i(X)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0d3ac73b",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06d74c1a",
   "metadata": {},
   "source": [
    "Les polynômes $L_i(X)$ ainsi construits forment une **base d'interpolation**. On peut ainsi calculer le polynôme interpolateur $P$ des $(x_i, y_i)$ grâce à la formule :\n",
    "\n",
    "$$\n",
    "    P(X) = \\sum_{i=0}^{n-1} y_i L_i(X)\n",
    "$$\n",
    "\n",
    "\n",
    "**Question 2 :** Écrire une fonction `polynome_interpolateur(R, vec_x, vec_y)` qui retourne le polynôme interpolateur dans l'anneau de polynômes `R`, associé aux listes de points d'évaluation `vec_x` (les valeurs $x_0, \\dots, x_{n-1}$) et de valeurs d'évaluation `vec_y` (les valeurs $y_0, \\dots, y_{n-1}$)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "77bca0d0",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7d84f98f",
   "metadata": {},
   "source": [
    "**Question 3 :** Afficher dans un même graphique :\n",
    "1. une liste de $8$ points du plan de la forme $(x_i, y_i)$ où $x_i = i$ et $y_i$ est un entier tiré aléatoirement entre $-20$ et $20$,\n",
    "2. le polynôme interpolateur des $(x_i)$ et $(y_i)$.\n",
    "\n",
    "On vérifiera que le tracé du polynôme passe bien par les points du plan qui on été tirés."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c9904569",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Sagemath",
   "language": "python",
   "name": "sagemath"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}