Horner-Schema

Grundidee und Rechenvorteil

Das Horner-Schema ist ein nach William George Horner benanntes Umformungsverfahren für Polynome. Es erleichtert vor allem die Berechnung von Funktionswerten; außerdem vereinfacht es Polynomdivisionen sowie die Bestimmung von Nullstellen und Ableitungen.

Für ein Polynom vom Grad n p(x)=b₀+b₁x+b₂x²+…+bₙxⁿ lautet die Hornerform p(x)=(…(bₙx+bₙ₋₁)x+…)x+b₀. Sie entsteht durch fortgesetztes Ausklammern von x. Statt Potenzen wie x², x³ usw. zu bilden, wird jeweils mit x multipliziert und anschließend der nächste Koeffizient addiert.

Für ein Polynom n-ten Grades benötigt die klassische Berechnung 2n−1 Multiplikationen: n−1 zur Bildung der Potenzen x² bis xⁿ und n zur Multiplikation dieser Potenzen mit den Koeffizienten. Im Horner-Schema genügen n Multiplikationen. Die Zahl der Additionen ist in beiden Fällen n.

Beispiel: 2x⁴−4x³−5x²+7x+11=(((2·x−4)·x−5)·x+7)·x+11. Bei Wiederverwendung der Zwischenergebnisse spart diese Form drei Multiplikationen. Sie eignet sich besonders für die Berechnung in umgekehrter polnischer Notation (UPN).

Tabellarische Berechnung

In der üblichen Tabelle stehen die Koeffizienten des Polynoms in der oberen Zeile. Der erste Koeffizient wird direkt in die untere Zeile übernommen. Dann wird jede neu erhaltene Zahl mit dem einzusetzenden x multipliziert; das Produkt kommt unter den nächsten Koeffizienten. Die Summe der jeweiligen Spalte wird wieder in die untere Zeile geschrieben. Die letzte Zahl dieser Zeile ist der Funktionswert.

Für 2x⁴−4x³−5x²+7x+11 und x=2 entstehen unten nacheinander 2, 0, −5, −3, 5. Daher ist der Funktionswert 5. Für x=5 ergeben sich die unteren Werte 2, 6, 25, 132, 671; hier ist der Funktionswert 671. Das Schema macht dabei auch sichtbar, dass größere eingesetzte Werte deutlich größere Zwischenergebnisse liefern können.

Zahlensysteme umrechnen

Eine Zahl in einem Stellenwertsystem kann als Polynom in der jeweiligen Basis aufgefasst werden: Im Dezimalsystem ist die Basis x=10, im Binärsystem x=2. Deshalb lässt sich das Horner-Schema zur Umwandlung in das Dezimalsystem verwenden.

Für 110101₂ gilt P₁₁₀₁₀₁(x)=1·x⁵+1·x⁴+0·x³+1·x²+0·x¹+1·x⁰. Mit x=2 wird dies in Hornerform zu ((((1·2+1)·2+0)·2+1)·2+0)·2+1. Die Zwischenergebnisse sind d₀=1, d₁=3, d₂=6, d₃=13, d₄=26 und d₅=53. Somit ist 110101₂=53₁₀.

Allgemein nimmt man die erste Ziffer als Anfangswert. Danach wird das bisherige Ergebnis wiederholt mit der Basis multipliziert und die nächste Ziffer addiert, bis alle Ziffern verarbeitet sind.

Beim kaskadierten Horner-Schema werden für die Multiplikation nur die Einer verwendet; Zehner werden als Überträge in eine weitere Zeile geschrieben. So bleiben die Rechnungen innerhalb des kleinen Einmaleins, es sind aber mehr Zwischenschritte nötig. Die senkrecht kaskadierende Schreibweise ordnet dieselbe Rechnung vertikal an; das Ergebnis kann am Ende in der Ergebniszeile abgelesen werden.

Für die umgekehrte Umrechnung von einer Dezimalzahl in eine andere Basis wird fortgesetzt durch diese Basis dividiert. Die Divisionsreste ergeben die Ziffern der Zielzahl von rechts nach links. Beim Beispiel 53 zur Basis 2 liefern die wiederholten Divisionen die Ziffern 110101₂.

Polynomdivision und Verschiebung

Bei der Division eines Polynoms durch einen linearen Divisor kann das Horner-Schema die Koeffizienten des Quotienten und den Rest direkt liefern. Für (aₙxⁿ+aₙ₋₁xⁿ⁻¹+…+a₁x+a₀):(x+d) mit Quotientenkoeffizienten eₙ₋₁,…,e₀ und Rest r gilt: eₙ₋₁=aₙ, eₖ=aₖ₊₁−d·eₖ₊₁ für k=n−2,n−3,…,0, r=a₀−d·e₀.

Der letzte Tabellenwert ist der Divisionsrest. Bei einer Division durch x−a gilt P(x)=(x−a)E(x)+r und damit P(a)=r. Das verbindet Funktionswertberechnung und Polynomdivision unmittelbar.

Auch ein Divisor zweiten Grades x²+d₁x+d₀ ist möglich. Dann lauten die rekursiven Quotientenkoeffizienten eₙ₋₂=aₙ, eₙ₋₃=aₙ₋₁−d₁eₙ₋₂, eₖ=aₖ₊₂−d₁eₖ₊₁−d₀eₖ₊₂, und der Rest hat die Form r₁x+r₀ mit r₁=a₁−d₁e₀−d₀e₁, r₀=a₀−d₀e₀. Beispielsweise ergibt die Division (−6x⁶+14x⁵−8x⁴−2x³+8x−6):(x²−2x+1) den Quotienten −6x⁴+2x³+2x²−2 und den Rest 4x−4.

Das vollständige Horner-Schema kann außerdem ein Polynom um den Wert a verschieben. Mit x=a+y wird P(x)=P(a+y)=Pₐ(y). Dazu wird P(x) wiederholt durch x−a dividiert. Die dabei entstehenden Reste r₀,…,rₙ sind die Koeffizienten von Pₐ(y)=∑ᵢ₌₀ⁿrᵢyⁱ. Für P(x)=x³−2x−5 und a=2 erhält man P₂(x)=P(2+x)=x³+6x²+10x−1.

Ableitungen und Nullstellen

Teilt man P(x) durch x−x₀, so liefert das Horner-Schema ein Quotientenpolynom Pₑ(x) und den Rest P(x₀). Aus (P(x)−P(x₀))/(x−x₀)=Pₑ(x) folgt mit dem Differenzenquotienten: P′(x₀)=Pₑ(x₀). Die Koeffizienten in der unteren Zeile des ersten Horner-Schemas bilden also das Polynom Pₑ; wendet man das Schema darauf nochmals bei x₀ an, erhält man den Ableitungswert. Für P(x)=x⁵−4x⁴+4x³+3x²−8x+4 bei x=2 zeigt das Schema P(2)=0 und P′(2)=4. Die direkte Probe mit P′(x)=5x⁴−16x³+12x²+6x−8 ergibt ebenfalls P′(2)=4.

Bei einer vollständigen Verschiebung x=a+y und Pₐ(y)=∑ᵢ₌₀ⁿrᵢyⁱ lassen sich auch höhere Ableitungen ablesen: P⁽ᵏ⁾(a)=k!·rₖ.

Zur Nullstellenbestimmung kann das Horner-Schema vermutete Nullstellen schnell prüfen, denn bei Division durch x−a ist a genau dann Nullstelle, wenn der Rest 0 ist. Nach dem Satz über rationale Nullstellen ist eine ganzzahlige Nullstelle ein Teiler des konstanten Koeffizienten b₀. Bei x³−6x²−x+6=0 mit b₀=6 sind daher ±1, ±2, ±3 und ±6 Kandidaten. Das Horner-Schema zeigt als tatsächliche Nullstellen −1, +1 und +6; nach einer gefundenen Nullstelle kann der zugehörige Linearfaktor abgespalten werden. Auch beim Newton-Verfahren ist das Schema nützlich, weil in jedem Schritt P(xₙ) und P′(xₙ) benötigt werden.