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 x2 − ε (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 :
« Pour ma part, je considère cela comme l’expérience la plus traumatisante de ma carrière en analyse numérique [1]. »
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é[2].
Conditionnement du polynôme de Wilkinson
Le polynôme de Wilkinson
a clairement 20 racines simples, situées en x = 1, 2, ..., 20. 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 à −2−23 × 2019 =−6,25 ×1017, et la racine en x = 20 devient x ≈ 20,8. Les racines en x = 18 et x = 19 se rapprochent jusqu'à devenir une racine double en x ≈ 18,62 qui se transforme en deux racines conjuguées complexes en x ≈ 19,5 ± 1,9 i à 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 −210 − 2−23, 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 p(x) = Π(x − αj) avec les racines α j simples, en ajoutant un petit multiple t·c(x) 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 |t| est plus grand que le rayon de convergence de cette série, qui est donné par la plus petite valeur de |t| 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 αj = j pour j = 1, ..., 20, 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 |αj − αk| entre eux est plus petite que |α j| .
Exemple de bon comportement. Pour la racine α1 = 1, 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ù |α1 − β | = 1, 2, 3, ..., 19 est supérieur à |α1| = 1. 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 1 + t /19! ≈ 0,99999991779365). 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 α20 = 20, la dérivée est égale à −2019/19! ce qui est très grand (environ 4 300 000), donc cette racine est très sensible aux petits changements de t. Les autres racines β sont proches de α20, dans le sens où |β − α20| = 1, 2, 3, ..., 19 est inférieur à |α20| = 20. Pour t = −2−23, l'approximation du premier ordre 20 − t × 2019/19! = 25,137... à 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 |t| ≈ 0,000000119 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 t = 0,000000001 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 α1 = 1 et α20 = 20 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 α20 = 20 est moins stable que α1 = 1 (à de petites perturbations du coefficient de x19) d'un facteur de 2019 = 5,2488 × 1024.
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 0, 1, 2, ..., 20 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.
↑(en) Lloyd N. Trefethen et David Bau, Numerical Linear Algebra, SIAM,
Références
Wilkinson a discuté de « son » polynôme dans
(en) J. H. Wilkinson, « The evaluation of the zeros of ill-conditioned polynomials. Part I. », Numerische Mathematik, vol. 1, , p. 150–166 (DOI10.1007/BF01386381).
(en) J. H. Wilkinson, Rounding Errors in Algebraic Processes, Englewood Cliffs, New Jersey, Prentice Hall, .
Il est mentionné dans les manuels standards d'analyse numérique, comme