Loading AI tools
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:
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].
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].
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]:
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 |
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
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]:
Niech . Dzielenie tego wielomianu przez dwumian można zapisać w tabeli:
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ę
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).
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
Algorytm Hornera dla obliczania początkowych elementów wymaga dodawań i mnożeń.
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
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.