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.Mal:Tr Etter introduksjonen av datamaskiner ble denne algoritmen grunnleggende for effektiv databehandling med polynomer.

Algoritmen er basert på Horners regel:

$\begin{array}{cc}{a}_0& +a_{1}x+a_2{x}^2+a_3{x}^3+\cdots +a_n{x}^n\\ & =a_0+x(a_1+x(a_2+x(a_3+\cdots +x(a_{n-1}+x{a}_n))\left)\right).\end{array}$

Dette tillater evaluering av et polynom av grad n med bare $n$ multiplikasjoner og $n$ addisjoner. Dette er optimalt, siden det finnes polynomer av grad n som ikke kan evalueres med færre aritmetiske operasjoner.Mal:Tr

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.Mal:Tr

Eksterne lenker

• Mal:MathWorld