ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges

Division polynomiale
    »
PGCD | Division selon les puissances croissantes & application aux développements limités
         Cas particulier de la division par x - a, recherche de l'équation d'une asymptote "oblique"

 

Soit K[x] l'ensemble des polynômes de la variable réelle ou complexe x (K = R ou C). Muni de l'addition et de la multiplication des fonctions, ces polynômes constituent un anneau unitaire, x → 1 est neutre pour la multiplication, son élément nul, neutre pour l'addition est le polynôme nul,  x → 0. Cet anneau est intègre : le produit de deux polynômes non nuls ne peut être nul à moins que l'un des deux soit nul.

Soit B un polynôme non nul; à l'instar de l'arithmétique dans Z, on dit que A et C sont congrus modulo B pour exprimer qu'il existe un polynôme Q tel que : A - C = BQ, polynôme produit de B par Q et on écrit A ≡ C mod.B


Montrer que l'on définit ainsi une relation d'équivalence dans K[x]

I -  Division suivant les puissances décroissantes :          » Programme JavaScript 

Dans cette première partie, on s'intéresse à la division, dite euclidienne, d'un polynôme A par un polynôme B comme défini ci-après, également qualifiée de division suivant les puissances décroissantes. L'algorithme est comparable à la division euclidienne dans N.

Théorème et définitions :    

Si A n'est pas multiple de B, la classe d'équivalence (ou de congruence) de A modulo B contient un unique polynôme R de degré strictement inférieur à B appelé reste de la division euclidienne de A par B; l'unique polynôme Q correspondant à R est le quotient de A par B. On a alors :

 A = BQ + R,  d°R < d°B

Unicité :     

Soit d le degré de B. Supposons qu'une classe contienne deux polynômes distincts R et S chacun de degré inférieur à d. On aura S - R = BQ. Si Q = 0, alors R = S. Si Q est non nul, S = R + BQ, donc d° S ≥ d°BQ ≥ d : contraire à l'hypothèse. Donc R est unique.

Existence :     

Si d°A < d, on pose R = A et c'est terminé !
Supposons A = a
nxn + ..., de degré n et B = bdxd + ..., de degré d, n ≥ d.
On pose Q1 = xn-d
× an/bd et A - BQ1 = R1.

On a d°R1 < d°A.
Si d°R1 < d, c'est gagné : on prend R = R1.
Sinon on applique le procédé à R1, on obtient R2 = R1 - BQ2 avec d°R2 < d°R1.

Si d°R2 < d, c'est gagné, on prend R = R2.
Sinon, on poursuit le procédé, on obtiendrait un R3 avec d°R3 < d°R2, etc.

On obtient ainsi un algorithme semblable à celui de la division euclidienne dans N qui, au bout de n - d + 1 applications au plus du procédé conduit à un Rk de degré nul puisque Rk < d°Rk-1.

   Il se peut que l'un des Rk soit nul. Dans ce cas l'algorithme s'arrête. On aura Rk-1 - BQk = Rk = 0, soit Rk-1 = BQk, puis Rk-2 - BQk-1 = Rk-1. Par conséquent Rk-2 = B(Qk-1 + Qk) : donc Rk-2 est multiple de B et finalement par récurrence finie A = BQ1, donc A multiple de B.

Les écritures successives précédentes des Rk montrent que au bout d'un nombre fini m d'applications du procédé, on a  :

A = B(Q1 + Q2 + ... + Qm) + Rm

Q = Q1 + Q2 + ... + Qm est le quotient de la division euclidienne de A par B, Rm en est le reste.

Exemple : Soit à diviser A = x3 + 2x2 - x - 2 par B = x2 + 1. On pose l'opération comme pour une division d'entiers :


 


Programmation :    

soit : x5 - 1 = (2x + 1)(x4/2 - x3/4 + x2/8 - x/16 + 1/32) - 33/32


          

II - PGCD de deux polynômes :   

Cette division polynomiale euclidienne permet de parler, tout comme en arithmétique élémentaire, de plus grand diviseur commun à deux polynômes :

Étant donnés deux polynômes A et B dans K[x], l'ensemble de leurs diviseurs communs n'est pas vide : tout polynôme constant (polynôme de degré 0) les divise. Considérons alors l'ensemble J des combinaisons AU + BV où U et V décrivent K[x]. J est un idéal de K[x]; en cet qualité, J est principal. Il existe donc un polynôme D divisant tout élément de J tel que :

  1. D divise A (choisir U = 1 et V = 0) et B (choisir U = 0 et V = 1) ;

  2. D est défini à une constante multiplicative près;

  3. Il existe Uo et Vo tels que D = AUo + BVo;

  4. Tout polynôme de K[x] divisant A et B divise également D.

Les propriétés 1 et 4 conduisent à qualifier D de plus grand diviseur commun à A et B  au sens d'un diviseur commun de plus haut degré défini à une constante multiplicative près. On note D = pgdc(A,B) ou D = pgcd(A,B). Si D (non nul) est de degré 0, on dit que A et B sont premiers entre eux. Autrement dit :

A et B sont dits premiers entre eux lorsque 1 est un PGCD de A et B

Vocabulaire :    

   On parle le plus souvent de PGCD (Plus Grand Commun Diviseur) au lieu de PGDC (Plus Grand Diviseur Commun). Il s'agit là de l'influence allemande et anglo-saxonne : dans la langue de Gauss, on parle de Größter Gemeinsamer Teiler (ggT),  soit,  en anglais Greatest Common Divisor (GCD). Idem pour le Plus Petit Multiple Commun (PPMC ou PPCM). : en allemand kleineres gemeinsames Vielfaches (kgV), en anglais : Least Common Multiple (LCM).

Comment calculer du PGCD de deux polynômes A et B :    

On procède aux divisions euclidiennes successives de A par B fournissant un reste R1, puis de B par R1 fournissant un reste R2, etc. :

A = BQ1 + R1, d°R1 < d°B     • B = R1Q2 + R2, d°R2 < d°R1     • R1 = R2Q3 + R3, d°R3 < d°R2
...     Rk-3 = Rk-2Qk-1 + Rk-1, d°Rk-1 < d°Rk-2     Rk-2 = Rk-1Qk + Rk, d°Rk < d°Rk-1

Les degrés des restes successifs diminuant strictement, à l'issue d'un nombre fini k de divisions, Rk sera de degré nul, c'est à dire constant, éventuellement nul.

Inversement deux cas se présentent :

En conclusion, on retrouve le résultat analogue à l'arithmétique élémentaire :

Le PGCD de deux polynômes A et B est le dernier reste non nul dans la division euclidienne de A par B

   Tout comme dans l'anneau (Z,+,×) des entiers relatifs, on a le résultat suivant :

Théorème de Bézout :    

Soit D le PGCD de deux polynômes A et B; il existe un unique couple de polynômes U et V tels que AU + BV = D.
Lorsque A et B sont premiers entre eux, leur PGCD est de degré 0; on peut le ramener à 1 et écrire AU + BV = 1.


Programmation :     

L'algorithme est conforme à l'analyse ci-dessus :

Le lecteur intéressé par la programmation pourra en consulter le listing faisant usage des listes au sens de n-uplets (données ordonnées de n éléments) : on entre les données polynomiales A et B sous forme de listes de leurs coefficients ordonnés suivant les puissances décroissantes. Le programme accepte les écritures fractionnaires et, en sortie, cherche à exprimer les coefficients du PGCD sous forme fractionnaire en utilisant le sous-programme de développement en fraction continue étudié sur cette page.

En effet : x3 - 9x = x(x + 3)(x - 3) et 2x2 - 5x - 3 = (2x + 1)(x - 3); le PGCD est donc x - 3, soit (en liste) 1,-3.

 i  Le degré de A peut être inférieur à celui de B : dans ce cas, la première division de A par B fournira un quotient nul et le reste sera A, au tour suivant l'algorithme divisera B par A.

   À la main, on a :


R2 est nul, donc le pgcd est le reste précédent R1 = -5x/4 + 15/4 = -5/4 × (x - 3)
soit x - 3 à une constante multiplicative près.


          

Division dans un anneau commutatif unitaire, idéal d'anneau, cas des polynômes : »

III - Division suivant les puissances croissantes :          » Programme JavaScript

Si nous ordonnons A et B suivant les puissances croissantes de la variable x (réelle ou complexe), on obtient un autre moyen de division fort utile dans la recherche de valeurs approchées de fonctions rationnelles et de développements limités asymptotiques d'une fonction (au voisinage d'un point où cette fonction n'est pas définie) comme, par exemple le développement limité de f(x) = 1/sin(x) au voisinage de 0.

Théorème :    

Soit A et B deux polynômes, B ne s'annulant pas en 0 (B possède un terme constant : sa valuation est nulle). Alors pour tout entier p, il existe un unique polynôme Q et un unique polynôme R, multiple de xp, tels que :

A = BQ + R    avec d°Q ≤ p

 R est le reste de la division de la division de A par B suivant les puissances croissantes et Q en est le quotient.

   Selon cette définition, on a degré Q < p + 1 ≤ v(R), valuation de R. Si A est divisible par B, R sera nul, sinon, la division peut se poursuivre indéfiniment.

Schéma de la démonstration :    

Écrivons A = ao + a1x + a2x2 + ... et B = bo + b1x + b2x2 + ... avec bo non nul. A et B sont donc ordonnés suivant les puissances croissantes de x. Si A contient xp en facteur, le résultat est trivial. Supposons qu'il n'en soit pas ainsi.

   On continue ainsi jusqu'à obtenir un Rk nul ou de degré au moins égal à p. On obtient alors une écriture du type :

A - B(qo + q1 + ... + qk) + Rk

Rk est multiple de xp, le quotient cherché est qo + q1 + ... + qk. On peut prouver (par l'absurde) son unicité.

Dans la pratique, la technique de  division de A par B suivant les puissances croissantes s'effectue de façon semblable à celle suivant les puissances décroissantes.

Remarques :   

  1. On peut toujours supposer bo = 1 en divisant tous les coefficients de B par bo, quitte à diviser le résultat de la division par bo.

  2. Si bo est nul : soit bk le premier coefficient non nul (par rang croissant) de B; on effectue la division de A par B/bkxk et on divise le résultat de la division par bkxk.

Exemple d'application :    

On sait développer sin x en série entière : sinx = x - x3/3! + x5/5! - x7/7!... On veut obtenir le développement de 1/sin(x). Le développement de sinx ne possède pas de terme constant. Selon la remarque 2 ci-dessus, on divise 1 (polynôme A) par B = sin (x)/x et on divisera par x le résultat.

à la "main" :

Résultat que le programme exprime par (les 0 isolés signifiant l'absence de la puissance correspondante) :

Divisons maintenant par x :

1/sin(x) = 1/x + x/6 + 7x3/360 + 31x5/15120 + o(x5)

 


Programmation :    

Le programme ci-après effectue la division suivant les puissances croissantes de deux polynômes A et B conformément à l'algorithme étudié ci-dessus. Le lecteur intéressé par la programmation pourra en consulter le listing faisant usage des listes au sens de n-uplets (données ordonnées de n éléments) : on entre les données polynomiales A et B sous forme de listes de leurs coefficients ordonnés suivant les puissances décroissantes. Le programme accepte les écritures fractionnaires et, en sortie, cherche à exprimer les coefficients du quotient et du reste sous forme fractionnaire en utilisant le sous-programme de développement en fraction continue étudié sur cette page.

Rappel : B ne doit pas s'annuler en 0 : terme constant non nul. Si ce n'est pas le cas, on divise B par xv où v est le terme de plus bas degré (valuation de B) et on  divisera ensuite le résultat par ce même xv.


              

On doit comprendre :

A =             B             ×              Q                 +              R
1 = (1 - x2/6 + x4/120) × (1 + x2/6 + 7 x4/360) + (x6/540 - 7x8/43200)

à l'ordre 5, le quotient est inchangé car il ne contient (comme le reste) dans ce cas particulier que des puissances paires : le coefficient de x5 est nul :

   Par défaut, le programme effectue la division de x5 - 1 par 2x + 1 suivant les puissances croissantes donc, en listes, -1,0,0,0,0,1 (équivalent à -1 + x5) par 1,2 (équivalent à 1 + 2x) avec p = 5. Ce qui conduit à :

- 1 + x5 = (1 + 2x)(-1 + 2x - 4x2 + 8x3 - 16x4 + 33x5) - 66x6

et on notera que ce résultat a peu de rapport avec la division euclidienne de ces mêmes polynômes

 i  Pour diviser -1 + x5 par x2 + 2x3 : on procède à la même division, et on divise ensuite le quotient par x2, le reste est inchangé :

- 1 + x5 = (x2  + 2x3)(-1/x2 + 2/x - 4x + 8x - 16x2 + 33x3) - 66x6

Un autre exemple d'application du programme :   

Nous allons calculer le développement de tan(x) à l'ordre 7 obtenu en divisant suivant les puissances croissantes le développement en série de sin(x) par celui de cos(x) en se limitant à l'ordre 7 :

Le programme comprend les entrées fractionnaires et, en sortie, cherche à exprimer les coefficients du quotient et du reste sous forme fractionnaire en utilisant le sous-programme de développement en fraction continue étudié sur cette page. On entre les coefficients sous forme de listes et suivant les puissances croissantes :

On obtient (le 1er 0 indique qu'il n'y a pas de terme constant) :

C'est dire que :

tan(x) = x + x3/3 +2x5/15 + 17x7/315 + o(x7)

 i  Le calcul du reste laisse présager un terme de degré 9 égal à 331x9/15120. Mais les développements fournis étant d'ordre 7, il n'y a pas de certitude... Il serait vain de demander à développer au-delà d'un rang non fourni en entrée.


© Serge Mehl - www.chronomath.com