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}{\mbox{I) }}&2x^{4}-4x^{3}-5x^{2}+7x+11&=\\{\mbox{II) }}&\left(2x^{3}-4x^{2}-5x+7\right)\cdot x+11&=\\{\mbox{III) }}&\left(\left(2x^{2}-4x-5\right)\cdot x+7\right)\cdot x+11&=\\{\mbox{IV) }}&\left(\left(\left(2\cdot x-4\right)\cdot x-5\right)\cdot x+7\right)\cdot 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 Vorteil in Rechenzeit und numerischer Genauigkeit (weniger Rundungsfehler) zu Buche. Im günstigsten Fall lässt sich der Aufwand für Multiplikationen auf fast die Hälfte reduzieren. Die hier dargestellte Form eignet sich besonders gut für die Berechnung in der umgekehrten polnischen Notation (UPN)

Tabellarische Schreibweise des Hornerschemas

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 3zeilige-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 folgendes 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.

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:

$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 2^{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 tabelarischer Form auf:

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

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äßt 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 zusammengefaßt werden:

Hat die Disvisionsaufgabe:

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

als Ergebnis

$e_{n-1}x^{n-1}+e_{n-2}x^{n-2}+\dots {}+e_{2}x^{2}+e_{1}x^{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},&{\mbox{f}}{\ddot {\mbox{u}}}{\mbox{r }}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äßt 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 Disvisionsaufgabe:

$(a_{n}x^{n}+a_{n-1}x^{n-1}+\dots {}+a_{2}x^{2}+a_{1}x^{1}+a_{0}):(x^{2}+d_{1}x+d_{0})$

als Ergebnis

$e_{n-2}x^{n-2}+e_{n-3}x^{n-3}+\dots {}+e_{2}x^{2}+e_{1}x^{1}+e_{0},{\mbox{ mit dem Rest }}r_{1}x+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}&{\mbox{f}}{\ddot {\mbox{u}}}{\mbox{r }}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 da:

	$\,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\,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 (z.B. 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_{1}(x)$ und den Rest $r_{0}$ ablesen, so dass gilt:

$P(x)\;=E_{1}(x)(x-a)+r_{0}$

Nun wird die Division auf das Ergebnis-Polynom $E_{1}(x)$ durchgeführt und erhalten $E_{2}$ bzw. den Rest $r_{1}$:

$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_{i}y^{i}\end{matrix}}$

D.h. die Reste bei der fortgesetzten Divission 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 erste Näherung raten. Für die weiter Berechnung ist es nun hilfreich $P(x)$ nach $x-2$ zu entwickeln (siehe "Methodus fluxionum et serierum infinitarum"). Gesucht ist also das Polynom $P_{2}(x)=P(2+x)$.

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

Das erweiterte Hornerschema

Eine weitere Eigenschaft des Horner Schemas ist es, dass man recht schnell die erste Ableitung an der Stelle $x_{0}$ 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 das $r=P(x_{0})$ 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äßt 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_{0})$. 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^{5}-4x^{4}+4x^{3}+3x^{2}-8x+4$

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

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 wir oben gesehen haben sehr schnell überprüfen ob die Vermutung stimmt.

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

Quelle

• William George Horner. A new method of solving numerical equations of all orders, by continuous approximation. Philosophical Transactions of the Royal Society of London, Seiten 308-335, Juli 1819.

Weblinks

• Facharbeit zum Thema
• Artikel zum Horner-Schema auf linux-related.de
• Polynomdivision und Division algebraischer Summen