Schemat Hornera

Schemat Hornera – wspólna nazwa dwóch algorytmów:

1. obliczania wartości dowolnego wielomianu o jednej zmiennej:

   ${\displaystyle w(x)=w_{0}+w_{1}x+w_{2}x^{2}+\ldots +w_{n-1}x^{n-1}+w_{n}x^{n};}$

2. dzielenia takiego wielomianu przez dwumian liniowy i moniczny, tj. postaci ${\displaystyle x-a}$ – znajdowania wielomianu ${\displaystyle q(x)}$ i liczby ${\displaystyle r}$ w tożsamości^[1]:

   ${\displaystyle w(x)=q(x)(x-a)+r.}$

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 ${\displaystyle 3x-6}$ 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 ${\displaystyle 4x^{2}-1.}$ Schemat Hornera obliczania wartości wielomianu uogólniono na wielomiany wielu zmiennych^[4].

Obliczanie wartości

Wstęp

Jeśli dany jest wielomian ${\displaystyle w(x)=w_{0}+w_{1}x+w_{2}x^{2}+\ldots +w_{n-1}x^{n-1}+w_{n}x^{n},}$ to obliczając jego wartość dla zadanego ${\displaystyle x}$ bezpośrednio z podanego wzoru, należy wykonać:

• ${\displaystyle n}$ dodawań;
• znaczącą liczbę mnożeń:

${\displaystyle 1+2+3+\ldots +(n-1)+n={\frac {n(n+1)}{2}}.}$

Wielomian ten można jednak przekształcić, korzystając z rozdzielności mnożenia względem dodawania:

${\displaystyle w(x)=w_{0}+x(w_{1}+x(w_{2}+\ldots +x(w_{n-1}+xw_{n})\ldots )).}$

Sprawia to, że wystarczy jedynie ${\displaystyle n}$ mnożeń i ${\displaystyle n}$ dodawań^[5].

Przykład

Obliczanie wartości ${\displaystyle w(2)}$ wielomianu opisanego wzorem ${\displaystyle w(x)=4x^{3}-5x^{2}+7x-20}$^[6]:

${\displaystyle {\begin{aligned}w(x)&=x(4x^{2}-5x+7)-20=\\&=x(x(4x-5)+7)-20,\\w(2)&=2(2(4\cdot 2-5)+7)-20=\\&=2(2(8-5)+7)-20=\\&=2(2\cdot 3+7)-20=\\&=2(6+7)-20=\\&=2\cdot 13-20=\\&=26-20=6.\\\end{aligned}}}$

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

Dany wielomian

${\displaystyle w(x)=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\ldots +a_{n-2}\,x^{n-2}+a_{n-1}x^{n-1}+a_{n}x^{n}}$

przekształcamy do postaci

${\displaystyle w(x)=a_{0}+x(a_{1}+x(a_{2}+\ldots +x(a_{n-2}+x(a_{n-1}+xa_{n}))\ldots )).}$

Następnie definiujemy:

${\displaystyle {\begin{aligned}b_{n}&:=a_{n},\\b_{n-1}&:=a_{n-1}+b_{n}x,\\b_{n-2}&:=a_{n-2}+b_{n-1}x\\&\;\dots \\b_{0}&:=a_{0}+b_{1}x.\end{aligned}}}$

Tak otrzymane ${\displaystyle b_{0}}$ będzie równe ${\displaystyle w(x)}$^[5]. Rzeczywiście, jeśli podstawimy kolejno ${\displaystyle b_{n},\ \dots ,\ b_{0}}$ do tego wielomianu, otrzymamy

${\displaystyle {\begin{aligned}w(x)&=a_{0}+x(a_{1}+x(a_{2}+\ldots x(a_{n-2}+x(a_{n-1}+b_{n}x))))=\\&=a_{0}+x(a_{1}+x(a_{2}+\ldots x(a_{n-2}+b_{n-1}x)))=\\&\dots \\&=a_{0}+xb_{1}=\\&=b_{0}.\end{aligned}}}$

Dzielenie wielomianu przez dwumian

Schemat

Dowolny wielomian ${\displaystyle w}$ można podzielić z resztą przez dwumian ${\displaystyle x-a}$. Innymi słowy, jeśli:

${\displaystyle w(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\ldots +a_{1}x+a_{0},}$

to istnieją wielomian ${\displaystyle B}$ stopnia ${\displaystyle n-1}$ i liczba ${\displaystyle r}$ takie, że:

${\displaystyle {\begin{aligned}w(x)&=(x-a)B(x)+r,\\w(x)&=a_{n}x^{n}+a_{n-1}x^{n-1}+\ldots +a_{1}x+a_{0}=\\&=(x-a)(b_{n-1}x^{n-1}+b_{n-2}x^{n-2}+\ldots +b_{1}x+b_{0})+r.\end{aligned}}}$

Po wymnożeniu i porównaniu współczynników obu stron mamy^[7]:

${\displaystyle {\begin{aligned}b_{n-1}&=a_{n}\\b_{n-2}&=a_{n-1}+ab_{n-1},\\b_{n-3}&=a_{n-2}+ab_{n-2},\\&\dots ,\\b_{0}&=a_{1}+ab_{1},\\r&=a_{0}+ab_{0}.\end{aligned}}}$

Przykład

Niech ${\displaystyle w(x)=5x^{3}-7x^{2}+3x-3}$. Dzielenie tego wielomianu przez dwumian ${\displaystyle x-2}$ można zapisać w tabeli:

• pierwszy wiersz zawiera wszystkie – również zerowe – współczynniki wielomianu ${\displaystyle w;}$
• dolny wiersz zawiera wyniki obliczeń według reguły danej wyżej:

współczynniki licznika ${\displaystyle w}$	5	−7	3	−3
iloczyny		10	6	18
współczynniki ilorazu ${\displaystyle B}$	5	3	9	15

Prawie wszystkie elementy dolnego wiersza – oprócz ostatniego – to współczynniki wielomianu ${\displaystyle B,}$ a ostatni element, czyli skrajnie prawy, to reszta z dzielenia^[8]:

${\displaystyle w(x)=(x-2)(5x^{2}+3x+9)+15.}$

Przy okazji można zauważyć, że jest to dowód wniosku z twierdzenia Bézouta o tym, że reszta r równa się ${\displaystyle w(2).}$

Inne zastosowania

Rozkład względem potęg dwumianu

Rozpatrzmy, co będzie, jeżeli wielomian ${\displaystyle w(x)}$ będziemy dzielić wielokrotnie przez ${\displaystyle x-a,}$ otrzymując za każdym razem pewien wielomian ${\displaystyle B_{j}}$ i resztę ${\displaystyle r_{j}{:}}$

${\displaystyle {\begin{aligned}w(x)&=(x-a)B(x)+r=\\&=(x-a){\Bigl (}(x-a)B_{1}(x)+r_{1}{\Bigr )}+r=\\&=(x-a)^{2}B_{1}(x)+r_{1}(x-a)+r=\\&=(x-a)^{2}{\Bigl (}(x-a)B_{2}(x)+r_{2}{\Bigr )}+r_{1}(x-a)+r=\\&=(x-a)^{3}B_{2}(x)+r_{2}(x-a)^{2}+r_{1}(x-a)+r,\\&\dots \\w(x)&=r_{n}(x-a)^{n}+r_{n-1}(x-a)^{n-1}+\ldots +r_{2}(x-a)^{2}+r_{1}(x-a)+r.\end{aligned}}}$

Otrzymaliśmy więc rozkład wielomianu ${\displaystyle w(x)}$ względem potęg dwumianu ${\displaystyle x-a.}$ Taki rozkład można otrzymać, stosując schemat Hornera kolejno do ${\displaystyle w(x),\ B(x),\ B_{1}(x),\ \dots ,\ B_{n-1}(x)}$ 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

${\displaystyle w(x)=(x-\alpha )^{j}v(x)+r(x),}$

gdzie ${\displaystyle r(x)}$ jest stopnia mniejszego niż ${\displaystyle j.}$ Po ${\displaystyle j}$-krotnym zróżniczkowaniu i podstawieniu ${\displaystyle \alpha {:}}$

${\displaystyle w^{(j)}(\alpha )=j!v(\alpha ).}$

Z tego wynika, że ${\displaystyle v(\alpha )}$ jest ${\displaystyle j}$-tą znormalizowaną pochodną wielomianu ${\displaystyle W(x)}$ w punkcie ${\displaystyle \alpha {:}}$

${\displaystyle v(\alpha )={\frac {w^{(j)}(\alpha )}{j!}}.}$

Współczynniki wielomianu ${\displaystyle v}$ i wartości ${\displaystyle v}$ w punkcie ${\displaystyle \alpha }$ obliczamy dzieląc wielomian ${\displaystyle W}$ i kolejno otrzymywane ilorazy przez dwumian ${\displaystyle x-\alpha {:}}$

${\displaystyle {\frac {w(x)}{(x-\alpha )^{k}}}\quad {}}$ dla ${\displaystyle k=1,\dots ,j-1.}$

Algorytm Hornera dla obliczania początkowych ${\displaystyle m\leqslant n}$ elementów ${\displaystyle {\frac {w^{(j)}(x)}{j!}}}$ wymaga ${\displaystyle (m+1)\left(n-{\frac {m}{n}}\right)}$ 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 ${\displaystyle K}$ będzie dowolnym ciałem, a ${\displaystyle K[x]}$ będzie jego pierścieniem wielomianów. Jeśli

${\displaystyle f(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\ldots +a_{1}x+a_{0}\in K[x],}$

to współczynniki ilorazu

${\displaystyle b_{n-1}x^{n-1}+\ldots +b_{1}x+b_{0},}$

otrzymanego z dzielenia ${\displaystyle f}$ przez ${\displaystyle x-a,\;a\in K}$ spełniają zależność:

${\displaystyle b_{n-1}=a_{n},\;b_{k}=a_{k+1}+cb_{k+1}}$

dla ${\displaystyle k=0,\;1,\;\dots ,\;n-2;}$ reszta z tego dzielenia – równa ${\displaystyle f(a)}$ – wynosi

${\displaystyle a_{0}+ab_{0}.}$

Zobacz też

• złożoność obliczeniowa
• algorytm Clenshawa

Przypisy

1. schemat Hornera, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2023-04-24].
2. 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. Fortuna, Macukow i Wąsowski 1993 ↓, s. 17.
6. 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

• ZenonZ. Fortuna ZenonZ., BohdanB. Macukow BohdanB., JanuszJ. Wąsowski JanuszJ., 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

• 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 (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-05-17].
• Scott Congreve, Horner’s Scheme (ang.), Uniwersytet Karola w Pradze, mff.cuni.cz [dostęp 2024-05-22] – krótki wykład z ćwiczeniami.

Encyklopedie internetowe (algorytm):

• Britannica: topic/Horners-method
• DSDE: Horners_skema