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

26

МИНИМИЗАЦИЯ

ФУНКЦИИ

одной

ПЕРЕМЕННОЙ

[Л'1. J

Наконец, перейдем к рассмотрению последовательных

стратегий

Рп,

начинающихся с выбора s

точек

ult и2........... us 6

[а,

b],

2 <

s

<

< п . В этом

случае,

сравнивая

значения

J

(tij),

, J (us) ,

мы

най­

дем отрезок

[as, 6S], содержащий точки «*

и us, a s<^us <^bs

с

вы­

численным

значением J (us) — min J (u {).

Согласно следствию 3.1 при

I < L < S

на классе Q* [а, b]

будем

любых, даже самых наилучших действиях

иметь bs — a s > — ■

,

где т = - у

при четном s,

т =

--- ~ ■■ при

нечетном s ( / n > l ) . В

то же самое время,

оказывается,. первые s ша­

гов

плана Фп приводят к

отрезку

[a*. b*s]

меньшей длины

as =

Fn-

(b — a) <

< b s

т +

1

Это вытекает из

следующих неравенств:

2Fn+2 >

(s +

1) F n s +з

при

s =

2т + 1,

3 <

s <

п,

( 1)

2Fn+2 >

(s +

2) F„_s.l3

при

s =

2in,

4 <

s <

n.

(2)

Справедливость

неравенства

(1)

при s = 3 и

(2)

при

s = 4

легко

установить с помощью индукции по п.

При всех s ^ 4 ,

оказывает­

ся,

верно более сильное неравенство (2),

вытекающее из монотон­

ного убывания

(s + 2 )

F„_s+3 при возрастании s

от s = 4 до s = ti:

(s +

2) F„_s+з =

(s +

2) Fn- s+2 +

(s + 2) Fn_ s+l >

(S + 2) F n- s + 2 + Fn—s_|_2 = (s + 3) F n- s +2.

При поиске точки u* на отрезке [as, bs] можно вычислить зна­

чения функции еще в п—s + 1

точках Зтого отрезка, включая точку

ds. Если даже точка й$ на [as,

bs] расположена очень удачно и до­

пускает применение оптимального

(в силу индукции) плана Ф п- з + i

на отрезке (as, bs] с участием точки й 3,

мы сможем получить лишь

бп.(Р„, b — a ) > bn-s+i (Фп- s+ь bs— a s) =

bs—as

>

bs ~

a s

Fn-s+3

Fn-,s+з

b — a = б*(Ф „, b — a).

/2+2

Таким образом, случай 2 <^s<Cn также

рассмотрен.

Ь — а

,

. Ь— а

п

. 6 — а

. „

— ------ <

8 <

— ------ ИЛИ

F n+l <

----------<

F n+2.

г п+*

* п+1

Е

точку и* минимума функции / (u )eQ *[a ,

Ь] с заданной точностью

s > 0 ,

произведя л наблюдений

значений

/(«),

не

превышает

e F п+2-

§

7. ОПТИМАЛЬНЫЙ ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК

ДЛЯ ЗАДАЧИ Б

Т е о р е м а 1. Для

задачи Б наименьшая возможная гаранти­

рованная на классе Q*[a, Ъ\погрешность равна

6„ (Ь— а) =

-b~ a- 1

однако оптимальной последовательной

2Fя+1

стратегии Р п при п~>\ не

существует.

Д о к а з а т е л ь с т в о . П р и л = 1

независимо

от

выбора

точки

их6 [а, Ь] (и даже не вычисляя

значения

J (их)) можем

положить

*

a -j- Ь

. *

* I

-

Ь — а

b — а

^

Ui = -----1—

с погрешностью |и — щ \- < ----------=

-----------. Очевидно,

2

2

2F2

любой

другой выбор «1

может

привести

лишь,

к большей

погреш­

ности. Теперь покажем,

что для

любого в,

0

<

е <

&~

а- , '

и

лк>

2Fn+1

бого л > 1 можно построить последовательный план Фл ,

для

кото­

рого

Ь — а

Ь — а

<

I 8.

< ? п (Фп, Ь — а)

2Еп+1

2Ел+1

План Фл будем строить следующим образом. На

отрезке [а, Ь] сна­

чала реализуем описанный при решении

задачи А фибоначчиев

план

Фп- 1 =

Фп—1 и получим'отрезок

[ал- ь

bn- i]

длины

28

МИНИМИЗАЦИЯ

ФУНКЦИИ

о д н о й

ПЕРЕМЕННОЙ

[,Гл. Т

После этого положим ип = un- i +

е, вычислим значение

J (ип)

и оп­

ределим

точку ип следующим образом:

— (an- i

+ ип), если

J (un_,) < J

(ип),

ип =

- у («л-1

+ Ьп~0, если J

(u„-i) >

J («„).

Принимая

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

и*, допустим

погрешность

■ип |< ип — «п-1

Ь— а . е

2F,л+г

Таким образом;

план Ф „,

гарантирующий погрешность,

как

угодно

близкую

к ——

-а-, построен при всех

п >

2 (рис. 3).

2F,п+1

(в-а))

Р и

с.

3

Далее докажем, что

б)? (b — а) =

inf бп (Р„,

Ь— а) =

ь ~ а . При всех я — 1, 2, . . .

,

рп

2Fn+l

а также убедимся в том,

что б„ (Рп, Ь— а) >

—— — для любой пос-

Рп при

2F„+1

ледовательной

стратегии

всех я > 2 . Как

было показано

выше, при п =

1 имеем 6f (b — а) =

—— —. При я =

2, очевидно,

6 l(P 2,

Ь - a )

=

Ъ— а

2Fs

4

для любой стратегии Р 2.

С другой стороны,

для любого е > 0

мож'

но указать стратегикГФг,

для которой

§ 7]

Оптимальный

последовательный

поиск

для задачи Б

29

Следовательно,

б! (b -

а) =

inf б! (Р2, b -

а)

=

2Fs

рг

причем нижняя грань

здесь

не

достигается.

Сделаем

индуктивное-

предположение:

пусть

6fc>

-

a

)

=

-

|

-

=

^ -

<

8

b ~

а )

^ k + i

для любой последовательной

стратегии Pk

при всех

k =

2,

3,

. . . „

га— 1, (га >

3),

и докажем, что тогда

б * ( й _ а ) ь = - А = ^ - < б Б ( Рл1 ь _ а)

ЛгП+1

для всех последовательных стратегий Рп.

Возьмем

произвольную

последовательную

стратегию

Р п.

(га^ З). Согласно определению

4.1 стратегии

Р п вначале

выбира­

ются точки щ,

и2, ....

us^ [a, b],

(l s^s^ra) .

Как и в задаче А, не-

умаляя общности, можем считать, что

2 ^ 's ^ ra

(см.

доказатель­

ство теоремы 6.1).

Сначала рассмотрим случай s = 2 < r a ,

когда стратегия

Рп начи­

нается с выбора двух точек а <

их< м2 •< Ь.

Начальные точки пла­

на Фп- i на [га,

b] обозначим через

га| = а-Ь

Fn~1— (b — а),

и2 — а-\------ ^ — (Ь — а).

Бп+1

Fn+i

Возможно

их •< га* или га± >

щ.

Пусть

сначала

и1 <га*.

Тогда

в худ­

шем случае

«*€[га.,

Ь\,

причем

для

поиска га'

на

[ralt Ь]

можно-

вычислить значение

функции еще

в га —

1

точках

этого

отрезка,,

& —

^ ь — и\ _ Ь— а

2Fп

2Fп

2Fn+i

для

любых стратегий Pnt

начинающихся с выбора двух

точек rals.

ы2,

га < гах< ! га2^ Ь\ где

Аналогичные рассуждения

показы­