XIV Аттетков и др. Методы оптимизации (1081420), страница 12
Текст из файла (страница 12)
и зп — — х,— х,, л',7'=1,2,3. Так как уо=2а.= .2, 2 = соп31, то в точке х„при а ) О имеем минимум функции у(х), а при а ( Π— - максимум. *А.Т. Вандермоня (1735 — 1796) французский математик. (х1 — х2) (х1 — хз) 7! (хз + хз) Л „Ь (Х2 — Х1)(Х2 — ХЗ) (ХЗ вЂ” Х1)(ХЗ вЂ” Хз) |2(хз + х1) |3('1 + Х2) + + (х2 х1)(хз х2) (хз х!)(х2 хз) |зхЗх1 (зх!хз 77 2.6, Методы пединоыиадьной аппроксиасапии Ксли известен отрезок, на котором минимизируемая функция унимодальна, то нет необходимости вычислять зна сение коэффициента а,.
Достаточно этот отрезок принять в качестве отрезка [хм хз), а точку хг Е (хм хз) выбрать произвольно в интервале (хм хз). В этом слу сае имеем ~с ) )гтг и ~з ) )гтг, откуда х* Е [хмхз). На первом шаге метода квадратичной аппроксимации при помощи (2.18) вычисляют х„и затем 1„" = 1[х„ц). Для -Ж вычислений на втором шаге из четырех точек х, и х„1= = 1,2, 3, выбирают новую тройку точек х; по следующему правилу: а) если ха Е [х2; хз) и Л ~ ~гэ го хс хг хз хз хг —.Ж Ж, Ф . сг) сг) -Ю. сэ) с2) -Н ) сгг б) еслих, Е[хг,хан~, >22,тох, =хм ха — — х,,хг = хг~ в) если ха Е [хм хг) и г', < гэ, то хс —— хм хз — — хг, хг Н) сц с2г сг) (2г -Щ , г) еслих, Е [хм хг) иг'„>12, тохс — — х„, хз — — хз, хг †.Ж Ж , (2) †, сг) , сг) Ф Х2 ° Далее из (2.18) находят х,, а затем описанную процедуру -сг~ повторяют на третьем шаге и так далее до тех пор, пока длина интервала неппредедеиностпи, в котором гарантированно ле- жит искомая точка х, минимума функции 1 (х), не станет мень- ше заданного наибольшего допустимого значения е,.
Отметим, что подтверждением приближения к точке х„и правильности вычислений может служить уменьшение значения функции у(х) в найденной точке х„по сравненинг со значением р(х, ) на предыдущем шаге. Пример 2.4. Найдем методом квадратичной аппроксимации минимУм фУнкции г(х) = хг + 16гсх, УнимоДальной на отрезке [1, 4). График этой функции приведен на рис. 2.11. 78 2. МЕТОДЫ ОДНОМЕРНОЙ МИНИМИЗАЦИИ 15 15 12 1,5 2 2,5 3 3,5 х Рис. 2.11 Выберем три точки х1 = 1,.
хз = 3, хз = 4 и вычислим в них значения Функции «(х): «л — — «(х1) = 17, «2 = «(х2) = 14,333, «[хз) = «(хз) = 20. Из (2.18) на первом шаге метода квадратичной аппроксимации найдем х~ ~ 2,286 и затем вычислим значение «„' ) = «(х[ ) ) = 12,225. так как х„е [хм хз] и «„< «2, то по указанному выше —.Ю ... Ж правилу х =х1, х =хз и х =х„.
Выбранным точкам соответствуют значения «, ~ =«(х~ ) =17, « ~ = «(х~~ ) =12,.225 и « ' = «(х.', ~) = 14,333. Используя (2.18), получим х„~ = 2,200 и «,' ~ = «ф ~) = 12,113. Поскольку х„е [х1, хз ] и «, < «2, то на третьем шаге имеемх,' =х, х =х ~ их' =и,, т.е. х' =1, х' 2,200 , 00 00 и х~' 2,286. Этим точкам соответствуют значения «1'~ = 17, 12,113 и « ' 12,225. В соответствии с (2.18) находим 00 00 х~ ~ = 2,087 и затем ф ~ = «(х~ ~) = 12,022.
С~о~а оказа~ось,. что х, Е [х,,хз ] и «„< «2 . Позтому для вычислений на четвертом шаге получаем х, = х,, х., «, ~ = 17, «2 ~ = 12,022, «зб ~ = 12,113. В соответствии с (2.18) имеем х„- 2,054 и «, — 12,009. -Ю 00 79 2.6, Методы иелиномиальной аппроксимации Из проведенных расчетов вытекает, что искомая точка х„минимума функции 1(х) лежит в интервале (х„, х, ) = — 10 трб = (1, 2,054). Дальнейшие вычисления приводят к незначительному уменьшению интервала неопределенности, так как каждая очередная точка будет правее точки 2.
Используя необходимое условие зкстрсмума функции ~'(х) = = О, заключаем, что х„= 2 и 1'(х„) = 12. Таким образом, в -(я) данном случае последовательность точек х„' приближается к точке минимума х,, монотонно убывая. Степень приближения текущей точки к точке минимума можно оценить следующим образом. Согласно формуле Тейлора, в окрестности точки минимума х.
целевой функции имеем 1(х1)-Йх )+ (х1 х.) У(х2)-1(х*)+ (х2 х*) . У (х~) 2 2 (х~), 2 Вычисляя разность двух приближенных равенств, находим: 1( '1) — 1(: ) = ' ( ' — х2)М+ '2 — 2,) = 1'ц(х,) 2 2 (Х~) (Х1 «2) (Х1 Ха). В результате получаем приближенную формулу В данном случае при выборе х~ = х„, хг = х„имеем (3) 00 р) 12,022 — 12,009 * ~ (2,087 — 2,054) . 6 что согласуется с полученными результатами.
Метод квадратичной аппроксимации удобно применять после локализации точки минимума методом золоьчого сечения или иешодом Фибониччи. Это объясняется тем, что для дважды дифферснцируемой функции многочлен второго порядка 80 2. МЕ РОДЫ ОДНОМЕРНОЙ МИНИМИЗАЦИИ достаточно хорошо аппроксимирует функцию в окрестности точки минимума. В одной из модификаций метода квадратичной аппроксима(й) ции на к-м шаге, к ) 1, в тройку точек х~ „г = 1, 2, 3, включают ' (й-Ц (й) найденную на предыдущем шаге точку х, (как точку х2 ), (й-1) -(й — Ц одну из точек х,, ближайшую к х„, и точку, симметрич(й — Ц -(й-Ц ную включенной точке х~ относительно х~ .
Последняя -(й) точка новая, и в ней перед вычислением х, необходимо определять значение минимизируемой функции. (й) (й) Такой выбор тройки точек х~ ~ приводит к равенству х2~ 1— — х, = хз — х. = Ьй, что упрощает (2.18): (й) (й) (й) ~~-, ) ~~-з ) (й) (й) 2 И",") -2Л4')+Их®) Процесс последовательных приближений к искомой точке х, минимума унимодальной функции 1(х) прекращают, если по[й-Ц лученные на двух последовательных шагах значения 1(х, ) И) и 1(х„) близки или если проведенные расчеты позволяют указать интервал неопределенности, длина которого меньше заданного наибольшего допустимого значения с„.
-(й) Отметим, что в данном случае точка х~, найденная на й-м шаге, может оказаться за пределами отрезка [хч, хз ), в то (й) (й) время как в методе квадратичной аппроксимации принадлежность точки х„укаэанному отрезку гарантирована. Пример 2.5. Применим описанную модификацию метода квадратичной аппроксимации для нахождения минимума функции У~, ) ~,, 1)2~ 8)2 на отрезке (2, 8). График этой функции приведен на рис. 2.12. Процесс итераций закончим, если длина интервала неопределенности не будет превышать 0,15.
На первом шаге выберем 81 2.б. Методы полипомиельпой аппроксимации т, = 2, х1 = 5 и х~' = 8. Результаты вычислений с учетом (2.19) сведены в табл. 2.6. После выполнения пятого шага приходим к заключению, что точка х„минимума функции ) 1х) расположена в интервале (2.,949, 3,076) длины 0,127. Точное значение х, = 3 соответствует минимальному значению 7'1х,) = О. Рис. 2.12 Таблица 2.6 82 2. МЕТОДЫ ОДНОМЕРНОЙ МИНИМИЗЛ11ИИ 2.7. Методы с использованием производных (х — х )2 2 где ~ точка, лежащая между точками х„и х.
Имея в виду, что вычисления проводятся в достаточно малой окрестности точки х., положим «"(~) = «"(х,). Тогда для приближенно вычисляемых значений «(х) получим «(х) — «(х„) = «(х) — «(х„) + («1х) — «(х)) — («(х*) — «(х*)) )) (х — х,) > «(х) — «(х,) — 2ЬТ = «" (х„) * — 2ЬТ. Из этих неравенств вытекает, что можно гарантировать выполнение неравенства «(х) > «(х„), если «" (х,)(х — х„)2 > 2Ь«. Это приводит к приближенной оценке абсолютной погрешности нахождения точки х„методом прямого поиска: 2ЬТ * ~«(х) (2. 20) Заданная точность г, нахождения точки х, не должна быть меньше Ь„, так как иначе эту точность нельзя достичь методом прямого поиска. Из (2.20) также следует, что при нахожде- В методах прямого гшиска при вычислении значений минимизируемой функции «(х) неизбежно возникая>т погрешности,.
к которым чувствительны алгоритмы прямого поиска, основанные на сравнении значений функции в отдельных точках. Пусть «(х) дважды непрерывно дифференцируемая функция в окрестности точки х„строгого локального минимума, значения которой вычисляются с абсолютной погрешностью, не превышающей Ь«. Оценим абсолютную погрешность Ь„, с которой может быть найдена точка х„с применением метода прямого поиска. Для представления функции «(х) в окрестности точки х„воспользуемся формулой Тейлора ~1Ц с учетом равенства «(х,) = 0: 2.7. Методы с использованием производных 83 нии точки х„происходит потеря примерно половины верных значащих цифр, с которыми можно вычислить приближенное значение минимизируемой функции [1Ц. Если унимодальная функция 1(х) непрерывно дифференцируема на отрезке минимизации, то точку х„наименьшего значения функции можно вычислять как корень уравнения 1'[х) = О с помощью тех или иных методов численного решения нелинейных уравнений [1Ц.
В этом случае на точность решения задачи решающее влияние оказывает погрешность вычисления производной функции. Если абсолютная погрешность вычисления производной не превышает Ьр, то для нижней оценки абсолютной погрешности вычисления корня х, уравнения 1(х) = О имеем [1Ц Ь1 1и(х„) (2.21) Метод средней точки. Будем искать минимум функции 1[х), непрерывно дифференцируемой и строго унимодаяьной на отрезке [ам 61). В этом случае единственной точкой х, Е [ам 61) минимума будет стационарная точка, в которой 1'(х„) = О. Отметим, что непрерывно дифференцируемая унимодияьная на отрезке функция может иметь на нем более одной стационарной точки.
В методе средней тонки используют простую идею: вычисляют производную ~'(х1) = К1 в средней точке х1 = = (а1+6~)/2 исходного отрезка и, если К1 > О, то отрезок [хм 61] отбрасывают, так кзк на нем строго унимодальная функция только возрастает., а если К1 ( О, то отбрасывают Таким образом, при нахождении этого корня можно сохранить все верные значащие цифры, с которыми можно вычислить значение производной 1'[х). Рассмотрим некоторые методы одномерной минимизации, основанные на использовании производной минимизируемой функции. 84 2.
МЕТОДЫ ОДНОМЕРНОЙ МИНИ>МИЗЛЦИИ отрезок [а~., х>]> поскольку на нем строго унимодальная функция лишь убывает. В данном случае отбрасывание половины исходного отрезка [а» 6>] аналоги >но процедуре исключения отрезка. Ясно, что в случае К = О имеем х. = х. Оставшуюся после отбрасывания половину отрезка обозначим [аз, бя] и, вычислив производную у'(хя) = К2 в его средней точке хз = (аз+ бз) >2, повторим процедуру отбрасывания половины отрезка и т.д. Условием прекращения вычислений на к-м шаге может быть выполнение неравенства 4.>.> ( е„, где 1ь > > = = бь >> — аь ы — длина отрезка [аь.>л, 6»~.~] после отбрасывания половины отрезка [аь, 6»]: е„наибольшая допустимая длина интервала неопределенности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
