TRACTABILITY OF MULTI-PARAMETRIC EULER AND WIENER
INTEGRATED PROCESSES
Mikhail Lifshits
Anargyros Papageorgiou
Henryk Woźniakowski
Abstract: We study average case approximation of Euler and Wiener integrated processes of
variables which are almost surely
-times continuously differentiable with respect to the
-th variable and
. Let
denote the minimal number of continuous
linear functionals which is needed to find an algorithm that uses
such functionals and
whose average case error improves the average case error of the zero algorithm by a factor
.
Strong polynomial tractability means that there are nonnegative numbers
and
such
that
![n(ε,d) ≤ Cε- p for alld ∈ IN = (1,2,...), andε ∈ (0,1).](files/32.1/HTML/32.1.10.abs9x.png)
We
prove that the Wiener process is much more difficult to approximate than the Euler process.
Namely, strong polynomial tractability holds for the Euler case iff
![-rk --1--
limki→n∞f lnk > 2ln3,](files/32.1/HTML/32.1.10.abs10x.png)
whereas it holds for the Wiener case iff
![liminf rk > 0 forsome s > 1.
k→∞ ks 2](files/32.1/HTML/32.1.10.abs11x.png)
Other types of tractability are also studied.
2000 AMS Mathematics Subject Classification: Primary: 65Y20; Secondary: 41A25,
41A63, 60G15, 60G60.
Keywords and phrases: Tractability, Wiener process, Euler process, integrated
processes, linear approximation.