Lattice-Nystrom method for Fredholm integral equations of the second kind with convolution type kernels
We consider Fredholm integral equations of the second kind of the form f(x) = g(x) + integral k(x-y) f(y) dy, where g and k are given functions from weighted Korobov spaces. These spaces are characterized by a smoothness parameter alpha > 1 and weights gamma(1) >= gamma(2) >=... The weight gamma(j) moderates the behavior of the functions with respect to the jth variable. We approximate f by the Nystrom method using n rank-1 lattice points. The combination of convolution and lattice group structure means that the resulting linear system can be solved in O(n log n) operations. We analyze the worst case error measured in sup norm for functions g in the unit ball and a class of functions k in weighted Korobov spaces. We show that the generating vector of the lattice rule can be constructed component-by-component to achieve the optimal rate of convergence O(n(-alpha/2+delta)), delta >0, with the implied constant independent of the dimension d under an appropriate condition on the weights. This construction makes use of an error criterion similar to the worst case integration error in weighted Korobov spaces, and the computational cost is only O(n log nd) operations. We also study the notion of QMC-Nystrom tractability: tractability means that the smallest n needed to reduce the worst case error (or normalized error) to F is bounded polynornially in epsilon(-1) and d; strong tractability means that the bound is independent of d. We prove that strong QMC-Nystrom tractability in the absolute sense holds iff Sigma(infinity)(j=1) gamma j  infinity)Sigma(d)(j=1) gamma(j)/(log d+1) < infinity (c) 2007 Published by Elsevier Inc.
nystrom method worst case error lattice rules tractability quasi-monte carlo rules fredholun integral equations