Käänteinen parabolinen interpolointi

Käänteinen parabolinen interpolointi on iteratiivinen numeerinen menetelmä yhtälön juuren löytämiseksi , jossa on yhden muuttujan jatkuva funktio. Menetelmän idea on funktion parabolinen interpolointi kolmen pisteen yli. Mutta toisin kuin Mullerin menetelmä, funktio käänteisfunktio interpoloidaan . Menetelmä on tehokkaampi kuin yksinkertaisemmat menetelmät, jos funktio on kahdesti differentioituva. Algoritmia käytetään osana suosittua Brent - menetelmää . $f(x) = 0$ $f(x)$ $f(x)$

Menetelmä

Käänteinen parabolinen interpolointialgoritmi saadaan rekursiivisella kaavalla :

x_{n+1}={\frac {f_{n-1}f_{n}}{(f_{n-2}-f_{n-1})(f_{n-2}-f_ {n})}}x_{n-2}+{\frac {f_{n-2}f_{n}}{(f_{n-1}-f_{n-2})(f_{n-1 }-f_{n})}}x_{n-1}

{}+{\frac {f_{n-2}f_{n-1}}{(f_{n}-f_{n-2})(f_{n}-f_{n-1}) }}x_{n},

missä . Kuten kaavasta seuraa, laskelmien aloittamiseen tarvitaan kolme lähtökohtaa ja on toivottavaa, mutta ei välttämätöntä, että juuri on niiden määrittelemässä segmentissä. $f_{k}=f(x_{k})$ ${\displaystyle x_{0},x_{1},x_{2))$

Todiste menetelmäkaavasta

Tarkastellaan kolmea pistettä argumenttien funktion arvoina . Näiden pisteiden Lagrangen interpolaatiopolynomi näyttää tältä ${\displaystyle x_{n-2},x_{n-1},x_{n))$ $f_{n-2},f_{n-1},f(n)$

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}+{\frac {(y-f_{n-2})(y-f_{n})}{(f_ {n-1}-f_{n-2})(f_{n-1}-f_{n})}}x_{n-1}

{}+{\frac {(y-f_{n-2})(y-f_{n-1})}{(f_{n}-f_{n-2})(f_{n} -f_{n-1})}}x_{n}.

Koska etsimme juuria , tämä korvaus antaa myös halutun toistuvan kaavan. $f(x)$ $y=f(x)=0$

Lähentyminen

Jos funktio on riittävän tasainen, alkupisteet ovat lähellä juuria, eikä juuri ole ääripää, menetelmä konvergoi nopeasti. Menetelmän asymptoottinen konvergenssi on noin 1,8. Joskus menetelmä ei kuitenkaan ole tehokas tai se ei johda tulokseen ollenkaan. Erityisesti, jos kaksi funktioarvoa vahingossa osuvat yhteen, iteraatioita ei voida jatkaa. Tämä epäkohta on eliminoitu yhdistämällä menetelmä robustimpiin menetelmiin, joilla on pienempi konvergenssinopeus, mikä tehdään erityisesti Brent-menetelmässä.

Vertailu muihin menetelmiin

Käänteinen parabolinen interpolointi liittyy läheisesti Mullerin menetelmään, jolla on suunnilleen sama konvergenssijärjestys, ja sekanttimenetelmään , jolla on alempi konvergenssikerta. Toisin kuin Newtonin menetelmä , jolla on korkea konvergenssiaste (2), menetelmä ei vaadi johdannaisten laskemista.

Linkit

James F. Epperson , Johdatus numeerisiin menetelmiin ja analyysiin , sivut 182-185, Wiley-Interscience, 2007. ISBN 978-0-470-04963-1