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

$w(x)=\prod _{i=1}^{20}(x-i)=(x-1)(x-2)\cdots (x-20).$

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

$p(x)=\sum _{i=0}^n{c}_i{x}^i.$

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 c_i 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 x² a une racine double en 0. Cependant, le polynôme x ² − ε (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 :

Modèle:Citation

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

$w(x)=\prod _{i=1}^{20}(x-i)=(x-1)(x-2)\cdots (x-20)$

a clairement 20 racines simples, situées en Modèle:Nobr. 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

$\begin{array}{cc}w(x)=& x^{20}-210x^{19}+20615x^{18}-1256850x^{17}+53327946x^{16}\\ & -1672280820x^{15}+40171771630x^{14}-756111184500x^{13}\\ & +11310276995381x^{12}-135585182899530x^{11}\\ & +1307535010540395x^{10}-10142299865511450x^9\\ & +63030812099294896x^8-311333643161390640x^7\\ & +1206647803780373360x^6-3599979517947607200x^5\\ & +8037811822645051776x^4-12870931245150988800x^3\\ & +13803759753640704000x^2-8752948036761600000x\\ & +2432902008176640000.\end{array}$

Trace du logarithme du polynôme de Wilkinson et de sa version perturbée

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

$\begin{array}{ccccc}1,00000& 2,00000& 3,00000& 4,00000& 5,00000\\ 6,00001& 6,99970& 8.00727& 8.91725& 20.84691\\ 10,09527\pm & 11,79363\pm & 13,99236\pm & 16,73074\pm & 19,50244\pm \\ 0,64350\mathrm{i}& 1,65233\mathrm{i}& 2,51883\mathrm{i}& 2,81262\mathrm{i}& 1,94033\mathrm{i}\end{array}$

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ù Modèle:Nobr est plus petit que Modèle:Nobr.

Wilkinson a choisi la perturbation de 2⁻²³ parce que son ordinateur Pilot ACE avait des mantisses à virgule flottante de 30 bits, donc pour les nombres autour de 210, 2⁻²³ était une erreur dans la position du premier bit non représentée dans l'ordinateur. Les deux nombres réels, −210 et Modèle:Nobr, sont représentés par le même nombre à virgule flottante, ce qui signifie que 2⁻²³ 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 Modèle:Nobr avec les racines α _j simples, en ajoutant un petit multiple Modèle:Math 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

$\frac{\mathrm{d}{\alpha }_j}{\mathrm{d}t}=-\frac{c({\alpha }_j)}{p^{\prime }({\alpha }_j)}.$

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 :

${\alpha }_j+\frac{\mathrm{d}{\alpha }_j}{\mathrm{d}t}t+\frac{{\mathrm{d}}^2{\alpha }_j}{\mathrm{d}{t}^2}\frac{t^2}{2!}+\cdots$

et on s'attend à des problèmes quand Modèle:Nobr est plus grand que le rayon de convergence de cette série, qui est donné par la plus petite valeur de Modèle:Nobr 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 Modèle:Nobr pour Modèle:Nobr, et c(x) est égal à x¹⁹. La dérivée est donc donnée par

$\frac{\mathrm{d}{\alpha }_j}{\mathrm{d}t}=-\frac{{\alpha }_j^{19}}{\prod _{k\ne j}({\alpha }_j-{\alpha }_k)}=-\prod _{k\ne j}\frac{{\alpha }_j}{{\alpha }_j-{\alpha }_k}.$

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 Modèle:Nobr entre eux est plus petite que Modèle:Nobr .

Exemple de bon comportement. Pour la racine Modèle:Nobr, 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ù Modèle:Nobr est supérieur à Modèle:Nobr. Par exemple, même si t est aussi grand que –10000000000, la racine α₁ ne change que de 1 à environ 0,99999991779380 (ce qui est très proche de l'approximation du premier ordre Modèle:Nobr). 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 Modèle:Nobr, la dérivée est égale à −20¹⁹/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 α₂₀, dans le sens où Modèle:Nobr est inférieur à Modèle:Nobr. Pour Modèle:Nobr, l'approximation du premier ordre Modèle:Nobr à la racine perturbée 20,84... est très mauvaise ; ceci est encore plus évident pour la racine α₁₉ 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 Modèle:Nobr 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 Modèle:Nobr 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 Modèle:Nobr et Modèle:Nobr 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 Modèle:Nobr est moins stable que Modèle:Nobr (à de petites perturbations du coefficient de x¹⁹) d'un facteur de Modèle:Nobr.

Deuxième exemple de Wilkinson

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

$w_2(x)=\prod _{i=1}^{20}(x-\frac{1}{2^i})=(x-\frac{1}{2})(x-\frac{1}{4})\cdots (x-\frac{1}{2^{20}}).$

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

$\frac{{\alpha }_j}{{\alpha }_j-{\alpha }_k}$

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

Influence de la base de polynômes

Le développement

$p(x)=\sum _{i=0}^n{c}_i{x}^i$

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 Modèle:Nobr sont

${\ell }_k(x)=\prod _{i\in \{0,\dots ,20\}\setminus \{k\}}\frac{x-i}{k-i},\text{pour}k=0,\dots ,20.$

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

$p(x)=\sum _{i=0}^{20}{d}_i{\ell }_i(x).$

Pour le polynôme de Wilkinson, on trouve

$w(x)=(20!){\ell }_0(x)=\sum _{i=0}^{20}{d}_i{\ell }_i(x)\text{avec}{d}_0=(20!),d_1=d_2=\cdots =d_{20}=0.$

Compte tenu de la définition du polynôme de base de Lagrange ℓ₀(x), un changement du coefficient d₀ 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.

Références

Wilkinson a discuté de « son » polynôme dans

• Modèle:Article.
• Modèle:Ouvrage.

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

• Modèle:Ouvrage.

Autres références :

• Modèle:Article.
• Modèle:Article

Un calcul numérique de haute précision est présenté dans :

• Modèle:Lien web, partie du RPN Calculator User Manual (en Python), vérifié le 27 septembre 2013.