Wissen: Horner-Schema

Einführung Horner-Schema

Das Horner-Schema wurde nach dem englischen Mathematiker William George Horner (1786 - 1837) benannt. Bei diesem Verfahren werden Multiplikationen bzw. Potenzen zerlegt und somit vereinfacht. Als Beispiel:

3·x² + 4·x + 5 = 3·x·x + 4·x + 5 = (3·x + 4)·x + 5

Auf diese Weise haben wir die Potenz x² durch das Ausklammern von x beseitigt. Es verbleiben nur einfache Multiplikationen mit x. Zudem haben wir 3 Multiplikationen mit x auf nur 2 Multiplikationen mit x vermindert.

Durch die Vereinfachung (also der Entfernung der Potenzen) sind Berechnungen einfacher und schneller möglich. Anwendung findet das Horner-Schema vor allem bei der Berechnung von Polynomen (insbesondere Polynomdivision), der Nullstellenberechnung sowie bei Ableitungen.

Horner-Beispiel mit Polynom 5. Grades

Bei der Einführung hatten wir ein Polynom 2. Grades. Im Folgenden ein Beispiel zur Anwendung des Horner-Schemas mit einem Polynom 5. Grades. Wir klammern schrittweise die x aus:

$$ 2·x^5 + 15·x^4 - 2·x^3 + x^2 + 20·x + 5 \\[10pt] = 2·x·x·x·x·x + 15·x·x·x·x - 2·x·x·x + x·x + 20·x + 5 \\ = 2·x·x·x·x\color{red}{·x} + 15·x·x·x\color{red}{·x} - 2·x·x\color{red}{·x} + x\color{red}{·x} + 20\color{red}{·x} + 5 \\ = (2·x·x·x·x + 15·x·x·x - 2·x·x + x + 20)\color{red}{·x} + 5 \\[10pt] = (2·x·x·x·x + 15·x·x·x - 2·x·x + x + 20)·x + 5 \\ = (2·x·x·x\color{red}{·x} + 15·x·x\color{red}{·x} - 2·x\color{red}{·x} + 1\color{red}{·x} + 20)·x + 5 \\ = ((2·x·x·x + 15·x·x - 2·x + 1)\color{red}{·x} + 20)·x + 5 \\[10pt] = ((2·x·x·x + 15·x·x - 2·x + 1)·x + 20)·x + 5 \\ = ((2·x·x\color{red}{·x} + 15·x\color{red}{·x} - 2\color{red}{·x} + 1)·x + 20)·x + 5 \\ = (((2·x·x + 15·x - 2)\color{red}{·x} + 1)·x + 20)·x + 5 \\[10pt] = (((2·x·x + 15·x - 2)·x + 1)·x + 20)·x + 5 \\ = (((2·x\color{red}{·x} + 15\color{red}{·x} - 2)·x + 1)·x + 20)·x + 5 \\ = ((((2·x + 15)\color{red}{·x} - 2)·x + 1)·x + 20)·x + 5\\[10pt] = \color{blue}{ ((((2·x + 15)·x - 2)·x + 1)·x + 20)·x + 5 } $$

Aus 14 Multiplikationen wurden durch das Horner-Schema nur 5 Multiplikationen, was beachtlich ist. Insbesondere Berechnungen, die mit Computern durchgeführt werden, sind dadurch wesentlich schneller.

Binärzahl in Dezimalzahl umwandeln mit Horner-Schema

Das Horner-Schema eignet sich auch, um eine Zahl in ein anderes Zahlensystem zu übertragen. Im Folgenden übertragen wir eine Binärzahl in eine Dezimalzahl:

110₂ = ?₁₀

110₂ = 1·2² + 1·2¹ + 0·2⁰ = 1·2·2 + 1·2 + 0 = (1·2 + 1)·2 + 0 = 6₁₀

Abgekürzt kann man sich das Horner-Schema wie folgt merken:

1. Nimm die erste Ziffer der Binärzahl und multipliziere sie mit 2.
2. Addiere die nächste Ziffer darauf, setze den ganzen Term in Klammern und multipliziere ihn mit 2.
3. Nimm die nächste Ziffer der Binärzahl und multipliziere sie mit 2.
4. Addiere die nächste Ziffer darauf, setze den ganzen Term in Klammern und multipliziere ihn mit 2.
usw.

Beachtet, dass die letzte Ziffer (bzw. der letzte Term) nicht mehr mit ·2 multipliziert wird.

Umwandlung der Binärzahl 101101 mit Horner-Schema

Nehmen wir uns eine größere Binärzahl und wandeln diese mit dem Horner-Schema und der obigen Verfahrensvorschrift um:

101101
= ((((((1·2 + 0)·2) + 1)·2) + 1)·2 + 0)·2 + 1
= 50₁₀

Diesen Term kann man schnell im Kopf rechnen, es ergibt sich als Ergebnis 50, die gesuchte Dezimalzahl.

Polynomdivision mit Horner-Schema

Das Horner-Schema eignet sich auch, um Polynomdivisionen zu lösen. Dabei wird wie folgt schrittweise verfahren:

Es sei zu berechnen: $$ (1 x^3 + 12 x^2 + 47 x + 60) : (x + 5) = $$

Schritt 1: Konstantes Glied des Divisors (x+5) mit umgekehrten Vorzeichen notieren, also -5.
$$ \begin{array}{c|c|c|c|c}&x^{3}&x^{2}&x^{1}&x^{0}\\ \color{#ff5105}{-5}& & & & \\ && \end{array} $$

Schritt 2: Koeffizienten des Dividenden in Potenzreihenfolge herausschreiben:
$$ \begin{array}{c|c|c|c|c}&x^{3}&x^{2}&x^{1}&x^{0}\\ \color{#ff5105}{-5}&1&12&47&60 \\ && \end{array} $$

Schritt 3: Ersten Koeffizienten unverändert notieren:
$$ \begin{array}{c|c|c|c|c}&x^{3}&x^{2}&x^{1}&x^{0}\\ \color{#ff5105}{-5}&1&12&47&60\\ \text{Lsg:}&\color{blue}{1}& \end{array} $$

Schritt 4: Wir multiplizieren die -5 mit der 1 und addieren die nächste Zahl herauf. (Ähnliches Prinzip wie beim Umwandeln der Binärzahlen, siehe oben.)
$$ (\color{#ff5105}{-5})*\color{blue}{1} + 12 = \color{green}{7} $$

Schritt 5: Das Ergebnis 7 notieren wir in der nächsten Spalte:
$$ \begin{array}{c|c|c|c|c}&x^{3}&x^{2}&x^{1}&x^{0}\\ \color{#ff5105}{-5}&1&12&47&60\\ \text{Lsg:}&1&\color{blue}{7}& \end{array} $$

Schritt 6: Wir multiplizieren die -5 mit der 7 und addieren die nächste Zahl 47 herauf.
$$ (\color{#ff5105}{-5})·\color{blue}{7} + 47 = \color{green}{12} $$

Schritt 7: Das Ergebnis 12 notieren wir in der nächsten Spalte:
$$ \begin{array}{c|c|c|c|c}&x^{3}&x^{2}&x^{1}&x^{0}\\ \color{#ff5105}{-5}&1&12&47&60\\ \text{Lsg:}&1&7&\color{blue}{12} \end{array} $$

Schritt 8: Wir multiplizieren die -5 mit der 12 und addieren die nächste Zahl 60 herauf.
$$ (\color{#ff5105}{-5})·\color{blue}{12} + 60 = \color{green}{0} $$

Schritt 9: Das Ergebnis 0 notieren wir in der nächsten Spalte:
$$ \begin{array}{c|c|c|c|c}&x^{3}&x^{2}&x^{1}&x^{0}\\ \color{#ff5105}{-5}&1&12&47&60\\ \text{Lsg:}&1&7&12&\color{blue}{0} \end{array} $$

Schritt 10: Wir haben als Ergebnis die Koeffizienten: 1, 7, 12, 0. Der Rest ist 0.

Unser Ergebnis-Polynom lautet demnach:
$$ 1·x^2 + 7·x^1 + 12·x^0 \color{#AAA}{ + \frac{0}{x+5} } $$

Zusammenfassung:
$$ (1 x^3 + 12 x^2 + 47 x + 60) : (x + 5) = \color{blue}{1·x^2 + 7·x^1 + 12·x^0} = \color{blue}{x^2 + 7·x + 12} $$

  Schreib uns deine Hinweise