Wilkinson-polynoom

Het Wilkinson-polynoom van graad ${\displaystyle k}$ is het polynoom

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

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

Het polynoom kan als test voor numerieke benaderingsmethoden worden gebruikt. Het numeriek bepalen van de nulpunten van het polynoom is namelijk een slecht geconditioneerd probleem. Dit wil zeggen dat de gevonden waarden van de nulpunten gevoelig zijn voor kleine onnauwkeurigheden in de berekening.

Polynomen worden normaal gesproken eerst helemaal uitgeschreven alvorens eraan te gaan rekenen, maar het is voor dit polynoom het probleem dat de coëfficiënten ontzaglijk groot worden, van de orde van grootte van ${\displaystyle k!}$, van k-faculteit. Het wordt ter illustratie voor ${\displaystyle k=7}$

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

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

${\displaystyle x^{20}-210x^{19}+20615x^{18}-1256850x^{17}}$

${\displaystyle \ +53327946x^{16}-1672280820x^{15}+40171771630x^{14}}$

${\displaystyle \ -756111184500x^{13}+11310276995381x^{12}}$

${\displaystyle \ -135585182899530x^{11}+1307535010540395x^{10}}$

${\displaystyle \ -10142299865511450x^{9}+63030812099294896x^{8}}$

${\displaystyle \ -311333643161390640x^{7}+1206647803780373360x^{6}}$

${\displaystyle \ -3599979517947607200x^{5}+8037811822645051776x^{4}}$

${\displaystyle \ -12870931245150988800x^{3}+13803759753640704000x^{2}}$

${\displaystyle \ -8752948036761600000x+2432902008176640000}$

Het is duidelijk dat in het tweede geval de coëfficiënten enorm verschillen in grootte. Een fout van ±0,001 in de constante heeft nauwelijks gevolgen, maar dezelfde fout in de coëfficiënt van ${\displaystyle x^{19}}$ geeft compleet andere nulpunten. Zelfs een fout van 10⁻¹⁰ geeft al onacceptabele onnauwkeurigheden en voor grotere ${\displaystyle k}$ wordt het nog erger. Dit zorgt ervoor dat veel standaard algoritmen de nulpunten van het polynoom niet goed kunnen bepalen, tenzij enorm veel significante cijfers worden gebruikt.

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

Lagrange-vorm

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

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

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