Schemat Hornera

Wstęp

Jeśli dany jest wielomian ${\displaystyle w(x)=w_{0}+w_{1}x+w_{2}x^{2}+\ldots +w_{n-1}x^{n-1}+w_{n}x^{n},}$ to obliczając jego wartość dla zadanego ${\displaystyle x}$ bezpośrednio z podanego wzoru, należy wykonać:

• ${\displaystyle n}$ dodawań;
• znaczącą liczbę mnożeń:

${\displaystyle 1+2+3+\ldots +(n-1)+n={\frac {n(n+1)}{2}}.}$

Wielomian ten można jednak przekształcić, korzystając z rozdzielności mnożenia względem dodawania:

${\displaystyle w(x)=w_{0}+x(w_{1}+x(w_{2}+\ldots +x(w_{n-1}+xw_{n})\ldots )).}$

Sprawia to, że wystarczy jedynie ${\displaystyle n}$ mnożeń i ${\displaystyle n}$ dodawań.

Przykład

Obliczanie wartości ${\displaystyle w(2)}$ wielomianu opisanego wzorem ${\displaystyle w(x)=4x^{3}-5x^{2}+7x-20}$:

${\displaystyle {\begin{aligned}w(x)&=x(4x^{2}-5x+7)-20=\\&=x(x(4x-5)+7)-20,\\w(2)&=2(2(4\cdot 2-5)+7)-20=\\&=2(2(8-5)+7)-20=\\&=2(2\cdot 3+7)-20=\\&=2(6+7)-20=\\&=2\cdot 13-20=\\&=26-20=6.\\\end{aligned}}}$

Obliczenia te można też zapisać w tabeli, ograniczając powtórzenia współczynników wielomianu, jego argumentu, nawiasów, znaków działań i równości:

Algorytm

Dany wielomian

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

${\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)}$. 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}+\ldots x(a_{n-2}+x(a_{n-1}+b_{n}x))))=\\&=a_{0}+x(a_{1}+x(a_{2}+\ldots x(a_{n-2}+b_{n-1}x)))=\\&\dots \\&=a_{0}+xb_{1}=\\&=b_{0}.\end{aligned}}}$

Schemat

Dowolny wielomian ${\displaystyle w}$ można podzielić z resztą przez dwumian ${\displaystyle x-a}$. Innymi słowy, jeśli:

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

to istnieją wielomian ${\displaystyle B}$ stopnia ${\displaystyle n-1}$ i liczba ${\displaystyle r}$ takie, że:

${\displaystyle {\begin{aligned}w(x)&=(x-a)B(x)+r,\\w(x)&=a_{n}x^{n}+a_{n-1}x^{n-1}+\ldots +a_{1}x+a_{0}=\\&=(x-a)(b_{n-1}x^{n-1}+b_{n-2}x^{n-2}+\ldots +b_{1}x+b_{0})+r.\end{aligned}}}$

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}+ab_{n-1},\\b_{n-3}&=a_{n-2}+ab_{n-2},\\&\dots ,\\b_{0}&=a_{1}+ab_{1},\\r&=a_{0}+ab_{0}.\end{aligned}}}$

Przykład

Niech ${\displaystyle w(x)=5x^{3}-7x^{2}+3x-3}$. Dzielenie tego wielomianu przez dwumian ${\displaystyle x-2}$ można zapisać w tabeli:

• pierwszy wiersz zawiera wszystkie – również zerowe – współczynniki wielomianu ${\displaystyle w;}$
• dolny wiersz zawiera wyniki obliczeń według reguły danej wyżej:

Prawie wszystkie elementy dolnego wiersza – oprócz ostatniego – to współczynniki wielomianu ${\displaystyle B,}$ a ostatni element, czyli skrajnie prawy, to reszta z dzielenia:

${\displaystyle w(x)=(x-2)(5x^{2}+3x+9)+15.}$

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(2).}$

Rozkład względem potęg dwumianu

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

${\displaystyle {\begin{aligned}w(x)&=(x-a)B(x)+r=\\&=(x-a){\Bigl (}(x-a)B_{1}(x)+r_{1}{\Bigr )}+r=\\&=(x-a)^{2}B_{1}(x)+r_{1}(x-a)+r=\\&=(x-a)^{2}{\Bigl (}(x-a)B_{2}(x)+r_{2}{\Bigr )}+r_{1}(x-a)+r=\\&=(x-a)^{3}B_{2}(x)+r_{2}(x-a)^{2}+r_{1}(x-a)+r,\\&\dots \\w(x)&=r_{n}(x-a)^{n}+r_{n-1}(x-a)^{n-1}+\ldots +r_{2}(x-a)^{2}+r_{1}(x-a)+r.\end{aligned}}}$

Otrzymaliśmy więc rozkład wielomianu ${\displaystyle w(x)}$ względem potęg dwumianu ${\displaystyle x-a.}$ 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}}}\quad {}}$ dla ${\displaystyle k=1,\dots ,j-1.}$

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