Библиографическое описание:О вычислительной избыточности метода дихотомии и условной минимизации унимодальных функций методом экономной дихотомии / В. А. Коднянко. - Текст : непосредственный // Системы и средства информатики. - 2019. - Т. 29, № 1. - С. 164-173. - ISSN 0869-6527, DOI 10.14357/08696527190113. Перевод заглавия: ON COMPUTATIONAL REDUNDANCY OF THE DICHOTOMOUS SEARCH AND CONDITIONAL MINIMIZATION OF UNIMODAL FUNCTIONS BY THE ECONOMICAL DICHOTOMOUS SEARCH
Аннотация:Высказана гипотеза о вычислительной избыточности широко известного метода дихотомии (МД), используемого наряду с другими известными численными методами, в частности методом золотого сечения (МЗС), для условной минимизации унимодальных функций. Сформулирована методика устранения вычислительной избыточности метода и на ее основе разработан и предложен метод минимизации таких функций, названный методом экономной дихотомии (МЭД). Разработаны алгоритмы и код, реализующие метод на языке 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.
Ключевые слова:унимодальная функция, метод дихотомии, метод золотого сечения, метод чисел Фибоначчи, метод экономной дихотомии, монотонная функция, быстродействие метода, unimodal function, Dichotomous search, Golden section search, Fibonacci number method, economical dichotomous search, Monotone function, method speed
