Методы безусловной одномерной оптимизации. Шипилов С.А. - 9 стр.

UptoLike

ВУЗ: 

НФИ КемГУ | Новокузнецк

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

Рубрика: 

9
a x
1
x
2
a
x
1
x
1
x
2
b
b
2
ba
+
x
2
Рисунок 2 – Метод золотого сечения
В этом суженном промежутке [a
1
, b
1
] вновь рассчитываются две точки
x
1
(1)
и x
2
(1)
,
симметричные относительно его середины, и значение функции в
этих точках. Процедура будет повторяться до тех пор, пока не будет выпол-
няться условие Δ
k
= b
k
-a
k
≤ ε, где ε – точность поиска, и тогда в качестве точки
локального минимума можно приближенно принять середину отрезка
2
*
kk
ba
x
+
≈ .
3.2.5 Метод золотого сечения
Термин “золотое сечение” ввел Леонардо да Винчи. Точка x
1
является зо-
лотым сечением отрезка [a, b], если отношение длины b-a всего отрезка к длине
b-x
1
большей части равно отношению длины большей части к длине x
1
–a
меньшей части (рисунок 2), т.е. x
1
– золотое сечение, если справедливо соотно-
шение
ax
xb
xb
ab
−
−
=
−
−
1
1
1
. Аналогично, точка x
2
симметричная точке x
1
относитель-
но середины отрезка [a, b], является вторым золотым сечением этого отрезка.
Отметим свойство золотого сечения: точка x
1
одновременно является зо-
лотым сечением отрезка [a, x
2
] , а другая точка x
2
- золотым сечением отрезка
[x
1
, b].
Суть метода золотого сечения заключается в следующем. Сначала на ис-
ходном отрезке [a
0
, b
0
] находятся точки x
1
и x
2
по следующим формулам:
x
1
= a
0
+(1-k)⋅(b
0
-a
0
) ;
x
2
= a
0
+k⋅(b
0
-a
0
) ;
где k =
2
15 −
= 0,618 – коэффициент сжатия.
Затем вычисляются значения функции в точках
x
1
и x
2
, т.е. y
1
=f(x
1
) и
y
2
=f(x
2
). При этом возможны два случая:
1
y
1
< y
2
, в этом случае новый отрезок будет равен: a
1
=a
0
и b
1
=x
2
. В этом
отрезке вновь выбираются две точки:
x
1
(1)
= a
1
+ (1- k)⋅(b
1
-a
1
) и x
2
(1)
=x
1
. 
      В этом суженном промежутке [a1, b1] вновь рассчитываются две точки
x1(1)
    и x2(1), симметричные относительно его середины, и значение функции в
этих точках. Процедура будет повторяться до тех пор, пока не будет выпол-
няться условие Δk = bk-ak ≤ ε, где ε – точность поиска, и тогда в качестве точки
локального минимума можно приближенно принять середину отрезка
     a + bk
x* ≈ k        .
       2
        3.2.5 Метод золотого сечения
      Термин “золотое сечение” ввел Леонардо да Винчи. Точка x1 является зо-
лотым сечением отрезка [a, b], если отношение длины b-a всего отрезка к длине
b-x1 большей части равно отношению длины большей части к длине x1–a
меньшей части (рисунок 2), т.е. x1 – золотое сечение, если справедливо соотно-
       b − a b − x1
шение        =       . Аналогично, точка x2 симметричная точке x1 относитель-
       b − x1 x1 − a
но середины отрезка [a, b], является вторым золотым сечением этого отрезка.
                                      a+b
                                       2

                  a              x1         x2              b


                  a              x1         x2


                                 x1         x2              b

                      Рисунок 2 – Метод золотого сечения

        Отметим свойство золотого сечения: точка x1 одновременно является зо-
лотым сечением отрезка [a, x2] , а другая точка x2 - золотым сечением отрезка
[x1, b].
        Суть метода золотого сечения заключается в следующем. Сначала на ис-
ходном отрезке [a0, b0] находятся точки x1 и x2 по следующим формулам:
            x1= a0 +(1-k)⋅(b0-a0) ;
            x2= a0 +k⋅(b0-a0) ;
                  5 −1
        где k =         = 0,618 – коэффициент сжатия.
                   2
        Затем вычисляются значения функции в точках x1 и x2 , т.е. y1=f(x1) и
y2=f(x2). При этом возможны два случая:
      1 y1 < y2 , в этом случае новый отрезок будет равен: a1=a0 и b1=x2. В этом
отрезке вновь выбираются две точки: x1(1) = a1+ (1- k)⋅(b1-a1) и x2(1)=x1.
                                                                              9

Страницы