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

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

Пример: Зададим максимальное число Фибоначчи, равное 55. Разделим единичный интервал поиска минимума [0, 1] на три части точками 21/55 и 34/55. Предположим, что значение Ф(34/55 ) – минимальное из четырех, вычисленных в указанных точках. Следовательно, интервал неопределенности лежит в пределах [21/55, 1], а его длина 34/55. Перейдем ко второму шагу. Будем считать полученный интервал единичным и зададим максимальное число Фибоначчи, равное 34. Разделим единичный интервал поиска минимума [0, 1] ([21/55, 1] исходного интервала) на три части точками 13/34 и 21/34. Очевидно, что точка 21/34 нового интервала неопределенности соответствует точке 34/55 исходного. Следовательно, в новом интервале следует вычислять целевую функцию только для одной точки 13/34. Предположим, что значение Ф(13/34) – минимальное из четырех, вычисленных в указанных точках интервала поиска. Следовательно, новый интервал неопределенности лежит в пределах [0, 21/34] ([21/55, 34/55] исходного интервала), а его длина 13/55. Вновь, считая полученный интервал единичным, зададим максимальное число Фибоначчи, равным 21 и продолжим итерационный процесс.

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

Известно, что «золотое сечение» отрезка [a, b] это такое сечение, когда отношение r большей части [a, с] отрезка к длине всего отрезка [a, b] равно отношению меньшей части [с, b] к большей части [a, с]

a_______________c_________b

Нетрудно показать, что r выражается формулой (2) для больших номеров k ряда чисел Фибоначчи. Следовательно, при больших значениях k метод «золотого сечения» по своей сути аналогичен методу Фибоначчи. Но, в отличие от метода Фибоначчи, здесь не нужно задавать число k до начала поиска.

Действительно, при больших значениях k координаты точек pk-1 и pk в методе Фибоначчи близки соответственно к 1-r ≈ 0.3820 и r ≈ 0.6180, и старт с этих значений близок к оптимальной стратегии. Таким образом, единичный интервал поиска минимума [0, 1] методом «золотого сечения» делим на три части точками 1 - r и r. Затем, аналогично методу Фибоначчи, находим минимум целевой функции Ф( pi) в четырех точках. Предположим для определенности, что Ф(0.3820) наименьшее из рассчитанных значений. Тогда, как мы знаем, решение находится в интервале неопределенности [0, 0.6180]. Полученный интервал также делим на части в соотношении

You can leave a response, or trackback from your own site.

Leave a Reply