Метод золотого сечения онлайн. Понятие и определение метода золотого сечения
Основная идея данного метода – сокращение числа n ш вычислений функции на каждом шаге (кроме первого)до 1 (минимально возможного значения) с дальнейшим использованием при поиске минимума второй пробной точки каждого шага, которая попадает внутрь нового доверительного интервала. Несмотря на то, что доверительный интервал сокращается при этом существенно менее, чем в два раза (в отличие от дихотомии), данный метод за счёт уменьшения n ш работает в общем значительно быстрее.
Золотым сечением отрезка [a,b ]называется такое его деление промежуточной точкой с , при котором выполняется соотношение (рис 10.12 а), где ξ – коэффициент золотого сечения.
Рис 10.12. Прямое и обратное золотые сечения отрезка
Выразим через xи отрезок ab отрезки ас и cb : аc = x ab; cb= x ac = x 2 ab .
Из условия аc + cb = ab после подстановки данных выражений и сокращения на аb получим следующее квадратное уравнение относительно x:
x 2 + x - 1 = 0 .
Решая его, находим корни:
Отбрасывая отрицательный корень, получим искомую величину отношения:
Разбивать отрезок [a,b ]можно не только в прямом, но и в обратном направлении – от b к a . Аналогичная точка d лежит симметрично с относительно средней точки интервала (a+b )/2(рис.10.12 б).
Величину отношения ad/ab получим, вычитая x из 1:
Точки d , с , задающие обратное и прямое разбиение отрезка в золотом сечении, обладают следующими свойствами.
1. Если отбросить часть отрезка [а,d ], то с d, b ].
2. Если отбросить часть отрезка [с, b ], то d – золотое сечение оставшейся части [a, с ].
Данные свойства можно доказать непосредственной подстановкой значений
Допустим, необходимо с точностью e найти минимум унимодальной функции F (x ) на [a,b ].
Предварительные действия (Шаг 0) .
Доверительный отрезок принимаем равным заданному: а 0 = а, b 0 = b .
Шаги i (i>0) выполняются в цикле при выполнении условия (b i - a i > e).
Шаг 1 . 1. Расчет положения двух пробных точек:
х 2 =а 0 + x(b 0 - а 0)» а 0 + 0,618 (b 0 - а 0);
х 1 = ( b 0 + а 0) - x 2 » а 0 + 0,382(b 0 - а 0).
2. Расчет значений функций F (x 1) и F (x 2).
3. Анализ значений функции в точках х 1 , х 2 и изменение доверительного отрезка по аналогии с дихотомией:
а) при F (x 1) ³ F (x 2) принимаем: a 1 = х 1 , х 1 = х 2 , b 1 = b 0 ,
б) при F (x 1) < F (x 2) принимаем: a 1 = а 0 , х 2 = х 1 , b 1 = х 2 .
4. Проверка окончания цикла: если (b 1 - a 1) > e -продолжение цикла, иначе - выход.
Шаги i (i>1) . Из предыдущей итерации (i -1) известно одно значение функции F (x ) во внутренней точке х доверительного отрезка [a i - 1 ; x i - 1 ]. Поэтому для сокращения достаточно ввести только одну новую пробную точку.
1. Расчет положения новой пробной точки: х¢ = (b i - 1 + а i - 1) - х , расчет значения функции F (x¢ ).
2. Упорядочение пробных точек х , х¢ и значений функции в них:
если (х < х¢ ), то { х 1 = х ; F (x 1)=F (x ); х 2 = х¢ ; F (x 2)=F (x¢ ) };
иначе { х 1 = х¢ ; F (x 1)=F (x¢ ) ; х 2 = х ; F (x 2)=F (x ) }.
Пункты 3 и 4 совпадают с шагом 1.
Скорость сходимости и точность метода. Так как на каждом шаге длина доверительного отрезка сокращается в t = 1/x » 1,618 раз, то длина[a 1 ,b 1 ] связана с длиной [a, b ] следующим образом: b 1 - a 1 = x (b 0 - a 0) =x (b - a ).
По аналогии для произвольного шага k длина доверительного отрезка: b k - a k = x k (b - a ).
Процесс заканчивается, когда выполняется неравенство b k - a k = x k (b - a ) £ e.
Отсюда следует, что номер шага k , на котором достигается требуемая точность e , равен k (e)= ]log t (b - a )/e [ = ]log t M [.
На первом шаге выполняется два вычисления целевой функции, на всех последующих n ш = 1. Поэтому полное число необходимых вычислений F (х )
п (e) =1+ n ш k (e) = 1+] log t ((b - a )/e)[ .
Зависимость e (п ) находим из равенства (b -a )/e = t ( n -1 ) : e (п ) = (b - a )x (n -1) .
Асимптотические скорости роста зависимостей e(n ) и n (e) для метода золотого сечения:
e (n ) = O[(b-a )x n ];
п(e ) = O =O .
Данный метод является ещё более быстрым по сравнению с дихотомией, так как в формуле для п (e)основание логарифма t » 1,618 < 2. Как и дихотомия, он является регулярным. Также он принадлежит к группе так называемых симметричных методов.
Последовательный метод определения экстремума называют симметричным , если на каждом i –том шаге поиска экстремума на доверительном отрезке [a i ,b i ] уже известна одна пробная точка x 1 и значение целевой функции F (x 1) в ней. Вторая (новая) пробная точка x 2 определяется как симметричная x 1 относительно средней точки (a i +b i )/2 доверительного интервала: x 2 = a i + b i - x 1 .
Метод дихотомии не является симметричным.
Замечание 1. Известная пробная точка x 1 в симметричном методе может быть как меньше, так и больше значения (a i +b i )/2 .
Замечание 2 . Свойство симметрии метода позволяет значительно упростить расчёт новых пробных точек. Формула x 2 = a i + b i - x 1 позволяет рассчитать вторую пробную точку x 2 независимо от того, как первая точка x 1 расположена относительно средней точки доверительного отрезка (до или после).
Замечание 3 . В практических расчетах при большом числе итераций из-за накопления погрешностей вычисления положение пробной точки x 1 на отрезках [a i ,b i ] может значительно отклоняться от золотого сечения. При этом, соответственно, полное число необходимых вычислений целевой функции п (e) будет увеличиваться. Для предотвращения этого явления, положение точки x с известным значением функции можно периодически уточнять по формулам х=a+ x(b-a )либо х=a+ (1-x)(b-a ) в зависимости от того, к какому из данных значений она ближе.
Пример 1 . Найти минимум функции F (х ) = х 2 – 2х на доверительном отрезке по методу золотого сечения при заданной точности e =0,5.
Решение .
Шаг 0. а 0 = а, b 0 = b .
Шаг 1 . Расчет положения двух пробных точек: х 2 =а 0 + x(b 0 – а 0) »1,3124; х 1 = (b 0 +а 0)-х 2) » 0,8876. Значения функции в них: F (x 1 ) = -0,9874; F (x 2) = -0,7768. Так как F (x 1 )<F (x x 2 ;b 0 ].Получаем новый доверительный отрезок [а 1 ;b 1 ] = .
b 1 -а 1 = 1,1124 > e = 0,5;продолжаем поиск.
Шаг 2 . Границы доверительного отрезка а 1 = 0,2; b 1 = 1,3124 . На нем известно значение функции в точке х» 0,8876, F (x ) = -0,9874.
Новая пробная точка: х¢ = ( b 1 +а 1) - 0,8876 » 0,6248. Значение функции в новой точке х¢ : F (x¢ ) = -0,8592.
Поскольку х¢<х, то принимаем х 1 = х¢ ; F (x 1) = F (x¢ ); х 2 = х ; F (x 2) = F (x ).
Так как F (x 1) > F (x 2), то отбрасываем часть доверительного отрезка [a 1 ;x 1 ].Получаем новый отрезок [а 2 ; b 2 ] = .
b 2 -а 2 = 0,6878 > e = 0,5;продолжаем поиск.
Шаг 3 . а 2 = 0,6246; b 2 = 1,3124 . Известно значение функции в точке х» 0,8876, F (x ) = -0,9874.
Новая пробная точка: х¢ = (b 2 +а 2) - 0,8876 » 1,0494.. Значение функции в новой точке х¢ : F (x¢ )= --0,9976.
Поскольку х¢>х, то принимаем х 1 = х ; F (x 1) = F (x ); х 2 =х¢ ; F (x 2) = F (x¢ ).
Так как F (x 1)>F (x 2),то отбрасываем часть доверительного отрезка [a 1 ; x 1 ] и получаем отрезок [а 3 ; b 3 ] = .
b 3 -а 3 =0,4248 < e =0,5;следовательно, поиск завершен.
Ответ. Выполнено3 шага, использовано 4 пробных точки. Найден итоговый доверительный интервал: [а 3 , b 3 ] = длины 0,4248.
Как видно из Примера 1 п.10.3, число необходимых вычислений функции сократилось по сравнению с методом дихотомии с 6 до 4.
Вопросы для проверки знаний.
1. Что называют а) золотым сечением отрезка, б) прямым и обратным золотым сечением отрезка?
3. Какое свойство золотого сечения используется при сокращении доверительного отрезка?
4. Какие методы называют симметричными и как симметричность используется для упрощения расчета пробных точек?
5. Как выполняются первый и последующие шаги в методе золотого сечения?
6. За счет чего метод золотого сечения является более быстрым по сравнению с дихотомией?
интервалом неопределенности , но при этом можно выполнить только n вычислений функции. Как следует выбрать n точек, в которых вычисляется функция? С первого взгляда кажется ясным, что не следует искать решение для всех точек, получаемых в результате эксперимента. Напротив, надо попытаться сделать так, чтобы значения функции, полученные в предыдущих экспериментах, определяли положение последующих точек. Действительно, зная значения функции, мы тем самым имеем информацию о самой функции и положении ее минимума и используем эту информацию в дальнейшем поиске.Предположим, что имеется интервал неопределенности (x 1 ,x 3) и известно значение функции f(x 2) внутри этого интервала (см. рис. 9.3). Если можно вычислить функцию всего один раз в точке х 4 , то где следует поместить точку х 4 , для того чтобы получить наименьший возможный интервал неопределенности ?
Рис.
9.3.
Положим х 2 –х 1 =L и х 3 –х 2 =R , причем L > R , как показано на рис. 9.3 , и эти значения будут фиксированы, если известны x 1 , x 2 и х 3 . Если х 4 находится в интервале (х 1 ; х 2) , то:
- если f(x 4) < f(x 2) , то новым интервалом неопределенности будет (x 1 ,x 2) длиной х 2 –х 1 =L ;
- если f(х 4)>f(x 2) , то новым интервалом неопределенности будет (х 4 ,х 3) длиной х 3 –х 4 .
Поскольку не известно, какая из этих ситуаций будет иметь место, выберем х 4 таким образом, чтобы минимизировать наибольшую из длин х 3 -х 4 и х 2 -х 1 . Достигнуть этого можно, сделав длины х 3 – х 4 и х 2 – х 1 равными т.е. поместив х 4 внутри интервала симметрично относительно точки х 2 , уже лежащей внутри интервала. Любое другое положение точки х 4 может привести к тому, что полученный интервал будет больше L . Помещая х 4 симметрично относительно х 2 , мы ничем не рискуем в любом случае. Если окажется, что можно выполнить еще одно вычисление функции, то следует применить описанную процедуру к интервалу (х 1 , х 2) , в котором уже есть значение функции, вычисленное в точке х 4 , или к интервалу (х 4 ,х 3) , в котором уже есть значение функции, вычисленное в точке х 2 .
Следовательно, стратегия ясна с самого начала. Нужно поместить следующую точку внутри интервала неопределенности симметрично относительно уже находящейся там точке. Парадоксально, но, чтобы понять, как следует начинать вычисления, необходимо разобраться в том, как его следует кончать.
На n -м вычислении n -ю точку следует поместить симметрично по отношению к (n - 1) -й точке. Положение этой последней точки в принципе зависит от нас. Для того чтобы получить наибольшее уменьшение интервала на данном этапе, следует разделить пополам предыдущий интервал. Тогда точка х будет совпадать с точкой х n-1 . Однако при этом мы не получаем никакой новой информации. Обычно точки х n-1 и х n отстоят друг от друга на достаточном расстоянии, чтобы определить, в какой половине, левой или правой, находится интервал неопределенности . Они помещаются на расстоянии е/2 по обе стороны от середины отрезка L n-1 ; можно самим задать величину е или выбрать эту величину равной минимально возможному расстоянию между двумя точками.
Интервал неопределенности будет иметь длину L n , следовательно, L n-1 = 2L n - е (рис.9.4 , нижняя часть). На предыдущем этапе точки х n-1 и х n-2 должны быть помещены симметрично внутри интервала L n-2 на расстоянии L n-2 от концов этого интервала. Следовательно, L n-2 = L n-1 +L n (pис.9.4 , средняя часть).
Рис. 9.4.
Замечание . Из рисунка ясно, что на предпоследнем этапе х n-2 остается в качестве внутренней точки.
Аналогично L n-3 =L n-2 +L n-1 (pис. 9.4 , верхняя часть)
В общем случае L j-1 =L j + L j+1
при 1 Таким образом, Если определить последовательность чисел Фибоначчи
следующим образом: F 0 =1, F 1 =l
, и F k =F k-1 +F k-2
для k = 2, 3,..
., то Следовательно, произведя n
вычислений функции,
мы уменьшим начальный интервал неопределенности
в l/F n
раз по сравнению с его начальной
длиной (пренебрегая е), и это - наилучший результат. Если поиск начат, то его несложно продолжить, используя
описанное выше правило симметрии. Следовательно, необходимо
найти положение первой точки, которая помещается на расстоянии L 2
от одного из концов начального
интервала, причем не важно, от какого конца, поскольку вторая
точкa помещается согласно правилу симметрии на расстоянии L 2
от второго конца интервала: После того как найдено положение первой точки, числа Фибоначчи
больше не нужны. Используемое значение е
может определяться из практических соображений. Оно должно быть
меньше L 1 \F n+x
, в противном
случае мы будем напрасно тратить время на вычисление функции. Таким образом, поиск методом
Фибоначчи
, названный так ввиду
появления при поиске чисел Фибоначчи
, является итерационной
процедурой. В процессе поиска интервала (x1; x2)
с точкой х 2
, уже
лежащей в этом интервале, следующая точка х 2
всегда выбирается такой, что х 3 –х 4 = х 2 –х 1
или х 4 -х 1 = х 3 -x 2
,
т.е. x 4 =х 1 -х 2 +х 3
. Если f(x 2) = f 2
и f(x 4) = f 4
,
то можно рассмотреть четыре случая
(рис. 9.5). Следующий из методов одномерной оптимизаци называется методом "золотого сечения"
. Не всегда можно заранее определить, сколько раз придется
вычислять функцию. В методе Фибоначчи
это нужно знать для
определения L 2
, т.е. положения
начальной точки (см. уравнение 2.4). Метод "золотого сечения"
почти столь же эффективен,
как и метод Фибоначчи
, однако при этом не требуется знать n
- количество вычислений функции, определяемое
вначале. После того как выполнено j
вычислений,
исходя из тех же соображений, что и ранее (см. уравнение 2.1),
записываем Т.е. Таким образом, , откуда .
Тогда Используйте метод золотого сечения для того, чтобы отыскать с точностью \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
;
Опять рассмотрим задачу из примера 2.6, в которой требуется минимизировать f(х)=(100-х
) 2 в интервале 60£х
£150. Для того чтобы перейти к интервалу единичной длины, проведем замену переменной, положив w=(х
- 60)/90. Таким образом, задача принимает следующий вид: минимизировать f(w)
= (40 – 90w
) 2 при ограничении 0£w£1. Итерация 1. I 1
= (0, 1); L 1
= l. Проведем два первых вычисления значений функции: w 1 = t
= 0,618, f(w 1)
= 244,0 w 2
= 1-t
= t
2 = 0,382, f(w 2)
= 31,6 Так как f(w 2) < f(w 1)
и w 2 < w 1
, интервал w ³ w 1
исключается. Итерация 2. I 2
=(0. 0,618); L 2
= 0,618 = t
. Следующее вычисление значения функции проводится в точке w 3 = t-t 2 = t(1-t) = t 3
= 0,236, f(w 3) = 352. Так как f(w 3) > f (w 2)
и w 3 < w 2
, интервал w £ w 3 , исключается. Итерация 3. I 3
=(0,236, 0,618); L 3
= 0,382 = t 2
. Следующее вычисление значения функции проводится в точке, расположенной на расстоянии t ´ (длина полученного интервала) от левой граничной точки интервала, или на расстоянии (1-t
) ´ (длина интервала) от правой граничной точки. Таким образом, w 4
=0,618 – (1-t)L 3
= 0.618 - t 2 L 3
0.618 - t 2 (t 2)
= 0.618 - t 4
= 0,472, f(w 4)
= 6,15. Так как f(w 4) < f (w 2)
и w 4 > w 2
, интервал w £ w 2
исключается. В результате получен следующий интервал неопределенности: 0,382 £ w
£ 0,618 для переменной w, или 94,4£х
£115,6 для переменной х
. Если в процессе поиска проведено шесть вычислений значений функции, то длина результирующего интервала для переменной w
равна t N -1 = t 5
= 0,09, что соответствует интервалу длины 8,1 для переменной х
. Для сравнения напомним, что в аналогичной ситуации метод деления интервала пополам привел к получению интервала длины 11,25. В общем случае если правая и левая граничные точки интервала неопределенности (обозначим их через XR
и XL
) известны, то координаты всех последующих пробных точек, получаемых в соответствии с методом золотого сечения, можно вычислить по формулам w = XR - t n
или w = XL + t n
, в зависимости от того, какой подынтервал был исключен на предыдущей итерации – левый или правый. В приведенных выше формулах через t n
обозначена n
-я степень t
, где п
– количество вычислений значений функции. Поиск с помощью метода золотого сечения может быть окончен либо исходя из заданного количества вычислений значений функции (и, следовательно, величины интервала неопределенности), либо по достижении относительной точности искомого значения функции. Наиболее предпочтительным является использование обоих критериев одновременно. Сравнение методов исключения интервалов.
Ниже проводится сравнение относительных эффективностей рассмотренных методов исключения интервалов. Обозначим длину неходкого интервала неопределенности через L 1
, а длину интервала, получаемого в результате N
вычислений значений функции, - через L N
. В качестве показателя эффективности того или иного метода исключения интервалов введем в рассмотрение характеристику относительного уменьшения исходного интервала FR(N)=L N /L 1
Напомним, что при использовании метода деления интервала пополам и метода золотого сечения длина получаемого интервала составляет L 1 (0,5) N /2
и L 1 (0.618) N -1
соответственно. Следовательно, относительное уменьшение интервала после N
вычислений значений функции равно FR(N) = (0,5) N /2
для метода деления интервала пополам; FR(N) = (0,618) N -1
для метода золотого сечения. Для сравнения рассмотрим также метод равномерного поиска, в соответствии с которым оценивание функции проводится в N равноотстоящих друг от друга точках (при этом интервал L 1 делится на (N+1) равных интервалов длины L 1 /(N+l)). Пусть х* – точка, в которой наблюдается минимум функции f(х). Тогда точка истинного минимума f(x) оказывается заключенной в интервале откуда L N = 2L 1 /(N+l). Следовательно, для метода равномерного поиска FR(N)=2/(N+1). В табл. 6.2 представлены значения FR(N), соответствующие выбранным N, для трех методов поиска. Из таблицы следует, что поиск величины относительного уменьшения интервала с помощью метода золотого сечения Таблица 6.2
обеспечивает наибольшее относительное уменьшение исходного интервала при одном и том же количестве вычислений значений функции. С другой стороны, можно также сравнить количества вычислений значения функции, требуемые для достижения заданной величины относительного уменьшения интервала или заданной степени точности. Если величина FR(N) = E задана, то значение N вычисляется по следующим формулам: для метода деления интервала пополам N=2 ln(E)/ln(0,5), для метода золотого сечения N=1+, для метода равномерного поиска В табл. 6.3 приведены данные о количествах вычислений значений функции, необходимых для определения координаты точки минимума с заданной точностью. Следует еще раз подчеркнуть, что метод золотого сечения оказывается более эффективным по сравнению с остальными двумя методами, поскольку он требует наименьшего числа оцениваний значения функции для достижения одной и той же заданной точности. Этот алгоритм используется для нахождения минимума функции
. Если необходимо найти нули функции, то используется другой алгоритм .
Не всегда можно определить заранее, сколько раз придется вычислять функцию. Метод золотого сечения почти столь же эффективен при n-2, что и метод Фибоначчи , однако при этом не требуется знать n – количество вычислений функции.
где τ - «золотое сечение»
Пример
. Методом золотого сечения найти точку минимума x * функции f(x) на отрезке с точностью ε и значение целевой функции в этой точке:
(2.4)
Рис.
9.5.
Входные данные
Выходные данные
Тесты
\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}.Код программы:
Правила ввода функции
Примеры правильного написания 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