Polynôme de Wilkinson

En analyse numérique, le polynôme de Wilkinson est un polynôme réel qui a été utilisé par James H. Wilkinson en 1963 pour illustrer un problème mal conditionné lors de la recherche de zéros d'un polynôme : la position des racines peut être très sensible aux perturbations des coefficients du polynôme.

Le polynôme est

 

Parfois, le nom polynôme de Wilkinson est également utilisé pour désigner d'autres polynômes apparaissant dans l'étude de Wilkinson.

Préliminaires 
Le polynôme de Wilkinson est apparu dans l'étude des algorithmes permettant de trouver les racines d'un polynôme

 

C'est une question courante en analyse numérique de se demander si le problème de trouver les racines de p à partir des coefficients ci est bien conditionné. Autrement dit, on espère qu’une petite variation dans les coefficients entraînera une petite variation dans les racines. Le polynôme de Wilkinson est un exemple de cas pathologique.

Le problème est mal conditionné lorsque le polynôme a une racine multiple. Par exemple, le polynôme x2 a une racine double en 0. Cependant, le polynôme x 2 − ε (avec une perturbation de taille ε ) a deux racines simples en  ±√ ε, qui est beaucoup plus grand que ε lorsque ε est petit.

On en déduit qu'il faut s'attendre à ce qu’un mauvais conditionnement apparaisse aussi lorsque le polynôme a des zéros très proches. Cependant, le problème peut également être extrêmement mal conditionné pour les polynômes dont les zéros sont bien séparés. Wilkinson a utilisé le polynôme w(x) pour illustrer ce point (Wilkinson 1963).

En 1984, il décrit l’impact personnel de cette découverte :

Le polynôme de Wilkinson est souvent utilisé pour illustrer le caractère indésirable du calcul naïf des valeurs propres d'une matrice en calculant d'abord les coefficients du polynôme caractéristique de la matrice, puis en trouvant ses racines, car l'utilisation des coefficients comme étape intermédiaire peut introduire un très mauvais conditionnement même si le problème d'origine était bien conditionné.

Conditionnement du polynôme de Wilkinson 
Le polynôme de Wilkinson
 
a clairement 20 racines simples, situées en . Ces racines sont très éloignées. Cependant, le polynôme est encore très mal conditionné.

En développant le polynôme, on trouve

 

Si le coefficient de x19 est réduit de 2−23, soit de −210 à −210,0000001192, alors la valeur w(20) diminue de 0 à , et la racine en  devient . Les racines en  et  se rapprochent jusqu'à devenir une racine double en  qui se transforme en deux racines conjuguées complexes en  à mesure que la perturbation augmente. Les 20 racines deviennent (à 5 décimales)

 

Certaines racines sont fortement déplacées, même si la modification du coefficient est minime et que les racines originales semblent très espacées. Wilkinson a montré par l'analyse de stabilité discutée dans la section suivante que ce comportement est lié au fait que certaines racines α (telles que α = 15) ont de nombreuses racines β qui sont « proches » au sens où  est plus petit que .

Wilkinson a choisi la perturbation de 2−23 parce que son ordinateur Pilot ACE avait des mantisses à virgule flottante de 30 bits, donc pour les nombres autour de 210, 2−23 était une erreur dans la position du premier bit non représentée dans l'ordinateur. Les deux nombres réels, −210 et , sont représentés par le même nombre à virgule flottante, ce qui signifie que 2−23 est l'erreur inévitable en représentant un coefficient réel proche de −210 par un nombre à virgule flottante sur cet ordinateur. L'analyse des perturbations montre que la précision du coefficient de 30 bits est insuffisante pour séparer les racines du polynôme de Wilkinson.

Analyse de stabilité 
On suppose que l'on perturbe un polynôme  avec les racines α j simples, en ajoutant un petit multiple  d'un polynôme c(x), et on souhaite étudier le comportement des racines αj . Au premier ordre, la variation des racines sera contrôlée par la dérivée

 

Lorsque la dérivée est grande, les racines seront plus stables sous les variations de t, et inversement si cette dérivée est petite les racines seront instables. En particulier, si α j est une racine multiple, alors le dénominateur s'annule. Dans ce cas, α j n'est généralement pas dérivable par rapport à t (à moins que c ne s'y annule), et les racines seront extrêmement instables.

Pour de petites valeurs de t, la racine perturbée est donnée par le développement de Taylor t :
 

et on s'attend à des problèmes quand  est plus grand que le rayon de convergence de cette série, qui est donné par la plus petite valeur de  tel que la racine α j devienne multiple. Une estimation très grossière de ce rayon consiste à prendre la moitié de la distance entre α j et la racine la plus proche et à la diviser par la dérivée ci-dessus.

Dans l'exemple du polynôme de Wilkinson de degré 20, les racines sont données par  pour , et c(x) est égal à x19. La dérivée est donc donnée par

 

Cela montre que la racine αj sera moins stable s'il existe de nombreuses racines α k proches de α j, dans le sens où la distance  entre eux est plus petite que  .

Exemple de bon comportement. Pour la racine , la dérivée est égale à 1/19! ce qui est très petit ; cette racine est stable même pour de grands changements de t. En effet, toutes les autres racines β en sont loin, dans le sens où  est supérieur à . Par exemple, même si t est aussi grand que –10000000000, la racine α1 ne change que de 1 à environ 0,99999991779380 (ce qui est très proche de l'approximation du premier ordre ). De même, les autres petites racines du polynôme de Wilkinson sont insensibles aux changements de t.

Exemple de mauvais comportement . Pour la racine , la dérivée est égale à −2019/19! ce qui est très grand (environ ), donc cette racine est très sensible aux petits changements de t. Les autres racines β sont proches de α20, dans le sens où  est inférieur à . Pour , l'approximation du premier ordre  à la racine perturbée 20,84... est très mauvaise ; ceci est encore plus évident pour la racine α19 où la racine perturbée a une grande partie imaginaire mais l'approximation du premier ordre (et d'ailleurs toutes les approximations d'ordre supérieur) sont réelles. La raison de cet écart est que  est supérieur au rayon de convergence de la série entière mentionnée ci-dessus (qui est d'environ 0,0000000029, légèrement inférieur à la valeur 0,00000001 donnée par l'estimation brute), donc l'approximation linéaire ne s'applique pas. Pour une valeur telle que  qui est nettement inférieure à ce rayon de convergence, l'approximation du premier ordre 19,9569... est raisonnablement proche de la racine 19,9509...

À première vue, les racines  et  du polynôme de Wilkinson semblent similaires, car elles se trouvent aux extrémités opposées d'un ensemble symétrique de racines et ont le même ensemble de distances 1, 2, 3, ..., 19 par rapport aux autres racines. Cependant, l'analyse ci-dessus montre que cela est extrêmement trompeur : la racine  est moins stable que  (à de petites perturbations du coefficient de x19) d'un facteur de .

Deuxième exemple de Wilkinson 
Le deuxième exemple considéré par Wilkinson est
 

Les vingt zéros de ce polynôme sont dans une progression géométrique de raison 2, et donc le quotient
 

ne peut pas être grand. En effet, les zéros de w2 sont assez stables aux changements relatifs importants des coefficients.

Influence de la base de polynômes 
Le développement

 

exprime le polynôme dans une base particulière, à savoir celle des monômes. Si le polynôme est exprimé dans une autre base, alors le problème de trouver ses racines peut cesser d'être mal conditionné. Par exemple, dans une forme de Lagrange, un petit changement dans un (ou plusieurs) coefficients ne modifie pas nécessairement trop les racines. En effet, les polynômes de base pour l'interpolation aux points  sont

 

Tout polynôme (de degré 20 ou moins) peut être exprimé sur cette base :

 

Pour le polynôme de Wilkinson, on trouve

 

Compte tenu de la définition du polynôme de base de Lagrange ℓ0(x), un changement du coefficient d0 ne produira aucun changement dans les racines de w. Cependant, une perturbation des autres coefficients (tous égaux à zéro) modifiera légèrement les racines. Le polynôme de Wilkinson est donc bien conditionné sur cette base.

Remarques

Références 
Wilkinson a discuté de « son » polynôme dans
 .
 .

Il est mentionné dans les manuels standards d'analyse numérique, comme
  .

Autres références :
 .
 

Un calcul numérique de haute précision est présenté dans :
 , partie du RPN Calculator User Manual (en Python), vérifié le 27 septembre 2013.

Polynôme
Analyse numérique