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 $W(x)\;$ przez dwumian $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 w dwumianie nie ma przy $x\;$ żadnej potęgi i współczynnika. Dla przykładu: dla dzielenia przez dwumian $x-5\;$ można stosować schemat Hornera. Jednak dla dzielenia przez dwumian $4x^2-1\;$ schematu Hornera stosować już nie wolno. Dla dzielenia wielomianu przez dwumian $3x-6\;$ można stosować schemat Hornera, jeżeli najpierw podzieli się dwumian i wielomian, przez 3.

Spis treści

1 Koncepcja
2 Algorytm Hornera obliczania wartości wielomianu
3 Inne zastosowania
4 Uogólnienie na abstrakcyjny pierścień wielomianów
5 Zobacz też

Koncepcja [edytuj]

Jeśli dany jest wielomian $W(x)=a_0+a_1x+a_2x^2+\ldots+a_{n-1}x^{n-1}+a_nx^n\;$ , to obliczając jego wartość dla zadanego $x\;$ bezpośrednio z podanego wzoru należy wykonać $1 + 2 + 3 + ... + (n-1) + n = 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={3 \over 2}:$

$W\left({3 \over 2}\right)={3 \over 2}\left({3 \over 2}\left({3 \over 2}\left({3 \over 2}\cdot 2+0\right)-5\right)+4\right)+1={3 \over 2}\left({3 \over 2}\left({9 \over 2}-5\right)+4\right)+1=$ ${3 \over 2}\left({3 \over 2}\cdot \left(-{1 \over 2}\right)+4\right)+1={3 \over 2}\left(-{3 \over 4} + 4\right) + 1 ={3\over 2}\cdot{13 \over 4}+1 = {39\over 8}+1={47\over 8}.$

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

Algorytm Hornera obliczania wartości wielomianu [edytuj]

Dany wielomian

$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

$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{matrix} b_n & := & a_{n}, \\ b_{n-1} & := & a_{n-1} + b_{n} x, \\ b_{n-2} & := & a_{n-2} + b_{n-1} x \\ & \vdots & \\ b_{0} & := & a_{0} + b_{1} x. \end{matrix}$

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{matrix} 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))), \\ & \vdots & \\ W(x) & = & a_0 + xb_1, \\ W(x) & = & b_0. \\ \end{matrix}$

Inne zastosowania [edytuj]

Dzielenie wielomianu przez dwumian [edytuj]

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

$W(x)=a_nx^n+a_{n-1}x^{n-1}+\ldots+a_1x+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_nx^n+a_{n-1}x^{n-1}+\ldots+a_1x+a_0=(x-c)(b_{n-1}x^{n-1}+b_{n-2}x^{n-2}+\ldots+b_1x+b_0)+r,$

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

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

Dla przykładu, podzielmy ten sam wielomian $W(x)=2x^4-5x^2+4x+1\;$ przez dwumian $x-{3 \over 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 wypisujemy wszystkie (również zerowe) współczynniki wielomianu $W(x)\;$ , a w dolnym wierszu wpisujemy kolejno wyniki obliczeń według reguły danej wyżej:

2	0	-5	4	1
2	${3\over 2}\cdot 2+0=3\;$	${3\over 2}\cdot 3-5=-{1 \over 2}\;$	${3\over 2}\cdot \left(-{1\over 2}\right)+4={13\over 4}\;$	${3\over 2}\cdot {13\over 4}+1={47\over 8}\;$

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({3 \over 2}\right),\;$ .

Rozkład względem potęg dwumianu [edytuj]

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

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

$W(x)=(x-c)((x-c)B_1(x)+r_1)+r=(x-c)^2B_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)^3B_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.\;$

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 [edytuj]

Dany wielomian

$w(x) = (x-\alpha)^jv(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) = {{w^{(j)}(\alpha)} \over {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\;$ :

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

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