Invers parabolisk interpolation

Invers parabolisk interpolation är en iterativ numerisk metod för att hitta roten till ekvationen , där är en kontinuerlig funktion av en variabel. Tanken med metoden är den paraboliska interpoleringen av en funktion över tre punkter. Men till skillnad från Muller-metoden interpoleras funktionen invers till . Metoden är effektivare än enklare metoder om funktionen är dubbelt differentierbar. Algoritmen används som en komponent i den populära Brent - metoden . $f(x)=0$ $f(x)$ $f(x)$

Metod

Den inversa paraboliska interpolationsalgoritmen ges av den rekursiva formeln :

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

var . Som följer av formeln, för att starta beräkningarna, behövs tre startpunkter och det är önskvärt, men inte nödvändigt, att roten ligger i det segment som anges av dem. $f_{k}=f(x_{k})$ ${\displaystyle x_{0},x_{1},x_{2))$

Bevis på metodformeln

Betrakta tre punkter som värdena för en funktion av argumenten . Lagrange-interpolationspolynomet för dessa punkter kommer att se ut så här ${\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}.

Eftersom vi letar efter en rot , ger denna ersättning också den önskade återkommande formeln. $f(x)$ $y=f(x)=0$

Konvergens

Om funktionen är tillräckligt jämn, de initiala punkterna är nära roten, och roten inte är ett extremum, konvergerar metoden mycket snabbt. Ordningen för asymptotisk konvergens av metoden är cirka 1,8. Men ibland är metoden inte effektiv eller leder inte till något resultat alls. I synnerhet, om två funktionsvärden av misstag sammanfaller, kan iterationer inte fortsätta. Denna nackdel elimineras genom att kombinera metoden med mer robusta metoder med lägre konvergenshastighet, vilket i synnerhet görs i Brentmetoden.

Jämförelse med andra metoder

Invers parabolisk interpolation är nära besläktad med Mullers metod, som har ungefär samma konvergensordning, och till sekantmetoden , som har en lägre konvergensordning. Till skillnad från Newtons metod , som har en hög konvergenshastighet (2), kräver metoden inte beräkning av derivat.

Länkar

James F. Epperson , En introduktion till numeriska metoder och analys , sidorna 182-185, Wiley-Interscience, 2007. ISBN 978-0-470-04963-1