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

Скачать файл (13,51Мб)

Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 11.04.2024

Просмотров: 188

Скачиваний: 1

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

30	МИНИМИЗАЦИЯ ФУНКЦИИ	о д н о й ПЕРЕМЕННОЙ		[Га. 1
	Ь - а ) >		Ъ— а
	Ь - а ) >		2Fn+i
			2Fn+i
	Пусть теперь щ > и \ . В худшем случае точка и*			мажет на
ходиться на отрезке [a, ui] длиной
	•		F
	их — а'> и \ — а =	— 2=i— (b — а ),

Fn+1

и для установления этого обстоятельства мы должны сделать по крайней мере три вычисления значений функции, причем хотя бы одно из них во внутренней точке отрезка [a, иД Следовательно, для поиска- и* на [а, щ] в своем распоряжении мы имеем самое боль шее п—2 вычисления значений функции на этом отрезке. Однако по предположению индукции

6,1_о («х — а)	их — а ^ ы\|— а	b — а
	2Fn-г ^ ZFn-г	2F„+i

так что

6«(Рп, Ь — а) > - Ь~ - а- И при

Аналогично доказывается это неравенство для случая ы2< « 2. Та ким образом, для всех стратегий Р„, начинающихся с выбора двух точек их, u2 6 [а, b] (s = 2), имеем

бЪп(Ра, Ь - а ) > - ± = £ - { П > 3).

^Гл+1

Перейдем к рассмотрению последовательных стратегий Рп, начи нающихся с выбора s точек uv иг, . . . , us 6 [а,Ь\, 2 < s < n . В этом случае, сравнивая значения J (uj), . . . , J ( u s), найдем отрезок [as, 6S],

содержащйй точки и*	и us,	a s<		us< jb s, с		вычисленным			значением
J (us) = min J (uj). Согласно следствию					3.1	при	любых даже			самых
l < i < s					будем иметь
наилучших действиях на классе Q* [a, b]					будем иметь
bs— a s >		Ь— а		где	т =	— > 2
bs— a s >				где	т =	— > 2
	т + 1			’		2
при четном s, т =	>	1	при нечетном s > 3 .
Далее нам понадобятся неравенства:
2Fn+i > ( s + 1) F n s +2			при всех		s =	2т +	1,	3 < s < /г
и
2Fn+i> ( s +	2)F„_s +2 при всех				s =	2in,	4 <	s <	n,	( 1)

§ Л

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

для

задачи

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

которых

при

п — 1

вытекает

из

неравенств

(6 .1 — 2),

при s =

(1)

просто

доказать

помощью

индукции

по п.

стратегии

Рп оказалось

s = п, то

Если

бВп(Рп,

b — а) >

Ь— а

Ь — а

2Fп+1

2(/п+1)

в силу

следствия 3.1

неравенств (1)

при

s = n .

Поэтому

пусть

3 ^ s ■< п — 1.

Однако в этом

случае

первые s шагов

плана

Фп—i

приводят к

отрезку [а*, 6*] меньшей длины:

Ы - as = - - ^ - (Ь— a) < J ^ L < bs- a s,

Fn+i

m + 1

что вытекает из неравенств (1). Для

получения

отрезка

[as, bs] нам

понадобилось s значений функции,

поэтому для

поиска и1 на [as, 6S]

мы имеем в распоряжении еще п — s + J

значение

функции

на этом

отрезке,

включая

точку us с известным J (us).

Однако

по

предпо-

' ложению индукции

6®_s+i {Ь — а) =

bs — as

2Fn-s+г

поэтому

8ъп (Рп, b - a ) > -bs- -as

•flo

b — a

2F„_s+2

2Fn+1

2/Vj-s+2

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

доказано,

что бб„(, Рл,

b — а) >•

b — а

для любой

последовательной стратегии Рп (п >

2Fn+i

любого е,

2), и, кроме того, для

О <с е <

■ Ь~

, существует

стратегия

Фп,

для которой

2Fл+1

Ь— а) <

Ь — а

бп (Ф п,

2Fп+1

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

6 ® ( й - а ) =

inf6^(P„,

b — а ) =

Рп

2Fn+1

Заметим, что величина е на практике не может быть сколь угодно малой в силу ограниченных возможностей измерительных приборов, ЭВМ и тгп. Пусть е > 0 — тот наименьший сдвиг между

числами, который можно измерить, и пусть 0 < ^ 8 < [-^ — — . Учи-"

2Fn+i

тывая конечность числа е, вместо описанного выше плана Фп можно использовать следующий более точный и полностью сим-

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

[Гл. 1

метричный план [230]. Этот план начинается с двух симметричных на [а, b] точек

ик = а + — — (b — а) + - Fn-n

1)nfl -в, ut = а + b — ик. F/i+1

Если после k вычислений функции найден отрезок						[aft,	(& >1;
а ± — а, ЬХ=	Ь), содержащий точки и*			и ик с	вычисленным		значени
ем J (ик) =	min /(«■), то	следующая		точка	берется	так:	Uk+i —
= ak + Ьк — ик и т. д. После п вычислений получим отрезок							[ап, Ьп\,
и можем положить ип =		я" Ьп .	С	помощью индукции			нетрудно
показать, что
	^ '	Ь —	а	Fn- 1
	^ '	&П\|^		2Fn
		2F,n+l		2Fn

Теперь можно ответить на вопрос: сколько следует произвести наблюдений значений /(к), чтобы с заданной точностью б> 0 оп ределить точку и* минимума /(i/)eQ *[a, 6 ]? Количество необхо димых для этого наблюдений равно наименьшему из чисел п, удов летворяющих неравенству

	Ь — а	I Fa-1
	2fn+i	Fn+i
Очевидно также, что гарантированная наименьшая возможная
.длина	отрезка [а„, Ьп], содержащего точку и*			минимума / (u )s
e Q *[a ,	b], который может быть получен по наблюдениям значений
этой функции в п точках		( п ^ 2 ),	задаваемых	последовательно,
всегда	больше 26^ (Ь— а) =	—— — .	Наконец, длина отрезка [а,Ь],
		Fn+i

на котором с заданной точностью 6 > 0 можно найти точку и* ми нимума / (ii)eQ *[a , b] по п наблюдениям значений /(w), меньше

Шп+Х.

§ 8. МЕТОД ЗОЛОТОГО СЕЧЕНИЯ

Описанные выше планы Фибоначчи являются эффективным методом отыскания точки и* минимума функции J(u )^ Q *[a, Ь]. Однако, к сожалению, нельзя воспользоваться планами Фибонач чи, не зная заранее числа п предполагаемых наблюдений значений ■функции, ибо выбор первых точек и\, «2 в этих планах требует знания числа п. Между тем на практике встречаются ситуации, когда число п по каким-либо причинам не может быть заранее определено. Иногда желательно не ограничивать себя каким-то

.наперед заданным числом п наблюдений значений J (и) и прово

§ «] Метод золотого сечения 33

дить наблюдения до тех пор, пока не удовлетворится какой-либо интересующий нас критерий, попутно стараясь, однако, чтобы ис пользуемый метод поиска по возможности скорее привел к точке минимума. В этом случае можно пользоваться методом деления отрезка пополам, не требующим знания числа п наблюдений зна

чений /(и). Однако существует еще один метод,	который также
не зависит от намечаемого числа п значений J (и)	и который при

достаточно больших п почти столь же эффективен, как и метод Фибоначчи. Это — метод золотого сечения [230].

Как известно, золотым сечением отрезка называется деление отрезка на две неравные части так, чтобы отношение всего отрезка к большей части равнялось отношению большей части к меньшей. Нетрудно проверить, что золотое сечение отрезка [а, Ь] произво дится двумя симметрично расположенными точками

их = а		3_^ 5			ы2 = а + b — их =
их = а		--------— (Ь— а) и			ы2 = а + b — их =
		= а +		(b — a),		u1< w 2,
причем
ь — а_ =	Ь-	их =	Ь — а	= , и, — а	=	1 + V5 _ j ^18033989.
Ь — их	их— а		щ — а	Ъ— и2		2

Замечательно здесь то, что точка щ в свою очередь производит золотое сечение отрезка [а, и2]: здесь

	и„ — их<^их— а = b — и2; и2— а								Г их — а
							их— а		« 2 — % ’
Аналогично точка и2 производит золотое сечение отрезка [«ь Ь\.
Опираясь		на	это свойство золотого сечения,							можно предложить
следующий метод поиска				точки и* минимума функции J (и) в Q* [а, Ь].
А именно сначала на отрезке [а, Ь] берем точки										их и и2,	задающие
золотое	сечение отрезка			[а,	Ь\ =	[ах,	6 Х].	Сравнивая J(u x) с J (и2),
находим	новый отрезок ,[а2,				А,],	а2 <^и* К		Ьг,	причем
	Ь2— = и 2 — а = Ъ— их						У 5— 1 {Ь — а),
								2
и на отрезке		[а2,	6 2] ’ находится			точка	w2, совпадающая с				одной из
точек их или		и»,	в которой		J (и2) = min J (щ)				и производящая золо-
						i< ;< 2					_
тое сечение отрезка [а2,				Ь2].	Далее берем			симметричную с и2 точку
и3 — аг + Ь2— Щ,			также	производящую				золотое		сечение	отрезка
[а2, 6 2],	вычисляя		значение J (и3)			и сравнивая			его	с J (u 2),	находим

2 Ф. П. Васильев

34 МИНИМИЗАЦИЯ ФУНКЦИИ ОДНОЙ ПЕРЕМЕННОЙ [Гл. I

новый отрезок [о3,

6 а], а 3<

и* <

Ь3, и т. д.

Пусть уже

известен

от

резок

/ " с " ___ J

V Л — 1

(— ------J

(Ь — а)

известна

точка ип, ап< ы л <

Ьп, производящая золотое сечение отрезка [ап,

6 „]

и _совпадающая

одной

из

точек

ult

и.,, ■<. ,

ы„,

которой

J (ип) =

min J (и,).

Тогда

качестве

« л+1

возьмем

точку

l<i<n

ип^\ =

ап -\-Ьп— ип,

также

производящую

золотое

сечение

отрезка

[ап, Ьп], вычисляем

значение J(u n+\)

и, сравнивая

с J(u n),

находим

новый отрезок

[я,1+ь b,i+i],

an+i < w* <

bn+i,

Ьп+1 — ал+, = [ ^

1 ) (ь — а)

и т. д. Процесс продолжаем до тех пор, пока не получим ы* с до статочной точностью или пока не выполнится другой интересующий нас критерий.

Пусть мы остановились на	п-м	шаге	(п > 2) и нашли отрезок
[a„, 6J , а„ < « * <& „. а также	точку	«л,	а„ < > „ < & „ , с вычислен