inštrukcije > matematika > Hornerjev algoritem

Objavljeno: 22.2.2019

Hornerjev algoritem

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.

Preberite še:

Potrebujete dodatne informacije? Pomagajo vam lahko inštruktorji matematike.