Odwrotna interpolacja kwadratowa

W analizie numerycznej, odwrotna interpolacja kwadratowa – metodą znajdowania pierwiastków, to znaczy jest algorytmem rozwiązywania równań postaci Pomysłem jest użycie interpolacji kwadratowej do aproksymacji funkcji odwrotnej do Ten algorytm jest rzadko używany samodzielnie, ale jest ważny ponieważ stanowi część popularnej metody Brenta.

MetodaEdytuj

Algorytm odwrotnej interpolacji kwadratowej jest definiowany przez równanie rekurencyjne

 

gdzie   Jak można zauważyć z zależności rekurencyjnej, ta metoda wymaga trzech początkowych wartości:     i  

Opis metodyEdytuj

Używamy trzech poprzedzających iteracji     i   z ich trzema wartościami funkcji     i   Stosując wzór interpolacji Lagrange’a do kwadratowej interpolacji odwrotności   otrzymamy

 

Patrzymy na pierwiastek   podstawiając   w powyższym równaniu i jego rezultatach w powyższej formule rekurencyjnej.

ZachowanieEdytuj

Asymptotyczne zachowanie jest bardzo dobre: ogólnie, iteracje   zbiegają szybko do pierwiastka gdy się do niego zbliżymy. Jakkolwiek wydajność jest często całkiem zła jeśli nie wystartujemy blisko rzeczywistego pierwiastka. Na przykład jeśli przez przypadek dwie z wartości funkcji     i   pokrywają się, algorytm zawodzi całkowicie. Zatem odwrotna interpolacja kwadratowa jest rzadko używana jako algorytm samodzielny.

Rząd zbieżności jest około 1,8 jak można udowodnić przez analizę metody siecznych.

Porównanie z innymi metodami znajdowania pierwiastkówEdytuj

Jak wspomniano na wstępie, odwrotna interpolacja kwadratowa jest stosowana w metodzie Brenta.

Odwrotna interpolacja kwadratowa jest również blisko związana z innymi metodami szukania pierwiastków. Używając interpolacji liniowej zamiast kwadratowej, dostajemy metodę siecznych. Interpolując   zamiast odwrotności   dostajemy metodę Mullera.

Linki zewnętrzneEdytuj