ВУЗ:
Составители:
111
12. МЕТОДЫ ОДНОМЕРНОЙ ОПТИМИЗАЦИИ
Задача отыскания экстремумов дифференцируемой функции f сво-
дится к решению уравнения
(
)
0=
′
xf
. Однако лишь в отдельных случа-
ях решение этого уравнения удаётся найти в явном виде. Поэтому в этом
случае прибегают к численным методам экстремального поиска.
Необходимость отдельного рассмотрения численных методов по-
иска экстремума функции одной переменной диктуется следующими
обстоятельствами. Во-первых, эти методы используются во многих
алгоритмах поиска экстремума функций, зависящих от нескольких
переменных. Во-вторых, иногда удаётся, используя те или иные приё-
мы, непосредственно с помощью алгоритмов одномерной оптимиза-
ции получить решение многомерных задач. В-третьих, классы функ-
ций одной переменной служат удобной моделью для теоретического
исследования эффективности методов оптимизации.
Задачу одномерной оптимизации можно сформулировать сле-
дующим образом. Требуется найти экстремум унимодальной функции
одной переменной
(
)
xf
, непрерывной вместе со своей первой произ-
водной на интервале
[
]
bа,
:
(
)
[
]
bаxxf ,,extr ∈→
.
Рассмотрим некоторые из методов одномерного поиска на приме-
рах поиска минимумов функции f(x).
12.1. МЕТОД ЛОКАЛИЗАЦИИ
Разобьём весь интервал
[
]
bа,
на N равных частей. На границах
всех подынтервалов, включая конечные точки интервала
[
]
bа,
, вы-
числяются значения функции
(
)
Nixf
i
,0, =
. Среди полученных зна-
чений
(
)
i
xf
выбирается наилучшее, т.е. то, которое соответствует ти-
пу отыскиваемого экстремума (например, при отыскании минимума
наилучшей будет точка x
2
(рис. 12.1)).
После выбирается новый интервал локализации экстремума, со-
стоящий из двух подынтервалов с наилучшей точкой посередине
(в нашем случае новый интервал будет равен
[
]
31
, xx
).
Применяя к новому интервалу тот же приём разбиения, и вычис-
ляя значение
(
)
xf
на границах полученных подынтервалов, можно
ещё больше сузить интервал локализации экстремума. Описанная про-
цедура повторяется до тех пор, пока неравенство
(
)
(
)
ε
≤−
kk
ab
не
станет истинным, где ε – требуемая точность вычислений, k – номер
итерации (k = 0, 1, 2, …). Тогда за точку экстремума можно принять
среднюю точку интервала
(
)
(
)
[
]
kk
ba ,
:
(
)
(
)
2
kk
ab
x
+
≈
∗
.
Страницы
- « первая
- ‹ предыдущая
- …
- 109
- 110
- 111
- 112
- 113
- …
- следующая ›
- последняя »
