Co to jest prosty sposób na znalezienie prawdziwych pierwiastków wielomianu (sześciennego)?

Question

wydaje mi się to oczywistym pytaniem, ale nigdzie nie mogłem go znaleźć. Mam wielomian sześcienny i muszę znaleźć prawdziwe korzenie tej funkcji. Jaki jest sposób wykonywania tej czynności?

Znalazłem kilka formuł zamkniętych dla pierwiastków o funkcji sześciennej, ale wszystkie z nich używają liczb zespolonych lub wielu funkcji goniometrycznych i nie lubię ich (a także nie wiem, który wybrać) .

Potrzebuję czegoś prostego; szybciej jest lepiej; i wiem, że w końcu będę potrzebował rozwiązać wielomiany wyższego rzędu, więc pomoc w rozwiązywaniu liczb może też pomóc. Wiem, że przydałaby mi się jakaś biblioteka do wykonania ciężkiej pracy dla mnie, ale powiedzmy, że chcę to zrobić jako ćwiczenie.

Koduję w języku C, więc nie proszę o import magic_poly_solver.

Pytanie dodatkowe: Jak znaleźć tylko korzenie w określonym przedziale?

Answer 1

Dla wielomianu sześciennego są closed form solutions, ale nie są szczególnie dobrze dopasowane do rachunku numerycznego.

Zrobilibyśmy następujące rzeczy w przypadku sześciennego: każdy wielomian sześcienny ma co najmniej jeden prawdziwy korzeń, można go łatwo znaleźć za pomocą metody Newtona. Następnie należy użyć deflation, aby uzyskać pozostałe kwadratowe wielomian do rozwiązania, zobacz moją odpowiedź there, jak poprawnie wykonać ten ostatni krok.

Jedno słowo ostrożności: jeśli dyskryminator jest bliski zeru, pojawi się numerycznie wielokrotny prawdziwy korzeń, a metoda Newtona zakończy się marnym niepowodzeniem. Co więcej, ponieważ w pobliżu korzenia, wielomian jest jak (x - x0)^2, stracisz połowę znaczących cyfr (od P (x) będzie < epsilon jak tylko x - x0 < sqrt (epsilon)). Więc możesz tego wykluczyć i użyć rozwiązania zamkniętego formularza w tym konkretnym przypadku lub rozwiązać wielomian pochodny.

Aby znaleźć korzenie w danym przedziale, sprawdź: Sturm's theorem.

Bardziej ogólnym (złożonym) algorytmem do ogólnego rozwiązywania wielomianów jest Jenkins-Traub algorithm. Jest to wyraźnie przesadne, ale działa dobrze na kubikach. Zwykle używasz implementacji innej firmy.

Ponieważ robisz C, używanie GSL jest z pewnością najlepszym wyborem.

Inną generyczną metodą jest znalezienie wartości własnych companion matrix z np. zrównoważona dekompozycja QR lub redukcja do formy Householder. Takie jest podejście przyjęte przez GSL.

Answer 2

Jeśli nie chcesz używać zamkniętych z rozwiązań (lub oczekujesz wielomianów o większym zamówieniu), najbardziej oczywistą metodą byłoby obliczenie przybliżonych korzeni za pomocą Newton's method.

Niestety nie jest możliwe określenie, które korzenie otrzymasz podczas iteracji, choć zależy to od wartości początkowej.

Zobacz także here.

Answer 3

Zob. Solving quartics and cubics for graphics autorstwa D Herbison-Evans, opublikowane w Graphics Gems V.

Answer 4

/******************************************************************************* 
* FindCubicRoots solves: 
*  coeff[3] * x^3 + coeff[2] * x^2 + coeff[1] * x + coeff[0] = 0 
* returns: 
*  3 - 3 real roots 
*  1 - 1 real root (2 complex conjugate) 
*******************************************************************************/ 

int FindCubicRoots(const FLOAT coeff[4], FLOAT x[3]); 

http://www.realitypixels.com/turk/opensource/index.html#CubicRoots