Hornerjev algoritem

Hórnerjev algorítem je matematični algoritem, ki se uporablja pri računaju s polinomi. Postopek se imenuje po angleškem matematiku Williamu Georgeu Hornerju.

Hornerjev algoritem se uporablja za naslednje naloge:

deljenje danega polinoma p z linearnim polinomom (x - a),
računanje vrednosti danega polinoma p v točki a,
iskanje ničel danega polinoma p.
računanje vrednosti odvoda polinoma v dani točki.

Izvedba algoritma

Bistvo Hornerjevga algoritma se skriva v dejstvu, da se lahko polinom učinkovito predstavi z njegovimi koeficienti, ki se jih zapiše po vrsti (od najvišje potence do najnižje).

Zgled 1

Izračuna naj se vrednost polinoma $p(x)=2x^{3}-6x^{2}+2x-1\,$ v točki $x=3\;$ .

Polinom se predstavi s koeficienti, ki se jih zapiše v naslednjo shemo:

   |   2    -6     2    -1
   |    
---|----------------------
 3 |

Na levi strani (spodaj) se je zapisalo dano število x = 3.

Hornerjev algoritem sestavljajo naslednji koraki:

korak 1: vodilni koeficient (v zgledu 2) se prepiše pod črto.
korak 2: število pod črto se pomnoži s številom x levo (v tem zgledu x = 3) in dobljeni zmnožek se zapiše nad črto v naslednji stolpec.
korak 3: števili v naslednjem stolpcu se sešteje in vsoto se zapiše pod črto.
korak 4: s številom, ki se ga je za zdaj dobilo pod črto, se izvede spet korak 2 in 3.
konec: postopek se nadaljuje, dokler se ne pride do zadnjega stolpca.

   |   2    -6     2    -1
   |         6     0     6    
---|-----------------------
 3 |   2     0     2  |  5
                      -----

Število, ki se ga je dobilo pod črto v zadnjem stolpcu, je vrednost polinoma v točki a (v tem primeru se je dobilo p(3) = 5). To število se po navadi tudi dodatno označi oziroma loči od ostalih števil pod črto.

Ostala števila pod črto (v zgledu 2, 0, 2) predstavljajo polinom k(x) - tj. količnik pri deljenju polinoma p s polinomom (x - a).

Zgled 2

Deli se polinom $p(x)=x^{3}-6x^{2}+11x-6\,\!$ s polinomom $(x-2)\,\!$ :

Tudi to deljenje se opravi po istem postopku kot zgoraj. Dobi se naslednji rezultat:

   |   1    -6    11    -6
   |         2    -8     6    
---|-----------------------
 2 |   1    -4     3  |  0
                      -----

Količnik deljenja je polinom, ki ga predstavljajo števila (1, -4, 3) pod črto, torej $k(x)=x^{2}-4x+3\,\!$ .

Ostanek pri deljenju je enak vrednosti polinoma p v točki 2 in je v tem primeru enak 0 (število pod črto desno).