Interpolare parabolică inversă

Interpolarea parabolică inversă este o metodă numerică iterativă pentru găsirea rădăcinii ecuației , unde este o funcție continuă a unei variabile. Ideea metodei este interpolarea parabolică a unei funcții în trei puncte. Dar, spre deosebire de metoda Muller, funcția inversă este interpolată . Metoda este mai eficientă decât metodele simple dacă funcția este de două ori diferențiabilă. Algoritmul este folosit ca o componentă a metodei populare Brent . $f(x)=0$ $f(x)$ $f(x)$

Metoda

Algoritmul de interpolare parabolică inversă este dat de formula recursivă :

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

unde . După cum rezultă din formulă, pentru a începe calculele, sunt necesare trei puncte de plecare și este de dorit, dar nu necesar, ca rădăcina să fie în segmentul specificat de acestea. $f_{k}=f(x_{k})$ ${\displaystyle x_{0},x_{1},x_{2))$

Dovada formulei metodei

Considerați trei puncte ca valori ale unei funcție a argumentelor . Polinomul de interpolare Lagrange pentru aceste puncte va arăta astfel $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}.

Deoarece căutăm o rădăcină , atunci această înlocuire oferă și formula recurentă dorită. $f(x)$ $y=f(x)=0$

Convergență

Dacă funcția este suficient de netedă, punctele inițiale sunt aproape de rădăcină, iar rădăcina nu este un extremum, atunci metoda converge foarte repede. Ordinea convergenței asimptotice a metodei este de aproximativ 1,8. Cu toate acestea, uneori metoda nu este eficientă sau nu duce deloc la un rezultat. În special, dacă două valori ale funcției coincid accidental, atunci iterațiile nu pot fi continuate. Acest dezavantaj este eliminat prin combinarea metodei cu metode mai robuste de rată de convergență mai mică, ceea ce, în special, se realizează în metoda Brent.

Comparație cu alte metode

Interpolarea inversă parabolică este strâns legată de metoda lui Muller, care are aproximativ același ordin de convergență, și de metoda secantei , care are un ordin inferior de convergență. Spre deosebire de metoda lui Newton , care are o rată mare de convergență (2), metoda nu necesită calculul derivatelor.

Link -uri

James F. Epperson , O introducere în metodele numerice și analiză , paginile 182-185, Wiley-Interscience, 2007. ISBN 978-0-470-04963-1