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:

…

(**)

Schemat Hornera

- 2 -

i odpowiadający jej sposób obliczania wartości dla argumentu z, zwany schematem Hornera:

, 1, 2, … ,

(***)

Liczba działań arytmetycznych potrzebnych do obliczenia wartości wielomianu za pomocą schematu

Hornera wynosi n mnożeń i n dodawań, a więc jest o n-1 mnożeń mniejsza niż w przypadku stosowania

metody bezpośredniej wynikającej z postaci (*).

Wzory (***) są przykładem zależności rekurencyjnej, którą tworzą współczynniki b: kolejny

współczynnik

oblicza się korzystając z wartości poprzedniego współczynnika

, a współczynnik

jest równy

.

Wielkość

występujące we wzorach (***) mają bardzo ciekawą interpretację. Wyrazy

są

współczynnikami ilorazu

otrzymanego z dzielenia wielomianu

przez dwumian

, a

jest resztą z tego dzielenia.