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
urediBistvo 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
urediIzračuna naj se vrednost polinoma v točki .
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
urediDeli se polinom s polinomom :
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 .
Ostanek pri deljenju je enak vrednosti polinoma p v točki 2 in je v tem primeru enak 0 (število pod črto desno).