МЕТОД ЗОЛОТОГО СЕЧЕНИЯ

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

Х₁ = a + λ(b-a) и X₂ = b - λ (b-a), где λ = ((3 - Ö(5))/2.

Заметим, что точка Х₁ в свою очередь производит золотое сечение отрезка
[a, X₂], а точка X₂ - золотое сечение отрезка [Х₁,b].

Алгоритм поиска.

Начальный отрезок [a,b] делим точками Х₁ и X₂ по правилу золотого сечения. Вычисляем значения функций f(Х₁) и f(X₂).

Сравнение этих значений позволяет отбросить либо интервал [a,Х₁], либо интервал [X₂,b]. На оставшемся интервале уже есть одна точка, производящая его золотое сечение. Поэтому следует вычислить значение второй такой точки. На этом заканчивается первая итерация.

Таким образом, на каждой итерации, начиная со второй, требуется лишь одно вычисление функции и при этом интервал неопределенности уменьшается на величину λ ~ 0,382. Итерации продолжаются до тех пор, пока интервал неопределенности [a,b] не станет меньше заданной точности решения ε.

Решим задачу примера 2 методом золотого сечения на том же рабочем листе, на котором приведено решение методом дихотомии.

Величину λ вычислим в ячейке Е39, а под решение отведем блок А41: G60. Приведем таблицу формул в соответствующих ячейках для первых двух итераций в строках 41 и 42. Формулы для остальных строк блока копируются из 42 строки. Для вычисления квадратного корня из 5 используется функция КОРЕНЬ Мастера Функций. В формулах строк 41 и 42 использован абсолютный адрес ячейки Е39, т.к. он не должен меняться при копировании.

Как видно из таблицы, и в этом случае широко используется функция ЕСЛИ Мастера функций.

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

1.4. Встроенная подпрограмма EXCEL “ Поиск решения ”.

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

Будем искать решение на том же рабочем листе. Выделим ячейку А63 для значений независимой переменной Х, а ячейку В63 - для значений целевой функции f(X). Занесем в ячейку В63 формулу =2*А63^2 + EXP(-A63).

Запустим подпрограмму, с помощью команды меню Сервис- Поиск решения.

В поле Установить целевую ячейку занесем адрес В63, с помощью переключателей в левой части диалога установим режим поиска минимального значения в этой ячейки. В поле Изменяя ячейки занесем адрес А63 и в списке Ограничения укажем дополнительные условия нахождения минимума c помощью кнопки Добавить. Для нашей задачи таких условий два: А63³0 и A63£1. Они указывают начальный интервал неопределенности, на котором целевая функция унимодальна.

Поиск решения начинается щелчком на кнопке Выполнить. Когда программа находит решение, открывается новый диалог Результаты поиска решений. Щелчком на кнопке ОК можно сохранить найденное решение.

Поиск по сайту: