GYMNASIUM OTTOBRUNN

Kollegstufe 1999/2001

Leistungskurs Mathematik

Facharbeit

Das Horner-Schema

Verfasser: Markus Bauer
Kursleiter: Erich Lintner
Bewertung: 13 Punkte


Copyright (c) 2002 Markus Bauer.
Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license is included.


Inhaltsangabe

I. Einleitung
II. Geschichtlicher Hintergrund
III. Das Horner-Schema
1. Herleitung
2. Das allgemeine Horner-Schema
3. Abspaltung eines Linearfaktors
4. Das erweiterte Horner-Schema
IV. Vorteile des Horner-Schemas
1. Bedeutung von Additionen und Multiplikationen
2. Berechnung nach der einfachsten Methode
3. Eine "intelligentere" Methode
4. Berechnung nach dem Horner-Schema
5. Ergebnis der Untersuchung
V. Anwendung in der Informatik
1. Grundlagen
2. Struktogramm
3. Verwirklichung in Turbo-Pascal
VI. Anwendungsbeispiel
1. Das Newton-Verfahren
2. Das Beispiel
VII. Schluss
VIII. Quellen und Hilfsmittel
1. Literaturverzeichnis
2. Internetquellen
3. Verwendete Software
IX. Lizenz


I. Einleitung

In der Analysis müssen häufig die Werte einer Funktion und die ihrer Ableitung 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 ein sehr einfaches Verfahren: Das Horner-Schema.
Ziel dieser Arbeit ist es, das Prinzip des Horner-Schemas darzustellen und einige weiterführende Aspekte, vor allem im Bereich der Informatik, auszuführen. Nach einer allgemeinen Herleitung und Erklärung des Schemas gehe ich auch auf weitere Nebeneffekte, wie das erweiterte Horner-Schema, ein. Außerdem werden ausführlich die Vorteile des Horner-Schemas dargestellt.
In Kombination mit dem Newton-Verfahren lässt sich das Horner-Schema sehr effektiv einsetzten und man kann hierbei rasch, auch bei komplizierteren Polynomen, eine Nullstelle berechnen. Hierauf wird in Form eines Beispiels eingegangen.
Ein wichtiger Aspekt dieser Arbeit ist die Anwendung des Horner-Schemas in der Informatik. Es lässt sich hierbei eine sehr einfache und effektive Anwendung programmieren, die ich in Turbo-Pascal geschrieben habe. Diese Programme habe ich in der Anlage auf einer Diskette beigefügt, die mit einer Benutzeroberfläche die Wirkungsweise des Schemas darstellen. Ebenfalls beigefügt sind die Quellcodes der Hauptprogramme und die verwendeten Units.
Die für deren Verständnis notwendigen Grundlagen werden in der Arbeit dargelegt.
Am Anfang der Arbeit gebe ich zunächst eine kurze Darstellung des geschichtlichen Hintergrundes.

zum Inhaltsverzeichnis

© 2001 Markus Bauer


II. Geschichtlicher Hintergrund

William George Horner wurde 1786 in Bristol, England, geboren. Er besuchte die Kingswood School Bristol. Bereits im Alter von vierzehn wurde er im Jahre 1800 stellvertretender Direktor und vier Jahre später sogar Direktor seiner Schule. Er verließ Bristol 1809 und gründete seine eigene Schule in Bath.
Horners einziger bedeutsamer Beitrag zur Mathematik war das Horner-Schema zur Lösung algebraischer Gleichungen. Es wurde am 1. Juli 1819 der Royal Society vorgelegt und noch im selben Jahr in den Philosophical Transactions of the Royal Society veröffentlicht. (1)
Jedoch war Horner nicht der Erste, der diese Methode entdeckt hatte, da sie bereits 500 Jahre früher Chu Shih-chieh ("1270-1330) bekannt war. Er war einer der bedeutendsten chinesischen Mathematiker, der einen bemerkenswerten Beitrag zur Entwicklung der chinesischen Algebra und zur Theorie von Gleichungen leistete. Er schrieb zwei wichtige Aufsätze. In seiner zweiten Arbeit, Ssu-yuan yu-chien (1303; Precious Mirror of the Four Elements), beschrieb er neben anderen mathematischen Problemen auch eine Lösung für eine allgemeine Gleichung 14. Grades. Er verwendete dazu eine Umwandlungsmethode, die er fan fa nannte und die eben Horner als das Horner-Schema wiederentdeckte. (2)
Im neunzehnten und frühen zwanzigsten Jahrhundert hatte das Horner-Schema einen herausragenden Platz in einigen Algebrabüchern. Dies lag vor allem an De Morgan, der Horners Name und sein Schema in vielen Artikeln, die er veröffentlicht hatte, ausführlich behandelte.
W. G. Horner starb 1837 in Bath. (3)


(1) aus dem Englischen übertragen nach O'Connor; Robertson. 1996, [a] horner.html
(2) aus dem Englischen übertragen nach Encyclopædia Britannica. 2000 und O'Connor; Robertson, 1996, [b] Chu.html
(3) aus dem Englischen übertragen nach O'Connor; Robertson. 1996, [a] horner.html

zum Inhaltsverzeichnis

© 2001 Markus Bauer


III. Das Horner-Schema

1. Herleitung

Hier beginne ich nun mit der Entwicklung des Horner-Schemas. Als Beispiel dient dazu ein allgemeines Polynom 3. Grades:

Aus dieser Funktion wird zunächst die Variable x aus den ersten drei Summanden ausgeklammert. Man erhält dann:

Klammert man x noch einmal aus den ersten beiden Summanden in der Klammer aus, so ergibt sich:

Nun kann man die Funktion schrittweise aufteilen und folgendermaßen berechnen:

Schema 1

(Das Symbol A := B hat dabei folgende Bedeutung: Der Wert des Ausdrucks B ergibt den neuen Wert A. H und G sind Hilfsvariablen) (4)
Die durchgeführten Rechnungen lassen sich übersichtlicher als in Schema 1 anordnen – im sogenannten Horner-Schema:

Gerechnet wird in Richtung der Pfeile. Nach unten wird immer addiert und nach rechts oben multipliziert. (Die Pfeile sind hier nur zur Verdeutlichung angebracht und werden normalerweise weggelassen.)


(4) vgl. Nitsche, 1968, 126

zum Inhaltsverzeichnis

© 2002 Markus Bauer


2. Das allgemeine Horner-Schema

Zunächst benötigt man eine ganzrationale Funktion vom Grad n, ein Polynom n-ten Grades:

(5)
Zum Berechnen eines Funktionswertes setzt man () (6) und nun kann man (wie ich im vorherigen Kapitel bereits gezeigt habe) nach dem folgenden allgemeinen Horner-Schema ermitteln:

Schema 2

In der ersten Zeile werden die Koeffizienten der Funktion notiert, wobei man nicht vorkommende Koeffizienten durch eine Null ersetzten muss. Ansonsten würde man die Werte eines Polynoms niedrigeren Grades berechnen.

Nun geht man nach folgendem Algorithmus vor:
Die erste Stelle der zweiten Zeile bleibt frei,[wobei mit gleichgesetzt wird;] die weiteren entstehen durch Multiplikation der unmittelbar voranstehenden Glieder der dritten Zeile mit ; die Glieder der dritten Zeile sind dabei die Summen der darüberstehenden Glieder der ersten und zweiten Zeile; das letzte Glied der dritten Zeile gibt dann den Wert an. (7)


(5) Diese Definitionen gelten für die gesamte Arbeit
(6) siehe (5)
(7) Lexikon Technik und exakte Naturwissenschaften. Band 5. Gesteine Kalispeter. 1972. Seite 1484

zum Inhaltsverzeichnis

© 2002 Markus Bauer


3. Abspaltung eines Linearfaktors

Das Horner-Schema besitzt jedoch noch einige weitere Eigenschaften.
Zur Veranschaulichung beginnen wir wieder mit einem Polynom 3. Grades:
;

Für den Fall, das sich bei eine Nullstelle befindet, kann man einen Linearfaktor abspalten.

Allgemein kann man zunächst eine Polynomdivision durchführen:


Vereinfachen wir nun mit und und
erhalten wir

Wenn nun bei eine Nullstelle ist, so ist , und daraus folgt:

Vergleichen wir nun die Zahlen in der dritten Zeile des Horner-Schemas, so finden wir diese gerade als Koeffizienten des Restpolynoms [] wieder. (8)

Nehmen wir nun wieder die allgemeine Funktion und betrachten unter diesem Aspekt das allgemeine Horner-Schema (Schema 2):

Schema 3

Daraus können wir nun folgendes ablesen:
;

Falls sich bei eine Nullstelle befindet, so fällt der letzte Summand weg:
;


(8) Otto, 1985, Seite 20

zum Inhaltsverzeichnis

© 2002 Markus Bauer


4. Das erweiterte Horner-Schema

Mit Hilfe der Zahlen in der dritten Zeile des allgemeinen Horner-Schemas (vgl. Schema 3) lässt sich auf einfache Weise die erste Ableitung an der Stelle berechnen.

Es gilt nämlich mit

für die Ableitung

und für wird = 0 und damit folgt

Wieder bilden die Zahlen der dritten Zeile des allgemeinen Horner-Schemas die Koeffizienten eines Polynoms, hier das der ersten Ableitung.
Wir können also das Horner-Schema wie folgt erweitern und erhalten in einem sowohl den Wert von als auch den von an der Stelle
(9)

Dieses Schema nennt man schließlich erweitertes Horner-Schema.
Allgemein sieht es folgendermaßen aus:


(9) Otto, 1985, Seite 20

zum Inhaltsverzeichnis

© 2002 Markus Bauer


IV. Vorteile des Horner-Schemas

In diesem Kapitel entwickle ich genauer die Vorteile des Horner-Schema und zeige, warum man es, vor allem auch in der Informatik, gerne benutzt.

1. Bedeutung von Additionen und Multiplikationen

Auf dem Computer benötigen Additionen und vor allem Multiplikationen Rechenzeit. Zwar dauert eine Multiplikation nur wenige Millisekunden, doch häufen sich diese und wird zusätzlich noch mit Gleitkommazahlen gerechnet, wird kostbare Rechenzeit benötigt. Es ist also ein Anliegen in der Informatik, Multiplikationen möglichst zu verringern, damit ein Programm nicht unnötig verlangsamt wird.
Aber auch, wenn man den Taschenrechner benutzt, ist es von Vorteil, weniger Rechenschritte zu haben; die Wahrscheinlichkeit sich zu vertippen, und damit auch die Fehlerwahrscheinlichkeit, verringert sich.
Selbst wenn man auf dem Papier rechnet, ist man froh, wenn man möglichst wenig Multiplikationen auszuführen hat, und somit ebenfalls die Gefahr sich zu verrechnen gesenkt werden kann.
Die Notwendigkeit zur Verminderung von Additionen und Multiplikationen ist hiermit gezeigt, und nun beschreibe ich, welche Vorteile das Horner-Schema dazu bietet.
Im folgenden verwende ich eine Beispielfunktion 4. Grades mit einem Wert , an dem die Funktion berechnet werden soll.

zum Inhaltsverzeichnis

© 2002 Markus Bauer


2. Berechnung nach der einfachsten Methode

Die einfachste Methode ein Polynom an einem bestimmten Wert zu berechnen besteht darin, die Funktion von links nach rechts durchzurechnen und dabei x dem gesuchten Wert gleichzusetzen. In dem Beispiel sähe das dann so aus:
;


Wir zählen nun die Additionen und Multiplikationen:
Additionen 4
Multiplikationen 10

Ganz allgemein kann man diesen Rechenvorgang folgendermaßen beschreiben:
Startgleichung
Rekursionsgleichung (für bis 0)
Ergebnis
Methode 1

Daraus ergibt sich die Anzahl der Additionen und Multiplikationen in einer allgemeinen Tabelle:
Additionen n
Multiplikationen
Ergebnis 1 (10)


(10) vgl. Mennicken; Wagenführer, 1977, Seite 17

zum Inhaltsverzeichnis

© 2002 Markus Bauer


3. Eine "intelligentere" Methode

Geht man ein bisschen schlauer vor, so kann man die Tatsache ausnutzen, dass, wenn man bereits berechnet hat, man mit ermitteln kann. Angewandt auf das Beispiel bedeutet das folgendes:
;


Wir zählen wieder die Additionen und Multiplikationen:
Additionen 4
Multiplikationen 8

Und das Ganze allgemein:
Startgleichung
Rekursionsgleichung (für k = 1 bis n)
Ergebnis
Methode 2

Allgemein kommen wir somit auf folgendes Ergebnis:
Additionen n
Multiplikationen 2n
Ergebnis 2 (11)

Das ist schon eine Einsparung von Multiplikationen gegenüber dem Vorhergehenden, doch nun werfen wir einen Blick auf das Horner-Schema.


(11) vgl. Demailly, 1994, Seite 4

zum Inhaltsverzeichnis

© 2002 Markus Bauer


4. Berechnung nach dem Horner-Schema

Unser Beispiel sieht im Horner-Schema folgendermaßen aus.

Additionen 4
Multiplikationen 4

Allgemein gelten für das Horner-Schema folgende Rekursionsgleichungen:
Startgleichung
Rekursionsgleichung (für bis 0)
Ergebnis
Methode 3

Da man pro Schritt nur eine Multiplikation und eine Addition benötigt, folgt daraus dieses Ergebnis:
Additionen n
Multiplikationen n
Ergebnis 3 (12)


(12) vgl. Demailly, 1994, Seite 5

zum Inhaltsverzeichnis

© 2002 Markus Bauer


5. Ergebnis der Untersuchung

Vergleicht man nun Ergebnis 1, 2 und 3, so ist deutlich zu erkennen, dass sich zwar die Anzahl der Additionen durch das Horner-Schema nicht verringern lassen, jedoch ist die Anzahl der Multiplikationen erheblich geringer, als bei einfacheren Methoden. Und hier liegt auch der entscheidende Vorteil des Horner-Schemas.
Betrachtet man außerdem noch die verschiedenen Rekursionsgleichungen (Methode 1 bis 3), so erkennt man, dass Methode 3 die einfachste ist. Auch hierdurch ist ersichtlich, dass die Berechnung nach dem Horner-Schema wesentlich leichter zu bewältigen ist. Eben durch ihre Einfachheit kann Methode 3 gut in der Informatik angewandt werden, womit sich das nächste Kapitel beschäftigt.

zum Inhaltsverzeichnis

© 2002 Markus Bauer


V. Anwendung in der Informatik

Mit den inzwischen gewonnenen Erkenntnissen lässt sich ein Computerprogramm schreiben, das unter Verwendung des Horner-Schemas ein Polynom an einer bestimmten Stelle berechnet.

1. Grundlagen

Die Vorteile wurden bereits im letztem Kapitel betrachtet: Das Horner-Schema spart erheblich an Multiplikationen, wodurch ein effektiver Programmcode geschrieben werden kann. Dadurch, dass sich derselbe Vorgang immer wiederholt, ist das Horner-Schema gut für den Computer geeignet.
Verwendet wird die im vorherigen Kapitel bereits angeführte Methode 3:

Startgleichung:
Rekursionsgleichung:
Ergebnis:

zum Inhaltsverzeichnis

© 2002 Markus Bauer


2. Struktogramm

Das Programm benötigt nun folgende EVA-Routinen (Eingabe-Verarbeitung-Ausgabe):
Zuerst liest man den Grad der Funktion (n) und die entsprechenden Koeffizienten (a) ein. Zuletzt muss noch der -Wert, an dem die Funktion berechnet werden soll, eingegeben werden.
In der Verarbeitung wird aus den erhaltenen Werten das Ergebnis nach dem Horner-Schema bestimmt. Der neue Wert ergibt sich, indem der vorher erhaltene mit multipliziert und anschließend der konstante Faktor addiert wird. Dieser immer gleiche Vorgang lässt sich leicht in einer Schleife realisieren.
Am Ende gibt man dann noch das Ergebnis aus.

Daraus ergibt sich ein allgemeines Struktogramm:

LESE n
LESE a[0] bis a[n]
LESE
H := a[n]

Zähle k von n–1 bis 0

SCHREIBE G

zum Inhaltsverzeichnis

© 2002 Markus Bauer


3. Verwirklichung in Turbo-Pascal

Praktisch habe ich dieses Programm in Turbo-Pascal realisiert. Hier dargestellt ist der Übersicht wegen eine gekürzte und vereinfachte Version des Programms Horner.pas (vgl. Download ), das die wichtigsten Elemente übersichtlich darstellt.

uses ZuHorn1, Base;

var a: TKoeffizienten;

    n: byte;
    x0: real;
    G: real;
    k: integer;
    neu: boolean;
begin
  ReadFunktion(a,n,neu);
  ReadFunktionswert(x0,neu);
  G := a[n];
  for k := n-1 downto 0 do
    G := G * x0 + a[k];
  WriteErgebnis(G,neu);
  readln;
end.
Hier befinden sich die notwenigen Variablen
und Prozeduren
type TKoeffizienten = array[0..255]
                                    of real;


Hilfsvariable
Zählvariable
Nötig, damit Programm mit der Unit
ZuHorn1 kompatibel ist
Lesen von n, a
und

Rekursive Berechnung nach dem
Horner-Schema
Schreibt G
Wartet auf einen Tastendruck, um das
Programm zu beenden.


zum Inhaltsverzeichnis

© 2002 Markus Bauer


VI. Anwendungsbeispiel

Nun ist es an der Zeit, die erworbenen Kenntnisse an einem Beispiel anzuwenden und nochmals zu verdeutlichen. Sehr gut eignet sich dazu eine Nullstellenberechnung, da in diesem Zusammenhang das Horner-Schema sehr effektiv eingesetzt werden kann.

1. Das Newton-Verfahren

Da mit dem Horner-Schema direkt keine Nullstellen ermittelt werden können, soll es dazu mit dem Newtonschen Näherungsverfahren kombiniert verwendet werden.
Das Newton-Verfahren beruht auf folgender Gleichung:

mit r = 0 stellt dabei einen Startwert da, der sich in der Nähe einer vermuteten Nullstelle befindet, und r gibt die Iterationsschritte an. Führt man nun diese Rekursionsgleichung genügend oft aus, mit , und besitzt […] eine einfache Nullstelle , so konvergiert das Newton'sche Verfahren sicher dann gegen , wenn die Iteration nahe genug an beginnt. (13)
Falls nicht konvergiert oder wird, so muss ein anderer Startwert gewählt werden und mit diesem neu begonnen werden.
Wie man auch aus der Gleichung erkennen kann, werden für jeden Schritt die Werte für und benötigt. Genau diese Werte lassen sich über das erweiterte Horner-Schema einfach bestimmen.


(13) Nische, 1968, Seite 78

zum Inhaltsverzeichnis

© 2002 Markus Bauer


2. Das Beispiel

Als Beispiel soll die folgende Funktion 4. Grades genommen werden:


Nun soll eine Nullstelle in der Umgebung von gesucht werden.
(Die Ergebnisse werden auf die dritte Stelle nach dem Komma gerundet.)

Wir berechnen nach dem Horner-Schema und :


Eingesetzt in Gleichung von Newton: ;

Es folgt der nächste Iterationsschritt mit .
Wir berechnen wieder nach dem Horner-Schema:


Wieder eingesetzt in Gleichung: ;

Da die Werte nun komplizierter werden, sei für die weiteren Berechnungen auf das Computerprogramm Horner2.exe im Downloadbereich verwiesen, das die Werte der Funktion und der Ableitung nach dem Horner-Schema berechnet und übersichtlich darstellt. Daraus ergibt sich dann:


Prüfen wir für im Horner-Schema nach

so können wir tatsächlich eine Nullstelle nachweisen.

Weiterhin können wir gleichzeitig den Linearfaktor mithilfe des Schemas abspalten. Daraus ergibt sich:
.

Bildet jetzt man mit dem zweiten Faktor eine neue Funktion
,
so kann man hiermit fortfahren und eine Nullstelle von suchen, und damit gleichzeitig eine Nullstelle von .

Hierbei möchte ich es belassen und auf die Programme im Anhang verweisen mit deren Hilfe man hier fortfahren kann.
(Als kleiner Tipp: In der Umgebung von befindet sich noch eine Nullstelle. Die zwei restlichen kann man dann einfach über die Lösungsformel bestimmen, oder das Programm Newton.exe (vgl. Download ) verwenden.)

zum Inhaltsverzeichnis

© 2002 Markus Bauer


VII. Schluss

Ich hoffe, dass durch meine Arbeit das Prinzip, die Funktionsweise und die Möglichkeiten der Anwendung des Horner-Schemas klargemacht werden konnten.
Da ein Schwerpunkt meiner Arbeit die Verwendung des Horner-Schemas in der Informatik darstellt, kann ich nur noch einmal auf die Programme im Anhang verweisen, die als Ergänzung und Fortführung der bereits beschriebenen Bereiche anzusehen sind. Diese Programme sind sicherlich auch interessant, wenn man die dahinterstehenden Mechanismen nicht kennt. Besonders praktisch finde ich das Programm Newton.exe das mithilfe des Newton-Verfahrens und der Horner-Schemas ziemlich schnell und sicher Nullstellen komplizierter Polynome findet.

zum Inhaltsverzeichnis

© 2002 Markus Bauer


VIII. Quellen und Hilfsmittel

1. Literaturverzeichnis

zum Inhaltsverzeichnis

© 2002 Markus Bauer


2. Internetquellen

zum Inhaltsverzeichnis

© 2002 Markus Bauer


3. Verwendete Software

zum Inhaltsverzeichnis

© 2002 Markus Bauer


IX. Lizenz

Diese Facharbeit wurde erstellt von Markus Bauer und stammt von der Internetseite http://www.horner-schema.de.

Dieses Dokument steht unter der GNU Free Documentation License.
Eine deutsche Übersetzung der Lizenz gibt es hier.


© 2002 Markus Bauer

Valid XHTML 1.1!