Schemat Hornera

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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 przez dwumian . 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 . Dla przykładu: dla dzielenia przez dwumian można stosować schemat Hornera. Jednak dla dzielenia przez dwumian schematu Hornera stosować już nie wolno. Dla dzielenia wielomianu przez dwumian można stosować schemat Hornera, jeżeli najpierw podzieli się dwumian i wielomian przez 3.

Koncepcja[edytuj]

Jeśli dany jest wielomian , to obliczając jego wartość dla zadanego bezpośrednio z podanego wzoru należy wykonać mnożeń oraz dodawań. Tymczasem proste przekształcenie sprawia, że wystarczy jedynie mnożeń i dodawań[1].

Dla przykładu, niech:

; chcemy obliczyć wartość tego wielomianu dla

Zapisujemy:

podstawiamy

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

Algorytm Hornera obliczania wartości wielomianu[edytuj]

Dany wielomian

przekształcamy do postaci

Następnie definiujemy:

Tak otrzymane będzie równe [1] Rzeczywiście, jeśli podstawimy kolejno do tego wielomianu, otrzymamy

Inne zastosowania[edytuj]

Dzielenie wielomianu przez dwumian[edytuj]

Schemat Hornera dzielenia wielomianu przez dwumian oparty jest na podobnej zasadzie. Zauważmy, że jeśli

to
gdzie jest wielomianem stopnia a jest liczbą, którą nazywa się resztą z dzielenia wielomianu przez dwumian. Jeżeli napiszemy:

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

Dla przykładu, podzielmy ten sam wielomian przez dwumian . Mamy tutaj . Praktycznie jest przeprowadzać obliczenia w tabeli. W jej pierwszym wierszu wypisujemy wszystkie (również zerowe) współczynniki wielomianu , a w dolnym wierszu wpisujemy kolejno wyniki obliczeń według reguły danej wyżej:

 2 
 0 
 -5 
 4 
 1 
 2 

Elementy dolnego wiersza są współczynnikami wielomianu , 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ę .

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

Rozpatrzmy, co będzie, jeżeli wielomian będziemy dzielić wielokrotnie przez , otrzymując za każdym razem pewien wielomian i resztę

Otrzymaliśmy więc rozkład wielomianu względem potęg dwumianu Taki rozkład można otrzymać, stosując schemat Hornera kolejno do 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

gdzie jest stopnia mniejszego niż . Po -krotnym zróżniczkowaniu i podstawieniu :

.

Z tego wynika, że jest -tą znormalizowaną pochodną wielomianu w punkcie :

.

Współczynniki wielomianu i wartości w punkcie obliczamy dzieląc wielomian i kolejno otrzymywane ilorazy przez dwumian :

dla .

Algorytm Hornera dla obliczania początkowych elementów wymaga dodawań i mnożeń.

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

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

Niech będzie pierścieniem wielomianów, gdzie jest dowolnym ciałem. Jeśli

to współczynniki ilorazu

otrzymanego z dzielenia przez spełniają zależność:

dla reszta z tego dzielenia (równa ) wynosi

.

Zobacz też[edytuj]

Przypisy

Bibliografia[edytuj]