Schemat Hornera

algorytm obliczania wartości wielomianu i dzielenia go przez moniczny dwumian liniowy Z Wikipedii, wolnej encyklopedii

Schemat Hornera – wspólna nazwa dwóch algorytmów:

  1. obliczania wartości dowolnego wielomianu o jednej zmiennej:
  2. dzielenia takiego wielomianu przez dwumian liniowy i moniczny, tj. postaci – znajdowania wielomianu i liczby w tożsamości[1]:

Schemat Hornera wykorzystuje minimalną liczbę mnożeń[potrzebny przypis]. Dzięki jego rekurencyjnej postaci łatwo go zaimplementować w językach programowania, które umożliwiają stosowanie funkcji rekurencyjnych.

Nazwa tego algorytmu upamiętnia Williama Hornera, który opisał go w 1819 roku[1]. Znali go już jednak matematycy chińscy w XIII wieku, a na początku XIX wieku także Paolo Ruffini[2]. Nazwa upamiętniająca Hornera upowszechniła się jeszcze w XIX wieku[3], do czego przyczynił się Augustus De Morgan[2].

Dla dzielenia wielomianu przez dwumian można stosować schemat Hornera, jeżeli najpierw podzieli się dwumian i wielomian przez 3. Nie dotyczy on jednak dzielenia przez dwumiany stopni wyższych niż jeden, np. przez Schemat Hornera obliczania wartości wielomianu uogólniono na wielomiany wielu zmiennych[4].

Obliczanie wartości

Podsumowanie
Perspektywa

Wstęp

Jeśli dany jest wielomian to obliczając jego wartość dla zadanego bezpośrednio z podanego wzoru, należy wykonać:

Wielomian ten można jednak przekształcić, korzystając z rozdzielności mnożenia względem dodawania:

Sprawia to, że wystarczy jedynie mnożeń i dodawań[5].

Przykład

Obliczanie wartości wielomianu opisanego wzorem [6]:

Obliczenia te można też zapisać w tabeli, ograniczając powtórzenia współczynników wielomianu, jego argumentu, nawiasów, znaków działań i równości[6]:

Więcej informacji współczynniki wielomianu, −5 ...
współczynniki

wielomianu

4 −5 7 −20
iloczyny 2×4 = 8 2×3 = 6 2×13 = 26
sumy −5+8 = 3 7+6 = 13 −20 + 26 = 6
Zamknij

Algorytm

Dany wielomian

przekształcamy do postaci

Następnie definiujemy:

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

Dzielenie wielomianu przez dwumian

Podsumowanie
Perspektywa

Schemat

Dowolny wielomian można podzielić z resztą przez dwumian . Innymi słowy, jeśli:

to istnieją wielomian stopnia i liczba takie, że:

Po wymnożeniu i porównaniu współczynników obu stron mamy[7]:

Przykład

Niech . Dzielenie tego wielomianu przez dwumian można zapisać w tabeli:

  • pierwszy wiersz zawiera wszystkie – również zerowe – współczynniki wielomianu
  • dolny wiersz zawiera wyniki obliczeń według reguły danej wyżej:
Więcej informacji licznika ...
współczynniki

licznika

5 −7 3 −3
iloczyny 10 6 18
współczynniki

ilorazu

5 3 9 15
Zamknij

Prawie wszystkie elementy dolnego wiersza – oprócz ostatniego – to współczynniki wielomianu a ostatni element, czyli skrajnie prawy, to reszta z dzielenia[8]:

Przy okazji można zauważyć, że jest to dowód wniosku z twierdzenia Bézouta o tym, że reszta r równa się

Inne zastosowania

Podsumowanie
Perspektywa

Rozkład względem potęg dwumianu

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

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

Podsumowanie
Perspektywa

Schematy podane wyżej można uogólnić na przypadek abstrakcyjnego pierścienia wielomianów[potrzebny przypis]. Niech będzie dowolnym ciałem, a będzie jego pierścieniem wielomianów. Jeśli

to współczynniki ilorazu

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

dla reszta z tego dzielenia – równa – wynosi

Zobacz też

Przypisy

Bibliografia

Linki zewnętrzne

Wikiwand - on

Seamless Wikipedia browsing. On steroids.