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ą:
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:
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:
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
Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
Michał Ładanowski | Java | .java | .java | ***** / 6 |
Poprawiony: 29 września 2012 16:31