Autor Wątek: Szukanie pierwiastków wielomianu.  (Przeczytany 2963 razy)

Offline karol57

  • Użytkownik

  • +1
# Maj 13, 2014, 14:06:03
Mam funkcję w postaci f(x) = 0.8x6 - 0.5x5 + x4 - 4x3 - 3x2 + 6x i muszę napisać program, który znajdzie miejsca zerowe oraz ekstrema na przedziale <-2.4; 2.6>.

Jedynym problemem jaki mam jest szukanie miejsc zerowych. Umiem szukać 1. miejsca zerowego (metody: siecznych, bisekcji, Newtona), ale nie mam pojęcia jak znaleźć ich więcej (w tym wypadku 4 na f i 3 na f').

Na razie znalazłem dwa rozwiązania, jednak oba polegają na pewnej formie oszustwa:
1. Popatrzeć na wykres funkcji i podzielić przedział na takie podprzedziały, aby w każdym było 1. miejsce zerowe.
2. Wysłać zapytanie do WolframAlpha i zinterpretować wynik.

Reasumując: Jaki algorytm stosuje się do szukania pierwiastków wielomianu?

P.S. Z góry dziękuję za szybką odpowiedź, bo mam termin do jutra.

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline albireo

  • Użytkownik

  • +1
# Maj 13, 2014, 14:32:48
Szybki pomysł, znaleźć miejsca zerowe pochodnej funkcji i szukać miejsc zerowych oryginalnej funkcji między miejscami zerowymi pochodnej oraz skrajnymi miejscami zerowymi pochodnej i w plus/minus nieskończoności. Można stosować "rekurencyjnie" aż się dojdzie do stopnia funkcji który łatwo obliczyć.
Tylko trzeba uważać na warunki brzegowe, bo miejsce zerowe pierwotnej funkcji może też wyjść na miejscu zerowym pochodnej i z powodu zaokrągleń się "zgubić".
« Ostatnia zmiana: Maj 13, 2014, 14:36:46 wysłana przez albireo »

Offline Xender

  • Użytkownik

  • +1
# Maj 13, 2014, 15:11:46
Jak znajdziesz jeden pierwiastek (powiedzmy x0), to dzielisz cały wielomian przez (x - x0). Rekurencyjnie szukasz miejsc zerowych wyniku tego dzielenia.

Ekstema lokalne to tyle, co miejsca zerowe pochodnej. Więc zapuścić powyższy algorytm na pochodnej i tyle.

Offline koirat

  • Użytkownik

  • +1
# Maj 13, 2014, 16:04:55
Ekstema lokalne to tyle, co miejsca zerowe pochodnej.
Mogą być to punkty przegięcia. Potrzebujesz jeszcze warunku wystarczającego.

Offline hashedone

  • Użytkownik

# Maj 13, 2014, 16:06:43
Można użyć metody Xendera, (znaleźć pierwiastek i dzielić go, potem szukać następnego pierwiastka), ale jeśli możesz w miarę optymalnie znaleźć przedziały w których będą po jednym pierwiastku, poszedł bym tym tropem choćby dla tego, że na takich przedziałach metody szukania pierwiastków będą potrzebować mniej iteracji.

Offline dynax

  • Użytkownik

# Maj 13, 2014, 21:14:10
Mogą być to punkty przegięcia. Potrzebujesz jeszcze warunku wystarczającego.

Ale to tylko kwestia zbadania czy w tym punkcie zmienia się znak pochodnej, więc wystarczy zbadać x0 + epsilon i x0 - epsilon.
Zastanawia mnie tylko czy jeśli rozpatrujemy ten przypadek myśląc o floatach a nie liczbach rzeczywistych to jest sens bawić się w algorytmikę czy nie wystarczy zbadać wszystkich możliwych do zapisania we float liczb z tego przedziału ;)

Offline Xirdus

  • Redaktor

  • +1
# Maj 13, 2014, 21:22:12
Zastanawia mnie tylko czy jeśli rozpatrujemy ten przypadek myśląc o floatach a nie liczbach rzeczywistych to jest sens bawić się w algorytmikę czy nie wystarczy zbadać wszystkich możliwych do zapisania we float liczb z tego przedziału ;)
Trochę tych liczb jest...

Offline Xender

  • Użytkownik

# Maj 13, 2014, 22:23:58
Mogą być to punkty przegięcia. Potrzebujesz jeszcze warunku wystarczającego.
Fakt. Sorry.

Ale to tylko kwestia zbadania czy w tym punkcie zmienia się znak pochodnej, więc wystarczy zbadać x0 + epsilon i x0 - epsilon.
Ja bym tam zbadał drugą pochodną, żeby nie robić częściowo-analitycznie-częściowo-numerycznie /* Nvm. Nie doczytałem, że metode Newtona sama jest numeryczna... */. Chyba, że teraz znów coś przeoczyłem? (Sorry, moja matma jest trochę-licealna-trochę-samoukowa).
« Ostatnia zmiana: Maj 14, 2014, 00:25:53 wysłana przez Xender »

Offline karol57

  • Użytkownik

# Maj 14, 2014, 00:19:27
Dobra. Zrobiłem.

Pierwiastków szukałem metodą Newtona startując od (a+b)/2, gdzie a i b to granice przedziału.
Gdy metoda Newtona prawdopodobnie rozbiega się, bądź f'(x0) = 0, a f(x0) != 0 to algorytm przestaje szukać miejsc zerowych i uznaje, że więcej 'nie ma'.

Następnie według pomysłu Xendera dzielę wielomian przez pierwiastek i zaczynam zabawę od nowa.

Szukanie ekstremów to zabawa jak wyżej tylko z pierwszą pochodną + analiza znaku drugiej pochodnej.

Oczywiście wszystkie porównania z dokładnością do ε.

W prawdzie w przypadku rozbieżności metody Newtona, bądź trafienia na f'(x0) = 0 można stracić sporo pierwiastków, to dla zadanego wielomianu wszystko działa prawidłowo, a ja nie mam siły już dzisiaj kombinować co zrobić w tym przypadku.

Dzięki wszystkim za pomoc.

Jakby ktoś chciał kod, to po oddaniu i sprawdzeniu projektu wrzucę tutaj do tematu.

...
Zastanawia mnie tylko czy jeśli rozpatrujemy ten przypadek myśląc o floatach a nie liczbach rzeczywistych to jest sens bawić się w algorytmikę czy nie wystarczy zbadać wszystkich możliwych do zapisania we float liczb z tego przedziału ;)
Też nad tym myślałem, ale uznałem, że to pewna forma oszustwa i problem należy rozwiązać analitycznie. W każdym razie przy moim ε to 'tylko' 50'000'000 miejsc do sprawdzenia, więc z Hornera 6x tyle mnożeń i dodawań + interpretacja.
« Ostatnia zmiana: Maj 14, 2014, 00:25:33 wysłana przez karol57 »

Offline Xender

  • Użytkownik

# Maj 14, 2014, 00:27:43
^ Skoro masz epslon, to numerycznie, nie analitycznie. Przejechanie po floatach to byłby bruteforce ;_;.

A tak jakby ktoś chciał przynerdzić nad problemem: https://en.wikipedia.org/wiki/Root-finding_algorithm.
« Ostatnia zmiana: Maj 14, 2014, 00:30:57 wysłana przez Xender »

Offline ShadowDancer

  • Redaktor

# Maj 14, 2014, 00:32:41
Metoda Newtona jest lokalnie zbieżna i po trafieniu na ekstremum może wystrzelić w kierunku nieskończoności, najpierw użyj metody bisekcji.

Offline karol57

  • Użytkownik

# Maj 14, 2014, 02:04:14
Czyli cały problem sprowadza się do znalezienia przedziałów w których jest jedno miejsce zerowe (ew. więcej, ale przedziały różnią się znakami).

O ile (właśnie czytam kod kogoś innego) inni hardcode'ują te przedziały to ja bym wolał, aby program dostawał jak najmniej informacji. Wydaje mi się, że można sprytnie pobawić się pochodnymi (jak @albireo napisał) i wtedy ładnie by wszystko wyszło.

Ale za późno już na myślenie. Na razie ważne, że wszystko działa i mam co oddać. Będę miał trochę wolnego czasu to przeanalizuje to dokładnie.