Итерация 3. Таким образом, исключается интервал (105; 116,25)

а =93,75 b =116,25, х_т=105,

L = 116,25—93,75=22,5,

x ₁=99,375, х ₂ = 110,625,

f(x ₁ ) =0,39< f (105)=25.

Таким образом, исключается интервал (105; 116,25). Новый ин­тервал неопределенности равен (93,75; 105), его средняя точка есть 99,375 (точка х ₁на итерации 3). Отметим, что за три итерации (шесть вычислений значения функции) исходный интервал поиска длины 90 уменьшился до величины (90)(1/2)³=11,25.

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

1. Если количество пробных точек принимается равным двум, то их следует размещать на одинаковых расстояниях от середины интервала.

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

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

Руководствуясь этими выводами, рассмотрим симметричное рас­положение двух пробных точек на исходном интервале единичной длины, которое показано на рис. 2.11. (Выбор единичного интервала обусловлен соображениями удобства.) Пробные точки отстоят от граничных точек интервала на расстоянии t. При таком симметрич­ном расположении точек длина остающегося после исключения ин­тервала всегда равна t независимо от того, какое из значений функ­ции в пробных точках оказывается меньшим. Предположим, что исключается правый подынтервал. На рис. 2.12 показано, что оставшийся подынтервал длины t содержит одну пробную точку, расположенную на расстоянии (1—t) от левой граничной точки.

Для того чтобы симметрия поискового образца сохранялась, расстояние (1-t) должно составлять t-ю часть длины интервала (которая равна t). При таком выборе t следующая подобная точка размещается на расстоянии, равной t-й части длины интервала, от правой граничной точки интервала (рис.2.13)

Рис. 2.12. Интервалы, полученные методом золотого сечения

Отсюда следует, что при выборе t в соответствии с условием 1-t =t² симметрия поискового образца, показанного на рис. 2.11, сохраняется при переходе к уменьшенному интервалу, который изображен на рис. 2.13. Решая это квадратное уравнение, получаем

откуда положительное решение t=0,61803…. Схема поиска, при которой пробные точки делят интервал в этом отношении, известна

под названием поиска с помощью метода золотого сечения. Заметим, что после первых двух вычислений значений функции каждое по­следующее вычисление позволяет исключить подынтервал, величина которого составляет (1—t)-ю долю от длины интервала поиска. Следовательно, если исходный интервал имеет единичную длину, то величина интервала, полученного в результате N вычислений зна­чений функции, равна t^N-1. Можно показать, что поиск с помощью метода золотого сечения является асимптотически наиболее эффек­тивным способом реализации минимаксной стратегии поиска.

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