Schemat Hornera
- 1 -
Jednym z często rozwiązywanych zadań numerycznych jest obliczanie wartości wielomianu.
Wynika to z waŜnego faktu matematycznego, zgodnie, z którym kaŜdą funkcję ciągłą, nawet o najbardziej
skomplikowanej postaci, moŜna lokalnie zastąpić wielomianem, którego postać zaleŜy od tego, jaką
chcemy uzyskać dokładność obliczeń i oczywiście od samej funkcji. Dla przykładu, wartości niektórych
standardowych funkcji w języku Pascal są obliczane, jako wartości odpowiednio dobranych wielomianów
lub ilorazów wielomianów.
Naszym zadaniem jest obliczenie wartości wielomianu:
(*)
dla ustalonej wartości argumentów x=z.
Wyznaczmy najpierw liczbę dodawań i mnoŜeń potrzebnych do obliczenia
ze wzoru (*).
Dla obliczenia kolejnych potęg z
2
, z
3
, …, z
n
naleŜy wykonać n-1 mnoŜeń. Następnie potrzeba n mnoŜeń
by obliczyć wartość jednomianów
dla i = 0, 1, …, n-1 i n dodawań, aby je zsumować. Zatem
obliczenie wartości wielomianu ze wzoru (*) wymaga wykonania 2n-1 mnoŜeń i n dodawań.
Wielomian (*) moŜna przedstawić w innej postaci sugerując odmienny sposób liczenia jego
wartości. PokaŜemy to najpierw na przykładzie wielomianu stopnia 3:
który moŜna zastąpić następująco:
Postać ta podpowiada następujący sposób obliczania wartości w
3
(z):
Szukaną wartością wielomianu jest
. ZauwaŜmy, Ŝe z wyjątkiem pierwszego kroku w kaŜdym
następnym są wykonywane te same działania: mnoŜenie poprzedniej wartości b przez z i dodanie do tego
iloczynu kolejnego współczynnika wielomianu. MoŜemy uogólnić tę obserwację i zastosować do
wielomianu dowolnego stopnia. Otrzymamy wtedy następującą postać wielomianu:
…
(**)
