Материал: Бородакий Нелинейное программирование в современных задачах оптимизации 2011

Скачать файл

Заказать новую работу

Внимание! Если размещение файла нарушает Ваши авторские права, то обязательно сообщите нам

Вход

Ввод исходных данных: a , b , ε ,

= b − a, xл = a + r1 ,

xп = a + (1 − r1)

Вычисление fп = f (xп),

fл = f (xл)

Нет

Да

fл ≤ fп

a = xл ,

b = xп ,

= b − a,

= b − a ,

xл = xп ,

xп = x л ,

xп = a + (1 − r1 )

x л = a + r1

fл = fп,

fп = fл,

fп = f (xп)

fл = f (xл)

Нет

≤ ε

Да

x = xл, fл ≤ fп;

xп, fл > fп.

Выход

Рис. 1.7. Блок-схема алгоритма метода «золотого сечения»

Решение. Как отмечалось выше, условием достижения точности является выполнение неравенства

n ≤ ε .

Поскольку

n = r2n (b − a) ,

то отсюда

r n (b − a) ≤ ε,

и, как следствие:

r n

≤

b − a

ln(r2

)≤ ln

b − a

n ln r2

≤ ln

b − a

так как r2 <1, то ln r2 < 0 . Следовательно,

n ≥ ln

ln r2

≈ −2,1 ln

− a

Так как

< 0 ,

то n ≈ 2 .

b − a

Задача 2. Найти методом золотого сечения точку минимума функции f (x) = x2 − x на отрезке [0, 2] с точностью ε = 0,1 .

Решение. Очевидно, что данная задача может быть легко решена классическим методом. Взяв производную исходной функции и приравняв производную к нулю, получим уравнение для нахождения точки экстремума:

2x* −1 = 0 = −0, 25 .

Разрешив последнее уравнение относительно x* , получим: x = 0,5, f = −0,25.

Решим задачу с помощью метода «золотого сечения». В соответствии с рассматриваемым методом r1 = 0,382 , r2 = 0,618 .

Учитывая это, результаты пошаговых расчетов можно свести в табл. 1.1.

								Таблица 1.1

n	n	bn		an	xл	xп	f (xл)	f (xп)
1	2	0		2	0,764	1,236	–0,180	0,26
2	1,236	0		1,236	0,472	0,764	–0,241	–0,18
3	0,764	0		0,764	0,292	0,472	–0,207	–0,24
4	0,472	0,292		0,764	0,472	0,584	–0,249	–0,2
5	0,292	0,292		0,584	0,404	0,472	–0,241	–0,2
6	0,18	0,404		0,584	0,472	0,515	–0,249216	–0,2
7	0,112	0,472		0,584	0,515	0,541	–0,249775	–0,2
Как	следует из		таблицы,		x ≈ 0,515,		f ≈ −0,249775 , что

совпадает с результатами, полученными с помощью производной. График, соответствующий исследуемой функции, приведен на рис. 1.8.

Рис. 1.8. Графическое изображение функции (задача 2)

1.2.3.2.Метод дихотомии

Вэтом методе используются производные целевой функции, поэтому он применим только в том случае, когда производная функции вычисляется достаточно просто.

В основу метода положен тот очевидный факт, что производная унимодальной функции меняет знак на отрезке поиска только один раз – в точке минимума (рис. 1.9).

Рис. 1.9. Характер производной унимодальной функции

Идея метода такова: на концах рассматриваемого отрезка вычисляют производные целевой функции, отрезок делят пополам и вычисляют производную в средней точке. Для следующей итерации выбирают тот отрезок из двух получившихся, на концах которого знаки производной различны, так как именно этот отрезок

содержит точку экстремума.
Это – общая	идея	метода,	которая фактически сводит
рассматриваемый	метод	к поиску	′
			корня уравнения f (x)= 0 на

отрезке [a, b] известным методом дихотомии. Эта идея работает, когда минимум функции f(x) является внутренней точкой отрезка [a, b]. Если x лежит на границе, то ситуация несколько иная,

однако в алгоритме, который будет изложен ниже, эта проблема не затрагивается.

Метод дихотомии дает более быстрое уменьшение отрезка, чем метод «золотого сечения». После n итераций длина отрезка

составляет 0,5n (b − a) , тогда как при использовании метода

«золотого сечения» длина отрезка будет – r n (b − a),	r ≈ 0,61 .
2	2

Приведем таблицу коэффициентов уменьшения исходного отрезка
[a, b] после n итераций для методов дихотомии					и «золотого
сечения» (табл. 1.2).
					Таблица 1.2

n	1	2	3		10

r n	0,61	0,38	0,23	...	0,0080
2
0,5n	0,5	0,25	0,125		0,001

Основной недостаток метода заключается в вычислительных трудностях, связанных с определением производных функции f (x) .

Алгоритм метода дихотомии (поиск минимума).
1.	Задан отрезок [a, b]. Вычислить длину отрезка	= b − a .
2.	Вычислить среднюю точку отрезка xc = a + 0,5	и значение

производной

dfdx (xc ).

Если производная равна нулю (с точностью ε1 ), то вычисления прекращаются – x ≈ xc .

Если производная меньше нуля, перейти к шагу 3. Если производная больше нуля – к шагу 4.

3. Положить a = xc . Вычислить = b − a .

Если ≤ ε2 , то закончить вычисления, положить x ≈ xc . В противном случае – перейти к шагу 2.

4. Положить b = xc . Вычислить = b − a .

Если ≤ ε2 , то закончить вычисления, положить x ≈ xc .

В противном случае – перейти к шагу 2. Блок-схема алгоритма приведена на рис. 1.10.

Источник: https://studfile.net/preview/16708738/

Смотрите также:



_1966(~1
_Антонян Ю.М., Сексуальные преступления. Чикатило и другие
_РГР № 1 (2)
- Габариты и масса 27
'Образ–Я' и его развитие средствами диалога
"Логистическая технология JIT"
"Особенности правовой системы Российской Федерации" по дисциплине "Теория государства и права"
«Анализ ликвидности и платежеспособности предприятия» (на материалах ОАО Московская кондитерская фабрика «Красный Октябрь»)