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

KoncepcjaEdytuj

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 wielomianuEdytuj

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 zastosowaniaEdytuj

Dzielenie wielomianu przez dwumianEdytuj

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:

 

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 dwumianuEdytuj

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 punkcieEdytuj

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ówEdytuj

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

PrzypisyEdytuj

BibliografiaEdytuj