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

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

для метода деления интервала пополам; для метода золотого сечения.

Для сравнения рассмотрим также метод равномерного поиска, в соответствии с которым оценивание функции проводится в N равноотстоящих друг от друга точках (при этом интервал Li делится на (N+1) равных интервалов длины ). Пусть х* - точка, в которой наблюдается минимум функции . Тогда точка истинного минимума f(x) оказывается заключенной в интервале

откуда . Следовательно, для метода равномерного поиска

.

В табл. 2.1 представлены значения FR (N), соответствующие выранным N, для трех методов поиска.

Таблица 2.1. Величины относительного уменьшения интервала

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

для метода деления интервала пополам

,

для метода золотого сечения

б

для метода равномерного поиска

.

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

Таблица 2.2. Требуемые количества вычислений значений функции

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

Поиск по сайту: