XIV Аттетков и др. Методы оптимизации (1081420), страница 11
Текст из файла (страница 11)
Далее в соответствии с (2.11) получаем Рис. 2.9 1д~ 2 = 1л ~+1л =31л — 26, 1Н з =1н 2+1х ~ = 51л — 4б, 1л' — 4 = 1н — з +1н — 2 = 81н — бл, 1л' — в = Ь вЂ” я + 1н — з = 131л — 106 и в общем виде 1л — к = Рк+21Н вЂ” 2Ркб, К = О; Л вЂ” 1, (2.12) где коэффициенты Р определены рекуррентным соотноше- нием Р„,=Р 1+Р„, 2, ш=З.,Х вЂ” 1, Р1=Р2=1. (2.13) Так как при К =% — 1 длина 1л к =11=1 отрезка [О, Ц известна, то из (2.12) можно найти длину интервала неопределенности (2.14) Рл -и Рн-и 2.4. Методы посдедоватедьного поиска Существует алгоритм метода прямого поиска, .удовлетворяющий соотношению 12.14). Все коэффициенты Г,п принадлежат множеству 1ч натуральных чисел, и их называют числами Фибоначчи*. В табл.
2.1 представлены эти числа до номера гп = 25. Таблица 2.1 Метод, использующий числа Фибоначчи для выбора длин отрезков 1ь, а значит, и точек ай Е 10, Ц, 1с = 1, Х, в которых вычисляют значения минимизируемой функции, называют методом Фибоначчи 1иногда оптимальным последовательным поиском). Вели на первом шаге поиска 1к = 1, К = Х вЂ” 1) интервал неопределенности имеет длину 11, то в соответствии с (2.12) и 12.14) длина 12 нового отрезка 1аг, 62] равна ыл' бГжРи 1 — РмГм — г 12 =Ру1л — 25Гу~ г = 11+2б Гл -11 1"л т1 гл' л'-,1 20 ГЛ Е1 ГЛ -11 Опишем алгоритм метода, пренебрегая малой величиной б, т.е.
принимая (2.15) 12 т'и Несложно проверить, .что в этом случае выполнение процедуры исключения отрезка на последнем, 1Х вЂ” 1)-м шаге поиска приводит к совпадению внутренних точек ал. 1 и жл 1см. рис. 2.9). *Фиаоначчи, или Леонардо Пизанский (1180 — 1240) — итакьлнский математик. 70 2.
МЕТОДЫ ОДНОМЕРНОЙ МИНИМИЗАЦИИ Отметим, что уже при Х = 11 имеем Гд/Гм = 144/89— — 1,617978, а при Х = 21 получаем Гэз/Гю = 17711,110946— — 1.,618034, что совпадает с отношением х золотого сечения с точностью до 10 ~. Таким образом, на первом шаге длина исходного отрезка уменьшается практически так же, как и в методе золотого сечения.
При 11 = 1 из (2.15) находим 1э = Гн/Гн~.ь Таким образом, учитывая (2.13), заключаем, что на первом шаге выбор точек, симметричных относительно середины отрезка ~0, .1], можно определить по формулам Г . Г ° Г,- х1 = 12 =, хя = 1 — 12 = 1 = ~ хе ~ хм ГН~-1 ГН+1 ГН~-~ причем расстояние между ними будет равно Гн Глà — 1 Гх — 2 д~ = х1 — хз = Гни 1 Гн~-1 Гжт1 После выполнения на этом шаге процедуры исключения отрезка одна из точек хм хз будет граничной точкой нового отрезка ]аз, а1], а другая - — его внутренней точкой, которую обозначим х~~.
Вторая внутренняя точка. на этом отрезке должна быть выбрана симметрично точке х.' относительно его середины. Аналогично происходит выбор второй внутренней точки нового отрезка на всех последующих шагах поиска. На к-м шаге в соответствии с равенством (2.12), в котором следует положить К = Х вЂ” й, и равенством (2.14) длина отрезка ]ам бь] Равна 1ь = Гл ьэ ь/Гн.ы и пРоисхоДит ее Уменьшение в 1ь!1ь-ь1 = Гн з ь/Гн ~ я рзз. Если внутренние точки на этом отрезке обозначить оь и Д, то проведенные рассуждения позволяют написать оь = аь +, 9ь = аь +, оь ( 11в., й = 1, Х вЂ” 1.
Гн-ь Гл'-ь1-ь Гл -» Гл-и Подчеркнем, что реализация метода Фибоначчи предполагает априорное задание требуемого количества Х вычисляемых 2.5, Сравнение к7етодов последовательвосо поиска 71 значений функции (или количества шагов поиска). Этот параметр необходим для реализации первого шага алгоритма при выборе точек х11 и:сш деления отрезка [а1,61).
Если параметр Х по каким-либо причинам не может быть задан заранее, следует использовать другие методы, например дихотомии или золотого сечения. 2.5. Сравнение методов последовательного поиска В качестве оценки скорости сходимости методов прямого поиска можно использовать скорость убывания длины интервала неопределенности в зависимости от числа и вычисленных значений минимизируемой функции в различных методах. Для метода д7ксотольии, пренебрегая в (2.8) малой величиной д, находим 1 — 25 1 (2.16) а для мет71да золотого сечения и метода, Фибоначчиь согласно (2.10) и (2.14), получаем 1 Г= 77 — 1 7 т и-7-1 "77-ь1 гпт1 соответственно, где т — 1,618034 —..
отношение золотого сечения, г7п, т Е 1ч, числа Фибоначчи. Используя формулу Бине* т" — ( — т) сравним два последних метода при н — ь оо: Р;7.Ь1, т" Ь' — ( — т) 1п Ь ) т 1ш1 — = 1пп = 1нп = — = 1717082. и — 7 11 и — 7сс т ' и — 'сс т" ' 7775 1776 *Смс Воробьев В.Н.
72 2. МЕТОДЫ ОДНОМЕРНОЙ МИНИМИЗАЦИИ Таким образом, скорость сходимости метода Фибоначчи при больших значениях п всего примерно на 17 о«св выше., чем скорость сходимости метода золотого сечения. Сравнивая при больших значениях и методы золотого сечения и дихотомии, получаем Р 2п«2 «2 и 1пп — "' = 1нп =т 1пп — ~ =О. и — «во1а и — «сс тп ' п «~ т ~ Таким образом, метод золотого сечения качественно „лучше" метода дихотомии. Но из (2.5) и (2.16) следует 1/2" ~з, и + 1 1пп — ' = 1ншн = 1цп =О« в — «сс 1,*, и- «2/(и+ 1) и — «сс 2««1з "' т.е.
скорость сходимости метода дихотомии при больших значениях п выше, чем скорость сходимости метода опп«и«мальнозо пасоавноео поиска. Итак, метод золотого сечения уступает по скорости сходимости лучшему методу методу Фибоначчи — примерно в 1,17 раза, но является более гибким, поскольку не требует выбора заранее определенного числа точек, в которых предстоит вычислить значения минимизируемой функции. В табл. 2.2 приведены значения длины интервалов неопределенности для рассмотренных методов в зависимости от числа Т««вычисленных значений функции. Пример 2.3. Используя методы дихотомии, золотого сечения и Фибоначчи, при заданном значении в„= 0,1 наибольшей допустимой длины интервала неопределенности найдем интервал, в котором расположена точка а, минимума униаодальной на отрезке ~0«Ц функции 1'(я) = 100(л — 0«24)з. График этой функции показан на рис.
2.10. Для данной функции Т""(я) = 200 = сопв1. Поэтому в соответствии с формулой (2.20) (см. 2.7) при вычислении значений функции с точностью «2«Т = 10 ' имеем нижнюю оценку 2.5, Сравнение методов последовательного поиска Таблица 8.9 1 2 3 5 6 7 8 9 10 и 12 13 14 15 16 17 18 19 20 1,О 0,667 0,500 0,400 о,ззз 0,286 0,250 0,222 0,200 0,182 0,167 0,154 0,143 О 133 0,125 О.,П8 о,ш 0,105 0,100 0,095 1,О 0,500 0,250 0,125 0,0625 0,0312 0,0156 0,00781 0,00391 0,00195 0,000976 1,О 0,618 0,382 0,236 О,146 0,090 0,056 0,0345 0,0213 0,0132 0,00813 0.,00502 о,оазп 0,00192 О,ООП9 0,000733 0,000453 0,000280 0,000173 0,000107 1,0 0,500 0,333 0,200 0,125 0,077 0,048 0,0294 0,0182 О,ОП2 0,00694 0,00429 0,00265 0,00164 0,00101 0,000626 0,000387 0,000239 0,000148 0,0000913 74 2.
МЕТОДЫ ОДНОМЕРНОЙ МИНИМИЗАЦИИ л.=н 'х,7г~*э=ю,.а7 ш-'д ~, а р нахождения точки и„минимума этой функции любым методом прямого поиска. Поэтому границы интервалов неопределенности достаточно вычислять с тремя знаками после запятой, а в методе дихотомии из условия (2.7) можно выбрать 26 = 10 з. Такое же значение д примем и на последнем шаге метода Фибоначчи, причем в нем для выполнения условия 1, < с„достаточно Х в соответствии с табл. 2.2 взять Х = 6, т.е. ограничиться числами Фибоначчи до Рн ~~ = г'7 = 13 включительно.
Применение метода дихотомии потребовало вычисления значений минимизируемой функции в восьми точках (табл. 2.3), что согласуется с табл. 2.2, а в методе золотого сечения (табл. 2.4) оказалось достаточным вычислить шесть значений этой функции,т.е. столько же, сколько и в методе Фибоначчи (табл. 2.5), что также согласуется с табл. 2.2. Отметим, что Таблица 2.3 Таблица 2.4' 75 2.6, Методы оолиномиальной алироксиггацин Таблица, Рьб применение оптимального пассивного поиска в данном случае потребовало бы вычисления этой функции в 19 точках. Из приведенных таблиц видно, что результаты расчетов подтверждают теоретические выводы о скорости сходимости различных методов.
2.6. Методы полиномиальной аппроксимации В методах прямого поиска мы не имели никакой информации о минимизируемой функции за исключением ее значений в выбранных нами точках и предположения, что она непрерывна и является унимодальной функцией на рассматриваемом отрезке. Если функцию в некоторой окрестности точки ее минимума можно достаточно точно заменить (аппроксимировать) многочленом, то для ее минимизации целесообразно использовать так называемые лаетоды полиномиальной аппроксимации.
Их общая особенность состоит в вычислении коэффициентов многочлена по известным значениям функции в отднльных точках и последующем нахождении минимума этого многочлена с использованием необходимых и достаточных условий экстремума. Ограничимся рассмотрением метода нвадратичной аппроксимации минимизируемой функции 7'(х), в котором график этой функции приближенно заменяют параболой, проходящей через три известные точки (хгч 7";), 1 = 1г 2, 3, где,~г = ~(хг). 76 2.
МЕТОДЪ| ОДНОМЕРНОЙ МИНИМИЗАЦИИ Известно [П), .что через три различные точки, не лежащие на одной прямой, можно провести только одну параболу р = = охз+ 6х+ с, и ф О. Коэффициенты а, Ь, с удовлетворяют системе линейных алгебраических уравнений (СЛАУ) ах~ + Ьх, + с = 7'м л = 1., 2, 3. Определитель этой СЛАУ 21 х! 1 22 х2 1 (х1 х2)(х1 хз)(х2 .ез) хз х;1 1 .2 представляет собой определитель Вондера!инда* и отличен от нуля, когда х1, хз, хз попарно различны. В этом случае СЛАУ имеет решение, и притом единственное. Его можно записать в Виде (х1 — х2) (хз х1) .7 7Х23 3 с + + (х1 х2)(х! хз) (хз х!)(х2 хз) (хз х1)(хз х2) Если найденные выражения для коэффициентов а, и 6 подставить в необходимое условие у' = 2ах + 6 = О экстремума функции, то получим ее единственную стационарную точку 6 1 117'23+127'31 +ЗЗГ12 (2.18) 2а 2 Ллзз+Ьез!+~33!2 гдето — — х, — х.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
