Hornerjev algoritem

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

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

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

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

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