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

Metoda

Algorytm odwrotnej interpolacji kwadratowej jest definiowany przez równanie rekurencyjne

${\displaystyle {\begin{aligned}x_{n+1}&={\frac {f_{n-1}f_{n}}{(f_{n-2}-f_{n-1})(f_{n-2}-f_{n})}}x_{n-2}\\[1ex]&+{\frac {f_{n-2}f_{n}}{(f_{n-1}-f_{n-2})(f_{n-1}-f_{n})}}x_{n-1}\\[1ex]&+{\frac {f_{n-2}f_{n-1}}{(f_{n}-f_{n-2})(f_{n}-f_{n-1})}}x_{n},\end{aligned}}}$

gdzie ${\displaystyle f_{k}=f(x_{k}).}$ Jak można zauważyć z zależności rekurencyjnej, ta metoda wymaga trzech początkowych wartości: ${\displaystyle x_{0},}$ ${\displaystyle x_{1}}$ i ${\displaystyle x_{2}.}$

Opis metody

Używamy trzech poprzedzających iteracji ${\displaystyle x_{n-2},}$ ${\displaystyle x_{n-1}}$ i ${\displaystyle x_{n}}$ z ich trzema wartościami funkcji ${\displaystyle f_{n-2},}$ ${\displaystyle f_{n-1}}$ i ${\displaystyle f_{n}.}$ Stosując wzór interpolacji Lagrange’a do kwadratowej interpolacji odwrotności ${\displaystyle f,}$ otrzymamy

${\displaystyle {\begin{aligned}f^{-1}(y)&={\frac {(y-f_{n-1})(y-f_{n})}{(f_{n-2}-f_{n-1})(f_{n-2}-f_{n})}}x_{n-2}\\[1ex]&+{\frac {(y-f_{n-2})(y-f_{n})}{(f_{n-1}-f_{n-2})(f_{n-1}-f_{n})}}x_{n-1}\\[1ex]&+{\frac {(y-f_{n-2})(y-f_{n-1})}{(f_{n}-f_{n-2})(f_{n}-f_{n-1})}}x_{n}.\end{aligned}}}$

Patrzymy na pierwiastek ${\displaystyle f,}$ podstawiając ${\displaystyle y=f(x)=0}$ w powyższym równaniu i jego rezultatach w powyższej formule rekurencyjnej.

Zachowanie

Asymptotyczne zachowanie jest bardzo dobre: ogólnie, iteracje ${\displaystyle x_{n}}$ 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 ${\displaystyle f_{n-2},}$ ${\displaystyle f_{n-1}}$ i ${\displaystyle f_{n}}$ 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ów

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 ${\displaystyle f}$ zamiast odwrotności ${\displaystyle f,}$ dostajemy metodę Mullera.

Linki zewnętrzne

• James F. Epperson, An introduction to numerical methods and analysis, s. 182–185, Wiley-Interscience, 2007. ISBN 978-0-470-04963-1.
• Lecture in Numerical Methods from 17. March 2015. web.info.uvt.ro. [zarchiwizowane z tego adresu (2018-03-04)].
• Lecture 07 Finding Roots – Brent’s Methods
• archive.ph. fourier.eng.hmc.edu. [zarchiwizowane z tego adresu (2017-04-25)]. The Bisection and Secant methods