Horner-Schema

Das Horner-Schema (nach William George Horner) ist ein Umformungsverfahren für Polynome, um die Berechnung von Funktionswerten so einfach wie möglich zu machen.

Funktion des Hornerschemas

In der Analysis müssen häufig die Werte einer Funktion (Mathematik) und die ihrer Ableitung (Mathematik) berechnet werden. Sei es, um eine Nullstelle zu bestimmen, einen Überblick über eine Funktion zu erhalten, oder um einen Graphen zu skizzieren.

Bei Polynomen erfordert dabei das Einsetzen der x-Werte in die Funktionsgleichung und die Berechnung der Potenzen bei nicht einfachen Zahlen und vor allem bei großen Potenzen erhebliche Mühe. Es wird viel Zeit benötigt und die Fehlerwahrscheinlichkeit ist hoch. Dabei gibt es für Polynome schon lange das Horner-Schema.

Durch fortgesetztes Ausklammern der freien Polynomvariablen x wird das Polynom als Schachtelung von Produkten und Summen dargestellt. In der umgewandelten Darstellung kommt keine Potenzfunktion, sondern nur noch Multiplikation und Addition vor.

Beispiel

${\begin{matrix}I)&2x^{4}-4x^{3}-5x^{2}+7x+11&=&\\II)&\left(2x^{3}-4x^{2}-5x+7\right)x+11&=&\\III)&\left(\left(2x^{2}-4x-5\right)x+7\right)x+11&=&\\IV)&\left(\left(\left(2x-4\right)x-5\right)x+7\right)x+11&&\\\end{matrix}}$

Rechenvorteil:

Der Ausdruck IV) mag, wegen der etwas unübersichtlichen Klammerschachtelung, komplizierter erscheinen als Ausdruck I). IV) bietet jedoch einen handfesten Rechenvorteil gegenüber I):

Um mit I) einen Funktionswert für eine bestimmte Zahl x auszurechnen, benötigt man 7 Multiplikationen: 3 Multiplikationen für das Errechnen der Werte x², x³ und x⁴ und 4 weitere Multiplikationen, um die Werte x bis x⁴ mit ihren Koeffizienten - in unserem Beispiel 7, -5, -4 und 2 - zu multiplizieren.

In IV) sind es hingegen nur 4 Multiplikationen.

Die Zahl der - rechnerisch weniger aufwändigen - Additionen ist in beiden Fällen gleich, nämlich 4.

Je länger das Polynom ist, desto stärker schlägt dieser Rechenvorteil zu Buche. Im günstigsten Fall lässt sich der Aufwand für Multiplikationen auf fast die Hälfte reduzieren.

Anwendungsmöglichkeiten des Hornerschemas

Umwandlung zwischen verschiedenen Zahlensystemen

Unsere vertraute Darstellung von Zahlen im dezimalen Stellenwertsystem ist nichts anderes als eine verkürzte Schreibweise für besondere Polynome, nämlich Polynome mit der Basis x = 10. Das gleiche gilt für alle anderen Stellenwertsysteme, beispielsweise das Binärsystem. Dort ist x = 2. Wir können uns das Horner-Schema zunutze machen, um Zahlen aus jedem anderen Stellenwertsystem in das Dezimalsystem umzuwandeln.

Beispiel: Die Binärzahl 110101 soll in das Dezimalsystem umgewandelt werden. Wie lautet die sich ergebende Dezimalzahl d?

Wir schreiben 110101_binär als Polynom:

$\mathrm {d=1\cdot 2^{5}+1\cdot 2^{4}+0\cdot 2^{3}+1\cdot 2^{2}+0\cdot 2^{1}+1\cdot 2^{0}}$

Nach dem Horner-Schema:

$\mathrm {d=((((1\cdot 2+1)\cdot 2+0)\cdot 2+1)\cdot 2+0)\cdot 2+1}$

Wir brauchen das nun nicht in einem Zuge auszurechnen, sondern können schrittweise vorgehen. Jeder Schritt besteht aus einer Multiplikation mit 2 und einer Addition. Der Übersicht halber schreiben wir die Schritte untereinander und notieren die Zwischenergebnisse:

${\begin{matrix}d_{0}&=&1&\qquad {\mbox{(erste Ziffer)}}\\d_{1}&=&1\cdot 2+1=&3\qquad {\mbox{(zweite Ziffer)}}\\d_{2}&=&3\cdot 2+0=&6\qquad {\mbox{(dritte Ziffer)}}\\d_{3}&=&6\cdot 2+1=&13\qquad {\mbox{(vierte Ziffer)}}\\d_{4}&=&13\cdot 2+0=&26\qquad {\mbox{(fünfte Ziffer)}}\\d_{5}&=&26\cdot 2+1=&53\qquad {\mbox{(sechste Ziffer)}}\\\mathbf {d} &\mathbf {=} &\mathbf {53} &\end{matrix}}$

Wir haben unsere gesuchte Dezimaldarstellung gefunden.

Verallgemeinert lautet das Verfahren: Eine Zahl aus einem Stellenwertsystem zur Basis x wird in das Dezimalsystem umgewandelt, indem

• der Wert der ersten Ziffer als Anfangswert genommen wird
• danach schrittweise das Ergebnis aus dem vorigen Schritt mit x multipliziert und die nächste Ziffer addiert wird
• bis alle Ziffern aufgebraucht sind.

Nullstellenbestimmung

f(x) = 2x³ + 4x² + 8

Geschichte

William George Horner erschuf dieses Verfahren zur Lösung algebraischer Gleichungen. Eigentlich wurde die Idee zu diesem Verfahren bereits vor 500 Jahren in China entdeckt, hat sich aber nicht verbreitet.

Quellen

• Facharbeit zum Thema

---

Weblinks:

• Artikel zum Horner-Schema auf linux-related.de