Материал: Методы оптимизации в примерах и задачах. Медведь Н.А., Фокин А.А

Скачать

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

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

 

b

a

 

z

a

или

b-a

=

b-z

 

(2.1.3)

 

z

a

 

b

z

b-z

z-a

 

 

 

 

 

Золотое сечение отрезка [a,b] производят две точки:

 

c

a

(1

)(b

a)

 

 

 

 

 

 

(2.1.4)

 

 

 

 

 

d

a

(b

a),

=0.5(1- 5) 0.618,

При этом, точка с производит золотое сечение отрезка [a,d], а точка d - золотое сечение отрезка [c,b].

Вычислим f(с) и f(d). Если f(с)<f(d), то отбрасываем интервал

]d,b[ и полагаем

 

 

 

 

 

 

 

 

 

a1 = a, b1

d , d1 c, c1

a1

(1

)(b1

a1 ).

Если f (c)

f (d), то полагаем

 

 

 

 

 

 

 

a

c, b = b, c = d, d = a

1

+ (b -a

).

1

1

1

1

 

 

1

1

 

Таким образом, на каждом следующем шаге метода золотого сечения требуется вычислить лишь одно значение унимодальной функции.

Приведем план организации вычислений при поиске точки минимума x* функции f методом золотого сечения с абсолютной

погрешностью .

 

 

 

 

 

 

 

 

 

 

 

 

 

1.

Вычислить с и d по формулам (2.1.4).

 

 

 

 

 

 

2.

Вычислить e

 

f (c)

f (d). Если e <0, перейти к п.5; если

 

e =0, перейти к п.7; если e >0, перейти к п.3.

 

 

3.

Положить а=с и вычислить h

b

a

 

, при этом если

 

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

h

, то x*

 

a

b

,

fmin f(x*).

 

 

 

 

 

 

 

 

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4.

Положить c=d и вычислить d по (2.1.4). Перейти к п.2.

 

5.

Положить b=d и вычислить h

b

a

 

. Если h

, то

 

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

x*

a b

,

fmin

f(x*).

 

 

 

 

 

 

 

 

 

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6.

Положить d=c и вычислить с по (2.1.4). Перейти к п.2.

 

7.

Положить a=c, b=d и вычислить h

 

 

 

b a

. Если h

,

 

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

23

то положить x*

a b

, fmin f(x*); в противном случае

2

 

 

перейти к п.2.

Если количество вычислений n функции f задано, то оптимальной стратегией поиска минимума является метод Фибоначчи. Этот метод связан с последовательностью чисел Фибоначчи {Fk}, определяемой соотношениями

Fk 2 Fk Fk 1 ,

F1 F2 1

Первые четырнадцать членов этой последовательности

имеют вид:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377.

Приведем план поиска на отрезке [a,b] точки х*, минимизирующей функцию f, основанный на использовании чисел Фибоначчи. Количество вычислений значения функции задано и равно n.

1.Сравнить 1 и n:

а) если n=1, перейти к п.2; б) если n>1, перейти к п.3.

2.

Вычислить x*

 

a

 

b

,

fmin

f(x*). Конец.

 

2

 

 

 

 

 

 

 

 

 

 

 

 

3.

Вычислить

 

 

 

 

 

 

 

 

 

 

 

 

x a

 

Fn

 

(b

a), x

 

=a+

Fn+1

(b-a)

(2.1.5)

 

 

 

 

2

 

 

1

Fn

 

 

 

 

 

Fn+2

 

 

 

 

2

 

 

 

 

 

 

 

4.Вычислить f(x1), f(x2).

5.Сравнить 2 и n:

а) если n=2, перейти к п.6; б) если n>2, перейти к п.9.

6.Сравнить f(x1) и f(x2):

а) если f (x1 ) f (x2 ), перейти к п.7; б) если f (x1 ) f (x2 ), перейти к п.8.

7. Положить

x*

x1

, fmin

f (x1 ). Конец.

8. Положить

x*

x2

, fmin

f (x2 ). Конец.

9.Сравнить f(x1) и f(x2):

а) если f (x1 ) f (x2 ), перейти к п.10;

24

б) если f (x1 ) f (x2 ), перейти к п.13.

10. Произвести следующие переобозначения:

x2 = b, x1 = x2, n-1 = n.

11. Вычислить:

x a

Fn

 

(b a).

(2.1.6)

 

 

1

Fn

 

 

 

 

2

 

 

12.Вычислить f(x1) и перейти к п.6.

13.Произвести следующие переобозначения

x1 = a, x2 = x1, n-1 = n.

14. Вычислить:

x

a

 

Fn 1

(b a).

(2.1.7)

 

 

2

 

 

Fn 2

 

 

 

 

 

15. Вычислить f(x2) и перейти к п.6.

 

Погрешность

 

найденного по методу Фибоначчи значения

х*, минимизирующего функцию f, имеет оценку:

b a . Fn 2

Для большей наглядности метода Фибоначчи приведем блоксхему вычислений (рис. 2.1.1).

25

Пример. Определить минимум функции

 

1

 

 

 

f (x)

 

x

 

 

x

 

 

 

 

на отрезке[1,2] с помощью шести вычислений функции.

Решение будем искать с помощью методов дихотомии и

золотого сечения:

 

 

 

 

а) Метод дихотомии Полученные в процессе вычислений значения переменных

удобно записывать в виде таблицы:

26

a

b

δ

c

d

f(с)

f(d)

h

1

2

0.1

1.45

1.55

1.8938

1.890

0.275

1.45

2

0.1

1.675

1.775

1.891

1.896

0.1625

1.45

1.775

0.01

1.6075

1.6175

1.8899

1.890

0.084

1.451.6175

 

 

x*

1

 

(1.45

1.6175)

1.534,

 

 

 

Ответ:

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

f (x*)

1.89034,

 

0.084.

 

 

 

 

б) Метод золотого сечения

 

 

 

 

a

b

c

 

 

 

d

 

f(с)

f(d)

e

h

1

2

1.382

1.618

1.89918

1.89005

e<0

0.309

1

1.618

1.236

1.382

1.90208

1.8992

e>0

0.191

1.236

1.618

1.382

1.472

1.8992

1.8926

e>0

0.118

1.382

1.618

1.472

1.528

1.8926

1.8906

e>0

0.073

1.472

1.618

1.528

1.5623

1.8906

1.88999

e>0

0.045

1.528

1.618

 

 

 

 

 

 

 

 

 

 

 

 

Здесь e вычисляется по формуле

 

 

 

 

 

e

f (c) f (d)

 

 

 

 

 

 

 

x*

1

(1.528

1.618)

1.573,

 

 

 

Ответ:

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

f (x*)

1.8899,

0.045.

 

 

 

Указанные задачи решить любым из рассмотренных методов.

Задачи для самостоятельного решения

2.1.1. Определить минимальное значение функции: f (x) e x 2 cos x

на отрезке[0;1] с погрешностью

0.05.

2.1.2. Вычислить наименьшее значение функции f на отрезке, точку х* определить с точностью до 0,05:

27

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

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

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