Методы оптимизации. Азарнова Т.В - 25 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

27
промежутка. Если же ε>
+ )1(2 k
L ,
то положить
1
+
=
k
k
и перейти к
шагу 3.
Следует заметить, что для данного метода на каждой итерации,
начиная со второй , вычисляется значение функции только в двух точках , так
как средняя точка нового промежутка всегда совпадает с одной из точек
рассматриваемых на предыдущей итерации. Таким образом, для данного
метода
2
2
1
)(
N
NR = , где
N
- количество вычислений функции. Нумерация
промежутков неопределенности подчеркивает тот факт, что на каждой
итерации вычисляется два значения функции.
Пример 2. Найти минимум функции xxxf 122)(
2
−= методом
деления промежутка пополам .
Решение. В качестве начального промежутка неопределенности
рассмотрим промежуток ]10,0[],[
000
=
=
baL и положим
1
=
ε
.
1. Положим
0
=
k
.
2. Вычислим:
(
)
10,10,5
2
100
000
−===
+
=
cc
xfLx .
3. Вычислим ,5,2
4
10
0
0
=+= y 5,7
4
10
10
0
=−= z , 5,17)(
0
−
=
yf ,
5,22)(
0
=
zf .
4.
(
c
xfyf
00
)( < , поэтому положим 5,0
0101
====
c
xbaa , 5,2
01
== yx
c
.
5. Получим 15],5,0[
22
=
>
=
=
ε
LL . Положим
1
=
k
и перейдем к шагу 3.
6. Вычислим ,25,1
4
5
0
1
=+= y 75,3
4
5
5
1
=−= z ,
875,11)(
1
−
=
yf
,
875,16)(
1
−
=
zf
.
7.
(
)
c
xfyf
11
)( >
, поэтому перейдем к шагу 5.
8.
(
)
c
xfzf
11
)( >
, поэтому положим
25,1
12
=
=
ya
,
75,3
12
=
=
zb
,
5,2
12
==
cc
xx
.
9. Получим
ε
>
=
=
5,2],75,3;25,1[
44
LL . Положим
2
=
k
и перейдем к шагу
3.
После третьего прохода алгоритма, получим
162,0],43,3;81,2[
88
=
<
=
=
ε
LL . Достигнута требуемая точность, поэтому
алгоритм заканчивает свою работу с
8
=
N
. Характеристика относительного
сокращения промежутка
16
1
)( =NR
. В качестве решения можно взять
среднюю точку последнего промежутка
125,3
4
*
==
c
xx
.
Метод золотого сечения
Метод золотого сечения относится к последовательным методам
нулевого порядка. В методе золотого сечения две внутренние точки , которые
используются для сокращения промежутка неопределенности , выбираются 
                                          27
промежутка.           Если же   L2( k +1) >ε , то положить k =k +1 и перейти к
шагу 3.
        Следует заметить, что для данного метода на каждой итерации,
начиная со второй, вычисляется значение функции только в двух точках, так
как средняя точка нового промежутка всегда совпадает с одной из точек
рассматриваемых на предыдущей итерации. Таким образом, для данного
                      1
метода R ( N ) = N , где N - количество вычислений функции. Нумерация
                     2 2
промежутков неопределенности подчеркивает тот факт, что на каждой
итерации вычисляется два значения функции.
        Пример 2. Найти минимум функции             f ( x) =2 x 2 −12 x методом
деления промежутка пополам.
        Решение. В качестве         начального промежутка неопределенности
рассмотрим промежуток L0 =[a 0 , b0 ] =[0,10] и положим ε =1.
1. Положим k =0 .
2. Вычислим: x 0c =
                        0 +10
                           2
                                                 ( )
                              =5, L0 =10, f x 0c =−10 .
                                 10              10
3. Вычислим              y 0 =0 + =2,5, z 0 =10 − =7,5 ,            f ( y 0 ) =−17,5 ,
                                  4               4
   f ( z 0 ) =22,5 .
                ( )
4. f ( y 0 ) < f x 0c , поэтому положим a1 =a 0 =0, b1 =x 0c =5 , x1c =y 0 =2,5 .
5. Получим L2 =[0,5], L2 =5 >ε =1. Положим k =1 и перейдем к шагу 3.
                                  5              5
6. Вычислим               y1 =0 + =1,25, z1 =5 − =3,75 ,             f ( y1 ) =−11,875 ,
                                  4              4
   f ( z1 ) =−16,875 .
                 ( )
7. f ( y1 ) > f x1c , поэтому перейдем к шагу 5.
8.   f ( z ) > f (x ),
        1
                  c
                  1       поэтому    положим       a 2 =y1 =1,25 ,      b2 =z1 =3,75 ,
   x 2c =x1c =2,5 .
9. Получим L 4 =[1,25;3,75], L4 =2,5 >ε . Положим k =2 и перейдем к шагу
   3.
После            третьего      прохода         алгоритма,        получим
L8 =[2,81;3,43], L8 =0,62 <ε =1 . Достигнута требуемая точность, поэтому
алгоритм заканчивает свою работу с N =8 . Характеристика относительного
                                   1
сокращения промежутка R ( N ) = . В качестве решения можно взять
                                  16
среднюю точку последнего промежутка x * =x 4c =3,125 .
                             Метод золотого сечения
        Метод золотого сечения относится к последовательным методам
нулевого порядка. В методе золотого сечения две внутренние точки, которые
используются для сокращения промежутка неопределенности, выбираются

Страницы