Soit un polynôme de degré $n$. Par exemple $n = 7$ avec le polynôme

$$P(x) = 2x^7 -4 x^5 + 3x^4 + x^2 - x + 9$$

On souhaite déterminer les racines de $P$, c'est à dire les solutions $P(x) = 0$.

En général, on ne peut espérer trouver les valeurs exactes de ces racines. On se contentera donc d'approximations.

Supposons que l'on développe une fonction racines(polynome), on aimerait pouvoir fournir directement le polynôme sous forme d'un texte, par exemple :

racines("2x^7 -4 x^5 + 3x^4 + x^2 - x + 9")

Mais, si cette forme est parlante pour nous, elle ne l'est pas du tout pour la machine ! Il nous faudrait une fonction faisant la transformation "2x^7 -4 x^5 + 3x^4 + x^2 - x + 9" → une forme plus adaptée.

On appelle une telle fonction parser, ce qui signifie analyseur. Le programme aurait alors la forme :

racines(polynôme en texte)
  polynome sous une bonne forme = parser(polynôme en texte)
  recherche des racines en utilisant la bonne forme

On décide donc d'une « forme » pour représenter le polynôme de façon à simplifier les nombreux calculs qu'il y aura à faire. Il existe probablement beaucoup de solutions. J'en propose une :

• On utilise un tableau de taille n + 1 avec n le degré du polynôme,
• tableau[i] contient la valeur du coefficient de $x^i$ dans le polynôme.

Ainsi $2x^7 -4 x^5 + 3x^4 + x^2 - x + 9$ → [9, -1, 1, 0, 3, -4, 0, 2]

Notez qu'il serait intéressant de disposer d'une fonction faisant l'inverse :

[9, -1, 1, 0, 3, -4, 0, 2] → "2x^7 -4 x^5 + 3x^4 + x^2 - x + 9"

On peut décider que l'on cherchera les racines sur un certain intervalle $[a\,;\,b]$ défini à l'avance. On peut aussi décider de chercher toutes les racines de $\mathbb{R}$.

Dans le second cas, je vous donne une astuce utile : On sait que les racines, s'il y en a, sont forcément dans un intervalle $[-M\,;\,M]$ avec $M = 1 + max(|a_i|)$ où les $a_i$ sont les coefficients du polynôme.

Donc, même si on cherche les racines sur $\mathbb{R}$, on peut restreindre la recherche à $[-M\,;\,M]$ sans perdre une racine.

Il faudra sûrement calculer $P(x)$ pour des valeurs de $x$. Il faudra donc prévoir une méthode de calcul et dans un souci de modularité, c'est mieux de prévoir une fonction rien que pour cela. Quelque chose comme :

def evaluate(p, x):
    """
    p: représentation du polynome
    x: réel
    renvoie la valeur de p(x)
    """
    ...

Comment trouver les racines d'une fonction ?

Il existe diverses techniques.

• Recherche exhaustive : on calcule $P(x)$ en parcourant tous les $x$,
• Méthode par dichotomie : Si on trouve $a$ et $b$ tels que $P(a)$ et $P(b)$ sont de signe opposés, alors on est certain qu'il y a au moins une racine dans $[a\,;\,b]$
• Méthode de Newton : exploite la dérivée. Très efficace et converge très vite.

On peut faire des mélanges et surtout exploiter ce que vous savez grâce aux mathématiques !

Voici une technique très efficace : Si on pouvait faire le tableau de variations de $P$, on verrait que $P$ est parfois croissant, parfois décroissant. Si $P$ est croissant sur un intervalle $[a\,;\,b]$ alors on est certain qu'il y a au plus une racine sur $[a\,;\,b]$. Idem pour $P$ décroissant.

Pour découper $\mathbb{R}$ en intervalles où $P$ est soit croissant soit décroissant, il faut chercher les changement de signes de $P'(x)$. Donc il faut résoudre $P'(x)=0$.

Donc pour résoudre $P(x) = 0$ on passe par la résolution de $P'(x) = 0$. Mais $P'(x)$ est aussi un polynôme. Il faut donc quelque chose de récursif. La fonction racines(P) appelle racines(derivee_P).

On va s'en sortir car $P'(x)$ est un degré moindre que $P(x)$ si bien que récursivement on va arriver à un polynôme de degré 1 dont il est facile de calculer l'unique racine.

Exemple :

• On cherche les racines de $P(x) = 2x^7 -4 x^5 + 3x^4 + x^2 - x + 9$.
• Pour cela on va chercher les racines de $P'(x) = 14x^6 - 20x^4 + 12x^3 + 2x - 1$
• Pour trouver les racines de P'(x), on cherche les racines de $P''(x) = 84x^5 - 80x^3 + 36 x^2 + 2$
• On cherche donc les racines de $P'''(x) = 420x^4 - 240x^2 + 72x$,
• On cherche donc les racines de $P''''(x) = 1680x^3 - 480x + 72$
• On cherche donc les racines de $P'''''(x) = 5040x^2 - 480$
• On cherche donc les racines de $P''''''(x) = 10080x$. C'est du degré 1, on n'a aucune peine à trouver que l'unique racine est $0$.
• Ayant trouvé la racine de $P''''''(x)$, on pourra trouver les racines de $P'''''(x)$, qui permettront de trouver les racines de $P''''(x)$, … et finalement on remonte aux racines de $P(x)$.

Cela peut sembler compliqué mais on peut l'obtenir simplement :

def racines(P):
    assert not is_zero(P) # fonction is_zero à écrire
    if degree(P) == 0:    # fonction degre à écrire
        return []         # pas de racines
    if degree(P) == 1:
        # là calcul des récines pour le cas de degré 1
        return ...
    # cas général d'un degré >= 2
    derivee_P = derivate(P) # fonction derivate à définir
    racines_derivee = racines(derivee_P)  # appel récursif
    
    # on peut poursuivre la recherche de racines de P
    # en exploitant la connaissance des racines de P'
    ...

Quand on a réussi à résoudre le problème de base, on peut imaginer des développements. Voici quelques idées :

• Donner une représentation graphique de la fonction polynôme en mettant les racines en évidence.
• Donner les intersections entre les courbes de deux fonctions polynôme.
• Donner la liste des minimums locaux d'un polynome