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.
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
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
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
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.)
zum Inhaltsverzeichnis
© 2002 Markus Bauer
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.
Die erste Stelle der zweiten Zeile bleibt frei,[wobeimit
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
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:
;
zum Inhaltsverzeichnis
© 2002 Markus Bauer
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:
zum Inhaltsverzeichnis
© 2002 Markus Bauer
In diesem Kapitel entwickle ich genauer die Vorteile des Horner-Schema und zeige, warum man es, vor allem auch in der Informatik, gerne benutzt.
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
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:
;
Additionen | 4 |
Multiplikationen | 10 |
Startgleichung |
![]() |
Rekursionsgleichung (für
![]() |
![]() |
Ergebnis |
![]() |
Additionen | n |
Multiplikationen |
![]() |
(10) vgl. Mennicken; Wagenführer, 1977, Seite 17
zum Inhaltsverzeichnis
© 2002 Markus Bauer
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:
;
Additionen | 4 |
Multiplikationen | 8 |
Startgleichung |
![]() |
Rekursionsgleichung (für k = 1 bis n) |
![]() |
Ergebnis |
![]() |
Additionen | n |
Multiplikationen | 2n |
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
Unser Beispiel sieht im Horner-Schema folgendermaßen aus.
Additionen | 4 |
Multiplikationen | 4 |
Startgleichung |
![]() |
Rekursionsgleichung (für
![]() |
![]() |
Ergebnis |
![]() |
Additionen | n |
Multiplikationen | n |
(12) vgl. Demailly, 1994, Seite 5
zum Inhaltsverzeichnis
© 2002 Markus Bauer
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
Mit den inzwischen gewonnenen Erkenntnissen lässt sich ein Computerprogramm schreiben, das unter Verwendung des Horner-Schemas ein Polynom an einer bestimmten Stelle berechnet.
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
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
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;
|
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
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.
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.
zum Inhaltsverzeichnis
© 2002 Markus Bauer
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
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
zum Inhaltsverzeichnis
© 2002 Markus Bauer
zum Inhaltsverzeichnis
© 2002 Markus Bauer
zum Inhaltsverzeichnis
© 2002 Markus Bauer
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.