Schemat Hornera

Z Wikipedii

Schemat Hornera – sposób obliczania wartości wielomianu dla danej wartości argumentu wykorzystujący minimalną liczbę mnożeń. Również algorytm dzielenia wielomianu W(x) przez dwumian x-c wiązany z nazwiskiem Hornera był jednak znany już Newtonowi, Ruffiniemu i matematykom chińskim w XII wieku.

Spis treści

1 Teoria pierścieni
- 1.1 Dowód
2 Koncepcja
3 Algorytm Hornera
4 Inne zastosowania
- 4.1 Dzielenie wielomianu przez dwumian
- 4.2 Obliczanie wartości znormalizowanych pochodnych w punkcie

[edytuj] Teoria pierścieni

Niech $P [X]$ będzie pierścieniem wielomianów. Jeśli

$f(X) = a_nX^n + a_{n-1}X^{n-1} + \dots + a_1X^1 + a_0 \in P[X],\; c \in P,$

to współczynniki ilorazu

$b_{n-1}X^{n-1} + \dots + b_1X^1 + b_0\;$

otrzymanego z dzielenia $f\;$ przez $X - c\;$ 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\;$ .

[edytuj] Dowód

Ten artykuł wymaga dopracowania zgodnie z zaleceniami edycyjnymi.
Należy w nim poprawić: potrzebny dowód.
Dokładniejsze informacje o tym, co należy poprawić, być może znajdziesz na stronie dyskusji tego artykułu.
Po naprawieniu wszystkich błędów można usunąć tę wiadomość.

[edytuj] Koncepcja

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 dla obliczenia jego wartości 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: $a_0+x(a_1+x(a_2+\ldots +x(a_{n-1}+xa_n)\ldots))$ pokazuje, że wystarczy jedynie n mnożeń i n dodawań. Mnożenia są operacją czasochłonną i eliminacja zbędnych mnożeń jest jednym z podstawowych problemów optymalizacji algorytmów.

Dla przykładu, niech:

W (x) = 2 x 4 - 5 x 2 + 4 x + 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$ i 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}{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.

[edytuj] Algorytm Hornera

Dany wielomian

$p(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots + a_n x^n.$

przekształcamy do postaci

$p(x) = a_0 + x(a_1 + x(a_2 + \cdots + x(a_{n-1} + a_n x)))$

Następnie rozpoczynając od najbardziej wewnętrznego działania definiujemy:

$\begin{matrix} b_n & := & a_{n} \\ b_{n-1} & := & a_{n-1} + b_{n} x \\ & \vdots & \\ b_{0} & := & a_{0} + b_{1} x \end{matrix}$

Jeśli podstawimy b_n do tego wielomianu otrzymamy

$\begin{matrix} p(x) & = & a_0 + x(a_1 + x(a_2 + \cdots x(a_{n-1} + b_n x))) \\ p(x) & = & a_0 + x(a_1 + x(a_2 + \cdots x(b_{n-1}))) \\ & \vdots & \\ p(x) & = & a_0 + x(b_1) \\ p(x) & = & b_0 \\ \end{matrix}$

tak więc b₀ jest wartością wielomianu p od x.

[edytuj] Inne zastosowania

[edytuj] Dzielenie wielomianu przez dwumian

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$ i $W (x) = (x - c) B (x) + r,$ to z teorii wynika, że B(x) jest wielomianem stopnia n–1, a r jest liczbą. 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}$

...

$b_0=a_1+c\cdot b_1$

$r=a_0+c\cdot b_0$

Dla przykładu, podzielmy ten sam wielomian co poprzednio, : $W (x) = 2 x 4 - 5 x 2 + 4 x + 1$ przez dwumian $x-{3 \over 2}$ . Mamy tutaj $a_4=2,\,a_3=0,\,a_2=-5,\,a_1=4,\,a_0=1$ . Obliczenia praktycznie jest przeprowadzać w tabeli: w jej pierwszym wierszu wypisujemy wszystkie, czyli również zerowe współczynniki wielomianu W(x), a w dolnym 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. Z twierdzenia Bezouta wynika natychmiast, że jest to wartość wielomianu

W (x) = 2 x 4 - 5 x 2 + 4 x + 1

dla $x={3 \over 2}$ .

[edytuj] Obliczanie wartości znormalizowanych pochodnych w punkcie

Dany wielomian

w (y) = (y - x) j v (y) + r (y)

(gdzie r(y) jest stopnia mniejszego niż j) po j-krotnym zróżniczkowaniu

w (j) (y) = j! v (y)

Z tego wynika, że v(y) jest j-tą znormalizowaną pochodną wielomianu w(y) w punkcie x.

$v(y) = {{w^{(j)}(y)} \over {j!}}$

Współczynniki wielomianu v i wartości v w punkcjie x obliczamy dzieląc wielomian w i kolejno otrzymywane ilorazy przez dwumian y-x.

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

Twierdzenie: Algorytm Hornera dla obliczania poczatkowych $m \le n$ elementów ${{w^{(j)}(y)} \over {j!}}$ wymaga $(m+1)(n-{m\over n})$ dodawań i mnożeń.