· 

Horner-Schema und Implementierung in Python

1. Darstellung eines Polynoms im Rechner

Zuerst überlegen  wir uns, wie man Polynome in Python darstellen kann. Eine platzsparende Möglichkeit besteht darin, nur die Koeffizienten zu übergeben.  Für das Polynom $$f(x)=2x^3+2x^2-5x-6$$ wäre das z. B. eine Liste mit dem folgenden Inhalt:
[1, 2, -5, -6]
In welcher Richtung du die Koeffizienten übergibst, bleibt dir überlassen. Achte aber darauf, dass sich dadurch ggf. die Programmierlogik ändert. Wir gehen davon aus, dass die Koeffizienten von links nach rechts übergeben werden.
Für das Polynom $$f(x)=2x^3-14x-12$$ musst du berücksichtigen, dass der Summand \(x^2\) nicht auftaucht und dort demnach eine \(0\) als Koeffizient steht. Dies musst du folglich auch bei der Definition des Polynoms als Liste von Koeffizienten berücksichtigen. Als zweiter Eintrag steht in der Liste dem Vorbild $$f(x)=2x^3+0x^2-14x-12$$ entsprechend eine \(0\):
[2, 0, -14, -12]
Mit
len([1, 2, -5, -6])-1
kannst du den Grad des Polynoms ermitteln. Wie du siehst, geht durch diese für den Computer verständliche Darstellung eines Polynoms keine Information verloren.

2. Implementierung

Für die Implementierung bietet sich die Definition einer Funktion mit dem Namen horner an. Dieser werden zwei Parameter übergeben, nämlich das Polynom (in Form einer Koeffizientenliste) und eine (zuvor geratene) Nullstelle.

def horner(polynom, nullstelle):

Wir definieren uns eine Hilfsvariable tmp mit dem Startwert 0, in der die Werte gespeichert werden, die beim Schritt "Multiplikation" entstehen. Zudem definieren wir eine zu Beginn leere Liste result, in der die Koeffizienten des Ergebnispolynoms stehen.

def horner(polynom, nullstelle):
   tmp = 0
   result = []

In einer for-Schleife, die jeden Koeffizienten des Polynoms durchläuft, wird nun (wie es der Algorithmus für das Horner-Schema vorsieht) zuerst nach unten hin der aktuelle Wert des Koeffizienten und das Ergebnis der Multiplikation addiert. Dieses Ergebnis wird dann der Koeffizientenliste des Ergebnispolynoms hinzugefügt.

def horner(polynom, nullstelle):
   tmp = 0
   result = []

   for i in range(len(polynom)):
      result.append(polynom[i] + tmp)

Anschließend wird durch die Multiplikation der vorgegebenen Nullstelle mit dem aktuellen Koeffizienten des Ergebnispolynoms der neue Wert ermittelt, der im nächsten Schleifendurchlauf für die Berechnung des darauffolgenden Koeffizienten des Ergebnispolynoms herangezogen wird.

def horner(polynom, nullstelle):
   tmp = 0
   result = []

   for i in range(len(polynom)):
      result.append(polynom[i] + tmp)
      tmp = nullstelle * result[i]

Nach der for-Schleife wird einfach das Ergebnis zurückgegeben.

def horner(polynom, nullstelle):
   tmp = 0
   result = []

   for i in range(len(polynom)):
      result.append(polynom[i] + tmp)
      tmp = nullstelle * result[i]
   return result
Wenn du die Funktion horner nun mit der Listendarstellung des Polynom $$f(x)=2x^3-14x-12$$ und der vorgegebenen (oder geratenen) Nullstelle \(x=-2\) aufrufst, erhältst du als Ergebnis die Koeffizienten des Ergebnispolynoms. Achte darauf, dass der letzte Eintrag in der Liste angibt, ob die Polynomdivision aufgegangen ist oder nicht. Wenn \(0\) herauskommt, ist die Polynomdivision aufgegangen (sonst nicht). Das Ergebnis kannst du dir auch auf die Konsole drucken lassen.
print(horner([2, 0, -14, -12], -2))

3. Interaktiver Quellcode