Элементы теории. Метод золотого сечения — метод поиска значений действительно-значной функции на заданном отрезке

Метод золотого сечения — метод поиска значений действительно-значной функции на заданном отрезке. В основе метода лежит принцип деления в пропорциях золотого сечения. Наиболее широко известен как метод поиска экстремума в решении задач оптимизации.

Этот метод также относится к методам исключения интервалов. Он отличается от метода деления интервала пополам тем, что единичный интервал делится двумя пробными точками на три части (рис. 9.1). Каждая пробная точка отстоит от конца интервала на одну и ту же величину j [7]» 0,61803.

Пусть задана функция f (x): [ a, b ] → R, f (x) Î C ([ a, b ]). Тогда для того, чтобы найти определённое значение этой функции на заданном отрезке, отвечающее критерию поиска (пусть это будет минимум), рассматриваемый отрезок делится в пропорции золотого сечения в обоих направлениях, то есть выбираются две точки х ₍₁₎ и x ₍₂₎ такие, что:

Таким образом: и

То есть точка х ₍₁₎ делит отрезок [ a, x ₍₂₎] в отношении золотого сечения. Аналогично x ₍₂₎ делит отрезок [ x ₍₁₎, b ] в той же пропорции. Это свойство и используется для построения итеративного процесса.

Рис. 9.1. Иллюстрация выбора промежуточных точек метода золотого сечения.

Алгоритм применения этого метода следующий:

- на первой итерации заданный отрезок делится двумя симметричными относительно его центра точками и рассчитываются значения в этих точках;

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

- на следующей итерации в силу показанного выше свойства золотого сечения уже надо искать всего одну новую точку;

- процедура продолжается до тех пор, пока не будет достигнута заданная точность.

1. Определим величину j = 0,61803×(b - a).

2. Определим х ₍₁₎ = b - j; x ₍₂₎ = a + j.

3. Подсчитаем значения f (х ₍₁₎) и f (x ₍₂₎).

4. Сравним f (х ₍₁₎)и f (x ₍₂₎). Если f (х ₍₁₎) < f (x ₍₂₎), исключим интервал (x ₍₂₎, b). Положим b = x ₍₂₎. Определим L = b - a. Если L > λ, перейдем к п.1. Если L £ λ, решение найдено.

5. Если f (х ₍₁₎) > f (x ₍₂₎), исключаем интервал (а, х ₍₁₎). Положим а = х ₍₁₎. Определим L = b - a. Если L > ɛ, перейдем к п.1. Если L £ λ, решение найдено.

6. Если f (х ₍₁₎) = f (x ₍₂₎), исключаем интервалы (a, х ₍₁₎) и (x ₍₂₎, b). Положим а = х ₍₁₎, b = x ₍₂₎. Определим L = b - a. Если L > λ, перейдем к п.1. Если L £ ɛ, решение найдено.

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

Выполнение работы в среде MS EXCEL

Реализация этого метода в MS EXCEL аналогична реализации предыдущего метода. Исходными данными также служат определенные интервалы поиска и заданное значение точности поиска ɛ. Таблица расчетных данных должна содержать, согласно алгоритму расчета, графы расчета величин a, b, t, L, х ₍₁₎, x ₍₂₎, f (х ₍₁₎), f (x ₍₂₎). Все величины, кроме a и b, рассчитываются по приведенным в алгоритме формулам, а величины a и b – по формулам, содержащим логические функции EXCEL. При этом формулы, введенные на второй итерации, должны быть составлены таким образом, чтобы при копировании на последующие итерации они обеспечивали бы правильность расчета без редактирования. Расчет заканчивается на той итерации, для которой L < λ.

Пример выполнения представлен в табл. 9.1.

Таблица 9.1

f (x) = (100- x)² λ= 0,1 j = 0,61803

Контрольные вопросы

1. Какой принцип лежит в основе метода золотого сечения?

2. Чем метод золотого сечения отличается от метода деления интервала пополам?

3. Чему равна пропорция золотого сечения?

4. Каков алгоритм применения метода золотого сечения?

5. Что является достоинством методов исключения интервалов?

6. Какое требование является единственным при применении метода золотого сечения?

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

8. Чем метод золотого сечения выделяется среди методов исключения интервалов?

9. Что является исходными данными при реализация метода золотого сечения в MS EXCEL?

10. Каким образом должны быть составлены формулы введенные на второй итерации при реализация метода золотого сечения в MS EXCEL?

11. На какой итерации заканчивается расчет при реализация метода золотого сечения в MS EXCEL?

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