Hornerjev algoritem

HORNERJEV ALGORITEM

UVOD IN NAMEN

Hornerjev algoritem je postopek za učinkovito vrednotenje polinoma v dani točki ter poenostavitev deljenja polinoma s členom oblike (x – c). Namesto standardnega vstavljanja vrednosti v polinom z več potencami, algoritem omogoča manjše število množenj in seštevanj, zato je računsko hitrejši in preglednejši.

Uporaben je predvsem v naslednjih primerih:

• za izračun vrednosti P(c), kjer je c poljubno realno število,
• za deljenje polinoma s (x – c) in iskanje količnika ter ostanka,
• kot osnova za polinomske metode v numerični matematiki.

OBLIKA POLINOMA ZA UPORABO HORNERJEVEGA ALGORITMA

Polinom mora biti zapisan v splošni obliki z urejenimi eksponenti od najvišje do najnižje potence:

P(x) = aₙxⁿ + aₙ₋₁xⁿ⁻¹ + … + a₁x + a₀

Algoritem pretvori ta izraz v gnezdeno obliko (postopno grupiranje faktorjev x):

P(x) = (…((aₙx + aₙ₋₁)x + aₙ₋₂)x + … + a₁)x + a₀

POSTOPEK IZRAČUNA P(c)

Koraki:

1. Zapišemo koeficiente polinoma: aₙ, aₙ₋₁, …, a₀
2. Izberemo vrednost c, pri kateri želimo izračunati P(c)
3. Uporabimo rekurzivni postopek:
   • Začnemo z: bₙ = aₙ
   • Nato računamo: bₖ = bₖ₊₁·c + aₖ, za k = n–1, n–2, …, 0
   • Zadnji izračunani b₀ je P(c)

PRIMER

Naj bo dan polinom:
P(x) = 2x³ – 6x² + 2x – 1,
in želimo izračunati P(3) po Hornerjevem algoritmu.

Koeficienti: 2 | –6 | 2 | –1
c = 3

Postopek:

• Začnemo z b₃ = 2
• b₂ = 2·3 + (–6) = 6 – 6 = 0
• b₁ = 0·3 + 2 = 2
• b₀ = 2·3 + (–1) = 6 – 1 = 5

Torej: P(3) = 5

DELJENJE POLINOMA S (x – c)

V tem primeru:

• Zadnji člen (b₀) je ostanek deljenja,
• Ostali koeficienti tvorijo količnik deljenja.

V zgornjem primeru:
P(x) = (x – 3)·(2x² + 0x + 2) + 5

ZAKLJUČEK

Hornerjev algoritem omogoča hiter in natančen izračun vrednosti polinoma ter enostavno deljenje s členi oblike (x – c). Zaradi svoje učinkovitosti in sistematičnosti se pogosto uporablja pri numeričnih in algebraičnih postopkih. Poleg računske hitrosti zagotavlja tudi boljšo stabilnost pri računanju z realnimi števili.