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.[bron?] 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
[bewerken | brontekst bewerken]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
[bewerken | brontekst bewerken]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
[bewerken | brontekst bewerken]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
[bewerken | brontekst bewerken]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
[bewerken | brontekst bewerken]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.