Schemat Hornera

Schemat Hornera

Schemat Hornera – sposób obliczenia wartości wielomianu dla danej wartości argumentu wykorzystujący minimalną liczbę mnożeń, również algorytm dzielenia wielomianu W(x) przez dwumian x − c. Wiązany z nazwiskiem Hornera, był jednak znany już Newtonowi, Ruffiniemu i matematykom chińskim w XII wieku. Przy dzieleniu wielomianów schemat Hornera wolno stosować tylko jeżeli w dwumianie nie ma przy x żadnej potęgi lub liczby. Dla przykładu: przy dwumianie x − 5 wolno nam stosować schemat Hornera. Jednak przy dwumianie 4x² − 1 schematu Hornera stosować już nie wolno. Przy dwumianie 3x − 6 można stosować schemat Hornera, jeżeli najpierw podzielić przez 3 ten dwumian oraz wielomian Koncepcja

Jeśli dany jest wielomian , to dla obliczenia jego wartości dla zadanego x bezpośrednio z podanego wzoru należy wykonać 1 + 2 + 3 + ... + (n − 1) + n = n(n + 1) / 2 mnożeń oraz n dodawań. Tymczasem proste przekształcenie pokazuje, że wystarczy jedynie n mnożeń i n dodawań. Mnożenia są operacją czasochłonną i eliminacja zbędnych mnożeń jest jednym z podstawowych problemów optymalizacji algorytmów.

Dla przykładu, niech:

W(x) = 2x⁴ − 5x² + 4x + 1; chcemy obliczyć wartość tego wielomianu dla x = 3 / 2.

Zapisujemy:

podstawiamy

Warto dla porównania obliczyć tę wartość metodą "tradycyjną" nie korzystając z kalkulatora.

Algorytm Hornera dla obliczenia wartości wielomianu

Dany wielomian

Przekształcamy do postaci

Następnie definiujemy:

Tak otrzymane b₀ będzie równe W(x). Rzeczywiście, jeśli podstawimy kolejno do tego wielomianu, otrzymamy

Inne zastosowania

Dzielenie wielomianu przez dwumian

Schemat Hornera dzielenia wielomianu W(x) przez dwumian x–c oparty jest na podobnej zasadzie. Zauważmy, że jeśli : i W(x) = (x − c)B(x) + r, to z teorii wynika, że B(x) jest wielomianem stopnia n–1, a r jest liczbą. Jeżeli napiszemy:

to po wymnożeniu i porównaniu współczynników obu stron mamy:

b_n _{− 1} = a_n,

Dla przykładu, podzielmy ten sam wielomian W(x) = 2x⁴ − 5x² + 4x + 1 przez dwumian . Mamy tutaj . Obliczenia praktycznie jest przeprowadzać w tabeli: w jej pierwszym wierszu wypisujemy wszystkie, czyli również zerowe współczynniki wielomianu W(x), a w dolnym wpisujemy kolejno wyniki obliczeń według reguły danej wyżej:

2	0	-5	4	1
2

Elementy dolnego wiersza są współczynnikami wielomianu B(x), natomiast skrajny prawy element jest resztą z dzielenia.

Oprócz tego, z twierdzenia Bézouta wynika natychmiast, że ta reszta równa się jednocześnie co właśnie i było udowodniono wyżej przez inną metodę.

Rozkład względem potęg dwumianu

Rozpatrzmy, co będzie, jeżeli po zbadanemu wyżej dzieleniu wielomianu W(x) przez x − c znów podzielimy przez x − c otrzymany wielomian B(x) i będziemy kontynuować dalej analogicznie. Będziemy odpowiednio przekształcać dany wielomian W(x):

W(x) = (x − c)B(x) + r,

W(x) = (x − c)((x − c)B₁(x) + r₁) + r = (x − c)²B₁(x) + r₁(x − c) + r,

W(x) = (x − c)²((x − c)B₂(x) + r₂) + r₁(x − c) + r = (x − c)³B₂(x) + r₂(x − c)² + r₁(x − c) + r,

Otrzymaliśmy więc rozkład wielomianu W(x) względem potęg dwumianu x − c. Taki rozkład można przeprowadzić, 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ółczynnikem).