Hornerova šema

Из Википедије, слободне енциклопедије

U matematici, Hornerova š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[уреди]

Neka je dat polinom

p(x) = \sum_{i=0}^n a_i x^i = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots + a_n x^n,

gde su a_0, \ldots, a_n realni brojevi, a potrebno je izračunati vrednost polinom za određenu vrednost promenljive x, na primer x_0.

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

\begin{align}
b_n & := a_n \\
b_{n-1} & := a_{n-1} + b_n x_0 \\
& {}\  \  \vdots \\
b_0 & := a_0 + b_1 x_0.
\end{align}

Tada b_0 ima vrednost p(x_0).

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

p(x) = a_0 + x(a_1 + x(a_2 + \cdots + x(a_{n-1} + a_n x)\cdots)). \,

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


\begin{align}
p(x_0) & = a_0 + x_0(a_1 + x_0(a_2 + \cdots + x_0(a_{n-1} + b_n x_0)\cdots)) \\
& = a_0 + x_0(a_1 + x_0(a_2 + \cdots + x_0(b_{n-1})\cdots)) \\
& {} \ \  \vdots \\
& = a_0 + x_0(b_1) \\
& = b_0.
\end{align}

Množenje i deljenje u pokretnom zarezu[уреди]

Hornerov meted 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) ai = 1, i x = 2. Zatim, x (ili x na određeni stepen) se iznova faktoriše. U ovom binarnom sistemu (sa osnovom 2), x = 2, pa se stepeni dvojke ponavljaju.

Primer[уреди]

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


\begin{align}
( 0.15625) m & = (0.00101_b) m = ( 2^{-3} + 2^{-5}) m = (2^{-3})m + (2^{-5})m \\[4pt]
& = 2^{-3} (m + (2^{-2})m) = 2^{-3} (m + 2^{-2} (m)).
\end{align}

Metod[уреди]

Nalaženje proizvoda dva binarna broja, d i m:

  • 1. Registar u kome se čuva srednji rezultat pripiše se promenljivoj d.
  • 2. Početi od najnižeg bita (prvog s desna) različitog od nule u m.
    • 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, investi šiftovanje udesno onim brojem bita koji se čuva u register 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 d srednjem rezultatu, i nastaviti korakom #2 sa sledećim najvišim bitom u m.

Deljenje[уреди]

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

 (d_3 2^3 + d_2 2^2 + d_1 2^1 + d_0 2^0)m = d_3 2^3 m + d_2 2^2 m + d_1 2^1 m + d_0 2^0 m

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:

 = d_0(m + 2 \frac{d_1}{d_0} (m + 2 \frac{d_2}{d_1} (m + 2 \frac{d_3}{d_2} (m)))).

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

 = d_0(m + 2 {d_1} (m + 2 {d_2} (m + 2 {d_3} (m)))),

odnosno:

 = d_3(m + 2^{-1} {d_2} (m + 2^{-1}{d_1} (m + {d_0} (m)))).

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 (2−1) je aritmetičko šiftovanje udesno, a za (0) nema operacije (kako je 20 = 1, neutral za množenje), i (21) 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 neku preciznost, ali ipak je 13 puta brži, i koristi samo 20% prostora koda.[5]

Određivanje korena polinoma[уреди]

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 p_n(x) stepena n sa nulama  z_n < z_{n-1} < \cdots < z_1 , odrediti polaznu pretpostavku  x_0 kao npr.  x_0 > z_1 . Sada iterativno primenjivati sledeća dva koraka:

1. Koristeći Njutnov metod, naći najveću nulu z_1 polinoma p_n(x) koristeći nagađanje x_0.

2. Koristeći Hornerovu šemu, podeliti (x-z_1) da bi dobili p_{n-1}. Vratiti se na korak 1 ali koristeći polinom p_{n-1} i polaznu pretpostavku z_1.

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[уреди]

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

Pretpostavimo da je polinom oblika,


p_6(x) = (x-3)(x+3)(x+5)(x+8)(x-2)(x-7)

koji se može predstaviti kao


p_6(x) = x^6 + 4x^5 - 72x^4 -214x^3 + 1127x^2 + 1602x -5040.

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 p(x) se deli sa (x-7) da bi dobili


p_5(x) = x^5 + 11x^4 + 5x^3 - 179x^2 - 126x + 720 \,

š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 korespodenciji 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 sa (x-3) i dobija se


p_4(x) = x^4 + 14x^3 + 47x^2 - 38x - 240 \,

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


p_3(x) = x^3 + 16x^2 + 79x + 120 \,

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


p_2(x) = x^2 + 13x + 40 \,

š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 p_2(x) 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++ implementacija[уреди]

Sledeći 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[уреди]

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[уреди]

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

Efikasnost[уреди]

Izračunavanje vrednosti polinoma stepena n u nekoj tački, zahteva najviše n sabiranja i (n2 + n)/2 množenja, ako se stepen računa ponovljenim množenjem i svaki monom se zasebno sračunava. (Ovo se može svesti na n sabiranja i 2n − 1 množenja, iterativnim računanjem stepena od x.) Ako su numerički podaci predstavljeni ciframa (ili bitovima), onda naivni algoritam takođe zahteva smeštanje oko 2n puta broj bitova od x (ocenjen polinom je približno veličine xn, i potrebno je smestiti xn). Nasuprot tome, Hornerova metoda zahteva samo n sabiranja i n množenja, i smeštanje svega n puta broj bitova od x. Hornerov metod može biti izračunat sa n spojenih sabiranje-oduzivanje operacija. Hornerov metod se još može proširiti tako da određuje prvih k delilaca polinoma sa kn 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 x matrica, Hornerov metod nije optimalan.

U opštem slučaju, bez Hornerove šeme, vrednost polinoma stepena n se može izračunati koristeći svega {\scriptstyle{\left\lfloor n/2 \right\rfloor + 2}} množenja i n sabiranja.

Reference[уреди]

  1. ^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2009). Introduction to Algorithms (3rd ed.). 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. ISBN . 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, pp. 105-136.

Literatura[уреди]

Spoljašnje veze[уреди]