{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "2363c0e8",
   "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": "6716a1a1",
   "metadata": {},
   "outputs": [],
   "source": [
    "POLY.<X> = PolynomialRing(QQ, \"X\")\n",
    "P = 2*X**4 - (1/2)*X -(3/2)\n",
    "Q = X**2 - 3*X + 2\n",
    "print(\"P =\", P)\n",
    "print(\"Q =\", Q)\n",
    "S = -2 * P(X) + Q(X**2+1)\n",
    "print(\"S =\", S)\n",
    "R = gcd(P, Q)\n",
    "print(\"R =\", R)\n",
    "print(P % R == 0)\n",
    "print(\"quotient =\", P // R)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "26922974",
   "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": "f5b38a40",
   "metadata": {},
   "outputs": [],
   "source": [
    "POLY_ZZ.<X> = PolynomialRing(ZZ, \"X\")\n",
    "P = POLY_ZZ.random_element(6)\n",
    "print(\"P =\", P)\n",
    "\n",
    "d = P.degree()\n",
    "print(\"d =\", d)\n",
    "\n",
    "Q = P\n",
    "for i in range(d):\n",
    "    Q = Q.derivative()\n",
    "print(Q)\n",
    "c = factorial(d) * P.constant_coefficient()\n",
    "print(c)\n",
    "print(Q == factorial(d) * P.constant_coefficient())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5e182eac",
   "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": "606a1baf",
   "metadata": {},
   "outputs": [],
   "source": [
    "M = matrix(QQ, [[-1, 0, 0], [-2, 1, 4], [-8, 0, 3]])\n",
    "P = M.characteristic_polynomial()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "66c7ea81",
   "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": "3a32fca6",
   "metadata": {},
   "outputs": [],
   "source": [
    "valeurs_propres = M.eigenvalues()\n",
    "print(all(P(s) == 0 for s in valeurs_propres))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a3d285ac",
   "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": "0a877dca",
   "metadata": {},
   "outputs": [],
   "source": [
    "I3 = matrix.identity(QQ, 3)\n",
    "for s in valeurs_propres:\n",
    "    print( (M - s*I3).rank() )"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "af96769c",
   "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": "a224b5b4",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(P(M))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d6fce904",
   "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": "f103cfc2",
   "metadata": {},
   "outputs": [],
   "source": [
    "R = PolynomialRing(ZZ, \"X\")\n",
    "X = R.gen()\n",
    "P = 2*X**6 - 3*X**5 - 13*X**4 + 29*X**3 - 27*X**2 + 32*X - 12"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c229d8d6",
   "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": "3d5c674b",
   "metadata": {},
   "outputs": [],
   "source": [
    "racines_ZZ = P.roots(ZZ)\n",
    "print(\"Dans Z :\", racines_ZZ)\n",
    "\n",
    "racines_QQ = P.roots(QQ)\n",
    "print(\"Dans Q :\", racines_QQ)\n",
    "\n",
    "racines_SR = P.roots(SR)\n",
    "print(\"Dans SR :\", racines_SR)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8d5297dd",
   "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": "cfd16d4f",
   "metadata": {},
   "outputs": [],
   "source": [
    "Q = 1\n",
    "racines_SR = P.roots(CC)\n",
    "for i in range(len(racines_SR)):\n",
    "    racine = racines_SR[i]\n",
    "    facteur = (X - racine[0])**racine[1]\n",
    "    Q *= facteur\n",
    "Q = P.leading_coefficient() * Q\n",
    "print(Q == P)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e8b41f91",
   "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": "865b52d4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def polynome_lagrange(R, vec_x, i):\n",
    "    X = R.gen()\n",
    "    res = R.one()\n",
    "    n = len(vec_x)\n",
    "    for j in range(n):\n",
    "        if j != i:\n",
    "            res = res * (X - vec_x[j])/(vec_x[i] - vec_x[j])\n",
    "    return res"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "15950aa0",
   "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": "2269f931",
   "metadata": {},
   "outputs": [],
   "source": [
    "def polynome_interpolateur(R, vec_x, vec_y):\n",
    "    n = len(vec_x)\n",
    "    res = R.zero()\n",
    "    for i in range(n):\n",
    "        res += vec_y[i] * polynome_lagrange(R, vec_x, i)\n",
    "    return res"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c1e28de1",
   "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": "1119418e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def teste_et_affiche():\n",
    "    n = 8\n",
    "    R = PolynomialRing(QQ, \"X\")\n",
    "    \n",
    "    # on crée les vecteurs x et y \n",
    "    vec_x = [ i for i in range(n) ]\n",
    "    vec_y = [ randint(-20, 20) for i in range(n) ]\n",
    "    \n",
    "    # on calcule le polynome interpolateur de Lagrange\n",
    "    P = polynome_interpolateur(R, vec_x, vec_y)\n",
    "    print(P)\n",
    "    \n",
    "    # on affiche les points et le polynome sur un même graphique\n",
    "    pl = points([[vec_x[i], vec_y[i]] for i in range(n)], color=\"red\", size=40)\n",
    "    pl += plot(P, 0, n-1)\n",
    "    pl.show()\n",
    "\n",
    "teste_et_affiche()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Sagemath",
   "language": "python",
   "name": "sagemath"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}