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
Wstęp
Jeśli dany jest wielomian to obliczając jego wartość dla zadanego bezpośrednio z podanego wzoru, należy wykonać:
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:
współczynniki
licznika
5
−7
3
−3
iloczyny
10
6
18
współczynniki
ilorazu
5
3
9
15
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
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
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ść:
ZenonZ.FortunaZenonZ., BohdanB.MacukowBohdanB., JanuszJ.WąsowskiJanuszJ., Metody numeryczne, Warszawa: Wydawnictwa Naukowo-Techniczne, 1993, ISBN 83-204-1551-9.
Wojciech Babiański, Lech Chańko, Joanna Czarnowska, Grzegorz Janocha, Dorota Ponczek, Jolanta Wesołowska: Matematyka 2. Podręcznik dla liceum ogólnokształcącego i liceum. Warszawa: Nowa Era, 2022. ISBN 978-83-267-3900-2.