Czy istnieje otwarta implementacja C dla rozwiązania równań kwartalnych:
Mam na myśli wdrożenie rozwiązania Ferrari. Na Wikipedii czytam, że rozwiązanie jest stabilne obliczeniowo tylko dla niektórych możliwych kombinacji znaków współczynników. Ale może mam szczęście ... Mam pragmatyczne rozwiązanie, rozwiązując analitycznie za pomocą komputerowego systemu algebry i eksportując do C. Ale jeśli istnieje przetestowana implementacja, wolałbym to wykorzystać. Szukam szybkiej metody i wolę nie używać ogólnej wyszukiwarki rootów.
Potrzebuję tylko prawdziwych rozwiązań.
Odpowiedzi:
Zdecydowanie odradzam stosowanie rozwiązań w formie zamkniętej, ponieważ są one zwykle bardzo niestabilne numerycznie. Musisz zachować szczególną ostrożność w sposobie i kolejności ocen dyskryminatora i innych parametrów.
Klasycznym przykładem jest równanie kwadratowe . Obliczenie pierwiastków jako spowoduje kłopoty dla wielomianów, w których od tego czasu można anulować w licznik ułamka. Musisz obliczyć .x 1 , 2 = - b ± √ax2+bx+c=0 b≫4acx1=-(b+sign(b) √
Higham w swoim arcydziele „Dokładność i stabilność algorytmów numerycznych” (wydanie 2, SIAM) wykorzystuje metodę bezpośredniego wyszukiwania, aby znaleźć współczynniki wielomianu sześciennego, dla których klasyczne analityczne rozwiązanie sześcienne daje bardzo niedokładne wyniki. Przykład, który podaje, to . W przypadku tego wielomianu korzenie są dobrze rozdzielone, a zatem problem nie jest źle uwarunkowany. Jeśli jednak wyliczy pierwiastki za pomocą metody analitycznej i oceni wielomian w tych korzeniach, otrzyma pozostałość , stosując metodę stabilnego standardu (metoda macierzy towarzyszącej) , pozostałość jest rzęduO ( 10 - 2 ) O ([a,b,c]=[1.732,1,1.2704] O(10−2) O(10−15) . Proponuje niewielką modyfikację algorytmu, ale nawet wtedy może znaleźć zestaw współczynników prowadzących do reszt co zdecydowanie nie jest dobre. Zobacz str. 480–481 wyżej wymienionej książki.O(10−11)
W twoim przypadku zastosowałbym metodę Bairstow . Wykorzystuje iteracyjną kombinację iteracji Newtona na formach kwadratowych (a następnie rozwiązane są pierwiastki kwadratowe) i deflacji. Można go łatwo wdrożyć, a w Internecie dostępne są nawet niektóre wdrożenia.
źródło
Zobacz te:
Rozwiązywanie Quartics i Cubics dla Graphics , pierwotnie opublikowany w Graphics Gems V . Oryginalny kod jest tutaj . Zobacz także to i to .
Uniwersalna metoda rozwiązywania równań kwartalnych .
źródło
Receptury numeryczne w c zapewniają zamkniętą ekspresję formy dla prawdziwych pierwiastków kwadratowych i sześciennych, które przypuszczalnie mają przyzwoitą precyzję. Ponieważ algebraiczne rozwiązanie kwartyku polega na rozwiązaniu sześciennej, a następnie rozwiązaniu dwóch kwadratów, być może kwantyk o zamkniętej formie z dobrą precyzją nie jest wykluczony.
źródło