ВУЗ:
Составители:
Рубрика:
9
Найденное нами приближенное значение точки минимума
x отличается от истинного значения на
величину
ε ≤
1
2
(1.6923 − 1.53846) ≈ 0.077
Приближенное значение функции f(x) в точке минимума есть
f(1.61538) = 1.89003 ≈ f
min
Применение описанных методов накладывает единственное требование на исследуемую функцию:
она должна быть унимодальной.
Следовательно, указанные методы можно использовать для анализа, как непрерывных, так и раз-
рывных функций, а также в случаях, когда переменные принимают значения из дискретного мно-
жества. Они принимают в расчет только отношение порядка на множестве значений функции и
не учитывают величин разности между значениями функции. Поэтому естественно рассмотреть
такие методы поиска, которые позволяют учесть относительные изменения значений функции. В
некоторых случаях такие методы оказываются более эффективными. Выигрыш эффективности, од-
нако, достигается введением дополнительного требования, согласно которому исследуемые функции
должны быть достаточно гладкими.
Основная идея таких методов состоит в возможности аппроксимации гладкой функции полиномом
и последующего его использования для оценивания координаты точки оптимума. Необходимыми
условиями являются требования унимодальности и непрерывности исследуемой функции. Соглас-
но теореме Вейерштрасса об аппроксимации, если функция непрерывна в некотором интервале, то
ее с любой степенью точности можно аппроксимировать полиномом достаточно высокого порядка.
Координату точки оптимума функции можно оценивать, находя координату точки оптимума по-
линома. Качество оценки координаты точки оптимума при этом можно повысить, либо используя
полином более высокого порядка, либо уменьшая интервалы аппроксимации. Второй способ более
предпочтителен, так как построение аппроксимирующего полинома порядка выше третьего доста-
точно сложно.
Метод квадратичной аппроксимации.
Метод квадратичной аппроксимации дает существенный эффект в случае, если минимизируемая
функция хорошо аппроксимируется на интервалах параболами.
Пусть известны точки
x
1
,x
2
,x
3
(x
1
<x
2
<x
3
)
и значение функции в этих точках: f
i
= f(x
i
),i=1, 2, 3
Используя эту информацию, можно аппроксимировать нашу функцию на отрезке [x
1
,x
2
] параболой
g(x)=ax
2
+ bx + c
Параметры этой параболы можно найти, потребовав выполнения условия
f(x
i
)=g(x
i
),i=1, 2, 3
a =
1
x
3
− x
2
(
f(x
3
) − f(x
1
)
x
3
− x
1
−
f(x
2
− f(x
1
))
x
2
− x
1
);
b =
x
3
+ x
1
x
3
− x
2
(
f(x
2
)f(x
1
)
x
2
− x
1
) −
x
2
+ x
1
x
3
− x
2
f(x
3
) − f(x
1
)
x
3
− x
1
удобно использовать также полином в форме
q = a
0
(x − x
1
)(x − x
2
)+b
0
(x − x
1
)+c
0
;
b
0
=
f(x
2
) − f(x
1
)
x
2
− x
1
; c
0
= f(x
1
)
Если точность квадратичной аппроксимации на отрезке достаточна высока, то координаты точки
9
Найденное нами приближенное значение точки минимума x отличается от истинного значения на
величину
1
ε ≤ (1.6923 − 1.53846) ≈ 0.077
2
Приближенное значение функции f (x) в точке минимума есть
f (1.61538) = 1.89003 ≈ fmin
Применение описанных методов накладывает единственное требование на исследуемую функцию:
она должна быть унимодальной.
Следовательно, указанные методы можно использовать для анализа, как непрерывных, так и раз-
рывных функций, а также в случаях, когда переменные принимают значения из дискретного мно-
жества. Они принимают в расчет только отношение порядка на множестве значений функции и
не учитывают величин разности между значениями функции. Поэтому естественно рассмотреть
такие методы поиска, которые позволяют учесть относительные изменения значений функции. В
некоторых случаях такие методы оказываются более эффективными. Выигрыш эффективности, од-
нако, достигается введением дополнительного требования, согласно которому исследуемые функции
должны быть достаточно гладкими.
Основная идея таких методов состоит в возможности аппроксимации гладкой функции полиномом
и последующего его использования для оценивания координаты точки оптимума. Необходимыми
условиями являются требования унимодальности и непрерывности исследуемой функции. Соглас-
но теореме Вейерштрасса об аппроксимации, если функция непрерывна в некотором интервале, то
ее с любой степенью точности можно аппроксимировать полиномом достаточно высокого порядка.
Координату точки оптимума функции можно оценивать, находя координату точки оптимума по-
линома. Качество оценки координаты точки оптимума при этом можно повысить, либо используя
полином более высокого порядка, либо уменьшая интервалы аппроксимации. Второй способ более
предпочтителен, так как построение аппроксимирующего полинома порядка выше третьего доста-
точно сложно.
Метод квадратичной аппроксимации.
Метод квадратичной аппроксимации дает существенный эффект в случае, если минимизируемая
функция хорошо аппроксимируется на интервалах параболами.
Пусть известны точки
x1 , x2 , x3 (x1 < x2 < x3 )
и значение функции в этих точках: fi = f (xi ), i = 1, 2, 3
Используя эту информацию, можно аппроксимировать нашу функцию на отрезке [x1 , x2 ] параболой
g(x) = ax2 + bx + c
Параметры этой параболы можно найти, потребовав выполнения условия
f (xi ) = g(xi ), i = 1, 2, 3
1 f (x3 ) − f (x1 ) f (x2 − f (x1 ))
a= ( − );
x3 − x2 x3 − x1 x2 − x1
x3 + x1 f (x2 )f (x1 ) x2 + x1 f (x3 ) − f (x1 )
b= ( )−
x3 − x2 x2 − x1 x3 − x2 x3 − x1
удобно использовать также полином в форме
q = a0 (x − x1 )(x − x2 ) + b0 (x − x1 ) + c0 ;
f (x2 ) − f (x1 )
b0 = ; c0 = f (x1 )
x2 − x1
Если точность квадратичной аппроксимации на отрезке достаточна высока, то координаты точки
