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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Метод[править | править вики-текст]

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

 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,

где  f_k = f(x_k). Как следует из формулы, для начала вычислений необходимы три начальные точки x_0, x_1, x_2 и желательно, но не обязательно, чтобы корень находился в задаваемом ими отрезке.

Доказательство формулы метода[править | править вики-текст]

Рассмотрим три точки  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.

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

Сходимость[править | править вики-текст]

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


Сравнение с другими методами[править | править вики-текст]

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

Ссылки[править | править вики-текст]