Глава 1.Численные методы минимизации функций. Минимизация функций одной переменной методом последовательного перебора

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

1.1. Постановка задачи

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

Определение 1.1.

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

В зависимости от свойств множества и функциимножествоможет содержать одну, несколько или даже бесконечно много точек, а также возможны случаи, когдапусто.

Определение 1.2.

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

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

Определение 1.3.

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

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

Определение 1.4.

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

Из определения и существования нижней грани следует, что минимизирующая последовательность всегда существует.

Определение 1.5.

Скажем, что последовательность сходится к непустому множеству , если, где— расстояние от точкидо множества.

Заметим, что если то всегда существует минимизирующая последовательность, сходящаяся к; например, можно взять стационарную последовательность, где— какая-либо точка из. Однако не следует думать, что прилюбая минимизирующая последовательность будет сходиться к.

Определение 1.6.

Пусть -погрешность решения рассматриваемой задачи минимизации для функции cпомощью метода .-гарантированная точность метода на классе функции . Метод- оптимальный метод на классе, если, а величину-наилучшей гарантированной точностью методов на классе. Если для некоторого метода выполняется неравенство, тоназовем - оптимальным на классе.

Определение 1.7.

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

1. точка совпадает с одной из точек;

2. ;

3. , причем - ближайшие кточки среди точек.

Определение 1.8.

Пусть - класс унимодальных функций на отрезке. На задан последовательный метод , если:

1. задано правило выбора первой порции точек ,, по которым определяется тройка точек, локализующая минимум на;

2. прина отрезкепо заданному правилу выбирается вторая порция точек, и по точкамопределяется тройка, локализующая минимумна;

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

Определение 1.9.

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