OBLICZANIE WARTOŚCI WIELOMIANU
1. Metoda tradycyjna- długi czas obliczeń.
W
n
(x) =a
n
x
n
+ a
n-1
x
n-1
+ ...+ a
2
x
2
+ a
1
x + a
0
ilość operacji = n dodawań +
2
)
1
(
+
n
n
mnożeń
np.
Wielomian 2 stopnia.
W
2
(x) = a
2
x
2
+ a
1
x + a
0
= a
2
·x·x + a
1
·x + a
0
ilość operacji = 2 dodawania +
2
)
1
2
(
2
+
mnożeń => 2 + 3 = 5
2. Metoda Hornera- krótki czas obliczeń.
Wielomian zapisany w postaci:
W
n
(x) =a
n
x
n
+ a
n-1
x
n-1
+ ...+ a
2
x
2
+ a
1
x + a
0
możemy zapisać w następującej postaci:
W
n
(x) = (...((a
n
x + a
n-1
)x + a
n-2
)x + ... + a
1
)x + a
0
ilość operacji = n dodawań + n mnożeń
Schemat Hornera:
b
0
= a
n
b
1
= b
0
x + a
n-1
b
2
= b
1
x + a
n-2
b
n-1
= b
n-2
x + a
1
b
n
= b
n-1
x + a
0
W(x) = b
n
np.
Wielomian 2 stopnia.
W
2
(x) = a
2
x
2
+ a
1
x + a
0
= ((a
2
·x + a
1
)·x + a
0
ilość operacji = 2 dodawania + 2 mnożenia = 4
Porównanie ilości elementarnych operacji arytmetycznych koniecznych do wyznaczenia
wartości wielomianu koniecznych do wykonania w metodzie tradycyjnej i metodzie Hornera.
n = 5
metoda tradycyjna - ilość operacji = 20
metoda Hornera - ilość operacji = 10
b
0
b
1
b
2
b
n-1
b
n