Geodesic
Complexity of Approximate Realizations of Lipschitz Functions by Schemes in Continuous Bases
Matematičeskie zametki, Tome 92 (2012) no. 1, pp. 27-43

Voir la notice de l'article provenant de la source Math-Net.Ru

We show that any function satisfying the Lipschitz condition on a given closed interval can be approximately computed by a scheme (nonbranching program) in the basis composed of functions $$ x-y,\quad |x|,\quad x*y=\min(\max(x,0),1)\min(\max(y,0),1), $$ and all constants from the closed interval $[0,1]$; here the complexity of the scheme is $O(1/\sqrt{\varepsilon})$, where $\varepsilon$ is the accuracy of the approximation. This estimate of complexity, is in general, order-sharp.
Keywords: Lipschitz function, (Lipshitz) continuous basis, Lipschitz condition, complexity of the approximate realization of functions, polynomial basis. 
@article{MZM_2012_92_1_a2,
     author = {Ya. V. Vegner and S. B. Gashkov},
     title = {Complexity of {Approximate} {Realizations} of {Lipschitz} {Functions} by {Schemes} in {Continuous} {Bases}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {27--43},
     publisher = {mathdoc},
     volume = {92},
     number = {1},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2012_92_1_a2/}
}
TY  - JOUR
AU  - Ya. V. Vegner
AU  - S. B. Gashkov
TI  - Complexity of Approximate Realizations of Lipschitz Functions by Schemes in Continuous Bases
JO  - Matematičeskie zametki
PY  - 2012
SP  - 27
EP  - 43
VL  - 92
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2012_92_1_a2/
LA  - ru
ID  - MZM_2012_92_1_a2
ER  - 
%0 Journal Article
%A Ya. V. Vegner
%A S. B. Gashkov
%T Complexity of Approximate Realizations of Lipschitz Functions by Schemes in Continuous Bases
%J Matematičeskie zametki
%D 2012
%P 27-43
%V 92
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2012_92_1_a2/
%G ru
%F MZM_2012_92_1_a2
Ya. V. Vegner; S. B. Gashkov. Complexity of Approximate Realizations of Lipschitz Functions by Schemes in Continuous Bases. Matematičeskie zametki, Tome 92 (2012) no. 1, pp. 27-43. http://geodesic.mathdoc.fr/item/MZM_2012_92_1_a2/