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 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

Deli 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).

Kategorija:Polinomi Kategorija:Algoritmi