🚀 go-pugleaf

Hi all.

In article <Bvs362.4wo@mentor.cc.purdue.edu> hrubin@mentor.cc.purdue.edu (Herman Rubin) writes:

   It is not necessarily the case that even in one dimension, Gaussian
   quadrature is that great.  If one uses 32-point quadrature, the result
   is exact for polynomials of degree 63, but it is not too hard to find
   "natural" functions which are not well approximated by polynomials of
   degrees under the thousands, at least.

To be more specific, suppose you want to compute the integral of a
function in the $d$-dimensional unit cube.  Suppose further that your
class of integrands belongs to the unit ball of the Sobolev space
$W^{r,\infty}$.  (Roughly speaking, overall smoothness of order $r$
almost everywhere; the "unit ball" part is a normalization.)  Our
model of computation assumes a fixed cost for function evaluations and
that basic scalar operations have unit cost.

Suppose we use a worst case setting, i.e., the error of an
algorithm $\phi$ using evalutions at $t_1, \ldots, t_n$ is given as
$$|sup_{f\in F} \bigg|\int_D f - \phi(f(t_1),\ldots,f(t_n)) \bigg|.$$
Then the minimal error possible with $n$ function evaluations is
proportional to $n^{-r/d}$.  Alternatively, the $\epsilon$-complexity
(the *minimal* cost of an $\epsilon$-accurate approximation) is
proportional to $(1/\epsilon)^{d/r}$.

If we ignore the proportionality constants, this means that for fixed
smoothness $r$ and error criterion $\epsilon$, the complexity grows
exponentially in $d$.  Note that we're talking about complexity here,
i.e., the minimal cost over all algorithms.  This means that the
integration problem is inherently intractible for high-dimensional
regions.

If we want to beat this intractability, we have onlly two
alternatives:

(1) Change the model of computation.

(2) Change the setting (e.g., use an expectation instead of a sup when
    combining the errors at each problem element $f$ to find the
    overall error of an algorithm).

(3) Use another class of functions as the problem elements.  
    
For further discussion, refer to Wo\'zniakowski's article in the
BUlletin of the AMS (January, 1991).

 
--
      Art Werschulz
      InterNet:  agw@cs.columbia.edu
      ATTnet:    Columbia University (212) 939-7061
                 Fordham University  (212) 636-6325