UNIVERSITY
OF WROCŁAW
 
Main Page
Contents
Online First
General Information
Instructions for authors


VOLUMES
43.2 43.1 42.2 42.1 41.2 41.1 40.2
40.1 39.2 39.1 38.2 38.1 37.2 37.1
36.2 36.1 35.2 35.1 34.2 34.1 33.2
33.1 32.2 32.1 31.2 31.1 30.2 30.1
29.2 29.1 28.2 28.1 27.2 27.1 26.2
26.1 25.2 25.1 24.2 24.1 23.2 23.1
22.2 22.1 21.2 21.1 20.2 20.1 19.2
19.1 18.2 18.1 17.2 17.1 16.2 16.1
15 14.2 14.1 13.2 13.1 12.2 12.1
11.2 11.1 10.2 10.1 9.2 9.1 8
7.2 7.1 6.2 6.1 5.2 5.1 4.2
4.1 3.2 3.1 2.2 2.1 1.2 1.1
 
 
WROCŁAW UNIVERSITY
OF SCIENCE AND
TECHNOLOGY

Contents of PMS, Vol. 32, Fasc. 1,
pages 131 - 165
 

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 d variables which are almost surely rk -times continuously differentiable with respect to the k -th variable and 0 ≤ rk ≤ rk+1 . Let n(ε,d) denote the minimal number of continuous linear functionals which is needed to find an algorithm that uses n 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 C and p such that

n(ε,d) ≤ Cε- p for alld ∈ IN = (1,2,...), andε ∈ (0,1).
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,
whereas it holds for the Wiener case iff
liminf rk > 0 forsome s > 1. k→∞ ks 2
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.

Download:    Abstract    Full text   Abstract + References