roots

Paramètres

p

un polynôme réel ou complexe ; ou un vecteur de nombres décimaux ou complexes = les coefficients du polynôme par ordre de puissances décroissantes.

algo

un caractère désignant l'algorithme à utiliser :

• "e" (par défaut) : les valeurs propres de la matrice compagnon sont utilisées.
• "f" : si isreal(p) et degree(p)<100 : l'algorithme de Jenkins-Traub est utilisé.
• "f" : si isreal(p) et degree(p)>=100: une erreur est émise.
• "f" : si ~isreal(p), une erreur est émise.

Description

Cette fonction retourne dans le vecteur complexe x les racines du polynôme p.

L'option "f" utilise l'algorithme rapide RPOLY, fondé sur la méthode de Jenkins-Traub.

Pour les polynôme réels de degré inférieur à 100, on peut utiliser l'option "f", qui peut être plus rapide dans certains cas. Toutefois, certains polynômes sont susceptibles de poser des problèmes de convergences pour l'algorithme associé à l'option "f". Par exemple, p=poly([1.e300,1.e0,1.e-300],'x'); provoque le bouclage infini de roots(p,"f")

Exemples

Dans les exemples suivants, on calcule des racines de polynômes.

// Un polynôme réel.
p = poly([1 2 3],"x")
roots(p)
// Les coefficients du polynôme sont donnés.
p = [3 2 1]
roots(p)
// Les racines d'un polynôme complexe.
p=poly([0,10,1+%i,1-%i],'x');
roots(p)
// Les racines du polynôme caractéristique d'une matrice.
A=rand(3,3);
p = poly(A,'x')
roots(p)
spec(A)

La représentation polynômiale peut avoir un impact significatif sur les racines. Dans l'exemple suivant, suggéré par Wilkinson dans les années 60 et présenté par Moler, on considère une matrice dont les termes diagonaux sont égaux à 1, 2, ..., 20. Bien entendu, les racines du polynôme caractéristique sont 1, 2, ..., 20. Si on calcule le polynôme caractéristique associé et qu'on calcule ses racines, on peut voir qu'elles sont significativement différentes des valeurs attendues. Cela montre que le seul fait de représenter les coefficients dans des doubles IEEE change les racines.

A = diag(1:20);
p = poly(A,'x')
roots(p)

L'option "f" produit une erreur si le polynôme est complexe ou que le degré est plus grand que 100.

// Le cas suivant produit une erreur
p = %i+%s;
roots(p,"f")
// Le cas suivant produit une erreur
p = ones(101,1);
roots(p,"f")

Le script suivant est une manière simple de vérifier que la matrice compagnon donne le même résultat que l'option "e". Il utilise explicitement la matrice compagnon pour calculer les racines. Il faut néanmoins inverser les coefficients du polynôme ; en effet, "roots" les attend dans l'ordre de degré décroissant, alors que "poly" les attend dans l'ordre croissant.

v= [1.12119799 0 3.512D+13 32 3.275D+27 0 1.117D+41 4.952D+27 1.722D+54 0 1.224D+67 0 3.262D+79 ];
r1 = roots(v,"e"); // Avec l'option "e"
dv = size(v,"*");
p = poly(v(dv:-1:1),"x","coeff"); // Inversion des coefficients de v
A = companion(p);
r2 = spec(A); // Avec la matrice compagnon
max(abs(r1-r2))

Voir aussi

• poly — définition d'un polynôme selon racines ou coefficients, ou caractéristique d'une matrice carrée
• spec — valeurs propres d'une matrice
• companion — matrice compagnon

Bibliographie

La routine RPOLY est decrite dans "Algorithm 493: Zeros of a Real Polynomial", ACM TOMS Volume 1, Issue 2 (June 1975), pp. 178-189