Schemat Hornera

Schemat Hornera – wspólna nazwa dwóch algorytmów:

• obliczania wartości wielomianu dla danego argumentu (w danym punkcie), wykorzystując minimalną liczbę mnożeń;
• dzielenia wielomianu $W(x)$ przez dwumian liniowy i moniczny, tj. postaci $x-c.$

Nazwa pochodzi od Williama Hornera, który opisał go w 1819 roku; znali go już jednak Isaac Newton, Paolo Ruffini i matematycy chińscy w XII wieku.

Schemat Hornera nie dotyczy dzielenia przez dwumiany stopni wyższych niż jeden, np. przez $4x^{2}-1.$ Dla dzielenia wielomianu przez dwumian $3x-6$ można stosować schemat Hornera, jeżeli najpierw podzieli się dwumian i wielomian przez 3.

Dzięki rekurencyjnej postaci schematu Hornera, jest go łatwo zaimplementować w językach programowania, które umożliwiają stosowanie funkcji rekurencyjnych.

Koncepcja

Jeśli dany jest wielomian $W(x)=a_{0}+a_{1}x+a_{2}x^{2}+\ldots +a_{n-1}x^{n-1}+a_{n}x^{n},$ to obliczając jego wartość dla zadanego $x$ bezpośrednio z podanego wzoru, należy wykonać $1+2+3+\ldots +(n-1)+n={\frac {n(n+1)}{2}}$ mnożeń oraz $n$ dodawań. Tymczasem proste przekształcenie $W(x)=a_{0}+x(a_{1}+x(a_{2}+\ldots +x(a_{n-1}+xa_{n})\ldots ))$ sprawia, że wystarczy jedynie $n$ mnożeń i $n$ dodawań.

Dla przykładu, niech:

$W(x)=2x^{4}-5x^{2}+4x+1;$ chcemy obliczyć wartość tego wielomianu dla $x=3/2.$

Zapisujemy:

$2x^{4}-5x^{2}+4x+1=x(x(x(x\cdot 2+0)-5)+4)+1;$ podstawiamy $x={\frac {3}{2}}{:}$

$W\left({\frac {3}{2}}\right)={\frac {3}{2}}\left({\frac {3}{2}}\left({\frac {3}{2}}\left({\frac {3}{2}}\cdot 2+0\right)-5\right)+4\right)+1={\frac {3}{2}}\left({\frac {3}{2}}\left({\frac {9}{2}}-5\right)+4\right)+1$

$={\frac {3}{2}}\left({\frac {3}{2}}\cdot \left(-{\frac {1}{2}}\right)+4\right)+1={\frac {3}{2}}\left(-{\frac {3}{4}}+4\right)+1={\frac {3}{2}}\cdot {\frac {13}{4}}+1={\frac {39}{8}}+1={\frac {47}{8}}.$

Warto dla porównania obliczyć tę wartość metodą „tradycyjną” nie korzystając z kalkulatora.

Algorytm Hornera obliczania wartości wielomianu

Dany wielomian

$W(x)=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\ldots +a_{n-2}\,x^{n-2}+a_{n-1}x^{n-1}+a_{n}x^{n}$

przekształcamy do postaci

$W(x)=a_{0}+x(a_{1}+x(a_{2}+\ldots +x(a_{n-2}+x(a_{n-1}+xa_{n}))\ldots )).$

Następnie definiujemy:

${\begin{aligned}b_{n}&:=a_{n},\\b_{n-1}&:=a_{n-1}+b_{n}x,\\b_{n-2}&:=a_{n-2}+b_{n-1}x\\&\;\dots \\b_{0}&:=a_{0}+b_{1}x.\end{aligned}}$

Tak otrzymane $b_{0}$ będzie równe $W(x)$. Rzeczywiście, jeśli podstawimy kolejno $b_{n},\ \dots ,\ b_{0}$ do tego wielomianu, otrzymamy

${\begin{aligned}W(x)&=a_{0}+x(a_{1}+x(a_{2}+\ldots x(a_{n-2}+x(a_{n-1}+b_{n}x)))),\\W(x)&=a_{0}+x(a_{1}+x(a_{2}+\ldots x(a_{n-2}+b_{n-1}x))),\\&\dots \\W(x)&=a_{0}+xb_{1},\\W(x)&=b_{0}.\end{aligned}}$

Inne zastosowania

Dzielenie wielomianu przez dwumian

Schemat Hornera dzielenia wielomianu $W(x)$ przez dwumian $x-c$ oparty jest na podobnej zasadzie. Zauważmy, że jeśli

$W(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\ldots +a_{1}x+a_{0},$

to

$W(x)=(x-c)B(x)+r,$

gdzie $B(x)$ jest wielomianem stopnia $n-1,$ a $r$ jest liczbą, którą nazywa się resztą z dzielenia wielomianu przez dwumian. Jeżeli napiszemy:

$a_{n}x^{n}+a_{n-1}x^{n-1}+\ldots +a_{1}x+a_{0}=(x-c)(b_{n-1}x^{n-1}+b_{n-2}x^{n-2}+\ldots +b_{1}x+b_{0})+r,$

to po wymnożeniu i porównaniu współczynników obu stron mamy:

${\begin{aligned}b_{n-1}&=a_{n}\\b_{n-2}&=a_{n-1}+c\cdot b_{n-1},\\b_{n-3}&=a_{n-2}+c\cdot b_{n-2},\\&\dots ,\\b_{0}&=a_{1}+c\cdot b_{1},\\r&=a_{0}+c\cdot b_{0}.\end{aligned}}$

Dla przykładu, podzielmy ten sam wielomian $W(x)=2x^{4}-5x^{2}+4x+1$ przez dwumian $x-{\frac {3}{2}}.$ Mamy tutaj $a_{4}=2,\,a_{3}=0,\,a_{2}=-5,\,a_{1}=4,\,a_{0}=1.$ Praktycznie jest przeprowadzać obliczenia w tabeli. W jej pierwszym wierszu wypisuje się wszystkie (również zerowe) współczynniki wielomianu $W(x),$ a w dolnym wierszu wpisuje kolejno wyniki obliczeń według reguły danej wyżej:

${\begin{array}{|c|}\hline 2&0&-5&4&1\\\hline 2&\displaystyle {\frac {3}{2}}\cdot 2+0=3&\displaystyle {\frac {3}{2}}\cdot 3-5=-{\frac {1}{2}}&\displaystyle {\frac {3}{2}}\cdot \left(-{\frac {1}{2}}\right)+4={\frac {13}{4}}&\displaystyle {\frac {3}{2}}\cdot {\frac {13}{4}}+1={\frac {47}{8}}\\\hline \end{array}}$

Elementy dolnego wiersza są współczynnikami wielomianu $B(x),$ natomiast skrajny prawy element jest resztą z dzielenia.

Przy okazji można zauważyć, że jest to dowód wniosku z twierdzenia Bézouta o tym, że reszta r równa się $W\left({\frac {3}{2}}\right).$

Rozkład względem potęg dwumianu

Rozpatrzmy, co będzie, jeżeli wielomian $W(x)$ będziemy dzielić wielokrotnie przez $x-c,$ otrzymując za każdym razem pewien wielomian $B_{j}$ i resztę $r_{j}{:}$

${\begin{aligned}W(x)&=(x-c)B(x)+r,\\W(x)&=(x-c)((x-c)B_{1}(x)+r_{1})+r=(x-c)^{2}B_{1}(x)+r_{1}(x-c)+r,\\W(x)&=(x-c)^{2}((x-c)B_{2}(x)+r_{2})+r_{1}(x-c)+r=(x-c)^{3}B_{2}(x)+r_{2}(x-c)^{2}+r_{1}(x-c)+r,\\&\dots \\W(x)&=r_{n}(x-c)^{n}+r_{n-1}(x-c)^{n-1}+\ldots +r_{2}(x-c)^{2}+r_{1}(x-c)+r.\end{aligned}}$

Otrzymaliśmy więc rozkład wielomianu $W(x)$ względem potęg dwumianu $x-c.$ Taki rozkład można otrzymać, stosując schemat Hornera kolejno do $W(x),\ B(x),\ B_{1}(x),\ \dots ,\ B_{n-1}(x)$ i biorąc reszty jako współczynniki (im później jest otrzymana reszta, tym przy większej potędze jest ona współczynnikiem).

Obliczanie wartości znormalizowanych pochodnych w punkcie

Dany wielomian

$w(x)=(x-\alpha )^{j}v(x)+r(x),$

gdzie $r(x)$ jest stopnia mniejszego niż $j.$ Po $j$-krotnym zróżniczkowaniu i podstawieniu $\alpha {:}$

$w^{(j)}(\alpha )=j!v(\alpha ).$

Z tego wynika, że $v(\alpha )$ jest $j$-tą znormalizowaną pochodną wielomianu $W(x)$ w punkcie $\alpha {:}$

$v(\alpha )={\frac {w^{(j)}(\alpha )}{j!}}.$

Współczynniki wielomianu $v$ i wartości $v$ w punkcie $\alpha$ obliczamy dzieląc wielomian $W$ i kolejno otrzymywane ilorazy przez dwumian $x-\alpha {:}$

${\frac {w(x)}{(x-\alpha )^{k}}}\quad {}$ dla $k=1,\dots ,j-1.$

Algorytm Hornera dla obliczania początkowych $m\leqslant n$ elementów ${\frac {w^{(j)}(x)}{j!}}$ wymaga $(m+1)\left(n-{\frac {m}{n}}\right)$ dodawań i mnożeń.

Uogólnienie na abstrakcyjny pierścień wielomianów

Schematy podane wyżej można uogólnić na przypadek abstrakcyjnego pierścienia wielomianów.

Niech $P[x]$ będzie pierścieniem wielomianów, gdzie $P$ jest dowolnym ciałem. Jeśli

$f(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\ldots +a_{1}x+a_{0}\in P[x],$

to współczynniki ilorazu

$b_{n-1}x^{n-1}+\ldots +b_{1}x+b_{0},$

otrzymanego z dzielenia $f$ przez $x-c,\;c\in P$ spełniają zależność:

$b_{n-1}=a_{n},\;b_{k}=a_{k+1}+cb_{k+1}$

dla $k=0,\;1,\;\dots ,\;n-2;$ reszta z tego dzielenia (równa $f(c)$) wynosi

$a_{0}+cb_{0}.$

Zobacz też

• twierdzenie Bézouta
• złożoność obliczeniowa

Bibliografia

• ZenonZ. Fortuna ZenonZ., BohdanB. Macukow BohdanB., JanuszJ. Wąsowski JanuszJ., Metody numeryczne, Warszawa: Wydawnictwa Naukowo-Techniczne, 1993, ISBN 83-204-1551-9 .