Obliczanie wartości wielomianu (schemat Hornera)

Schemat Hornera to efektywna metoda obliczania wartości wielomianu w punkcie, która minimalizuje liczbę potrzebnych operacji (mnożeń). Pozwala to na szybsze i bardziej efektywne obliczenia niż tradycyjne metody, matematyczne.

Załóżmy, że mamy wielomian stopnia 5:

$$w(x)=4x^5+3x^4+7x^3-14x^2+12x-15$$

Schemat Hornera pozwala go przekształcić do postaci:

$$w(x)=(4x^4+3x^3+7x^2-14x+12)x-15$$

$$w(x)=((4x^3+3x^2+7x-14)x+12)x-15$$

$$w(x)=(((4x^2+3x+7)x-14)x+12)x-15$$

$$w(x)=((((4x+3)x+7)x-14)x+12)x-15$$

To oznacza, że wartość wielomianu w punkcie x można obliczyć w sposób iteracyjny, zaczynając od współczynnika przy najwyższej potędze x.

Algorytm w języku Python

def horner1(lista, x):
    n = len(lista)-1 #stopień wielomianu
    wynik = lista[0]
    for i in range(1, n+1):
        wynik = wynik * x + lista[i]
    return wynik
    
def horner2(lista, x):
    n = len(lista)-1 #stopień wielomianu
    wynik = lista[0]
    for i in lista[1:]:
        wynik = wynik * x + i
    return wynik

# Przykład użycia
wspolczynniki = [2, -3, 5, -7]
x = 2
result = horner1(wspolczynniki, x)

print('Wartość wielomianu dla x =', x, 'W(x) =',  result)

Złożoność obliczeniowa schematu Hornera jest liniowa i wynosi O(n), gdzie n to stopień wielomianu. To sprawia, że jest bardziej efektywny niż tradycyjne metody obliczania wartości wielomianu, takie jak schemat współczynników, które mają złożoność obliczeniową O(n^2).

W przypadku schematu Hornera, jedno przejście przez pętlę for jest wystarczające do obliczenia wartości wielomianu dla określonej wartości x. W każdym kroku pętli wykonujemy jedno mnożenie i jedno dodawanie, co przekłada się na liniową złożoność.

Złożoność obliczeniowa może być kluczowym aspektem przy wyborze algorytmu w przypadku dużych danych, zwłaszcza gdy mamy do czynienia z wielomianami o wysokich stopniach. Schemat Hornera jest często stosowany w praktyce ze względu na swoją efektywność obliczeniową.