Metoda LAGUERRE za - Laguerre's method

W analizie numerycznej , metoda LAGUERRE za to algorytm korzeń rozpoznawczych dostosowany do wielomianów . Innymi słowy, sposób Laguerre'a można stosować numerycznie rozwiązać równanie p ( x ) = 0 dla danego wielomianu p ( x ) . Jedną z najbardziej przydatnych właściwości tej metody jest to, że jest z szeroko zakrojonych badań empirycznych, bardzo blisko do bycia „najpewniejszy” sposób, co oznacza, że jest on prawie na pewno zawsze zbiegają się do jakiegoś pierwiastka wielomianu, bez względu na to, co przypuszczalne jest wybrany. Metoda ta została nazwana na cześć Edmond Laguerre'a , francuski matematyk.

Definicja

Algorytm sposobu Laguerre'a znaleźć jeden pierwiastek wielomianu p ( x ) stopnia n wynosi:

• Wybierz początkową przypuszczenie x ₀
• Dla k = 0, 1, 2, ...
  • Jeśli jest bardzo mała, wyjść z pętli${\ Displaystyle P (x_ {k})}$
  • Obliczać ${\ Displaystyle G = {\ Frac {s '(x_ {k})} P {(x_ {k})}}}$
  • Obliczać ${\ Displaystyle H = G ^ {2} - {\ Frac {s '' (x_ {k})} P {(x_ {k})}}}$
  • Oblicz , gdzie znak się wybierać tak, aby mianownik o większej wartości bezwzględnej, w celu uniknięcia utraty wagi wraz z postępem iteracji.${\ Displaystyle A = {\ Frac {n} {G \ Pm {\ sqrt {(n-1) (NH-G ^ {2})}}}}}$
  • Zestaw ${\ Displaystyle x_ {k + 1} = x_ {k} -a}$
• Powtarzać aż jest na tyle mała, czy została osiągnięta maksymalna liczba iteracji.

Jeżeli główny Stwierdzono, odpowiedni współczynnik liniowy może być usunięty z p . Ten krok deflacja zmniejsza stopień wielomianu o jeden, tak że w końcu, przybliżeń dla wszystkich korzeni p można znaleźć. Należy jednak pamiętać, że może prowadzić do deflacji przybliżonych czynniki, które znacznie różnią się od odpowiadających dokładnie czynników. Ten błąd jest przynajmniej jeśli korzenie znajdują się w celu zwiększenia wielkości.

Pochodzenie

Zasadnicze twierdzenie algebry stwierdza, że każdy n ty stopień wielomianu można zapisać w postaci ${\ P} displaystyle$

${\ Displaystyle p (x) = C (X-x_ {1}) (X-x_ {2}) \ cdots (X-x_ {n})}$

takie, że gdzie są korzenie wielomianu. Jeżeli weźmiemy pod uwagę logarytm naturalny z obu stron, okazuje się, że ${\ Displaystyle x_ {k}}$${\ Displaystyle (k = 1,2, ..., n)}$

${\ Displaystyle \ ln | p (x) | = \ ln | C | + \ ln | x-x_ {1} | + \ ln | x-x_ {2} | + \ cdots + \ ln | x-x_ { n} |.}$

Oznaczmy przez pochodną

${\ Displaystyle G = {\ Frac {d} {dx}} \ ln | p (x) | = {\ Frac {1} {x x_ {1}}} + {\ Frac {1} {x x_ {2}}} + \ cdots + {\ Frac {1} {x x_ {n}}}}$

i zanegowane drugiej pochodnej o

${\ Displaystyle H = - {\ Frac {d ^ {2}} {dx ^ {2}}} \ ln | p (x) | = {\ Frac {1} {(x x_ {1}) ^ { 2}}} + {\ Frac {1} {(x x_ {2}) ^ {2}}} + \ cdots + {\ Frac {1} {(x x_ {n}) ^ {2}} }.}$

Następnie zrobić to, co nazywa „Acton drastyczne zestaw założeń”, że korzeń szukamy, powiedzmy, jest w pewnej odległości od naszej odgadnięcia , a wszystkie pozostałe korzenie są zgrupowane w pewnej odległości. Jeśli oznaczymy tej odległości ${\ X_ displaystyle {1}}$${\ Displaystyle X}$

${\ Displaystyle A = x x_ {1} \}$

i

${\ Displaystyle b = X-x_ {i} \ quad i = 2,3, \ ldots n}$

Następnie nasz równanie można zapisać jako ${\ Displaystyle G}$

${\ Displaystyle G = {\ Frac {1} {A}} + {\ Frac {n-1} {b}}}$

a wyrażenie staje ${\ Displaystyle H}$

${\ Displaystyle H = {\ Frac {1} {A ^ {2}}} + {\ Frac {n-1} {b ^ {2}}}.}$

Rozwiązanie tych równań dla stwierdzamy, że ${\ A} displaystyle$

${\ Displaystyle A = {\ Frac {n} {G \ Pm {\ sqrt {(n-1) (NH-G ^ {2})}}}}}$,

gdzie pierwiastek kwadratowy liczby zespolonej dobiera się w celu wytworzenia większej wartości bezwzględnej mianowniku lub równoważnie, aby spełniać wymagania:

${\ Displaystyle \ OperatorName {Re} \ ({\ overline {G}} {\ sqrt {(n-1) (NH-G ^ {2})}} \,) 0>}$,

gdzie Re oznacza części rzeczywistej liczby zespolonej, a G jest sprzężona z G ; lub

${\ Displaystyle A = {\ Frac {P (x)} {P '(x)}} \ cdot \ lewo ({\ Frac {1} {n}} + {\ Frac {n-1} {n}} \ {\ sqrt {1 - {\ Frac {n} {n-1}} \ {\ Frac {P (x) P '' (x)} {P '(x) ^ {2}}}} } \ prawej) ^ {- 1}}$,

gdzie pierwiastek kwadratowy liczby zespolonej jest wybierany, aby mieć nieujemną część rzeczywistą.

Dla małych wartościach P, ( x ), wzór ten różni się od przesunięcia trzeciego rzędu metody Halleya błędem w O ( P ( x ) ³ ) , więc zbieżność blisko głównego zostaną sześciennych,.

Zauważ, że nawet jeśli „drastyczne zbiór założeń” nie działa z jakiegoś szczególności wielomianu P ( x ) , p ( x ) może być przekształcona w pokrewnej wielomianu R , dla którego założenia są prawidłowe, na przykład poprzez przesunięcie pochodzenie Ku odpowiednia liczba zespolona wag , dając q ( x ) = p ( x - w ) , aby dać odrębnych korzenie różne wartości amplitudy w razie potrzeby (co będzie, jeśli niektóre korzenie sprzężenie zespolone), i następnie się r z q ( x ) przez wielokrotne zastosowania transformacji korzeń kwadratury stosowany w metodzie Graeffe za tyle razy, aby mniejsze korzenie znacznie mniejsze niż największy root (i tak, skupione w porównaniu); przybliżone pierwiastek z metodą Graeffe może być następnie wykorzystany do rozpoczęcia nowego powtórzenie metody Laguerre'a w dniu badania . Przybliżoną root p ( x ) można następnie otrzymać w prosty niż dla R .

W przypadku wprowadzenia silniejsze założenie, że te określenia G odpowiadającą korzeni x _I , I = 2, 3, ..., n jest pomijalnie mała w porównaniu do terminu odpowiadającej korzenia x ₁ , prowadzi to do sposobu Newtona .

Nieruchomości

Strefa przyciągania metodą Laguerre'a za wielomianu x ^ 4 2 * x ^ 3 + 3 * x ^ 2 + 4 * X + 1

Jeśli x jest prosty pierwiastkiem wielomianu p ( x ) , a następnie w sposób zbieżny Laguerre'a kubiczną gdy przypuszczalne x ₀ jest wystarczająco blisko głównego X . Z drugiej strony, jeśli x jest wielokrotnością korzenia to zbieżność jest linią prostą. Uzyskuje się to z karą obliczania wartości dla wielomianu i jego pierwszej i drugiej pochodnej w każdym etapie iteracji.

Główną zaletą metody LAGUERRE jest to, że jest niemal gwarantowane są zbieżne do jakiegoś pierwiastka wielomianu bez względu na to, gdzie początkowe przybliżenie jest wybrany . Jest to w przeciwieństwie do innych metod, takich jak metoda Newtona Raphsona które mogą nie zbiegają do słabo wybranych początkowych prób. Może nawet zbieżne złożonego korzenia wielomianu, ponieważ pierwiastek podejmowane w celu obliczenia powyżej mogą być liczbą ujemną. Może to być uważane za korzyść lub odpowiedzialności w zależności od zastosowania, do którego jest stosowana metoda. Dowody empiryczne wykazały, że brak zbieżności jest niezwykle rzadkie, dzięki czemu jest dobrym kandydatem do algorytmu wielomian korzenia rozpoznawczej ogólnego przeznaczenia. Jednakże, ze względu na dość ograniczone teoretycznego zrozumienia algorytmu wielu analityków liczbowe niechętnie go użyć jako takiego, i wolą lepiej zrozumiany metod, takich jak algorytm Jenkins-Traub , dla których bardziej stałe teoria opracowane. Niemniej jednak, algorytm jest dość prosty w obsłudze w porównaniu do innych metod „najpewniejszy”, dość łatwo być stosowany ręcznie lub przy pomocy kalkulatora gdy automatyczny komputer jest niedostępny. Szybkość, z jaką sposób zbieżny oznacza, że jedna jest tylko bardzo rzadko wymagane do obliczenia więcej niż kilka iteracji, aby uzyskać wysoką dokładność.

Referencje

• Acton, Forman S. (1970). Metody numeryczne, które działają . Harper & Row. ISBN  0-88385-450-3 .
• Goedecker, S. (1994). „Uwaga na algorytmach znaleźć Roots wielomianów”. SIAM J. Sci. Comput . 15 (5): 1059/63. doi : 10,1137 / 0915064 .
• Mekwi, Wankere R. (2001). „Metody iteracyjne dla Roots wielomianów” . Praca magisterska, University of Oxford .
• Pan, VY (1997). „Rozwiązywanie wielomian równanie: Niektóre Historia i ostatnie postępy”. SIAM Rev . 39 (2): 187-220. doi : 10,1137 / S0036144595288554 .
• Press, WH; Teukolsky, SA; Vetterling WT; Flannery, BP (2007). "Sekcja 9.5.3. Metoda LAGUERRE za" . Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN  978-0-521-88068-8 .
• Ralston, Anthony; Rabinowitz, Philip (1978). A Najpierw Kurs Analizy Numerycznej . McGraw-Hill. ISBN  0-07-051158-6 .