Обратная параболическая интерполяция

Обратная параболическая интерполяция — итерационный численный метод нахождения корня уравнения ${\displaystyle f(x)=0}$, где ${\displaystyle f(x)}$ — непрерывная функция одной переменной. Идея метода состоит в параболической интерполяции функции по трём точкам. Но в отличие от метода Мюллера интерполируется функция обратная к ${\displaystyle f(x)}$. Метод эффективнее более простых методов, если функция дважды дифференцируема. Алгоритм используется в качестве составной части популярного метода Брента.

Алгоритм обратной параболической интерполяции задаётся рекуррентной формулой:

${\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},}$

где ${\displaystyle f_{k}=f(x_{k})}$. Как следует из формулы, для начала вычислений необходимы три начальные точки ${\displaystyle x_{0},x_{1},x_{2}}$ и желательно, но не обязательно, чтобы корень находился в задаваемом ими отрезке.

Рассмотрим три точки ${\displaystyle x_{n-2},x_{n-1},x_{n}}$ как значения функции от аргументов ${\displaystyle f_{n-2},f_{n-1},f(n)}$. Интерполяционный многочлен Лагранжа для этих точек будет выглядеть следующим образом

${\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}.}$

Поскольку мы ищем корень ${\displaystyle f(x)}$ , то ${\displaystyle y=f(x)=0}$ и эта замена даёт искомую рекуррентную формулу.

Если функция достаточно гладкая, начальные точки близки к корню и корень не является экстремумом, то метод сходится очень быстро. Порядок асимптотической сходимости метода около 1,8. Однако иногда метод не эффективен или вообще не приводит к результату. В частности, если два значения функции случайно совпали, то продолжение итераций невозможно. Этот недостаток устраняется комбинированием метода с более робастными методами меньшей скорости сходимости, что, в частности, сделано в методе Брента.

Обратная параболическая интерполяция тесно связана с методом Мюллера, который имеет примерно такой же порядок сходимости и с методом секущих, порядок сходимости которого меньше. В отличие от метода Ньютона, который имеет большую скорость сходимости (2), метод не требует вычисления производных.

• James F. Epperson, An introduction to numerical methods and analysis, pages 182—185, Wiley-Interscience, 2007. ISBN 978-0-470-04963-1

В статье есть список источников, но не хватает сносок. Без сносок сложно определить, из какого источника взято каждое отдельное утверждение. Вы можете улучшить статью, проставив сноски на источники, подтверждающие информацию. Сведения без сносок могут быть удалены. (1 сентября 2013)