О вычислительной избыточности метода дихотомии и условной минимизации унимодальных функций методом экономной дихотомии | Научно-инновационный портал СФУ

О вычислительной избыточности метода дихотомии и условной минимизации унимодальных функций методом экономной дихотомии

Перевод названия: ON COMPUTATIONAL REDUNDANCY OF THE DICHOTOMOUS SEARCH AND CONDITIONAL MINIMIZATION OF UNIMODAL FUNCTIONS BY THE ECONOMICAL DICHOTOMOUS SEARCH

Тип публикации: статья из журнала

Год издания: 2019

Идентификатор DOI: 10.14357/08696527190113

Ключевые слова: унимодальная функция, метод дихотомии, метод золотого сечения, метод чисел Фибоначчи, метод экономной дихотомии, монотонная функция, быстродействие метода, unimodal function, Dichotomous search, Golden section search, Fibonacci number method, economical dichotomous search, Monotone function, method speed

Аннотация: Высказана гипотеза о вычислительной избыточности широко известного метода дихотомии (МД), используемого наряду с другими известными численными методами, в частности методом золотого сечения (МЗС), для условной минимизации унимодальных функций. Сформулирована методика устранения вычислительной избыточности метода и на ее основе разработан и предложен метод минимизации таких функций, названный методом экономной дихотомии (МЭД). Разработаны алгоритмы и код, реализующие метод на языке Delphi. Приведены результаты вычислительного эксперимента, показавшие, что по быстродействию, определяемому количеством вычислений минимизируемой функции (МФ), экономный метод не менее чем в 1,5 раза эффективнее классического МД. Это значит, что в среднем из трех вычислений МФ по МД одно является избыточным. По сравнению с МЗС и МД в среднестатистическом плане метод имеет приблизительно в 1,3 и 1,7 раз большее быстродействие соответственно. Иными словами, метод работает во столько раз быстрее МЗС, во сколько последний работает быстрее классического МД. Данный вывод позволяет критически отнестись к устоявшемуся представлению о том, что МД - худший из методов отсечения отрезков. С учетом полученных результатов МЭД заметно превосходит по быстродействию лучший из них - МЗС и может обоснованно претендовать на лидирующие позиции в данном семействе методов. The hypothesis about the computational redundancy of the well-known dichotomous search, applied along with other known numerical methods, in particular, the golden section search, for the conditional minimization of unimodal functions, is discussed. The technique for eliminating the computational redundancy of the method is formulated and on its basis, a method for minimizing such functions, called the economical dichotomous search, is developed. The author developed the algorithms and code that implement the method in Delphi. The results of a computational experiment are described. They show that the economical method is about 1.5 times more efficient than the classical dichotomous search by a speed determined by the number of calculations of the minimized function. It means that, on average, in three calculations of the function being minimized by dichotomous search, one is redundant. In comparison with the golden section search and the dichotomous search in the average statistical plan, the method is approximately 1.3 and 1.7 times faster, respectively. In other words, the method works as many times faster than the method of the golden section search, as the latter works faster than the classical dichotomous search. This conclusion allows us to take a critical view of the established notion that the dichotomous search is the worst method of cutting off segments. Taking into account the obtained results, the dichotomous search significantly exceeds the speed of the best of them - the golden section search and can reasonably claim to have the leading position in this family of methods.

Ссылки на полный текст

Издание

Журнал: Системы и средства информатики

Выпуск журнала: Т. 29, 1

Номера страниц: 164-173

ISSN журнала: 08696527

Место издания: Москва

Издатель: Федеральное государственное учреждение "Федеральный исследовательский центр "Информатика и управление" Российской академии наук

Авторы

Вхождение в базы данных

Информация о публикациях загружается с сайта службы поддержки публикационной активности СФУ. Сообщите, если заметили неточности.

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