Нахождение точки минимума функции золотым сечением. Tag Archives: метод золотого сечения. Правила ввода функции
Метод золотого сечения
Рассмотрим такое симметричное расположение точек x 1 и х 2 на отрезке [а ; b ], при котором одна из них становится пробной точкой и на новом отрезке, полученном после исключения части исходного отрезка. Использование таких точек позволяет на каждой итерации метода исключения отрезков, кроме первой, ограничиться определением только одного значения f (x ), так как другое значение уже найдено на одной из предыдущих итераций.
Рассмотрим сначала отрезок и для определенности предположим, что при его уменьшении исключается правая часть этого отрезка. Пусть х 2 = , тогда симметрично расположенная точка х 1 = 1- (рис.2.2).
Рис. 2.2.
Пробная точка х 1 отрезка перейдет в пробную точку х 2 = 1- нового отрезка . Чтобы точки х 2 = , и х 2 = 1- делили отрезки и в одном и том же отношении, должно выполняться равенство или, откуда находим положительное значение … Таким образом, х 1 = 1- = , .
Для произвольного отрезка [а ; b ] выражения для пробных точек примут вид
1. Точки x 1 и х 2 обладают следующим свойством: каждая из них делит отрезок [а ; b ] на две неравные части так, что отношение длины всего отрезка к длине его большей части равно отношению длин большей и меньшей частей отрезка. Точки с таким свойством называются точками золотого сечения отрезка [а ; b ].
2. На каждой итерации исключения отрезков с пробными точками одна из них переходит на следующий отрезок и значение f (x ) в этой точке вычислять не следует. Если новым отрезком становится [а ; х 2 ], то на него переходит пробная точка исходного отрезка, становясь его второй пробной точкой (х 2 "= х 1) (рис. 2.2). В случае перехода к отрезку [х 1 ; b ] пробная точка исходного отрезка становится первой пробной точкой отрезка [х 1 ; b ].
3. Легко проверить, что х 1 =а+b -х 2 , и x 2 =а+b -х 1 . Поэтому на каждой итерации метода золотого сечения недостающую пробную точку нового отрезка можно найти по перешедшей на него пробной точке с помощью сложения и вычитания.
4. В конце вычислений по методу золотого сечения в качестве приближенного значения х* можно взять середину последнего из полученных отрезков.
На каждой итерации отрезок поиска точки минимума уменьшается в одном и том же отношении, поэтому в результате п итераций его длина становится. Таким образом, точность n определения точки х* после п итераций находят из равенства, а условием окончания поиска точки х * с точностью служит неравенство n .
Пример решения методами дихотомии и золотого сечения
Дана функция, где d=2, e=1
Необходимо найти минимум на отрезке , где, т.е. на отрезке
Составить программу, которая выдаст число итераций при точности е=0,001
Решить двумя методами: дихотомии и золотого сечения
Решение методом дихотомии:
Так как f1 Так как f1 Решение методом золотого сечения: Так как f1 Так как f1 Так как f1 Листинг программы реализующей методы дихотомии и золотого сечения представлен в приложении А Метод золотого сечения имеет достаточно большое применение во многих сферах. Так как всё в мире имеет какую-либо форму: предметы, растения, животные, люди - всё. Что представляют собой эти формы? Любое целое обязательно разделено на части разных размеров. Эти части имеют отношения между собой и ко всему миру, имеют формы. А строение любой формы образуется при помощи симметрии и золотого сечения. Метод золотого сечения применяют в фотографии, живописи. Для фотографа метод золотого сечения - один из самых простых способов выделить главное на картинке. Применяется этот метод и в web-дизайне. В живописи же примером может послужить картина И.И. Шишкина "Сосновая роща". На этой знаменитой картине И.И. Шишкина с очевидностью просматриваются мотивы золотого сечения. Ярко освещенная солнцем сосна (стоящая на первом плане) делит длину картины по золотому сечению. Справа от сосны - освещенный солнцем пригорок. Он делит по золотому сечению правую часть картины по горизонтали. Слева от главной сосны находится множество сосен - при желании можно с успехом продолжить деление картины по золотому сечению и дальше. В архитектуре метод золотого сечения также нашёл своё применение. По законам золотого сечения были построены наиболее известные нам сооружения, такие как Парфенон (V в. до н.э.), собор Парижской Богоматери (Нотр-дам де Пари). Яркими примерами в русской архитектуре станут Смольный собор в Санкт-Петербурге и храм Василия Блаженного, в котором, если взять высоту собора за единицу, то основные пропорции, определяющие членение целого на части, образуют ряд золотого сечения. В основном же, метод золотого сечения применяют в программировании. Он является одним из простейших вычислительных методов решения задач оптимизации. Цель курсовой работы - рассмотреть численные методы поиска экстремума функций одной переменной, а именно метод золотого сечения. Исходя из поставленной цели, необходимо решить следующие задачи: Рассмотреть метод золотого сечения, его алгоритм выполнения; Рассмотреть метод чисел Фибоначчи и его алгоритм выполнения; Показать реализацию метода золотого сечения в программировании. Задачи линейного программирования были первыми, подробно изученными задачами поиска экстремума функций при наличии ограничений типа неравенств. В 1820 году Фурье и затем в 1947 году Данциг предложил метод направленного перебора смежных вершин в направлении возрастания целевой функции -- симплекс-метод, ставший основным при решении задач линейного программирования. Присутствие в названии дисциплины термина "программирование" объясняется тем, что первые исследования и первые приложения линейных оптимизационных задач были в сфере экономики, так как в английском языке слово "programming" означает планирование, составление планов или программ. Вполне естественно, что терминология отражает тесную связь, существующую между математической постановкой задачи и её экономической интерпретацией (изучение оптимальной экономической программы). Термин "линейное программирование" был предложен Данцигом в 1949 году для изучения теоретических и алгоритмических задач, связанных с оптимизацией линейных функций при линейных ограничениях. Поэтому наименование "математическое программирование" связано с тем, что целью решения задач является выбор оптимальной программы действий. Выделение класса экстремальных задач, определяемых линейным функционалом на множестве, задаваемом линейными ограничениями, следует отнести к 1930-м годам. Одними из первых, исследовавшими в общей форме задачи линейного программирования, были: Джон фон Нейман - математик и физик, доказавший основную теорему о матричных играх и изучивший экономическую модель, носящую его имя, и Канторович - советский академик, лауреат Нобелевской премии (1975), сформулировавший ряд задач линейного программирования и предложивший в 1939 году метод их решения (метод разрешающих множителей), незначительно отличающийся от симплекс-метода. В 1931 году венгерский математик Б. Эгервари рассмотрел математическую постановку и решил задачу линейного программирования, имеющую название "проблема выбора", метод решения получил название "венгерского метода". Канторовичем совместно с М.К. Гавуриным в 1949 году разработан метод потенциалов, который применяется при решении транспортных задач. В последующих работах Канторовича, Немчинова, В.В. Новожилова, А.Л. Лурье, А. Брудно, Аганбегяна, Д.Б. Юдина, Е.Г. Гольштейна и других математиков и экономистов получили дальнейшее развитие как математическая теория линейного и нелинейного программирования, так и приложение её методов к исследованию различных экономических проблем. Методам линейного программирования посвящено много работ зарубежных учёных. В 1941 году Ф.Л. Хитчкок поставил транспортную задачу. Основной метод решения задач линейного программирования -- симплекс-метод -- был опубликован в 1949 году Данцигом. Дальнейшее развитие методы линейного и нелинейного программирования получили в работах Куна (англ.), А. Таккера (англ.), Гасса (Saul. I. Gass), Чарнеса (Charnes A.), Била (Beale E.M.) и др. Одновременно с развитием линейного программирования большое внимание уделялось задачам нелинейного программирования, в которых либо целевая функция, либо ограничения, либо то и другое нелинейны. В 1951 году была опубликована работа Куна и Таккера, в которой приведены необходимые и достаточные условия оптимальности для решения задач нелинейного программирования. Эта работа послужила основой для последующих исследований в этой области. Начиная с 1955 году опубликовано много работ, посвященных квадратическому программированию (работы Била, Баранкина и Дорфмана (Dorfman R.), Франка (Frank M.) и Вольфа (Wolfe P.), Марковица и др.). В работах Денниса (Dennis J. B.), Розена (Rosen J. B.) и Зонтендейка (Zontendijk G.) разработаны градиентные методы решения задач нелинейного программирования. В настоящее время для эффективного применения методов математического программирования и решения задач на компьютерах разработаны алгебраические языки моделирования, представителями которыми являются AMPL и LINGO. Пусть Х=. Положим х1=1/T. Так как Т2=Т+1,то 1-1/Т=1/Т2. Итак,отношение длины всего отрезка,к длине большей из его частей равно отношению длины большей части к длине меньшей части: 1/(1/Т)=(1/Т)/(1/Т2) Деление отрезка в таком отношении называется золотое сечение. Точку x2 выберем симметрично точке x1 относительно середины отрезка X:x2=1/T2. Сравнив значения f(x1) и f(x2),находим отрезок локализации минимума ( или ).Нетрудно увидеть, что лежащая внутри локализации точка, где вычисление проведено, делит отрезок в отношении золотого сечения. Алгоритм определяется условием одинаковым в методе Фибоначчи, то есть разница в выборе точки x1. На каждом шаге точка очередного вычисления выбирается симметрично относительно середины отрезка к лежащей внутри этого отрезка точке уже сделанного вычисления. Рисунок 1 - График взаимного расположения первых 2 вычислений по методу золотого сечения
Таблица 1 ? Взаимное расположение генерируемых алгоритмом точек Очевидно, что в случае X=, длина отрезка локализации минимума после N вычислений равна (b-a)/(TN-1). Этот алгоритм используется для нахождения минимума функции
. Если необходимо найти нули функции, то используется другой алгоритм .
Не всегда можно определить заранее, сколько раз придется вычислять функцию. Метод золотого сечения почти столь же эффективен при n-2, что и метод Фибоначчи , однако при этом не требуется знать n – количество вычислений функции.
где τ - «золотое сечение»
Пример
. Методом золотого сечения найти точку минимума x * функции f(x) на отрезке с точностью ε и значение целевой функции в этой точке:
В основе этого метода лежит понятие "золотого сечения", введенного Леонардо да Винчи и используемого, в частности, при построении архитектурных сооружений античности и эпохи Возрождения. Золотым сечением отрезка называется его разбиение на две неравные части, так, что отношение длины всего отрезка к длине его большей части равно отношению длины большей части к длине меньшей части (рис.1.3, слева) Золотое сечение осуществляется двумя точками x1 и x2, расположенными симметрично относительно середины отрезка (рис.1.3, справа). Нетрудно проверить, что Точка x1 осуществляет золотое сечение не только отрезка , но и отрезка , а точка x2 осуществляет золотое сечение не только отрезка , но и отрезка . Действительно, Из (1.10) и (1.11) получаем: x1 = a + , x2 = a +. (1.12) Формулы (1.12) являются основными расчетными формулами метода золотого сечения. Из (1.12) следует, что x1 + x2 = a + b. Если обозначить r = , то формулы (1.12) можно переписать так: x1 = b - r(b - a), x2 = a + r(b - a) (1.13) Процедура деления отрезка такая же, как и для методов дихотомии и Фибоначчи. Вычисляются значения функции в выбранных точках: f(x1) и f(x2). Определяется новый отрезок локализации следующим образом: если f(x1) f(x2), то a1 = a, b1 = x2; если f(x1) > f(x2), то a1 = x1, b1 = b. Так же, как и в методе Фибоначчи, одна из пробных точек x1, x2 станет пробной точкой на новом отрезке локализации. Поэтому на каждой итерации достаточно определить только одно значение f(x), так как другое уже найдено на предыдущей итерации. В конце вычислений можно взять в качестве приближенного значения x* середину последнего из полученных отрезков. После выполнения n итераций погрешность удовлетворяет следующему неравенству: Условием окончания вычислений является выполнение неравенства n <. Алгоритм 1.4 (Алгоритм метода золотого сечения). Шаг 1. Ввести исходные данные: a, b, . Положить r = , n = . Шаг 2. Определить x1 и x2 по формулам (1.13). Шаг 3. Вычислить f(x1) и f(x2). Шаг 4. Проверить критерий окончания вычислений. Если n <, перейти к шагу 5, иначе - к шагу 6. Шаг 5. Перейти к новому отрезку локализации и новым пробным точкам. Если f(x1) f(x2), то положить b = x2, x2 = x1, f(x2) = f(x1), x1 = b - r(b - a) и вычислить f(x1). Иначе положить a = x1, x1 = x2, f(x1) = f(x2), x2 = a + r(b - a) и вычислить f(x2). Положить n = rn и перейти к шагу 4. Шаг 6. Положить x* . Вычислить f * f(x*). Реализация в пакете MathCAD 14 Найдем минимум функции f(x), x с точностью до В итоге получаем f(x*) = -3.749, x*=0.382 с точностью за 18 итераций. Используйте метод золотого сечения для того, чтобы отыскать с точностью \varepsilon локальный максимум функции на отрезке . a, b — концы отрезка, на котором требуется найти максимум, и точность \varepsilon. Точка локального максимума и локальный максимум в формате (x_{max}, y_{max}). Для начала проанализируем данную нам функцию. Найдем ее область определения. D(f) = x^2 + 1 + \cos x > 0 D(f) = x^2 + 1 + \cos x = x^2 + \frac{1}{2} \cos^2 \frac{x}{2} > 0 \forall x \in \mathbb{R} Таким образом, функция определена на всей числовой оси и мы имеем право рассматривать функцию для любого значения аргумента (также это видно по графику). x_1 \le x_2 \le x_{max} \Rightarrow f(x_1) \le f(x_2) \lef(x_{max}) X_1 \ge x_2 \ge x_{max} \Rightarrow f(x_1) \le f(x_2) \lef(x_{max}) Отсюда следует, что если функция f(x) унимодальна на отрезке ,
то максимум этой функции единственен, а локальные минимумы обязательно располагаются на его концах. Так как данная нам функция не является таковой, то для корректного применения метода и получения желаемого результата мы будем собственноручно задавать такие отрезки, на которых представленная функция унимодальна (их несложно выделить по графику). Проведя анализ функции, обратимся к самому методу золотого сечения. Для того чтобы найти определенное значение функции на заданном отрезке, отвечающее заданному критерию поиска (в нашем случае максимум), рассматриваемый отрезок требуется поделить в пропорции золотого сечения в обоих направлениях, то есть выбираются две точки x_1 и x_2 такие, что \frac{b — a}{b — x_1} = \frac{b — a}{x_2 — a} = \varphi = \frac{1 + \sqrt{5}}{2} То есть точка x_1 делит отрезок в отношении золотого сечения. Аналогично x_2 делит отрезок в той же пропорции. Для нахождения максимума выполняем следующую последовательность действий: #include #include using
namespace
std
;
const
double
goldenRatio
=
(1
+
sqrt
(5
)
)
/
2
;
// "Золотое" число
// Рассматриваемая нами функция
double
function
(double
x
)
{
return
log
(1
+
x
*
x
-
cos
(x
)
)
-
pow
(M_E
,
sin
(M_PI
*
x
)
)
;
int
main
()
{
double
a
,
b
;
// Концы отрезка
double
accuracy
;
// Точность, с которой мы находим локальный максимум
double
x1
,
x2
;
// Точки, делящие текущий отрезок в отношении золотого сечения
cin
>>
a
>>
b
>>
accuracy
;
while
(fabs
(b
-
a
)
>
accuracy
)
{
x1
=
b
-
(b
-
a
)
/
goldenRatio
;
x2
=
a
+
(b
-
a
)
/
goldenRatio
;
Введение
Метод золотого сечения
История появления метода золотого сечения
Понятие и определение метода золотого сечения
Правила ввода функции
Примеры правильного написания F(x):
1) 10 x e 2x ≡ 10*x*exp(2*x)
2) x e -x +cos(3x) ≡ x*exp(-x)+cos(3*x)
3) x 3 -x 2 +3 ≡ x^3-x^2+3
Сущность этого метода заключается в следующем. Интервал неопределенности делится на две неравные части так, что отношение длины большего отрезка к длине всего интервала равно отношению длины меньшего отрезка к длине большего (рис 3).
На каждом шаге этой итеративной процедуры, кроме первого, вычисляется только одно значение функции. Однако Химмельблау рекомендовал вычислять на каждом шаге две точки, для того чтобы не накапливалась погрешность, так как τ имеет приближенное значение (рис 4).
Если длина конечного интервала неопределенности равна δ, то для достижения требуемой точности число вычислений значений функции по методу золотого сечения можно найти по условию
f(x)=x 4 +2x 2 +4x+1=0 , [-1;0], ε=0.1
Решение
. Положим a 1 = a, b 1 = b. Вычислим λ 1 = a 1 + (1- 0.618)(b 1 - a 1), μ 1 = a 1 + 0.618(b 1 - a 1).
Вычислим f(λ 1) = -0.5623, f(μ 2) = -0.2149
Итерация №1
.
Поскольку f(λ 1) μ 2 = a 2 + 0.618(b 2 - a 2) = -1 + 0.618(-0.382 +1), f(μ 2) = f(-0.618) = -0.2149
Итерация №2
.
Поскольку f(λ 2) > f(μ 2), то a 3 = -0.7639, b 3 = b 2 , λ 3 = -0.618
μ 3 = a 3 + 0.618(b 3 - a 3) = -0.7639 + 0.618(-0.382 +0.7639), f(μ 3) = f(-0.5279) = -0.5623
Итерация №3
.
Поскольку f(λ 3) μ 4 = a 4 + 0.618(b 4 - a 4) = -0.7639 + 0.618(-0.5279 +0.7639), f(μ 4) = f(-0.618) = -0.4766
Итерация №4
.
Поскольку f(λ 4) μ 5 = a 5 + 0.618(b 5 - a 5) = -0.7639 + 0.618(-0.618 +0.7639), f(μ 5) = f(-0.6738) = -0.5623
Остальные расчеты сведем в таблицу.
Находим x как середину интервала : x=(-0.618-0.70818104)/2 = -0.66309052.
N
a n
b n
b n -a n
λ n
μ n
F(λ n)
F(μ n)
1
-1
0
1
-0.618
-0.382
-0.5623
-0.2149
2
-1
-0.382
0.618
-0.7639
-0.618
-0.548
-0.5623
3
-0.7639
-0.382
0.3819
-0.618
-0.5279
-0.5623
-0.4766
4
-0.7639
-0.5279
0.236
-0.6738
-0.618
-0.5811
-0.5623
5
-0.7639
-0.618
0.1459
-0.7082
-0.6738
-0.5782
-0.5811
6
-0.7082
-0.618
0.09018
-0.6738
-0.6524
-0.5811
-0.5772
Ответ: x = -0.66309052; F(x) = -0.57965758
Входные данные
Выходные данные
Тесты
\varepsilon
a
b
(x_{max}, y_{max})
0.001
1.05
2.2
(1.74435, 0.951781)
0.0001
1.05
2.2
(1.74417, 0.951781)
0.0001
5.7
8
(7.57498, 3.68407)
0.0001
3
4
(3.61901, 2.31289)
Алгоритм
Однако следует помнить о том, что используемый нами метод золотого сечения принадлежит к группе симметричных методов и накладывает некоторые ограничения на исследуемую функцию. Применимость данного метода гарантируется только для непрерывных
, унимодальных
функций.
Унимодальная функция — это функция, которая монотонна на обе стороны от точки максимума x_{max}.Код программы:
