title: Hornerschema
text: 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:
  
  als:
  
  en berekent  successievelijk door:
  
  Dit komt neer op herhaaldelijk het resultaat van de vorige stap vermenigvuldigen met  en de volgende coëfficiënt er bij optellen. In totaal  vermenigvuldigingen en  optellingen. Directe berekening zou minimaal  vermenigvuldigingen en  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 . Er geldt immers:
  
  Ook blijkt daaruit dat het Hornerschema het omgekeerde is van het successievelijk uitdelen van . Immers bij gegeven  en de waarde  van de polynoom  worden de coëfficiënten () bepaald door het Hornerschema in omgekeerde volgorde te doorlopen.
  
  Voorbeeld 
  We evalueren de polynoom:
  
  in het punt . We kunnen door directe berekening gemakkelijk nagaan dat de uitkomst  moet zijn:
  
  Hierin staan 5 paar haakjes. Met elk paar haakjes correspondeert 1 stap van de berekening.
  Men kan  opbouwen in 5 stappen waarbij elke volgende stap bouwt op het resultaat van de vorige stap.
  
  Het volstaat nu  te vervangen door 5 om de evaluatie na vijf stappen te verkrijgen.
  
  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 :
  
  Afgeleide 
  De bovenstaande polynoom neemt voor  de waarde aan van de afgeleide van  in , immers:
  
  Dat betekent dat door nogmaals het Hornerschema toe te passen op de ontstane derde regel, de waarde van de afgeleide van  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:
  
  Controle met het Hornerschema, met de coëfficiënten van de afgeleide van : 
  
      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 3217 in het 7-tallig stelsel, dus de waarde  van de polynoom
  
  Met het Hornerschema:
  
  Met het echte schema:
  
      7  |   3    2    1
         |       21  161
     --------------------
         |   3   23  162
  
  Om omgekeerd de voorstelling van  in het 7-tallig stelsel te bepalen, moeten we de coëfficiënten van  weten. Dit doen we gewoonlijk door successievelijk door 7 te delen.
  
  De resttermen zijn de gezochte coëfficiënten, dus: . 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.
  
  Numerieke wiskunde