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. Etter introduksjonen av datamaskiner ble denne algoritmen grunnleggende for effektiv databehandling med polynomer.
Algoritmen er basert på Horners regel:

  
    
      
        
          
            
              
                
                  
                    
                      a
                      
                        0
                      
                    
                  
                  
                    
                    +
                    
                      a
                      
                        1
                      
                    
                    x
                    +
                    
                      a
                      
                        2
                      
                    
                    
                      x
                      
                        2
                      
                    
                    +
                    
                      a
                      
                        3
                      
                    
                    
                      x
                      
                        3
                      
                    
                    +
                    ⋯
                    +
                    
                      a
                      
                        n
                      
                    
                    
                      x
                      
                        n
                      
                    
                  
                
                
                  
                  
                    
                    =
                    
                      a
                      
                        0
                      
                    
                    +
                    x
                    
                      
                        (
                      
                    
                    
                      a
                      
                        1
                      
                    
                    +
                    x
                    
                      
                        (
                      
                    
                    
                      a
                      
                        2
                      
                    
                    +
                    x
                    
                      
                        (
                      
                    
                    
                      a
                      
                        3
                      
                    
                    +
                    ⋯
                    +
                    x
                    (
                    
                      a
                      
                        n
                        −
                        1
                      
                    
                    +
                    x
                    
                    
                      a
                      
                        n
                      
                    
                    )
                    
                      
                        )
                      
                    
                    
                      
                        )
                      
                    
                    
                      
                        )
                      
                    
                    .
                  
                
              
            
          
        
      
    
    {\displaystyle {\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 
  
    
      
        
          
            n
          
        
      
    
    {\displaystyle {\displaystyle n}}
   multiplikasjoner og 
  
    
      
        
          
            n
          
        
      
    
    {\displaystyle {\displaystyle n}}
   addisjoner. Dette er optimalt, siden det finnes polynomer av grad n som ikke kan evalueres med færre aritmetiske operasjoner.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.


== Eksterne lenker ==
(en) Eric W. Weisstein, Horner's Rule i MathWorld.