WikiSort.ru - Не сортированное

Обратная параболическая интерполяция — итерационный численный метод нахождения корня уравнения ${\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

Для улучшения этой статьи желательно: Проставив сноски, внести более точные указания на источники.