Schemat Hornera jako jeden z przykładów algorytmu klasycznego

Schemat Hornera jest algorytmem służącym do szybkiego obliczania wartości wielomianu.

Weźmy funkcję kwadratową: y=a0x2+a1x+a2. Jest ona wielomianem stopnia drugiego o współczynnikach a0, a1, a2 (ao jest różne od zera). Zwykle, gdy chcemy obliczyć jego wartość wykonujemy trzy działania mnożenia i dwa dodawania.
Natomiast gdy wielomian uporządkujemy w ten sposób, że zgrupujemy dwa pierwsze wyrazy i wyciągniemy wspólny czynnik x przed nawias, to otrzymamy wielomian postaci:
Y=(a0x+a1)x+a2, co w praktyce dla obliczenia jego wartości wymaga wykonania dwóch działań mnożenia i dwóch dodawania.
Trzeciego stopnia: W(x)= a0x3+a1x2+a2x+a3 po rozpisaniu według powyżej zasady przyjmie postać: W(x)=(a0x+a1)x+a2)x+a3 , a więc do obliczenia jego wartości należy wykonać trzy działania mnożenia i trzy dodawania.
Uogólniając, w przypadku wielomianu n-tego stopnia, który ma ogólna postać:
W(x)=a0xn+a1xn-1+a2xn-2+...+an-1x+an dla n>=0 (***)
można go uporządkować następująco:
W(x)=(...((a0x+a1)x+a2)x+a3)x+...+an-1x+an
W celu obliczenia wartości wielomianu należałoby wykonać obliczenia zgodnie ze znaną zasadą kolejności wykonywania działań, poczynając od najbardziej zagnieżdżonych nawiasów.
Za początkową wartość wielomianu należy przyjąć wartość współczynnika ao przy najwyższej potędze. Za każdym razem należy aktualną wartość wielomianu pomnożyć przez x i dodać kolejny współczynnik. ALGORYTM ten został nazwany SCHEMATEM HORNERA.

W(x)= ao-początkowa wartośc wielomianu
W(x)=W(x)x+ai gdzie i=1,2,3,...,n (czynnik powtarzający się-iteracja)
Przy obliczaniu wartości wielomianu n-tego stopnia za pomocą schematu Hornera należy więc wykonać n mnożeń i n dodawań. Korzystając ze schematu Hornera przyspieszamy swoje obliczenia, aniżeli korzystalibyśmy z wzoru (***)


Ćw.1
Rozpisz wielomian z zastosowaniem schematu Hornera, a następnie dokonaj sprawdzenia wyników po prawej i lewej stronie:
a) y= 3x6+4x5+6x4+9x3+10x2+x+1
L=(...(3x+4)x+6)x+9)x+10)x+1)x+1
Spr.
P= (...(3x2+4x+6)x+9)x+10)x+1)x+1=(...(3x3+4x2+6x+9)x+10)x+1)x+1=
=((3x4+4x3+6x2+9x+10)x+1)x+1)=((3x5+4x4+6x3+9x2+10x+1)x+1=
=3x6+4x5+6x4+9x3+10x2+x+1+L c.n.p
b) y= 7x7+5x4+4x2+3x+10=7x7+0x6+0x5+ 5x4+0x3 +4x2+3x+10
L= (...(7x+0)x+0)x+5)x+0)x+4)x+3)x+10=(...(7x)x)x+5)x)x+4)x+3)x+10
Spr.
P=(...(7x3+5)x)x+4)x+3)x+10=(...(7x4+5x)x+4)x+3)x+10=
=(7x5+5x2+4)x+3)x+10=7x6+5x3+4x+3)x+10=7x7+5x4+4x3+3x+10=L c.n.p

Obliczanie wartości wielomianu:
Mamy wielomian: W(x)=3x4+6x2+x+12
Oblicz wartość wielomianu dla x=1
W(1)=3(1)4+6(1)2+1+12=22
Ćw2.
Jak zatem obliczyć wartość wielomianu korzystając ze schematu Hornera?
Stwórz algorytm, który obliczałby wartość wielomianu n –tego stopnia wyłącznie przy zmianie współczynników oraz dla dowolnego argumentu x?

y:=ao
y:=yx+a1
y:=yx+a2
y:=yx+a3
...
y:=yx+an-1
y:=yx+an

Uogólniając można to zapisać w jednolity sposób, oprócz pierwszego wiersza:
y:=ao
y:=yx+ai dla i=1,2,3,...,n

Rozwiązanie można prześledzić na podstawie wielomianu:
Y=3x4+6x2+x+12 dla x=1
y:=ao=3
y:=3*1+6=9
y:=9*1+1=10
y:=10+12=22 c.n.p