Сравнение методов исключения интервалов

Для сравнения эффективности рассмотренных методов обозначим длину исходного интервала , а длину интервала, полученного в результате вычислений функции, через . В качестве показателя эффективности используем характеристику относительного уменьшения длины интервала . Напомним, что для метода половинного деления , а для метода золотого сечения . Результаты расчетов для различных количеств вычислений функции приведены в таблице 2.2.

Таблица 2.2

Метод поиска	Количество вычислений значений функции
Половинное деление	0,5	0,177	0,031	0,006	0,0009
Золотое сечение	0,618	0,146	0,013	0,001	0,0001
Равномерный поиск	0,667	0,333	0,282	0,125	0,095

Видно, что метод золотого сечения дает наибольшее относительное уменьшение исходного интервала при одном и том же количестве вычислений функции.

Полиномиальная аппроксимация

Применение рассмотренных методов исключения интервалов накладывает на функцию единственное требование – она должна быть унимодальной. Рассмотренные методы можно использовать для анализа как непрерывных, так и разрывных и дискретных функций. Их логическая структура основана на сравнении значений функции в двух пробных точках. При этом не учитывается величина разности между значениями функции.

Рассмотрим подход, который позволяет повысить эффективность определения экстремума за счет учета величины относительных изменений. Однако при этом на функцию накладываются дополнительные ограничения – она должна быть гладкой.

Основная идея состоит в возможности аппроксимации гладкой функции полиномами и использовании аппроксимирующего полинома для оценивания координаты точки экстремума.

Согласно теореме Вейерштрасса об аппроксимации, если функция непрерывна на некотором интервале, то ее с любой степенью точности можно аппроксимировать полиномом достаточно высокого порядка. Если для унимодальной функции найти такой полином, то его можно использовать для оценки точки экстремума функции.

Известно, что качество оценки точки экстремума можно повысить двумя путями:

• Повышением порядка полинома;

• Уменьшением интервала аппроксимации.

С точки зрения технологии второй метод является предпочтительным.

Простейшим вариантом полиномиальной аппроксимации является квадратичная аппроксимация, так как квадратичность хорошо сочетается с унимодальностью

Пусть заданы точки и соответствующие этим точкам значения функции . Известно, что можно выбрать постоянные коэффициенты таким образом, что значения квадратичной функции

(2.3)

совпадут со значениями функции в трех указанных точках.

Примем, что в точке выполняется . Тогда

. Отсюда .

Коэффициент найдем из условия .

. Отсюда .

Наконец, из условия найдем . Имеем

.

Решив последнее уравнение относительно , получим

.

Если качество аппроксимации оказывается достаточно высоким, то оценку точки экстремума функции можно получить путем исследования стационарных точек полученного аппроксимирующего полинома.

Вычислим производную (2.3) и приравняем ее к нулю

.

Отсюда .

Пример. Найти оценку экстремальной точки для функции на интервале . Возьмем точки . Тогда .

Найдем значения коэффициентов квадратичной аппроксимации:

,

.

Подставив эти значения в формулу для получим . Точное значение равно .