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

Скачать

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

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

а) f(x)=xsinx+2cosx,

[

 

,

 

];

4

3

 

 

 

 

 

 

 

 

 

 

б)

f(x)=

1+x2 +e-2x ,

[0;1];

 

 

 

 

 

 

 

 

x

 

x2

 

 

 

 

 

в)

f(x)=10x lg

 

 

-

 

,

[0,5;1];

 

e

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

г)

f(x)=

1

x

2

 

 

x(ln x 1),

[0,5;1];

3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

д)

f(x)=

 

 

1

 

2x -2x2 ,

[3,5;4,5].

 

 

 

 

 

 

ln 2

 

 

 

 

 

 

 

 

 

 

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

 

 

а)

f(x)=1+x-

5

x

2

+

1

x

4

,

[0;1];

 

 

2

 

 

4

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

б) f(x)=2x2 -(x+1)4 ,

 

 

 

 

[-3;-2];

 

 

в) f(x)=

 

1

 

x

3

-e

x

-2x,

 

 

 

 

[-1,5;1];

 

 

3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

г) f(x)=x-

1

 

 

x

2

+cosx,

 

 

 

[0;1];

 

 

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

д) f(x)=1-6x-3x2 -x6 ,

 

 

 

 

[-1;0];

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5

 

 

 

 

 

 

 

 

е) f(x)=20x-x2 +8x4 ,

 

 

 

 

[3;3,5].

2.1.4. Проверить соотношение между числами Фибоначчи Fn

и величиной

1

 

5

(уравнение Люкаса)

 

 

 

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Fn

 

 

 

n

1

 

 

(

 

 

 

)n

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

для n=0, 1, 2. Установить ошибку аппроксимации

 

 

 

 

 

 

 

n

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Fn

 

 

 

 

 

 

 

.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.1.5. Найти минимум функции

 

 

 

 

 

 

y

3

 

6x

 

 

 

4x2

 

 

 

 

 

 

 

 

 

 

 

 

 

28

на отрезке [0;1] при четырех экспериментах. Эксперименты должны отстоять друг от друга по меньшей мере на 0,05.

Какова длина последнего интервала неопределенности? Какое наибольшее значение при этом достигается?

2.2.Методы полиномиальной интерполяции

2.2.1.Интерполирующий полином и его свойства

Пусть после проведения k испытаний имеет место следующая ситуация:

ak < xk < bk ; f(ak) > f (xk) < f(bk),

которая в силу унимодальности функции f(x) гарантирует, что точка минимума x* будет находиться внутри интервала [ak. bk], т. е.

ak < x* < bk.

Совокупность таких точек (ak, xk, bk) будем называть совокупностью “удачных точек”.

Рассмотрим класс методов, называемых методами полиномиальной интерполяции, основная идея которых заключается в следующем: по информации об m испытаниях {xi, f(xi),

i = 1,2,…,m} строится интерполирующий полином φn(x) степени n ≤ m-1, обладающий следующими свойствами:

• φn(x) – равномерное приближение минимизируемой

функции на интервале [ak, bk];

~

• точка минимума x полинома φn(x) определяется достаточно просто.

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

2.2.2 Квадратичная интерполяция

Метод квадратичной интерполяции часто называют методом Пауэлла. Сущность этого метода заключается в следующем: по трем

29

точкам функция f(x) аппроксимируется квадратичной параболой φ2(x) (интерполяционным многочленом Лагранжа), после чего находится точка минимума полинома φ2(x). Затем положение минимума функции f(x) аппроксимируется положением минимума полинома φ2(x), так как его проще вычислить.

Таким образом, если известны значения функции f(x) в трех различных точках ak, xk, bk, равные соответственно f(ak), f(xk), f(bk), то функция f(x) может быть аппроксимирована квадратичной функцией

φ2(x) =

0 +

1·x1+

2·x2,

(2.2.1)

где 0, 1, 2 определяется из уравнений

 

0

+

1·ak +

2·ak2 = f(ak),

 

0

+

1·xk +

2·xk2

= f(xk),

(2.2.2)

0

+

1·bk +

2·bk2

= f(bk).

 

 

После преобразований уравнений (2.2.2) получаем

 

 

0 = [xkbk(bk-xk)f(ak) + bkak(ak-bk)f(xk) + akxk(xk-ak)f(bk)]/

,

 

1 = [(xk2-bk2)f(ak) + (bk2-ak2)f(xk) + (ak2-xk2)f(bk)]/ ,

 

(2.2.3)

 

2 = [(bk-xk)f(ak) + (ak-bk)f(xk) + (xk-ak)f(bk)]/

,

 

 

где = (ak-xk)(xk-bk)(bk-ak).

 

 

 

 

 

 

 

 

 

 

 

 

Интерполяционный многочлен

 

 

 

 

 

 

 

2 (x)

f (ak )(x

xk )(x

bk )

 

 

f (xk )(x

ak )(x

bk )

 

f (bk )(x

ak )(x

xk )

(2.2.4)

(ak

xk )(ak

bk )

 

(xk - ak )(xk - bk )

(bk ak )(bk

xk )

 

 

 

 

имеет минимум

~

 

 

 

 

 

 

 

 

 

 

 

 

bk]

только

x во внутренней точке интервала [ak,

тогда, когда

2

> 0, т. е. когда для совокупности “удачных точек”

выполняется неравенство

 

 

 

 

 

 

 

 

 

 

 

 

 

f (ak )

 

 

 

 

 

f (xk )

 

 

f (bk )

 

 

0

 

(2.2.5)

 

(ak

xk )(ak

bk )

(xk - ak )(xk - bk )

 

(bk

ak )(bk xk )

 

 

 

 

 

 

В этом случае из условия dφ2(x)/dx = 0 нетрудно получить,

что

30

~

 

1

 

[(xk 2 - bk 2 )f(ak )

(bk 2 - ak

2 )f(xk )

(ak

2 - xk 2 )f(bk )]

 

x

 

 

 

 

 

 

 

 

 

 

 

(2.2.6)

 

 

 

 

 

 

 

 

 

 

 

2

2

 

2[(xk - bk )f(ak ) (bk - ak )f(xk )

(ak - xk )f(bk )]

 

 

После проведения

испытаний

одним

из

рассмотренных в

предыдущем

параграфе

методов

в

точке

~

осуществляется

x

сокращение интервала неопределенности, содержащего точку минимума x*, и определяется новая совокупность “удачных точек”,

при этом возможны четыре случая:

 

 

~

~

 

*

находится в

1) если x

< xn и f( x ) < f(xn), точка минимума x

 

 

 

~

 

 

интервале [ak, xk], и ak = ak, bk = xk, xk = x (рис. 2.2.1а);

~

~

 

*

находится в

2) если x

< xn и f( x ) ≥ f(xn), точка минимума x

 

 

~

~

 

 

интервале [ x , bk], и ak =

x , bk = bk, xk = xk (рис. 2.2.1б);

~

~

 

*

находится в

3) если x

> xk и f( x ) < f(xn), точка минимума x

 

 

 

~

 

 

интервале [xk, bk], и ak = xk, xk = x ,bk = bk (рис. 2.2.1в);

~

~

 

*

находится в

4) если x

> xk и f( x ) ≥ f(xk), точка минимума x

 

 

~

~

 

 

интервале [ak , x ], и ak = ak, xk = xk, bk = x (рис. 2.2.1г);

f

 

f

 

 

0

ak x

xk bk

x

0 ak x xk bk

x

 

~

 

 

~

 

 

а)

 

б)

 

f

 

 

 

f

 

0 ak

xk

x

bk

x 0 ak

xk

x

x

 

 

~

 

 

~

 

 

в)

 

 

г)

 

Рисунок 2.2.1. Определение новой совокупности “удачных точек”

31

будет определить

Следует отметить, что, если точность ε задана слишком

малой, то ak, xk, bk и соответствующие им значения f(ak), f(xk), f(bk)

~

будут очень близки друг к другу, величину x

практически невозможно.

2.2.3. Кубическая интерполяция

Для четырех точек испытаний (m = 4) поиск минимума унимодальной функции f(x) можно вести с помощью метода кубической интерполяции (м. Давидона), который отличается от метода квадратичной интерполяции тем, что в нем в качестве интерполирующего полинома φn(x) используется кубическая парабола

φ3(x) = 0 + 1·x + 2·x2 + 3·x3,

(2.2.7)

что обеспечивает большую точность вычислений.

Функция (2.2.7) имеет один максимум и один минимум, если выполняется неравенство

22 ≥ 3 1 3.

В этом случае точка минимума ~ полинома φ (x) определяется по x 3

формуле

~

+ (bk

a k )

~

,

x = a k

 

где

~ = 1, если

Значение получаем из следующей формулы:

2

 

4

2

12

 

 

 

2

2

1

2

 

1,2 =

 

 

 

 

 

 

 

.

 

 

6

3

 

 

 

 

 

 

 

 

 

 

Далее, аналогично методу квадратичной интерполяции, процедура поиска минимума унимодальной функции f(x) связана с

32

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

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

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