Hornerjev algoritem

Iz MaFiRaWiki

V podčlanku /Glavanmasa najdete tudi študentski prispevek na to temo,

ki ga želimo združiti s tem člankom.

Hornerjev algoritem je postopek, s katerim učinkovito izračunamo vrednost polinoma v določeni točki, z njim pa lahko tudi delimo polinom z realnim polinomom oblike xx0.

RAČUNANJE VREDNOSTI POLINOMA V DOLOČENI TOČKI

p(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0

v točki x = t. Namesto, da bi izračunali vsako od potenc t, t2, ..., tn posebej, jih računamo sproti. To naredimo tako, da polinom prepišemo v

p(x) = ((\cdots ((0 + a_n) x + a_{n-1}) x + \cdots) x + a_1) x + a_0

in računamo oklepaje od znotraj navzven.

Psevdokoda

algoritem Horner
vhod: koeficienti polinoma a[0], a[1], ..., a[n] in argument t
izhod: vrednost polinoma z danimi koeficienti pri argumentu t

v := 0
ponavljaj za i = n, n-1, ..., 2, 1, 0:
   v := v * t + a[i];
vrni v;

Implementacija

Osebna orodja