Plus grand diviseur commun de polynômes

Le calculateur donne le PGCD (plus grand diviseur commun) de deux polynômes saisis.

Le calculateur donne le plus grand diviseur commun en utilisant la méthode d'Euclide et la division polynomiale. Les coefficients polynomiaux sont des entiers, des fractions ou des nombres complexes avec des fractions our des parties fractionnelles réelles et imaginaires. Le résultat est un polynôme qui divise les deux polynômes saisis sans reste ou 1 s'il n'existe pas un tel polynôme.

PLANETCALC, Plus grand diviseur commun de polynômes.

Plus grand diviseur commun de polynômes.

Algorithme de correction des pseudo-restes.
Le coefficient PGCD sera calculé à chaque étape.
Résultat
 
Le fichier est très volumineux; un ralentissement du navigateur peut se produire pendant le chargement et la création.

Le phénomène de croissance exponentielle des coefficients.

Pour le calcul du PGCD des polynômes de degré plus important, les coefficients du polynôme reste augmentent exponentiellement. Même dans ce calculateur, vous pouvez le voir avec les données saisies par défaut ; la séquence de reste contient de grosses fractions. Pour éliminer les fractions et réduire les coefficients entiers, une pseudo-division peut être utilisée avec un algorithme de réduction du coefficient du reste. 3 algorithmes de calcul des pseudo-restes sont disponibles dans ce calculateur, sans compter la pseudo-division triviale sans aucun coefficient de réduction.

Le meilleur coefficient de réduction donne la méthode de réduction de contenu, qui divise tous les termes par le coefficient PGCD. Néanmoins, le coût en calcul de cette méthode peut être inacceptablement important pour des polynômes de degré important avec des coefficients complexes puisque l'algorithme d'Euclide est appliqué à chaque itération pour chaque coefficient.

Comme variante de compromis contrôlant la croissance est un algorithme basé sur la sous-résultat PRS, le calculateur utilise deux d'entre eux (Algorithme 1 et Algorithme 3), décris pas W.S. Brown dans l'article : L'algorithme des sous-résultats PRS1.
Le calculateur produit le tableau des pseudo-restes avec le contenu polynomial pour chaque reste afin d'estimer l'efficacité de l'algorithme. Moins il y a de contenu, plus l'algorithme est efficace.


  1. W.S. Brown, Laboratoires Bell. ACM Transactions sur le logiciel mathématique, Vol 4, No 3, Septembre 1978, p.p. 237-249 

URL copiée dans le presse-papiers
PLANETCALC, Plus grand diviseur commun de polynômes

commentaires