algorytm.org

Metoda Laguerre’a

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Metoda Laguerre’a
Ocena użytkowników:***** / 9
SłabyŚwietny 
Wpisany przez Michał Ładanowski, 22 lutego 2011 21:42

Metoda Laguerre’a pozwala obliczać miejsca zerowe wielomianów oraz funkcji analitycznych, lokalnie rozwijalnych w szereg potęgowy do wyrazów rzędu n. Jest to metoda zadana następującą iteracją:
z_{i+1}=z_{i}-\frac{nP_{n}(z_{i})}{P'_{n}(z_{i})\pm\sqrt{(n-1)((n-1)[P'_{n}(z_{i})]^{2}-nP_{n}(z_{i})P''_{n}(z_{i}))}}


gdzie:
zi – początkowe przybliżenie (jeśli nie znamy może to być dowolna liczba),
n – stopień wielomianu,
Pn – wielomian stopnia n.

Obliczenie pierwszej i drugiej pochodnej w przypadku wielomianów nie stanowi problemu.
Znak w mianowniku dobieramy tak, aby jego moduł był większy.

Idea algorytmu:
  • szukamy miejsca zerowego wielomianu Pn metodą Laguerre’a.
  • obniżamy stopień wielomianu(deflacja) Pn dzięki czemu unikamy sytuacji, w której metoda zbiega do wcześniej znalezionego miejsca zerowego (z1):
    Czyli znaleźć taki wielomian Pn-1: Pn(z) = (z – z1) Pn-1(z).
  • Szukamy miejsce zerowe(z'2) wielomianu stopnia obniżonego metodą Laguerre’a. Następnie wygładzamy to miejsce poprzez użycie metody Laguerre’a na niewydzielonym (Pn) wielomianie z punktem początkowym z'2. Wygładzenie takie ma na celu uchronienie się przed uzyskaniem zaburzonego miejsca zerowego z'2, którego przyczyną może być nawet niewielkie zaburzenie współczynników wielomianu wyliczonych przy operacji deflacji.


W skrócie:
ML – metoda Laguerre’a
Mamy Pn.
Szukamy jego miejsce zerowe za pomocą ML i uzyskujemy z1.
Szukamy Pn-1 : Pn(z) = (z – z1) Pn-1(z).
Szukamy miejsce zerowe Pn-1 metodą Laguerre’a i uzyskujemy z'2.
Wygładzamy to miejsce poprzez ML na wielomianie Pn z punktem startowym z'2, dostajemy z2.
Szukamy Pn-2 : Pn(z) = (z – z1)(z – z2) Pn-2(z).
Szukamy miejsce zerowe Pn-2 metodą Laguerre’a i uzyskujemy z'3.
Wygładzamy to miejsce poprzez ML na wielomianie Pn z punktem startowym z'3, dostajemy z3.
itd....

Uwagi końcowe:
  • Miejsc zerowych szukamy numerycznie (czyli ze skończoną precyzją). Tak więc jeśli jednym z miejsc zerowych jest np. 2 + 12323E-10i oznaczać to może oczywiście, że miejscem zerowym jest liczba rzeczywista 2.
  • metoda jest zbieżna sześciennie do pojedynczych miejsc zerowych.
  • metoda jest zbieżna liniowo do wielokrotnych miejsc zerowych.

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Michał ŁadanowskiJava
.java
.java
***** / 6
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 29 września 2012 16:31
Dodaj komentarz