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+\dots +w_{n-1}{x}^{n-1}+w_n{x}^n;$

2. dzielenia takiego wielomianu przez dwumian liniowy i moniczny, tj. postaci $x-a$ – znajdowania wielomianu $q(x)$ i liczby $r$ w tożsamości:

   $w(x)=q(x)(x-a)+r.$

Schemat Hornera wykorzystuje minimalną liczbę mnożeńSzablon:Fakt. 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. Znali go już jednak matematycy chińscy w XIII wieku, a na początku XIX wieku także Paolo Ruffini. Nazwa upamiętniająca Hornera upowszechniła się jeszcze w XIX wieku, do czego przyczynił się Augustus De Morgan.

Dla dzielenia wielomianu przez dwumian $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 $4x^2-1.$ Schemat Hornera obliczania wartości wielomianu uogólniono na wielomiany wielu zmiennych.

Obliczanie wartości

Wstęp

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

• $n$ dodawań;
• znaczącą liczbę mnożeń:

$1+2+3+\dots +(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+\dots +x(w_{n-1}+x{w}_n)\dots )).$

Sprawia to, że wystarczy jedynie $n$ mnożeń i $n$ dodawańSzablon:Odn.

Przykład

Obliczanie wartości $w(2)$ wielomianu opisanego wzorem $w(x)=4x^3-5x^2+7x-20$Szablon:Odn:

$\begin{array}{cc}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{array}$

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ściSzablon:Odn:

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

$w(x)=a_0+a_{1}x+a_2{x}^2+a_3{x}^3+\dots +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+\dots +x(a_{n-2}+x(a_{n-1}+x{a}_n))\dots )).$

Następnie definiujemy:

$\begin{array}{cc}{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{array}$

Tak otrzymane $b_0$ będzie równe $w(x)$Szablon:Odn. Rzeczywiście, jeśli podstawimy kolejno $b_n,\dots ,b_0$ do tego wielomianu, otrzymamy

$\begin{array}{cc}w(x)& =a_0+x(a_1+x(a_2+\dots x(a_{n-2}+x(a_{n-1}+b_{n}x))))=\\ & =a_0+x(a_1+x(a_2+\dots x(a_{n-2}+b_{n-1}x)))=\\ & \dots \\ & =a_0+x{b}_1=\\ & =b_0.\end{array}$

Dzielenie wielomianu przez dwumian

Schemat

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

$w(x)=a_n{x}^n+a_{n-1}{x}^{n-1}+\dots +a_{1}x+a_0,$

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

$\begin{array}{cc}w(x)& =(x-a)B(x)+r,\\ w(x)& =a_n{x}^n+a_{n-1}{x}^{n-1}+\dots +a_{1}x+a_0=\\ & =(x-a)(b_{n-1}{x}^{n-1}+b_{n-2}{x}^{n-2}+\dots +b_{1}x+b_0)+r.\end{array}$

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

$\begin{array}{cc}{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},\\ & \dots ,\\ b_0& =a_1+a{b}_1,\\ r& =a_0+a{b}_0.\end{array}$

Przykład

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

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

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

Prawie wszystkie elementy dolnego wiersza – oprócz ostatniego – to współczynniki wielomianu $B,$ a ostatni element, czyli skrajnie prawy, to reszta z dzieleniaSzablon:Odn:

$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).$

Inne zastosowania

Rozkład względem potęg dwumianu

Rozpatrzmy, co będzie, jeżeli wielomian $w(x)$ będziemy dzielić wielokrotnie przez $x-a,$ otrzymując za każdym razem pewien wielomian $B_j$ i resztę $r_j:$

$\begin{array}{cc}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,\\ & \dots \\ w(x)& =r_n(x-a{)}^n+r_{n-1}(x-a{)}^{n-1}+\dots +r_2(x-a{)}^2+r_1(x-a)+r.\end{array}$

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

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

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

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

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

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

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

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

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

$f(x)=a_n{x}^n+a_{n-1}{x}^{n-1}+\dots +a_{1}x+a_0\in K[x],$

to współczynniki ilorazu

$b_{n-1}{x}^{n-1}+\dots +b_{1}x+b_0,$

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

$b_{n-1}=a_n,b_k=a_{k+1}+c{b}_{k+1}$

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

$a_0+a{b}_0.$

Zobacz też

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

Bibliografia

• Szablon:Cytuj
• Szablon:Cytuj książkę

Linki zewnętrzne

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