Schemat Hornera

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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 dwumian jest postaci x + a. 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.

Koncepcja[edytuj | edytuj kod]

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

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

Dzielenie wielomianu przez dwumian[edytuj | edytuj kod]

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

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

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

Uogólnienie na abstrakcyjny pierścień wielomianów[edytuj | edytuj kod]

Schematy podane wyżej można uogólnić na przypadek abstrakcyjnego pierścienia wielomianów.

Niech P[x]\; będzie pierścieniem wielomianów, gdzie P\; jest dowolnym ciałem. Jeśli

f(x) = a_nx^n + a_{n-1}x^{n-1} + \dots + a_1x + a_0 \in P[x],\;

to współczynniki ilorazu

b_{n-1}x^{n-1} + \dots + b_1x + b_0,\;

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

b_{n-1} = a_n,\; b_k = a_{k+1} + c b_{k+1}\;

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

a_0 + cb_0\;.

Zobacz też[edytuj | edytuj kod]