Hornerjev algoritem/Glavanmasa

Iz MaFiRaWiki

Vsebina

DEFINICIJA

Hornerjev algoritem je postopek, ki temelji na primerjavi koeficientov polinomov na obeh straneh enakosti.

a_nx^n + a_{n-1}x^{n-1} + \cdots + a_2x^2 + a_1x + a_0 = (x - x_0)q(x) + o(x), kjer je
q(x) = b_{n-1}x^{n-1} + b_{n-2}x^{n-2}+\cdots + b_2x^2 + b_1x + b_0, o(x) ostanek, vsi koeficenti so realna števila. Število an, ki je različno od 0 imenujemo vodilni koeficent, a0 pa konstantni člen; n je stopnja polinoma p.


s primerjavo koeficientov dobimo formule:

  • bn − 1 = an
  • bn − 2 = an − 1 + x0bn − 1
  • \cdots
  • b1 = a2 + x0b2
  • b0 = a1 + x0b1
  • p(x0) = a0 + x0b0
  • x0 je možna ničla, možne ničle pa delijo konstantni člen a0

te formule običajno prepišemo v posebno tabelo:

an an − 1 \cdots a1 a0
x0 x0bn − 1 \cdots x0b1 x0b0
an = bn − 1 an − 1 + x0bn − 1 = bn − 2 \cdots a1 + x0b1 = b0 a0 + x0b0 = p(x0)

Hornerjev algoritem uporabljamo predvsem za računanje vrednosti polinoma v določeni točki, oziroma za računanje ničel polinoma. To je ekvivalentno deljenje polinoma z (x-x0) in če se deljenje izide, oziroma če je x0 ničla polinoma, dobimo v zadnjem stolpcu in zadnji vrstici 0, oziroma p(x0) = 0.


PRIMER

Imamo polinom p(x) = x4 − 3x3 − 5x2 + 3x + 4

Možne ničle za ta polinom delijo konstantni člen, ki je v tem primeru 4. Torej so možne ničle: -1, -2, -4, 1, 2, 4

Zapišemo tabelo, po stopnjah razvstimo koeficiente, možno ničlo pripišemo levo. To je ekvivalentno deljenje polinoma z (x-1) in če se deljenje izide, oziroma če je 1 res ničla polinoma, dobimo v zadnjem stolpcu in zadnji vrstici 0.

  |1   -3    -5    3    4
--|-----------------------
1 |     1    -2   -7   -4      
--|-----------------------
  |1   -2    -7    -4   0


Torej vidimo, da je 1 ničla polinoma p(x). v zadnji vrstici pa smo dobili nov polinom q(x) = x3 − 2x2 − 7x − 4.


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