inštrukcije > matematika > Hornerjev algoritem
Objavljeno: 22.2.2019
Hornerjev algoritem je poimenovan po angleškem matematiku Williamu Georgeu Hornerju, čeprav so metodo poznali že 600 let prej na Kitajskem.
Če imamo podan polinom
$p(x) = \sum\limits_{i=0}^n a_ix^i = a_0 + a_1x + a_2x^2 + a_3x^3 + ... + a_nx^n$
Kjer so $a_0$ do $a_n$ realna števila želimo dobiti vrednost polinoma pri vrednosti $x$, recimo $x_0$.
Da bi to lahko dosegli, definiramo novo sekvenco konstant:
$b_n := a_n$
$b_{n-1} := a_{n-1} + b_nx_0$
$...$
$b_0 := a_0 + b_1x_0$
če to velja, je $b_0$ vrednost $p(x_0)$.
Da bi videli zakaj je temu tako, lahko zapišemo polinom v drugačni obliki.
$p(x_0) = a_0 + x_0(a_1 + x_0(a_2 + ... + x_0 (a_{n-1} + b_nx_0) ... ))$
$p(x_0) = a_0 + x_0(a_1 + x_0(a_2 + ... + x_0 (b_{n-1}) ... ))$
$...$
$p(x_0) = a_0 + x_0(b_1)$
$p(x_0) = b_0$
Hornerjev algoritem uporabljamo tudi za računanje oziroma iskanje ničel polinoma. Metodo vam pojasni inštruktor Fran na posnetku spodaj.