Horner-Schema

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 $p(x)=b_0 + b_1 x + b_2 x^2 + \dots + b_n x^n$ vom Grade n aus einem beliebigen Polynomring ist das Horner-Schema definiert als:

$p(x)= (\dots ( b_n x + b_{n-1} )x + \dots )x + b_0.$^[1]

Funktion des Hornerschemas

Rechenvorteile

Bei Polynomen in der klassischen Schreibweise müssen die Potenzen a², a³ usw. errechnet werden, wenn der Funktionswert an einer Stelle x = a 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 2n − 1 Multiplikationen bei einem Polynom vom Grad n nötig:

• n − 1 Multiplikationen zur Bildung der Potenzen x², x³, … xⁿ;
• weitere n Multiplikationen zur Multiplikation der Potenzen x, x², x³, … xⁿ mit ihren Koeffizienten.^[2]

Im Hornerschema hingegen kommt man mit n Multiplikationen aus.

Die Zahl der – rechnerisch weniger aufwendigen – Additionen ist in beiden Fällen gleich, nämlich n.

Verfahren

Durch fortgesetztes Ausklammern der freien Polynomvariablen x wird das Polynom als Schachtelung von Produkten und Summen dargestellt.

Beispiel

Das folgende Beispiel illustriert den geringeren Rechenaufwand beim Hornerschema:

$11 + 7x - 5x^2 -4x^3 + 2x^4 \;=\; 11 + x \cdot\left(7 + x \cdot(-5 + x \cdot(-4 + x \cdot 2))\right)$

In der klassischen Darstellung (linke Seite) werden 7 Multiplikationen benötigt, davon 3 zur Bildung der Potenzen x², x³, x⁴.^[2] Im Horner-Schema (rechte Seite) kommt man dagegen mit 4 Multiplikationen aus.

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).

Tabellarische Schreibweise des Hornerschemas

Herleitung

Betrachten wir nochmals obiges Beispiel und setzen:

$\alpha\; :=$	$\;\;2$
$\beta\; :=$	$\;\,\;2\cdot x-4 = \alpha\cdot x -4$
$\gamma\; :=$	$\;\;(2\cdot x-4)\cdot x-5 = \beta\cdot x -5$
$\delta\; :=$	$\;((2\cdot x-4)\cdot x-5)\cdot x+7 = \gamma\cdot x +7$
$\epsilon\; :=$	$(((2\cdot x-4)\cdot x-5)\cdot x+7)\cdot x+11 = \delta\cdot x +11$

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 x 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:

${\, 2}$

${\,-4}$

${\,-5}$

${\, 7}$

${\,11}$

$\Bigg\downarrow$

+

+

+

+

$\,\alpha x$

$\,\beta x$

$\,\gamma x$

$\,\delta x$

$\nearrow$

$\mid$

$\nearrow$

$\mid$

$\nearrow$

$\mid$

$\nearrow$

$\mid$

$\cdot{x}$

=

$\cdot{x}$

=

$\cdot{x}$

=

$\cdot{x}$

=

$\nearrow$

$\downarrow$

$\nearrow$

$\downarrow$

$\nearrow$

$\downarrow$

$\nearrow$

$\downarrow$

${\,2=\alpha}$

${\,\alpha x-4=\beta}$

${\,\beta x-5=\gamma}$

${\,\gamma x+7=\delta}$

${\,\delta x+11=\epsilon}$

Beispiel

Die Berechnung des obigen Polynoms für x = 2 mit Hilfe des Horner-Schemas stellt sich wie folgt dar:

	2	−4	−5	7	11
2 )		4	0	−10	−6
	2	0	−5	−3	5

Den Wert, für den man das Polynom berechnen möchte, schreibt man dabei üblicherweise in die zweite Zeile vor das Schema. Anschließend multipliziert man die erste Zahl im Schema mit diesem Wert und addiert das Ergebnis zur ersten Zeile (letzte Zeile). Multiplikation dieses Ergebniswertes in der letzten Zeile mit dem Wert, für den man das Polynom berechnen möchte, liefert jeweils den folgenden Ergebniswert. Die letzte Zahl (hier fünf) ist das Endergebnis.

Für x = 5 ergeben sich jedoch wesentlich höhere Zwischenergebnisse:

	2	−4	−5	7	11
5 )		10	30	125	660
	2	6	25	132	671

Durch Anwendung des kaskadierten Horner-Schemas (s.u.) wird zwar die Anzahl der Multiplikationen erhöht, die Zwischenergebnisse jedoch verkleinert, was für eine Berechnung des Polynoms von Hand vorteilhafter ist:

			2
		06	-4
		25	-5
	13	32	7
06	17	21	11
6	7	1	(5)

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, und umgekehrt.

Umwandlung ins Dezimalsystem

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:

$P_{110101}(x)=1\cdot x^5 + 1\cdot x^4 + 0\cdot x^3 + 1\cdot x^2 + 0\cdot x^1 + 1\cdot x^0$

so ist

$\mathrm{d} = P_{110101}(2) = 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& &\mbox{(1. Ziffer)}\\ d_1&=&d_0\cdot 2 + 1&=& 1 \cdot 2 + 1&=& 3& &\mbox{(2. Ziffer)}\\ d_2&=&d_1\cdot 2 + 0&=& 3 \cdot 2 + 0&=& 6& &\mbox{(3. Ziffer)}\\ d_3&=&d_2\cdot 2 + 1&=& 6 \cdot 2 + 1&=& 13& &\mbox{(4. Ziffer)}\\ d_4&=&d_3\cdot 2 + 0&=&13 \cdot 2 + 0&=& 26& &\mbox{(5. Ziffer)}\\ d_5&=&d_4\cdot 2 + 1&=&26 \cdot 2 + 1&=& 53& &\mbox{(6. Ziffer)}\\ \mathbf{d}&=&d_5& & &=&\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.

Am einfachsten schreibt man die Rechnung wieder in tabellarischer Form auf:

	1	1	0	1	0	1
2 )		2	6	12	26	52
	1	3	6	13	26	53

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.

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.

	1	1	0	1	0	1
2 )		2	6	12	6	12
	1	3	6	3	6	3
		0	0	1	0	1

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:

	1	1	0	1	0	1
2 )		2	6	12	6	12
	1	3	6	3	6	3
		0	0	1	0	1
2 )					2	4
				1	2	5
					0	0

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.

Vereinfachte Schreibweise

Das kaskadierte Horner-Schema kann durch etwas mehr Kopfrechnen stark vereinfacht dargestellt werden. Die Rechnung beschleunigt sich dadurch erheblich.

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       1 1         0         1         0         1         (2)

1     0 1 1       3 0         1         0         1         (2)

1     0 1 1     0 3 0       6 1         0         1         (2)

1     0 1 1     0 3 0     1 6 1       3 0         1         (2)

1     0 1 1     0 3 0     1 6 1     0 3 0       6 1         (2)

1     0 1 1     0 3 0     1 6 1     0 3 0     1 6 1       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 1 1     0 3 0     1 6 1     0 3 0     1 6 1       3 (2)

1     0 1 1     0 3 0     1 6 1   1 0 3 0     1 6 1       3 (2)

1     0 1 1     0 3 0     1 6 1 0 1 0 3 0   2 1 6 1       3 (2)

1     0 1 1     0 3 0     1 6 1 0 1 0 3 0 0 2 1 6 1   5   3 (2)

1     0 1 1     0 3 0     1 6 1 0 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)

2 05     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.

2 05     13       (2)

2 05   6 13     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.

02 05     6 13       1 (2)

1 02 05     06 13       1 (2)

1 02 05     06 13       1 (2)

1 02 05   3 06 13     0 1 (2)

Die gewonnene Ziffer ist eine 0. In der Spalte der unbearbeiteten Quotienten steht jetzt eine 13.

01 02 05     3 06 13       0 1 (2)

0 01 02 05     13 06 13       0 1 (2)

0 01 02 05     13 06 13       0 1 (2)

0 01 02 05   6 13 06 13     1 0 1 (2)

Nach diesem Schritt steht in der Quotientenspalte eine 06. Die führende Null wird ignoriert, das Verfahren startet mit der 6.

0 01 02 05     06 13 06 13       1 0 1 (2)

0 01 02 05   3 06 13 06 13     0 1 0 1 (2)

Die jetzt noch zu behandelnde Zahl ist 3.

0 01 02 05     03 06 13 06 13       0 1 0 1 (2)

0 01 02 05   1 03 06 13 06 13     1 0 1 0 1 (2)

Jetzt ist nur noch eine 1 übrig.

0 01 02 05     01 03 06 13 06 13       1 0 1 0 1 (2)

0 01 02 05   0 01 03 06 13 06 13     1 1 0 1 0 1 (2)

0 01 02 05   0 01 03 06 13 06 13     1 1 0 1 0 1 (2)

Nach der letzten Rechnung steht in der Quotientenspalte eine 0. Das Verfahren ist damit abgeschlossen. In der Ergebniszeile steht die gesuchte Zahl in richtiger Reihenfolge.

Polynomdivision

Polynomdivision mit linearem Divisor

Am folgendem Beispiel

$(x^5-4x^4+4x^3+3x^2-8x+4)\,:\,({x - 2})$

wird zunächst die Polynomdivision mit einem linearem Divisor im Horner-Schema dargestellt.

Die Polynomdivision wird üblicherweise in einer schriftlichen Form durchgeführt.

$\begin{matrix} {}&(1x^5&-4x^4&+4x^3&+3x^2&-8x&+4)&:&({1x - 2}) = {1x^4 - 2x^3 + 0x^2 + 3x - 2}\\ -(&\underline{1x^5}&\underline{-2x^4})\\ &&-2x^4\\ &-(&\underline{-2x^4}&\underline{+4x^3})\\ &&&0x^3\\ &&-(&\underline{0x^3}&\underline{-0x^2})\\ &&&&3x^2\\ &&&-(&\underline{3x^2}&\underline{-6x})\\ &&&&&-2x\\ &&&&-(&\underline{-2x}&\underline{+4})\\ &&&&&&0\\ \end{matrix}$

Lässt man nun die Potenzen von x weg, so erhält man folgende Darstellung:

(	1	−4	4	3	−8	4	)	:	( 1	−2	)	=	1	−2	0	3	−2
−(	1	−2	)
		−2
	−(	−2	4	)
			0
		−(	0	0	)
				3
			−(	3	−6	)
					−2
				−(	−2	4	)
						0

Verdichtet man nun dieses Schema auf drei Zeilen und übernimmt den ersten Koeffizienten des Dividenden in die dritte Zeile, so erhält man:

(	1	−4	4	3	−8	4	)  :  ( 1	−2 )
−(		−2	4	0	−6	4	)
	1	−2	0	3	−2	0

Wie man nun sieht, sind die doppelt unterstrichenen Werte der letzten Zeile die Koeffizienten des Ergebnispolynoms und der letzte Wert dahinter ist der Divisionsrest (hier Null).

Multipliziert man nun das Vorzeichen in die zweite Zeile, so erfolgt die Berechnung nach folgendem Ablauf:

${\, 1}$

${\,-4}$

${\, 4}$

${\, 3}$

${\,-8}$

${\, 4}$

$\Bigg\downarrow$

+

+

+

+

+

$\, 2$

$\,-4$

$\, 0$

$\, 6$

$\,-4$

$\nearrow$

$\mid$

$\nearrow$

$\mid$

$\nearrow$

$\mid$

$\nearrow$

$\mid$

$\nearrow$

$\mid$

$\cdot{2}$

=

$\cdot{2}$

=

$\cdot{2}$

=

$\cdot{2}$

=

$\cdot{2}$

=

$\nearrow$

$\downarrow$

$\nearrow$

$\downarrow$

$\nearrow$

$\downarrow$

$\nearrow$

$\downarrow$

$\nearrow$

$\downarrow$

${\,1}$

${\,-2}$

${\, 0}$

${\, 3}$

${\,-2}$

${\, 0}$

Vermerkt man nun noch den vorzeichengedrehten Wert des Absolutglieds des Divisors vor dem Schema, so bekommt man die allgemeine Darstellung des Horner-Schemas:

	1	−4	4	3	−8	4
2)		2	−4	0	6	−4
	1	−2	0	3	−2	0

Das obige Beispiel kann nun in folgender Formel zusammengefasst werden:

Hat die Divisionsaufgabe:

$(a_{n}x^n+a_{n-1}x^{n-1}+\dots{}+a_2x^2+a_1x^1+a_0) : (x+d)$

als Ergebnis

$e_{n-1}x^{n-1}+e_{n-2}x^{n-2}+\dots{}+e_2x^2+e_1x^1+e_{0}, \mbox{ mit dem Rest } r$

so bestimmen sich die Koeffizienten nach folgender Vorschrift:

$\begin{matrix} e_{n-1} &=& a_n\\ e_k &=& a_{k+1} - d\cdot e_{k+1},& \mathrm{f\ddot ur}\ k=n-2, n-3, \dots{}, 1, 0\\ r &=& a_0 - d\cdot e_0 \\ \end{matrix}$

Das Horner-Schema stellt sich dann wie folgt dar:

	$\,a_n$	$\,a_{n-1}$	$\,a_{n-2}$	$\ldots$	$\,a_2$	$\,a_{1}$	$\,a_{0}$
${-d\,})$		$-d\,e_{n-1}$	$-d\,e_{n-2}$	$\ldots{}$	$-d\,e_{2}$	$-d\,e_{1}$	$-d\,e_{0}$
	$\,e_{n-1}$	$\,e_{n-2}$	$\,e_{n-3}$	$\ldots$	$\,e_{1}$	$\,e_{o}$	$\,r$

Anmerkung: Mit diesem Ergebnis lässt sich die Berechnung von Funktionswerten eines Polynoms P an der Stelle a auch folgendermaßen herleiten: Betrachten wir die Division P(x) durch x − a $\frac{P(x)}{(x-a)} = E(x) + \frac{r}{x-a}$ $\Rightarrow P(x) = {(x-a)}E(x) + {r}$ $\Rightarrow P(a) = 0 \cdot E(a) + {r} = r$

Polynomdivision mit einem Divisor 2. Grades

Hat die Divisionsaufgabe:

$(a_{n}x^n+a_{n-1}x^{n-1}+\dots{}+a_2x^2+a_1x^1+a_0) : (x^2 + d_1x +d_0)$

als Ergebnis

$e_{n-2}x^{n-2}+e_{n-3}x^{n-3}+\dots{}+e_2x^2+e_1x^1+e_{0}, \mbox{ mit dem Rest } r_1x+r_0$

so bestimmen sich die Koeffizienten nach folgender Vorschrift:

$\begin{matrix} e_{n-2} &=& a_n\\ e_{n-3} &=& a_{n-1} - d_1\,e_{n-2}\\ e_k &=& a_{k+2} - d_1\,e_{k+1} - d_0\,e_{k+2} & \mathrm{f\ddot ur}\ k=n-4, n-5, \dots{}, 1, 0\\ r_1 &=& a_1 - d_1\,e_0 - d_0\,e_1 \\ r_0 &=& a_0 - d_0\,e_0 \\ \end{matrix}$

Das verallgemeinerte Horner-Schema stellt sich dann wie folgt dar:

	$\,a_n$	$\,a_{n-1}$	$\,a_{n-2}$	$\,a_{n-3}$	$\ldots$	$\,a_3$	$\,a_2$	$\,a_{1}$	$\,a_{0}$
${-d_0\,})$			$-d_0\,e_{n-2}$	$-d_0\,e_{n-3}$	$\ldots{}$	$-d_0\,e_{3}$	$-d_0\,e_{2}$	$-d_0\,e_{1}$	$-d_0\,e_{0}$
${-d_1\,})$		$-d_1\,e_{n-2}$	$-d_1\,e_{n-3}$	$-d_1\,e_{n-4}$	$\ldots{}$	$-d_1\,e_{2}$	$-d_1\,e_{1}$	$-d_1\,e_{0}$
	$\,e_{n-2}$	$\,e_{n-3}$	$\,e_{n-4}$	$\,e_{n-5}$	$\ldots$	$\,e_{1}$	$\,e_{0}$	$\,r_{1}$	$\,r_0$

Ein Beispiel:

$( - 6x^6 + 14x^5 - 8x^4 - 2x^3 + 8x - 6)\, :\, (x^2 - 2x + 1)$

Im Horner-Schema:

	−6	14	−8	−2	0	8	−6
−1 )			6	−2	−2	0	2
2 )		−12	4	4	0	−4
	−6	2	2	0	−2	4	−4

Daraus ergibt sich:

$\frac{(-6x^6 + 14x^5 - 8x^4 - 2x^3 + 8x - 6)}{(x^2 - 2x + 1)} \,=\, -6x^4 + 2x^3 + 2x^2 - 2 \mbox{ Rest } 4x - 4$

Lineartransformation

In einigen Fällen, beispielsweise zur Verbesserung der Konvergenz beim Newton-Verfahren, kann es sehr hilfreich sein, ein Polynom P in ein Polynom P_a, a konstant, zu transformieren, so dass mit x = a + y gilt:

$P(x) = P(a+y)\; =\; P_a(y) = P_a(x-a)$

Eine solche Lineartransformation kann man durch Einsetzen von a + y anstelle von x und anschließendes Ausmultiplizieren erhalten. Wesentlich effizienter lässt sich diese Rechnung mit dem vollständigen Horner-Schema durchführen.

Betrachten wir das Polynom $P(x)=\sum_{i=0}^n a_i x^i$ vom Grad n welches wir nach Potenzen von y = x − a entwickeln wollen: Hierzu dividieren wir das Polynom P(x) mittels des Horner-Schemas durch (x − a). Wie oben gezeigt können wir aus dem Schema das Polynom E₁(x) und den Rest r₀ ablesen, so dass gilt:

$P(x)\; = E_1(x) (x-a) + r_0$

Nun wird die Division auf das Ergebnis-Polynom E₁(x) durchgeführt und erhalten E₂ bzw. den Rest r₁:

$E_1(x)\; = E_2(x) (x-a) + r_1$

Nach n Divisionen erhält man:

$E_{n-1}(x)\; = E_n(x) (x-a) + r_{n-1}$ mit $E_n(x)\; = a_n =: r_n$

Es folgt:

$\begin{matrix} P(x)& = & E_1(x) (x-a) + r_0 \\ & = & \left(E_2(x) (x-a) + r_1\right)(x-a) + r_0 \\ & = & \left(\dots\left( r_n(x-a) + r_{n-1}\right)(x-a) + \dots + r_1\right)(x-a) + r_0 \\ \end{matrix}$

Mit y = x − a ist dann die Lineartransformation P_a

$\begin{matrix} P_a(y) &=& \left(\dots\left( r_n y + r_{n-1}\right) y + \dots + r_1\right) y + r_0 \\ &=& \sum_{i=0}^n r_iy^i \end{matrix}$

D.h. die Reste bei der fortgesetzten Division mit dem Linearfaktor (x − a) bilden die Koeffizienten des transformierten Polynoms P_a

Beispiel

Möchte man z.B. die Nullstelle des Polynoms $P(x)\,=\,x^3-2x-5$ berechnen, so kann man leicht den Punkt x = 2 als erste Näherung raten. Für die weitere Berechnung ist es nun hilfreich P(x) nach x − 2 zu entwickeln (siehe „Methodus fluxionum et serierum infinitarum“). Gesucht ist also das Polynom P₂(x) = P(x − 2).

	1	0	−2	−5
2)		2	4	4
	1	2	2	−1
2)		2	8
	1	4	10
2)		2
	1	6

Das gesuchte Polynom ist also $P_2(x)\,=\, x^3+6x^2+10x-1$.

Berechnung der Ableitung

Eine weitere Eigenschaft des Horner Schemas ist es, dass man recht schnell die erste Ableitung an der Stelle x₀ berechnen kann.

Betrachten wir die Division

$\frac{P(x)}{(x-x_0)}$

mit dem Ergebnis

$P_{e}(x) + \frac{r}{(x-x_0)}$

welches wir aus dem Horner-Schema ablesen können. Weiter oben konnte man auch sehen, dass r = P(x₀) ist. Es gilt also

$\frac{P(x)}{(x-x_0)} = P_{e}(x) + \frac{P(x_0)}{(x-x_0)}$

$\Rightarrow\;\frac{P(x)-P(x_0)}{(x-x_0)} = P_{e}(x)$

Die Ableitung $P^{\prime}(x)$ lässt sich mit dem Differenzenquotienten berechnen. Es gilt

$P^{\prime}(x_0) = \frac{{\rm d}P(x_0)}{{\rm d}x} = \lim_{x\rightarrow x_0}\frac{P(x)-P(x_0)}{(x-x_0)}$

Daraus folgt

$P^{\prime}(x_0) = P_{e}(x_0)$

D.h. die Zahlen in der dritten Zeile des Horner-Schemas bilden die Koeffizienten für P_e(x₀). Durch nochmalige Anwendung des Horner-Schemas kann dann schließlich der Wert der Ableitung $P^{\prime}(x_0)$ berechnet werden.

Beispiel

Betrachten wir das Polynom P(x) = x⁵ − 4x⁴ + 4x³ + 3x² − 8x + 4 an der Stelle x=2

	1	−4	4	3	−8	4
2)		2	−4	0	6	−4
	1	−2	0	3	−2	0
2)		2	0	0	6
	1	0	0	3	4

Aus dem Schema kann man nun ablesen: $P(2)\,=\,0$ und $P^{\prime}(2)\,=4$

Probe

$P^{\prime}(x)= 5x^4-16x^3+12x^2+6x-8$

Aus dem Horner-Schema

	5	−16	12	6	−8
2 )		10	−12	0	12
	5	−6	0	6	4

folgt $P^{\prime}(2)\,=4$.

Mehrfache Ableitungen

Auch die Werte der weiteren Ableitungen lassen sich aus dem Horner-Schema ablesen. Sei

$P(x)= \sum_{i=0}^n a_ix^i$ und $P_a(y)= \sum_{i=0}^n r_iy^i$, mit x = a + y

das Polynom welches wir aus dem vollständigen Horner-Schema ablesen können (siehe oben), so ist

$P^{(k)}(a) = P^{(k)}(a+0) = P^{(k)}_a(0)= k!\,r_k$

Nullstellenbestimmung

Das Horner-Schema lässt sich in verschiedenen numerischen Verfahren zur Nullstellenbestimmung von Polynomen einsetzen.

Hat man z.B. eine Nullstelle „erraten“ so kann man, wie oben gezeigt wurde, schnell überprüfen ob die Vermutung stimmt.

Um das "Erraten" der Nullstelle in nicht zu komplexen Aufgaben zu verkürzen, kann man den Satz über rationale Nullstellen verwenden. Aus diesem folgt, dass eine ganzzahlige Nullstelle ein Teiler von b₀ ist. Sollte ein Faktor vor dem höchstwertigen x stehen (z.B. 3 bei: 3x³ − 18x² − 3x + 18 = 0), so sind auch die Teiler von b0 und am besten die gesamte Funktion durch diesen zu teilen (→ x³ − 6x² − x + 6 = 0)

Beispiel: Man betrachte x³ − 6x² − x + 6 = 0 mit b₀ = 6. Die möglichen Teiler von 6 und damit Kandidaten für Nullstellen sind 1, 2, 3, 6, und auch -1, -2, -3, -6. Mit dem Hornerschema kann man nun die Funktionswerte an diesen Stellen berechnen und so die tatsächlichen Nullstellen bestimmen. Als Nullstellen erhält man dann -1, +1, +6. Hat man eine Nullstelle bestimmt, kann man mit dem Hornerschema zudem, wie weiter oben erläutert, auch einen Linearfaktor abspalten.

Ein weiteres Einsatzgebiet ist das Newtonsche Näherungsverfahren. Für das Newton-Verfahren benötigt man in jedem Iterations-Schritt P(x_n) und P'(x_n). Diese Werte lassen sich, wie oben beschrieben, recht schnell mit dem Horner-Schema berechnen.

Geschichte

William George Horner war nicht der erste, der dieses Verfahren entdeckte. Er hatte es vor allem De Morgan zu verdanken, dass das Verfahren unter seinem Namen bekannt wurde. Paolo Ruffini veröffentlichte 15 Jahre vor Horner bereits ein entsprechendes Verfahren; es wird in Spanien daher auch als regla de Ruffini bezeichnet. Erste bekannte Beschreibungen des Verfahrens reichen bis in die Anfänge des 14. Jahrhunderts zurück. Der Chinese Zhu Shijie beschrieb bereits 1303 in seinem Buch Siyuan yujian eine Umwandlungsmethode zur Lösung von Gleichungen, die er fan fa nannte.

Literatur

• William George Horner: A new method of solving numerical equations of all orders, by continuous approximation. In: Philosophical Transactions of the Royal Society of London (1819), S. 308-335.
• Charles D. Miller, Margaret L. Lial, David I. Schneider: Fundamentals of College Algebra. Scott & Foresman/Little & Brown Higher Education, 3. überarbeitete Auflage 1990, ISBN 0-673-38638-4, S. 204-209
• Gisela Engeln-Müllges, Klaus Niederdrenk, Reinhard Wodicka: Numerik-Algorithmen: Verfahren, Beispiele, Anwendungen. Springer 2005, ISBN 3540626697, S. 92-100 (Auszug in der Google Buchsuche)

Weblinks

• Markus Bauer: Das Horner-Schema. Facharbeit, Gymnasium Ottobrunn 2001
• Das Hornerschema und andere Tricks auf Matroids Matheplanet am 27. Juli 2003
• Olaf Schimmel: Berechnung mit dem Horner-Schema
•  Wikibooks: Horner-Schema – Implementierungen in der Algorithmensammlung

Einzelnachweise und Anmerkungen

1. ↑ Josef Stoer: Numerische Mathematik 1. 9 Auflage. Springer, 2004.
2. ↑ ^{a b} Bei der Berechnung der Potenzen x^k, k≥2, kann man zuerst die niedrigen und dann die höheren Potenzen berechnen. Damit macht man sich jeweils zunutze, dass x^{k − 1} schon berechnet ist, wenn x^k gebraucht wird. Für x^k braucht man daher nur eine weitere Multiplikation und nicht deren (k − 1). Insgesamt kommt man deshalb mit (n − 1) Multiplikationen für die Berechnung aller Potenzen aus.