Metoda na obliczanie współczynników wielomianu za pomocą schematu Hornera

Własności wielomianów; pierwiastki, współczynniki. Dzielenie wielomianów. Wzory Viete'a. RÓWNANIA I NIERÓWNOŚCI wielomianowe (wyższych stopni). Rozkład na czynniki.
Gofer33
Użytkownik
Użytkownik
Posty: 15
Rejestracja: 26 sty 2017, o 21:49
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 5 razy

Metoda na obliczanie współczynników wielomianu za pomocą schematu Hornera

Post autor: Gofer33 »

Witam, mam problem z zadaniem na studia, siedze kilka godzin, jest juz dawno po terminie, ale mimo wszystko chce to jeszcze zaliczyć.

Mamy sobie wielomian interpolacyjny w postaci Newtona, to są jego współczynniki:
\(\displaystyle{
c_{1} = f[x_{0}, x_{1}],
c_{2} = f[x_{0}, x_{1}, x_{2}]
, ... ,
c_{n} = f[x_{0}, ... , x_{n}]
}\)


Znamy też węzły
\(\displaystyle{
x_{0} ... x_{n}
}\)


I zadanie polega na tym, żeby za pomocą tych danych znależć postać naturalną(tą w której mamy wszystko wymnożone i uporządkowane). Zadanie niby proste, niby wystarczy przemnożyć wszystko i mamy. Lecz jest to kurs informatyczny i takie standardowe podejście jest nieefektywne więc trzeba to zrobić tak, żeby algorytm działał w czasie \(\displaystyle{ O(n^2).}\)

Wskazówką do tego zadania jest skorzystanie z innego algorytmu:

\(\displaystyle{
w_{n}(x) := f[x_{0}, ... , x_{n}]
\\
w_{k}(x) := f[x_{0}, ... , x_{k}] + (x − x_{k})w_{k+1}(x) (k = n − 1, . . . , 0)
}\)


No i \(\displaystyle{ w_{0}(x) }\) jest wartością naszego wielomianu w punkcie \(\displaystyle{ x}\).

Jest to tzw. uogólniony schemat Hornera.

Ogólnie to rozumiem ten algorytm, zaimplementowałem go, rozumiem jak działają ilorazy różnicowe i jak wygląda postać Newtona wielomianu interpolacyjnego, ale nie mogę wpaść na to jak korzystając z wyżej wymienionego algorytmu napisać nowy, który liczy współczynniki wielomianu w postaci naturalnej. Szukałem w necie i też nie widzę podobnych zagadnień, mam nadzieje, że ktoś przynajmniej coś podpowie, nie liczę na kompletne rozwiązanie.
Ostatnio zmieniony 13 gru 2020, o 22:40 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Więcej szacunku dla Williama George'a Hornera.
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Metoda na obliczanie współczynników wielomianu za pomocą schematu Hornera

Post autor: Dasio11 »

Gofer33 pisze: 13 gru 2020, o 22:16\(\displaystyle{
w_{n}(x) := f[x_{0}, ... , x_{n}]
\\
w_{k}(x) := f[x_{0}, ... , x_{k}] + (x − x_{k})w_{k+1}(x) (k = n − 1, . . . , 0)
}\)
Wskazówka: jeśli dane jest \(\displaystyle{ w_{k+1}}\), to ile czasu zajmie obliczenie \(\displaystyle{ w_k}\) ?
Gofer33
Użytkownik
Użytkownik
Posty: 15
Rejestracja: 26 sty 2017, o 21:49
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 5 razy

Re: Metoda na obliczanie współczynników wielomianu za pomocą schematu Hornera

Post autor: Gofer33 »

Dasio11 pisze: 14 gru 2020, o 09:42 Wskazówka: jeśli dane jest \(\displaystyle{ w_{k+1}}\), to ile czasu zajmie obliczenie \(\displaystyle{ w_k}\) ?
Ten algorytm działa w czasie \(\displaystyle{ O(n)}\). Ściślej to każdym kroku wykonujemy jedno mnożenie, jedno dodawanie oraz jedno odejmowanie. Niewiele mi to raczej daje, ponieważ docelowy algorytm ma działać co najwyżej \(\displaystyle{ O(n^2)}\), więc bedzie bardziej skomplikowany niz ten ze wskazowki. Algorytm ze schematu Hornera mozna przedstawic w postaci tabelki i widac jak on dziala, mimo wszystko po rozrysowaniu wielu przykladow dalej nie widze rozwiazania mojego problemu.
Ostatnio zmieniony 14 gru 2020, o 22:25 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości: niewiele.
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Metoda na obliczanie współczynników wielomianu za pomocą schematu Hornera

Post autor: Dasio11 »

To "jedno mnożenie" jest mnożeniem wielomianów, które zajmuje przynajmniej tyle ile wynosi mniejszy z ich stopni. W tym przypadku: \(\displaystyle{ n-k}\).

A gdyby nawet wychodził algorytm działający w czasie liniowym, to tym lepiej - przecież wymóg działania w czasie \(\displaystyle{ \mathcal{O}(n^2)}\) jest tylko ograniczeniem z góry, więc oczywiście spełniają go wszystkie algorytmy w \(\displaystyle{ \mathcal{O}(n)}\).
Gofer33
Użytkownik
Użytkownik
Posty: 15
Rejestracja: 26 sty 2017, o 21:49
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 5 razy

Re: Metoda na obliczanie współczynników wielomianu za pomocą schematu Hornera

Post autor: Gofer33 »

Dasio11 pisze: 14 gru 2020, o 12:59 To "jedno mnożenie" jest mnożeniem wielomianów, które zajmuje przynajmniej tyle ile wynosi mniejszy z ich stopni. W tym przypadku: \(\displaystyle{ n-k}\).

A gdyby nawet wychodził algorytm działający w czasie liniowym, to tym lepiej - przecież wymóg działania w czasie \(\displaystyle{ \mathcal{O}(n^2)}\) jest tylko ograniczeniem z góry, więc oczywiście spełniają go wszystkie algorytmy w \(\displaystyle{ \mathcal{O}(n)}\).
Nie widzę tutaj tego mnożenia wielomianów, przyjrzymy się temu:

\(\displaystyle{
w_{n}(x) := f[x_{0}, ... , x_{n}]
\\
w_{k}(x) := f[x_{0}, ... , x_{k}] + (x − x_{k})w_{k+1}(x) (k = n − 1, . . . , 0)
}\)


Podzielmy sobie to na czynniki:

\(\displaystyle{ f[x_{0}, ... , x_{k}]}\) - współczynnik wielomianu w postaci Newtona - liczba

\(\displaystyle{ x}\) - określony x dla którego szukamy wartości - liczba

\(\displaystyle{ x_{k}}\) - też określony x, u mnie na wykładzie się określa to mianem węzła - liczba

\(\displaystyle{ w_{k+1}(x)}\) - wartość z poprzedniego kroku algorytmu - liczba

Także ja tutaj nie widzę żadnego mnożenia wielomianów(a może powinienem?). W każdym razie w dalszym stopniu nie przybliża mnie do rozwiązania zadania. Ten algorytm, który tutaj analizujemy nie jest rozwiązaniem. On ma być tylko wskazówką do problemu, który objaśniłem w pierwszym poście. Ten algorytm, który analizujemy znajduje wartość wielomianu w punkcie x, a ja potrzebuję algorytm, który na wejściu ma \(\displaystyle{ c_{1} ... c_{n}}\) i\(\displaystyle{ x_{0} ... x_{n}}\) ma na wyjściu mi dać współczynniki tego wielomianu w postaci naturalnej w czasie max O(\(\displaystyle{ n^2}\)). Prawdopodobnie ten algorytm będzie wykorzystywał algorytm wyżej wymieniony.
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Metoda na obliczanie współczynników wielomianu za pomocą schematu Hornera

Post autor: Dasio11 »

Podany algorytm można traktować nie tylko jako obliczanie wartości wielomianu w zadanym punkcie, ale też jako obliczanie wielomianu w całości. Jeśli znasz współczynniki wielomianu \(\displaystyle{ w_{k+1}(x)}\)

\(\displaystyle{ w_{k+1}(x) = a_0 + a_1 x + \ldots + a_{n-k-1} x^{n-k-1}}\)

to algorytm mówi jak obliczyć wielomian \(\displaystyle{ w_k(x)}\):

\(\displaystyle{ w_k(x) = c_k + (-x_k+x) \big( a_0 + a_1 x + \ldots + a_{n-k-1} x^{n-k-1} \big) = (c_k - x_k a_0) + (a_0 - x_k a_1) x + \ldots + a_{n-k-1} x^{n-k}}\)

Pojedynczy krok wykonuje liniową liczbę operacji, więc całość oczywiście działa w czasie \(\displaystyle{ \mathcal{O}(n^2)}\).
Gofer33
Użytkownik
Użytkownik
Posty: 15
Rejestracja: 26 sty 2017, o 21:49
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 5 razy

Re: Metoda na obliczanie współczynników wielomianu za pomocą schematu Hornera

Post autor: Gofer33 »

Dziękuję, to mi pomogło rozwiązać problem. Własciwie to próbowałem raz tego sposobu i próbowałem go przeliczyć ręcznie, żeby dowiedzieć się czy działa i pomyliłem się w ręcznych obliczeniach i uznałem, że to nie działa, głupota. Dziękuję jeszcze raz.
ODPOWIEDZ