Математические и алгоритмические основы решения задачи

2 Математические и алгоритмические основы решения задачи

 

Пусть  имеет первую и вторую производную. Разложим  в ряд Тейлора в некоторой точке , ограничиваясь при этом тремя членами разложения:

. (3)

Иными словами, аппроксимируем нашу функцию в точке , параболой (рисунок 1). Для этой параболы можно аналитически вычислить положение экстремума как корень уравнения первой производной от (3):

.

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

Рисунок 4. Поиск минимума функции методом парабол

Обычно в практических реализациях данного метода не используют аналитический вид первой и второй производных . Их заменяют конечно-разностными аппроксимациями. Наиболее часто берут симметричные разности с постоянным шагом h:

Это эквивалентно аппроксимации функции параболой, проходящей через три близкие точки

, , .

Окончательное выражение, по которому можно строить итерационный процесс, таково:

(4)

Данный метод отличается от других методом поиска минимума высокой скоростью сходимости. Вблизи экстремума, вплоть до расстояний ~, сходимость практически не отличается от квадратичной. Однако алгоритм требует постоянного контроля сходимости. Например, итерационный процесс будет сходиться к минимуму, если:

1)    знаменатель формулы

должен быть > 0. Если это не так, нужно сделать шаг в обратном направлении, причем достаточно большой. Обычно в итерационном процессе полагают

.

Иногда ради упрощения расчетов полагают

,

однако это существенно уменьшает скорость сходимости.

2)  если это не так, то от  следует сделать шаг

,

с .

Если и при этом условие убывания не выполнено, уменьшают τ и вновь делают шаг.

 

3 Функциональные модели и блок-схемы решения задачи

 

Функциональные модели и блок-схемы решения задачи представлены на рисунке 5, 6.

Используемые обозначения:

· X0, MIN_VAL – начальная точка;

· H, MAX_VAL – конечная точка;

· EPS – требуемая точность;

· FN – функция для вычисления минимума;

· X1 – вспомогательная точка;

· X2 – вспомогательная точка;

· XN – вспомогательная точка;

· F_X0 – функция от начальной точки X0;

· F_X1 – функция от вспомогательной точки X1;

· F_X2 – функция от вспомогательной точки X2;

· F_XN – функция от вспомогательной точки XN;

· Q – рабочая переменная;

· A – рабочая переменная;

· B – рабочая переменная;

· C – рабочая переменная;

· D – рабочая переменная;

· Z – рабочая переменная;

· K – рабочая переменная.

Рисунок 5 – Блок-схема решения задачи для функции PARABL_METHOD

Рисунок 6 – Функциональная модель решения задачи для поиска минимума