§ 9.3. Методы прямого поиска. Оптимальный пассивный поиск. Метод деления отрезка пополам. Методы Фибоначчи и золотого сечения

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

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

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

1. Оптимальный пассивный поиск.

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

Рис. 9.8

Оценим погрешность этого метода. Для удобства положим . В силу выбора точки справедливы неравенства Поэтому из предложения 9.2 следует, что Значит, Так как положение точки минимума х на отрезке заранее неизвестно, то для справедлива лишь следующая гарантированная оценка погрешности:

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

Пример 9.7. Используем оптимальный пассивный поиск для того, чтобы найти с точностью точку х локального минимума функции локализованную на отрезке [0, 1].

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

Таблица 9.2 (см. скан)

Так как минимальное значение достигается в точке то

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

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

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

Предложение 9.3. Если функция унимодальна на отрезке то она унимодальна и на любом отрезке

Для удобства изложения обозначим отрезок через Поиск минимума начинают с выбора на отрезке двух симметрично расположенных точек Здесь параметр метода. Далее вычисляют значения Сравнение этих значений в силу предложения 9.2 позволяет сократить отрезок локализации следующим образом:

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

1°. Вычисляют

2°. Находят значения

3°. Новый отрезок локализации определяют по правилу:

В первом случае за очередное приближение к точке минимума принимают а во втором случае (рис. 9.9).

Рис. 9.9

Обозначим через длину отрезка Как нетрудно заметить, справедливо равенство

Поэтому, если параметр достаточно мал то длина вновь полученного отрезка почти вдвое меньше длины предыдущего отрезка. Отсюда — и название метода.

Используя равенство (9.9), с помощью метода математической индукции легко показать, что

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

Тогда за приближение к х с точностью можно принять

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

Пример 9.8. Применяя метод деления отрезка пополам, найдем с точностью точку х локального минимума функции локализованную на отрезке [0, 1]. Вычисления будем вести на -разрядной десятичной ЭВМ.

Зададим

1 итерация. 1. Вычислим

2. Определим значения

3. Так как то следует положить .

Результаты следующих итераций приведены в табл. 9.3.

Таблица 9.3 (см. скан)

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

3. Метод Фибоначчи.

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

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

и начальными значениями Укажем несколько первых чисел:

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

Новый отрезок локализации определяют по тому же правилу:

В первом случае за очередное приближение к точке минимума принимают а во втором случае

Рис. 9.10

Важно то, что в любом случае точка совпадает с одной из точек

Поэтому на очередном шаге достаточно вычислить значение функции лишь в одной недостающей точке.

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

Пример 9.9. Применяя метод Фибоначчи, найдем с точностью точку х локального минимума функции локализованную на отрезке [0, 1]. Вычисления будем вести на -разрядной десятичной ЭВМ.

Первым среди чисел Фибоначчи, для которого выполняется условие является число отвечающее Зададим

Первый шаг. 1. Вычислим

2. Определим значения и .

3. Так как то положим

Второй шаг. 1. Учитывая, что и 0.618056, вычислим

2. Вычислим значение .

3. Так как то положим Результаты остальных шагов приведены в табл. 9.4.

Таблица 9.4 (см. скан)

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

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

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

Из-за указанных недостатков вместо

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

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

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

(рис. 9.11). Действительно, как нетрудно проверить,

Замечательно то, что точка а осуществляет золотое сечение не только отрезка но и отрезка Действительно,

Рис. 9.11

Точно так же точка осуществляет золотое сечение не только отрезка но и отрезка Этот факт далее существенно используется.

Очередная итерация метода золотого сечения производится аналогично итерации метода деления отрезка пополам. В отличие от него точки находятся по формулам

Важно то, что какой бы из отрезков или не был бы выбран за очередной отрезок локализации, точка (в первом случае а во втором случае совпадает с одной из точек Поэтому на очередном шаге

таточно вычислить значение функции лишь в одной недостающей точке.

Заметим, что точка отстоит от концов отрезка на величину, не превышающую . Поэтому верна оценка

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

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

Пример 9.10. Найдем методом золотого сечения с точностью точку локального минимума функции локализованную на отрезке [0, 1].

Положим

1 итерация. 1. Вычислим и .

2. Вычислим .

3. Так как то положим .

II итерация. 1. Учтем, что , и вычислим

2. Вычислим .

3. Так как то положим

Результаты остальных итераций приведены в табл. 9.5.

Таблица 9.5 (см. скан)

Так как то итерации следует прекратить и положить Таким образом, Отметим, что для достижения точности потребовалось 10 вычислений значений функции, как и в методе Фибоначчи.

5. Эффективность методов прямого поиска.

Эффективность указанных методов можно оценивать, например, тем, во сколько раз уменьшается после использования вычислений значений функции первоначальная длина отрезка локализации. Другой критерий — величина гарантированной оценки погрешности. Табл. 9.6 позволяет сравнить по этим критериям рассмотренные выше методы. Как видно, очень неэффективен пассивный поиск. Метод деления отрезка пополам уступает почти эквивалентным по эффективности методам Фибоначчи и золотого сечения.

Таблица 9.6 (см. скан)

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

Таблица 9.7 (см. скан)

6. Влияние погрешности вычислений.

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

прякого поиска ограничена снизу величиной где радиус интервала неопределенности (см. § 9.2). Это означает, например, что прямые методы не позволяют найти на -разрядной десятичной ЭВМ точку локального экстремума функции с точностью Задание приведет лишь к бесполезной трате машинного времени.