Файл: Васильев Ф.П. Лекции по методам решения экстремальных задач.pdf

12

МИНИМИЗАЦИЯ ФУНКЦИИ о д н о й ПЕРЕМЕННОЙ

[Гл. 1

вете на эти вопросы будем различать задачи А и Б.

1.

Начнем с задачи А.

Пусть для некоторой функции / (ы

e Q *[a , b] с помощью пассивной

стратегии Р „ = { « £}

(i— 1,

...,

п)

среди точек

{« ,}е [« , Ь] выбрана точка uk, J (uk) = m in / («£)

и от-

резок [«ft_i,

«ft+i], содержащий точку и*

минимума /(«)

на [а,

Ь].

В задаче А в качестве приближения к и*

принимаем точку

и* =

uk,

допуская при этом погрешность

I и ” — и п I < т а х { “ *+1 ~

ы«> «ft — « ft - i} .

Очевидно любой другой выбор

и* с вычисленным

J

(«*)

для

резков [«,--1, «i+i]

( i = l , 2, ..., п) и погрешность \и* — «*| будет как

угодно

близкой

к шах{«,-+1— «,-, «£— «£_ 1}

(например, если

шах {«,+1— щ, iii— «i_i} =

«,+1— щ, то можно взять

— « -!- «i+i— 8 при « ^ « i+i— 8,

J g («) —

Щ-\) (и — ui+1 - f e)

при

« >

«i+i— e,

-J- («t+1 ~

где e

достаточно

малое

положительное

число).

И поскольку

^ Q*[a, b] и в

качестве гарантированной на Q*(a, 6]

точности в оп­

ределении и*

с помощью стратегии Р п должны взять максималь­

ную из возможных погрешностей;

шах ш ах{ « £+1 — «,, u£ — uC- i } =

max {«£+, — и£) =

L„ (Р , Ь — а).

Величина

Ln (Рп, Ь — а) от

/ (« )e Q * [a , b] не

зависит и ха­

рактеризует стратегию Р п на классе функций Q *[a, Ь].

Теперь естественно считать,

что пассивная стратегия Р п луч­

ше другой пассивной стратегии

РП, если

Ln(Pn>b — a)

<^L„(Pn, Ь— а).

§ 3]

Оптимальный пассивный поиск в задачах А и Б

13

■ О п р е д е л е н и е 2.

Пассивную

стратегию

Рп

назовем

опти­

мальной для задачи А, если Ln (Ь— а) = Ln {Рп>Ь— а).

Т е о р е м а

1. Для

задачи А при всех

1

оптимальная пас­

сивная стратегия существует, единственна и имеет вид

°п = Jt»i = а

■ Ь— а . .

уП

I

,

I

1 , •••

а + 1

Д о к а з а т е л ь с т в о . Прежде всего,

очевидно Ln(Pn, Ь— а) =

_= ь

а д дя

любой другой

пассивной

стратегии P n= W i} : я =

п

1

— < « n ^ « 7i+i = Ь всегда

отрезок [ии,

i= « o ^ « i< U 2<

найдется

■Wft+i] длины Uft+i— uk >

°

• и®°

в

противном

случае

сумма

длин всех отрезков [«i,

щ+{\

(f = 0,

1,

...,

п) будет меньше длины

отрезка [а, b]. Следовательно,

Ln (Р„, Ъ — а) =

шах {«i+i — и£} >

Ь ~ а

О<£<п

п

+ 1

для любой пассивной стратегии Р ц,

причем равенство здесь дости­

гается только при Рп = Рп. А

стратегии

P n= W i}

для некоторой функции / (u )eQ *[a,

Ь] найден

отрезок [Uh-u иь+ij,

содержащий точку и* минимума J (и)

на [а, Ь].

В задаче Б значение J (и*) нас не интересует, поэтому в качестве

приближения к и*

можем

взять и* = — (ы*—i +

Uk+\),

допуская

при этом

погрешность \и* —

— uk-\)

(любой другой

выбор и*

может

привести

к увеличению погрешности

при соот­

выбора стратегии Р п и функции / (n )eQ *[a, Ь].

Для любой фик­

сированной пассивной стратегии Р п= { щ }

нетрудно указать функ­

цию / (« )e Q *[a ,

b), для которой отрезок [«й_ ь

содержащий

точку «*,

будет

совпадать с любым из наперед

взятых отрезков

[Ы{-ь Щ+1]

( i = l ,

ti), и погрешность lu

— ипI

будет как угодно

•близкой к

— («£+1 — tii—i) (см., например,

функцию J&(u) из п. 1).

16

МИНИМИЗАЦИЯ

ФУНКЦИИ о д н о й ПЕРЕМЕННОЙ

[Л/1. /

Из теорем 2— 3 непосредственно вытекает

С л е д с т в и е 1.

Для

любой пассивной стратегии Р п= { щ }

на

отрезке [а, Ь] существует

функция 7 (u )e Q *[a ,

b], такая,

что

для

тройки

точек ап, Ьп,

ип,

локализующей точку минимума J (и) на

[а, 6] по точкам щ,

ип,

справедливо неравенство

Ь п - а п > ± = ± - = 2 1 * ( Ь - а ) ,

т-\- 1

где т — - j- для четных п, т = -п ~ 1 для нечетных п (п >

1).

Как видим, при решении задачи Б с помощью пассивных стра­

тегий предпочтительнее брать четное число п — 2т, поскольку

l L + i (b -

а) = Lfm (b — а) = .

?

2(/л+ 1)

О п р е д е л е н и е 1. Пусть / («)eQ *[fl,

Ь]. Скажем,

что на от­

резке [а,

Ь] задана последовательная стратегия Рп, если:

1) задано'

правило

выбора

первых

нескольких

точек и\, и2, ...,

us^ [a, b

( l ^ s ^ n ) ,

из которых определяются три точки as, bs,

й3, локали­

зующие точку

минимума

/(«) на [а,

b]

(см. определение 2.2);

2) если

l^ s < ;n , то по известному правилу на отрезке [cs, 6S] вы­

бирается

несколько точек

«s+i> •••> ии i(l ^.s<C.k^.n) и среди точек.

us, us+1, ...,

Uk определяется тройка аь,

bh, йь, локализующая точку

минимума;

если k< in , то на [a?,, 6/J по некоторому правилу выби­

тройка От, Ьт, йт и т.

д. Этот процесс продолжается до тех пор,,

пока не будет выбрана

последняя п-я точка и определена соответ­

ствующая тройка

а п, Ьп,

йп, локализующая точку, ы*

минимума

/ (и)

на [а,

Ь]; 3)

имеется

правило, по которому одна

из точек,

ы* £

[а п, 6Л]

принимается в качестве приближения для и*.