2.1.3. Программная реализация метода на алгоритмическом языке

Реализация метода пассивного поиска на ЭВМ с использованием какого-либо алгоритмического языка чрезвычайно проста. Подобные задачи являются классическими при изучении языков программирования и приводятся во многих существующих учебниках. Суть их решения на ЭВМ сводится к тому, что используя тот или иной циклический алгоритм, на каждом шаге цикла последовательно вычисляется значение некоторого выражения, полученный результат сравнивается с результатом предыдущего шага и выбирается тот из них, который меньше. Поэтому, алгоритмическая простота программного решения не требует акцентирования нашего внимания, приводится здесь в качестве учебного примера и может быть использована на практике при изучении основ программирования. Для языка программирования Си возможен следующий вариант реализации задачи поиска локального минимума на отрезке методом пассивного поиска.

Программа prg1_1.c реализации метода пассивного поиска и ее результат.

(Программа осуществляет поиск локального минимума функции на интервале с шагом h = 1 для функции )

#include<stdio.h> // подключение библиотеки стандартного ввода-вывода

#include<math.h> // подключение математической библиотеки

void main(void) // главная функция

{

float min=0,x,y,k; // описание используемых в программе переменных

for(x=-5.0;x<=-2.0;x++) // основной цикл вычисления значений функции на

{ y=x*x*x-x+exp(-x); // заданном промежутке

printf("x = %4.1f y = %6.3f\n",x,y); // вывод на экран значений каждого шага

if(y<min) // цикл проверки и переопределения минимального значения функции

{ min=y;

k=x;

} //окончание внутреннего цикла

}; //окончание основного цикла

// вывод на экран результатов

// вычислений

printf("минимальное значение функции на [-5,-2] \n");

printf("y = %6.3f, точка минимума x = %4.1f\n",min,k);

}

2.2. Метод деления отрезка пополам

Аналитические и вычислительные методы, рассмотренные выше, позволяют с некоторой точностью выделить интервал (отрезок, окрестность, локализующую тройку) на заданном промежутке , в котором существует единственная точка , где функция принимает экстремальное значение. Иначе говоря, если функция унимодальная на интервале , то строится такая последовательность , при которой минимум функции находится в интервале неопределенности , т.е. .

При этом, алгоритм выбора элементов последовательности называют стратегией поиска. При заданных количествах вычислений функции оптимальной считается та стратегия, которая приводит к наименьшему интервалу неопределенности , или определяет интервал неопределенности с заданной точностью за меньшее количество вычислений. В п.2.1. мы рассмотрели метод пассивного поиска и убедились, что, не смотря на его аналитическую простоту, вычисления при поиске минимума могут оказаться достаточно громоздкими (в случае уменьшения шага интервала исследования).

Рассмотрим другие итерационные методы нахождения экстремума функции на отрезке и те стратегии, которые используются в них для определения интервала неопределенности . Один из таких методов - метод деления отрезка пополам.

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

Д ля удобства пояснения алгоритма метода обозначим исходный отрезок = (рис. 2.4), возьмем , построим точки и вычислим .

Если , то по критерию 1 заключаем, что . Если же , то .

В первом случае в качестве приближения точки возьмем и примем обозначение . Во втором случае – . Таким образом, в найден отрезок , где содержится и указано приближение . Если , то поставленная задача решена. В противном случае отрезок следует подвергнуть аналогичному дроблению (схема 2.1) и продолжить процесс дробления до тех пор, пока на некотором шаге не выполнится неравенство . При этом на отрезке будет получено приближение  точка, в которой функция достигает приближенное значение локального минимума: .

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