Хорнерова шема

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) представља једну од наведених ствари: (и) алгоритам за израчунавање полинома, који се састоји из трансформације полинома у облик погоднији за израчунавање; или (ии) метод за одређивање корена полинома. Овај метод познат је и под називом Руффини–Хорнеров метод.

Овај метод је назван по британском математичару Вилијаму Џорџу Хорнеру, иако је био познат и пре по Паулу Руфинију као и шесто година раније, по кинеском математичару Qин Јиу-Схао (енгл. Qин Јиусхао).

Опис алгоритма

Нека је дат полином

$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},$

где су $a_{0},\ldots ,a_{n}$ реални бројеви, а потребно је израчунати вредност полином за одређену вредност променљиве $x$, на пример $x_{0}$.

Да бисмо то постигли, дефинишемо нови низ константи:

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

Тада $b_{0}$ има вредност $p(x_{0})$.

Како би доказали да је ова тачно, приметимо да се полином може записати у следећем облику

$p(x)=a_{0}+x(a_{1}+x(a_{2}+\cdots +x(a_{n-1}+a_{n}x)\cdots )).\,$

На овај начин, итеративно замењујући $b_{i}$ у претходном изразу, добијамо

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

Множење и дељење у покретном зарезу

Хорнеров метод је брз и ефикасан метод за множење и дељење бинарних бројева на микроконтролеру (енгл. мицроцонтроллер) који не садржи посебно коло за множење бинарних бројева. Један од бинарних бројева који се множе се престави као прост полином, где је (користећи горе поменуту нотацију) $a_{i}=1$, и $x=2$. Затим, $x$ (или $x$ на одређени степен) се изнова факторише. У овом бинарном систему (са основом 2), $x=2$, па се степени двојке понављају.

Пример

На пример, да бисмо нашли производ два броја, (0.15625) и $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}}$

Метод

Налажење производа два бинарна броја, $d$ и $m$:

• 1. Регистар у коме се чува средњи резултат припише се променљивој $d$.
• 2. Почети од најнижег бита (првог с десна) различитог од нуле у $m$.
  • 2б. Бројати (улево) број битова до следећег највишег не-нула бита. Ако више нема значајних битова, онда узети вредност бита са тренутне позиције.
  • 2ц. Користећи ту вредност, извести шифтовање удесно оним бројем бита који се чува у регистру за средњи резултат
• 3. Ако су избројани ски не-нула битови, онда регистер за средњи резултат сада садржи коначно решење. У супротном, додати $d$ средњем резултату, и наставити кораком #2 са следећим највишим битом у $m$.

Дељење

У општем случају, за бинарни број са битовима: ($d_{3}d_{2}d_{1}d_{0}$) производ је:

$(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$

У овој фазе алгоритма, потребно је избацити терме са коефицијентима нула, тако да буду избројани само бинарни коефицијенти једнаки јединици, тако да се не јавља проблем множења или дељења са нулом, упркос овој импликацији у факторисаној једначини:

$=d_{0}(m+2{\frac {d_{1}}{d_{0}}}(m+2{\frac {d_{2}}{d_{1}}}(m+2{\frac {d_{3}}{d_{2}}}(m)))).$

Сви имениоци су јединице (или се израз изоставља), па добијамо:

$=d_{0}(m+2{d_{1}}(m+2{d_{2}}(m+2{d_{3}}(m)))),$

односно:

$=d_{3}(m+2^{-1}{d_{2}}(m+2^{-1}{d_{1}}(m+{d_{0}}(m)))).$

У бинарној (основа 2) математици, множење степеном двојке је само аритметичко шифтовање. Тако се множење бројем 2 израчунава помоћу операције аритметичко шифтовање. Фактор $(2^{-1})$ је аритметичко шифтовање удесно, а за $(0)$ нема операције (како је $2^{0}=1$, неутрал за множење), и $(2^{1})$ резултује шифтовање за једно место улево. Производ множења се сада брзо може израчунати само аритметичким шифтовањем, сабирањем и одузимањем.

Метод је прилично брз на процесорима који подржавају једно-инстукционе шифтуј-и-додај операције. У поређењу са C-овом библиотеком за рачунање у покретном зарезу, Хорнеров метод жртује одређену прецизност, али ипак је 13 пута бржи, и користи само 20% простора кода.

Одређивање корена полинома

Коришћењем Хорнерове шеме у комбинацији са Њутновим методом, могу се одредити реални корени полинома. Алгоритам функционише на следећи начин. Нека је дат полином $p_{n}(x)$ степена $n$ са нулама $z_{n}<z_{n-1}<\cdots <z_{1}$, одредити полазну претпоставку $x_{0}$ као нпр. $x_{0}>z_{1}$. Сада итеративно примењивати следећа два корака:

1. Користећи Њутнов метод, наћи највећу нулу $z_{1}$ полинома $p_{n}(x)$ користећи нагађање $x_{0}$.

2. Користећи Хорнерову шему, поделити $(x-z_{1})$ да би добили $p_{n-1}$. Вратити се на корак 1 али користећи полином $p_{n-1}$ и полазну претпоставку $z_{1}$.

Ова два корака се понављају док се не добију све реалне нуле почетног полинома. Ако одређене нуле нису довољно прецизне, добијене вредности се могу употребити као полазне претпоставке за Њутнов метод али користећи цео полином уместо редукованог.

Пример

Налажење корена полинома коришћењем Хорнерове шеме

Претпоставимо да је полином облика,

$p_{6}(x)=(x-3)(x+3)(x+5)(x+8)(x-2)(x-7)$

који се може представити као

$p_{6}(x)=x^{6}+4x^{5}-72x^{4}-214x^{3}+1127x^{2}+1602x-5040.$

Из горе наведеног знамо да је највећи корен овог полинома 7, па можемо да узмемо као полазну претпоставку број 8. Користећи Њутнов метод, први корен, са вредношћу 7, се добија као што је приказано црном бојом горњој слици. Следећи $p(x)$ се дели мономом $(x-7)$ да би добили

$p_{5}(x)=x^{5}+11x^{4}+5x^{3}-179x^{2}-126x+720\,$

што је представљено црвеном бојом на горњој слици. Њутнов метод се користи да би нашли највећу нулу полинома са полазном претпоставком 7. Највећа нула овог полинома која је у кореспонденцији са другом највећом нулом почетног полинома налази се на броју 3 и заокружена је црвеном бојом. Полином петог степена се сада дели мономом $(x-3)$ и добија се

$p_{4}(x)=x^{4}+14x^{3}+47x^{2}-38x-240\,$

који је приказан жутом бојом. Нула овог полинома је нађена на броју 2, поново користећи Њутнов метод и заокружена је жутом бојом. Хорнерова шема се сада користи за добијање полинома трећег степена

$p_{3}(x)=x^{3}+16x^{2}+79x+120\,$

који је приказан зеленом бојом и пронађена му је нула на броју  −3. Овај полином се даље редукује на

$p_{2}(x)=x^{2}+13x+40\,$

што је приказано плавом бојом и има нулу  −5. Коначни корен полазног полинома може се добити или коришћењем последње нуле као полазне претпоставке за Њутнов метод, или редуковање $p_{2}(x)$ и решавањем линеарне једначине. Као што се може видети, добијени су очекивани корени −8, −5, −3, 2, 3, и 7.

C++/C имплементација

Следећи C++/C код представља функцију за израчунавање вредности полинома помоћу Хорнерове шеме.

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 имплементација

Следећи Пyтхон код је имплементација Хорнеровог метода.

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

Примена

Хорнерова шема се може користити за конвертовање између различитих позиционих бројевних система - у том случају $x$ је база тог бројевног система и $a_{i}$ коефицијенти су цифре које се користе у $x$- бројевном систему за репрезентацију датог броја; такође се може користити ако је $x$ матрица, у том случају добија се још већа ефикасност при рачунању. Заправо, када је $x$ матрица, даље убрзање је могуће и користи структуру матрице, потребно је само ${\sqrt {n}}$ уместо $n$ множења (науштрб коришћења додатног меморијског простора) употребом 1973 метода Патерсона и Стокмавера.

Ефикасност

Израчунавање вредности полинома степена $n$ у некој тачки, захтева највише $n$ сабирања и ${\textstyle {\frac {n^{2}+n}{2}}}$ множења, ако се степен рачуна поновљеним множењем и сваки моном се засебно срачунава. (Ово се може свести на $n$ сабирања и $2n-1$ множења, итеративним рачунањем степена од $x$.) Ако су нумерички подаци представљени цифрама (или битовима), онда наивни алгоритам такође захтева смештање око $2n$ пута број битова од $x$ (оцењен полином је приближно величине $x^{n}$, и потребно је сместити $x^{n}$). Насупрот томе, Хорнерова метода захтева само $n$ сабирања и $n$ множења, и смештање свега $n$ пута број битова од $x$. Хорнеров метод може бити израчунат са $n$ спојених сабирање-одузивање операција. Хорнеров метод се још може проширити тако да одређује првих $k$ делилаца полинома $kn$ сабирања и множења.

Хорнеров метод је оптималан, у смислу да сваки други алгоритам за израчунавање вредности полинома мора да искористи макар толико операција колико и Хорнеров. Александар Островски (Алеxандер Остроwски) је 1954. доказао да је број потребних сабирања минималан. Виктор Пан (Вицтор Пан) је 1966. доказао да је број множења минималан. У сваком случају, када је $x$ матрица, Хорнеров метод није оптималан.

У општем случају, без Хорнерове шеме, вредност полинома степена $n$ се може израчунати користећи свега ${\scriptstyle {\left\lfloor n/2\right\rfloor +2}}$ множења и $n$ сабирања.

Литература

• Цормен, Тхомас Х.; Леисерсон, Цхарлес Е.; Ривест, Роналд L. & Цлиффорд Стеин (2009). Интродуцтион то Алгоритхмс (3рд изд.). МИТ Пресс. стр. 41, 900, 990. 
• Хорнер, Wиллиам Георге (1819). „А неw метход оф солвинг нумерицал еqуатионс оф алл ордерс, бy цонтинуоус аппроxиматион”. Пхилосопхицал Трансацтионс. Роyал Социетy оф Лондон: 308—335.  Дирецтлy аваилабле онлине виа тхе линк, бут алсо репринтед wитх аппраисал ин D.Е.Смитх: А Соурце Боок ин Матхематицс, МцГраw-Хилл, 1929; Довер репринт, 2 волс 1959
• Спиегел, Мурраy Р. (1956). Сцхаум'с Оутлине оф Тхеорy анд Проблемс оф Цоллеге Алгебра. МцГраw-Хилл Боок Цомпанy. 
• Кнутх, Доналд (1997). Тхе Арт оф Цомпутер Программинг. Вол. 2: Семинумерицал Алгоритхмс (3рд изд.). Аддисон-Wеслеy. стр. 486—488 ин сецтион 4.6.4. ИСБН 978-0-201-89684-8. 
• Крипасагар, Венкат (март 2008). „Еффициент Мицро Матхематицс - Мултиплицатион анд Дивисион Тецхниqуес фор МЦУс”. Цирцуит Целлар магазине (212): 60. 
• Миками, Yосхио (1913). „11”. Тхе Девелопмент оф Матхематицс ин Цхина анд Јапан (1ст изд.). Цхелсеа Публисхинг Цо репринт. стр. 74–77.  Yес, реаллy! Ит лоокс ас тхоугх тхе линк ис такинг yоу то а цомплетелy дифферент wорк, бут yоу енд уп ат Миками'с боок, ас yоу финд он цхецкинг тхе специфиед пагес.
• Улрицх, Либрецхт (2005). „13”. Цхинесе Матхематицс ин тхе Тхиртеентх Центурy (2нд изд.). Довер. стр. 175—211. ИСБН 978-0-486-44619-6. 
• Wyлие, Алеxандер (1897). Цхинесе Ресеарцхес. Принтед ин Схангхаи. , Јоттингс он тхе Сциенце оф Цхинесе Аритхметиц (репринтед фром иссуес оф Тхе Нортх Цхина Хералд (1852).
• Т. Холдред (1820), А Неw Метход оф Солвинг Еqуатионс wитх Еасе анд Еxпедитион; бy wхицх тхе Труе Валуе оф тхе Ункноwн Qуантитy ис Фоунд Wитхоут Превиоус Редуцтион. Wитх а Супплемент, Цонтаининг Тwо Отхер Метходс оф Солвинг Еqуатионс, Деривед фром тхе Саме Принципле Рицхард Wаттс. Солд бy Давис анд Дицксон, матхематицал анд пхилосопхицал боокселлерс, 17, Ст. Мартин'с-ле-Гранд; анд бy тхе аутхор, 2, Дензел Стреет, Цларе-Маркет, 56пп..

Спољашње везе

• Хазеwинкел Мицхиел, ур. (2001). „Хорнер сцхеме”. Енцyцлопаедиа оф Матхематицс. Спрингер. 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.)