|
Polynomdarstellung nach Knuth |
| |
- Knuth hat 1969 gezeigt, daß man ein Polynom p(x) vom Grad
n >= 4 mit floor(n/2) + 2 Multiplikationen und n+1 Additionen
auswerten kann.
- Für n=5 sind das z.B. 2 Multiplikationen und 6 Additionen,
also weniger als mit dem Horner-Schema.
- Das Polynom muß dazu in eine besondere Darstellung umgerechnet
werden. Diese lautet
p(x) = (...((q(x+rho)((x+rho)2-z1)+R1)
((x+rho)2-z2)+R2)...)
((x+rho)2-zm)+Rm
- Dabei ist n entweder 2m oder 2m+1, q(.) ist
entweder quadratisch oder linear und zi
bzw. Ri sind reelle Koeffizienten, rho wird
zur Nullpunktverschiebung benutzt.
- Mit funktionentheoretischen Methoden kann man zeigen, daß diese
Darstellung immer möglich ist, wenn das Ausgangspolynom nur Nullstellen
mit nichtnegativem Realteil hat. Dies kann aber durch eine Nullpunktverschiebung
immer erreicht werden, wenn man eine obere Schranke für den Betrag der
Nullstellen kennt. Dazu wird hier die Schranke von Marden benutzt:
|z| <= rho=2*max{ |an-i/an|1/i }
wobei an der Höchstkoeffizient ist. Deshalb
erscheint in der Darstellung nicht x sondern x+rho.
-rho ist der "Entwicklungspunkt" in der Ergebnisliste. Die
zi sind die Nullstellen des Polynoms , das die ungeradzahligen
Koeffizienten des (verschobenen) Ausgangspolynoms zu Koeffizienten hat.
(Der Beweis, dass die zi stets reell sind (mit Mitteln der
komplexen Funktionentheorie) ist ziemlich tiefliegend)
|
| |
|
Die Eingaben |
| |
- Der Grad n des Polynoms. Wichtig: n >= 4.
- Die Koeffizienten an,
... ,a0. an ist der Hoechstkoeffizient.
Wichtig: an*a0 ungleich 0.
|
| |
|
Die Ausgaben |
| |
- Die Originalkoeffizienten.
- Koeffizienten einer Taylorentwicklung (Zwischenresultat).
- Koeffizienten des ungeraden Anteils (Zwischenresultat).
- Die neuen Koeffizienten zi
bzw. Ri.
- Eine Tabelle von Probeauswertungen, bestehend aus den x-Stellen und den
Differenzen der Auswertungen des Polynoms in der Originaldarstellung und in
der Knuth-Darstellung.
|
| |
|
Fragen ?! |
| |
- Beurteilen Sie die Rundungsfehlereinflüsse. Warum
treten häufig grössere Fehler auf ?
|
| |
|
|
| |
|
|