Schemat Hornera

Schemat Hornera – sposób obliczania wartości wielomianu dla danej wartości argumentu wykorzystujący minimalną liczbę mnożeń, jest to również algorytm dzielenia wielomianu ${\displaystyle W(x)}$ przez dwumian ${\displaystyle x-c.}$ Schemat ten wiązany jest z nazwiskiem Hornera, był jednak już znany Newtonowi, Ruffiniemu i matematykom chińskim w XII wieku.

Przy dzieleniu wielomianów schemat Hornera można stosować tylko wtedy, gdy dwumian jest postaci ${\displaystyle x+a.}$ Dla przykładu: dla dzielenia przez dwumian ${\displaystyle x-5}$ można stosować schemat Hornera. Jednak dla dzielenia przez dwumian ${\displaystyle 4x^{2}-1}$ schematu Hornera stosować już nie wolno. Dla dzielenia wielomianu przez dwumian ${\displaystyle 3x-6}$ można stosować schemat Hornera, jeżeli najpierw podzieli się dwumian i wielomian przez 3.

Koncepcja

Jeśli dany jest wielomian ${\displaystyle 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 ${\displaystyle x}$ bezpośrednio z podanego wzoru należy wykonać ${\displaystyle 1+2+3+...+(n-1)+n={\frac {n(n+1)}{2}}}$ mnożeń oraz ${\displaystyle n}$ dodawań. Tymczasem proste przekształcenie ${\displaystyle W(x)=a_{0}+x(a_{1}+x(a_{2}+\ldots +x(a_{n-1}+xa_{n})\ldots ))}$ sprawia, że wystarczy jedynie ${\displaystyle n}$ mnożeń i ${\displaystyle n}$ dodawań^[1].

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

Dla przykładu, niech:

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

Zapisujemy:

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

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

${\displaystyle ={\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

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

przekształcamy do postaci

${\displaystyle 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:

${\displaystyle {\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 ${\displaystyle b_{0}}$ będzie równe ${\displaystyle W(x)}$^[1]. Rzeczywiście, jeśli podstawimy kolejno ${\displaystyle b_{n},\ \dots ,\ b_{0}}$ do tego wielomianu, otrzymamy

${\displaystyle {\begin{aligned}W(x)&=a_{0}+x(a_{1}+x(a_{2}+\cdots x(a_{n-2}+x(a_{n-1}+b_{n}x)))),\\W(x)&=a_{0}+x(a_{1}+x(a_{2}+\cdots 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 ${\displaystyle W(x)}$ przez dwumian ${\displaystyle x-c}$ oparty jest na podobnej zasadzie. Zauważmy, że jeśli

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

to

${\displaystyle W(x)=(x-c)B(x)+r,}$

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

${\displaystyle 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:

${\displaystyle {\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 ${\displaystyle W(x)=2x^{4}-5x^{2}+4x+1}$ przez dwumian ${\displaystyle x-{\frac {3}{2}}.}$ Mamy tutaj ${\displaystyle 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 wypisujemy wszystkie (również zerowe) współczynniki wielomianu ${\displaystyle W(x),}$ a w dolnym wierszu wpisujemy kolejno wyniki obliczeń według reguły danej wyżej:

${\displaystyle {\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 ${\displaystyle 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ę ${\displaystyle W\left({\frac {3}{2}}\right).}$

Rozkład względem potęg dwumianu

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

${\displaystyle {\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}+\dots +r_{2}(x-c)^{2}+r_{1}(x-c)+r.\end{aligned}}}$

Otrzymaliśmy więc rozkład wielomianu ${\displaystyle W(x)}$ względem potęg dwumianu ${\displaystyle x-c.}$ Taki rozkład można otrzymać, stosując schemat Hornera kolejno do ${\displaystyle 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

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

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

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

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

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

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

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

Algorytm Hornera dla obliczania początkowych ${\displaystyle m\leq n}$ elementów ${\displaystyle {\frac {w^{(j)}(x)}{j!}}}$ wymaga ${\displaystyle (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 ${\displaystyle P[x]}$ będzie pierścieniem wielomianów, gdzie ${\displaystyle P}$ jest dowolnym ciałem. Jeśli

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

to współczynniki ilorazu

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

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

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

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

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

Zobacz też

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

Przypisy

Bibliografia

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