Hornerjev algoritem

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

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.

Izvedba algoritma[uredi | uredi kodo]

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[uredi | uredi kodo]

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[uredi | uredi kodo]

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