Schemat Hornera

algorytm obliczania wartości wielomianu i dzielenia go przez moniczny dwumian liniowy

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

edytuj

Wstęp

edytuj

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

edytuj

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

Algorytm

edytuj

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

edytuj

Schemat

edytuj

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

edytuj

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

edytuj

Rozkład względem potęg dwumianu

edytuj

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

edytuj

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

edytuj

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ż

edytuj

Przypisy

edytuj
  1. a b schemat Hornera, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2023-04-24].
  2. a b   John J. O’Connor; Edmund F. Robertson: Schemat Hornera w MacTutor History of Mathematics archive (ang.) [dostęp 2024-05-22].
  3.   Jeff Miller, Horner's method [w:] Earliest Known Uses of Some of the Words of Mathematics (H) (ang.), MacTutor History of Mathematics archive, University of St Andrews, mathshistory.st-andrews.ac.uk [dostęp 2024-05-22].
  4.   Juna Manuel Peña, Thomas Sauer, On the multivariate Horner scheme (ang.), SIAM Journal on Numerical Analysis 37(4), czerwiec 1998, ResearchGate, researchgate.net [dostęp 2024-05-22].
  5. a b Fortuna, Macukow i Wąsowski 1993 ↓, s. 17.
  6. a b Nowa Era 2022 ↓, s. 110.
  7.   Michał Niedźwiedź, Schemat Hornera, Zintegrowana Platforma Edukacyjna, zpe.gov.pl [dostęp 2024-05-22].
  8. Nowa Era 2022 ↓, s. 111.

Bibliografia

edytuj
  • Zenon Fortuna, Bohdan Macukow, Janusz Wąsowski, 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.

Linki zewnętrzne

edytuj