|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Оценка трудоёмкости алгоритма по поиску нуля одной выпуклой кусочно-линейной функции
Е. В. Просолупов, Г. Ш. Тамасян Санкт-Петербургский гос. университет, Университетский пр., 35, 198504 Санкт-Петербург, Россия
Аннотация:
Известно, что задача ортогонального проецирования точки на стандартный симплекс сводится к решению скалярного уравнения. В работе анализируется трудоёмкость алгоритма поиска нуля выпуклой кусочно-линейной функции, предложенного в [30]. Проведён анализ лучших и худших случаев входных данных для алгоритма. Для этого изучены наибольшее и наименьшее числа итераций алгоритма как функции от размера входных данных. Показано, что в случае равенства элементов входного множества алгоритм совершает наименьшее число итераций. В случае же различающихся элементов входного множества количество итераций максимально и очень слабо зависит от конкретных значений элементов множества. Приведены результаты вычислительных экспериментов со случайными входными данными высокой размерности. Табл. 2, ил. 2, библиогр. 34.
Ключевые слова:
стандартный симплекс, ортогональное проецирование точки, нули функции.
Статья поступила: 10.03.2017 Переработанный вариант: 26.12.2017
Образец цитирования:
Е. В. Просолупов, Г. Ш. Тамасян, “Оценка трудоёмкости алгоритма по поиску нуля одной выпуклой кусочно-линейной функции”, Дискретн. анализ и исслед. опер., 25:2 (2018), 82–100; J. Appl. Industr. Math., 12:2 (2018), 325–333
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da897 https://www.mathnet.ru/rus/da/v25/i2/p82
|
Статистика просмотров: |
Страница аннотации: | 185 | PDF полного текста: | 127 | Список литературы: | 24 | Первая страница: | 5 |
|