algorytm bairstowa na zespolone pierwiastki wielomianow

[bisz]

pytanie poniekad z informatyki:) wiadomo ze kazdy wielomian stopnia n-go moze miec n pierwiastkow rzeczywistych lub niekoniecznie rzeczywistych, interesuje mnie numeryczny algorytm na znajdowanie takowych, np program matlab pokazuje cos takiego :

>> solve(\(\displaystyle{ \large x^{15}+x^{14}+x^{13}+x^{12}+x^{10}+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1}\))

ans =

\(\displaystyle{ \large -1.1852836523606740470548945617935}\)
\(\displaystyle{ \large-0.89794109047543546502325970856796-0.28500702184226650343519055676731i}\)
\(\displaystyle{ \large -0.89794109047543546502325970856796+0.2850070218422665034351905567673i}\)
\(\displaystyle{ \large-0.63802887271009610592880356586868-0.66865706740358274202182596945709i}\)
\(\displaystyle{ \large-0.63802887271009610592880356586868+0.66865706740358274202182596945709i}\)
\(\displaystyle{ \large-0.27070733207441928458340070264918-0.99190704339866049251066873429193i}\)
\(\displaystyle{ \large-0.27070733207441928458340070264918+0.99190704339866049251066873429193i}\)
\(\displaystyle{ \large-0.11016405242165045177266384174416-1.0710794938742083689453857549327i}\)
\(\displaystyle{ \large-.11016405242165045177266384174416+1.0710794938742083689453857549327i}\)
\(\displaystyle{ \large 0.34165858969139297572198928079296-0.88552023488548687456624337017118i}\)
\(\displaystyle{ \large 0.34165858969139297572198928079296+0.88552023488548687456624337017118i}\)
\(\displaystyle{ \large 0.71774032047499069903809103231990-0.66603729338374579753163607493891i}\)
\(\displaystyle{ \large 0.71774032047499069903809103231990+0.66603729338374579753163607493891i}\)
\(\displaystyle{ \large 0.95008426369555465607549478661384-0.38550519400572837446155294186891i}\)
\(\displaystyle{ \large 0.95008426369555465607549478661384+0.38550519400572837446155294186891i}\)



no i fajnie :> ale jak on to liczy te pierwiastki, cos slyszalem o algorytmie bairstowa ale nie wiele znalazlem, ktos cos wie ? kombinowalem na podstawie 3mianu kwadratowego ze czesc rzeczywista pierwiastka zespolonego jest rowna wspolrzednej x wierzchołka paraboli ale np przy rownaniu stopnia 4 to sie juz nie sprawdza... w sumie caly zabieg sprowadza sie do odnalezienia 2 liczb spełniających jedno rownanie. ktos ma jakis pomysl lub cos wie ?:)

Edit. Wczesniej rzeczywiście nikt by sie nie domyślił moich intencji zwlaszcza ze zagadnienie bardziej nawet informatyczne niz matematyczne.

[florek177]

Może coś tu znajdziesz.

... =firefox-a

[Fibik]

Lepsza jest chyba metoda iteracyjna Laguerre'a.
Obliczenia wykonujemy na liczbach zespolonych - nie jest to wielki problem, w C++ jest klasa complex - można jej użyć, albo zrobić własną - definiujemy kilka operatorów: +, - *, /, może jeszcze funkcja sqrt i to wszystko.

Iterację rozpoczynamy od zera, po znalezieniu pierwiastka lub pary (liczby sprzężone), konieczna jest deflacja - dzielimy wielomian przez: x - p lub x^2 - px + q.
Jest jeszcze mały kłopot z pierwiastkami wielokrotnymi.

Kiedyś nawet miałem taki algorytm - liczył wszystko jak należy z dokładnością do 15 cyfr.