Wilkinson-polynoom

De Wilkinson-polynoom van graad k {\displaystyle k} is de polynoom

∏ i = 1 k ( x − i ) = ( x − 1 ) ( x − 2 ) … ( x − k ) {\displaystyle \prod _{i=1}^{k}(x-i)=(x-1)(x-2)\ldots (x-k)}

De nulpunten van deze polynoom zijn de gehele getallen 1 , 2 , 3 , … , k {\displaystyle 1,2,3,\ldots ,k} .

De praktische relevantie van deze polynoom ligt in het gebruik als test voor numerieke benaderingsmethoden. Het numeriek bepalen van de nulpunten van de polynoom is namelijk een slecht geconditioneerd probleem. Dit wil zeggen dat de gevonden waarden van de nulpunten zeer gevoelig zijn voor kleine onnauwkeurigheden in de berekening.

Normaal gesproken worden polynomen eerst helemaal uitgeschreven alvorens eraan te gaan rekenen. Voor deze polynoom is het probleem dat de coëfficiënten ontzaglijk groot worden, namelijk van de orde van grootte van k ! {\displaystyle k!} ( k {\displaystyle k\,} faculteit). Ter illustratie: voor k = 7 {\displaystyle k=7} hebben we

− 5040 + 13068 x − 13132 x 2 + 6769 x 3 − 1960 x 4 + 322 x 5 − 28 x 6 + x 7 {\displaystyle -5040+13068x-13132x^{2}+6769x^{3}-1960x^{4}+322x^{5}-28x^{6}+x^{7}}

Voor k = 20 {\displaystyle k=20} vinden we al

2432902008176640000 − 8752948036761600000 x {\displaystyle 2432902008176640000-8752948036761600000x}
+ 13803759753640704000 x 2 − 12870931245150988800 x 3 {\displaystyle +13803759753640704000x^{2}-12870931245150988800x^{3}}
+ 8037811822645051776 x 4 − 3599979517947607200 x 5 {\displaystyle +8037811822645051776x^{4}-3599979517947607200x^{5}}
+ 1206647803780373360 x 6 − 311333643161390640 x 7 {\displaystyle +1206647803780373360x^{6}-311333643161390640x^{7}}
+ 63030812099294896 x 8 − 10142299865511450 x 9 {\displaystyle +63030812099294896x^{8}-10142299865511450x^{9}}
+ 1307535010540395 x 10 − 135585182899530 x 11 {\displaystyle +1307535010540395x^{10}-135585182899530x^{11}}
+ 11310276995381 x 12 − 756111184500 x 13 {\displaystyle +11310276995381x^{12}-756111184500x^{13}}
+ 40171771630 x 14 − 1672280820 x 15 + 53327946 x 16 {\displaystyle +40171771630x^{14}-1672280820x^{15}+53327946x^{16}}
− 1256850 x 17 + 20615 x 18 − 210 x 19 + x 20 {\displaystyle -1256850x^{17}+20615x^{18}-210x^{19}+x^{20}}

Het is duidelijk dat in het tweede geval de coëfficiënten enorm verschillen in grootte. Een fout van ±0,001 in de grootste coëfficiënt heeft nauwelijks gevolgen, maar zo'n zelfde fout in de coëfficiënt van x 19 {\displaystyle x^{19}} geeft compleet andere nulpunten. Zelfs een fout van 10−10 geeft al onacceptabele onnauwkeurigheden. Voor nog grotere k {\displaystyle k} is dit nog veel erger. Dit zorgt ervoor dat veel standaard algoritmen de nulpunten van deze polynoom niet goed kunnen bepalen, tenzij enorm veel significante cijfers worden gebruikt.

In 1984 merkte Wilkinson zelf op: Voor mezelf sprekend beschouw ik het [werk aan deze polynoom] als de meest traumatische ervaring van mijn loopbaan.

Lagrange-vorm

Men kan deze polynoom ook uitdrukken in andere polynomen. Men schrijft de polynoom dan niet als een som van machten van x {\displaystyle x} met coëfficiënten, maar als som van andere polynomen met bijbehorende coëfficiënten. Iedere polynoom, dus ook de Wilkinson-polynoom, kan bijvoorbeeld als een som van lagrange-polynomen worden geschreven:

f ( x ) = a 1 ℓ 1 ( x ) + a 2 ℓ 2 ( x ) + … + a k ℓ k ( x ) {\displaystyle f(x)=a_{1}\ell _{1}(x)+a_{2}\ell _{2}(x)+\ldots +a_{k}\ell _{k}(x)}

met coëfficiënten a 1 , a 2 , … , a k {\displaystyle a_{1},a_{2},\ldots ,a_{k}} . Als we dit voor de Wilkinson-polynoom doen, blijkt dat deze polynoom feitelijk zelf een lagrange-polynoom is. De verandering aan de nulpunten door verandering van een coëfficiënt is nu veel zwakker.