Hornerova šema
Tipično, polinom se predstavlja oblikom:
$f(x)=\sum_{k=0}^{n} a_k x^k$
ili
gde su ak realni brojevi koji predstavljaju koeficijente polinoma, a xk su promenljive polinoma.
Za prethodni polinom kažemo da je n-tog stepena, na primer deg(f(x)) = n, gde je n najveći stepen promenljive.
Hornerova šema za deljenje polinoma je metod za izračunavanje vrednosti polinoma f(x) za vrednost promenljive x = x0 razlaganjem polinoma na monome (polinome prvog stepena). Svaki monom uključuje najviše jedno množenje i jedno sabiranje. Rezultat dobijen iz jednog monoma se dodaje na rezultat dobijen iz sledećeg monoma, i tako redom akumulativnom metodom. Ovaj postupak se u Americi naziva još i sintetičko deljenje.
Kako bismo objasnili prethodno zapišimo polinom u drugačijoj formi;
Možemo ga zapisati ovako:
Algoritam koji sledi iz ovog pravila zasniva se na izračunavanju monoma gore formiraninh počevši od onog u najdubljoj zagradi i krećući se izračunavanjem monoma u spoljnjim zagradama.
Metoda se primenjuje praćenjem sledećih koraka:
2. bk = ak
3. bk - 1 = ak - 1 + bkx0
4. k = k - 1
5. Ako je k ≥ 0 vratiti se na korak 3.
U suprotnom je kraj.
Ovaj metod se može i grafički predstaviti za polinom petog stepena datog sa:
koji može biti izračunat za x = x0 transformacijom polinoma u oblik:
Drugi način predstavljanja rezultata korišćenjem ove metode je pomoću tablice date ispod:
K | 5 | 4 | 3 | 2 | 1 | 0 |
b5 = a5 | b4 = a4 + x0b5 | b3 = a3 + x0b4 | b2 = a2 + x0b3 | b1 = a1 + x0b2 | b0 = a0 + x0b1 |
Primer: Izračunaj vrednost polinoma f(x) = x4 + 3x3 + 5x2 + 7x + 9 za x = 2
Rešenje:
Pošto je polinom četvrtog stepena onda je n = 4
K | 4 | 3 | 2 | 1 | 0 |
Korak | b4 = 1 | b3 = 3 + 2 * 1 | b2 = 5 + 2 * 5 | b1 = 7 + 2 * 15 | b0 = 9 + 2 * 37 |
Rezultat | 1 | 5 | 15 | 37 | 83 |
Pa je, f(2) = 83.
Zašto koristimo ovu metodu?
Uobičajeno, kada izračunavamo polinom za određenu vrednost promenljive, navikli smo zameniti vrednost ove promenljive u polinom i izračunati. Takođe možemo razviti i primeniti matematičku aplikaciju za izračunavanje kako bismo to uradili, što je neophodno kada radimo sa složenim polinomima velikog stepena.
Način na koji računar procesuira problem uglavnom zavisi od toga kako vi kao programer opišete proces računaru. Možete napraviti da vaša aplikacija rešava polinome direktnom zamenom ili koristeći sintetičko deljenje prema Hornerovom pravilu. Jedina razlika između ova dva pristupa je brzina kojom će računar rešiti problem u bilo kom od ova dva slučaja.
Prednost Hornerovog pravila je u tome što smanjuje broj operacija množenja. Znajući da je vreme potrebno računaru za izračunavanje samo jedne operacije množenja 5 do 20 puta duže od vremena potrebnog za sabiranje, jasno je da će aplikacija za izračunavanje polinoma pomoću Hornerovog pravila značajno smanjiti vreme potrebno računaru da izračuna polinom.