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



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

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

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

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

.

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

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

Метод поиска

Количество вычислений значений функции

N=2 N=5 N=10 N=15 N=20
Метод деления интервала пополам 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.182 0.125 0.095

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

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

,

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

б

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

.

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

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

Метод поиска

Количество вычислений значений функции

Е=0.1 Е=0.05 Е=0.01 Е=0.001
Метод деления интервала пополам 7 9 14 20
Метод золотого сечения 6 8 11 16
Метод равномерного поиска 19 39 199 1999

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


Дата добавления: 2018-02-15; просмотров: 717; Мы поможем в написании вашей работы!






Мы поможем в написании ваших работ!