Inverzní kvadratická interpolace - Inverse quadratic interpolation - Wikipedia

v numerická analýza, inverzní kvadratická interpolace je algoritmus hledání kořenů, což znamená, že se jedná o algoritmus pro řešení rovnic tvaru F(X) = 0. Myšlenkou je použít kvadratická interpolace přiblížit inverzní z F. Tento algoritmus se sám o sobě používá jen zřídka, ale je důležitý, protože je součástí populárního Brentova metoda.

Metoda

Algoritmus inverzní kvadratické interpolace je definován pomocí relace opakování

${ displaystyle 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}}$

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

kde F_k = F(X_k). Jak je vidět z relace opakování, tato metoda vyžaduje tři počáteční hodnoty, X₀, X₁ a X₂.

Vysvětlení metody

Používáme tři předchozí iteráty, X_n−2, X_n−1 a X_n, s jejich funkčními hodnotami, F_n−2, F_n−1 a F_n. Uplatnění Lagrangeův interpolační vzorec kvadratická interpolace na inverzní k F výnosy

${ displaystyle 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}}$

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

Hledáme kořen F, takže dosadíme y = F(X) = 0 ve výše uvedené rovnici a výsledkem je výše uvedený rekurzní vzorec.

Chování

Asymptotické chování je velmi dobré: obecně se opakuje X_n jakmile se přiblíží, rychle konvergují ke kořenu. Výkon je však často velmi špatný, pokud počáteční hodnoty nejsou blízké skutečnému kořenu. Například pokud náhodou dvě z hodnot funkcí F_n−2, F_n−1 a F_n shodovat, algoritmus úplně selže. Inverzní kvadratická interpolace se tedy zřídka používá jako samostatný algoritmus.

Pořadí této konvergence je přibližně 1,84, což dokazuje Sekansová metoda analýza.

Srovnání s jinými metodami hledání kořenů

Jak je uvedeno v úvodu, inverzní kvadratická interpolace se používá v Brentova metoda.

Inverzní kvadratická interpolace také úzce souvisí s některými jinými metodami hledání kořenů lineární interpolace místo kvadratické interpolace dává sekansová metoda. Interpolace F místo inverzní k F dává Mullerova metoda.

Viz také

• Postupná parabolická interpolace je související metoda, která používá paraboly k nalezení extrémů spíše než ke kořenům.

Reference

• James F. Epperson, Úvod do numerických metod a analýz, strany 182-185, Wiley-Interscience, 2007. ISBN  978-0-470-04963-1