Hornerova šema

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) predstavlja jednu od navedenih stvari: (i) algoritam za izračunavanje polinoma, koji se sastoji iz transformacije polinoma u oblik pogodniji za izračunavanje; ili (ii) metod za određivanje korena polinoma. Ovaj metod poznat je i pod nazivom Ruffini–Hornerov metod.

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{aligned}b_{n}&:=a_{n}\\b_{n-1}&:=a_{n-1}+b_{n}x_{0}\\&{}\ \ \vdots \\b_{0}&:=a_{0}+b_{1}x_{0}.\end{aligned}}$

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{aligned}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{aligned}}$

Množenje i deljenje u pokretnom zarezu

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) $a_{i}=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{aligned}(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{aligned}}$

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, 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 $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 $2^{0}=1$, neutral za množenje), i $(2^{1})$ 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.

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.

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 monomom $(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 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 $(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++/C implementacija

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

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 $a_{i}$ 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 koristi strukturu matrice, potrebno je samo ${\sqrt {n}}$ umesto $n$ množenja (nauštrb korišćenja dodatnog memorijskog prostora) upotrebom 1973 metoda Patersona i Stokmavera.

Efikasnost

Izračunavanje vrednosti polinoma stepena $n$ u nekoj tački, zahteva najviše $n$ sabiranja i ${\textstyle {\frac {n^{2}+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 $x^{n}$, i potrebno je smestiti $x^{n}$). 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 $kn$ sabiranja i množenja.

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. Viktor Pan (Victor Pan) je 1966. dokazao da je broj množenja minimalan. 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.

Literatura

• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. & Clifford Stein (2009). Introduction to Algorithms (3rd изд.). MIT Press. стр. 41, 900, 990. 
• Horner, William George (1819). „A new method of solving numerical equations of all orders, by continuous approximation”. Philosophical Transactions. Royal Society of London: 308—335.  Directly available online via the link, but also reprinted with appraisal in D.E.Smith: A Source Book in Mathematics, McGraw-Hill, 1929; Dover reprint, 2 vols 1959
• Spiegel, Murray R. (1956). Schaum's Outline of Theory and Problems of College Algebra. McGraw-Hill Book Company. 
• Knuth, Donald (1997). The Art of Computer Programming. Vol. 2: Seminumerical Algorithms (3rd изд.). Addison-Wesley. стр. 486—488 in section 4.6.4. ISBN 978-0-201-89684-8. 
• Kripasagar, Venkat (mart 2008). „Efficient Micro Mathematics - Multiplication and Division Techniques for MCUs”. Circuit Cellar magazine (212): 60. 
• Mikami, Yoshio (1913). „11”. The Development of Mathematics in China and Japan (1st изд.). Chelsea Publishing Co reprint. стр. 74–77.  Yes, really! It looks as though the link is taking you to a completely different work, but you end up at Mikami's book, as you find on checking the specified pages.
• Ulrich, Librecht (2005). „13”. Chinese Mathematics in the Thirteenth Century (2nd изд.). Dover. стр. 175—211. ISBN 978-0-486-44619-6. 
• Wylie, Alexander (1897). Chinese Researches. Printed in Shanghai. , Jottings on the Science of Chinese Arithmetic (reprinted from issues of The North China Herald (1852).
• T. Holdred (1820), A New Method of Solving Equations with Ease and Expedition; by which the True Value of the Unknown Quantity is Found Without Previous Reduction. With a Supplement, Containing Two Other Methods of Solving Equations, Derived from the Same Principle Richard Watts. Sold by Davis and Dickson, mathematical and philosophical booksellers, 17, St. Martin's-le-Grand; and by the author, 2, Denzel Street, Clare-Market, 56pp..

Spoljašnje veze

• Hazewinkel Michiel, ур. (2001). „Horner scheme”. Encyclopaedia of Mathematics. Springer. ISBN 978-1556080104. 
• Weisstein, Eric W. „Horner's method”. MathWorld. 
• Module for Horner's Method by John H. Mathews
• Qiu Jin-Shao, Shu Shu Jiu Zhang (Cong Shu Ji Cheng ed.)