Schemat Hornera – wspólna nazwa dwóch algorytmów:
- 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};}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5df66b80d516752e87707f6a25153901811260d5)
- dzielenia takiego wielomianu przez dwumian liniowy i moniczny, tj. postaci
– znajdowania wielomianu
i liczby
w tożsamości[1]: ![{\displaystyle w(x)=q(x)(x-a)+r.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7379a02337025de428c8d1e2f2bf4d80928d91d5)
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
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ń:
![{\displaystyle 1+2+3+\ldots +(n-1)+n={\frac {n(n+1)}{2}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c7af2ccfde1a864b2abc3dbece848f1919d18694)
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 )).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fc013b15598dc907fe8fc6b93e2c7cef92f2e510)
Sprawia to, że wystarczy jedynie
mnożeń i
dodawań[5].
Przykład
Obliczanie wartości
wielomianu opisanego wzorem
[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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e259f73152ee8135aa7251a41cc21729cfe6111c)
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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eedd4f4c7fa8e534db64e6f4ccffed77b8b8215b)
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 )).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/185db4c1fe153a4a913b3b22960cc4658bc9e726)
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a1e8a4965e6f2661feff51a16cf1d00f015f9832)
Tak otrzymane
będzie równe
[5]. Rzeczywiście, jeśli podstawimy kolejno
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4ecb4f2f5f580020739baa577e5ab729cfb2fd85)
Dzielenie wielomianu przez dwumian
Schemat
Dowolny wielomian
można podzielić z resztą przez dwumian
. Innymi słowy, jeśli:
![{\displaystyle w(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\ldots +a_{1}x+a_{0},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5765a7d12a0ac95f38df9242e72db8cf8e6c781b)
to istnieją wielomian
stopnia
i liczba
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/11e20229733cf89b86dd3e8f1164645cc05caaac)
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6197ed4865855ec6d4e4ae1f1341706360493214)
Przykład
Niech
. Dzielenie tego wielomianu przez dwumian
można zapisać w tabeli:
- pierwszy wiersz zawiera wszystkie – również zerowe – współczynniki wielomianu
![{\displaystyle w;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e82fb67b014735ea5887724550164a6cd196fbb4)
- 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
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ę
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d36b22cfc722967c251b2ef35883faf4306364c4)
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
![{\displaystyle w(x)=(x-\alpha )^{j}v(x)+r(x),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/46c9b978c3f63f0eba9b9b0b4a5d13836865851e)
gdzie
jest stopnia mniejszego niż
Po
-krotnym zróżniczkowaniu i podstawieniu
![{\displaystyle w^{(j)}(\alpha )=j!v(\alpha ).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4b5d9f997c88cd862e21670ab6698fc25186de56)
Z tego wynika, że
jest
-tą znormalizowaną pochodną wielomianu
w punkcie
![{\displaystyle v(\alpha )={\frac {w^{(j)}(\alpha )}{j!}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2d60f478e4f19ea7de03d9da4dabb4cc68d51167)
Współczynniki wielomianu
i wartości
w punkcie
obliczamy dzieląc wielomian
i kolejno otrzymywane ilorazy przez dwumian
dla ![{\displaystyle k=1,\dots ,j-1.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/81305686466456f5474d187aebef0842d9da6da5)
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[potrzebny przypis]. Niech
będzie dowolnym ciałem, a
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],}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5a00709b0952b44d4d13429d272737071c66520b)
to współczynniki ilorazu
![{\displaystyle b_{n-1}x^{n-1}+\ldots +b_{1}x+b_{0},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/883e5e937570b66bf750d309cee654b9c0b13694)
otrzymanego z dzielenia
przez
spełniają zależność:
![{\displaystyle b_{n-1}=a_{n},\;b_{k}=a_{k+1}+cb_{k+1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dd17ca330e89f6a0ec858df35b5fb575ea1c0cba)
dla
reszta z tego dzielenia – równa
– wynosi
![{\displaystyle a_{0}+ab_{0}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b973dbcda867b2e33236031fcd109ad30fafde1e)
Zobacz też
Przypisy
- ↑ a b schemat Hornera, [w:] Encyklopedia PWN [dostęp 2023-04-24] .
- ↑ a b
John J. O'Connor; Edmund F. Robertson: Schemat Hornera w MacTutor History of Mathematics archive (ang.) [dostęp 2024-05-22]. - ↑
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]. - ↑
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]. - ↑ a b Fortuna, Macukow i Wąsowski 1993 ↓, s. 17.
- ↑ a b Nowa Era 2022 ↓, s. 110.
- ↑
Michał Niedźwiedź, Schemat Hornera, Zintegrowana Platforma Edukacyjna, zpe.gov.pl [dostęp 2024-05-22]. - ↑ 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.