Das Horner-Schema (nach William George Horner) ist ein Umformungsverfahren für Polynome, um die Berechnung von Funktionswerten zu erleichtern. Es kann genutzt werden, um die Polynomdivision sowie die Berechnung von Nullstellen und Ableitungen zu vereinfachen.
Definition Zu einem Polynom vom Grade aus einem beliebigen Polynomring ist das Horner-Schema definiert als:
Funktion des Hornerschemas Rechenvorteile Bei Polynomen in der klassischen Schreibweise müssen die Potenzen , usw. errechnet werden, wenn der Funktionswert an einer Stelle errechnet werden soll. Im umgeformten Polynom nach dem Horner-Schema kommen keine Potenzen, sondern nur noch Multiplikation und Addition vor. Die Berechnung wird beschleunigt, weil weniger Multiplikationen nötig sind: Deren Anzahl wird durch die Anwendung des Horner-Schemas auf fast die Hälfte reduziert.
In der klassischen Schreibweise sind Multiplikationen bei einem Polynom vom Grad nötig:
Multiplikationen zur Bildung der Potenzen ;Bei der Berechnung der Potenzen , k≥2, kann man zuerst die niedrigen und dann die höheren Potenzen berechnen. Damit macht man sich jeweils zunutze, dass schon berechnet ist, wenn gebraucht wird. Für braucht man daher nur eine weitere Multiplikation und nicht deren . weitere Multiplikationen zur Multiplikation der Potenzen mit ihren Koeffizienten.
Insgesamt benötigt man deshalb Multiplikationen für die Berechnung.
Im Hornerschema hingegen kommt man mit Multiplikationen aus.
Die Zahl der – rechnerisch weniger aufwändigen – Additionen ist in beiden Fällen gleich, nämlich .
Verfahren Durch fortgesetztes Ausklammern der freien Polynomvariablen wird das Polynom als Schachtelung von Produkten und Summen dargestellt.
Beispiel Das folgende Beispiel illustriert den geringeren Rechenaufwand beim Hornerschema:
In der klassischen Darstellung (linke Seite) werden zusätzlich zu den Additionen, Subtraktionen und Multiplikationen noch drei Potenzen gebildet, die durch die Verwendung des Horner-Schemas (rechte Seite) von den Multiplikationen erfasst werden und somit wegfallen. Bei Wiederverwendung der Zwischenergebnisse spart man sich dadurch drei Multiplikationen.
Anwendung In der Analysis müssen häufig die Werte eines Polynoms und seiner Ableitung berechnet werden: Sei es, um eine Nullstelle zu bestimmen, eine Kurvendiskussion durchzuführen oder um einen Graphen zu skizzieren.
Die hier dargestellte Form eignet sich besonders gut für die Berechnung in der umgekehrten polnischen Notation (UPN).
Zwischen 1975 und 2003 wurde die Einkommensteuer in der BRD nach dem Horner-Schema berechnet, um Rundungsfehler bei der Kalkulation mit elektronischen Taschenrechnern oder Computern zu vermeiden und damit die Rechtssicherheit zu gewährleisten. Bundesministerium der Finanzen: Interaktiver Lohn- und Einkommensteuerrechner: RundungsvorschriftDie Einkommensteuertarif-Formeln seit 1958 Wolfgang und Johannes Parmentier: Die Einkommensteuertarif-Formeln seit 1958.
Tabellarische Schreibweise des Hornerschemas Herleitung Betrachten wir nochmals obiges Beispiel und setzen:
Nun überträgt man die Koeffizienten, die Zwischenprodukte und Teilsummen in eine dreizeilige Tabelle, wobei in die erste Zeile die Koeffizienten eingetragen werden. In die dritte Zeile kommen die Teilsummen. Dabei wird der erste Koeffizient des Polynoms direkt übernommen. Die zuvor berechnete Teilsumme multipliziert mit ergibt dann den nächsten Summanden, den man dann in die zweite Zeile unter den folgenden Koeffizienten einträgt.
So erhält man nach und nach das folgende Rechenschema:
Beispiel Die Berechnung des obigen Polynoms für mit Hilfe des Horner-Schemas stellt sich wie folgt dar: 2 −4 −5 7 11 2 4 0 −10 −6 2 0 −5 −35 Den Wert, für den man das Polynom berechnen möchte, schreibt man dabei zur Erinnerung üblicherweise in die mittlere Zeile vor das Schema, die erste Zahl der oberen Zeile schreibt man auch in die untere Zeile. Anschließend multipliziert man diese Zahl mit dem Wert, für den man das Polynom berechnen möchte, schreibt das Ergebnis in die mittlere Zeile der zweiten Spalte, addiert die beiden Werte der zweiten Spalte und schreibt das Ergebnis in die untere Zeile. Anschließend wird wiederholt die Spaltensumme aus der unteren Zeile mit dem Wert, für den man das Polynom berechnen möchte, multipliziert und das Ergebnis in die mittlere Zeile der nächsten Spalte geschrieben, die Spalte addiert usw. Die letzte Zahl (hier fünf) ist das Endergebnis.
Für ergeben sich jedoch wesentlich höhere Zwischenergebnisse: 2 −4 −5 7 11 5 10 30 125 660 2 6 25 132 671
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 . Das Gleiche gilt für alle anderen Stellenwertsysteme, beispielsweise das Binärsystem. Dort ist . Wir können uns das Horner-Schema zunutze machen, um Zahlen aus jedem anderen Stellenwertsystem in das Dezimalsystem umzuwandeln, und umgekehrt.
Umwandlung ins Dezimalsystem Beispiel: Die Binärzahl 110101 soll in das Dezimalsystem umgewandelt werden. Wie lautet die sich ergebende Dezimalzahl ?
Wir schreiben 110101binär als Polynom:
so ist
Nach dem Horner-Schema:
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:
Wir haben unsere gesuchte Dezimaldarstellung gefunden.
Verallgemeinert lautet das Verfahren: Eine Zahl aus einem Stellenwertsystem zur Basis wird in das Dezimalsystem umgewandelt, indem der Wert der ersten Ziffer als Anfangswert genommen wird danach schrittweise das Ergebnis aus dem vorigen Schritt mit multipliziert und die nächste Ziffer addiert wird bis alle Ziffern aufgebraucht sind. Am einfachsten schreibt man die Rechnung wieder in tabellarischer Form auf: 1101012)26122652136132653
Kaskadiertes Horner-Schema Der Nachteil des einstufigen Horner-Schemas besteht darin, dass Multiplikationen mit großen Faktoren nötig werden können (im obigen Beispiel 2 · 26 = 52). Um innerhalb des kleinen Einmaleins zu bleiben, wendet man das kaskadierte oder mehrstufige Horner-Schema an. Hier werden jedoch mehr Zwischenschritte benötigt.
Dabei wird nur der Einer für die Multiplikation herangezogen. Der Zehner wird wie ein Übertrag in die nächste Zeile unter den Einer geschrieben. Bei der 13 aus dem obigen Beispiel wird also die 3 unter die 12 geschrieben und die 1 unter die 3. Im nächsten Schritt wird nur 3 · 2 + 0 = 6 gerechnet (statt 13 · 2 + 0 = 26). Dieses Ergebnis wird ebenso behandelt; der Zehner ist hier 0. Die letzte Rechnung (6 · 2 + 1), ergibt wieder 13. Der Einer dieses Ergebnisses ist die letzte Ziffer des Endergebnisses.
1101012) 261261213636300101
Um die weiteren Ziffern zu berechnen, wird auf die in der letzten Zeile stehenden Zehner (00101) dasselbe Schema erneut angewandt. Dabei kann man die führenden Nullen vernachlässigen:
1101012) 2612612136363001012) 24 12500
Da jetzt nur noch Nullen in der Übertragszeile stehen, ist das Verfahren beendet. Das Gesamtergebnis (53) liest man in der letzten Spalte der Einer von unten nach oben.
Senkrecht kaskadierende Schreibweise Die Ziffern der Ausgangszahl werden zunächst senkrecht untereinander geschrieben. Links daneben wird eine senkrechte Linie gezogen. Unterhalb der letzten Ziffer eine waagerechte Linie, unter der am Ende das Ergebnis steht.
Zuerst wird die höchstwertige Ziffer (die erste 1) eine Zeile tiefer in die vorhergehende Spalte übertragen. Diese steht jetzt links neben der zweiten Ziffer (ebenfalls eine 1). Die linke Zahl wird mit der Zahlenbasis (hier 2) multipliziert, die rechte Zahl addiert (1 · 2 + 1). Vom Ergebnis (3) wird der Zehner eine Spalte weiter links geschrieben, der Einer eine Zeile tiefer.
Das gleiche Verfahren wird mit dem Einer des Ergebnisses (3) und der nächsten Ziffer (0) durchgeführt. Das Ergebnis (3 · 2 + 0 = 6) wird ebenso notiert wie das vorige Ergebnis.
Die dritte Rechnung lautet 6 · 2 + 1 = 13, danach ist 3 · 2 + 0 = 6 und schließlich wieder 6 · 2 + 1 = 13 zu berechnen. Wie in den vorherigen Schritten werden Einer und Zehner des Ergebnisses diagonal untereinander geschrieben.
Unter der waagerechten Linie steht jetzt die letzte Ziffer des Endergebnisses (3).
1 1 0 1 0 1 (2) 1 11 0 1 0 1 (2) 1 0 11 30 1 0 1 (2) 1 0 11 0 30 61 0 1 (2) 1 0 11 0 30 1 61 30 1 (2) 1 0 11 0 30 1 6 1 0 3 0 6 1 (2) 1 0 11 0 30 1 61 0 30 1 61 3(2)
Zur Berechnung der weiteren Ziffern wird jetzt die führende Spalte mit den bisher unberücksichtigten Zehnern genauso behandelt wie die Ausgangszahl.
Die erste gültige Ziffer wird eine Zeile tiefer in die vorherige Spalte übertragen. Diese Zahl (1) wird mit der Basis (2) multipliziert und zum Produkt (2) die nächste Ziffer (0) addiert. Zehner und Einer des Ergebnisses (02) werden diagonal wie oben gezeigt in das Schema eingetragen.
Das Ergebnis der letzten Rechnung (2 · 2 + 1 = 05) wird ebenso eingetragen. Die Einer dieses Ergebnisses (5) sind die nächste Ziffer des Endergebnisses.
1 0 11 0 30 1 61 0 30 1 6 1 3(2) 1 0 11 0 30 1 61 1 0 3 0 1 6 1 3(2) 1 0 11 0 30 1 610 10 30 2 1 6 1 3(2) 1 0 11 0 30 1 610 10 30 0 2 1 6 1 5 3(2) 1 0 11 0 30 1 610 1 0 3 0 0 2 1 6 1 5 3(2)
Da in der Zehnerspalte nur noch Nullen stehen, ist die Rechnung beendet. Das Endergebnis (53) lässt sich jetzt in der Ergebniszeile ablesen, diesmal sogar in der richtigen Reihenfolge.
Verfahren für die umgekehrte Richtung Auf die umgekehrte Weise lässt sich eine Dezimalzahl in eine Zahl eines anderen Zahlensystems umrechnen. An Stelle einer fortgesetzten Multiplikation mit der Basis des anderen Zahlensystems tritt eine fortgesetzte Division durch diese Zahl. Die Ziffern der Zahl im anderen Zahlensystem ergeben sich von rechts nach links durch die Divisionsreste.
In der Tabellenschreibweise werden die Ziffern der Ausgangszahl untereinander geschrieben und für das Ergebnis wird eine waagerechte Linie gezogen. Die senkrechte Linie wird hier jedoch rechts der Ziffern gezogen. Zur Erinnerung kann die Zahlenbasis rechts unten notiert werden.
5 3 (2)
Die erste Ziffer, vermehrt um eine führende Null, (05) wird durch die Zahlenbasis (2) geteilt. Der Quotient (2) wird in die vorangehende Spalte geschrieben. Der Rest (1) in die Zeile darunter.
05 3 (2) 205 13 (2)
Dieser Rest bildet mit der nächsten Ziffer (3) eine neue zweistellige Zahl (13). Diese Zahl wird wiederum durch die Basis geteilt, das Ergebnis (6 Rest 1) wie oben diagonal in das Schema eingetragen.
205 13 (2) 205 613 1(2)
Da jetzt alle Ziffern abgearbeitet sind, ist der Rest der letzten Rechnung (1) die letzte Ziffer des Endergebnisses.
Die nicht bearbeiteten Quotienten werden wie eine neue Dezimalzahl behandelt (26), auf die dasselbe Verfahren angewandt wird.
0205 613 1(2) 10205 0613 1(2) 10205 0613 1(2) 10205 30613 01(2)
Die gewonnene Ziffer ist eine 0. In der Spalte der unbearbeiteten Quotienten steht jetzt eine 13.
010205 30613 01(2) 0010205 130613 01(2) 0010205 130613 01(2) 0010205 6130613 101(2)
Nach diesem Schritt steht in der Quotientenspalte eine 06. Die führende Null wird ignoriert, das Verfahren startet mit der 6.
0010205 06130613 101(2) 0010205 306130613 0101(2)
Die jetzt noch zu behandelnde Zahl ist 3.
0010205 0306130613 0101(2) 0010205 10306130613 10101(2)
Jetzt ist nur noch eine 1 übrig.
0010205 010306130613 10101(2) 0010205 0010306130613 110101(2) 0010205 0010306130613 110101(2)