Inverz parabola interpoláció

Az inverz parabolikus interpoláció egy iteratív numerikus módszer az egyenlet gyökerének megtalálására , ahol egy változó folytonos függvénye. A módszer ötlete egy függvény parabolikus interpolációja három ponton keresztül. De a Muller-módszerrel ellentétben a függvény inverze interpolálva van . A módszer hatékonyabb, mint az egyszerűbb módszerek, ha a függvény kétszer differenciálható. Az algoritmust a népszerű Brent-módszer összetevőjeként használják . $f(x)=0$ $f(x)$ $f(x)$

Módszer

Az inverz parabolikus interpolációs algoritmust a rekurzív képlet adja meg :

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},

ahol . A képletből következően a számítások elindításához három kiindulási pont szükséges , és kívánatos, de nem szükséges, hogy a gyök az általuk meghatározott szegmensben legyen. $f_{k}=f(x_{k})$ ${\displaystyle x_{0},x_{1},x_{2))$

A metódusképlet bizonyítása

Tekintsünk három pontot az argumentumok függvényének értékének . A Lagrange-interpolációs polinom ezekhez a pontokhoz így fog kinézni ${\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}.

Mivel gyökeret keresünk , így ez a csere is megadja a kívánt ismétlődő képletet. $f(x)$ $y=f(x)=0$

Konvergencia

Ha a függvény kellően sima, a kezdőpontok közel vannak a gyökérhez, és a gyökér nem szélsőséges, akkor a metódus nagyon gyorsan konvergál. A módszer aszimptotikus konvergenciájának sorrendje körülbelül 1,8. Néha azonban a módszer nem hatékony, vagy egyáltalán nem vezet eredményre. Különösen, ha két függvényérték véletlenül egybeesik, akkor az iterációkat nem lehet folytatni. Ezt a hátrányt kiküszöböljük, ha a módszert robusztusabb, alacsonyabb konvergencia-arányú módszerekkel kombináljuk, ami különösen a Brent-módszer esetében valósul meg.

Összehasonlítás más módszerekkel

Az inverz parabolikus interpoláció szorosan összefügg a Muller-féle módszerrel, amelynek nagyjából azonos a konvergencia-rendje, és a szekantáló módszerrel , amely alacsonyabb konvergencia-renddel rendelkezik. Ellentétben a Newton-módszerrel , amelynek nagy a konvergencia rátája (2), a módszer nem igényli a derivatívák kiszámítását.

Linkek

James F. Epperson , Bevezetés a numerikus módszerekbe és elemzésekbe , 182-185. oldal, Wiley-Interscience, 2007. ISBN 978-0-470-04963-1