Schemat Hornera

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

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

   w ( x ) = w 0 + w 1 x + w 2 x 2 + … + w n − 1 x n − 1 + w n x n ; {\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 x − a . {\displaystyle x-a.} Schemat Hornera to znajdowanie wielomianu q {\displaystyle q} i liczby r {\displaystyle r} w tożsamości^[1]:

   w ( x ) = q ( x ) ( x − a ) + r . {\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 3 x − 6 {\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 4 x 2 − 1. {\displaystyle 4x^{2}-1.} Schemat Hornera obliczania wartości wielomianu uogólniono na wielomiany wielu zmiennych^[4].

Jeśli dany jest wielomian w ( x ) = w 0 + w 1 x + w 2 x 2 + … + w n − 1 x n − 1 + w n x n , {\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 x {\displaystyle x} bezpośrednio z podanego wzoru, należy wykonać:

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

1 + 2 + 3 + … + ( n − 1 ) + n = n ( n + 1 ) 2 . {\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:

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

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

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

w ( x ) = x ( 4 x 2 − 5 x + 7 ) − 20 = = x ( x ( 4 x − 5 ) + 7 ) − 20 , w ( 2 ) = 2 ( 2 ( 4 ⋅ 2 − 5 ) + 7 ) − 20 = = 2 ( 2 ( 8 − 5 ) + 7 ) − 20 = = 2 ( 2 ⋅ 3 + 7 ) − 20 = = 2 ( 6 + 7 ) − 20 = = 2 ⋅ 13 − 20 = = 26 − 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

Dany wielomian

w ( x ) = a 0 + a 1 x + a 2 x 2 + a 3 x 3 + … + a n − 2 x n − 2 + a n − 1 x n − 1 + a n x n {\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

w ( x ) = a 0 + x ( a 1 + x ( a 2 + … + x ( a n − 2 + x ( a n − 1 + x a n ) ) … ) ) . {\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:

b n := a n , b n − 1 := a n − 1 + b n x , b n − 2 := a n − 2 + b n − 1 x … b 0 := a 0 + b 1 x . {\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 b 0 {\displaystyle b_{0}} będzie równe w ( x ) {\displaystyle w(x)} ^[5]. Rzeczywiście, jeśli podstawimy kolejno b n ,   … ,   b 0 {\displaystyle b_{n},\ \dots ,\ b_{0}} do tego wielomianu, otrzymamy

w ( x ) = a 0 + x ( a 1 + x ( a 2 + … x ( a n − 2 + x ( a n − 1 + b n x ) ) ) ) = = a 0 + x ( a 1 + x ( a 2 + … x ( a n − 2 + b n − 1 x ) ) ) = … = a 0 + x b 1 = = b 0 . {\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}}}

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

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

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

w ( x ) = ( x − a ) B ( x ) + r , w ( x ) = a n x n + a n − 1 x n − 1 + … + a 1 x + a 0 = = ( x − a ) ( b n − 1 x n − 1 + b n − 2 x n − 2 + … + b 1 x + b 0 ) + r . {\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]:

b n − 1 = a n b n − 2 = a n − 1 + a b n − 1 , b n − 3 = a n − 2 + a b n − 2 , … , b 0 = a 1 + a b 1 , r = a 0 + a b 0 . {\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}}}

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

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

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

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

w ( x ) = ( x − 2 ) ( 5 x 2 + 3 x + 9 ) + 15. {\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ę w ( 2 ) . {\displaystyle w(2).}

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

w ( x ) = ( x − a ) B ( x ) + r = = ( x − a ) ( ( x − a ) B 1 ( x ) + r 1 ) + r = = ( x − a ) 2 B 1 ( x ) + r 1 ( x − a ) + r = = ( x − a ) 2 ( ( x − a ) B 2 ( x ) + r 2 ) + r 1 ( x − a ) + r = = ( x − a ) 3 B 2 ( x ) + r 2 ( x − a ) 2 + r 1 ( x − a ) + r , … w ( x ) = r n ( x − a ) n + r n − 1 ( x − a ) n − 1 + … + r 2 ( x − a ) 2 + r 1 ( x − a ) + r . {\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 w ( x ) {\displaystyle w(x)} względem potęg dwumianu x − a . {\displaystyle x-a.} Taki rozkład można otrzymać, stosując schemat Hornera kolejno do w ( x ) ,   B ( x ) ,   B 1 ( x ) ,   … ,   B n − 1 ( x ) {\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).

Dany wielomian

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

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

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

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

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

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

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

Algorytm Hornera dla obliczania początkowych m ⩽ n {\displaystyle m\leqslant n} elementów w ( j ) ( x ) j ! {\displaystyle {\frac {w^{(j)}(x)}{j!}}} wymaga ( m + 1 ) ( n − m n ) {\displaystyle (m+1)\left(n-{\frac {m}{n}}\right)} dodawań i mnożeń.

Schematy podane wyżej można uogólnić na przypadek abstrakcyjnego pierścienia wielomianów^{[potrzebny przypis]}. Niech K {\displaystyle K} będzie dowolnym ciałem, a K [ x ] {\displaystyle K[x]} będzie jego pierścieniem wielomianów. Jeśli

f ( x ) = a n x n + a n − 1 x n − 1 + … + a 1 x + a 0 ∈ K [ x ] , {\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

b n − 1 x n − 1 + … + b 1 x + b 0 , {\displaystyle b_{n-1}x^{n-1}+\ldots +b_{1}x+b_{0},}

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

b n − 1 = a n , b k = a k + 1 + c b k + 1 {\displaystyle b_{n-1}=a_{n},\;b_{k}=a_{k+1}+cb_{k+1}}

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

a 0 + a b 0 . {\displaystyle a_{0}+ab_{0}.}

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

• 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.

• 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.