Hornerschema
Uit Wikipedia, de vrije encyclopedia
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.