Division synthétique

En algèbre, la division synthétique est une méthode de division euclidienne de polynômes demandant moins d'écritures et de calculs que l'algorithme traditionnel. Elle généralise au cas de polynômes quelconques la méthode de Ruffini-Horner.

Division par Modèle:Math

Modèle:Article détaillé Dans le cas de la division euclidienne d'un polynôme P(x) par (x-a)), la division synthétique est essentiellement équivalente à la méthode de Horner. Ainsi, sur l'exemple de la réduction de

$\frac{x^3-12x^2-42}{x-3}$,

la division synthétique consiste à écrire les coefficients du dividende (en mettant des zéros pour les termes absents)

$\begin{array}{cc}\begin{array}{c}\\ \end{array}& \begin{array}{cccc}1& -12& 0& -42\\ & & & \end{array}\end{array}$,

puis à écrire à gauche a, l'opposé du coefficient constant du diviseur (ici, 3)

$\begin{array}{cc}\begin{array}{c}\\ 3\end{array}& \begin{array}{cccc}1& -12& 0& -42\\ & & & \end{array}\end{array}$.

On descend ensuite le premier coefficient à gauche vers la dernière rangée :

$\begin{array}{cc}\begin{array}{c}\\ 3\\ \end{array}& \begin{array}{cccc}1& -12& 0& -42\\ & & & \\ 1& & & \end{array}\end{array}$,

puis on multiplie ce nombre par a, et on écrit le résultat dans la rangée intermédiaire, et dans la colonne à droite

$\begin{array}{cc}\begin{array}{c}\\ 3\\ \end{array}& \begin{array}{cccc}1& -12& 0& -42\\ & 3& & \\ 1& & & \end{array}\end{array}$,

on additionne dans cette colonne

$\begin{array}{cc}\begin{array}{c}\\ 3\\ \end{array}& \begin{array}{cccc}1& -12& 0& -42\\ & 3& & \\ 1& -9& & \end{array}\end{array}$

et on recommence jusqu'à la fin du tableau (deux autres étapes ici)

$\begin{array}{cc}\begin{array}{c}\\ 3\\ \end{array}& \begin{array}{cccc}1& -12& 0& -42\\ & 3& -27& -81\\ 1& -9& -27& -123\end{array}\end{array}$

Le reste est le nombre le plus à droite (ici, -123) et le quotient a pour coefficients les autres nombres, ici le quotient est donc $x^2-9x-27$. On en déduit que : $x^3-12x^2-42=(x^2-9x-27)(x-3)-123$, et donc que :

$\frac{x^3-12x^2-42}{x-3}=x^2-9x-27-\frac{123}{x-3}$.

Évaluation en a

La valeur de $P(x)$ en $a$ est le reste de la division euclidienne de P par $(x-a)$, puisque $P(x)=(x-a)Q(x)+R$, et donc que $P(a)=(a-a)Q(a)+R=R$. Cette méthode de calcul de $P(a)$ demande environ moitié moins de multiplications que la méthode naïve.

Division synthétique par un polynôme quelconque

Cas d'un polynôme unitaire

La méthode précédente se généralise à la division par un polynôme unitaire D(x) quelconque, avec une légère modification indiquée ici en gras. Dans l'exemple

$\frac{x^3-12x^2-42}{x^2+x-3}$,

on écrit les coefficients du dividende sur la première ligne

$\begin{array}{cccc}1& -12& 0& -42\end{array}$,

et les coefficients de l'opposé du diviseur $-D(x)=-x^2-x+3$ (sauf le premier) dans une diagonale montant vers la droite, comme ci-dessous :

$\begin{array}{cc}\begin{array}{c}\\ & 3\\ -1& \end{array}& \begin{array}{cccc}1& -12& 0& -42\\ & & & \\ & & & \end{array}\end{array}$

Comme précédemment, on descend ensuite le premier coefficient à gauche vers la dernière rangée :

$\begin{array}{cc}\begin{array}{c}\\ & 3\\ -1& \\ \end{array}& \begin{array}{cccc}1& -12& 0& -42\\ & & & \\ & & & \\ 1& & & \end{array}\end{array}$.

On multiplie ensuite ce coefficient par toute la diagonale de gauche, et on place les résultats en diagonale et sur la droite du nombre descendu :

$\begin{array}{cc}\begin{array}{c}\\ & 3\\ -1& \\ \end{array}& \begin{array}{cccc}1& -12& 0& -42\\ & & 3& \\ & -1& & \\ 1& & & \end{array}\end{array}$

On additionne tous les nombres de la colonne immédiatement à droite.

$\begin{array}{cc}\begin{array}{c}\\ & 3\\ -1& \\ \end{array}& \begin{array}{cccc}1& -12& 0& -42\\ & & 3& \\ & -1& & \\ 1& -13& & \end{array}\end{array}$,

et on recommence ces deux étapes jusqu'au moment où la diagonale suivante dépasserait le dernier coefficient du dividende.

$\begin{array}{cc}\begin{array}{c}\\ & 3\\ -1& \\ \end{array}& \begin{array}{cccc}1& -12& 0& -42\\ & & 3& -39\\ & -1& 13& \\ 1& -13& 16& \end{array}\end{array}$

On termine d'additionner les colonnes restantes éventuelles :

$\begin{array}{cc}\begin{array}{c}\\ & 3\\ -1& \\ \end{array}& \begin{array}{cccc}1& -12& 0& -42\\ & & 3& -39\\ & -1& 13& \\ 1& -13& 16& -81\end{array}\end{array}$

Le reste est formé du même nombre de colonnes que les diagonales (ici 2), ce qui donne $x^3-12x^2-42=(x^2+x-3)(x-13)+16x-81$, ou encore

$\frac{x^3-12x^2-42}{x^2+x-3}=x-13+\frac{16x-81}{x^2+x-3}$

Cas général

On peut évidemment commencer par diviser D(x) par son coefficient dominant a (lorsqu'on travaille dans un anneau, si a est inversible), puis en multipliant le quotient obtenu par 1/a (mais pas le reste) ; en pratique, il est plus efficace et plus sûr d'effectuer la division à chaque étape, après addition, mais avant de multiplier les diagonales, comme on le voit dans l'exemple suivant :

$\frac{6x^3+5x^2-7}{3x^2-2x-1}$

On ajoute une ligne supplémentaire correspondant à la division (sans changer le signe, cette fois) :

$\begin{array}{c}\begin{array}{c}\\ & 1& \\ 2& & \\ \\ & & /3\end{array}\begin{array}{cccc}6& 5& 0& -7\\ & & & \\ & & & \\ & & & \\ & & & \end{array}\end{array}$

Après chaque étape de Modèle:Citation, la valeur est divisée par a :

$\begin{array}{c}\begin{array}{c}\\ & 1& \\ 2& & \\ \\ & & /3\end{array}\begin{array}{cccc}6& 5& 0& -7\\ & & & \\ & & & \\ 6& & & \\ 2& & & \end{array}\end{array}$

et c'est cette valeur qui est utilisée pour remplir la diagonale suivante :

$\begin{array}{c}\begin{array}{c}\\ & 1& \\ 2& & \\ \\ & & /3\end{array}\begin{array}{cccc}6& 5& 0& -7\\ & & 2& \\ & 4& & \\ 6& & & \\ 2& & & \end{array}\end{array}$

On recommence la séquence addition-division, dans la colonne suivante :

$\begin{array}{c}\begin{array}{c}\\ & 1& \\ 2& & \\ \\ & & /3\end{array}\begin{array}{cccc}6& 5& 0& -7\\ & & 2& \\ & 4& & \\ 6& 9& & \\ 2& 3& & \end{array}\end{array}$

puis on construit la nouvelle diagonale :

$\begin{array}{c}\begin{array}{c}\\ & 1& \\ 2& & \\ \\ & & /3\end{array}\begin{array}{cccc}6& 5& 0& -7\\ & & 2& 3\\ & 4& 6& \\ 6& 9& & \\ 2& 3& & \end{array}\end{array}$.

Lorsqu'on atteint les colonnes de droite, l'opération est terminée (on ne divise pas les coefficients du reste)

$\begin{array}{c}\begin{array}{c}\\ & 1& \\ 2& & \\ \\ & & /3\end{array}\begin{array}{cccc}6& 5& 0& -7\\ & & 2& 3\\ & 4& 6& \\ 6& 9& 8& -4\\ 2& 3& & \end{array}\end{array}$

En définitive, le résultat se lit ainsi :

$\begin{array}{cccc}2x& +3& 8x& -4\end{array}$

et on a donc

$\frac{6x^3+5x^2-7}{3x^2-2x-1}=2x+3+\frac{8x-4}{3x^2-2x-1}$

Forme compacte

Cependant, le format précédent devient trop encombrant lorsque le degré du diviseur est plus grand que la moitié du degré du dividende. Comme chaque produit peut être écrit dans une ligne quelconque, tant que la colonne est correcte, un algorithme glouton permet d'optimiser la place prise, comme l'illustre l'exemple suivant :

$\frac{a{x}^7+b{x}^6+c{x}^5+d{x}^4+e{x}^3+f{x}^2+gx+h}{i{x}^4-j{x}^3-k{x}^2-lx-m}=n{x}^3+o{x}^2+px+q+\frac{r{x}^3+s{x}^2+tx+u}{i{x}^4-j{x}^3-k{x}^2-lx-m}$

$\begin{array}{cc}\begin{array}{c}\\ \\ \\ \\ j& k& l& m\end{array}& \begin{array}{cccccccc}& & & & qj& & & \\ & & & pj& pk& qk& & \\ & & oj& ok& ol& pl& ql& \\ & nj& nk& nl& nm& om& pm& qm\\ a& b& c& d& e& f& g& h\\ a& o_0& p_0& q_0& r& s& t& u\\ n& o& p& q& & & & \end{array}\end{array}$

L'algorithme (comportant des étapes de division si i ≠ 1) est le suivant :

1. Écrire les coefficients du dividende

   $\begin{array}{c}\begin{array}{cccccccc}a& b& c& d& e& f& g& h\end{array}\end{array}$

2. Écrire à gauche les coefficients du diviseur changés de signe, à l'exception du coefficient dominant.

   $\begin{array}{cc}\begin{array}{cccc}j& k& l& m\end{array}& \begin{array}{cccccccc}a& b& c& d& e& f& g& h\end{array}\end{array}$

3. Marquer la séparation entre le quotient et le reste par une barre verticale, en laissant autant de colonnes pour le reste que le degré du diviseur.

   $\begin{array}{cc}\begin{array}{cccc}j& k& l& m\\ \end{array}& \begin{array}{cccccccc}a& b& c& d& e& f& g& h\\ & & & & & & & \end{array}\end{array}$

4. Modèle:Citation le premier coefficient du dividende.

   $\begin{array}{cc}\begin{array}{cccc}j& k& l& m\\ \end{array}& \begin{array}{cccccccc}a& b& c& d& e& f& g& h\\ a& & & & & & & \end{array}\end{array}$

   • Si le diviseur n'est pas unitaire, diviser le terme qui vient d'être descendu ou sommé par le coefficient dominant du diviseur, et le placer sur la ligne suivante. À la première étape, on a donc $n=\frac{a}{i}$.
   • Multiplier ce nombre par chaque coefficient de gauche (les coefficients du diviseur changés de signe). Placer chaque produit au sommet des colonnes suivantes.

   $\begin{array}{cc}\begin{array}{c}\\ j& k& l& m\end{array}& \begin{array}{cccccccc}& nj& nk& nl& nm& & & \\ a& b& c& d& e& f& g& h\\ a& & & & & & & \\ n& & & & & & & \end{array}\end{array}$

5. Additionner colonne par colonne ; on a donc $o_0=b+nj$.

   $\begin{array}{cc}\begin{array}{c}\\ j& k& l& m\end{array}& \begin{array}{cccccccc}& nj& nk& nl& nm& & & \\ a& b& c& d& e& f& g& h\\ a& o_0& & & & & & \\ n& & & & & & & \end{array}\end{array}$

6. Répéter les deux étapes précédentes, jusqu'à atteindre la barre de séparation. Soit $o=\frac{o_0}{i}$.

   $\begin{array}{cc}\begin{array}{c}\\ \\ j& k& l& m\end{array}& \begin{array}{cccccccc}& & oj& ok& ol& & & \\ & nj& nk& nl& nm& om& & \\ a& b& c& d& e& f& g& h\\ a& o_0& p_0& & & & & \\ n& o& & & & & & \end{array}\end{array}$

   on a donc $p_0=c+nk+oj$. Soit $p=\frac{p_0}{i}$.

   $\begin{array}{cc}\begin{array}{c}\\ \\ \\ j& k& l& m\end{array}& \begin{array}{cccccccc}& & & pj& pk& & & \\ & & oj& ok& ol& pl& & \\ & nj& nk& nl& nm& om& pm& \\ a& b& c& d& e& f& g& h\\ a& o_0& p_0& q_0& & & & \\ n& o& p& & & & & \end{array}\end{array}$

   on a donc $q_0=d+nl+ok+pj$. Soit $q=\frac{q_0}{i}$.

   $\begin{array}{cc}\begin{array}{c}\\ \\ \\ \\ j& k& l& m\end{array}& \begin{array}{cccccccc}& & & & qj& & & \\ & & & pj& pk& qk& & \\ & & oj& ok& ol& pl& ql& \\ & nj& nk& nl& nm& om& pm& qm\\ a& b& c& d& e& f& g& h\\ a& o_0& p_0& q_0& r& & & \\ n& o& p& q& & & & \end{array}\end{array}$

7. Le calcul des coefficients du reste s'obtient en additionnant les colonnes restantes sans effectuer de nouveaux calculs (par exemple, $r=e+nm+ol+pk+qj$, $s=f+om+pl+qk$).

   $\begin{array}{cc}\begin{array}{c}\\ \\ \\ \\ j& k& l& m\end{array}& \begin{array}{cccccccc}& & & & qj& & & \\ & & & pj& pk& qk& & \\ & & oj& ok& ol& pl& ql& \\ & nj& nk& nl& nm& om& pm& qm\\ a& b& c& d& e& f& g& h\\ a& o_0& p_0& q_0& r& s& t& u\\ n& o& p& q& & & & \end{array}\end{array}$

8. Comme précédemment, l'interprétation est donc :

   $\frac{a{x}^7+b{x}^6+c{x}^5+d{x}^4+e{x}^3+f{x}^2+gx+h}{i{x}^4-j{x}^3-k{x}^2-lx-m}=n{x}^3+o{x}^2+px+q+\frac{r{x}^3+s{x}^2+tx+u}{i{x}^4-j{x}^3-k{x}^2-lx-m}$

Voir aussi

• Anneau euclidien
• Base de Gröbner

Références

• Modèle:Article
• Modèle:Article

Liens externes

• Modèle:MathWorld
• Modèle:MathWorld