ALGORITHMES POUR LES POLYNÔMES

1 - Représentation par une liste de coefficients


?

def ?
Nous en aurons besoin : construisons le triangle de Pascal : c'est une liste de listes, qu'on notera T, telle que T[n][k] est égal au coefficient binomial « \(k\) parmi \(n\) ». Et le lien avec les polynômes est immédiat : la formule du binôme affirme (en particulier) que \[ (\mathrm{X} + 1)^n = \sum_{k = 0}^n \begin{pmatrix}n \\ k\end{pmatrix} \mathrm{X}^k, \] autrement dit T[n] est également la liste qui représente le polynôme \((\mathrm{X} + 1)^n\), avec la convention qu'on a choisie.
    Pour construire le triangle, on utilise la formule qui permet de déduire chaque ligne de celle qui la précède (la fameuse formule du triangle de Pascal).

def TriangleDePascal(n) :

a) Évaluation

?

def ?

b) Opérations sur les polynômes

?

def ?

c) Composition

?

def ?

d) Une application : sommes des puissances

Commençons par quelques rappels : pour chaque entier naturel \(n\) on a \[ \underset{\text{$n$ fois}}{\underbrace{1 + 1 + 1 + \dots + 1}} = n, \] \[ 1 + 2 + 3 + \dots + n = \frac{n(n + 1)}{2}, \] \[ 1^2 + 2^2 + 3^2 + \dots + n^2 = \frac{n(n + 1)(2n + 1)}{6}, \] ce qui laisse penser que plus généralement la somme \[ s_p(n) = 1^p + 2^p + 3^p + \dots + n^p \] est un polynôme en \(n\) (et il y a même de bonnes raisons de penser que son terme dominant est \(n^{p+1}/(p + 1)\), en faisant une petite analogie primitivesque, mais passons).
    Pour prouver notre affirmation, examinons astucieusement \[ s_{p+1}(n + 1) = \sum_{k = 0}^{n} (k+1)^{p+1} = \sum_{k = 0}^{n} \sum_{\ell = 0}^{p + 1} \begin{pmatrix}p + 1 \\ \ell\end{pmatrix} k^\ell, \] la première somme étant obtenue par un changement d'indice et la seconde (qui est en fait une double-somme) en utilisant la formule du binôme. Permutons les petits accordéons, et sortons les deux premiers termes : \[ \sum_{\ell = 0}^{p + 1} \begin{pmatrix}p + 1 \\ \ell\end{pmatrix} \sum_{k = 0}^{n} k^\ell = \sum_{\ell = 0}^{p + 1} \begin{pmatrix}p + 1 \\ \ell\end{pmatrix} s_\ell(n) = s_{p+1}(n) + (p+1)s_p(n) + \sum_{\ell = 0}^{p - 1} \begin{pmatrix}p + 1 \\ \ell\end{pmatrix} s_\ell(n). \] Rappelons que tout ceci est égal à ce dont on est parti, à savoir \(s_{p+1}(n+1)\). En retranchant aux deux membres \(s_{p+1}(n)\), on fait apparaître à gauche \[ s_{p+1}(n+1) - s_{p+1}(n) = (n + 1)^{p + 1} \] et à droite une formule qui fait intervenir seulement \(s_p(n)\) et des \(s_\ell(n)\) avec \(\ell < p\) : donc une formule de récurrence ! En arrangeant tout celà on obtient finalement \[ s_p(n) = \frac{1}{p + 1} \times \left( (n+1)^{p+1} - \sum_{\ell = 0}^{p - 1} \begin{pmatrix}p + 1 \\ \ell\end{pmatrix} s_\ell(n)\right). \] En raisonnant par récurrence forte, on obtient alors la propriété suivante : \(s_p(n)\) est un polynôme en \(n\), de degré \(p+1\), et de coefficient dominant \(1/(p+1)\).
    Mais ce qui va nous intéresser ici, c'est d'exploiter la formule de récurrence pour calculer (la liste qui représente) le polynôme \(s_p(n)\).

def ?
?

def ?
?

def ?
?


2 - Arithmétique dans \(\mathbf{Q}[\mathrm{X}]\)

a) Division euclidienne

?

def ?

b) Algorithme d'Euclide étendu

?

def ?
?

def ?

c) Polynômes sans facteur carré

?

def ?
?

def ?

d) Division suivant les puissances croissantes

?

def ?
?


3 - Recherche des racines

a) Localisation des racines

On a déjà rencontré cette idée avec la dichotomie, où l'on avait besoin d'un encadrement « de départ ». Pour trouver les racines (complexes) d'un polynôme, il est donc naturel de commencer par une estimation qui majore leurs modules.

Propriété (localisation des racines).

Soit \(\mathrm{P}(\mathrm{X}) = a_0 + a_1\mathrm{X} + a_2\mathrm{X}^2 + \dots + a_d\mathrm{X}^d\) un polynôme (à coefficients complexes) de degré \(d \geq 1\) (donc \(a_d \neq 0\)). Si \(z\) est une racine de \(\mathrm{P}\), alors \[ |z| < 1 + \underset{0 \leq i \leq d-1}{\mathrm{max}}\; \frac{|a_i|}{|a_d|}. \]

def RayonMaximal(P) :
    m = 0
    for i in range(len(P) - 1) :
        y = abs(P[i])
        if y > m :
            m = y
    return m / abs(P[-1])

b) Méthode de Newton

?

from random import random as Aléa
from numpy import exp, pi as π
def CpxAléa(r_max = 1) :
    r = Aléa() * r_max
    θ = Aléa() * (2 * π)
    return r * exp(1j * θ)

?

def Newton(P, dP, z0) :
    z = z0
    h = P(z) / dP(z)
    while abs(h) > 1e-10 :
        z -= h
        h = P(z) / dP(z)
    return z - h

?

def AjouterRacine(L, z) :
    i = 0
    while i < len(L) and abs(L[i] - z) > 1e-9 :
        i += 1
    if i == len(L) :
        L.append(z)

?

def RacinesComplexes(P) :
?

>>>

c) Racines réelles

?

def ?
?

def ?
?

4 - La librairie numpy.polynomial

a) Manipulations de base

?

def ?

b) Polynômes de Lagrange

?

def ?

c) Polynômes de Bernoulli

?

def ?