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 wypisuje się wszystkie (również zerowe) współczynniki wielomianu ${\displaystyle W(x),}$ a w dolnym wierszu wpisuje 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}+\ldots +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}}}\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ń.