ВУЗ:
Составители:
Рубрика:
4
0
Рис. 1: Унимодальные функции
0
bx* x
2
a x
1
0
bx* x
2
a x
1
Теорема: Пусть функция f(x) унимодальна на отрезке [a, b], а ее минимум достигается в точке
x
∗
. Для любых точек x
1
и x
2
этого отрезка и таких, что a<x
1
<x
2
<bверно следующее: 1. если
f(x
1
) >f(x
2
), то точка минимума x
∗
∈ [x
1
,b) (рис. 2) 2. если f(x
1
) <f(x
2
), то точка минимума
x
∗
∈ (a, x
2
] (рис. 3). Доказательство: Рассмотрим случай, когда f(x
1
) >f(x
2
). Допустим противное,
т. е. x
∗
∈ (a, x
1
]. Тогда, так как x
∗
-точка минимума, то по определению f(x
∗
) ≤ f(x) для x ∈ [a, b]
Получаем двойное неравенство f (x
∗
) ≤ f(x
1
) >f(x
2
) при x
∗
<x
1
<x
2
, как однако это невозмож-
но, так унимодальная функция монотонна по обе стороны от точки x
∗
. Аналогичные соображения
действуют в случае, когда f(x
1
) <f(x
2
). Примечание: Если f(x
1
)=f(x
2
), то можно исключать оба
крайних интервала, при этом точка минимума будет принадлежать отрезку [x
1
,x
2
]. Таким образом,
организовав специальным способом выбор точек на отрезке, можно построить процедуру последо-
вательного исключения интервалов отрезка. Процедура завершается, когда оставшиийся отрезок не
достигнет достаточно малых размеров. При этом не требуется, чтобы исследуемая функция была
дифференцируемой и даже нерпрерывной, более того она может быть задана таблично. Рассмот-
рим наиболее простые методы поиска минимума (максимума) унимодальной функции, с которыми
должен быть знаком каждый студент, прослушавший курс по экстремальным задачам.
Метод деления отрезка пополам.
Рассматриваем задачу отыскания точки минимума x
∗
унимодаль-
ной функции f(x), определенной на отрезке. Возьмем две точки. x
1
=
a+b−δ
2
; x
2
=
a+b+δ
2
,гдеδ-
достаточно малая положительная постоянная. При этом точки x
1
,x
2
делят отрезок почти пополам-
отсюда название метода. Вычисляем и сравниваем значения f(x
1
) и f(x
2
) Если f(x
1
) >f(x
2
)?nj
согласно доказанной теореме новый отрезок поиска точки x
∗
будет [x
1
,b]. Границы нового отрезка
обозначим через a
1
и b
1
,т.е.a
1
= x
1
,b
1
= b.Еслиf(x
1
) <f(x
2
),тоa
1
= a, b
1
= x
2
. При этом длина
нового отрезка будет ∆
1
= b
1
−a
1
=
b−a
2
+(1−
1
2
)δ На новом отрезке повторяем процедуру выбора
точек x
1
и x
2
(мы сохраняем их обозначения ) и сравнения значений функции в этих точках. На k-ой
итерации будем иметь: x
1
=
a
k−1
+b
k−1
−δ
2
; x
2
=
a
k−1
+b
k−1
+δ
2
;∆
k
= b
k
−a
k
=
b−a
2
k
+(1−
1
2
k
δ)=
b−a−δ
2
k
+δ
Если приводим k шагов процедуры, то количество рассматриваемых точек и соответственно коли-
чество вычисленных значений функции равно: n =2k. Если полученный отрезок [a
k
,b
k
]достаточно
мал (см. ниже), то принять середину отрезка за решение задачи x
∗
≈ x
∗
n
=
a
k
+b
k
2
. при этом погреш-
ность составляет |x
∗
−x
∗
n
|≤
1
2
(b
k
−a
k
) ≤
b−a
2
k+1
+
δ
2
. В случаях, когда вычисление значений функции
не вызывает затруднений, итерации следует проводить до тех пор, пока
1
2
(b
k
− a
k
) <εили
b−a−δ
2
k+1
,
где ε- требуемая заданная точность вычисления. Тогда можно получить оценку для числа необхо-
димых итерации: k>log
2
(
b−a−δ
ε−
δ
2
) − 1, число точек вычисления значений функции равно N =2k.
4
0
Рис. 1: Унимодальные функции
0 0
a x1 x* x2 b a x1 x* x2 b
Теорема: Пусть функция f (x) унимодальна на отрезке [a, b], а ее минимум достигается в точке
x∗ . Для любых точек x1 и x2 этого отрезка и таких, что a < x1 < x2 < b верно следующее: 1. если
f (x1 ) > f (x2 ), то точка минимума x∗ ∈ [x1 , b) (рис. 2) 2. если f (x1 ) < f (x2 ), то точка минимума
x∗ ∈ (a, x2 ] (рис. 3). Доказательство: Рассмотрим случай, когда f (x1 ) > f (x2 ). Допустим противное,
т. е. x∗ ∈ (a, x1 ]. Тогда, так как x∗ -точка минимума, то по определению f (x∗ ) ≤ f (x) для x ∈ [a, b]
Получаем двойное неравенство f (x∗ ) ≤ f (x1 ) > f (x2 ) при x∗ < x1 < x2 , как однако это невозмож-
но, так унимодальная функция монотонна по обе стороны от точки x∗ . Аналогичные соображения
действуют в случае, когда f (x1 ) < f (x2 ). Примечание: Если f (x1 ) = f (x2 ), то можно исключать оба
крайних интервала, при этом точка минимума будет принадлежать отрезку [x1 , x2 ]. Таким образом,
организовав специальным способом выбор точек на отрезке, можно построить процедуру последо-
вательного исключения интервалов отрезка. Процедура завершается, когда оставшиийся отрезок не
достигнет достаточно малых размеров. При этом не требуется, чтобы исследуемая функция была
дифференцируемой и даже нерпрерывной, более того она может быть задана таблично. Рассмот-
рим наиболее простые методы поиска минимума (максимума) унимодальной функции, с которыми
должен быть знаком каждый студент, прослушавший курс по экстремальным задачам.
Метод деления отрезка пополам. Рассматриваем задачу отыскания точки минимума x∗ унимодаль-
ной функции f (x), определенной на отрезке. Возьмем две точки. x1 = a+b−δ 2 ; x2 = a+b+δ
2 , где δ-
достаточно малая положительная постоянная. При этом точки x1 , x2 делят отрезок почти пополам-
отсюда название метода. Вычисляем и сравниваем значения f (x1 ) и f (x2 ) Если f (x1 ) > f (x2 )?nj
согласно доказанной теореме новый отрезок поиска точки x∗ будет [x1 , b]. Границы нового отрезка
обозначим через a1 и b1 , т. е. a1 = x1 , b1 = b. Если f (x1 ) < f (x2 ), то a1 = a, b1 = x2 . При этом длина
нового отрезка будет ∆1 = b1 − a1 = b−a 1
2 + (1 − 2 )δ На новом отрезке повторяем процедуру выбора
точек x1 и x2 (мы сохраняем их обозначения ) и сравнения значений функции в этих точках. На k-ой
итерации будем иметь: x1 = ak−1 +b2k−1 −δ ; x2 = ak−1 +b2k−1 +δ ; ∆k = bk −ak = b−a 2k
+(1− 21k δ) = b−a−δ
2k
+δ
Если приводим k шагов процедуры, то количество рассматриваемых точек и соответственно коли-
чество вычисленных значений функции равно: n = 2k. Если полученный отрезок [ak , bk ]достаточно
мал (см. ниже), то принять середину отрезка за решение задачи x∗ ≈ x∗n = ak +b 2
k
. при этом погреш-
∗ ∗ 1 b−a δ
ность составляет |x − xn | ≤ 2 (bk − ak ) ≤ 2k+1 + 2 . В случаях, когда вычисление значений функции
не вызывает затруднений, итерации следует проводить до тех пор, пока 12 (bk − ak ) < ε или b−a−δ 2k+1
,
где ε- требуемая заданная точность вычисления. Тогда можно получить оценку для числа необхо-
димых итерации: k > log2 ( b−a−δε− δ
) − 1, число точек вычисления значений функции равно N = 2k.
2
Страницы
- « первая
- ‹ предыдущая
- …
- 2
- 3
- 4
- 5
- 6
- …
- следующая ›
- последняя »
