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

Метод золотого сечения также является последовательным методом минимизации. Опираясь на свойства золотого сечения отрезка, этот метод использует найденные значения F(X) более рационально, чем метод деления отрезка пополам, что позволяет переходить к очередному отрезку, содержащему точку Х* после вычисления одного, а не двух значений F(X).

Метод основан на делении текущего отрезка , где содер­жится искомый экстремум, на две неравные части, подчиняющие­ся правилу золотого сечения, для определения следующего отрез­ка, содержащего максимум.

Правило золотого сечения: Отношение всего Отрезка к большей его части равно отношению большей части от­Резка к меньшей. Ему удовлетворяют две точки с и D, располо­Женные симметрично относительно середины отрезка:

Путем сравнения F(с) И F(D) Определяют следующий отрезок, где содержится максимум. Если F(D) > F(с), то в качестве сле­дующего отрезка выбирается отрезок , в противном слу­чае — отрезок .

Новый отрезок снова делится на неравные части по правилу золотого сечения. Следует отметить, что точка D является и точ­кой золотого сечения отрезка , Т. е.

Поэтому на каждой следующей итерации (кроме «запуска» метода на исходном отрезке) нужно вычислять только одно зна­чение критерия оптимальности.

Существуют аналитические формулы для расчета новой точ­ки на отрезке, где находится максимальное значение F(X).

Золотое сечение отрезка осуществляется двумя точками:

(3)

Причем Х1 есть вторая точка золотого сечения отрезка , а Х2 – первая точка золотого сечения отрезка .

Зная одну из точек золотого сечения отрезка , другую можно найти по одной из формул

X1 = A + B — X2,X2 = A + B – X1.(4)

Пусть F(X) Q и требуется найти точку минимума Х* функции F(X) на . Построим последовательности {An}, {Bn}, {}, N = 1, 2, …, следующим образом:

(5)

Первая и вторая точки золотого сечения (3) отрезка .

Для определения чисел An, Bn,По найденным An-1, Bn-1, Необходимо выполнить следующие операции:

1) найти одну из точек золотого сечения отрезка по известной другой точке , используя формулы (4) или (3);

2) вычислить значение F(X) во вновь найденной точке золотого сечения;

3) сравнить значения и и найти An, bn, Xn по формулам (5).

Таким образом, на каждом шаге определения An, Bn и , N=2, 3, …, требуется вычисление одного значения F(X). Положив , найдем точку минимума Х* с точностью N:

(6)

Откуда следует, что число шагов N метода золотого сечения, обеспечивающее заданную точность  нахождения точки Х*, должно удовлетворять неравенству:

(7)

Либо можно принять другое условие окончания поис­ка — величина отрезка, содер­жащего максимум, меньше за­данной погрешности.

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

На рис.

18 приведены два этапа поиска максимума функ­ции методом золотого сече­ния: 1 – интервал, включающий в себя искомый максимум функции после первого этапа (первого золотого сечения в точках C и D); 2 – то же, после второго этапа (новая точка E и старая точка D).

Пример 17. Найти минимальное значение F* и точку минимума Х* функции На отрезке . Точку Х* Найти с точностью =0,05.

Решение. Вычисления проведем по формулам (5) представив результаты в табл. 12.

Таблица 12

n

X1(n)

X2(n)

F(x1(n))

F(x2(n))

Примечание

0,309

1,500

2,000

1,691

1,809

-92,049

-91,814

0,191

1,500

1,809

1,618

1,691

-91,464

-92,049

0,118

1,618

1,809

1,691

1,736

-92,049

-92,138

0,073

1,691

1,809

1,736

1,764

-92,138

-92,084

0,045

1,736

-92,138

Первоначальные значения Х1 И х2 находим по формулам (3), а значения точности  по формуле (6).

Из таблицы получаем

Заметим, что если воспользоваться формулой (7), то необходимое число шагов N можно определить заранее. В нашем случае N 4,79, т. е. N= 5, и отпадает необходимость во втором столбце табл. 12.

Пример 18. Найти точку минимума Х*И минимум F* функции F(X)=X2+3X(Lnx-1) на отрезке С точностью =0,05.

Решение. Вычисления представим в табл. 13.

Таблица 13

Похожие главы из других работ:

Графическое моделирование зависимостей максимальной высоты и длины полёта тела от коэффициента сопротивления среды

Текст программы в среде MathCAD:

время полёта до наивысшей точки траектории равна половине времени t1, поэтому высота траектории равна: Дальность полёта в горизонтальном направлении: коэффициент сопротивления среды (в данном случае воздуха) Т.о…

Графическое моделирование зависимостей максимальной высоты и длины полёта тела от коэффициента сопротивления среды

Тексты программ в среде Matlab

Часть 1: grid on; hold on; g=9.81; V=10; m=0:0.1:1 H=(V^2)./(2*g*(1+m.^2)); plot(m,H); График: Часть 2: grid on; hold on; g=9.81; V=10; m=0:0.1:1 L=(m*(V^2))./(2*g*(1+m.^2)); plot(m…

Конечно-разностные схемы моделирования распространения волн

2.9.3 Исходный код программы для вывода в среде MATLAB

Представлен исходный код программы для вывода в среде MATLAB…

Конечно-разностные схемы моделирования распространения волн

Исходный код программы для вывода в среде MATLAB

Конечно-разностные схемы моделирования распространения волн

3.7.3 Исходный код программы для вывода в среде MATLAB

Концепции информационного поиска

Реализация векторной модели в среде Matlab

Входные данные: -terms — множество терминов; -docs — множество документов; -freq — таблица частот терминов…

Концепции информационного поиска

Реализация оценок качества поиска в среде Matlab

Математические и программные модели движения кораблей

2. Программная модель движения кораблей в среде Matlab

Методы обработки рентгеновских диагностических изображений

3. Методы автоматического анализа медицинских изображений в среде MatLab

Организация поиска информации

4. Реализация векторной модели в среде Matlab

Входные данные: · terms — множество терминов; · docs — множество документов; · freq — таблица частот терминов…

Организация поиска информации

5.

Реализация оценок качества поиска в среде Matlab

Практика моделирования и оптимизации линейных систем в среде расширения MatLab Control System

2. Моделирование в среде MatLab и Simulink

Решение задачи с помощью программ Mathcad и Matlab

1. Текст программы в среде MathCAD

Время полёта до наивысшей точки траектории равна половине времени t1, поэтому высота траектории равна: Дальность полёта в горизонтальном направлении: — коэффициент сопротивления среды (в данном случае воздуха) Т.о…

Решение задачи с помощью программ Mathcad и Matlab

2. Тексты программ в среде Matlab

Часть 1: grid on; hold on; g=9.81; V=10; m=0:0.1:1 H=(V^2)./(2*g*(1+m.^2)); plot(m,H); График: Часть 2: grid on; hold on; g=9.81; V=10; m=0:0.1:1 L=(m*(V^2))./(2*g*(1+m.^2)); plot(m,L); График: Вывод Из графиков видно, что высота полета тела…

Экспертная оценка автоматизированной системы безопасности

Задание правил в среде MatLAB

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

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

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

В соответствии с данным методом в каждый текущий момент времени рассматривается всегда две точки, например, в начальный момент точки х1 и х2 так, чтобы а < х1 < х2 < b. При этом возможен один из двух случаев (рис. 3.7). Согласно свойству унимодальной функции в первом случае искомая точка хmin не может находиться на отрезке , во втором случае на отрезке (показаны штриховкой). Значит, область поиска сужается, и следующую точку х3 необходимо брать на одном из укороченных отрезков: – случай 1 или – случай 2.

Далее следует определиться, где на исходном отрезке необходимо выбирать точки х1 и х2. Первоначально о положении точки хmin ничего не известно, поэтому любой из приведенных выше случаев возможен с одинаковой вероятностью. Это означает, что лишним может оказаться любой из отрезков: или . Отсюда следует, что точки х1 и х2 необходимо выбирать симметрично относительно середины отрезка .

Рис. 3.7. Варианты выбора области поиска минимума целевой функции

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

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

Рассмотрим для простоты вместо отрезка отрезок единичной длины (рис. 3.8).

Рис. 3.8.

На рис. 3.8 ÷АВê=÷CDê= х, ÷АCê=÷ВDê= 1 – х, ÷ВСê= 1 – 2х.

Для того, чтобы точка B была «выгодной» как на данном, так и на следующем этапе (шаге), она должна делить отрезок AD в таком же отношении, как и AC: AB/AD = BC/AC. При этом в силу симметрии аналогичным свойством будет обладать и точка C: CD/AD = BC/BD. В обозначениях координаты x эти пропорции принимают вид: x/1 = (1 – 2x)/(1 – x). Решим эту пропорцию:

х(1 – х) = 1 – 2х Þ х – х2 = 1 – 2х Þ х – х2 – 1 + 2х = 0 Þ – х2 + 3х – 1 = 0 Þ х2 – 3х + 1 = 0; Д = b2 – 4ac = 9 – 4 = 5.

Корни этого уравнения равны:

.

Корень x2 > 1 не приемлем, т. е. уравнение имеет один корень.

О точке, которая расположена на расстоянии длины от одного из концов отрезка, говорят, что она осуществляет «золотое сечение» данного отрезка. Очевидно, что каждый отрезок имеет две такие точки, расположенные симметрично относительно его середины.

Таким образом, алгоритм метода «золотого сечения» заключается в следующем (рис. 3.9). На исходном отрезке выбираются две точки x1 и x2 , так, чтобы выполнялось приведенное выше соотношение «золотого сечения» этого отрезка. Вычисляются значения целевой функции в этих точках f (x1) и f (x2). Они сравниваются, и из дальнейшего рассмотрения исключается отрезок, прилегающий к точке, дающей большее значение целевой функции (здесь отрезок ). Т. е. исходный отрезок «стягивается» до отрезка .

Рис. 3.9. Иллюстрация алгоритма метода «золотого сечения»

Для этого нового отрезка находится его середина, и по отношению к ней симметрично оставшейся точке x1 ставится точка x3.

Для нее рассчитывается значение целевой функции f (x3) и сравнивается с f (x1). Из дальнейшего рассмотрения опять исключается отрезок, прилегающий к точке с большим значением целевой функции, здесь это отрезок . Текущий отрезок «стягивается» до нового отрезка, здесь это и т. д.

Метод «золотого сечения» прост, эффективен и широко применяется в практической оптимизации.

Метод линеаризации

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

Пример № 1. Рассмотрим суть данного метода на примере № 2 многопараметрической однокритериальной задачи оптимизации, который решался ранее. Напомним формулировку задачи: найти х1опт и х2опт. Целевая функция у = х2 / х1 ® max, ограничения:

1 £ х1 £ 8, 2 £ х2 £ 12, х1 × х2 ³ 10.

В первую очередь приводим данную задачу к задаче линейного программирования. Для этого проводим логарифмирование ограничений и целевой функции:

lg 1 £ lg х1 £ lg 8; lg 2 £ lg х2 £ lg 12; lg х1 + lg х2 ³ lg 10.

После вычислений получим:

0 £ lg х1 £ 0,903; 0,301 £ lg х2 £ 1,079; lg х1 + lg х2 ³ 1.

После логарифмирования целевой функции:

lg y = lg х2 – lg х ® max.

Далее задача решается с применением симплекс-метода или графо-аналитически.

Пример № 2. Необходимо определить область рациональных режимов резания (например, токарной обработки) исходя из условия максимума производительности.

Целевой функцией в данном случае является величина Q производительности обработки:

Q = B× n× S ® max,

где B – постоянный множитель; n – число оборотов шпинделя; S – подача.

При решении задачи оптимизации абсолютное значение целевой функции не играет никакой роли. Таким образом, от исходной формулировки целевой функции можно перейти к формулировке упрощённой:

Q = n× S ® max.

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

ln Q = ln n + ln S. Тогда Z = ln Q;

x1 = ln n; x2 = ln S; Z = x1 + x2 ® max.

Ограничения, накладываемые на область допустимых решений задачи Smin, Smax, nmin, nmax, определяются паспортом станка, заданными параметрами шероховатости обработанной поверхности, стойкостью инструмента и др. Пример графо-аналитического решения задачи приведен на рис. 3.10.

Этот алгоритм используется для нахождения минимума функции. Если необходимо найти нули функции, то используется другой алгоритм.

Не всегда можно определить заранее, сколько раз придется вычислять функцию. Метод золотого сечения почти столь же эффективен при n-2, что и метод Фибоначчи, однако при этом не требуется знать n – количество вычислений функции.
Сущность этого метода заключается в следующем. Интервал неопределенности делится на две неравные части так, что отношение длины большего отрезка к длине всего интервала равно отношению длины меньшего отрезка к длине большего (рис 3).

где τ — «золотое сечение»

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

Однако Химмельблау рекомендовал вычислять на каждом шаге две точки, для того чтобы не накапливалась погрешность, так как τ имеет приближенное значение (рис 4).
Если длина конечного интервала неопределенности равна δ, то для достижения требуемой точности число вычислений значений функции по методу золотого сечения можно найти по условию

Пример. Методом золотого сечения найти точку минимума функции на отрезке с точностью ε и значение целевой функции в этой точке:
, , ε=0.1
Решение. Положим a1 = a, b1 = b. Вычислим λ1 = a1 + (1- 0.618)(b1 — a1), μ1 = a1 + 0.618(b1 — a1).
Вычислим f(λ1) = -0.5623, f(μ2) = -0.2149
Итерация №1.
Поскольку f(λ1) 1), то b2 = -0.382, a2 = a1, μ2 = -0.618
μ2 = a2 + 0.618(b2 — a2) = -1 + 0.618(-0.382 +1), f(μ2) = f(-0.618) = -0.2149
Итерация №2.
Поскольку f(λ2) > f(μ2), то a3 = -0.7639, b3 = b2, λ3 = -0.618
μ3 = a3 + 0.618(b3 — a3) = -0.7639 + 0.618(-0.382 +0.7639), f(μ3) = f(-0.5279) = -0.5623
Итерация №3.
Поскольку f(λ3) 3), то b4 = -0.5279, a4 = a3, μ4 = -0.618
μ4 = a4 + 0.618(b4 — a4) = -0.7639 + 0.618(-0.5279 +0.7639), f(μ4) = f(-0.618) = -0.4766
Итерация №4.
Поскольку f(λ4) 4), то b5 = -0.618, a5 = a4, μ5 = -0.6738
μ5 = a5 + 0.618(b5 — a5) = -0.7639 + 0.618(-0.618 +0.7639), f(μ5) = f(-0.6738) = -0.5623
Остальные расчеты сведем в таблицу.

Находим как середину интервала : x=(-0.618-0.70818104)/2 = -0.66309052.

Добавить комментарий

Закрыть меню