Horners regel

algoritme

Horners metode (eller Horners skjema) er i matematikk og informatikk en algoritme for polynomevaluering.

Selv om den er oppkalt etter William George Horner, er denne metoden mye eldre, ettersom den har blitt tilskrevet Joseph-Louis Lagrange av Horner selv, og kan spores tilbake mange hundre år til kinesiske og persiske matematikere.[trenger referanse] Etter introduksjonen av datamaskiner ble denne algoritmen grunnleggende for effektiv databehandling med polynomer.

Algoritmen er basert på Horners regel:

Dette tillater evaluering av et polynom av grad n med bare multiplikasjoner og addisjoner. Dette er optimalt, siden det finnes polynomer av grad n som ikke kan evalueres med færre aritmetiske operasjoner.[trenger referanse]

Alternativt refererer Horners metode også til en metode for å tilnærme røttene til polynomer, beskrevet av Horner i 1819. Den metoden er en variant av Newton–Raphson-metoden som er gjort mer effektiv for håndberegning ved å bruke Horners regel. Det ble mye brukt inntil datamaskiner kom i generell bruk rundt 1970.[trenger referanse]

Eksterne lenker

rediger