WikiDer > Wilkinson-Polynom

Das Wilkinson-Polynom des Grades ${displaystyle k}$ ist der Polynom

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

Das Nullen dieses Polynoms sind die ganzen Zahlen ${displaystyle 1,2,3,ldots,k}$.

Die praktische Relevanz dieses Polynoms liegt in seiner Verwendung als Test für numerische Näherungsverfahren. Die numerische Bestimmung der Nullstellen des Polynoms ist ein schlecht konditioniertes Problem. Das bedeutet, dass die gefundenen Werte der Nullstellen sehr empfindlich auf kleine Ungenauigkeiten in der Berechnung reagieren.

Normalerweise werden Polynome zuerst vollständig ausgeschrieben, bevor Berechnungen mit ihnen durchgeführt werden. Für dieses Polynom besteht das Problem darin, dass Koeffizienten immens werden, nämlich in der Größenordnung von grootte ${displaystyle k!}$ (${displaystyle k,}$Fakultät). Zur Veranschaulichung: für ${Anzeigestil k=7}$ haben wir

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

Vor dem ${Anzeigestil k=20}$ wir finden schon

${displaystyle 2432902008176640000-8752948036761600000x}$

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

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

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

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

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

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

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

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

Im zweiten Fall unterscheiden sich die Koeffizienten offensichtlich stark in der Größe. Ein Fehler von ±0,001 im größten Koeffizienten hat kaum Konsequenzen, aber ein ähnlicher Fehler im Koeffizienten von ${Displaystil x^{19}}$ ergibt ganz andere Nullen. Sogar ein Fehler von 10⁻¹⁰ gibt bereits inakzeptable Ungenauigkeiten. Für noch größere ${displaystyle k}$ ist das viel schlimmer. Dies stellt sicher, dass viele Standard Algorithmen kann die Nullstellen dieses Polynoms nicht gut bestimmen, es sei denn, eine enorme Menge bedeutende Zahlen werden verwendet.

Im 1984 bemerkte Wilkinson selbst auf: Für mich persönlich halte ich die [Arbeit an diesem Polynom] für die traumatischste Erfahrung meiner Karriere.

Lagrange-Form

Man kann dieses Polynom auch in anderen Polynomen ausdrücken. Das Polynom wird dann nicht als Summe der Potenzen von geschrieben ${Anzeigestil x}$ mit Koeffizienten, sondern als Summe anderer Polynome mit entsprechenden Koeffizienten. Zum Beispiel kann jedes Polynom, einschließlich des Wilkinson-Polynoms, als Summe von Lagrange-Polynome geschrieben sein:

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

mit Koeffizienten ${displaystyle a_{1},a_{2},ldots ,a_{k}}$. Wenn wir dies für das Wilkinson-Polynom tun, stellt sich heraus, dass dieses Polynom selbst ein Lagrange-Polynom ist. Die Änderung an den Nullstellen durch Änderung eines Koeffizienten ist jetzt viel schwächer.