scientific article; zbMATH DE number 139637

Publication date 28 March 1993

asymptotic behaviour continuous functions measures of complexity

Approximation by other special function classes (41A30) Analysis of algorithms and problem complexity (68Q25)

[For the entire collection see Zbl 0745.00057.] A fixed nonempty set \(B\) consisting of continuous functions \(w_ k(x_ 1,\dots,x_ m): \mathbb{R}^ m\to \mathbb{R}\), \(m=m(w_ k)\) is said to be a basis. A scheme in this basis is a sequence of continuous functions \(f_ 1(x_ 1,\dots,x_ n),\dots,f_ L(x_ 1,\dots,x_ n)\), where \(f_ i(x_ 1,\dots,x_ n)=x_ i\), \(i=1,\dots,n\); \(f_ \ell(x_ 1,\dots,x_ n)=w_ k(f_{j_ 1}(x_ 1,\dots,x_ n),\dots,f_{j_ m}(x_ 1,\dots,x_ n)) \), \(w_ k\in B\), \(k=k(\ell)\), \(n<\ell<L\). In the considered set of continuous functions let \({\mathfrak A}_ B\) be the subset of all the functions \(g\) which can be exactly realized by schemes from the basis \(B\). The author defines three measures of complexity on the set \({\mathfrak A}_ B\). For instance, one of these measures \(L_ B(g)\) is the smallest number of elements in the scheme realizing the function \(g\). Then \(L_ B(g,\varepsilon)=\inf\{L_ B(g)\mid g\in{\mathfrak A}_ B,\;\| f-g\|<\varepsilon\}\) is the complexity of the \(\varepsilon\)- approximation of the function \(f\) by functions from \({\mathfrak A}_ B\). The aim of the paper is to examine the asymptotic behaviour of \(L_ B(g,\varepsilon)\), as \(\varepsilon\to 0\). The same problem for other two measures of complexity is defined by the author in the paper.

Recommendations

Cited in

(17)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4029617)