Schemat Hornera

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

1. obliczania wartości dowolnego wielomianu o jednej zmiennej:

   $w(x)=w_{0}+w_{1}x+w_{2}x^{2}+\ldots +w_{n-1}x^{n-1}+w_{n}x^{n};$

2. dzielenia takiego wielomianu przez dwumian liniowy i moniczny, tj. postaci $x-a$ – znajdowania wielomianu $q(x)$ i liczby $r$ w tożsamości:

   $w(x)=q(x)(x-a)+r.$

Schemat Hornera wykorzystuje minimalną liczbę mnożeń. Dzięki jego rekurencyjnej postaci łatwo go zaimplementować w językach programowania, które umożliwiają stosowanie funkcji rekurencyjnych.

Nazwa tego algorytmu upamiętnia Williama Hornera, który opisał go w 1819 roku. Znali go już jednak matematycy chińscy w XIII wieku, a na początku XIX wieku także Paolo Ruffini. Nazwa upamiętniająca Hornera upowszechniła się jeszcze w XIX wieku, do czego przyczynił się Augustus De Morgan.

Dla dzielenia wielomianu przez dwumian $3x-6$ można stosować schemat Hornera, jeżeli najpierw podzieli się dwumian i wielomian przez 3. Nie dotyczy on jednak dzielenia przez dwumiany stopni wyższych niż jeden, np. przez $4x^{2}-1.$ Schemat Hornera obliczania wartości wielomianu uogólniono na wielomiany wielu zmiennych.

Obliczanie wartości

Wstęp

Jeśli dany jest wielomian $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 $x$ bezpośrednio z podanego wzoru, należy wykonać:

• $n$ dodawań;
• znaczącą liczbę mnożeń:

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

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

Sprawia to, że wystarczy jedynie $n$ mnożeń i $n$ dodawań.

Przykład

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

${\begin{aligned}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}}.\end{aligned}}$

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

Algorytm

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))))=\\&=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}}$

Dzielenie wielomianu przez dwumian

Schemat

Schemat Hornera dzielenia wielomianu $w(x)$ przez dwumian $x-a$ jest oparty 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-a)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śli napiszemy:

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

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}+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

Podzielmy rozważany wcześniej 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);$
• w dolnym wierszu wpisuje kolejno wyniki obliczeń według reguły danej wyżej:

współczynniki licznika $w(x)$	$2$	$0$	$-5$	$4$	$1$
iloczyny		${\frac {3}{2}}\cdot 2=3$	${\frac {3}{2}}\cdot 3={\frac {9}{2}}$	${\frac {3}{2}}\cdot \left(-{\frac {1}{2}}\right)=-{\frac {3}{4}}$	${\frac {3}{2}}\cdot {\frac {13}{4}}={\frac {39}{8}}$
współczynniki ilorazu $B(x)$	$2$	$3$	$-{\frac {1}{2}}$	${\frac {13}{4}}$	${\frac {47}{8}}$

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

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

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).$

Inne zastosowania

Rozkład względem potęg dwumianu

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

${\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 $w(x)$ względem potęg dwumianu $x-a.$ 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 $K$ będzie dowolnym ciałem, a $K[x]$ będzie jego pierścieniem wielomianów. Jeśli

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

to współczynniki ilorazu

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

otrzymanego z dzielenia $f$ przez $x-a,\;a\in K$ 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(a)$ – wynosi

$a_{0}+ab_{0}.$

Zobacz też

• 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 .

Linki zewnętrzne

• Michał Niedźwiedź, Schemat Hornera, Zintegrowana Platforma Edukacyjna, zpe.gov.pl [dostęp 2024-05-22].
• Krzysztof Kwiecień, nagrania kanału Khan Academy na YouTube [dostęp 2024-05-21]:
  • Wprowadzenie do dzielenia wielomianów za pomocą schematu Hornera, 14 sierpnia 2018.
  • Dzielenie wielomianów: Schemat Hornera, 15 sierpnia 2018.
  • Dlaczego schemat Hornera działa?, 18 sierpnia 2018.
• Horner scheme (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-05-17].
• Scott Congreve, Horner’s Scheme (ang.), Uniwersytet Karola w Pradze, mff.cuni.cz [dostęp 2024-05-22] – krótki wykład z ćwiczeniami.