Wilkinson-polynoom
Van Wikipedia
 |
Er wordt getwijfeld aan de feitelijke juistheid van een of meer onderdelen van dit artikel.
Raadpleeg de bijbehorende overlegpagina voor meer informatie, en pas na controle desgewenst het artikel aan. |
De Wilkinson-polynoom van graad k is de polynoom
.
De nulpunten van deze polynoom zijn de gehele getallen 
.
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 precieze waarden van de nulpunten zeer gevoelig zijn voor kleine onnauwkeurigheden bij 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! (k faculteit). Ter illustratie: voor k = 7 hebben we
- − 5040 + 13068x − 13132x2 + 6769x3 − 1960x4 + 322x5 − 28x6 + x7,
voor k = 20 vinden we al
- 2432902008176640000 − 8752948036761600000x
- + 13803759753640704000x2 − 12870931245150988800x3
- + 8037811822645051776x4 − 3599979517947607200x5
- + 1206647803780373360x6 − 311333643161390640x7
- + 63030812099294896x8 − 10142299865511450x9
- + 1307535010540395x10 − 135585182899530x11
- + 11310276995381x12 − 756111184500x13
- + 40171771630x14 − 1672280820x15 + 53327946x16
- − 1256850x17 + 20615x18 − 210x19 + x20.
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 x19 geeft compleet andere nulpunten. Zelfs een fout van 10-10 geeft al onacceptabele onnauwkeurigheden. Voor nog grotere 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.
[bewerk] Lagrange-vorm
Men kan deze polynoom ook uitdrukken in termen van andere (standaard-)polynomen. Men schrijft de polynoom dan niet als een som van machten van 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 worden geschreven als een som van Lagrange-polynomen:
met coëfficiënten a1, a2, ...,ak. 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.
