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

UptoLike

ВУЗ: 

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

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

Рубрика: 

10
2
y
1
< y
2
, тогда новый отрезок будет составлять: a
1
=x
1
и b
1
=b
0
. В новом
отрезке также выбираются две точки:
x
1
(1)
= x
2
и x
2
(1)
= a
1
+ k⋅(b
1
- a
1
).
И в первом и во втором случаях рассчитывается лишь одна новая точка
(вторая известна). В новой точке рассчитывается значение функции и вновь
производится сравнение в двух точках, и в зависимости от этого выбирается
новый отрезок. Процедура повторяется до тех пор, пока не будет выполняться
условие (
b
k
- a
k
) ≤ ε , где ε – точность поиска.
3.2.6 Метод Фибоначчи
В методе Фибоначчи требуется, чтобы общее число n вычислений функ-
ции было выбрано заранее, так как точки, в которых производится вычисление,
определяются по формулам:
)(
2
)(
1
kk
kn
kn
k
k
ab
F
F
ax −⋅+=
−
−−
, k=0, ..., n-2 ;
)(
1
)(
2
kk
kn
kn
k
k
ab
F
F
ax −⋅+=
−
−−
, k=0, ..., n-2 ;
где
F
i
= F
i-1
+F
i-2
, i=1, 2, ... F
0
= F
1
= 1 - называется последовательностью чисел
Фибоначчи (1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... , т.е. каждый член
последовательности рассчитывается как сумма двух предыдущих членов).
Алгоритм поиска.
Выбирается начальный отрезок [
a
0
, b
0
] и число вычислений n таким обра-
зом, чтобы
Δ
−
>
00
ab
F
n
, где Δ > 0 – конечная длина отрезка.
Затем рассчитываются координаты двух точек:
)(
00
2
0
)0(
1
ab
F
F
ax
n
n
−⋅+=
−
,
)(
00
1
0
)0(
2
ab
F
F
ax
n
n
−⋅+=
−
и значение функции в этих точках
y
1
=f(x
1
(0)
) и y
2
=f(x
2
(0)
).
В случае
y
1
< y
2
a
1
=a
0
и b
1
=x
2
(0)
, )(
11
1
3
1
)1(
1
ab
F
F
ax
n
n
−⋅+=
−
−
, x
2
(1)
= x
1
(0)
.
В случае
y
1
> y
2
a
1
= x
1
(0)
и b
1
= b
0
, x
1
(1)
= x
2
(0)
, )(
11
1
2
1
)1(
2
ab
F
F
ax
n
n
−⋅+=
−
−
.
Таким образом данная процедура повторяется (n – 2) раза.
При
k = (n – 2) точки x
k
и y
k
совпадают и соответствуют середине отрезка,
поэтому чтобы обеспечить дальнейшее сокращение отрезка, точка последнего
вычисления функции перемещается вправо на величину константы
различимости
δ
>0, которая выбирается заранее существенно меньше заданной
точности. 
    2 y1 < y2 , тогда новый отрезок будет составлять: a1=x1 и b1=b0. В новом
отрезке также выбираются две точки: x1(1) = x2 и x2(1)= a1 + k⋅(b1 - a1).
      И в первом и во втором случаях рассчитывается лишь одна новая точка
(вторая известна). В новой точке рассчитывается значение функции и вновь
производится сравнение в двух точках, и в зависимости от этого выбирается
новый отрезок. Процедура повторяется до тех пор, пока не будет выполняться
условие (bk - ak) ≤ ε , где ε – точность поиска.

      3.2.6 Метод Фибоначчи
     В методе Фибоначчи требуется, чтобы общее число n вычислений функ-
ции было выбрано заранее, так как точки, в которых производится вычисление,
определяются по формулам:
                       F
         x1( k ) = ak + n−k −2 ⋅ (bk − ak ) , k=0, ..., n-2 ;
                        Fn−k
                       F
         x2( k ) = ak + n−k −1 ⋅ (bk − ak ) , k=0, ..., n-2 ;
                        Fn−k
где Fi= Fi-1+Fi-2, i=1, 2, ... F0= F1= 1 - называется последовательностью чисел
    Фибоначчи (1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... , т.е. каждый член
    последовательности рассчитывается как сумма двух предыдущих членов).
      Алгоритм поиска.
      Выбирается начальный отрезок [a0, b0] и число вычислений n таким обра-
                   b − a0
зом, чтобы Fn > 0         , где Δ > 0 – конечная длина отрезка.
                      Δ
      Затем рассчитываются координаты двух точек:
                         F
            x1( 0) = a0 + n−2 ⋅ (b0 − a0 ) ,
                          Fn
                         F
            x2( 0) = a0 + n−1 ⋅ (b0 − a0 )
                          Fn
и значение функции в этих точках y1=f(x1(0)) и y2=f(x2(0)).
          В случае y1 < y2
                                                     F
         a1=a0 и b1=x2(0) ,           x1(1) = a1 + n−3 ⋅ (b1 − a1 ) ,      x2(1)= x1(0) .
                                                     Fn−1
          В случае y1 > y2
                                                                      F
         a1= x1(0) и b1= b0 ,         x1(1)= x2(0) ,      x2(1) = a1 + n−2 ⋅ (b1 − a1 ) .
                                                                      Fn−1
      Таким образом данная процедура повторяется (n – 2) раза.
      При k = (n – 2) точки xk и yk совпадают и соответствуют середине отрезка,
поэтому чтобы обеспечить дальнейшее сокращение отрезка, точка последнего
вычисления функции перемещается вправо на величину константы
различимости δ >0, которая выбирается заранее существенно меньше заданной
точности.
10

Страницы