Odwrotna interpolacja kwadratowa

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.

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}.}$

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.

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.

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.

• 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