ПРИЛОЖЕНИЕ. ПРОЦЕДУРЫ ОДНОМЕРНОГО ПОИСКА

Все алгоритмы для задачи (5.1), описанные в этой главе и следующих, включают задачу определения

Рассмотрим последнюю задачу одномерного поиска.

5.П.1. Основа

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

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

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

содержащему определяется интервал

который также содержит и строго входит в Всегда и либо либо

Поэтому интервалы становятся все меньше и меньше, пока не будет достигнута в пределе точка .

5.П.2. Золотое сечение или поиск Фибоначчи

Поиск золотого сечения относится к непрерывной и вогнутой функции Здесь используются параметры Фибоначчи

Следует обратить внимание на то, что

Если дан интервал длиной то очередной интервал выбирается следующим образом. Пусть — точки в интервале

Если то в качестве нового интервала берется

Если то в качестве нового интервала берется

Если то в качестве нового интервала берется либо либо Благодаря вогнутости мы убеждены, что оптимальная точка содержится в выбранном интервале (рис. 5.3).

Ясно, что этот процесс вырабатывает последовательность интервалов которые в пределе стягиваются к оптимальной точке

Рис. 5.3. Метод золотого сечения.

Здесь Следовательно,

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

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

Например, пусть в итерации мы определили и оказалось, что

Тогда Теперь нужно определить (упр. 8), а было вычислено. Таким образом, параметры Фибоначчи гарантируют, что нужно будет вычислить лишь в одной новой точке.

5.П.3. Деление пополам или поиск Больцано

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

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

Упражнения

(см. скан)

(кликните для просмотра скана)

(кликните для просмотра скана)

(см. скан)