Metoda Duranda-Kernera

W analizie numerycznej metoda Weierstrassa lub metoda Duranda-Kernera , odkryta przez Karla Weierstrassa w 1891 r. I ponownie odkryta niezależnie przez Duranda w 1960 r. I Kernera w 1966 r., Jest algorytmem wyszukiwania pierwiastków do rozwiązywania równań wielomianowych . Innymi słowy, metodę można wykorzystać do numerycznego rozwiązania równania

fa ( x ) = 0,

gdzie f jest danym wielomianem, który można przyjąć, że jest skalowany tak, że współczynnik wiodący wynosi 1.

Wyjaśnienie

To wyjaśnienie uwzględnia równania stopnia czwartego. Można to łatwo uogólnić na inne stopnie.

Niech wielomian f będzie zdefiniowany przez

${\ Displaystyle f (x) = x ^ {4} + ax ^ {3} + bx ^ {2} + cx + d}$

dla wszystkich x .

Znane liczby a , b , c , d to współczynniki .

Niech (potencjalnie zespolone) liczby P , Q , R , S będą pierwiastkami tego wielomianu f .

Następnie

${\ Displaystyle f (x) = (xP) (xQ) (xR) (xS)}$

dla wszystkich x . Z tego równania można wydzielić wartość P :

${\ Displaystyle P = x - {\ Frac {f (x)} {(xQ) (xR) (xS)}}.}$

Więc jeśli jest używany jako iteracja punktu stałego

${\ Displaystyle x_ {1}: = x_ {0} - {\ Frac {f (x_ {0} )}{(x_{0}-Q)(x_{0}-R)(x_{0}-S)}},}$

₀ jest silnie stabilny, ponieważ każdy punkt początkowy x ≠ Q , R , S dostarcza po jednej iteracji pierwiastek P = x ₁ .

Ponadto, jeśli zastąpimy zera Q , R i S przybliżeniami q ≈ Q , r ≈ R , s ≈ S , takimi że q , r , s nie są równe P , to P nadal jest stałym punktem zaburzonej stałej - iteracja punktowa

${\ Displaystyle x_ {k + 1}: = x_ {k} - { \frac {f(x_{k})}{(x_{k}-q)(x_{k}-r)(x_{k}-s)}},}$

od

${\ Displaystyle P - {\ Frac {f (P)} {(Pq) (Pr) (PS)}} = P-0 = P.}$

Zauważ, że mianownik nadal jest różny od zera. Ta iteracja punktu stałego jest odwzorowaniem skurczu dla x wokół P .

Kluczem do tej metody jest teraz połączenie iteracji punktu stałego dla P z podobnymi iteracjami dla Q , R , S w jednoczesną iterację dla wszystkich pierwiastków.

Inicjalizuj p , q , r , s :

₀⁰ p := (0,4 + 0,9 ja ) ,

₀ q := (0,4 + 0,9 ja ) ¹ ,

₀ r := (0,4 + 0,9 ja ) ² ,

₀ s := (0,4 + 0,9 ja ) ³ .

Nie ma nic specjalnego w wyborze 0,4 + 0,9 i poza tym, że nie jest to ani liczba rzeczywista , ani pierwiastek z jedności .

Dokonaj podstawień dla n = 1, 2, 3, ...:

${ \ Displaystyle p_ {n} = p_ {n-1} - {\ frac {f (p_ {n-1})}} {(p_ {n-1} -q_ {n-1}) (p_ {n-1} }-r_{n-1})(p_{n-1}-s_{n-1})}},}$

${\ Displaystyle q_ {n} = q_ {n-1} - {\ Frac {f (q_ {n- 1})}{(q_{n-1}-p_{n})(q_{n-1}-r_{n-1})(q_{n-1}-s_{n-1})}} ,}$

${\ Displaystyle r_{n}=r_{n-1}-{\frac {f(r_{n-1})}{(r_{n-1}-p_{n})(r_{n-1}-q_{ n})(r_{n-1}-s_{n-1})}},}$

${\ Displaystyle s_ {n} = s_ {n-1} - {\ Frac {f (s_ {n-1})} {(s_ {n-1} -p_ {n}) (s_ {n-1} -q_{n})(s_{n-1}-r_{n})}}.}$

Powtórz iterację, aż liczby p , q , r , s zasadniczo przestaną się zmieniać względem pożądanej precyzji. Mają wtedy wartości P , Q , R , S w pewnej kolejności iz wybraną precyzją. Więc problem rozwiązany.

Należy zauważyć, że należy zastosować arytmetykę liczb zespolonych i że pierwiastki znajdują się jednocześnie, a nie pojedynczo.

Wariacje

Ta procedura iteracji, podobnie jak metoda Gaussa-Seidela dla równań liniowych, oblicza jedną liczbę na raz na podstawie już obliczonych liczb. Wariant tej procedury, podobnie jak metoda Jacobiego , oblicza jednocześnie wektor przybliżeń pierwiastków. Oba warianty są skutecznymi algorytmami wyszukiwania korzeni.

Można by też wybrać wartości początkowe dla p , q , r , s inną procedurą, nawet losowo, ale w taki sposób, że

• znajdują się w jakimś niezbyt dużym okręgu zawierającym również pierwiastki f ( x ), np. okrąg wokół początku układu współrzędnych o promieniu ${\ displaystyle 1+\max {\big (}|a|,|b|,|c|,|d|{\big )}} , (gdzie 1$ , a , b , c , d to współczynniki f ( x ))

i to

• nie są zbyt blisko siebie,

co może coraz bardziej budzić niepokój wraz ze wzrostem stopnia wielomianu.

₀₀₀ Jeśli współczynniki są rzeczywiste, a wielomian ma nieparzysty stopień, to musi mieć co najmniej jeden pierwiastek rzeczywisty. Aby to znaleźć, użyj rzeczywistej wartości p jako początkowego przypuszczenia i utwórz q i r , itd., Zespolone pary sprzężone . Następnie iteracja zachowa te właściwości; to znaczy p _n zawsze będzie rzeczywiste, a q _n i r _n itd. zawsze będą sprzężone. W ten sposób p _n zbiegnie się do rzeczywistego pierwiastka P . Alternatywnie, spraw, aby wszystkie początkowe domysły były prawdziwe; tak pozostaną.

Przykład

Ten przykład pochodzi z odnośnika 1992. Rozwiązane równanie to x ³ − 3 x ² + 3 x − 5 = 0 . Pierwsze 4 iteracje przesuwają p , q , r pozornie chaotycznie, ale potem pierwiastki znajdują się z dokładnością do 1 miejsca po przecinku. Po iteracji numer 5 mamy 4 poprawne miejsca po przecinku, a kolejna iteracja numer 6 potwierdza, że ​​obliczone pierwiastki są stałe. To ogólne zachowanie jest charakterystyczne dla metody. Zauważ również, że w tym przykładzie korzenie są używane, gdy tylko zostaną obliczone w każdej iteracji. Innymi słowy, obliczenia dla każdej drugiej kolumny wykorzystują wartość poprzednich kolumn obliczonych.

to nie.	P	Q	R
0	+1,0000 + 0,0000i	+0,4000 + 0,9000i	−0,6500 + 0,7200i
1	+1,3608 + 2,0222i	−0,3658 + 2,4838i	−2,3858 − 0,0284i
2	+2,6597 + 2,7137i	+0,5977 + 0,8225i	−0,6320−1,6716i
3	+2,2704 + 0,3880i	+0,1312 + 1,3128i	+0,2821 - 1,5015i
4	+2,5428 - 0,0153i	+0,2044 + 1,3716i	+0,2056 - 1,3721i
5	+2,5874 + 0,0000i	+0,2063 + 1,3747i	+0,2063 - 1,3747i
6	+2,5874 + 0,0000i	+0,2063 + 1,3747i	+0,2063 - 1,3747i

Zauważ, że równanie ma jeden pierwiastek rzeczywisty i jedną parę sprzężonych pierwiastków zespolonych, a suma pierwiastków wynosi 3.

Wyprowadzenie metody metodą Newtona

Dla każdej n -krotki liczb zespolonych istnieje dokładnie jeden wielomian moniczny stopnia n , który ma je jako swoje zera (z zachowaniem krotności). Ten wielomian jest dany przez pomnożenie wszystkich odpowiednich czynników liniowych, to znaczy

${\ Displaystyle g _ {\ vec {z}} (X) = (X-z_ {1}) \ cdots (X-z_ {n}).}$

Ten wielomian ma współczynniki zależne od określonych zer,

${\ Displaystyle g _ {\ vec {z}} (X) = X ^ {n} + g_ {n-1} ({\ vec {z}}) X ^ {n-1} + \ cdots + g_ {0 }({\vec {z}}).}$

Te współczynniki to, do znaku, elementarne wielomiany symetryczne ${\ Displaystyle \ alpha _ {1} ({\ vec {z}}), \ kropki, \alpha _{n}({\vec {z}})}$ stopni 1,...,n .

Aby znaleźć wszystkie pierwiastki danego wielomianu ${\ Displaystyle f (X) = X ^ {n} + c_ {n-1} X ^ {n-1} + \ cdots + c_ {0}}$ z wektorem współczynników ${\ Displaystyle (c_ {n-1}, \ kropki, c_ {0})}$ jednocześnie jest teraz to samo, co znalezienie wektora rozwiązania dla systemu Vieta

${\ Displaystyle {\ rozpocząć {macierz} c_ {0} & = & g_ {0} ({\ vec {z}}) & = & (-1) ^ {n} \ alfa _ {n} ({\ vec { z}})&=&(-1)^{n}z_{1}\cdots z_{n}\\c_{1}&=&g_{1}({\vec {z}})&=&( -1)^{n-1}\alpha _{n-1}({\vec {z}})\\&\vdots &\\c_{n-1}&=&g_{n-1}({ \vec {z}})&=&-\alpha_{1}({\vec {z}})&=&-(z_{1}+z_{2}+\cdots +z_{n}). \end{macierz}}}$

Metodę Duranda-Kernera uzyskuje się jako wielowymiarową metodę Newtona zastosowaną do tego układu. Algebraicznie wygodniej jest traktować te tożsamości współczynników jako tożsamości odpowiednich wielomianów, ${\ Displaystyle g _ {\ vec {z}} (X) = f (X)}$ . W metodzie Newtona szuka się, biorąc pod uwagę pewien ${\ Displaystyle g _ {{\ vec {z}} + {\ vec {w}}} (X) = f (X)} jest spełnione$$początkowy$ przyrostowy $,$ że do warunków drugiego i wyższego rzędu w przyroście . W tym celu rozwiązuje tożsamość

${\ Displaystyle f (X) - g _ {\ vec {z}} (X) = \ suma _ {k = 1} ^ {n} {\ Frac {\ częściowe g_ {\ vec {z}} (X)} {\częściowe z_{k}}}w_{k}=-\suma _{k=1}^{n}w_{k}\prod _{j\neq k}(X-z_{j}).}$

Jeśli liczby $są różne$ to wyrażone po prawej stronie tworzą wymiarowej ${\ Displaystyle \ mathbb {C} [X] _ {n-1}}$ wielomianów o maksymalnym stopniu n - 1. Zatem rozwiązanie ${\ Displaystyle {\ vec {w}}}$ równanie przyrostu istnieje w tym przypadku. Współrzędne przyrostu uzyskuje się po prostu oceniając równanie przyrostu ${\ displaystyle {\ vec {w}}}$

${\ Displaystyle - \ suma _ {k = 1} ^ {n }w_{k}\prod _{j\neq k}(X-z_{j})=f(X)-\prod _{j=1}^{n}(X-z_{j})}$

w punktach ${\ displaystyle X = z_ {k}}$ , co skutkuje

${\ Displaystyle -w_ {k} \ prod _ {j \ neq k} ( z_{k}-z_{j})=-w_{k}g_{\vec {z}}'(z_{k})=f(z_{k})} ,$ czyli ${\ Displaystyle w_ {k} = - {\ Frac {f (z_ {k})} {\ prod _ {j \ neq k} (z_ {k} -z_ {j})}}.}$

Inkluzja korzenia poprzez kręgi Gerschgorina

W pierścieniu ilorazowym ( algebrze ) klas reszt modulo ƒ ( X ) mnożenie przez X definiuje endomorfizm , który ma zera ƒ ( X ) jako wartości własne z odpowiednimi krotnościami. Wybierając podstawę, operator mnożenia jest reprezentowany przez swoją macierz współczynników A , macierz towarzyszącą ƒ( X ) dla tej podstawy.

Ponieważ każdy wielomian można zredukować modulo ƒ ( X ) do wielomianu stopnia n - 1 lub mniejszego, przestrzeń klas reszt można utożsamić z przestrzenią wielomianów stopnia ograniczonego przez n - 1. Można przyjąć podstawę problemu z interpolacji Lagrange'a jako zbioru n wielomianów

${\ Displaystyle b_ {k} (X) = \ prod _ {1 \ równoważnik j \leq n,\;j\neq k}(X-z_{j}),\quad k=1,\dots ,n,}$

gdzie ${\ displaystyle z_ {1}, \ kropki, z_ {n} \ in \ mathbb {C}}$ są parami różnych liczb zespolonych. Zauważ, że funkcje jądra dla interpolacji Lagrange'a to ${\ Displaystyle L_ {k} (X) = {\ Frac {b_ {k} (X)} {b_{k}(z_{k})}}}$ .

Dla operatora mnożenia zastosowanego do wielomianów bazowych otrzymuje się z interpolacji Lagrange'a

${\ Displaystyle X \ cdot b_ {k} (X) \ mod f (X) = X \ cdot b_ { k}(X)-f(X)}$	${\ Displaystyle = \ suma _ {j = 1} ^ {n }{\Big (}z_{j}\cdot b_{k}(z_{j})-f(z_{j}){\Big )}\cdot {\frac {b_{j}(X)}{ b_{j}(z_{j})}}}$
	${\ Displaystyle = z_ {k} \ cdot b_ {k} (X) + \ suma _ {j = 1} ^ {n}w_{j}\cdot b_{j}(X)}$ ,

gdzie ${\ Displaystyle w_ {j} = - {\ Frac {f (z_ {j})} {b_ {j} (z_ {j})}} }$ to znowu aktualizacje Weierstrassa.

Macierz towarzysząca ƒ( X ) to zatem

${\ Displaystyle A = \ operatorname {diag} (z_ {1}, \ kropki, z_ {n}) + {\ rozpocząć {pmatrix} 1 \\\ vdots \\1 \ koniec {pmatrix}} \ cdot \ lewo ( w_{1},\kropki ,w_{n}\prawo).}$

Z przypadku transponowanej macierzy twierdzenia Gershgorina o okręgu wynika, że ​​​​wszystkie wartości własne A , to znaczy wszystkie pierwiastki ƒ ( X ), są zawarte w związku dysków ${\ Displaystyle D(a_{k,k},r_{k})}$ o promieniu ${\ Displaystyle r_ {k} = \ suma _ {j \ neq k} {\ duży |} a_ {j, k} {\ duży |}}$ .

Tutaj mamy $}$ , więc centra są kolejnymi iteracjami iteracji Weierstrassa i promieniami ${\ displaystyle r_ {k} = (n-1) \ lewo | w_ {k} \ prawo |},$ które są wielokrotnościami aktualizacji Weierstrassa. Jeśli korzenie ƒ ( X ) są dobrze izolowane (w stosunku do precyzji obliczeniowej), a punkty ${\ Displaystyle z_ {1}, \ kropki, z_ {n} \ in \ mathbb {C} }$ są wystarczająco bliskimi przybliżeniami do tych pierwiastków, wtedy wszystkie krążki staną się rozłączne, więc każdy z nich będzie zawierał dokładnie jedno zero. Punkty środkowe okręgów będą lepszymi przybliżeniami zer.

Każda macierz $sprzężona$ również macierzą ƒ ( X Wybór T jako macierzy diagonalnej pozostawia niezmiennik struktury A. Korzeń bliski $niezależnie$$zawarty$ dowolnym odizolowanym okręgu środkiem T . Wybór optymalnej diagonalnej macierzy T dla każdego indeksu skutkuje lepszymi oszacowaniami (zob. odn. Petkovic i in. 1995).

Wyniki konwergencji

Związek między rozwinięciem szeregu Taylora a metodą Newtona sugeruje, że odległość od ${ \displaystyle O{\big (}|w_{k}|^{2}{\big)}}$$pierwiastka$ rzędu , jeśli korzeń jest dobrze odizolowany od pobliskich korzeni, a przybliżenie jest wystarczająco blisko korzenia. Więc po zbliżeniu, metoda Newtona jest zbieżna kwadratowo ; to znaczy, błąd jest podnoszony do kwadratu z każdym krokiem (co znacznie zmniejszy błąd, gdy będzie mniejszy niż 1). W przypadku metody Duranda – Kernera zbieżność jest kwadratowa, jeśli wektor ${\ Displaystyle {\ vec {z}} = (z_ {1}, \ kropki, z_ { n})}$ jest bliskie pewnej permutacji wektora pierwiastków f .

Dla konkluzji o zbieżności liniowej istnieje bardziej konkretny wynik (zob. odn. Petkovic i in. 1995). Jeśli wektor początkowy i jego wektor Weierstrassa aktualizuje się $} = (w_ {1 },\dots ,w_{n})}$${$ spełnia nierówność

$\ Displaystyle \ max _ {1 \ równoważnik k \ równoważnik n} | w_ {k} | \ równoważnik {\ Frac {1} {5n}} \ min _ {1 \ równoważnik j <k \ równoważnik n} | z_ {k}-z_{j}|,}$

wtedy ta nierówność obowiązuje również dla wszystkich iteracji, wszystkich dysków inkluzji ${\ Displaystyle D {\ duży (} z_ {k} + w_ {k}, ( n-1)|w_{k}|{\big )}}$ są rozłączne, a zbieżność liniowa ze współczynnikiem skrócenia równym 1/2 jest zachowana. Ponadto dyski inkluzyjne mogą w tym przypadku być wybrane jako

${\ Displaystyle D \ lewo (z_ {k} + w_ {k}, {\ tfrac {1} {4} }|w_{k}|\right),\quad k=1,\kropki ,n,}$

z których każdy zawiera dokładnie jedno zero z f .

Brak ogólnej konwergencji

Metoda Weierstrassa / Duranda-Kernera generalnie nie jest zbieżna: innymi słowy, nie jest prawdą, że dla każdego wielomianu zbiór wektorów początkowych, który ostatecznie zbiega się do pierwiastków, jest otwarty i gęsty. W rzeczywistości istnieją otwarte zbiory wielomianów, które mają otwarte zbiory wektorów początkowych, które zbiegają się w okresowe cykle inne niż pierwiastki (patrz Reinke i in.)

• Weierstraß, Karl (1891). „Neuer Beweis des Satzes, dass jede ganze racjonale Function einer Veränderlichen dargestellt werden kann als ein Product aus linearen Functionen derselben Veränderlichen” . Sitzungsberichte der königlich preussischen Akademie der Wissenschaften zu Berlin .
• Durand, E. (1960). „Równania typu F ( x ) = 0: Racines d'un polynom” . w Massonie; i in. (red.). Rozwiązania Numériques des Equations Algébriques . Tom. 1.
•   Kerner, Immo O. (1966). „Ein Gesamtschrittverfahren zur Berechnung der Nullstellen von Polynomen”. Matematyka numeryczna . 8 (3): 290–294. doi : 10.1007/BF02162564 . S2CID 115307022 .
• Prešić, Marica (1980). „Twierdzenie o zbieżności dla metody jednoczesnego wyznaczania wszystkich zer wielomianu” (PDF) . Publications de l'Institut Mathématique . Nowa seria. 28 (42): 158–168.
•    Petkovic, MS, Carstensen, C. i Trajkovic, M. (1995). „Formuła Weierstrassa i metody znajdowania zera”. Matematyka numeryczna . 69 (3): 353–372. CiteSeerX 10.1.1.53.7516 . doi : 10.1007/s002110050097 . S2CID 18594004 . {{ cite journal }} : CS1 maint: wiele nazwisk: lista autorów ( link )
• Bo Jacoby, Nulpunkter for polynomier , CAE-nyt (czasopismo Dansk CAE Gruppe [duńska grupa CAE]), 1988.
• Agnethe Knudsen, Numeriske Metoder (notatki z wykładów), Københavns Teknikum.
• Bo Jacoby, Numerisk løsning af ligninger , Bygningsstatiske meddelelser (wydane przez Duńskie Towarzystwo Nauk Strukturalnych i Inżynierii), tom 63 no. 3-4, 1992, s. 83-105.
• Gourdon, Xavier (1996). Combinatoire, Algorithmique et Geometrie des Polynomes . Paryż: École Polytechnique. Zarchiwizowane od oryginału w dniu 2006-10-28 . Źródło 2006-08-22 .
• Victor Pan (maj 2002): Jednowymiarowe wyszukiwanie pierwiastków wielomianowych z niższą precyzją obliczeniową i wyższymi współczynnikami zbieżności . Tech-Report, City University of New York
• Neumaier, Arnold (2003). „Zawieranie klastrów zer wielomianów” . Journal of Computational and Applied Mathematics . 156 (2): 389–401. Bibcode : 2003JCoAM.156..389N . doi : 10.1016/S0377-0427(03)00380-7 .
• Jan Verschelde, Metoda Weierstrassa (znana również jako metoda Duranda-Kernera) , 2003.
• Bernhard Reinke, Dierk Schleicher i Michael Stoll, `` Wyszukiwarka korzeni Weierstrassa nie jest generalnie zbieżna , 2020

Linki zewnętrzne

• Ada Generic_Roots przy użyciu metody Duranda – Kernera (archiwum) - implementacja typu open source w Adzie
• Wielomianowe pierwiastki — implementacja typu open source w Javie
• Wyodrębnianie pierwiastków z wielomianów: metoda Duranda – Kernera - zawiera demonstrację apletu Java