Temat 1
Obliczanie wielomianu metodą klasyczną i
metodą Hornera
Tomasz Walocha
Akademia Górniczo-Hutnicza w Krakowie
Kierunek Metalurgia
Wydział odlewnictwa
Rok I
Grupa VI
Spis treści
1. Metoda Hornera
2. Wykonywanie obliczeń metodą
klasyczną i Hornera
3. Przedstawienie różnicy czasu
wykonywania obliczeń obiema
metodami (tabelka)
4. Przedstawienie różnicy czasu
wykonywania obliczeń obiema
metodami (wykres)
5. Wnioski
1. Metoda Hornera
Metoda Hornera: Schemat Hornera  sposób obliczania wartości wielomianu dla danej
wartości argumentu wykorzystujący minimalną liczbę mnożeń, jest to również algorytm
dzielenia wielomianu W(x) przez dwumian x-C. Schemat ten wiązany jest z nazwiskiem
Hornera, był jednak już znany Newtonowi, Ruffiniemu i matematykom chińskim w XII
wieku.
Przy dzieleniu wielomianów schemat Hornera można stosować tylko wtedy gdy w dwumianie
nie ma przy x żadnej potęgi i współczynnika. Dla przykładu: dla dzielenia przez dwumian
x-5 można stosować schemat Hornera. Jednak dla dzielenia przez dwumian 4x2-1 schematu
Hornera stosować już nie wolno. Dla dzielenia wielomianu przez dwumian 3x-6 można
stosować schemat Hornera, jeżeli najpierw podzieli się dwumian i wielomian, przez 3.
2. Wykonywanie obliczeń metodą klasyczną i
Hornera
Metoda klasyczna:
W(x)= 2x2+3x-5 W(x)=5
W(5)=2*5*5+3*5-5
W(5)=60
Metoda hornera:
W(x)=(2x+3)x-5
W(5)=(2*5+3)5-5
W(5)=13*5-5
W(5)=60
Metoda klasyczna:
W(x)=3x3+4x2+3x+6 W(x)=3
W(3)=3*3*3+4*3*3+3*3+6
W(3)=81+36+9+6
W(3)=132
Metoda hornera:
W(x)=(3x2+4x+3)x+6
W(3)=((3x+4)x+3)x+6
W(3)=((3*3+4)3+3)3+6
W(3)=((9+4)3+3)3+6
W(3)=(13*3+3)3+6
W(3)=(39+3)3+6
W(3)=42*3+6
W(3)=126+6
W(3)=132
Metoda klasyczna:
W(x)=2x4+4x3+5x2+2x-4 W(x)=2
W(2)=2*2*2*2*2+4*2*2*2+5*2*2+2*2-4
W(2)=32+32+20+4-4
W(2)=84
Metoda Hornera:
W(x)=(2x3+4x2+5x+2)x-4
W(2)=((2x2+4x+5)x+2)x-4
W(2)=(((2x+4)x+5)x+2)x-4
W(2)=(((2*2+4)2+5)2+2)2-4
W(2)=((8*2+5)2+2)2-4
W(2)=(21*2+2)2-4
W(2)=44*2-4
W(2)=88-4
W(2)=84
Metoda klasyczna:
W(x)=3x5+2x4+3x3+5x2+2x-10 W(x)=1
W(1)=3*1+2*1+3*1+5*1+2*1-10
W(1)=3+2+3+5+2-10
W(1)=15-10
W(1)=5
Metoda Hornera:
W(x)=(3x4+2x3+3x2+5x+2)x-10
W(1)=((3x3+2x2+3x+5)x+2)x-10
W(1)=(((3x2+2x+3)x+5)x+2)x-10
W(1)=((((3x+2)x+3)x+5)x+2)x-10
W(1)=((((3*1+2)1+3)1+5)1+2)1-10
W(1)=(((5*1+3) 1+5)1+2)1-10
W(1)=((8*1+5)1+2)1-10
W(1)=13*1+2)1-10
W(1)=15*1-10
W(1)=5
Metoda klasyczna:
W(x)=2x6+3x5+4x4+2x3+3x2+5x-120 W(x)=2
W(2)=2*2*2*2*2*2*2+3*2*2*2*2*2+4*2*2*2*2+2*2*2*2+3*2*2+5*2-120
W(2)=128+96+64+16+12+10-120
W(2)=326-120
W(2)=206
Metoda hornera:
W(x)=(2x5+3x4+4x3+2x2+3x+5)x-120
W(2)=((2x4+3x3+4x2+2x+3)x+5)x-120
W(2)=(((2x3+3x2+4x+2)x+3)x+5)x-120
W(2)=((((2x2+3x+4)x+2)x+3)x+5)x-120
W(2)=(((((2x+3)x+4)x+2)x+3)x+5)x-120
W(2)=(((((2*2+3)2+4)2+2)2+3)2+5)2-120
W(2)=((((7*2+4)2+2)2+3)2+5)2-120
W(2)=(((18*2+2)2+3)2+5)2-120
W(2)=((38*2+3)2+5)2-120
W(2)=(79*2+5)2-120
W(2)=163*2-120
W(2)=206
3. Przedstawienie różnicy czasu wykonywania
obliczeo obiema metodami (tabelka)
Liczba 7-12 (9) Czas hornera Czas klasyczny
1000 0 1
10000 0 4
100000 6 45
1000000 59 447
10000000 589 4473
100000000 5885 44732
Liczba 15-19 (17) Czas hornera Czas klasyczny
1000 0 1
10000 1 14
100000 11 137
1000000 107 1374
10000000 1070 13742
100000000 10699 137420
Liczba 20-25 (22) Czas hornera Czas klasyczny
1000 0 3
10000 1 22
100000 14 221
1000000 137 2209
10000000 1372 22095
100000000 13725 220952
4. Przedstawienie różnicy czasu wykonywania
obliczeo obiema metodami (wykres)
Wykres liczb o potędze 9
50000
45000
40000
35000
30000
25000
Czas hornera
Czas klasyczny
20000
15000
10000
5000
0
1000 10000 100000 1000000 10000000 100000000
Wykres liczby o potędze 17
160000
140000
120000
100000
80000
Czas hornera
Czas klasyczny
60000
40000
20000
0
1000 10000 100000 1000000 10000000 10000000
Wykres liczby o potędze 22
250000
200000
150000
Czas hornera
Czas klasyczny
100000
50000
0
1000 10000 100000 1000000 10000000 100000000
5. Wnioski
Na podstawie zaobserwowanych wyników przedstawionych w tabelach oraz
wykresach możemy stwierdzid iż metoda hornera jest dużo szybsza i
skuteczniejsza od metody klasycznej. Przy porównaniu czasów wykonania
działania obiema metodami widzimy że metoda hornera jest przy dużych
liczbach nawet 12x szybsza od metody klasycznej a przy dokładniejszej
obserwacji wykresu widzimy ze przy liczbie 10000000 czas obliczeo metoda
klasyczna gwałtownie wzrasta i z większymi liczbami staje się coraz większy
Bibliografia:
www.wikipedia.pl
Doświadczenie przeprowadzono na programie:
TurboDelphii