Метод дихотомического поиска | Метод золотого сечения |
Шаг 1 | Шаг 1 |
/о = (0, 3) = (xL, хя), | /о = (0, 3) = (xL, xR), |
xi =0,5(3 + 0-0,1) = 1,45, /(xi) = 4,35, | х, = 3 - 0,618(3 - 0) = 1,146, /(х,) = 3,438, |
хг = 0,5(3 + 0 + 0,1) = 1,55, i\x2) = 4,65, | х2 = 0 + 0,618(3 - 0) = 1,854, /(хг) = 5,562, |
/(х2) > /(Xi) => xL = 1,45, /т = (1,45, 3). | /(х2) > /(X!) => X/. = 1,146, /, = (1,146, 3). |
Шаг 2 | Шаг 2 |
/, = (1,45, 3) = (xL, хв). | /1 =(1,146, 3) = (xL, хд), |
Xi = 0,5(3 + 1,45 - 0,1) = 2,175, /(Xi) = 5,942, | Хт = х2 на шаге 1 = 1,854, /(Xi) = 5,562, |
х2 = 0,5(3 + 1,45 + 0,1) = 2,275, f(x2) = 5,908, | Хг = 1,146 + 0,618(3 - 1,146) = 2,292, /(х2) = 5,903, |
fxi) > i\x2) => Хя = 2,275, /, = (1,45, 2,275). | /(х2) > /(Xi) => X/. = 1,854, /, = (1,854, 3). |
Продолжая вычисления, получим с заданной точностью интервалы, содержащие точку максимума функции f(x).
На рис. 21.2 показан шаблон Excel ch21DichotomousGoldenSection.xls, предназначенный для поиска экстремумов функций описанными методами. Входными данными являются функция f(x) и константы a, b и Д. В данном примере функция f(x) задается в ячейке ЕЗ с помощью формулы
=ЕСЛИ(СЗ<=2;3*СЗ;(-СЗ+20)/3) Отметим, что здесь ссылка СЗ играет роль переменной х. Константы а и Ь, введенные в ячейки В4 и D4, задают интервал поиска точки экстремума функции f(x). Значение предела точности Д вводится в ячейку ВЗ. Метод поиска задается путем ввода символа х в ячейку D5 (метод дихотомического поиска) или в ячейку F5 (метод золотого сечения).
На рис. 21.2 для сравнения показаны результаты вычислений в соответствии с обоими методами. Как видно на рисунке, метод золотого сечения потребовал всего 40 % числа итераций, выполненных методом дихотомического поиска.
УПРАЖНЕНИЯ 21.1.1
1. С помощью шаблона ch21DichotomousGoldenSection.xls решите задачу из примера 21.1.1, положив Д = 0,01. Сравните точность полученных результатов с данными, показанными на рис. 21.2.
2. Методом дихотомического поиска найдите максимумы следующих функций, полагая при этом, что Д = 0,05.
a) /(*)=•;-т, 2<х<4;
b) f(x) = х cosx, 0 < х < я;
c) f(x) = хsinrcx, 1,5<х<2,5;
d) f(x) = -(х - З)2, 2<х<4;
,. . \Ах, 0<*<2, W [4-х, 2<*<4.
в с d в
DichotomoirsGolden Section Seaich
Input data: Type f(C3) in E3, where C3 represents x m )
oooootd
1 450000 1 450000 1 812500 1.812500 1 903125 1 948438 1 971094 1 982422 1.988086 1 988086 1 989502 1 989502 1 969856 1 969856 1 989944 I 989989 1 989989 1990000 1 990000
3OXO00 3OXO00 2 275000 2 275000 2093750 2 093750 2093750 2093750 2.093750 2.093750 2 090918 2 090918 2 090210 2 090210 2 0900ЭЗ 2 090033 2 0900ЭЗ 2 090011 2 090011 2090005
1 450000 2.175000 1 812500 1 993750 1 903125 1 948438 1 971094 1 982422 1 988086 1 990918 1 989502 1 990210 1 989856 1 990033 1 989944 1 9899B9 1 990011 1 990000 1.990005; 1 990003
1 550000 2.275000
1 912500
2 09Э750 2 003125 2 048438 2.071094 2 082422 2 088086 2 090918 2 089502 2 090210 2089856 2 090033 2 089944 2089989 2090011 2 090000 2090005 2 090003
4 350000
5 941667 5 437500 5981250 5 709375 5 845313 5913281 5 947266 5 964258 5 972754 5968506 5.9706X 5969568 5.970099 5 969833 5 969966 5 970033 5 969999 5 970016 5 970008
4 650000
5 908333 5 7Э7500 5 968750 5 998958 5 983854 5 976X2 5 972526 5 970638 5 969694 5 970166 59699X 5 970048 5 969969 5 97X19 5.970004 5 969996 5 9700ГО 5 969996 5 969999
ВС D 1 E
Dichotomou&Golden Section Seaich
Input data: Type t{C3) in E3. aiare СЗ гедч :ents и in fy>
0 000000
1 145898 1 854102 1 854102 1 854102 1 854102 1957428 1 957428 1 996894
3000000 30000X 3000000 2 562306 2 291796 2124612 2124612 2 060753 2 060753
1 145898
1 854102
2 291796 2124612 2 021286
1 957428 2021266 1.996894"
2 021286
1 854102
2 291796 2 562Э06 2 291796 2124612 2 021286 2060753 2.021286 2 036361
3 437694 5 562306 5 902735 5 958463 5 992905 5 872283 5 992905 5 990683 5992905
5 562306 5.902735 5 812565 5 902735 5 958463 5 992905 5.979749 5 992905 5 987BB0
Рис. 21.2. Реализация методов прямого поиска в Excel
Получите формулу для определения максимального числа итераций, выполняемых в методе дихотомического поиска при заданной величине Д и длине начального интервала неопределенности I0 = b- а.
21.1.2. Градиентный метод
В этом разделе рассматривается метод решения задач нелинейного программирования с дважды непрерывно дифференцируемыми функциями. Основная идея метода заключается в построении последовательности точек с учетом направления градиента исследуемой функции.
Одним из градиентных методов является изложенный в разделе 20.1.2 метод Ньютона-Рафсона, который ориентирован на решение систем уравнений. Здесь рассматривается еще один метод, который называется методом наискорейшего подъема2.
В русскоязычной математической литературе описываемый метод, называемый методом наискорейшего спуска, ориентирован на решение задач безусловной минимизации. - Прим. ред.
Согласно градиентному методу вычисления завершаются при нахождении точки, в которой градиент функции равен нулю. Но это лишь необходимое условие для того, чтобы в данной точке находился оптимум. Чтобы удостовериться, что найдена именно точка оптимума, обычно привлекаются свойства вогнутости или выпуклости функции f(x).
Рассмотрим задачу максимизации функции f(X). Пусть Х° - начальная точка, с которой начинается реализация метода, УДХ*) - градиент функции f в k-й точке X*. Идея метода сводится к определению в данной точке направления р, вдоль которого производная по направлению df/dp достигает своего максимума. Это происходит в том случае, когда последовательные точки X* и Х*+1 связаны соотношением
где г* - параметр, называемый длиной шага в точке X*.
Обычно значение параметра г* выбирается из условия, чтобы в точке Х*1 наблюдалось максимальное увеличение значения целевой функции /. Другими словами, если функция Л(г) определяется соотношением
то г* равен значению г, на котором функция h(r) достигает максимума. Поскольку Л(г) является функцией одной переменной, чтобы найти ее максимум, можно применить метод поиска экстремума, описанный в подразделе 21.1.1, если, конечно, функция h(r) строго одновершинная.
Описанная процедура заканчивается, когда две последовательные точки X* и X**1 близки. Это эквивалентно тому, что rVf(Xk) = 0. Поскольку г * 0, последнее соотношение означает, что в точке X* выполняется необходимое условие экстремума УДХ*) = 0.
Пример 21.1.2
Рассмотрим задачу максимизации функции
/(х,,х2) = 4х, + 6х2 -2х] -2хххг -2х22.
Функция Дх,, х2) является квадратичной, и нам известно, что ее абсолютный мак-
Решим эту задачу методом наискорейшего подъема. На рис. 21.3 изображена последовательность получаемых точек. Градиенты в двух последовательных итерационных точках с необходимостью являются ортогональными (перпендикулярными) друг к другу. Для данной функции градиент вычисляется по формуле
k+l
X" + rkVf(Xk),
h(r) = f(Xk + rVf(Xk)),
УДХ) = (4 - 4x, - 2x2, 6 - 2x, - 4x2). Пусть начальной точкой является Х° = (1, 1).
X = (l, l) + r(-2, 0) = (l-2r, 1).