Метод золотого сечения пример решения

Правила ввода функции

Примеры правильного написания 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

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

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

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

Пример . Методом золотого сечения найти точку минимума x * функции f(x) на отрезке [a;b] с точностью ε и значение целевой функции в этой точке:
f(x)=x 4 +2x 2 +4x+1=0 , [-1;0], ε=0.1
Решение. Положим a₁ = a, b₁ = b. Вычислим λ₁ = a₁ + (1- 0.618)(b₁ — a₁), μ₁ = a₁ + 0.618(b₁ — a₁).
Вычислим f(λ₁) = -0.5623, f(μ₂) = -0.2149
Итерация №1.
Поскольку f(λ₁) f(μ₂), то a₃ = -0.7639, b₃ = b₂, λ₃ = -0.618
μ₃ = a₃ + 0.618(b₃ — a₃) = -0.7639 + 0.618(-0.382 +0.7639), f(μ₃) = f(-0.5279) = -0.5623
Итерация №3.
Поскольку f(λ₃) x как середину интервала [a,b]: x=(-0.618-0.70818104)/2 = -0.66309052.
Ответ: x = -0.66309052; F(x) = -0.57965758

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

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

Читайте также: Nda sound что это

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

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

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

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

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

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

(3)

Причем Х1 есть вторая точка золотого сечения отрезка [A; X2], а Х2 – первая точка золотого сечения отрезка [X1; B].

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

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

(5)

Первая и вторая точки золотого сечения (3) отрезка [An-1; Bn-1].

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

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

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

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

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

Читайте также: Front ru не работает

(6)

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

(7)

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

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

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

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

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

Рассмотрим такое симметричное расположение точек x₁ и х₂ на отрезке [а; b], при котором одна из них становится пробной точкой и на новом отрезке, полученном после исключения части исходного отрезка. Использование таких точек позволяет на каждой итерации метода исключения отрезков, кроме первой, ограничиться определением только одного значения f (x), так как другое значение уже найдено на одной из предыдущих итераций.

Рассмотрим сначала отрезок [0; 1] и для определенности предположим, что при его уменьшении исключается правая часть этого отрезка. Пусть х₂ = , тогда симметрично расположенная точка х₁ = 1- (рис.2.2).

Рис. 2.2.-Определение пробных точек в методе золотого сечения

Пробная точка х₁ отрезка [0; 1] перейдет в пробную точку х₂ = 1- нового отрезка [0; т]. Чтобы точки х₂ = , и х₂ = 1- делили отрезки [0; 1] и [0; ] в одном и том же отношении, должно выполняться равенство или , откуда находим положительное значение … Таким образом, х₁ = 1- = , .

Для произвольного отрезка [а; b] выражения для пробных точек примут вид

1. Точки x₁ и х₂ обладают следующим свойством: каждая из них делит отрезок [а; b] на две неравные части так, что отношение длины всего отрезка к длине его большей части равно отношению длин большей и меньшей частей отрезка. Точки с таким свойством называются точками золотого сечения отрезка [а; b].

2. На каждой итерации исключения отрезков с пробными точками одна из них переходит на следующий отрезок и значение f (x) в этой точке вычислять не следует. Если новым отрезком становится [а; х₂], то на него переходит пробная точка исходного отрезка, становясь его второй пробной точкой (х₂‘= х₁) (рис. 2.2). В случае перехода к отрезку [х₁; b] пробная точка исходного отрезка становится первой пробной точкой отрезка [х₁; b].

3. Легко проверить, что х₁=а+b—х₂ , и x₂=а+b—х₁. Поэтому на каждой итерации метода золотого сечения недостающую пробную точку нового отрезка можно найти по перешедшей на него пробной точке с помощью сложения и вычитания.

4. В конце вычислений по методу золотого сечения в качестве приближенного значения х* можно взять середину последнего из полученных отрезков .

На каждой итерации отрезок поиска точки минимума уменьшается в одном и том же отношении , поэтому в результате п итераций его длина становится . Таким образом, точность _n определения точки х* после п итераций находят из равенства, а условием окончания поиска точки х* с точностью служит неравенство _n .