Hornerschema

Het Hornerschema, algoritme van Horner, rekenschema van Horner of de regel van Horner is een algoritme om op een efficiënte manier een polynoom te evalueren. Het algoritme is genoemd naar William George Horner, die het in 1819 beschreef.

In de geschiedenis hebben vele wiskundigen zich beziggehouden met methoden om een polynoom te evalueren. De eerste bekende beschrijving van een algoritme zoals het Hornerschema in 1303 is van de Chinese wiskundige Ch'in Chiu-Shao die zijn methode, die hij fan fa noemde, gebruikte voor het oplossen van vergelijkingen. Het algoritme was al in 1669 aan Newton bekend. Dat de naam van Horner toch bekend gebleven is, is vooral te danken aan De Morgan, die in tal van publicaties Horners naam aan deze methode gaf. In Italië publiceerde Paolo Ruffini 15 jaar voor Horner een overeenkomstige methode, reden waarom men ook wel van de Regola di Ruffini spreekt.

Het Hornerschema schrijft de polynoom:

$p(x)=a_{0}+a_{1}x+a_{2}x^{2}+\ldots +a_{n}x^{n}$

als:

$p(x)=\left(\ldots \left(\left(a_{n}x+a_{n-1}\right)x+a_{n-2}\right)x+\ldots \right)x+a_{0}$

en berekent $p(x_{0})$ successievelijk door:

$c_{n-1}=a_{n}$

$c_{n-2}=c_{n-1}x_{0}+a_{n-1}$

$c_{n-3}=c_{n-2}x_{0}+a_{n-2}$

$\vdots$

$c_{0}=c_{1}x_{0}+a_{1}$

$p(x_{0})=c_{0}x_{0}+a_{0}$

Dit komt neer op herhaaldelijk het resultaat van de vorige stap vermenigvuldigen met $x_{0}$ en de volgende coëfficiënt er bij optellen. In totaal $n$ vermenigvuldigingen en $n$ optellingen. Directe berekening zou minimaal $2n$ vermenigvuldigingen en $n$ optellingen vergen.

De berekening laat zich overzichtelijk in een schema, het eigenlijke Hornerschema, onderbrengen, zoals in een volgend voorbeeld getoond wordt.

Uit de bovenstaande berekening ziet men eenvoudig dat het Hornerschema ook gebruikt kan worden om een polynoom te delen door de lineaire polynoom $x-x_{0}$. Er geldt immers:

$p(x)=p(x_{0})+(x-x_{0})(c_{0}+c_{1}x+c_{2}x^{2}+\ldots +c_{n-1}x^{n-1})$

Ook blijkt daaruit dat het Hornerschema het omgekeerde is van het successievelijk uitdelen van $x_{0}$. Immers bij gegeven $x_{0}$ en de waarde $p(x_{0})$ van de polynoom $p(x)$ worden de coëfficiënten ($a_{k}$) bepaald door het Hornerschema in omgekeerde volgorde te doorlopen.

Voorbeeld

We evalueren de polynoom:

$p(x)=5x^{4}-4x^{3}+3x^{2}-2x+1$

in het punt $x=5$. We kunnen door directe berekening gemakkelijk nagaan dat de uitkomst $p(5)=2691$ moet zijn:

$p(x)=(((((5)x-4)x+3)x-2)x+1)$

Hierin staan 5 paar haakjes. Met elk paar haakjes correspondeert 1 stap van de berekening. Men kan $p(x)$ opbouwen in 5 stappen waarbij elke volgende stap bouwt op het resultaat van de vorige stap.

$(5)$

$((5)x-4)$

$(((5)x-4)x+3)$

$((((5)x-4)x+3)x-2)$

$(((((5)x-4)x+3)x-2)x+1)$

Het volstaat nu $x$ te vervangen door 5 om de evaluatie na vijf stappen te verkrijgen.

$c_{3}=5$

$c_{2}=5\times 5-4=21$

$c_{1}=21\times 5+3=108$

$c_{0}=108\times 5-2=538$

$p(5)=538\times 5+1=2691$

Schema

De bovenstaande berekening laat zich kort in het volgende schema weergeven:

   5  |   5   −4    3   −2    1
      |       25  105  540 2690 
  ------------------------------
      |   5   21  108  538 2691

Daarin zijn de stappen goed te herkennen. Vooraan, voor de streep, staat het argument 5. Achter de streep staan de coëfficiënten van de polynoom. Op de tweede rij staan de successievelijke tussenresultaten, die ontstaan door vermenigvuldiging van het argument met het totaal op de derde rij van de optelling van de eerste en tweede rij van de vorige kolom. Het gezochte eindresultaat, 2691, staat als laatste in de derde rij. De getallen daarvoor zijn de coëfficiënten van de deling van de polynoom door $x-5$:

$p(x)=(x-5)(5x^{3}+21x^{2}+108x+538)+2691$

Afgeleide

De bovenstaande polynoom neemt voor $x-5$ de waarde aan van de afgeleide van $p$ in $x-5$, immers:

$p'(x_{0})=\lim _{x\to 5}{\frac {p(x)-p(5)}{x-5}}=\left[5x^{3}+21x^{2}+108x+538\right]_{x=5}$

Dat betekent dat door nogmaals het Hornerschema toe te passen op de ontstane derde regel, de waarde van de afgeleide van $p$ berekend wordt:

   5  |   5   −4    3   −2     1
      |       25  105  540  2690 
  ------------------------------
   5  |   5   21  108  538 (2691)
      |       25  230 1690
  ------------------------------
          5   46  338 2228

Resultaat:

$p'(5)=2228$

Controle met het Hornerschema, met de coëfficiënten van de afgeleide van $p$:

$p'(x)={\frac {\mathrm {d} (5x^{4}-4x^{3}+3x^{2}-2x+1)}{\mathrm {d} x}}=20x^{3}-12x^{2}+6x-2$

   5  |  20  −12    6   −2  
      |      100  440 2230  
  -------------------------
      |  20   88  446 2228

Uitbreidingen

Om in het schema het werken met grote getallen te vermijden, zijn er uitbreidingen ontwikkeld met meer rijen voor eenheden, tientallen enz. Ook zijn er schema's voor polynoomdelingen, die in essentie verkorte en verdichte schrijfwijzen zijn van staartdelingen.

Talstelsels

Bij het omrekenen van de voorstelling van een getal van het ene talstelsel in een ander, maakt men gebruik van het Hornerschema of de omkering, het successievelijk uitdelen, zoals uit de volgende voorbeelden blijkt.

We bepalen de decimale voorstelling van het getal 321₇ in het 7-tallig stelsel, dus de waarde $p(7)$ van de polynoom

$p(x)=3x^{2}+2x+1$

Met het Hornerschema:

$c_{1}=3$

$c_{0}=3\times 7+2=23$

$p(7)=23\times 7+1=162$

Met het echte schema:

   7  |   3    2    1
      |       21  161
  --------------------
      |   3   23  162

Om omgekeerd de voorstelling van $p(7)=162$ in het 7-tallig stelsel te bepalen, moeten we de coëfficiënten van $p(x)$ weten. Dit doen we gewoonlijk door successievelijk door 7 te delen.

$p(7)=162=23\times 7+1$

$23=3\times 7+2$

$3=0\times 7+3$

De resttermen zijn de gezochte coëfficiënten, dus: $p(7)=321_{7}$. We zien dat deze berekening juist de omgekeerde volgorde is van het Hornerschema.

We kunnen natuurlijk ook het Hornerschema volgen voor deze laatste berekening, maar dan moeten we in het 7-tallig stelsel rekenen.

$c_{1}=1$

$c_{0}=1\times 13_{7}+6=22_{7}$

$p(7)=22_{7}\times 13_{7}+2=321_{7}$