Эта публикация цитируется в
1 статье
Сложность приближенной реализации липшицевых функций схемами в континуальных базисах
Я. В. Вегнер,
С. Б. Гашков Московский государственный университет им. М. В. Ломоносова
Аннотация:
В работе показано, что любую функцию, удовлетворяющую условию Липшица на данном отрезке, можно приближенно вычислить схемой (неветвящейся программой) в базисе, состоящем из функций
$$
x-y,\quad |x|,\quad x*y=\min(\max(x,0),1)\min(\max(y,0),1),
$$
и всех констант из отрезка
$[0,1]$, сложность которой равна
$O(1/\sqrt{\varepsilon})$, где
$\varepsilon$ – точность приближения. Указанная оценка сложности, вообще говоря, по порядку точная.
Библиография: 21 название.
УДК:
519.712.4 Поступило: 26.01.2009
Исправленный вариант: 23.08.2011
DOI:
10.4213/mzm7099