Horners regel

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:

{\displaystyle {\begin{aligned}a_{0}&+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n}\\&=a_{0}+x{\bigg (}a_{1}+x{\Big (}a_{2}+x{\big (}a_{3}+\cdots +x(a_{n-1}+x\,a_{n}){\big )}{\Big )}{\bigg )}.\end{aligned}}}

Dette tillater evaluering av et polynom av grad n med bare ${\displaystyle n}$ multiplikasjoner og ${\displaystyle n}$ 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]}