Przeczytaj

Jak już wiemy, schemat HorneraWilliam George HornerHornera jest wykorzystywany do obliczania wartości wielomianówwielomianwielomianów. Wykorzystamy tę metodę w czasie bieżącej lekcji.

Za przykład posłuży nam wielomian trzeciego stopnia. Obliczymy jego wartość dla wybranych argumentów. Zrobimy to na dwa sposoby: najpierw metodą tradycyjną wykonamy wszystkie operacje, a następnie skorzystamy ze schematu Hornera. Ostatecznie porównamy ilości wykonywanych operacji.

Ogólna postać wielomianu trzeciego stopnia to:

W_{(x)} = a_{0} x^{3} + a_{1} x^{2} + a_{2} x + a_{3}

Możemy zapisać równanie obliczające jego wartość za pomocą wzoru:

$W_{(x)}=(a_0 ⋅ x ⋅ x ⋅ x)+(a_1 ⋅ x ⋅ x)+(a_2 ⋅ x)+a_3$

Ważne!

Wielomian, którego stopień jest równy n, składa się z n + 1 składników.

A oto przykładowy wielomian trzeciego stopnia:

W_{(X)} = 6 x^{3} + 8 x^{2} - 2 x + 23

Dla x = 2 jego wartość wynosi:

W_{(X = 2)} = 6 \cdot 2^{3} + 8 \cdot 2^{2} - 2 \cdot 2 + 23 = 48 + 32 - 4 + 23 = 99

Aby obliczyć wynik, trzeba sześć razy wykonać operację mnożenia oraz trzykrotnie operacje dodawania:

W_{(X = 2)} = 6 \cdot 2 \cdot 2 \cdot 2 + 8 \cdot 2 \cdot 2 - 2 \cdot 2 + 23 = 48 + 32 - 4 + 23 = 99

Przykład 1

Zapiszemy algorytm tradycyjny, dzięki któremu będziemy mogli obliczyć wartość takiego wielomianu. Ponieważ użyjemy pętli for x in range(n+1), której wartość zmiennej sterującej x zwiększa się od 0 do n, więc współczynniki podamy jako listę elementów w kolejności od najmniejszego do największego wykładnika potęgi (od aIndeks dolny 3 do aIndeks dolny 0).

wielomian_tradycyjnie(stopien, wspolczynniki, argument)
	wynik przypisz 0
	aktualny_stopien przypisz 0
    
	wykonaj stopien+1 razy
		do wynik dodaj wspolczynniki[aktualny_stopien] * (argument podniesiony do potegi aktualny_stopien)
		zwiększ aktualny_stopien o 1

	wypisz wynik

Zdefiniujmy funkcję, która wykorzystując ten algorytm obliczy wartość wielomianu. Współczynniki towarzyszące poszczególnym jednomianom (czyli czynniki aIndeks dolny n w wyrażeniach aIndeks dolny nxIndeks górny n) podamy w kolejności od najmniejszego do największego wykładnika potęgi (od aIndeks dolny 3 do aIndeks dolny 0):

def wielomian_iter(stopien, lista_wsp, argument):
	wynik = 0

	for _stopien in range(stopien + 1):
		wynik += lista_wsp[_stopien] * (argument ** _stopien)

	return f"Wynikiem dla argumentu {argument} jest wartość {wynik}"

# przykład wykonania
print(wielomian_iter(3, [23, -2, 8, 6], 7))
Wynikiem dla argumentu 7 jest wartość 2459

Przykład 2

Zmodyfikujmy zapisaną funkcję w taki sposób, by obliczyć, ile operacji podstawowych było niezbędnych podczas wyznaczania wartości wielomianu. Sprawdźmy, czy uzyskany wynik zgadza się z wartością obliczoną na początku lekcji (powinien on wynosić 9).

def wielomian_iter_licz(stopien, lista_wsp, argument):
	wynik = lista_wsp[0]
	ile_oblicz = 0

	for _stopien in range(1, stopien + 1):
		wynik += lista_wsp[_stopien] * (argument ** _stopien)
		ile_oblicz += _stopien # liczba mnożeń

        ile_oblicz += 1 # liczba dodawań
            
		return f"Aby obliczyć wielomian konieczne jest {ile_oblicz} operacji podstawowych."	

# przykład wykonania
print(wielomian_iter_licz(3, [23, -2, 8, 6], 7))
Aby obliczyć wielomian konieczne jest 9 operacji podstawowych.

Obliczanie wartości wielomianu z zastosowaniem schematu Hornera

Schemat Hornera optymalizuje ilość operacji arytmetycznych niezbędnych do obliczenia wartości wielomianu.

Wykorzystując go otrzymujemy wzór:

W_{(X)} = (\dots ((a_{0} x + a_{1}) x + a_{2}) x + \dots + a_{n - 1}) x + a_{n}

Kolejne współczynniki:

a_{0} \dots a_{n}

są mnożnikami potęg zmiennej x, zapisanymi od lewej do prawej strony wielomianu. Poszczególne wyrazy wielomianu (jednomiany) są zapisane od najwyższej potęgi zmiennej x do najniższej.

Po przekształceniu przykładowego wielomianu z wykorzystaniem schematu Hornera okazuje się, że w celu wyznaczenia wartości całego wyrażenia konieczne jest wykonanie trzech operacji mnożenia i trzech operacji dodawania:

W_{(X)} = ((6 x + 8) x - 2) x + 23

Przykład 3

Zapiszemy algorytm obliczania wartości wielomianu za pomocą wersji iteracyjnej schematu Hornera. W liście, która jest jednym z parametrów funkcji, współczynniki podajemy w kolejności od najmniejszego stopnia do największego, a przy niewystępujących potęgach w wielomianie uzupełniamy zerami.

wielomian_horner_iteracyjnie(stopien, wspolczynniki, argument)
	wynik przypisz wspolczynniki[stopien]

	wykonuj dopóki stopien > 0
		zmniejsz stopien o 1
		wynik przypisz wynik * argument + wspolczynniki[stopien]

	zwróć wynik

Zdefiniujmy funkcję, która wykorzystując ten algorytm pozwoli nam obliczyć wartość wielomianu. Stopień wielomianu to najwyższa potęga x'a w tym wielomianie. W liście, która jest jednym z parametrów, współczynniki przy niewystępujących potęgach w wielomianie uzupełniamy zerami. Wówczas możemy pominąć podawanie stopnia jako parametru funkcji, gdyż będziemy mogli obliczyć go ze wzoru stopien = liczba współczynników -1.

def horner_iter(wsp, x):
	"""Wersja iteracyjna algorytmu Hornera. Współczynniki w liście wsp podajemy od końca"""
	stopien = len(wsp) - 1
	wynik = wsp[stopien]

	while stopien > 0:
		stopien = stopien - 1
		wynik = wynik * x + wsp[stopien]

	return wynik

# przykładowe wykonanie
print(horner_iter([23, -2, 8, 6], 7))
2459

Możemy również sprawdzić, ile operacji podstawowych wykonujemy w tej funkcji:

def horner_iter_ilosc_oper(wsp, x):
	"""Wersja iteracyjna algorytmu Hornera. Współczynniki w liście wsp podajemy od końca"""
	stopien = len(wsp) - 1
	wynik = wsp[stopien]
	zlicz = 0 

	while stopien > 0:
		stopien = stopien - 1
		wynik = wynik * x + wsp[stopien]
		zlicz += 2 # 2 operacje podstawowe

	return wynik, zlicz

# przykładowe wykonanie
print(horner_iter([23, -2, 8, 6], 7))
(2459, 6)

Definiując funkcję rekurencyjną, będziemy musieli podać następujące dane wejściowe:

stopień wielomianu,
współczynniki kolejnych wyrazów wielomianu,
argument, dla którego obliczamy wartość wielomian.

Przykład 4

Wzór rekurencyjny obliczania wartości wielomianu za pomocą schematu Hornera możemy zapisać w następujący sposób:

W_{n} = {\begin{array}{lc} a_{0} & d l a n = 0 \\ W_{n - 1} (x) \cdot x + a_{n} & d l a n \geq 1 \end{array}

Zapiszemy algorytm rekurencyjny, który pozwala obliczyć wartość wielomianu z zastosowaniem schematu Hornera:

rek_horner(stopien, lista_wspolczynnikow, wartosc_argumentu)
	jesli stopien jest równy 0, zwróć lista_wspolczynnikow[0]
	w przeciwnym przypadku 
		zwróć (wartosc_argumentu 
		* rek_horner(stopien - 1, lista_wspolczynnikow, wartosc_argumentu) 
		+ lista_wspolczynnikow[stopien])

Zdefiniujmy funkcję, która wykorzystując algorytm rekurencyjny obliczy wartość wielomianu. Współczynniki towarzyszące poszczególnym jednomianom (czyli czynniki aIndeks dolny n w wyrażeniach aIndeks dolny nxIndeks górny n) podamy w kolejności od największego do najmniejszego wykładnika potęgi (od aIndeks dolny 0 do aIndeks dolny 3):

def rek_horner(stopien, lista_wsp, argument):
	if stopien == 0:
		return lista_wsp[stopien]
	else:
		return argument * rek_horner(stopien - 1, lista_wsp, argument) + lista_wsp[stopien]
    
# przykład wywołania
print(rek_horner(3, [6, 8, -2, 23], 7))
2459

Sprawdźmy, ile operacji podstawowych trzeba wykonać w celu obliczenia wartości wielomianu z zastosowaniem metody rekurencyjnej.

Ważne!

Funkcja rekurencyjna wywołuje wielokrotnie siebie samą; w celu sprawdzenia liczby wykonywanych przez nią operacji musimy posłużyć się zmienną, która istnieje w przestrzeni nazwprzestrzeń nazwprzestrzeni nazw poza funkcją. Do tego celu użyjemy zmiennej typu integer, który jest typem niezmiennymniezmiennaniezmiennym. Aby zmieniać wartość takiej zmiennej z wnętrza funkcji, musimy zadeklarować dostęp do niej za pomocą słowa kluczowego global. Dzięki temu będziemy mogli zmieniać wartość zmiennej, która istnieje „poza” funkcją, a jest niezmiennaniezmiennaniezmienna.

Przykład 5

Zdefiniujemy funkcję, która poda liczbę wykonanych operacji arytmetycznych podczas wyznaczania wartości wielomianu z zastosowaniem metody rekurencyjnej:

def rek_horner_licz(stopien, lista_wsp, argument):
	global zlicz

	if stopien == 0:
		return lista_wsp[stopien]
	else:
		zlicz += 2 # jedno wywołanie funkcji to 2 operacje podstawowe
		return argument * rek_horner_licz(stopien - 1, lista_wsp, argument) + lista_wsp[stopien]

Spróbujmy uruchomić funkcję; pamiętajmy o wcześniejszym zadeklarowaniu zmiennej zlicz oraz o wyświetleniu jej wartości po zakończeniu działania funkcji:

# inicjujemy zmienną, w której będziemy zliczać ilości wykonania
zlicz = 0

# uruchamiamy właściwą funkcję
rek_horner_licz(3, [6, 8, -2, 23], 7)

# sprawdzamy wartość zmiennej
print(zlicz)
6

Polecenie 1

Bazując na postaci rekurencyjnej funkcji obliczającej wartość wielomianu, spróbujmy zapisać ją używając wyrażenia trójargumentowego.

Dla zainteresowanych

Dla języka Python opracowano moduł o nazwie SymPy – pozwala on na zapisywanie wyrażeń algebraicznych i obliczanie ich wartości.

Słownik

William George Horner

brytyjski matematyk żyjący w latach 1786–1837; w wieku 14 lat został asystentem nauczyciela w szkole w Bristolu, a w 1809 roku założył własną szkołę w Bath; podał sposób wyznaczania wartości wielomianu z wykorzystaniem minimalnej liczby operacji możenia

wielomian

wyrażenie algebraiczne będące sumą jednomianów, czyli wyrażeń postaci aIndeks dolny nxIndeks górny n

stopień wielomianu

najwyższa potęga przy zmiennej, która nie jest równa zero

algorytm

przepis postępowania prowadzący do rozwiązania ustalonego problemu, określający ciąg czynności elementarnych, które należy w tym celu wykonać

iteracja

technika programowania polegająca na powtarzaniu tych samych operacji w pętli określoną liczbę razy lub do momentu, aż zostanie spełniony zadany warunek

rekurencja

technika programowania polegająca na odwoływaniu się procedur lub funkcji do samych siebie, aż do momentu spełnienia warunku podstawowego

przypadek podstawowy

przypadek, dla którego funkcja rekurencyjna nie wywołuje samej siebie, a zamiast tego zwraca z góry określoną wartość

wykonanie elementarne w rekurencji

moment, gdy funkcja rekurencyjna zwraca konkretną wartość zamiast kolejnego wywołania rekurencyjnego

przestrzeń nazw

(ang. namespace) - miejsce w pamięci operacyjnej, w której przechowywana jest dana zmienna; najczęściej przestrzeń nazw związana jest z funkcją, a zmienne używane w niej są widoczne tylko w obrębie tej przestrzeni - jest to „zakres obowiązywania” tych zmiennych

niezmienna

(ang. immutable) sekwencja lub zmienna, która jest niemodyfikowalna „w miejscu”, a więc nie można zmienić żadnego z jej elementów wewnątrz, trzeba stworzyć nowy obiekt, który zawiera zmienione elementy

Wprowadzenie

Gra edukacyjna

Obliczanie wartości wielomianu z zastosowaniem schematu Hornera

Słownik