Метод парабол

Пусть функция f(x) два раза дифференцируема на интервале [ a, b ]. В основе метода парабол лежит условие минимума:

f¢(x)=0.

Итерационный процесс метода парабол имеет вид:

. (12)

Итерационный процесс (12) является ньютоновским и вблизи экстремума с ненулевой второй производной сходится квадратично. Если f¢¢(x) = 0, то сходимость будет линейной.

Для расчета f¢(x) и f¢¢(x) используют конечные разности. С учетом этого итерационный процесс (12) будет иметь вид:× ×

- × . (13)

Внимание: на каждом шаге необходимо проверять, движемся ли мы к минимуму. Вторая производная в знаменателе (12) или (13) должна быть положительной.

Если вторая производная отрицательна, т. е. итерационный процесс сходится к максимуму, следует сделать шаг в обратном направлении.

Для этого:

вычислив x^(t+1), проверяем f(x^(t+1)) > f(x^(t)), если да, то приближение x^(t+1) использовать нельзя;

делаем шаг в сторону убывания f(x). Рассчитываем шаг по формуле h = t(x^(t+1)-x^(t)), где t - const (например, t= );

проверяем условие убывания функции. Если оно не выполняется, то t уменьшаем вдвое и делаем шаг из точки x^(t). Процесс продолжаем до тех пор, пока не добьемся убывания функции.

Замечание. Если функция имеет несколько локальных минимумов, то итерационный процесс может сойтись к любому из них.