Одномерная минимизация. Горячев Л.В. - 6 стр.

UptoLike

ВУЗ: 

ДВФУ | Владивосток

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

Рубрика: 

6
x
2
по (**), переход к 1.
Методы половинного и золотого сечения относятся к классу так называемых симметричных мето-
дов. Дело в том, что имеющиеся на каждом шаге две точки отрезка x
1
и x
2
симметрично располо-
жены относительно центра этого отрезка. Благодаря этому свойству всякий симметричный метод
полностью определяется заданием отрезка [a, b] и правилом выбора первой точки. Тогда другая
точка x
2
(x
1
) находится по правилу общему для всех симметричных методов:
x
2
= a + b − x
1
, если x
1
известна,
x
1
= a + b − x
2
, если x
2
известна.
Несмотря на свою простоту и изящность, все симметричные методы обладают тем недостатком, что
погрешность, допущенная в задании точки x
1
на первом шаге, приводит к быстрому накоплению
погрешностей на дальнейших шагах и уже при небольших n результаты будут сильно отличаться
от тех, которые могли бы получиться при точной реализации симметричного метода с точными
исходными данными.
Впервые интерес к золотой пропорции возник еще в античной науке (Пифагор, Платон, Евклид).
Античные скульптуры и архитекторы широко используют её в своих художественных произведени-
ях. Об этом и других применениях золотой пропорции можно познакомится в книге А. П. Стахова
(Коды золотой пропорции. -М, Радио и связь, 1984).
Для иллюстрации сказанного приведем простой пример: определить минимальное значение функ-
ции e
−x
− 2cosx на отрезке [0, 1]. Точку x
∗
найти с абсолютной погрешностью ε<0.05.
1. Имеем отрезок [a, b]=[0, 1]. Вычисляем на нем по правилам (*) и (**) точки x
1
и x
2
: x
1
=
0.382,x
2
=0.618.
2. Вычисляем f(x
1
)иf(x
2
):f(x
1
)=−1.1733; f(x
2
)=−1.0910.
3. Так как f(x
2
) >f(x
1
), то имеем новый отрезок поиска: [a, b]=[0, 0.618]. Проверяем на остановку:
h =
1
2
(0.618 − 0) = 0.309 > 0.05.
4. На новом отрезке нам уже известна одна точка золотого сечения x
2
:= x
1
=0.382. Находим
x
1
=0+0.382 · 0.616 = 0.236.
5. Вычисляем f(x
1
),f(x
2
) - нам известно: f(x
1
)=−1.155,f(x
2
)=−1.1733.
6. Сравнивая значения f(x
1
)иf(x
2
), имеем, что f(x
1
) >f(x
2
), следовательно приходим к новому
отрезку [a, b]=[0.236, 0.618]. На нем имеет точку золотого сечения x
2
, h =(0.618 − 0.236)/2=
0.191 > 0.05.
7. Находим новые точки на отрезке [0.238, 0.618]:
x
1
:= x
2
=0.382;
x
2
=0.236 + 0.618 · (0.618 − 0.236) = 0.472.
8. Вычисляем f(x
2
)=−1.1575; f (x
1
)=−1.1733 - нам известно, так как f(x
2
) >f(x
1
), заключаем,
что новый отрезок поиска [a, b]=[0.236, 0.472].
9. На новом отрезке
x
2
:= x
1
=0.382;
x
1
=0.236 + 0.318 · (0.472 − 0.236) = 0.326.
10. Находим f (x
1
)=−1.1728; f (x
2
)=−1.1733. Сравниваем: f(x
1
) >f(x
2
). Заключаем, что новый
отрезок [a, b]=[0.326, 0.472]; h =0.07 > 0.05.
11. На новом отрезке
x
1
:= x
2
=0.382;
x
2
=0.326 + 0.618 · (0.472 − 0.326) = 0.416.
12. Находим f(x
2
)=−1.1696; f (x
1
)=−1.1733.Таккакf(x
1
) <f(x
2
), новый отрезок поис-
ка [a, b]=[0.326, 0.416], h =
1
2
(0.416 − 0.326) = 0.045 < 0.05. Вычисления закончены x
∗
≈
1
2
(0.416 + 0.326) = 0.372,f
min
≈ f(0.372) = −1.1739.
МЕТОД ФИБОНАЧЧИ
В тех случаях, когда вычисление значений функции в точках отрезка затруднительно (например,
в условиях промышленного эксперимента) естественно стремление ограничиться числом необходи-
мых измерений, не теряя в точности определения точки минимума. Поэтому в таких ситуациях
применять метод, который бы при заданном n и мел бы наибольшую точность. К числу методов
оптимальных по точности относится и метод Фибоначчи.
Числа Фибоначчи определяются соотношением:
F
n+2
= F
n+1
+ F
n
; n =0, 1, 2,...; F
0
=0,F
1
=1.
6

x2 по (**), переход к 1.
Методы половинного и золотого сечения относятся к классу так называемых симметричных мето-
дов. Дело в том, что имеющиеся на каждом шаге две точки отрезка x1 и x2 симметрично располо-
жены относительно центра этого отрезка. Благодаря этому свойству всякий симметричный метод
полностью определяется заданием отрезка [a, b] и правилом выбора первой точки. Тогда другая
точка x2 (x1 ) находится по правилу общему для всех симметричных методов:
x2 = a + b − x1 , если x1 известна,
x1 = a + b − x2 , если x2 известна.
Несмотря на свою простоту и изящность, все симметричные методы обладают тем недостатком, что
погрешность, допущенная в задании точки x1 на первом шаге, приводит к быстрому накоплению
погрешностей на дальнейших шагах и уже при небольших n результаты будут сильно отличаться
от тех, которые могли бы получиться при точной реализации симметричного метода с точными
исходными данными.
Впервые интерес к золотой пропорции возник еще в античной науке (Пифагор, Платон, Евклид).
Античные скульптуры и архитекторы широко используют её в своих художественных произведени-
ях. Об этом и других применениях золотой пропорции можно познакомится в книге А. П. Стахова
(Коды золотой пропорции. -М, Радио и связь, 1984).
Для иллюстрации сказанного приведем простой пример: определить минимальное значение функ-
ции e−x − 2 cos x на отрезке [0, 1]. Точку x∗ найти с абсолютной погрешностью ε < 0.05.
1. Имеем отрезок [a, b] = [0, 1]. Вычисляем на нем по правилам (*) и (**) точки x1 и x2 : x1 =
0.382, x2 = 0.618.
2. Вычисляем f (x1 )иf (x2 ) : f (x1 ) = −1.1733; f (x2 ) = −1.0910.
3. Так как f (x2 ) > f (x1 ), то имеем новый отрезок поиска: [a, b] = [0, 0.618]. Проверяем на остановку:
h = 12 (0.618 − 0) = 0.309 > 0.05.
4. На новом отрезке нам уже известна одна точка золотого сечения x2 := x1 = 0.382. Находим
x1 = 0 + 0.382 · 0.616 = 0.236.
5. Вычисляем f (x1 ), f (x2 ) - нам известно: f (x1 ) = −1.155, f (x2 ) = −1.1733.
6. Сравнивая значения f (x1 )иf (x2 ), имеем, что f (x1 ) > f (x2 ), следовательно приходим к новому
отрезку [a, b] = [0.236, 0.618]. На нем имеет точку золотого сечения x2 , h = (0.618 − 0.236)/2 =
0.191 > 0.05.
7. Находим новые точки на отрезке [0.238, 0.618]:
x1 := x2 = 0.382;
x2 = 0.236 + 0.618 · (0.618 − 0.236) = 0.472.
8. Вычисляем f (x2 ) = −1.1575; f (x1 ) = −1.1733 - нам известно, так как f (x2 ) > f (x1 ), заключаем,
что новый отрезок поиска [a, b] = [0.236, 0.472].
9. На новом отрезке
x2 := x1 = 0.382;
x1 = 0.236 + 0.318 · (0.472 − 0.236) = 0.326.
10. Находим f (x1 ) = −1.1728; f (x2 ) = −1.1733. Сравниваем: f (x1 ) > f (x2 ). Заключаем, что новый
отрезок [a, b] = [0.326, 0.472]; h = 0.07 > 0.05.
11. На новом отрезке
x1 := x2 = 0.382;
x2 = 0.326 + 0.618 · (0.472 − 0.326) = 0.416.
12. Находим f (x2 ) = −1.1696; f (x1 ) = −1.1733. Так как f (x1 ) < f (x2 ), новый отрезок поис-
ка [a, b] = [0.326, 0.416], h = 12 (0.416 − 0.326) = 0.045 < 0.05. Вычисления закончены x∗ ≈
1
2 (0.416 + 0.326) = 0.372, fmin ≈ f (0.372) = −1.1739.
МЕТОД ФИБОНАЧЧИ
В тех случаях, когда вычисление значений функции в точках отрезка затруднительно (например,
в условиях промышленного эксперимента) естественно стремление ограничиться числом необходи-
мых измерений, не теряя в точности определения точки минимума. Поэтому в таких ситуациях
применять метод, который бы при заданном n и мел бы наибольшую точность. К числу методов
оптимальных по точности относится и метод Фибоначчи.
Числа Фибоначчи определяются соотношением:
Fn+2 = Fn+1 + Fn ; n = 0, 1, 2, . . . ; F0 = 0, F1 = 1.

Страницы