Schemat Hornera – wspólna nazwa dwóch algorytmów: obliczania wartości dowolnego wielomianu o jednej zmiennej:
dzielenia takiego wielomianu przez dwumian liniowy i moniczny, tj. postaci Schemat Hornera to znajdowanie wielomianu i liczby w tożsamości:
Schemat Hornera wykorzystuje minimalną liczbę mnożeń. 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. Znali go już jednak matematycy chińscy w XIII wieku, a na początku XIX wieku także Paolo Ruffini [dostęp 2024-05-22].. Nazwa upamiętniająca Hornera upowszechniła się jeszcze w XIX wieku Jeff Miller, Horner's method [w:] Earliest Known Uses of Some of the Words of Mathematics (H) , MacTutor History of Mathematics archive, University of St Andrews, mathshistory.st-andrews.ac.uk [dostęp 2024-05-22]., do czego przyczynił się Augustus De Morgan.
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 Juna Manuel Peña, Thomas Sauer, On the multivariate Horner scheme , SIAM Journal on Numerical Analysis 37(4), czerwiec 1998, ResearchGate, researchgate.net [dostęp 2024-05-22]..
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ć: dodawań; znaczącą liczbę mnożeń:
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ń.
Przykład Obliczanie wartości wielomianu opisanego wzorem :
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: współczynniki wielomianu4−57−20iloczyny2×4 = 82×3 = 62×13 = 26sumy−5+8 = 37+6 = 13−20 + 26 = 6
Algorytm Dany wielomian
przekształcamy do postaci
Następnie definiujemy:
Tak otrzymane będzie równe . Rzeczywiście, jeśli podstawimy kolejno do tego wielomianu, otrzymamy
Dzielenie wielomianu przez dwumian 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 Michał Niedźwiedź, Schemat Hornera, Zintegrowana Platforma Edukacyjna, zpe.gov.pl [dostęp 2024-05-22].:
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−73−3iloczyny10618współczynniki ilorazu 53915 Prawie wszystkie elementy dolnego wiersza – oprócz ostatniego – to współczynniki wielomianu a ostatni element, czyli skrajnie prawy, to reszta 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ę 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. 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ż złożoność obliczeniowa algorytm Clenshawa
Przypisy
Bibliografia
Linki zewnętrzne Krzysztof Kwiecień, nagrania kanału Khan Academy na YouTube [dostęp 2024-05-21]: Wprowadzenie do dzielenia wielomianów za pomocą schematu Hornera, 14 sierpnia 2018. Dzielenie wielomianów: Schemat Hornera, 15 sierpnia 2018. Dlaczego schemat Hornera działa?, 18 sierpnia 2018. Horner scheme , Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-05-17]. Scott Congreve, Horner’s Scheme , Uniwersytet Karola w Pradze, mff.cuni.cz [dostęp 2024-05-22] – krótki wykład z ćwiczeniami.
Kategoria:Twierdzenia o wielomianach H