855 research outputs found
On adaptive information with varying cardinality for linear problems with elliptically contoured measures
No full textAbstractAdaptive information is not more powerful than nonadaptive information for solving linear problems with elliptically contoured measures provided that the cardinality of information is fixed (see G. W. Wasilkowski and H. Woźniakowski, 1984, Numer. Math.44, 169–190). Can adaptive information be essentially more powerful than nonadaptive information when cardinality is allowed to vary? The answer is negative if a Gaussian measure is considered (see G. W. Wasilkowski, 1986, J. Complexity2, 204–228). This work generalizes the result to a class of elliptically contoured measures for which the answer is still negative
A brief history of the life and works of G.W. Jackson : forty-five years principal of the G.W. Jackson High School, Corsicana, Texas
No full textAn autobiographical pamphlet by G.W. Jackson.Includes 3 poems by the author
Any iteration for polynomial equations using linear information has infinite complexity
No full textAbstractThis is the third paper in which we study iterations using linear information for the solution of nonlinear equations. In Wasilkowski [1] and [2] we have considered the existence of globally convergent iterations for the class of analytic functions. Here we study the complexity of such iterations. We prove that even for the class of scalar complex polynomials with simple zeros, any iteration using arbitrary linear information has infinite complexity. More precisely, we show that for any iteration ϕ and any integer k, there exists a complex polynomial ƒ with all simple zeros such that the first k approximations produced by ϕ do not approximate any solution of ƒ=0 better than a starting approximation x0. This holds even if the distance between x0 and the nearest solution of ƒ=0 is arbitrarily small
On a posteriori upper bounds for approximating linear functionals in a probabilistic setting
No full textSome nonlinear problems are as easy as the approximation problem
No full textAbstractIn this paper we study the following problem. Given an operator S and a subset F0 of some linear space, approximate S(f) for any fϵF0 possessing only partial information on f. Although all operators S considered here are nonlinear (e.g. min f(x), min¦f(x)¦, 1/f or ∥f∥), we prove that these problems are “equivalent” to the problem of approximating S(f) = f, i.e. S = I. This equivalence provides optimal (or nearly optimal) information and algorithms
Integration and Approximation of Multivariate Functions: Average Case Complexity with Isotropic Wiener Measure
No full textAbstractWe study the average case complexity of multivariate integration and L2 function approximation for the class F = C([0, 1]d) of continuous functions of d variables. The class F is endowed with the isotropic Wiener measure (Brownian motion in Lévy′s sense). For the integration problem, the average case complexity of solving the problem to within ϵ is proportional to ϵ-2/(1 + 1/d). This is a negative result since for a large number d of variables, the average case complexity is close to ϵ−2; the latter is also achieved by the classical Monte Carlo method in the randomized worst case setting. Furthermore, Θ(ϵ−2) is the highest possible average case complexity among all probability measures with finite expectation of ||ƒ2L2. Thus, for large d, the average case complexity of the integration problem with isotropic Wiener measure behaves as the worst possible average complexity. For the function approximation problem, the complexity is even higher since it is proportional to ϵ−2d. These two negative results are in a sharp contrast to (H. Woźniakowski, Bull. Amer. Math. Soc.24, No. 1 (1991), 185-194; Bull. Amer. Math. Soc., to appear), where, for F endowed with the Wiener sheet measure, small average case complexities have been proven. Indeed, they are of order ϵ−1(log ϵ−1)(d−1)/2 and ϵ−2(log ϵ−1)2(d−1) for the integration and function approximation problems, respectively. ccc
Information of varying cardinality
No full textAbstractWe study adaptive information of varying cardinality for linear problems defined on a separable Banach space. It is known that for linear problems adaptive information of fixed cardinality does not help in the worst case setting. It does not help also in the average case setting with Gaussian measures. We prove that in the worst case setting a similar result holds for information of varying cardinality. In the average case setting with Gaussian measures, information of varying cardinality can be more powerful than information of fixed cardinality. However, optimal information has a structure which is almost as simple as nonadaptive information of fixed cardinality. We also give a condition under which varying cardinality does not help. These results are useful for deriving tight bounds on complexity, which is also studied in this paper
Liberating the dimension for L2-approximation
No full textAbstractWe consider approximation of ∞-variate functions with the error measured in a weighted L2-norm. The functions being approximated belong to weighted tensor product spaces with arbitrary weights γu. We provide complexity upper bounds and sufficient conditions for polynomial and weak tractabilities expressed in terms of the properties of the weights γu and the complexity of the corresponding univariate approximation problem. These tractability conditions are also necessary for important types of weights including product weights
- …
