Multivariate approximation in the worst case setting over reproducing kernel Hilbert spaces

We study the worst case setting for approximation of d variate functions from a general reproducing kernel Hilbert space with the error measured in the L_∞ norm. We mainly consider algorithms that use n arbitrary continuous linear functionals. We look for algorithms with the minimal worst case errors and for their rates of convergence as n goes to infinity. Algorithms using n function values will be analyzed in a forthcoming paper.We show that the L_∞ approximation problem in the worst case setting is related to the weighted L₂ approximation problem in the average case setting with respect to a zero-mean Gaussian stochastic process whose covariance function is the same as the reproducing kernel of the Hilbert space. This relation enables us to find optimal algorithms and their rates of convergence for the weighted Korobov space with an arbitrary smoothness parameter α>1, and for the weighted Sobolev space whose reproducing kernel corresponds to the Wiener sheet measure. The optimal convergence rates are n^-(α-1)/2 and n^-1/2, respectively.We also study tractability of L_∞ approximation for the absolute and normalized error criteria, i.e., how the minimal worst case errors depend on the number of variables, d, especially when d is arbitrarily large. We provide necessary and sufficient conditions on tractability of L_∞ approximation in terms of tractability conditions of the weighted L₂ approximation in the average case setting. In particular, tractability holds in weighted Korobov and Sobolev spaces only for weights tending sufficiently fast to zero and does not hold for the classical unweighted spaces.     

Complexity of Weighted Approximation over

We study approximation of univariate functions defined over the reals. We assume that the rth derivative of a function is bounded in a weighted L_p norm with a weight ψ. Approximation algorithms use the values of a function and its derivatives up to order r−1. The worst case error of an algorithm is defined in a weighted L_q norm with a weight ρ. We study the worst case (information) complexity of the weighted approximation problem, which is equal to the minimal number of function and derivative evaluations needed to obtain error . We provide necessary and sufficient conditions in terms of the weights ψ and ρ, as well as the parameters r, p, and q for the weighted approximation problem to have finite complexity. We also provide conditions which guarantee that the complexity of weighted approximation is of the same order as the complexity of the classical approximation problem over a finite interval. Such necessary and sufficient conditions are also provided for a weighted integration problem since its complexity is equivalent to the complexity of the weighted approximation problem for q=1.     

Weighted BMO and discrete time hedging within the Black-Scholes model

The paper combines two objects rather different at first glance: spaces of stochastic processes having weighted bounded mean oscillation (weighted BMO) and the approximation of certain stochastic integrals, driven by the geometric Brownian motion, by integrals over piece-wise constant integrands. The consideration of the approximation error with respect to weighted BMO implies L_p and uniform distributional estimates for the approximation error by a John-Nirenberg type theorem. The general results about weighted BMO are given in the first part of the paper and applied to our approximation problem in the second one.     

The nonlinear programming method of Wilson,Han, and Powell with an augmented Lagrangian type line search function

Summary The paper represents an outcome of an extensive comparative study of nonlinear optimization algorithms. This study indicates that quadratic approximation methods which are characterized by solving a sequence of quadratic subproblems recursively, belong to the most efficient and reliable nonlinear programming algorithms available at present. The purpose of this paper is to analyse the theoretical convergence properties and to investigate the numerical performance in more detail. In Part 1, the exactL ₁-penalty function of Han and Powell is replaced by a differentiable augmented Lagrange function for the line search computation to be able to prove the global convergence and to show that the steplength one is chosen in the neighbourhood of a solution. In Part 2, the quadratic subproblem is exchanged by a linear least squares problem to improve the efficiency, and to test the dependence of the performance from different solution methods for the quadratic or least squares subproblem.     

A numerical method for the Benjamin-Ono equation

This paper is concerned with the numerical solution of the Cauchy problem for the Benjamin-Ono equationu _t +uu _x −Hu _xx =0, whereH denotes the Hilbert transform. Our numerical method first approximates this Cauchy problem by an initial-value problem for a corresponding 2L-periodic problem in the spatial variable, withL large. This periodic problem is then solved using the Crank-Nicolson approximation in time and finite difference approximations in space, treating the nonlinear term in a standard conservative fashion, and the Hilbert transform by a quadrature formula which may be computed efficiently using the Fast Fourier Transform.     

Operator-splitting galerkin methods for one kind of oin reaction model for the pollution in groundwater

Abstract. The operator-splitting methods for the mathematic model of one kind of oin reactionsfor the problem of groundwater are considered. Optimal error estimates in Lz and Hl norm areobtained for the approximation solution.     

Crossing minimization in weighted bipartite graphs

Given a bipartite graph G=(L₀,L₁,E) and a fixed ordering of the nodes in L₀, the problem of finding an ordering of the nodes in L₁ that minimizes the number of crossings has received much attention in literature. The problem is NP-complete in general and several practically efficient heuristics and polynomial-time algorithms with a constant approximation ratio have been suggested. We generalize the problem and consider the version where the edges have nonnegative weights. Although this problem is more general and finds specific applications in automatic graph layout problems similar to those of the unweighted case, it has not received as much attention. We provide a new technique that efficiently approximates a solution to this more general problem within a constant approximation ratio of 3. In addition we provide appropriate generalizations of some common heuristics usually employed for the unweighted case and compare their performances.     

Refinable Functions with Exponential Decay: An?Approach via Cascade Algorithms

Refinable functions with exponential decay arise from applications such as the Butterworth filters in signal processing. Refinable functions with exponential decay also play an important role in the study of Riesz bases of wavelets generated from multiresolution analysis. A fundamental problem is whether the standard solution of a refinement equation with an exponentially decaying mask has exponential decay. We investigate this fundamental problem by considering cascade algorithms in weighted L _p spaces (1≤p≤∞). We give some sufficient conditions for the cascade algorithm associated with an exponentially decaying mask to converge in weighted L _p spaces. Consequently, we prove that the refinable functions associated with the Butterworth filters are continuous functions with exponential decay. By analyzing spectral properties of the transition operator associated with an exponentially decaying mask, we find a characterization for the corresponding refinable function to lie in weighted L ₂ spaces. The general theory is applied to an interesting example of bivariate refinable functions with exponential decay, which can be viewed as an extension of the Butterworth filters.     

Boundary control of parabolic systems: Finite-element approximation

Finite-element approximation of a Dirichlet type boundary control problem for parabolic systems is considered. An approach based on the direct approximation of an input-output semigroup formula is applied. Error estimates inL ₂[OT; L ₂()] andL ₂[OT; L ₂()] norms are derived for optimal state and optimal control, respectively. It turns out that these estimates areoptimal with respect to the approximation theoretic properties.Research supported in part under Grant no. NSG 4015, National Aeronautics and Space Administration.     

Algorithms for bestL 1 andL ∞ linear approximations on a discrete set

This paper supplies algorithms for the best approximation to a real-valued function, defined as a table of values, by a linear approximating function in both theL ₁ andL norms. The algorithms are modified simplex algorithms which due to the particular structures of the tableaux have been condensed and require minimal storage space. Both algorithms are given asAlgol procedures and sample times are noted for several examples.     

Finite element approximation of viscoelastic fluid flow: Existence of approximate solutions and error bounds

Summary We study a finite element approximation of viscoelastic fluid flow obeying an Oldroyd B type constitutive law. The approximate stress, velocity and pressure are respectivelyP ₁ discontinuous,P ₂ continuous,P ₁ continuous. We use the method of Lesaint-Raviart for the convection of the extra stress tensor. We suppose that the continuous problem admits a sufficiently smooth and sufficiently small solution. We show by a fixed point method that the approximate problem has a solution and we give an error bound.This work has been supported in part by the GDR CNRS 901 Rhéologie der polymères fondus.     

Integration and approximation in arbitrary dimensions

We study multivariate integration and approximation for various classes of functions of d variables with arbitrary d. We consider algorithms that use function evaluations as the information about the function. We are mainly interested in verifying when integration and approximation are tractable and strongly tractable. Tractability means that the minimal number of function evaluations needed to reduce the initial error by a factor of ɛ is bounded by C(d)ɛ^−p for some exponent p independent of d and some function C(d). Strong tractability means that C(d) can be made independent of d. The ‐exponents of tractability and strong tractability are defined as the smallest powers of ɛ{^-1} in these bounds. We prove that integration is strongly tractable for some weighted Korobov and Sobolev spaces as well as for the Hilbert space whose reproducing kernel corresponds to the covariance function of the isotropic Wiener measure. We obtain bounds on the ‐exponents, and for some cases we find their exact values. For some weighted Korobov and Sobolev spaces, the strong ‐exponent is the same as the ‐exponent for d=1, whereas for the third space it is 2. For approximation we also consider algorithms that use general evaluations given by arbitrary continuous linear functionals as the information about the function. Our main result is that the ‐exponents are the same for general and function evaluations. This holds under the assumption that the orthonormal eigenfunctions of the covariance operator have uniformly bounded L∞ norms. This assumption holds for spaces with shift-invariant kernels. Examples of such spaces include weighted Korobov spaces. For a space with non‐shift‐invariant kernel, we construct the corresponding space with shift-invariant kernel and show that integration and approximation for the non-shift-invariant kernel are no harder than the corresponding problems with the shift-invariant kernel. If we apply this construction to a weighted Sobolev space, whose kernel is non-shift-invariant, then we obtain the corresponding Korobov space. This enables us to derive the results for weighted Sobolev spaces. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the convergence of an algorithm for discreteL p approximation

Summary The convergence properties of an algorithm for discreteL _p approximation (1p<2) that has been considered by several authors are studied. In particular, it is shown that for 1<p<2 the method converges (with a suitably close starting value) to the best approximation at a geometric rate with asymptotic convergence constant 2-p. A similar result holds forp=1 if the best approximation is unique. However, in this case the convergence constant depends on the function to be approximated.     

Complexity of Weighted Approximation over

We study approximation of multivariate functions defined over ^d. We assume that all rth order partial derivatives of the functions considered are continuous and uniformly bounded. Approximation algorithms (f) only use the values of f or its partial derivatives up to order r. We want to recover the function f with small error measured in a weighted L_q norm with a weight function ρ. We study the worst case (information) complexity which is equal to the minimal number of function and derivative evaluations needed to obtain error . We provide necessary and sufficient conditions in terms of the weight ρ and the parameters q and r for the weighted approximation problem to have finite complexity. We also provide conditions guaranteeing that the complexity is of the same order as the complexity of the classical approximation problem over a finite domain. Since the complexity of the weighted integration problem is equivalent to the complexity of the weighted approximation problem with q=1, the results of this paper also hold for weighted integration. This paper is a continuation of [7], where weighted approximation over was studied.     

Smolyak's algorithm for weighted <Emphasis Type="Italic">L</Emphasis><Subscript>1</Subscript>-approximation of multivariate functions with bounded <Emphasis Type="Italic">r</Emphasis>th mixed derivatives over ℝ<Superscript>d</Superscript>

We are interested in numerical algorithms for weighted L₁ approximation of functions defined on . We consider the space ℱ_r,d which consists of multivariate functions whose all mixed derivatives of order r are bounded in L₁-norm. We approximate f∈ℱ_r,d by an algorithm which uses evaluations of the function. The error is measured in the weighted L₁-norm with a weight function ρ. We construct and analyze Smolyak's algorithm for solving this problem. The algorithm is based on one-dimensional piecewise polynomial interpolation of degree at most r−1, where the interpolation points are specially chosen dependently on the smoothness parameter r and the weight ρ. We show that, under some condition on the rate of decay of ρ, the error of the proposed algorithm asymptotically behaves as , where n denotes the number of function evaluations used. The asymptotic constant is known and it decreases to zero exponentially fast as d→∞.     

A θ-stable approximations of abstract Cauchy problems

Summary We study the approximation of linear parabolic Cauchy problems by means of Galerkin methods in space andA -stable multistep schemes of arbitrary order in time. The error is evaluated in the norm ofL _t ² (H _x ¹ ) L _t (L _x ² ).     

Lp-Continuous extreme selectors of multifunctions with decomposable values: Relaxation theorems

Some density theorems of L _p-continuous selectors whose values are extreme points are proved for a class of multivalued maps. applications to the Darboux problem for a differential inclusion are presented.Supported in part by RFFI Grant 93-011-264.     

Finite element approximation of the volume-matching problem

Summary Optimal orderH ¹ andL error bounds are obtained for a continuous piecewise linear finite element approximation of the volume matching problem. This problem consists of minimising |v| _1, ² overvH ¹() subject to the inequality constraintv0 and a number of linear equality constraints. The presence of the equality constraints leads to Lagrange multipliers, which in turn lead to complications with the standard error analysis for variational inequalities. Finally we consider an algorithm for solving the resulting algebraic problem.Supported by a SERC research studentship     

SimultaneousL 1 approximation of a compact set of real-valued functions

Summary In this paper the uniqueness results found in simultaneous Chebychev approximation are extended to simultaneousL ₁ approximation. In particular a sufficient condition to guarantee uniqueness of a best approximate to aL ₁ compact set is given.This paper is taken in part from a thesis to be submitted by M. P. Carroll in partial fulfillment of the requirements for the Ph. D. degree in the Department of Mathematics at Rensselaer Polytechnic Institute.     

Fitting scattered data on spherelike surfaces using tensor products of trigonometric and polynomial splines

Summary A method is presented for fitting a function defined on a general smooth spherelike surfaceS, given measurements on the function at a set of scattered points lying onS. The approximating surface is constructed by mapping the surface onto a rectangle, and using a tensor-product of polynomial splines with periodic trigonometric splines. The use of trigonometric splines allows a convenient solution of the problem of assuring that the resulting surface is continuous and has continuous tangent planes at all points onS. Two alternative algorithms for computing the coefficients of the tensor fit are presented; one based on global least-squares, and the other on the use of local quasi-interpolators. The approximation order of the method is established, and the numerical performance of the two algorithms is compared.Supported in part by the National Science Foundation under Grant DMS-8902331 and by the Alexander von Humboldt Foundation