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.
Metoda na obliczanie współczynników wielomianu za pomocą schematu Hornera
-
- 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
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.
Powód: Więcej szacunku dla Williama George'a Hornera.
- Dasio11
- 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
Wskazówka: jeśli dane jest \(\displaystyle{ w_{k+1}}\), to ile czasu zajmie obliczenie \(\displaystyle{ w_k}\) ?
-
- 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
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.
Powód: Poprawa wiadomości: niewiele.
- Dasio11
- 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
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)}\).
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)}\).
-
- 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
Nie widzę tutaj tego mnożenia wielomianów, przyjrzymy się temu: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)}\).
\(\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.
- Dasio11
- 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
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)}\).
\(\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)}\).
-
- 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
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.