U matematici, Hornеrova šema (takođe poznata i kao Hornerov metod ili Hornerovo pravilo) (engl. Horner's method, Horner's sheme, Horner's rule)[1][2] predstavlja jednu od navedenih stvari: (i) algoritam za izračunavanje polinoma, koji se sastoji iz transformacije polinoma u oblik pogodniji za izračunavanje[2]; ili (ii) metod za određivanje korena polinoma.[3] Ovaj metod poznat je i pod nazivom Ruffini–Hornerov metod.[4]

Ovaj metod je nazvan po britanskom matematičaru Vilijamu Džordžu Horneru, iako je bio poznat i pre po Paulu Rufiniju kao i šesto godina ranije, po kineskom matematičaru Qin Jiu-Shao (engl. Qin Jiushao).

Opis algoritma uredi

Neka je dat polinom

 

gde su   realni brojevi, a potrebno je izračunati vrednost polinom za određenu vrednost promenljive  , na primer  .

Da bismo to postigli, definišemo novi niz konstanti:

 

Tada   ima vrednost  .

Kako bi dokazali da je ova tačno, primetimo da se polinom može zapisati u sledećem obliku

 

Na ovaj način, iterativno zamenjujući   u prethodnom izrazu, dobijamo

 

Množenje i deljenje u pokretnom zarezu uredi

Hornerov metod je brz i efikasan metod za množenje i deljenje binarnih brojeva na mikrokontroleru (engl. microcontroller) koji ne sadrži posebno kolo za množenje binarnih brojeva. Jedan od binarnih brojeva koji se množe se prestavi kao prost polinom, gde je (koristeći gore pomenutu notaciju)  , i  . Zatim,   (ili   na određeni stepen) se iznova faktoriše. U ovom binarnom sistemu (sa osnovom 2),  , pa se stepeni dvojke ponavljaju.

Primer uredi

Na primer, da bismo našli proizvod dva broja, (0.15625) i  :

 

Metod uredi

Nalaženje proizvoda dva binarna broja,   i  :

  • 1. Registar u kome se čuva srednji rezultat pripiše se promenljivoj  .
  • 2. Početi od najnižeg bita (prvog s desna) različitog od nule u  .
    • 2b. Brojati (ulevo) broj bitova do sledećeg najvišeg ne-nula bita. Ako više nema značajnih bitova, onda uzeti vrednost bita sa trenutne pozicije.
    • 2c. Koristeći tu vrednost, izvesti šiftovanje udesno onim brojem bita koji se čuva u registru za srednji rezultat
  • 3. Ako su izbrojani ski ne-nula bitovi, onda register za srednji rezultat sada sadrži konačno rešenje. U suprotnom, dodati   srednjem rezultatu, i nastaviti korakom #2 sa sledećim najvišim bitom u  .

Deljenje uredi

U opštem slučaju, za binarni broj sa bitovima: ( ) proizvod je:

 

U ovoj faze algoritma, potrebno je izbaciti terme sa koeficijentima nula, tako da budu izbrojani samo binarni koeficijenti jednaki jedinici, tako da se ne javlja problem množenja ili deljenja sa nulom, uprkos ovoj implikaciji u faktorisanoj jednačini:

 

Svi imenioci su jedinice (ili se izraz izostavlja), pa dobijamo:

 

odnosno:

 

U binarnoj (osnova 2) matematici, množenje stepenom dvojke je samo aritmetičko šiftovanje. Tako se množenje brojem 2 izračunava pomoću operacije aritmetičko šiftovanje. Faktor   je aritmetičko šiftovanje udesno, a za   nema operacije (kako je  , neutral za množenje), i   rezultuje šiftovanje za jedno mesto ulevo. Proizvod množenja se sada brzo može izračunati samo aritmetičkim šiftovanjem, sabiranjem i oduzimanjem.

Metod je prilično brz na procesorima koji podržavaju jedno-instukcione šiftuj-i-dodaj operacije. U poređenju sa C-ovom bibliotekom za računanje u pokretnom zarezu, Hornerov metod žrtuje određenu preciznost, ali ipak je 13 puta brži, i koristi samo 20% prostora koda.[5]

Određivanje korena polinoma uredi

Korišćenjem Hornerove šeme u kombinaciji sa Njutnovim metodom, mogu se odrediti realni koreni polinoma. Algoritam funkcioniše na sledeći način. Neka je dat polinom   stepena   sa nulama  , odrediti polaznu pretpostavku   kao npr.  . Sada iterativno primenjivati sledeća dva koraka:

1. Koristeći Njutnov metod, naći najveću nulu   polinoma   koristeći nagađanje  .

2. Koristeći Hornerovu šemu, podeliti   da bi dobili  . Vratiti se na korak 1 ali koristeći polinom   i polaznu pretpostavku  .

Ova dva koraka se ponavljaju dok se ne dobiju sve realne nule početnog polinoma. Ako određene nule nisu dovoljno precizne, dobijene vrednosti se mogu upotrebiti kao polazne pretpostavke za Njutnov metod ali koristeći ceo polinom umesto redukovanog.[6]

Primer uredi

 
Nalaženje korena polinoma korišćenjem Hornerove šeme

Pretpostavimo da je polinom oblika,

 

koji se može predstaviti kao

 

Iz gore navedenog znamo da je najveći koren ovog polinoma 7, pa možemo da uzmemo kao polaznu pretpostavku broj 8. Koristeći Njutnov metod, prvi koren, sa vrednošću 7, se dobija kao što je prikazano crnom bojom gornjoj slici. Sledeći   se deli monomom   da bi dobili

 

što je predstavljeno crvenom bojom na gornjoj slici. Njutnov metod se koristi da bi našli najveću nulu polinoma sa polaznom pretpostavkom 7. Najveća nula ovog polinoma koja je u korespondenciji sa drugom najvećom nulom početnog polinoma nalazi se na broju 3 i zaokružena je crvenom bojom. Polinom petog stepena se sada deli monomom   i dobija se

 

koji je prikazan žutom bojom. Nula ovog polinoma je nađena na broju 2, ponovo koristeći Njutnov metod i zaokružena je žutom bojom. Hornerova šema se sada koristi za dobijanje polinoma trećeg stepena

 

koji je prikazan zelenom bojom i pronađena mu je nula na broju  −3. Ovaj polinom se dalje redukuje na

 

što je prikazano plavom bojom i ima nulu  −5. Konačni koren polaznog polinoma može se dobiti ili korišćenjem poslednje nule kao polazne pretpostavke za Njutnov metod, ili redukovanje   i rešavanjem linearne jednačine. Kao što se može videti, dobijeni su očekivani koreni −8, −5, −3, 2, 3, i 7.

C++/C implementacija uredi

Sledeći C++/C kod predstavlja funkciju za izračunavanje vrednosti polinoma pomoću Hornerove šeme.

int Horner( int a[], int n, int x ) {
    int result = a[n];
    for(int i=n-1; i >= 0 ; --i)
        result = result * x + a[i];
    return result;
}

Python implementacija uredi

Sledeći Python kod je implementacija Hornerovog metoda.

def horner(x, *polynomial):
    """A function that implements the Horner Scheme for evaluating a
    polynomial of coefficients *polynomial in x."""
    result = 0
    for coefficient in polynomial:
        result = result * x + coefficient
    return result

Primena uredi

Hornerova šema se može koristiti za konvertovanje između različitih pozicionih brojevnih sistema - u tom slučaju   je baza tog brojevnog sistema i   koeficijenti su cifre koje se koriste u  - brojevnom sistemu za reprezentaciju datog broja; takođe se može koristiti ako je   matrica, u tom slučaju dobija se još veća efikasnost pri računanju. Zapravo, kada je   matrica, dalje ubrzanje je moguće i koristi strukturu matrice, potrebno je samo   umesto   množenja (nauštrb korišćenja dodatnog memorijskog prostora) upotrebom 1973 metoda Patersona i Stokmavera.[7]

Efikasnost uredi

Izračunavanje vrednosti polinoma stepena   u nekoj tački, zahteva najviše   sabiranja i   množenja, ako se stepen računa ponovljenim množenjem i svaki monom se zasebno sračunava. (Ovo se može svesti na   sabiranja i   množenja, iterativnim računanjem stepena od  .) Ako su numerički podaci predstavljeni ciframa (ili bitovima), onda naivni algoritam takođe zahteva smeštanje oko   puta broj bitova od   (ocenjen polinom je približno veličine  , i potrebno je smestiti  ). Nasuprot tome, Hornerova metoda zahteva samo   sabiranja i   množenja, i smeštanje svega   puta broj bitova od  . Hornerov metod može biti izračunat sa   spojenih sabiranje-oduzivanje operacija. Hornerov metod se još može proširiti tako da određuje prvih   delilaca polinoma   sabiranja i množenja.[8]

Hornerov metod je optimalan, u smislu da svaki drugi algoritam za izračunavanje vrednosti polinoma mora da iskoristi makar toliko operacija koliko i Hornerov. Aleksandar Ostrovski (Alexander Ostrowski) je 1954. dokazao da je broj potrebnih sabiranja minimalan.[9] Viktor Pan (Victor Pan) je 1966. dokazao da je broj množenja minimalan.[10] U svakom slučaju, kada je   matrica, Hornerov metod nije optimalan.

U opštem slučaju, bez Hornerove šeme, vrednost polinoma stepena   se može izračunati koristeći svega   množenja i   sabiranja.

Reference uredi

  1. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. & Clifford Stein (2009). Introduction to Algorithms (3rd изд.). MIT Press. стр. 41, 900, 990. 
  2. ^ а б „Wolfram MathWorld: Horner's Rule”. 
  3. ^ „Wolfram MathWorld: Horner's Method”. 
  4. ^ „French Wikipedia: Méthode de Ruffini-Horner”. 
  5. ^ Kripasagar, March 2008, "Efficient Micro Mathematics", Circuit Cellar, issue 212, pp. 62.
  6. ^ Kress, Rainer, "Numerical Analysis", Springer. 1991. pp. 112.
  7. ^ Higham, Nicholas. (2002). Accuracy and Stability of Numerical Algorithms. Philadelphia: SIAM. ISBN 978-0-89871-521-7. . Section 5.4.
  8. ^ W. Pankiewicz. „Algorithm 337: calculation of a polynomial and its derivative values by Horner scheme”. 
  9. ^ Ostrowski, A. M. (1954). "On two problems in abstract algebra connected with Horner's rule", Studies in Math. Mech. pp. 40-48. New York: Academic Press.
  10. ^ Pan, Y. Ja. (1966). "On means of calculating values of polynomials, Russian Math. Surveys" . 21: 105—136.  Недостаје или је празан параметар |title= (помоћ).

Literatura uredi

Spoljašnje veze uredi