RUS  ENG
Полная версия
ЖУРНАЛЫ // Прикладная дискретная математика // Архив

ПДМ, 2014, номер 3(25), страницы 111–116 (Mi pdm472)

Вычислительные методы в дискретной математике

Вычисление вещественной W-функции Ламберта $W_0$ в пределах FP//LINSPACE

М. А. Старицын, С. В. Яхонтов

Санкт-Петербургский государственный университет, г. Санкт-Петербург, Россия

Аннотация: Строится FP//LINSPACE алгоритмический аналог вещественной W-функции Ламберта $W_0(x)$ на отрезке $[-(re)^{-1},(re)^{-1}]$ FP//LINSPACE алгоритмических вещественных чисел, где $r$ – рациональное, $r>4/3$ (в качестве $r$ можно брать любое рациональное с таким условием). Для построения алгоритмического аналога вещественной W-функции Ламберта $W_0(x)$ предлагается алгоритм WLE расчёта двоично-рациональных приближений данной функции на отрезке $[-(re)^{-1},(re)^{-1}]$ с полиномиальной временной и линейной емкостной сложностью на машине Тьюринга. Алгоритм WLE строится на основе разложения в ряд Тейлора данной функции, при этом показывается и используется в алгоритме линейная сходимость ряда Тейлора W-функции Ламберта $W_0(x)$ на отрезке $[-(re)^{-1},(re)^{-1}]$.

Ключевые слова: вещественная W-функция Ламберта $W_0$, алгоритмические вещественные функции, машина Тьюринга, полиномиальная временная сложность, линейная емкостная сложность.

УДК: 510.25+510.52+519.688



© МИАН, 2024