Читайте также: |
|
[править | править исходный текст]
Материал из Википедии — свободной энциклопедии
Метод золотого сечения — метод поиска экстремума действительной функции одной переменной на заданном отрезке. В основе метода лежит принцип деления отрезка в пропорциях золотого сечения. Является одним из простейших вычислительных методов решения задач оптимизации. Впервые представлен Джеком Кифером в 1953 году.
Описание метода[править | править исходный текст]
Пусть задана функция . Тогда для того, чтобы найти определённое значение этой функции на заданном отрезке, отвечающее критерию поиска (пусть это будет минимум), рассматриваемый отрезок делится в пропорции золотого сечения в обоих направлениях, то есть выбираются две точки и такие, что:
Иллюстрация выбора промежуточных точек метода золотого сечения.
, где — пропорция золотого сечения.
Таким образом:
То есть точка делит отрезок в отношении золотого сечения. Аналогично делит отрезок в той же пропорции. Это свойство и используется для построения итеративного процесса.
Алгоритм[править | править исходный текст]
1. На первой итерации заданный отрезок делится двумя симметричными относительно его центра точками и рассчитываются значения в этих точках.
2. После чего тот из концов отрезка, к которому среди двух вновь поставленных точек ближе оказалась та, значение в которой максимально (для случая поискаминимума), отбрасывают.
3. На следующей итерации в силу показанного выше свойства золотого сечения уже надо искать всего одну новую точку.
4. Процедура продолжается до тех пор, пока не будет достигнута заданная точность.
Формализация[править | править исходный текст]
1. Шаг 1. Задаются начальные границы отрезка и точность .
2. Шаг 2. Рассчитывают начальные точки деления: и значения в них целевой функции: .
· Если (для поиска max изменить неравенство на ), то
· Иначе .
3. Шаг 3.
· Если , то и останов.
· Иначе возврат к шагу 2.
Алгоритм взят из источника: Джон Г.Мэтьюз, Куртис Д.Финк "Численные методы. Использование MATLAB". — М, СПб: "Вильямс", 2001. — 716 с.
Метод чисел Фибоначчи[править | править исходный текст]
В силу того, что в асимптотике , метод золотого сечения может быть трансформирован в так называемый метод чисел Фибоначчи. Однако при этом в силу свойств чисел Фибоначчи количество итераций строго ограничено. Это удобно, если сразу задано количество возможных обращений к функции.
Алгоритм[править | править исходный текст]
1. Шаг 1. Задаются начальные границы отрезка и число итераций , рассчитывают начальные точки деления: и значения в них целевой функции: .
2. Шаг 2. .
· Если , то .
· Иначе .
3. Шаг 3.
· Если , то и останов.
· Иначе возврат к шагу 2.
Карт-чек N45377063
25.03.2014 14:35:37
Банковская карточка 676821******1506
Отправитель платежа: "ОАО "Белгазпромбанк" код 742
Плательщик: Нестеренко Любовь Леонидовна, г. БОРИСОВ,
ул. ФАБРИЧНАЯ, д.19,
Получатель платежа: "Минский институт управления", УНП
100687805, р/с 3015012260011 в "Открытое акционерное
общество "БПС-Сбербанк" код 369
Назначение платежа: экзамен
Оплачено по услуге: 90 000 BYR
Комиссия: 900 BYR
Сумма: 90 900 BYR
Код авторизации: 386509
RRN: 000004687898
Дата добавления: 2015-12-01; просмотров: 36 | Нарушение авторских прав