Ф.П. Васильев - Методы оптимизации (1125241), страница 7
Текст из файла (страница 7)
ГрЕШНОСтЬ МЕтОда р„ ЗДЕСЬ будЕт раВНа А(/, ри) = ХЧ „, — Хч 1. ПОЭтОМу 6(ри) = Зцр А(/ ри) < геЯ < тах (х. — х, ). ПУсть шах (хг „, — х; 1) = хй „, — хй и Возьмем фУнкцию /й —— 1+1 1 = / (х) = ]х — хй]. Это строго унимодальная функция достигает своей нийкней грани на отрезке [а, 6] з точке х, = хи и [ай 1, хй„1], пРичем йй(/й,Р ) = ей ! — хй и следовательно, гаРан- тированная погрешйость метода ри на классе С) равна 6(р ) = тах (хй, х,), Для 1«1«и получения оптимального пассивного метода остается выяснить, достигается ли нижняя грань щ( 6(р ) = 6, где Р— мнойкество всех пассивных методов, и если достигается, то на каком методе р «Р .
Оказывается, здесь нужно различать случаи четного и нечетного и. Теорема !. При всех нечвтньгх п=2т+1 (т> О) существует бесконечно много оптимальных пассивных методов на классе Ог наилучшая гарантированная точноппь пассивнь1х методов Рз,„„! на этом хлассе ровна (Ь вЂ” а)/(т+ 1), ДОКааатЕЛЬСтза, ВОЗЬМЕМ ПаССИВНЫй МЕтсд ри =(О1, .. их ), ГдЕ И 1 = а+ я(6— — и)/(т ч-1) (1 = 1,, т), а точки оз,. „! (1 = О, 1,..., т) расположены на отрезке [а, ь] произвольно, лишь бы пм 1 <с21 < из, „1, озй ! — «21, <(ь — а)/(т+1), Очевидно, 6(ри ) = = (Ь вЂ” а)/(тн+ 1). С друГОй СтОрОНЫ, дпя ЛЮбОГО ПаССИВНОГО МЕтОда ри = (Х1,., и Х„) (Х! —— =а<я «,,х <ь=х,, п=2тт!) имеем 6(р„)= тах (х,, ! — х, 1)рйзахтгь— .1- 1' 1«< хг„хз„,-хзт 2, ..
ч хч — хг, хг-а) >(Ь-а)/(тч-1). Следовательно, методы р оптимальны и 6, =(Ь вЂ” а)/(т 4 1). П Теорема 2 При всех четных п=2т (т) 1) оптимального пассивногометода на классе О. нв существует; наилучшая гарантированная точность пассивных методов Рзи на этом няассе равна (Ь вЂ” а)/(т+ 1). В качестве г-оятимального метода мохсно взять Рт=(х1, ..«и«), гдесзс 1=а+ъ(6-а)/(гп+1)-г, из; — -а+ъ(6 — а)/(го+1)+г (1=!,,т, 0 < г < (6 — а)/(2(т + 1))). Доказательство.
Сначала убедимся з том, что 6(р ) >(Ь вЂ” а)/(т+1) для любого пассивного метода ри = [хг, .. и хи) (хо — — а < х! «... х < Ь = хи„1, и = 2т). Обозначим я= ат (ь — а)/(т ч-1). имеются две возможности: либо тх > ай либо хз < х. если хг > х, то 6(р ) = гпах (х +1 — х; 1) ~) тз — а> х — а=(ь — а)/(т+1). если же х < х, то 6(р ) = шах (х,.„, — хч 1)>хз — а. В самом деле, если бы щах (х «1 — х, 1) <хгиа, то хз,. 1<1« 1< «и 1 < хз — а (1 = 1,, т) и, кроме того, х! — а < хг — а. Сложив эти неравенства, придем к противоречивому неравенству 6 — а < (т+ 1)(хз — а) < (т+ 1)(х — а) = ь — а, Таким образом, при хг < б имеем 6(ри) = шах (хг,! — хг 1) = 6(р,', 1), где р,', 2«1<и пассивный метод на отрезке [х1, Ь], составленный иэ точек хг, .. «хи метода ри.
Но и — 1 = 2т- — 1 — нечетное число, поэтому, применяя теорему 1 к отрезку [х1, Ь], имеем 6(р„' ,) ) (Ь— — х1)/т, тогда 6(ри)= 6(р„' 1) >(ь-х1)/т>(6-х)/т=(ь — а)/(т+1), тем самым докааано, что 6(Р«) > (Ь вЂ” а)/(тп+ 1) пРи всех Р б Рт, С дРУгой стоРоны, 6(Р ) = (Ь вЂ” а)/(т т 1)+ е для всех г (О < г < (Ь вЂ” а)/(2(т + 1))). Следовательно, 6„= (6 - а)/(™т +! ), П Иэ теорем 1, 2 вытекает, что предпочтительнее пользоваться пассивными методами с четным числом и = 2т точек, поскольку в случае и = 2т + 1 наилучшая гарантированная точность остается такой же, как и при и = 2т. 4. Перейдем к рассмотрению последовательных методов минимизации унимодальных функций на [а, 6].
Здесь нам понадобятся знаменитые числа Фибоначчи, которые, как известно [193], ойределяются соотношениями +2 Рич-1 С помощью индукции легко показать, что и-е число Фибоначчи представимо в виде Используя числа Р, построим и-точечный последовательный метод, который принято назы- вать методом Фибоначчи. Этот ь1етод относится к классу симметричных методов, описанных в Э 4, и определяетсв заданием на отрезке [а, 6] точки х, = а+ (Ь вЂ” а)Р 1/Г, или симме- тричной ей тачки хг —— а+ ь — х, = а+(6 — а)Р„/Г „1. с помощью индукции нетрудно показать, что такой симметричный метод обладает свойством (4.4) и на й.м шаге (й < и), когда про- веденм вычисления значений функции а точках х1,...,хй, приводит к отрезку локализации минимума [ай,бй] длиной 6йй = Ьй — ай = (Ь вЂ” а)Р« — й,.з/Р +! причем точка хй (ай < хй < Ьй) с вычисленным значением /(бй) = т!и /(х;) совпадает с одной иэ точен 1««й и-й Р.
й хй =а! т(Ьй — а1,)1 " — — ай+(Ь вЂ” а) —" и — йе2 (4) хй = ай + (6й — ай)тг — = ай -1-(Ь вЂ” а) — с: — = ай -1- Ьй — хэп и и — й+1 и — йа! « — йч2 1 1 расположенных на отрезке [ай, 6й] симметрично относительно его середины. Как видно из (4), при й = и-1 точки х'„1, хи ! совпадают, Это означает, что при й =и-1 пеРваЯ часть пРоцесса эаканчизаетсЯ вычйслением значениЯ фУнкции в точке хи ! и опРеДеле- нием отрезка локализации минимума [а« 1, Ь 1]длины Ьи,-аи, =(Ь вЂ” а)уз/Ри+! — — 2(6- — а)/Р„й1, причем точка х,', = хи ! — — хи ! совпадает с серединой отрезка [а„1, 6„1]. В заключение, несколько нарушая симметричность процесса, последнее п.е вычисление зна- чениа минимизиРУемой фУнкции /(х) пРоводитсЯ з точке хи = хи 1+ е (или х = жи ! — г), где 0 < г < (6 — а)/Ри+1, и отрезок [аи, Ь ) локализации минймума определяется по фор- мУлам а«=а 1, Ьи=хи 1+г пРИ/(х 1)</(х 1+г) и а«=хи 1, Ь«=Ь« ! пРН /(х„1) >/(жи 1+ с), так что в худшем случае ьи — а« =(ь — а)/Ри1+ э.
Описанный метод обозначим через Фи, Теорема 3. Лри всех и > 1 оптимального последовательного метода на классе унимодальных функций не существует; наилучшая гарантированная точность после- довательных методов яо атом классе равно (6 — а)/Р«„1. В качестве г-оптимального метода можно взять метод Фибоначчи Фи.
Доказательство этой теоремы можно найти з [1481 3741 684], Заметим, что число Ри 1/Р 1, вообще говоря, является бесконечной периодической де- сятичной дробью, поэтому первая точка х, метода Фи будет задаваться на ЭВМ приближенно. Во избежание быстрого роста погрешности из-за неточности задания первой точки на практи- ке нужно пользоваться модификацией метода Фи, описанной в $4 для симметричных методов з общем случае.
Следует подчеркнуть, что метод Фи для своей реализации требует, чтобы число и зычис. лений значений минимизируемой фувнции было задано заранее — выбор первой точки а этом методе невозможен без знания и. В тех случаях, когда число и по каким-либо причинам не может быть задано заранее, можно применять метод золотого сечения, не требугощий для своей реализации априорного знания и. Для сравнения вспомним, что методом золотого сечения за и вычислений значений функции мы получали отрезок [а«,Ь«] локализации минимума длины 6 — аи=((угб — 1)/2)и '(Ь— — а) =(2/(чгб+ 1))и '(6 — а). С учетом формулы Ри „1т((/5+!)/2)и+ /Угб, вытекающей из (3) при больших и, для метода Фи получаем отрезок лонализации минимума, длина которого близка к (Ь-а)/Р„+ ! т(2/(~~ 5+! ))" + '(6- а)/Угб.
Отсюда следует, что метод золотого сечения хуже метода Ф при больших и всего в ((т/ЬЧ-1)/2) /1/5=1,1708... раз, т, е. на классе унимодзльных 16ункций метод золотого сечения близок к оптимальным методам. Интересно 24 г . !. методы минимизации ФУН((Ций Однсй перпменной б б. мптод ломлных также заметить что т.
е. при достаточно больших и начальные точки я>, из методов Фибоначчи и золотого сечения практически созпадают. Упражнения 1. Найти гарантированную на классе уиимодальных функций точность последозательного (или пассизного) и-точечного метода р„, если з качестзе погрешности метода р при минимизации функции /=/(к) принята зелйчина >5(/ р„) = [/„— /(В )[ [755]. 2.
Сравнить оптимальные и е-оптимальные пассизные методы на классе унимодальных функции с методом деления отрезка пополам, 3. Указать асс точки метода Ф на отрезке (О, 11 при и = 2, 3, 4, 5, 4. Применить метод Фь к функциям /(к) = и, Пя) = !з — 1! на отрезке 10,21 5. Найти наименьшее и, для которого точность метода золотого сечения хуже точности метода Фибоначчи я 2 раза. 0. Доказать, что число Фибоначчи Р'„язляется ближайшим целым числом к ((1-Ь ч- Л)/2) /Л. 7.
Доказать, что Решение УРазнениз (4.1) пРедставимо з виде /Ь„= ( — 1)" с'„>С>з 0 Ч-( — 1) >г зс>> (и =3,4,...), Отсюда вывести закон изменения погрешности величины /Ь„, если /з>, /зх заданы неточно. 8. Доказать, что последовательность (сз /лз ь!) сходится к т> — †(Л вЂ” 1)/2,монотонно возРастаЯ, а (сз >/Рз ) сходитсЯ к т, монотонно УбываЯ. 9. Используя утверждения упражнений 7, 8, доказать, что метод золотого сечения является единственным симметричным методом, удовлетворяющим условию (4.4) прн всех и = 1, 2...
10. ПУсть дан симметРичный метод с начальными отРезками >5 >, >5з, пУсть 7>г > 2 — заданное натуральное число. Используя утаерждения упражнений 7, 8, указать промежуток изменения отношения >5з/ьь>, чтобы метод удовлетворял условию (4.4) прн всех и = 1,..., 1ЬГ. И. Пусть дан некоторый симметричный метод, удовлетворяющий условию (4.4) при и = = 1. Используя утзер>кдения упражнений 7, 8, указать максимальное число ЬГ, при котором условие (4.4) выполняется для всех и=2,..., >>Г. 0 6.
Метод ломаных Описанные выше методы часто приходится применять без априорного знания о том, что минимизируемая функция является унимодалъной. Однако в этом случае погрешности в определении минимального значения и точек минимума функции могут быть значительными. Например, применение этих методов к минимизации непрерывных на отрезке функций приведет, вообще говоря, лишь в окрестность точки локального минимума, в которой значение функции может сильно отличаться от искомого минимального значения на отрезке.
Поэтому представляется важной разработка методов поиска глобального минимума, позволя>ощнх строить минимизирующие последовательности и получить приближенное решение задач минимизации первого и второго типов (см. $1) для функции, не обязательно уннмодальных. Здесь мы рассмотрим один из таких методов для класса функций, удовлетворяющих условн>о Липшица. О п р е дел е н не 1. Говорят, что функция /(х) удовлетворяет условию Липшица на отрезке [а, Ь], если существует постоянная Х > О такая, что ~Х(х) — Х(у)~ < Х [х — у[ ь/х, у Е [а, 6].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
