Metoda Graeffe'a

W matematyce metoda Graeffe'a lub metoda Dandelina-Lobachesky'ego-Graeffe'a to algorytm znajdowania wszystkich pierwiastków wielomianu . Został opracowany niezależnie przez Germinala Pierre'a Dandelina w 1826 r. i Łobaczewskiego w 1834 r. W 1837 r. Karl Heinrich Gräffe odkrył również główną ideę metody. Metoda oddziela pierwiastki wielomianu poprzez ich wielokrotne podnoszenie do kwadratu. To podnoszenie pierwiastków do kwadratu odbywa się w sposób dorozumiany, to znaczy działa tylko na współczynnikach wielomianu. Wreszcie, W celu przybliżenia korzeni stosuje się wzory Viète .

Iteracja Dandelina-Graeffe'a

Niech p ( x ) będzie wielomianem stopnia n

${\ Displaystyle p (x) = (xx_ {1}) \ cdots (xx_ {n}).}$

Następnie

${\ Displaystyle p (-x) = (-1) ^ {n} (x + x_ {1}) \ cdots (x + x_ {n}).}$

Niech q ( x ) będzie wielomianem, którego pierwiastkami są kwadraty ${\ Displaystyle x_ {1} ^ {2}, \ cdots, x_ {n} ^ {2}}$

${\ Displaystyle q (x) = \ lewo (xx_ {1} ^ {2} \ prawo) \ cdots \ lewo (xx_ {n} ^ {2} \ prawo).}$

Wtedy możemy napisać:

${\ Displaystyle {\ rozpocząć {wyrównane} q (x ^ {2}) & = \ lewo (x ^ {2} -x_ {1} ^ {2} \ prawo) \ cdots \ lewo (x ^ {2} - x_{n}^{2}\right)\\&=(x-x_{1})(x+x_{1})\cdots (x-x_{n})(x+x_{n})\ \&=\left\{(x-x_{1})\cdots (x-x_{n})\right\}\times \left\{(x+x_{1})\cdots (x+x_{ n})\right\}\\&=p(x)\times \left\{(-1)^{n}(-x-x_{1})\cdots (-x-x_{n})\ prawo\}\\&=p(x)\czasy \lewo\{(-1)^{n}p(-x)\prawo\}\\&=(-1)^{n}p(x) p(-x)\end{wyrównane}}}$

q ( ​​x ) można teraz obliczyć za pomocą operacji algebraicznych na współczynnikach samego wielomianu p ( x ) . Pozwalać:

${\ Displaystyle {\ rozpocząć {wyrównane} p (x) & = x ^ {n} + a_ {1} x ^ {n-1} + \ cdots + a_ {n-1} x + a_ {n} \\ q(x)&=x^{n}+b_{1}x^{n-1}+\cdots +b_{n-1}x+b_{n}\end{wyrównane}}}$

wtedy współczynniki są powiązane przez

$Displaystyle b_ {k} = (-1) ^{k}a_{k}^{2}+2\suma _{j=0}^{k-1}(-1)^{j}\,a_{j}a_{2k-j},\ qquad a_{0}=b_{0}=1.}$

Graeffe zauważył, że jeśli rozdzielić p ( x ) na części nieparzyste i parzyste:

${\ Displaystyle p (x) = p_ {e} \ lewo (x ^ {2} \ prawo) + xp_ {o} \ lewo (x^{2}\prawo),}$

wówczas otrzymujemy uproszczone wyrażenie algebraiczne dla q ( x ) :

${\ Displaystyle q (x) = (-1) ^ {n} \ lewo (p_ {e} (x) ^ {2} -xp_ {o} (x) ^ {2} \ prawo).}$

To wyrażenie obejmuje podniesienie do kwadratu dwóch wielomianów tylko o połowę stopnia i dlatego jest używane w większości implementacji metody.

Kilkukrotne powtórzenie tej procedury oddziela pierwiastki pod względem ich wielkości. Powtórzenie k razy daje wielomian stopnia n :

${\ Displaystyle q ^ {k} (y) = y ^ {n} + {a ^ {k}}_{1}\,y^{n-1}+\cdots +{a^{k}}_{n-1}\,y+{a^{k}}_{n}\, }$

z korzeniami

${\ Displaystyle y_ {1} = x_ {1} ^ {2 ^ {k}}, \, y_ {2} = x_ {2} ^ {2 ^ {k}}, \, \ kropki, \, y_ { n}=x_{n}^{2^{k}}.}$

$znaczy$ wielkości pierwiastków pierwotnego wielomianu zostały oddzielone jakimś ${\ Displaystyle |x_ {k}|\ geq \ rho |x_ {k+1}|}$ to , to pierwiastki k -tej iteracji są oddzielone szybko rosnącym czynnikiem

${\ Displaystyle \ rho ^ {2 ^ {k}} \ geq 1 + 2 ^ {k} (\ rho -1)}$ .

Klasyczna metoda Graeffe'a

Następnie wykorzystywane są stosunki Vieta

${\ Displaystyle {\ rozpocząć {wyrównane} a_ {\;1} ^ {k} & = - (y_ {1} + y_ {2} + \ cdots + y_ {n}) \\ a_ {\; 2} ^ {k}&=y_{1}y_{2}+y_{1}y_{3}+\cdots +y_{n-1}y_{n}\\&\;\vdots \\a_{\;n }^{k}&=(-1)^{n}(y_{1}y_{2}\cdots y_{n}).\end{wyrównane}}}$

Jeśli korzenie ${\ Displaystyle$$1$ współczynnik ${\ Displaystyle |x_ {m}|\ geq \ rho |x_ {m+1}|}$ } , a następnie iterowane potęgi ${\ Displaystyle y_ {1}, y_ {2}, ..., y_ {n}}$ korzeni są oddzielone przez współczynnik , ${\ Displaystyle \ rho ^ {2 ^ {k}}$ } który szybko staje się bardzo duży.

Współczynniki iterowanego wielomianu można następnie przybliżyć za pomocą ich członu wiodącego,

${\ Displaystyle a_ {\; 1} ^ {k} \ około -y_ {1}}$

${\ Displaystyle a_ {\; 2} ^ {k} \ około y_{1}y_{2}}$ i tak dalej,

sugerując

${\ Displaystyle y_ {1} \ około -a_ {\;1} ^ {k}, \; y_ {2} \ około -a_ {\;2} ^ {k} / a_ {\;1} ^ {k },\;\kropki \;y_{n}\około -a_{\;n}^{k}/a_{\;n-1}^{k}.}$

Wreszcie logarytmy są używane do znalezienia wartości bezwzględnych pierwiastków pierwotnego wielomianu. Same te wielkości są już przydatne do generowania znaczących punktów początkowych dla innych metod wyszukiwania pierwiastków.

Aby również uzyskać kąt tych pierwiastków, zaproponowano wiele metod, z których najprostszą jest kolejne obliczenie pierwiastka kwadratowego z (prawdopodobnie złożonego) pierwiastka z q m ( y ) {\ Displaystyle $( y)}$ , m w zakresie od k do 1 i sprawdzanie, który z dwóch wariantów znaku jest pierwiastkiem z ${\ Displaystyle q ^ {m-1} (x)}$ . Zanim przejdziemy do pierwiastków z ${\ Displaystyle q ^ {m-2} (x)}$ może być konieczne numeryczne poprawienie dokładności przybliżeń pierwiastków dla ${\ Displaystyle q ^ {m-1} (x) }$ , na przykład metodą Newtona .

Metoda Graeffe'a najlepiej sprawdza się w przypadku wielomianów z prostymi pierwiastkami rzeczywistymi, chociaż można ją dostosować do wielomianów o złożonych pierwiastkach i współczynnikach oraz pierwiastkach o większej krotności. Na przykład zaobserwowano, że dla pierwiastka ${\ Displaystyle x_ {\ ell + 1} = x_ {\ ell + 2} = \ kropki = x_ {\ell +d}}$ z krotnością d , ułamki

${\ Displaystyle \ lewo | {\ Frac {(a_ {\; \ ell + i} ^ {m-1}) ^ {2}} {a_ {\; \ ell + i} ^ {m.}}} \ prawo |}$ tendencję do ${\ Displaystyle {\ binom {d} {i}}}$

dla ${\ Displaystyle i = 0,1, \ kropki, d}$ . Pozwala to oszacować strukturę krotności zbioru pierwiastków.

Z numerycznego punktu widzenia metoda ta jest problematyczna, ponieważ współczynniki iterowanych wielomianów obejmują bardzo szybko wiele rzędów wielkości, co pociąga za sobą poważne błędy numeryczne. Drugim, ale mniejszym problemem jest to, że wiele różnych wielomianów prowadzi do tych samych iteracji Graeffe'a.

Styczna metoda Graeffe'a

Ta metoda zastępuje liczby obciętymi szeregami potęgowymi stopnia 1, znanymi również jako liczby podwójne . Symbolicznie osiąga się to poprzez wprowadzenie „algebraicznej nieskończenie małej” $z$ właściwością definiującą ${\ displaystyle \ varepsilon ^ {2} = 0$ } Wtedy wielomian ${\ Displaystyle p (x + \ varepsilon) = p (x) + \ varepsilon \, p' (x)}$ ma korzenie ${\ Displaystyle x_ {m} - \ varepsilon}$ , z mocami

${\ Displaystyle (x_ {m} - \ varepsilon) ^ {2 ^ {k}} = x_ {m} ^ {2 ^ {k}} - \ varepsilon \, {2 ^ {k}} \, x_ {m }^{2^{k}-1}=y_{m}+\varepsilon \,{\dot {y}}_{m}.}$

${\ Displaystyle x_ {m} = - {\ tfrac {2 ^ {k} \, y_ {m}} {{\ kropka {y}} _ {m}}}.}$ wartość można łatwo jako $ułamek$

Ten rodzaj obliczeń z nieskończenie małymi jest łatwy do zaimplementowania, analogicznie do obliczeń z liczbami zespolonymi. Jeśli przyjmie się złożone współrzędne lub początkowe przesunięcie o jakąś losowo wybraną liczbę zespoloną, wówczas wszystkie pierwiastki wielomianu będą różne iw konsekwencji możliwe do odzyskania w iteracji.

Renormalizacja

Każdy wielomian można przeskalować w dziedzinie i zakresie tak, że w wynikowym wielomianie pierwszy i ostatni współczynnik mają rozmiar jeden. Jeśli rozmiar wewnętrznych współczynników jest ograniczony przez M , to rozmiar wewnętrznych współczynników po jednym etapie iteracji Graeffe'a jest ograniczony przez ${\ Displaystyle nM ^ {2}}$ . Po k $_$ granicę _

Aby przezwyciężyć ograniczenie wynikające ze wzrostu potęg, Malajovich-Zubelli proponują reprezentację współczynników i wyników pośrednich w k-tym etapie algorytmu za pomocą przeskalowanej postaci biegunowej

${\ Displaystyle c = \ alfa \, e ^ {- 2 ^ {k} \, r},}$

gdzie ${\ Displaystyle \ alfa = {\ Frac {c} {| c |}}}$ jest liczbą zespoloną o długości jednostkowej i ${\ Displaystyle r = -2 ^ {- k} \ log | c |}$ jest dodatnią liczbą rzeczywistą. Oddzielenie potęgi w wykładniku zmniejsza wartość bezwzględną c ${\ displaystyle 2 ^ {k}}$ do odpowiedniego pierwiastka diadycznego. Ponieważ zachowuje to wielkość (reprezentacji) początkowych współczynników, proces ten nazwano renormalizacją.

Mnożenie dwóch liczb tego typu jest proste, natomiast dodawanie następuje po rozkładzie na czynniki ${\ Displaystyle c_ {3} = c_ {1} + c_ {2} = | c_ {1} | \ cdot \ lewo (\ alfa _ {1 }+\alpha _{2}{\tfrac {|c_{2}|}{|c_{1}|}}\right)}$ , gdzie ${\ displaystyle c_ {1}}$ jest wybierany jako większa z obu liczb, to znaczy ${\ displaystyle r_ {1}<r_ {2}}$ . Zatem

${\ Displaystyle \ alfa _ {3} = {\ tfrac {s} {| s |}}}$ i ${\ Displaystyle r_ {3} = r_ {1} + 2 ^ {- k} \ \ log {| s |}}$ z ${\ Displaystyle s = \ alfa _ {1} + \ alfa _ {2} \, e ^ {2 ^ {k} (r_ {1} -r_ {2})}.}$

Współczynniki $\ Displaystyle a_ {0}, a_ {1}, \ kropki, a_ {n}}$ końcowego etapu k iteracji Graeffe'a, dla pewnej dość dużej wartości k , są reprezentowane przez pary ${\ Displaystyle (\ alfa _ {m}, r_ {m})}$ , ${\ Displaystyle m = 0, \ kropki, n}$ . Identyfikując rogi wypukłej obwiedni zbioru punktów ${\ Displaystyle \ {(m, r_ {m}): \; m = 0, \ kropki, n\}}$ można wyznaczyć krotności pierwiastków wielomianu. Łącząc tę ​​renormalizację z iteracją styczną, można bezpośrednio ze współczynników w rogach obwiedni wyodrębnić pierwiastki pierwotnego wielomianu.

Zobacz też

• Algorytm znajdowania korzeni

• Weisstein, Eric W. „Metoda Graeffe'a” . MathWorld .
•   Malajowicz, Gregorio; Zubelli, Jorge P. (2001). „Iteracja styczna Graeffe”. Matematyka numeryczna . 89 (4): 749–782. CiteSeerX 10.1.1.44.3611 . doi : 10.1007/s002110100278 .