Ф.П. Васильев - Методы оптимизации (2002), страница 7

Таким образом, и-точечные (т, е. использующие вычисление значений функции в и точ- ках) последовательные и пассивные методы описаны, Если в определении 1 принять, что Я вЂ” класс унимодальных функций на отрезке [а, 6], Р = Ра — множество всех и-точечных последовательных (или пассивных) методов, А(/ р ) = Ьа — а †дли отрезка локализации минимума, полученного минимумом р для функций / = /(х) с 42, то придем к определениям гарантированной точности, оптимальйого и г-оптимального последовательного (пассивного) метода для унимодальных функций.

Кратко рассмотрим вопросы существования и построения оптимальных методов для таких функций, 3, Сначала остановимся на пассивных методах. Пусть р = [х1,...,ха) — какой-либо пассивный метод, а = зс < х! «... ха ( Ь = хаь!. Применяя его к какой-либо функции /(х) И ъъъ, получаем отрезок [х! 1, х,.ь!] локализации минимума этой функции, так что по- грешность метода р„здесь будет равна А(/ р )=хъь1-х, 1. Поэтому 6(р )= зпр А(/,ра)( 1 е !2 < шах (х 1 — х. !). пУсть шах (с!+! — хъ !) = хй„! — хй !.

Возьмем фУнкцию /а —— "!<1 1-1-1 ъ — 1 1 1<а = / (х) = [х-х,[. Это строго унимодальная функция достигает своей нижней грани на отрезке [а, ~] в точке х, = хй б [хь 1, хъ 1], причем А(/й, ра) = хъ 1 — хь !. следовательно, гаран- тированная погрешйость метода р на классе 42 равна б(р„) = !пах (х! „, — хъ,), Для 1(ъ<а получения оптимального пассивного метода остается выяснить, достигается ли нижняя грань ьп! 6(р ) = 6„, где Р— множество всех пассивных методов, и если достигается, то на каком Р, „е Р„ методе р„ и Р„. Оказывается, здесь нужно различать случаи четного и нечетного и.

Теорема 1. При всех нечетных и=2т+1 (т>О) существует бесконечно много оптимальных пассивных методов на классе Я; наилучшая гарантированная точность пассивных методов Рз ъ ! на этом классе равна (6 — а)/(т+ 1). Доказательство. Возьмем пассивный метод ра =(е1, .. а за), где е ъ =аж!(6— — а)/(т 4!) (ъ = 1, .. и т), а точки изъ „! (ъ = О, 1,..., ъи) расположены на отрезке [а, 6] ПРОИЗВОЛЬНО, ЛИШЬ бЫ Ъъз! ! < Озч < О21+ 1, Х21+ ! — Ъ21 ! < (Ь вЂ” а)/(!а+1). ОЧЕВИДНО, 6(Ра ) = = (Ь вЂ” а)/(т+ 1).

С другой стороны, для любого пассивного метода р = (х1,..., ха) (х, = =а<и!«...х (6=з „,, и=2т+1) имеем 6(р )= шах (з! ! — хъ !)>гпах(ь— и а!-1' 1(1(а хзз зг„зъ„з ° ! з4-хз~ хз — а) Э>(6 — а)/(т+1). Следовательно, методы р„оптимальны и 6„= (Ь вЂ” в)/(т + 1) Д Теорема 2. При всех четнь!х и =2т (т > 1) оптимального пассивного метода на классе ъ) нг существует; наьлучиъая гарантированная точность пассивных методов Р „ на этол! классе равна (Ь вЂ” а)/(пъ+!).

В качестве г-олтимального мгтода можно взять р =[о!, .. аз„), где аз! 1 — — а+ъ(Ь вЂ” а)/(т+!) — г, агъ -— а! ъ(6 — а)/(пъ41) Ьг (! =1,, т, О < г < (Ь вЂ” а)/(2(т+!))).. Доказательство. Сначала убедимся в том, что 6(р„) >(Ь вЂ” а)/(т-1-1) для лъобого пассивного метода Ра =(зъ, .. и за] (хо — — а<( х! «... ха < ъ = х „1, и = 2т). Обозначим з = а-Ь (Ь вЂ” а)/(тп+!). Имеются две возможности: либо хз > х, либо хх < х. Если х > х, то 6(ра) = шах (х +! — хъ !) ~ )хз — а> з — а=(ь — а)/(т+ 1), если же зз (х, то 6(р„) = 1( шах (х,+! — хъ !)>хх-а, В самом деле, еслибы шах (х,.ъ! — хъ !) <х -а, то зъч!— 1(!< * 1<1<а — ! (х — а (ъ = 1, ..

а т) и, кроме того, х! — а< за — а. Сложив эти неравенства, придем к противоречивому неравенству Ь вЂ” а< (пъ+!)(хз — а) ь (т+ 1)(х — а) = Ь вЂ” а. таким образом, при зз < х имеем 6(р„) = шах (х,.+! — хъ !) = 6(р„' !), где р„' ПаССИВНЫй МЕтад На ОтрЕЗКЕ [Хъ, 6], СОСтаВЛЕННЫй ИЗ ТОЧЕК Зг,, Ха МЕтада ра. НО И вЂ” 1 = 2т— — 1 — нечетное число, поэтому, применяя теорему! к отрезку [х1, 6], имеем 6(р„' !) >(Ь— -х!)/т, Тогда 6(р„) = 6(р„' !) >(Ь вЂ” х!)/пъ>(6 — В)/та=(6-а)/(т41), Тем самым доказано, что б(р ) >(Ь вЂ” а)/(т+1) при всех р„б Рз . С другой с~арапы, 6(р„,) =(Ь вЂ” а)/(т+ 1)+ г для всех г (О ( г < (Ь вЂ” а)/(2(т+!))).

Следовательно, б = (Ь вЂ” а)/(т ю!). 13 Из теорем 1, 2 вытекает, что предпочтительнее пользоваться пассивными методами с четным числом и = 2т точек, поскольку в случае и = 2т + 1 наилучшая гарантированная точность остается такой же, как и при и = 2т.

4. Перейдем к рассмотрению последовательных методов минимизации унимодальных функций на [а, Ь]. Здесь нам понадобятся знаменитые числа Фибоначчи, которые, как известно [193], ойределяются соотношениями Риаз 1а.1.1 ! Р ъЪ ! 2 ''' Р! Рх С помощью индукции легко показать, что и-е число Фибоначчи представимо в виде Используя числа Р, построим и-точечный последовательный метод, который принято назы- вать методом Фибоначчи. Этот метод относится к классу симметричных методов, описанных в э 4, и определяется заданием на отрезке [а 6] точки х! — — а+ (Ь вЂ” а)Р„1/Р„ъ! или симме- тричной ей точки хх —— а+ 6 — х! — — ач-(6 — а)Р /Ра „!. с помощью индукции нетрудно показать, что такой симметричный метод обладает свойством (4.4) и на Ь-м шаге (й < и), когда про- ведены вычисления значений функции в точках хъ,..., хъ, приводит к отрезку локализации минимума[ай,Ьй] длиной гзй — — Ьъ — ай — — (Ь вЂ” а) Ра й ь 2/Ра+ 1, причем точка хь (аъ < хй < Ьй) с вычисленным значением /(хй) = пип /(хъ) совпадает с одной из точек 1<1(й Р -ь хй — — аь + (Ьъ — аъ) " = ай -1- (Ь вЂ” а) —" й йра й,2 "'+!' (4) хй = аъ + (61,.

— аъ, ) —;: — т — = аг, + (6 — а) „= а, 4 Ьъ — х, Р— ь Га й й й 1г„й,2 Ра+ ! расположенных на отрезке [аь, Ь„[ симметрично относительно его середины. Как видно из (4), при 6 =и-1 точки х„' 1, хч ! совпадают. Это означает, что при Ь =и-1 первая часть процесса заканчивается вычислением значении функции в точке ха ! и определе- нием отрезка локализации минимума [аа 1, 6„1] длины 6„! — а„! — -(Ь-а)рз/Га ь ! — — 2(6— — а)/ба+!, причем точка зъ ! — — хъ ! — — ха ! совпадает с серединой отрезка [а„,Ьа !].

В аакл!очение, несколько нарушая симметричность процесса, последнее и-е вычисление зна- чения минимизируемой функции /(х) проводится в точке ха = и 1+ г (или х„= ха ! — г), где О < г < (Ь вЂ” а)/Ра+ 1, и отрезок [а„, Ьа] локализации минимума определяется по фор- МУЛаМ ааааа 1, 6„=З„1+г ПРИ/(За 1)</(Ха !+г) И за=ма 1, Ьа=Ьа ! ПРИ /(Х„1)>/(Ха !+а), таК Чта В ХудШЕМ СпуЧаЕ Ь -аа=(Ь вЂ” а)/Ра„ъ+г. ОПИСаННЫй Мвтад обозначим через Ф„.

Теорема 3. При всех и > 1 оптимального последовательного метода на классе унимодаяьных функций не существует; наилучшая гарантированная точность после- довательных л!етодоа на этом классе равна (Ь вЂ” а)/Р„!. В качестве г-оптимального метода можно взять метод Фибоначчи Ф, Доказательство этой теоремы можно найти в [148; 3741 684]„ Заметим, что число Ра 1/Ра „1, вообще говоря, является бесконечной периодической де- сятичной дробью, поэтому первая точка х! метода Фа будет задаваться на ЭВМ приближенно. Во избежание быстрого роста погрешности из-за неточности задания первой точки на практи- ке нужно пользоваться модификацией метода Фа, описанной в $4 для симметричных методов в общем случае.

Следует подчеркнуть, что метод Фа для своей реализации требует, чтобы число ъъ вычис. лений значений минимизируемой функции бьшо задано заранее — выбор первой точки в этом методе невозможен без знания и. В тех случаях, когда число и по каким-либо причинам не может быть задано заранее, можно применять метод золотого сечения, не требующий для своей реализации априорного знания и. Для сравнения вспомним, что методом золотого сечения за и вычислений значений функции мы получали отрезок [а, Ьа] локализации минимума длины Ь вЂ” а„' = ((ъ/3 — 1)/2)" '(Ь— — а) = (2/(Лч-1))" '(Ь вЂ” а). С учетом формулы Ра „! т ((~/5+ 1)/2)" + /чъб, вытека!ошей иа (3) при больших и, для метода Фа получаем отрезок локализации минимума, длина которого близка к (6- а)/Р ъ ! ш (2/(у!3+1))а ~ '(Ь-а)/члб.

Ото!ода следУет, что метод золотого сечениЯ хуже метода Ф при больших и всего в ((ъ/3+ 1)/2) /ъ/3 = 1, 1708... раз, т. е. на классе унимодальных !Рункций метод золотого сечения близок к оптимальным методам, Интересно 24 Гл. 1. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ ОДНОЙ ПЕРЕМЕННОЙ 8 8. МЕТОД ЛОМАНЫХ также заметить что Упражнении й О й 6.

Метод ломаных т. е гч - ! 3 — чг5 1 угв т/5 — 1 т. е. при достаточно больших и начальные точки х!, хв методов Фибоначчи и золотого сечения практически совпадают. 1. Найти гарантированную на классе унимодальных функций точность последовательного [или пассивного) п-точечного метода р„, если в качестве погрешности метода р„при минимизации функции / = /(х) принята велйчина /ь[/,р„) = [/, — /[х„)[[755[. 2.

Сравнить оптимальные и з-оптимальные пассивные методы на классе унимодзльных функции с методом деления отрезка пополам, 3. Указать все точки метода Ф на отрезке [О, 1] при и = 2, 3, 4, 5. 4. Применить метод Фз к функциям /(х) = х, /(х) = [в — 1[ на отрезке [0,2). б. Найти наименьшее и, для которого точность метода золотого сечения хуже точности метода Фибоначчи в 2 раза. В. Доказать, что число Фибоначчи Р„ является ближайшим целым числом к ((1 + + чгб)/2)" /т/5. 7.