Hornerjev algoritem

Hórnerjev algorítem je matematični algoritem, ki ga uporabljamo pri računaju s polinomi. Postopek se imenuje po angleškem matmatiku W. G. Hornerju.

Hornerjev algoritem uporabljamo 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.

Izvedba algoritma

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

Zgled 1

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

Polinom predstavimo s koeficienti, ki jih zapišemo v naslednjo shemo:

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

Na levi strani (spodaj) smo zapisali dano število x = 3.

Hornerjev algoritem sestavljajo naslednji koraki:

• Korak 1: Vodilni koeficient (v našem primeru 2) prepišemo pod črto.
• Korak 2: Število pod črto pomnožimo s številom x levo (v našem primeru x = 3) in dobljeni zmnožek zapišemo nad črto v naslednji stolpec.
• Korak 3: Števili v naslednjem stolpcu seštejemo in vsoto zapišemo pod črto.
• Korak 4: S številom, ki smo ga zdaj dobili pod črto, izvedemo spet korak 2 in 3.
• Konec: Postopek nadaljujemo, dokler ne pridemo do zadnjega stolpca.

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

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

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

Zgled 2

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

Tudi to deljenje opravimo po istem postopku kot zgoraj. Dobimo 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).