Brad Baxter

Raymond Brummelhuis

CONVERGENCE OF STATIONARY RBF-SCHEMES FOR THE NUMERICAL SOLUTION OF EVOLUTION EQUATIONS

Introduction

In this paper we establish convergence rates for semi-discrete stationary RBF schemes for the classical heat equation and, more generally, for a large class of translation invariant pseudo-differential evolution equations which include the fractional heat equation and the Kolmogorov-Fokker-Planck equations of Lévy processes (under natural conditions on the Lévy measure), but also hyperbolic equations such as the half-wave equation.

The scheme we investigate is the RBF-version of the method of lines, whose numerical performance was examined in for example [START_REF] Brummelhuis | A radial basis function scheme for option pricing in exponential Lévy models[END_REF], [START_REF] Khaliq | A parallel time stepping approach using meshfree approximations for pricing options with non-smooth payoffs[END_REF], [START_REF] Pettersson | Improved radial basis function methods for multi-dimensional option pricing[END_REF] [5], [START_REF] Chan | A Numerical Study of Radial Basis Function Based Methods for Options Pricing under the One Dimension Jump-diffusion Model[END_REF]. For the theoretical analysis of this paper, we will study this scheme when implemented on regular square grids with a grid size tending to 0. We use stationary RBF-interpolation, letting the basis function scale with the grid. Our main results will relate the order of convergence of the scheme to the degree of the operator and to the order of the underlying RBF interpolation. The latter will only be algebraic, since we use stationary interpolation, but can be arbitrarily large, depending on the basis function. We will furthermore show that under certain circumstances approximate approximation phenomena occur, in the sense that, in case of non-convergence of the scheme to the true solution, one can nevertheless get arbitrarily close to the real solution by an appropriate choice of basis function, or, if the scheme does converge, one can, for initial values which are sufficiently smooth, observe an apparent order of convergence which is bigger than the actual one for grid-sizes which are small but not too small. We do not limit ourselves to particular examples of RBFs such as the generalized multiquadrics or the polyharmonic basis functions, but perform our analysis for a general class of basis functions which we define in section 2. Since this class is a generalization of one introduced by Martin Buhmann in [START_REF] Buhmann | Multivariate Cardinal Interpolation with Radial Basis Functions[END_REF] and by which it was inspired, we have called it the Buhmann class. We will analyze the properties of our scheme in Fourier space and, for that reason, first re-examine in section 3 the convergence of RBF-interpolation on regular grids from the Fourier point of view by deriving precise estimates for the Wiener norm of the difference between a function and its RBFinterpolant. Our convergence theorems have a non-zero intersection with classical results of Buhman and Powell (see [START_REF] Buhmann | Radial Basis Functions[END_REF] and its references), strengthening these in some respects. Despite the use of the Wiener norm we can allow certain classes of polynomially increasing functions. The Fourier transform of such a function will have a non-integrable algebraic singularity at 0, and the allowed order of the singularity (and therefore the allowed rate of growth of the function) will depend on the basis function which is used for the interpolation. In section 4 we show that the convergence rates which we found in section 3 is best possible, and discuss approximate approximation.

The next two sections examine the convergence of the RBF-variant of the method of lines, first, in section 5, for the in many respects typical case of classical heat equation before indicating, in section 6, how to extend the results to a general class of class of pseudo-differential evolution equations. We show that the scheme converges at a rate of h κ-q , where q is the order of the operator (q = 2 for the heat equation) and κ the order of convergence of the underlying RBF-interpolation scheme, which is also the order of the singularity in 0 of the Fourier transform of the basis function which is used. We show that this rate in in general optimal, and again show there is an approximate approximation phenomenon, in the sense that for appropriate basis functions which are sufficiently "flat" and with sufficiently smooth initial data there can be an apparent higher order of convergence when h is not too small, which is determined by the degree of smoothness of the initial data. This is shown to explain the empirical convergence rates which were found in [START_REF] Brummelhuis | A radial basis function scheme for option pricing in exponential Lévy models[END_REF].

One limitation of the present analysis is that we have restricted ourselves to interpolation on regular grids of scaled integer points, whereas one of the strengths of the RBF method is that one can use arbitrarily scattered interpolation points, opening up the way to adaptive methods (this flexibility may be especially important for variable coefficient linear differential operators or non-linear ones). Note, however, that the much-used Finite Difference methods are usually restricted to regular grids also, and that even on regular grids the RBF method of this paper can have definite advantages over the FD methods: they do not discretize the operator, and can therefore be better suited when the latter has a singular kernel, such as for the Kolmogorov backward equation of a Lévy processes: see [START_REF] Brummelhuis | A radial basis function scheme for option pricing in exponential Lévy models[END_REF]. Another limitation is that we only have treated translation invariant operators, which are Fourier multiplier operators. These do however already include large classes of operators which are of interest of applications, such as the aforementioned Kolmogorov-Fokker-Planck equations of certain Lévy processes or the fractional heat equation. It would obviously be interesting to generalize our results to variable coefficient PDEs, but this may require other methods. Finally, as noted, we primarily examine convergence in Wiener norm. It would also be interesting to examine convergence of the scheme in the L 2 norm or, more generally, Sobolev norms. Notational convention(s): C denotes the usual "variable constant", whose precise numerical value is allowed to change from one occurrence to the other.

We use the following convention for the Fourier transform f = F(f ) of an integrable function f on R n ; f (ξ) = R n f (x)e -i(x,ξ) dx, (x, ξ) being the Euclidean inner product on R n . We will routinely use the extension of the Fourier transform F to the space of tempered distributions S (R n ), where S(R n ) is the usual Schwarz-space of rapidly decreasing functions.

For s ∈ R, let L 1 s (R n ) be the space of measurable functions on R n for which [START_REF] Baxter | On the asymptotic cardinal function of the multiquadric ϕ(r) = (r 2 + c 2 ) 1/2 as c → ∞[END_REF] ||f || 1,s :=

R n (1 + |ξ|) s |f (ξ)| dξ < ∞.
We will also need the weighted L ∞ -spaces L ∞ s (R n ) of measurable functions such that [START_REF] Brummelhuis | A radial basis function scheme for option pricing in exponential Lévy models[END_REF] ||f || ∞,s := sup

x∈R n (1 + |x|) s |f (x)|. If s < 0, an element f of L ∞ s (R n ) is of polynomial growth of order at most |s|: |f (x)| ≤ C(1 + |x|) |s| on R n , with C = ||f || ∞,s .
Derivatives of functions f = f (x) on R n will be denoted by ∂ α x f (x) or by f (α) (x), α ∈ N n a multi-index. If K ∈ N and λ ∈ (0, 1], then C K,λ b (R n ) will denote the Hölder space of K-times differentiable functions on R n with bounded derivatives of all orders, such that the derivatives of order K satisfy a uniform Hölder condition on R n with exponent λ, provided with the norm Finally, x and x denote the usual floor and ceiling functions, defined as the greatest, respectively smallest integer which is less than, respectively greater than a real number x; note that x = x + 1 if x / ∈ N, while x = x = x otherwise.

A class of basis functions for interpolation on a regular grid

2.1. The Buhmann class. We introduce a large and flexible class of basis functions which is well-suited for stationary interpolation on regular grids. Since this class of functions is a slight generalisation of one introduced earlier by Buhmann [START_REF] Buhmann | Multivariate Cardinal Interpolation with Radial Basis Functions[END_REF] (called admissible in there) we will call it the Buhmann class. From the onset, we will allow non-radial basis functions, radiality not being essential for most of the theory (as is of course well known). Definition 2.1. For κ ≥ 0 and N > n we define the Buhmann class B κ,N (R n ) as the set of functions ϕ ∈ C(R n ) such that (i) ϕ is of polynomial growth of order strictly less than κ, in the sense that ϕ ∈ L ∞ -κ+ε (R n ) for some ε > 0.

(ii) (Regularity and strict positivity.) The restriction to R n \ 0 of the Fourier transform ϕ := F(ϕ) (in the sense of tempered distributions) can be identified with a function in C n+ κ +1 (R n \ 0), which we will continue to denote by ϕ, which is pointwise strictly positive: ϕ(η) > 0 for all η ∈ R n \ 0.

(iii) (Elliptic singularity at 0.) There exist positive constants c, C such that for all |α| ≤ n + κ + 1,

(3)

|∂ α η ϕ| ≤ C|η| -κ-|α| , |η| ≤ 1, while also (4) ϕ(η) ≥ c|η| -κ , |η| ≤ 1.
(iv) (Decay at infinity.) There exist positive constants

C α , |α| ≤ n + κ + 1, such that (5) |∂ α η ϕ(η)| ≤ C α |η| -N , |η| ≥ 1.
We use the term "elliptic" for condition (iii) because of the ressemblance of ( 3) and ( 4) with the ellipticity condition on symbols in pseudo-differential theory (where the singularity would be at infinity). The significance of n + κ + 1 is that this is the smallest integer which is strictly greater than n + κ. (Note that if κ / ∈ N, then n + κ + 1 = n + κ .) Conditions (ii) and (iii) for derivatives up till this order will imply polynomial decay of order n + κ of the associated Lagrange interpolation function which we will define below. Requiring higher order differentiability would not improve this rate of decay: n + κ is best possible, under condition (iii).

In some if not all of the results of this paper, strict positivity of ϕ on R n \0 could have been replaced by the weaker condition that the "periodisation" of ϕ, k ϕ(η + 2πk), be pointwise strictly positive on all of R n , as in [START_REF] Buhmann | Multivariate Cardinal Interpolation with Radial Basis Functions[END_REF]; note that by [START_REF] Chan | Adaptive Radial Basis Function Methods for Pricing Options Under Jump-Diffusion Models[END_REF] with α = 0, this series converges absolutely on R n \ Z n , given that N > n, while it can be set equal to ∞ on Z n , in view of (4). Since for most of the radial basis functions used in practice, ϕ(η) itself is already strictly positive, we have opted to impose the stronger condition, also to simplify our proofs, some of which are already fairly long.

Remarks 2.2. (i) Buhmann [START_REF] Buhmann | Multivariate Cardinal Interpolation with Radial Basis Functions[END_REF] studied stationary RBF interpolation on regular grids for a slightly more restricted class of radial basis functions. The main difference between his original class and the one of our definition 2.1 (besides, as already mentioned, Buhmann requiring strict positivity of the periodisation of ϕ instead of of ϕ itself) lies in condition (iii), where Buhmann asks that for small |η|, ϕ(η) be asymptotically equivalent to a positive multiple of |η| -κ modulo an relative error which has to be sufficiently small:

ϕ(η) = A|η| -κ (1 + h(η)) with |∂ α η h(η)| = O(|η| ε-|α| ) as η → 0 for |α| ≤ n + κ + 1,
with an ε > κ -κUnder these conditions Buhmann proved the existence of a unique Lagrange function for interpolation on Z n , constructed as an infinite linear combination of translates of ϕ, which moreover decays as |x| -κ-n at infinity. This fundamental result remains true for ϕ's in B κ,N (R n ): see theorem 2.3 below and and its proof in Appendix A. The condition that ε > κ -κ is in our treatment made unnecessary by lemma A.2.

(ii) All conditions in definition 2.1 except the first are on the Fourier transform of ϕ. One can show (cf. Appendix A) that if the Fourier transform of a polynomially increasing function ϕ satsifies (ii), (iii) and (iv), then there exists a function ϕ(x) which grows at most as max(|x| κ-n log |x|, 1) at infinity (and, slightly better, as max(|x| κ-n , 1) if κ / ∈ N) and a polynomial P (x) such that ϕ(x) = ϕ(x) + P (x). The function ϕ is unique modulo polynomials of degree κ -n. If we moreover require ϕ to have polynomial growth of order strictly less than κ, as in definition 2.1, then P (x) will be a polynomial of degree of at most κ -1 (which is κ if κ / ∈ N, and κ-1 if κ ∈ N). Note that the Fourier transform of a polynomial is a linear combination of derivatives of the delta-distriubution in 0, and therefore equals 0 on R n \ 0.

(iii) The condition that N > n will suffice for convergence of the RBF interpolants on regular grids hZ n as h → 0, but will have to be strengthened to n > N +k for convergence of the RBF schemes for solving parabolic PDEs and PIDEs which are of order k (in the space variables).

The usual examples of radial basis functions, such as the generalised multiquadrics, cubic and higher order splines, thin plate splines, inverse multiquadrics and Gaussians, are Buhmann class.

One can show that if

ϕ ∈ B κ,N (R n ) ∩ L ∞ -p (R n
), for some p ∈ N, then ϕ conditionally positive definite of order µ, where µ is the smallest integer such that 2µ > max( κ -n, p, 0) (for this it would in fact be sufficient that ϕ| R n \0 is locally integrable, satisfies (3) with α = 0 and is integrable on {|η| ≥ 1}). One can therefore, by standard RBF theory, interpolate an arbitrary function on a finite set X of points by a linear combination of translates of ϕ plus a polynomials of degree µ -1, provided X is unisolvent for such polynomials: see for example [START_REF] Buhmann | Radial Basis Functions[END_REF]. This in general involves solving a linear system of equations. The next theorem establishes the existence and main properties of a Lagrange function in terms of which the solution of the interpolation problem on Z n can be simply expressed.

Theorem 2.3. Suppose that ϕ ∈ B κ,N (R n ) with κ ≥ 0 and N > n. Then there exist coefficients c k , k ∈ Z n , such that (6) L 1 (x) := L 1 (ϕ)(x) := k∈Z n c k ϕ(x -k)
is a well-defined Lagrange function for interpolation on Z n :

L 1 (j) = δ 0j , j ∈ Z n .
The function L 1 satisfies the bound

(7) |L 1 (x)| ≤ C(1 + |x|) -κ-n , x ∈ R n ,
and its Fourier transform is given by

(8) L 1 (η) = ϕ(η) k ϕ(η + 2πk)
.

Moreover, at the points of 2πZ n , L 1 satisfies the Fix-Strang conditions:

(9) L 1 (2πk + η) = δ 0k + O(|η| κ ), η → 0.
See Appendix A for the proof.

Remarks 2.4. (i) We will write L 1 (ϕ) if we want to stress the dependence on the basis function ϕ, otherwise we will simply write L 1 . The subindex 1 in L 1 is a notational reminder that L 1 is a Lagrange function for interpolation on the standard grid Z n with width 1. For stationary RBF interpolation on the scaled grids hZ n one uses the scaled basis functions ϕ(x/h), whose associated Lagrange functions then simply are

L h (x) := L 1 (x/h). If f ∈ L ∞ -p (R n ) for some p < κ, then s h [f ](x) := j f (hj)L 1 (h -1 x -j
) is an infinite linear combination of translates of ϕ which will interpolate f on hZ n , where the series converges absolutely in view of the growth restriction on f.

(ii) One important point of the theorem is that the basis function ϕ need not decay at infinity, but is allowed to grow polynomially. A high order of growth will in fact lead to a high order convergence of the stationary RBF interpolants as h → 0, since this will translate into a strong singularity of the Fourier transform in 0, and therefore a large κ, meaning that the Fix -Strang conditions will be satisfied to a high order. The latter then implies a convergence rate of O(h κ ) in sup-norm, as shown by Buhmann (under suitable conditions on f ), see for example [START_REF] Buhmann | Radial Basis Functions[END_REF], Chapter 4, and as we will show below for the Wiener norm with an entirely different approach: see theorems 3.2, 3.4 and 3.9. Note that, contrary to ϕ, the Lagrange function L 1 will decay at infinity, as shown by [START_REF] Hon | A Radial basis function method for solving options pricing model[END_REF], and this the more rapidly the higher κ is. It is possible for L 1 (x) to have faster decay: Buhmann [START_REF] Buhmann | Multivariate Cardinal Interpolation with Radial Basis Functions[END_REF] shows that if ϕ(η) ∼ |η| -κ as η → 0 with κ ∈ 2N, then

L 1 (x) ≤ C(1 + |x|) -κ-n-ε ,
while there are examples of ϕ for which L 1 (x) decays exponentially: see [START_REF] Buhmann | Radial Basis Functions[END_REF] for details and references.

(iii) The proof of theorem 2.3 shows that the coefficients c -k are precisely the Fourier coefficients of ( k ϕ(η + 2πk) -1 . They satisfy bounds analogous to the ones satisfied by L 1 :

|c k | = O(|k| -n-κ
). This guarantees that the defining series for L 1 (x) converges absolutely, including for when κ = 0, in view of condition (i) of definition 2.1. By [START_REF] Hon | A Radial basis function method for solving options pricing model[END_REF], the Fourier transform of L 1 exists in classical sense, as an absolutely convergent integral. We also note that since the denominator of ( 8) is 2π-periodic and bounded away from 0, L 1 (η) will have the same decay as ϕ(η) as |η| → ∞. We state this as a lemma, for later reference: Lemma 2.5. There exists a constant C = C n > 0 such that for all ∈ Z n \0, [START_REF] Maz | On approximate approximations using Gaussian kernels[END_REF] max

η∈[-π,π] n |η| -κ | L 1 (η + 2π )| ≤ C| | -N .
Proof. The function k ϕ(η + 2πk) is periodic and, by the positivity and ellipticity of ϕ at 0, bounded from below by c|η| -κ for some c > 0. Hence

| L 1 (η + 2π )| = |ϕ(η + 2π )| k ϕ(η + 2πk) ≤ C|η| κ |η + 2π | -N ,
which implies [START_REF] Maz | On approximate approximations using Gaussian kernels[END_REF].

Another useful lemma clarifies the smoothness properties of L 1 :

Lemma 2.6. There exist constants C α such that for each multi-index α with |α| ≤ n + κ + 1 and all k = 0, (11)

∂ α η L 1 (η + 2πk) -δ 0k ≤ C α (1 + |k|) N |η| κ-|α| ,
for η = 0 in a neighborhood of 0. In particular, if κ > 0 then L 1 belongs to the Hölder space

C κ -1,λ b (R n ), with λ = κ -( κ -1). Note that κ -1 = κ if κ is non-integer, but that it is equal to κ -1 if κ is a positive integer, so that λ = 1 then.
Proof of lemma 2.6. This is elementary: if we let ϕ per (η) := k ϕ(η + 2πk), then applying Leibnitz's rule to the product L 1 ϕ per = ϕ yields that

(∂ α η L 1 ) ϕ per = ∂ α η ϕ - β<α α β ∂ β η L 1 ∂ α-β η ϕ per .
The estimate [START_REF] Maz | Approximate approximation[END_REF] for k = 0 now follows by induction on α, using that

∂ α η ϕ per (η + 2πk) = ∂ α η ϕ per (η) = O(|η| -κ-|α|
), together with (5) of definition 2.1 and lemma 2.5 (to start the induction). If k = 0, we use the same argument, starting from

ϕ L 1 -1 = ϕ -ϕ per ,
on observing that the right hand side is C κ +n+1 near 0, since equal to k =0 ϕ(η + 2πk). Finally, the fact that L 1 (η + 2πk) -δ 0k is O(|η| κ implies that all derivatives of order up to κ , if κ / ∈ N, or κ -1, if κ ∈ N \ 0, exist and are 0. Their continuity in 0 follows from [START_REF] Maz | Approximate approximation[END_REF].

Remark 2.7. We pause to briefly examine the differentiability of L 1 if κ ∈ N. Letting g(η) := k =0 ϕ(η + 2πk) and ψ(η) := |η| κ ϕ(η), we have that

L 1 (η) = ψ(η) ψ(η) + |η| κ g(η)
.

This shows that L 1 cannot be C κ in 0 if κ ∈ N is not even, even if ψ would be (note that then ψ(0) = 0 given that ϕ is Buhmann class). If κ ∈ 2N, then L 1 will be as smooth as ψ(η) is in 0 (and as ϕ is away from 0).

Finally, we observe that to construct numerical PDE schemes using RBF interpolation one will obviously need sufficient differentiability of L 1 . The proof of theorem 2.3 given in appendix A also yields existence and decay of derivatives of L 1 , provided N is chosen sufficiently large:

Theorem 2.8. Suppose that k ∈ N and let ϕ ∈ B κ,N (R n ) with N > n + k. Then L 1 ∈ C k (R n ). Moreover, |∂ α x L 1 (x)| = O(|x| -κ-n ) as |x| → ∞, for all |α| ≤ k.

Convergence of RBF-interpolants

As stated in the introduction, we will limit ourselves to stationary interpolation on regular grids hZ n , meaning that we let the basis function scale with the grid-size: ϕ h (x) := ϕ(x/h). The associated Lagrange function scales similarly, and the RBF interpolant s h [f ] of a given function f : R n → R can be conveniently written as [START_REF] Pettersson | Improved radial basis function methods for multi-dimensional option pricing[END_REF] s

h [f ](x) = j f (hj)L 1 x h -j .
where L 1 is the Lagrange function of theorem 2.3. Here, and below, sums over j, k, , etc. are understood to be over Z n . Note that the use of the Lagrange function eliminates the need for inverting the coefficient matrix (ϕ h (hj -hk)) j,k = (ϕ(j -k)) j,k in the standard formulation of RBF interpolation 1 . The decay at infinity of L 1 easily implies that the series [START_REF] Pettersson | Improved radial basis function methods for multi-dimensional option pricing[END_REF] converges absolutely if f ∈ L ∞ -p (R n ) for some p < κ: we will express this by saying that f is of polynomial growth of order strictly less than κ.

Throughout this section, we fix a basis function ϕ = ϕ 1 ∈ B κ,N (R n ) with κ > 0 and N > n. We will systematically work in Fourier-space, and examine convergence in Wiener norm,

||f || A := || f || 1 ,
except for the end of this section where we will also briefly examine weigthed sup-norms. Convergence in Wiener norm of course trivially implies convergence in Chebyshev or uniform norm, since ||f || ∞ ≤ ||f || A .

We begin by computing the Fourier transform of s h [f ] for Schwarz-class functions f. For sufficiently rapidly decaying functions g, let us define the function Σ h (g) [START_REF] Stein | Harmonic Analysis: Real-Variable Methods, Orthogonality and Oscillatory Integrals[END_REF] Σ h (g)(ξ) :

= k g(ξ + 2πh -1 k) L 1 (hξ).
The map Σ h will play an important rôle in what follows. We note for later use that Σ h is a contraction with respect to the L 1 -norm: indeed, by the positivity of L 1 and monotone convergence,

||Σ h (g)|| 1 ≤ k R n |g(ξ + 2πh -1 k)| L 1 (hξ) dξ = R n |g(ξ)| k L 1 (hξ + 2πk) dξ = ||g|| 1 , 1
In the present, idealized, set-up of interpolation on hZ n that coefficient matrix is infinite; in practice, one would have to truncate the matrix: |j|, |k| ≤ N (where, |j| = |j|∞ = maxν |jν |) with N ∼ h -1 , taking larger and larger sections of the matrix as h → 0. One would also have to truncate the series for L1, leading to quasi-interpolation.

since k L 1 (η + 2πk) = 1; Σ h therefore extends to a contraction on L 1 (R).

We also note that if g ∈ L 1 (R n ), then the defining series for Σ h (g) converges absolutely a.e., since

]0,π] n k |g(ξ + 2πk)|dξ = R n |g(ξ)|dξ < ∞. Lemma 3.1. If f ∈ S(R n ) then the Fourier transform of s h [f ]
, is given by the L 1 -function

(14) Σ h ( f )(ξ) := k f (ξ + 2πh -1 k) L 1 (hξ).
Proof. Since κ > 0, L 1 is integrable by theorem 2.3 and hence

s h [f ] ∈ L 1 (R n ), since ||s h [f ]|| 1 ≤ h n j |f (hj)| ||L 1 || 1 . Applying Fubini's theorem to the function (j, x) → f (hj)L 1 (h -1 x -j)e -i(x,ξ) on Z n × R n one finds s h [f ](ξ) =   j f (jh)e -ih(j,ξ)   h n L 1 (hξ) = k f (ξ + 2πh -1 k) L 1 (hξ), = Σ h ( f )(ξ), (15)
where for the second line we used the Poisson summation formula: j g(j) = k g(2πk), with g(x) := f (hx)e -ih(x,ξ) . If κ = 0, theorem 2.3 no longer guarantees that L 1 and therefore s h [f ] is integrable (though it may be under stronger conditions on ϕ, as per Buhmann's result for integer pair κ) but its Fourier transform will still exist as a tempered distribution, and will still be given by Σ h ( f ), as an easy approximation argument will show.

We can now state our first convergence theorem. Theorem 3.2. Let κ > 0. Then there exists a constant C = C(ϕ) > 0 such that for all tempered functions f for which f ∈ L 1 κ (R n ) and for all positive h ≤ 1,

(16) || f -s h [f ] || A ≤ Ch κ R n | f (ξ)| |ξ| κ dξ
Note that the integrability condition on f at infinity implies a certain smoothness: f must have continuous and bounded derivatives of order κ .

Proof. The hypothesis on f implies that f is a bounded continuous function. It follows that s h [f ] is well-defined, by [START_REF] Hon | A Radial basis function method for solving options pricing model[END_REF], and that there exists a constant C > 0 such that for all h ≤ 1,

(17) || s h [f ] || ∞ ≤ C||f || ∞ . Indeed, |s h [f ](x)| ≤ ||f || ∞ j |L 1 (h -1 x-j)|;
the right had side is h-periodic, and its sup on {|x| ≤ h/2} can be estimated by a constant times j |L 1 (j)|, which converges since κ > 0.

The Fourier transform of s h [f ] therefore exists as a temperered distribution. We show using a density argument that s h

[f ] = Σ h ( f ): since f ∈ L 1 (R n ), then there exists a sequence f ν ∈ S(R n ) such that || f ν -f || 1 → 0. Consequently Σ h ( f ν ) → Σ h (f ) in L 1
and therefore also as tempered distributions. On the other hand,

||s h [f ν ] -s h [f ]|| ∞ ≤ C||f -f ν || ∞ ≤ C|| f -f ν || 1 → 0, so s h [f ν ] → s h [f ] as tempered distributions also. Hence Σ h ( f ν ) = s h [f ν ] → s h [f ], and consequently s h [f ] = Σ h ( f ). Note that, as a consequence, s h [f ] is in A(R n ) if f is.
We now observe that since 0

≤ L 1 ≤ 1, || s h [f ] -f || 1 ≤ R n | f (ξ)|   (1 -L 1 (hξ)) + k =0 L 1 (hξ + 2πk)   dξ = 2 R n (1 -L 1 (hξ)) | f (ξ)| dξ, (18)
where we used again that the sum of translates of L 1 by elements of 2πZ n is equal to 1. Now since ϕ ∈ B κ,N (R n ), formula [START_REF] Khaliq | A parallel time stepping approach using meshfree approximations for pricing options with non-smooth payoffs[END_REF] together with (iii) of definition 2.1 implies that there exists a constant

C = C(ϕ) > 0 such that 0 ≤ 1 -L 1 (η) ≤ C|η| κ on R n , by the Fix-Strang condition in 0. Hence 1 -L 1 (hξ) ≤ Ch κ |ξ| κ , which implies (16). Remarks 3.3. (i) The theorem remains true if κ = 0, if one adds the condi- tion that f ∈ L ∞ ε (R n )
for some ε > 0, to ensure convergence of the defining series for s h [f ]. As we already noted, it may happen that the Lagrange function decays more rapidly than (1 + |x|) -n at infinity. An easy example is when ϕ is a function in S(R n ), such as a Gaussian, in which case L 1 will also be in in S(R n ), by [START_REF] Khaliq | A parallel time stepping approach using meshfree approximations for pricing options with non-smooth payoffs[END_REF]. In such cases, no further restriction on f will be necessary.

Moreover, even if the decay of L 1 cannot be improved, one can still show that if f is integrable, then the defining series for s h [f ] is summable in the sense that if for a χ ∈ S(R n ) with χ(0) = 1 we let

s ε h [f ](x) := j χ(εjh)f (hj)L 1 (h -1 x -j),
then as ε → 0, s ε h [f ] converges uniformly on R n to a continuous function whose Fourier transform is Σ h ( f ), independently of the choice of χ. To show this, observe that the Fourier transform of the left hand side is equal to (2π

) -n Σ h ( χ ε * f ), where χ ε (ξ) = ε -n χ(-εξ).
Since, by a classical theorem on convolution with approximate identities,

(2π) -n χ ε * f → f in L 1 (observing that (2π) -n R -n χ(-ξ)dξ = χ(0) = 1)
, and since Σ h is a contraction, it follows that s ε h [f ] converges in Wiener norm, and therefore in sup-norm, to the inverse Fourier transform of the, integrable, function Σ h ( f ). If we now define s h [f ] as the limit of the s ε h [f ], the estimate (16) follows as before. We in fact only need the Fourier transform of χ to be integrable, but this excludes taking for χ the characteristic function of a cube centered at 0, which would entail ordinary convergence of the series for

s h [f ](x).
The reader may of course wonder why one would want to consider the case of κ = 0 at all, since the theorem then doesn't show that s h [f ] converges to f and, as we will see in section 4, this is not true in general. The reason is that we can still have approximate approximation, in the sense that the error can be made arbitrarily small with an appropriate choice of basis function: see section 4.

(ii) The theorem generalizes to the case when f = ν is a finite Borel measure for which

|ξ| κ ∈ L 1 (R n , d|ν|): in that case, (19) || f -s h [f ] || ∞ ≤ Ch κ R n |ξ| κ d|ν|(ξ).
To show this, one first defines Σ h (ν) by duality:

if ψ ∈ S(R n ), then Σ h (ν), ψ := ν, Σ (ψ) , where Σ h (ψ) := k ψ(ξ + 2πh -1 k) L 1 (hξ + 2πk) ∈ C b (R n , and one checks that s h [f ] = Σ h (ν) as tempered distributions. Since ||Σ h (ψ)|| ∞ ≤ C||ψ|| ∞ , on account of the decay of L 1 , Σ h (ν) is a finite Borel measue.
Using again that the sum of the translates of L 1 by elements of (2π)Z n is 1, one then estimates

| Σ h (ν) -ν, ψ | = ν, Σ h (ψ) -ψ ≤ 2||ψ|| ∞ R n (1 -L 1 (hξ))d|ν (ξ),
where we can take ψ ∈ C b (R n ). It follows that the variation norm of Σ h (ν)-ν is bounded by Ch κ , which implies (19).

We next observe that the right hand side of (16) still makes sense for certain f having a non-integrable singularity at 0. Allowing such singularities means allowing f 's which grow at a certain polynomial rate, and we can for such f prove the following approximation theorem. Theorem 3.4. Let f be a tempered function on R n such that |f (x)| ≤ C(1 + |x|) p for some p < κ, and such that

(20) f | R n \0 ∈ L 1 (R n \ 0, |ξ| κ dξ). Then s h [f ] -f is in L 1 (R n ), and
(21) ||s h [f ] -f || A ≤ Ch κ R n | f (ξ)| |ξ| κ dξ.
Proof. Equation (20) means that, away from 0, the tempered distribution f can be identified with a locally integrable function which is integrable with respect to the weight |ξ| κ . We first check that s h [f ] is a tempered distribution: this is a consequence of the estimate

(22) || s h [f ] || ∞,-p ≤ C|| f || ∞,-p , p ≥ 0.
To prove this, note that f → s h [f ] commutes with translations by elements of hZ n : if k ∈ Z n , then

s h [f ](x -kh) = s h [f (• -hk)](x). Let | • | = | • | ∞ be the ∞ -norm on R n . If |x| ≤ h/2 and f ∈ L ∞ -p (R n ) with p < κ, then |s h [f ](x)| ≤ ||f || ∞,-p   1 + |j|≥1 (1 + h|j|) p (1 + |h -1 x -j|) κ+n   ≤ C||f || ∞,-p , since |h -1 x -j| ≥ |j|/2 if |j| ≥ 1. Next, if |x -hk| ≤ h/2 with k ∈ Z n , then |s h [f ](x)| ≤ C||f (• -hk)|| ∞,-p ≤ C(1 + h|k|) p ||f || ∞,-p , which implies (22). The next lemma identifies the Fourier transform if s h [f ]. Lemma 3.5. Suppose that |f (x)| ≤ C(1 + |x|) p for some p < κ and that f | R\0 ∈ L 1 (R n \ 0, min(|ξ| κ , 1)dξ). Then the tempered distribution s h [f ] -f can be identified with the function (23) L 1 (hξ) -1 f (ξ) + k =0 f (ξ + 2πh -1 k) L 1 (hξ), ξ = 0, which is in L 1 (R n ).
The proof of the lemma involves extending f to a continuous linear functional on the Hölder spaces

C κ -1,λ b (R n ) with λ = κ -( κ -1) (so that λ = κ -κ if κ /
∈ N, and λ = 1 otherwise), and using this to define Σ h ( f ) as a tempered distribution. In order not to interrupt the flow of the argument with distribution-theoretical technicalities, we postpone the proof to Appendix B. Note that the individual terms of (23) are integrable on account of the Fix-Strang conditions satisfied by L 1 , and that the L 1 -norm of (23) can be bounded by the L 1 -norm of 2( L 1 (hξ) -1)| f (ξ)|, using once more that the sum of translates of L 1 by elements of (2π)Z n is identically equal to one.

The lemma implies the estimate (18), and the theorem follows as before.

Example 3.6.

If the function f on R n satisfies (24) |∂ α x f (x)| ≤ C α (1 + |x|) p-|α| , |α| ≤ p + n + 1, with p ≥ 0 then one can show that f | R n \0 ∈ C(R n \ 0), and that | f (ξ)| ≤ C|ξ| -p-n near 0 while f (ξ) = O(|ξ| -p -n-1
) at infinity: if (24) holds for all α, this follows for example from Stein [START_REF] Stein | Harmonic Analysis: Real-Variable Methods, Orthogonality and Oscillatory Integrals[END_REF], proposition 1 of Chapter VI.

Examination of the proof shows that we only need the number of derivatives indicated. It follows that |ξ| κ f (ξ) is integrable if p < κ and theorem 3.4 therefore applies to such functions.

Remark 3.7. If κ / ∈ N then theorem 3.4 remains true if f | R n \0 can be identified with a Borel measure ν on R n \ 0 for which |ξ| κ ∈ L 1 (R n , d|ν|).
The estimate (21) then generalises to an estimate for the variation norm of Σ( f ) -f (as measure on R n ) which then implies a uniform estimate

(25) ||s h [f ] -f || ∞ ≤ Ch κ R n |ξ| κ d|ν|(ξ).
If one is satisfied with a slower rate of convergence, the growth condition at infinity on f can be weakened accordingly: Corollary 3.8. Let k ≤ κ and suppose that f is a tempered function with grows at a polynomial rate strictly less than κ, such that for all h ≤ 1,

f | R n \0 ∈ L 1 (R n , (|ξ| k ∧ |ξ| κ )dξ). Then || s h [f ] -f || 1 ≤ C h k R n | f (ξ)| (|ξ| k ∧ |ξ| κ ) dξ Proof. The hypotheses on f cetainly imply that f | R n ∈ L 1 (R n , min(|ξ| κ , 1)dξ),
so we can apply lemma 3.5. In particular, the estimate (18) still holds. We now split this integral into three parts over the ranges h|ξ| ≤ h, h ≤ h|ξ| ≤ 1 qnd h|ξ| ≥ 1, and use the Fix -Strang condition in 0,

R n 1 -L 1 (hξ) | f (ξ)| dξ ≤ C |hξ|≤h (h|ξ|) κ | f (ξ)| dξ + h<|hξ|≤1 (h|ξ|) κ | f (ξ)| dξ + |hξ|>1 | f (ξ)| dξ ≤ C h κ |ξ|≤1 |ξ| κ | f (ξ)| dξ + h k 1≤|ξ|≤h -1 |ξ| k | f (ξ)| dξ + h k |ξ|≥h -1 | f (ξ)| |ξ| k dξ ≤ Ch k R n | f (ξ)| |ξ| k ∧ |ξ| κ dξ,
where we used the trivial bound |η| κ ≤ |η| k if |η| ≤ 1, but only for the second integral.

The corollary shows that there is an interplay between the order of convergence of the RBF interpolator and the smoothness of the function which is interpolated, as quantified by the decay of f (ξ) at infinity. The singularity of f (ξ) at 0 can be of order |ξ| -κ-n+ε , as before, allowing a polynomial growth of f (x) of order less than κ.

Although our focus in this paper is on convergence in the Wiener norm, we want to note that we can allow more general more general distributional f which are not necessarily functions or measures on R \ 0 if we replace the Wiener norm with weighted sup-norms. We give an example which can be deduced from theorem 3.2 by an approximation argument. Recall that

||f || ∞,-p = sup R n (1 + |x|) -p |f (x)|.
Theorem 3.9. Let p ∈ N, p < κ and let f be a tempered function on R n whose Fourier transform can be written as

(26) f = |α|≤p ∂ α ξ ν α , with ν α complex Borel measures on R n satisfying (27) R n (1 + |η|) κ d|ν α |(η) < ∞. Then (28) ||s h [f ] -f || ∞,-p ≤ C f h κ ,
where we can take

(29) C f = C • |α|≤p ||(1 + |η|) κ || L 1 (|ν α| ) ,
for some positive constant C independent of f.

Proof. The hypothesis on f imply that f is continuous and of polynomial growth of order at most p:

||f || ∞,-p < ∞. Let χ R (x) := χ(x/R), where χ = χ 1 ∈ C ∞ c (R n ), 0 ≤ χ ≤ 1, χ(x) = 1 on B(0, 1
). We will apply theorem 3.2 to χ R f and for that purpose first bound || χ R f || 1,κ . Lemma 3.10. For f as in theorem 3.9 and R ≥ 1,

(30) || χ R f || 1,κ ≤ C f R p , with C f as in (29). Proof. Since f χ R = (2π) -n f * χ R = (2π) -n α (-1) |α| ν α * ∂ α ξ χ R , we find that (writing χ (α) for ∂ α ξ χ) (2π) n || χ R f || 1,κ ≤ |α|≤p R n+|α| R n R n | χ (α) (R(ξ -η))|(1 + |ξ|) κ d|ν α |(η)dξ = |α|≤p R |α| R n R n | χ (α) (ζ)|(1 + |η + R -1 ζ|) κ d|ν α |(η)dζ.
The lemma follows by observing that (1+|η+R -1 ζ|) ≤ (1+|η|)(1+R -1 |ζ|) ≤ (1 + |η|)(1 + |ζ|) and using the rapid decay of χ.

Proof of theorem 3.9 (continued). By theorem 3.2,

||s h [f χ R ] -f χ R || ∞ ≤ C f R p h κ . We next compare s h [f ] with s h [χ R f ]: since χ R (x) = 1 for |x| ≤ R, |s h [f ](x) -s h (χ R f )(x)| = h|j|≥R |(f (hj) -χ R (hj)f (hj))L 1 (h -1 x -j)| ≤ 2 h|j|≥R |f (hj)| |L 1 (h -1 x -j)|. Now if |x| ≤ R/2, then |hj| ≥ R implies that |x -hj| ≥ |hj|/2 so that |h -1 x -j| ≥ |j|/2. Hence, by the decay at infinity of L 1 , sup |x|≤R/2 h|j|≥R |f (hj)| L 1 (h -1 x -j) ≤ ||f || ∞,-p h p h|j|≥R |j| p-κ-n ≤ C||f || ∞,-p h κ R p-κ ,
since we can for example bound the sum by a constant times |y|≥R/h |y| p-κ-n dy (recall that p < κ).

Writing s h [f ] -f = s h [f ] -s h [χ R f ] + s h [χ R f ] -χ R f + χ R f -f , these estimates imply that R -p sup |x|≤R/2 |s h [f ](x) -f (x)| ≤ C f h κ , for R ≥ 1, which implies the theorem.
.

Examples of functions f which satisify the hypothesis of theorem 3.9 are the inverse Fourier transforms of compactly supported distributions of order p < κ since, by a structure theorem going back to Laurent Schwartz, such a compactly supported distribution can be written in the form (26)).

Approximate approximation

It is easy to show that the approximation error in the Wiener norm cannot go to 0 faster than

h κ : if f ∈ L 1 (R n ) has compact support, then the supports of f (• + 2πk/h) will be disjoint if h is sufficiently small. It follows that || s h [f ] -f || 1 = R n | f (ξ)| L 1 (hξ) -1|dξ + k =0 R n | f (ξ + 2πk/h)| L 1 (hξ)dξ = R n | f (ξ)|(1 -L 1 (hξ))dξ + k =0 R n | f (ξ)| L 1 (hξ + 2πk)dξ = 2 R n | f (ξ)| 1 -L 1 (hξ) dξ, since k L 1 (η + 2πk) = 1. If we define (31) l κ := l κ (ϕ) := 2 lim inf η→0 1 -L 1 (η) |η| κ .
then Fatou's lemma implies that

(32) lim inf h→0 h -κ ||s h [f ] -f || A ≥ l κ R n |ξ| κ | f (ξ)| dξ.
We will see below that l κ > 0. The inequality (32) remains valid if f is not compactly supported but decays sufficiently fast at infinity: see theorem 4.3 below. Here we first examine the corresponding upper bound.

As we just noted, one cannot in general do better that O(h κ ) for the approximation error. However, for suitable basis functions ϕ and for f (ξ) which decay sufficiently fast at infinity we may observe a higher apparent rate of convergence for h's which are small but not too small. If

ϕ ∈ B κ,N (R n ), we let 2 (33) l κ := l κ (ϕ)) := 2 lim sup |η|→0 1 -L 1 (η) |η| κ .
A slight modification of the proof of theorems 3.2 and 3.4 then gives the following more precise estimate for the approximation error. It is convenient to introduce the homogeneous version of the space L 1 s (R n ):

(34)

• L 1 s (R n ) = g : R n → C meas. : ||g|| • 1,s := R n |g(ξ)| |ξ| s dξ < ∞ .
With this notation, the hypothesis on f in theorem 3.4 can be stated more briefly as

f | R n \0 ∈ • L 1 κ (R n ) (interpreting f | R n \0 as an a.e. defined function on R n ). Note that if s ≥ 0, then L 1 s (R n ) = • L 1 s (R n ) ∩ L 1 (R n ). Theorem 4.1. Let ϕ ∈ B κ,N (R n
) with κ ≥ 0 and N > n and let s > κ, and suppose that f ∈ L 1 s (R n ). Then there exists for each ε > 0, a constant C ε such that

(35) ||s h [f ] -f || A ≤ (l κ (ϕ) + ε)h κ || f || • 1,κ + C ε h s || f || • 1,s . More generally, this inequality holds if f ∈ L ∞ -p (R n ) for some p < κ such that f | R n \0 ∈ • L 1 κ (R n ) ∩ • L 1 s (R n ) = L 1 (R n , max (|ξ| κ , |ξ| s )) for some s > κ.
The theorem implies that if l κ (ϕ) is very small, and f ∈ L 1 s (R n ) with s > κ then the rate of convergence for small, but not too small h's will at first appear to be h s h κ , up to the point that the first term dominates and the error saturates at a level comparable to l κ (ϕ)h κ . This is the phenomenon of approximate approximation which was discovered by Maz'ya [START_REF] Maz'ya | Approximate approximations[END_REF] in the context of quasi-interpolation: see also Maz'ya and Schmidt [START_REF] Maz | Approximate approximation[END_REF]. The quasiinterpolants these authors consider are, in our notation, j f (jh)ϕ h (x-jh) with ϕ(x) of the form φ(x/c), where c is a shape parameter: see also below. Such quasi-interpolants will not converge to f (x), but it is shown in [START_REF] Maz | Approximate approximation[END_REF] that if φ is smooth, satisfies certain moment conditions and decays sufficiently rapidly at infinity, and if f has bounded derivatives up till order L, then by choosing c sufficiently large one can achieve an apparent order of convergence of h L up to a small saturation error which goes to 0 as c tends to infinity. This should be compared with theorem 4.1 if κ = 0, in which case there will also be no actual convergence and where the required smoothness of f is formulated in terms of its Fourier transform. Of course, this theorem concerns the exact interpolants instead of the quasi-interpolants. We will encounter similar approximate approximation phenomena when studying convergence rates of RBF schemes in sections 5 and 6 below.

Proof of theorem 4.1. It suffices to bound ||(1 -L 1 (hξ)) f (ξ)|| 1 . Let l := l κ (ϕ). Then if ε > 0, there exists a ρ(ε) > 0 such that if h|ξ| < ρ(ε), then 0 ≤ 1 -L 1 (hξ) ≤ 1 2 (l + ε)h κ |ξ| κ , and ||(1 -L 1 (hξ)) f (ξ)|| 1 ≤ |hξ|≤ρ(ε) (1 -L 1 (hξ))| f (ξ)| dξ + 2 |hξ|≥ρ(ε) | f (ξ)| dξ ≤ 1 2 (l + ε)h κ |ξ|≤ρ(ε)/h |ξ| κ | f (ξ)| dξ + 2ρ(ε) -s h s |ξ|>ρ(ε)/h | f (ξ)| |ξ| s dξ,
which implies the theorem for both of the cases considered.

Corollary 4.2. If f satisfies the conditions of theorem 4.1, then

(36) lim sup h→0 h -κ ||s h [f ] -f || A ≤ l κ (ϕ) R n |ξ| κ | f (ξ)| dξ.
The next theorem complements this upper bound by the lower bound (32) when f is not necessarily compactly supported.

l κ (ϕ) R n |ξ| κ | f (ξ)|dξ ≤ lim inf h→0 h -κ ||s h [f ] -f || A ≤ lim sup h→0 h -κ ||s h [f ] -f || A ≤ l κ (ϕ) R n |ξ| κ | f (ξ)|dξ.
Proof. We only need to establish the lower bound.

If |ξ| ∞ = max j |ξ j | is the ∞ -norm on R n , let Q h = {ξ ∈ R n : |ξ| ∞ ≤ π/h} = [-π/h, π/h] n ,
the cube centered at 0 with sides 2π/h, and let

Q h ( ) = h -1 + Q h . Then || s h [f ] -f || 1 = Q h ( ) k L 1 (hξ) -δ 0,k f (ξ + 2πk/h) dξ = Q h k L 1 (hξ + 2π ) -δ 0,k f (ξ + 2π(k + )/h) dξ so that || s h [f ] -f || 1 ≥ Q h L 1 (hξ + 2π ) -δ 0,-f (ξ) dξ - Q h k =- L 1 (hξ + 2π ) -δ 0,-k | f (ξ + 2π(k + )/h)|dξ. ( 37
)
The double sum in the second line can be bounded by

k =-,0 Q h L 1 (hξ + 2π ) f (ξ + 2π(k + )/h) dξ + =0 Q h L 1 (hξ + 2π ) -1 f (ξ + 2π(k + )/h) dξ ≤ C (1 + | |) N + 2 |ξ|∞≥π/h | f (ξ)| dξ ≤ Ch s R n f (ξ)| |ξ| s dξ,
where we used that sup

Q h | L 1 (hξ + 2π )| = sup η∈Q 1 L 1 (η + 2π ) ≤ C (1 + | |) N .
The first line of (37), on account of L 1 taking values in [0, 1], equals

Q h   (1 -L 1 (hξ) + =0 L 1 (hξ + 2π )   | f (ξ)|dξ = 2 R n (1-L 1 (hξ))| f |1 Q h dξ,
where 1 Q h is the indicator function of Q h . The lower bound now follows once more by Fatou's lemma and the definition of l κ (ϕ).

The next proposition gives a simple explicit formula for l κ and l κ :

Proposition 4.4. For ϕ ∈ B κ,N (R n ) with κ ≥ 0 and N > n, let A = A(ϕ) := lim inf η→0 |η| κ ϕ(η) and A := A(ϕ) := lim sup η→0 |η| κ ϕ(η). Then if κ > 0, (38) l κ (ϕ) = 2 A k =0 ϕ(2πk), l κ (ϕ) = 2 A k =0 ϕ(2πk), while if κ = 0, ( 39
) l 0 (ϕ) = 2 k =0 ϕ(2πk) A + k =0 ϕ(2πk) , l 0 (ϕ) = 2 k =0 ϕ(2πk) A + k =0 ϕ(2πk) .
Note that A(ϕ) > 0, and that the series in these formulas converges absolutely.

Proof.

If L 1 = L 1 (ϕ) is the Lagrange function associated to ϕ, then 0 ≤ 1 -L 1 (η) = k =0 ϕ(η + 2πk) k ϕ(η + 2πk) . If we let g(η) := k =0 ϕ(η + 2πk), then g is continuous (even C κ +n+1 ) in a neighborhood of 0. Since 1 -L 1 (η) |η| κ = g(η) |η| κ ϕ(η) + |η| κ g(η) , (
lim h→0 h -κ ||s h [f ] -f || A = l κ (ϕ) ||f || • 1,κ , (40)
for f as in theorem 4.1 with s > κ.

We can often construct basis functions with small l κ (ϕ) by introducing a socalled shape-parameter c and taking ϕ of the form ϕ(x) = φ(x/c) := φ c (x) with c large, for suitable φ ∈ B κ,N (R n ):

Proposition 4.6. Suppose that φ ∈ B κ,N (R n ) with κ ≥ 0 and N > max(κ, n). Then lim c→∞ l κ (φ c ) = 0. Proof. Since φ c (η) = c n φ(cη), it follows that A(φ c ) = c n-κ A(φ)
, and therefore, by (38), if κ > 0,

l κ (φ c ) = 2 c κ A(φ) k =0 φ(2πck) ≤ C c κ-N k =0 |k| -N ,
which tends to 0 as c → ∞ under the stated conditions on κ. The case of κ = 0 ifollows by observing that

l 0 (φ c ) ≤ 2 A(φ c ) k =0 φ c (2πk),
and proceeding as before.

Examples of basis functions φ which satisfy the conditions of the corollary are the (generalized) multiquadrics, whose Fourier transforms decay exponentially at infinity, but none of the homogeneous basis functions, since for these κ = N : see examples 5.13 below for a more extended discussion. In fact, for a multiquadric, φ(ξ) decays expontially at infinity, and l κ (c) will decay exponentially in c.

5.

Convergence of stationary RBF schemes for PDE: the case of the heat equation 5.

1. An RBF scheme for the heat equation. We introduce an RBF scheme for the Cauchy problem for the classical heat equation, (41)

∂ t u(x, t) = ∆u(x, t), x ∈ R n , t > 0 u(x, 0) = f (x), ∆ = n j=1 ∂ 2
x j being the Laplace operator, and examine its convergence. The scheme is a variant of the classical method of lines, and looks for approximate solutions u h of the form

(42) u h (x, t) = k∈Z n c k (t; h)L 1 (h -1 x -k),
where the c k (•; h) : [0, ∞) → R are differentiable functions. Here, L 1 is the Lagrange interpolation function of theorem 2.3, associated to a given basis function ϕ ∈ B κ,N (R n ) with N > n + 2 which we fix in this section.

The coefficients c k (t; h) of u h are determined by requiring that u h solve (41) exactly in the points of hZ n :

∂ t u h (hj, t) = ∆u h (jh, t), ∀j ∈ Z n ,
while u h (x, 0) is taken to be equal to s h [f ](x), the RBF interpolant of f. This leads to the following initial value problem for the coefficients c j (t; h):

(43)    dc j dt (t; h) = h -2 k ∆L 1 (j -k)c k (t; h) c j (0; h) = f (jh).
Since this is an infinite system of ODEs we first discuss existence and uniqueness of solutions in suitable function spaces.

For s ∈ R, let ∞ s := ∞ s (Z n ) := {(c j ) j∈Z n : ||c|| ∞,s := sup j (1 + |j|) s |c j | < ∞}.
It follows from theorem 2.8 that the convolution operator

A := A L : (c j ) j → k ∆L 1 (j -k)c k j , is a bounded operator on ∞ -p if 0 ≤ p < κ. Indeed, (1 + |j|) -p k ∆L 1 (j -k)c k ≤ k (1 + |j|) -p |(1 + |k|) s |∆L 1 (j -k)| ||c|| ∞,-p ≤ k (1 + |j -k|) p |∆L 1 (j -k)| ||c|| ∞,-p , using that (1 + |k|) ≤ (1 + |j -k|)(1 + |j|).
The sum of the series on the right is independent of j and finite if p < κ, by theorem 2.8. The system (43), which can be written as dc/dt = h -2 A L (c(t)) and has a unique solution which is given by c(t) = e h -2 tA L (c(0)).

If for c ∈ ∞ -p we define (with some abuse of notation)

s h [c](x) := j∈Z n c j L 1 (h -1 x -j), then s h : c → s h [c] is a bounded linear operator from ∞ -p → L ∞ -p (R) if 0 ≤ p < κ. Indeed, using the decay of L 1 , ||s h [c]|| ∞,-p ||c|| ∞,-p ≤ sup x∈R n (1 + |x|) -p j (1 + |j|) p (1 + |h -1 x -j|) κ+n = sup y∈R n (1 + |hy|) -p j (1 + |j|) p (1 + |y -j|) κ+n ≤ sup y∈R n 1 + |y|) 1 + h|y| p j (1 + |y -j|) p (1 + |y -j|) κ+n .
The sum on the right converges and defines a 1-periodic continuous function on R n which is therefore uniformly bounded, while the factor in front can be estimated by max (

1, h -n ). If f ∈ L ∞ -p (R n ), we can in particular take c(0) = f | hZ n , and (44)
u h [f ](x, t) := s h e h -2 tA L (f | hZ n ) (x),
is the unique function (42) whose coefficients satisfy (43). We then the following lemma:

Lemma 5.1. If p < κ and f ∈ L ∞ -p (R n ) then there is a unique function u h = u h [f ] ∈ C 1 [0, ∞); L ∞ -p (R n ) satisfying (42) and (43) and f → u h [f ](•, t) is a bounded linear map on L ∞ -p (R).
In particular, for each fixed t, u h (x, t) has tempered growth in x, and thus possesses a well-defined Fourier transform, which we will study next.

G(η) := G ϕ (η) := k |η + 2πk| 2 L 1 (η + 2πk) (45) = k |η + 2πk| 2 ϕ(η + 2πk) k ϕ(η + 2πk)
where the series converges, by theorem 2.8.

Lemma 5.2. Let ϕ ∈ B κ,N (R) with N > n + p and κ > 0. If f ∈ L 1 (R n ), then (46) u h (ξ) = e -th -2 G(hξ) s h [f ](ξ).
Proof. Let us first assume that f ∈ S(R n ) is a rapidly decreasing function.

Then f | hZ n ∈ s≥0 ∞ s and it follows from the proof of lemma 5.1 that (c j (t; h)) j ∈ s≥0 ∞ s . The Fourier transform of u h is given by u h (ξ, t) = h n L 1 (hξ) γ h (ξ, t), where γ h (ξ, t) := j∈Z c j (t; h)e -ih(j,ξ) , the sum being absolutely convergent, and (43) implies that

∂ t γ h (ξ, t) = h -2   j ∆L 1 (j)e -ih(j,ξ)   γ h (ξ, t) = h -2 k ∆L 1 (hξ + 2πk) γ h (ξ, t) = -h -2 G(hξ)γ h (ξ, t),
where the second line follows from the Poisson summation formula, whose application is justified by the decay at infinity of ∆L 1 and its Fourier transform. Hence u h satisfies the same ODE, ∂ t u h (ξ, t) = -h -2 G(hξ) u h (ξ, t) which, together with the initial condition, u h (x, 0) = s h [f ](x) implies (68).

If f ∈ L 1 (R n ), (68) follows by a standard approximation argument: if 1 and therefore e -h -2 tG(hξ) Σ( f ν )(ξ) → e -h -2 tG(hξ) Σ( f (ξ)) also, since G is non-negative, and hence as tempered distributions.

f ν → f in L 1 with f ν rapidly deceasing, then f → f ν in L ∞ , so by lemma 5.1, u h [f ν ](•, t) → u h [f ](•, t) in sup-norm also, since κ > 0. Hence their Fourier transforms converge in S (R n ). On the other hand, s h [f ν ] = Σ( f ν ) → Σ( f ) in L
The following proposition lists some useful properties of G. Proposition 5.3. Suppose that ϕ 1 ∈ B κ,N with N > n + 2 and let G := G ϕ be defined by (45). Then (i) G is a positive 2π-periodic function, and

G(η) = 0 iff η ∈ 2πZ n . (ii) If κ > 2, then G(η) = |η| 2 + O(|η| κ ) in a neighborhood of η = 0. (iii) G belongs to the Hölder space C κ -1,λ b (R n ) with λ = κ -( κ -1).
Proof. (i) The periodicity is obvious and the positivity of G is an immediate consequence of the positivity of ϕ and therefore of L 1 . Next, G(η) = 0 iff |η +2πk| 2 L 1 (η +2πk) = 0 for all k. Since L 1 is non-zero outside of (2π)Z n \0, this implies that η ∈ (2π)Z n . Conversely, any such η is a zero, given that L 1 (2πk) = δ 0k .

To prove (ii), write

(47) G(η) -|η| 2 = |η| 2 ( L 1 (η) -1) + k =0 |η + 2πk| 2 L 1 (η + 2πk).
The first term on the right is O(|η| κ+2 ) by the Fix-Strang condition in 0 (cf. theorem 2.3), while the second can be estimated by C|η| κ , where we used [START_REF] Maz | On approximate approximations using Gaussian kernels[END_REF] and N > n + 2. Finally, (iii) follows from lemma 2.6.

Property (iii) allows us to extend lemma 5.2 to functions of polynomial growth: compare lemma 3.5.

Lemma 5.4. Suppose that f ∈ L ∞ -p (R n ) for some p < κ such that f | R n \0 ∈ L 1 (R n , (|ξ| κ ∧ 1)dξ) .
Then the identity (68) holds in the sense of distributions. Moreover, u h [f ] -u can be identified with the function

(48) e -th -2 G(hξ) s h [f ](ξ) -f (ξ) + e -t(h -2 G(hξ)-|ξ| 2 -1 e -t|ξ| 2 f (ξ), which is integrable on R n .
Here, and below, f without argument will indicate the distribution, and f (ξ) the function with which it can be identified on R n \ 0.

Proof. We just clarify the statement of the lemma, and refer to Appendix B for the detailed proof, which uses elements of the proof of lemma 3.5. The proof of that lemma shows that s h

[f ] = Σ h ( f ) extends to a continuous linear functional on C κ -1,λ b (R n ).

Since (i) and (iii) of proposition 5.3 imply that the function e

-h -2 tG(h•) is in C κ -1,λ b (R n ), its product with Σ h ( f ) is well-defined as an element of the dual of C κ -1,λ b (R n ).
We can now show convergence in Wiener norm of the u h to the solution of the Cauchy problem (41). It is convenient to introduce the weighted

L 1 -spaces L 1 (R n ) k,κ , with norm (49) ||g|| k,κ := R n |g(ξ)| (|ξ| k ∧ |ξ| κ )dξ.
These spaces decrease with k for k ≤ κ; in particular,

L 1 κ (R n ) = L 1 κ,κ (R n ) ⊂ L 1 k,κ (R n ) if k ≤ κ. Theorem 5.5. Let ϕ ∈ B κ,N (R n ) with N > n + 2 and κ > 2 and suppose that f ∈ L ∞ -p (R n ) for some p < κ such that f | R n \0 ∈ L 1 κ-2,κ (R n ) Let u h := u h [f ]
and let u be the solution to the Cauchy problem (41) with initial value f. Then there exists a constant C = C ϕ independent of h and f such that

(50) ||u h (•, t) -u(•, t)|| A ≤ C(1 + t) || f || κ-2,κ h κ-2 ,
for 0 < h ≤ 1, say. In particular, u h converges to u in sup-norm at a rate of h κ-2 .

Proof. Note that the conditions on f are weaker than those of theorems 3.2 and 3.4. Indeed, we will be applying corollary 3.8 with k = κ -2. By lemma 5.4, we can estimate || u h (ξ, t) -u(ξ, t)|| 1 by

(51) e -h -2 tG(hξ) s h [f ] -f 1 + (e -h -2 tG(hξ) -e -tξ 2 ) f 1 .
By the positivity of G, the first term can be bounded by || s h [f ] -f || 1 which can be estimated using corollary 3.8. To bound the second term, we write

e -h -2 tG(hξ) -e -t|ξ| 2 = e -t|ξ| 2 e -h -2 t(G(hξ)-|hξ| 2 ) -1 ,
and use the the inequality |e x -1| ≤ |x|e max(Rex,0) together with proposition 5.3(ii) to bound this by

Cth κ-2 |ξ| κ e -t|ξ| 2 +Ch κ-2 t|ξ| κ ≤ Cth κ-2 |ξ| κ e -1 2 t|ξ| 2 , if |hξ| ≤ r with r sufficiently small: |ξ| 2 -Ch κ-2 |ξ| κ = h -2 (|hξ| 2 -h κ |ξ| κ ) ≥ 1 2 h -2 |hξ| 2 = 1 2 |ξ| 2 if h|ξ| ≤ (2C) -1/(κ-2) =: r.
We now split the second integral of (51) into an integral over h|ξ| ≤ r and one over the complement. Then

h|ξ|≤r e -h -2 tG(hξ) -e -t|ξ| 2 | f (ξ)| dξ (52) ≤ C h κ-2 |ξ|≤rh -1 t|ξ| κ | f (ξ)|e -1 2 t|ξ| 2 dξ ≤ Ch κ-2 |ξ|≤1 t|ξ| κ | f (ξ)|dξ + sup z |z| 2 e -1 2 |z| 2 1≤|ξ|≤r/h |ξ| κ-2 | f (ξ)| dξ = C(t + 1) h κ-2 || f || κ-2,κ .
Since the integral over |ξ| ≥ rh -1 can be bounded by

|ξ|≥rh -1 e -h -2 tG(hξ) -e -t|ξ| 2 | f (ξ)| dξ ≤ 2r -(κ-2) h κ-2 |ξ|≥rh -1 |ξ| κ-2 | f (ξ)| dξ ≤ Ch κ-2 || f || κ-2,κ ,
if r/h ≥ 1 or h ≤ r, the theorem follows.

Remarks 5.6. (i) If we strengthen the hypothesis on

f to f | R n \0 ∈ • L 1 κ-2 (R n ), then the proof gives an error bound of Ch κ-2 || f || • κ-2 with a constant C which is independent of t.
(ii) The estimate for the integral over |ξ| ≥ r/h may seem quite rough, but note that since h -2 G(hξ) is 2π/h-periodic and equal to 0 in points of 2πh -1 Z n , e -h -2 G(hξ) -e -t|ξ| 2 can get arbitrarily close to 1 on this set. It is not difficult to verify that h κ-2 is the exact order of approximation if κ > 2, and that the scheme does not converge if κ = 2. Let (53)

g κ = g κ (ϕ) := lim inf η→0 G ϕ (η) -|η| 2 |η| κ .
It will follow from proposition 5.11 below that g κ > 0 if ϕ is Buhmann class.

Theorem 5.7. Let f ∈ L ∞ -p (R n ) for some p < κ such that f | R n \0 ∈ L 1 k,κ (R n ) for some k ∈ (κ -2, κ]. Then if κ > 2, (54) lim inf h→0 h -κ+2 ||u h (•, t) -u(•, t)|| A ≥ g κ t R n |ξ| κ | f (ξ)|e -t|ξ| 2 dξ, while if κ = 2, (55) lim inf h→0 ||u h -u|| A ≥ R n 1 -e -g 2 t|ξ| 2 e -t|ξ| 2 | f (ξ)| dξ. Proof. Since || s h [f ] -f || 1 ≤ C f h k ,
the first line of the proof of theorem 5.5 together with Fatou's lemma implies that

lim inf h→0 h -κ+2 || u h (•, t)-u(•, t)|| 1 ≥ R n lim inf h→0 h -κ+2 e -h -2 tG(hξ) -e -t|ξ| 2 | f (ξ)| dξ.
Let R(η); = G(η) -|η| 2 . By the mean value theorem,

e -h -2 tG(hξ) -e -t|ξ| 2 = e -h -2 tR(hξ) -1 e -t|ξ| 2 = -h -2 tR(hξ)e ζ hξ,
h -κ R(hξ) = g κ |ξ| κ , (54) follows
. If κ = 2, then e -h -2 tR(hξ) -1 e -t|ξ| 2 ≥ 1 -e -h -2 t|R(hξ)| e -t|ξ| 2 ,
which implies (55), since lim inf h→0 h -2 R(hξ) = g 2 |ξ| 2 .

5.3.

Approximate approximation properties of the scheme. As we have just seen, our RBF scheme for the heat equation does not converge if κ = 2, which is for example the case when our basis function is the Hardy multiquadric on R. It turns out that in such cases we can still achieve an arbitrarily small absolute error by a judicious choice of the basis function ϕ, e.g. by introducing a shape parameter. This is again an approximate approximation phenomenon of the type encountered in section 4, and which if κ > 2 will take the form of a higher apparent rate of convergence, up till a certain threshold h 0 , for u h for initial conditions f whose Fourier transform decay sufficiently rapidly at infinity. We start with the case of κ = 2, where we have the following refinement of theorem 5.5. In all of this subsection, we let ϕ be a function in B 2,N (R n ) with N > n + 2 and κ ≥ 2, and f a function satisfying the conditions of lemma 5.4.

Theorem 5.8. Suppose that ϕ ∈ B 2,N (R n ), N > n + 2, is such that (56) g 2 := g 2 (ϕ) := lim sup η→0 G ϕ (η) -|η| 2 |η| 2 < 1.
Let 0 < k ≤ 2. Then there exists for all γ with g 2 < γ < 1 a constant C γ > 0 such that

(57) ||u h (•, t) -u(•, t)|| A ≤ e -1 γ 1 -γ + C γ h k R n | f (ξ)| max(1, |ξ| k )dξ.
3 If h sufficiently small, then h|ξ| ≤ 1 and therefore |h -2 R(hξ)| ≤ Ch κ-2 |ξ| κ .

Taking γ close to g 2 , we see that if g 2 1, then for small but not too small h's the second term on the right will dominate, and the scheme will have an apparent convergence rate of k, which can be as big as 2, until the error saturates at a level comparable to g 2 when h becomes too smallcompare with the discussion after theorem 4.1. Also, if we first let h → 0 and then γ → g 2 , we see that

lim sup h→0 ||u h (•, t) -u(•, t)|| A ≤ e -1 g 2 1 -g 2 R n | f (ξ)| max(1, |ξ| k )dξ.
We will see below that g 2 can often be made arbitrarily small by introducing a shape parameter in the basis funcion ϕ.

Proof. For a γ as in the statement of the theorem there exists a ρ = ρ(γ) with c > 0 such that

(58) max |η|≤ρ |G(η) -|η| 2 | ≤ γ|η| 2 . Hence if |hξ| ≤ ρ, |h -2 G(hξ) -|ξ| 2 | ≤ γ|ξ| 2 and e -h -2 tG(hξ) -e -t|ξ| 2 ≤ e γt|ξ| 2 -1 e -t|ξ| 2 ≤ γt|ξ| 2 e -(1-γ)t|ξ| 2 ≤ e -1 γ 1 -γ . Hence |ξ|≤ρh -1 e -h -2 tG(hξ) -e -t|ξ| 2 | f (ξ)| dξ ≤ e -1 γ 1 -γ || f || 1 .
The integral over h|ξ| > ρ can, as before, be bounded by The bound (57) is independent of t, but the hypotheses exclude polynomially increasing f , whose Fourier transform will be singular in 0. For such f we have the following more precise result, which is valid for any κ ≥ 2 and which shows if f (ξ) decays sufficiently rapildly, it is possible to get a much better apparent rate of convergence. Let (59)

C γ || |ξ| k f || 1 h k , where C γ = ρ(γ) -k . Since ||s h [f ] -f || A ≤ C|| f || ∞,
g κ := g κ (ϕ) := lim sup η→0 G(η) -|η| 2 |η| κ .
Theorem 5.9. If κ > 2, then for all s > κ and all ε > 0 there exist a constant C ε which does not depend on t > 0, such that

||u h (•, t) -u(•, t)|| A ≤ (g κ + ε)h κ-2 |ξ|≤rh -1 t|ξ| κ | f (ξ)|e -(1-ε)t|ξ| 2 dξ ((l κ + ε)h κ + C ε h s ) • R n | f (ξ)| max(|ξ| κ , |ξ| s )dξ. ( 60
)
while if κ = 2, the estimate holds on replacing the first term on the right by

R n | f (ξ)| 1 -e -g 2 t|ξ| 2 e -t|ξ| 2 dξ.
Proof. We adapt the proof of theorem 5.8. The first term of (51) is treated using theorem 4.1. As for the second term, by choosing r = r(ε) sufficiently small, we can bound the integral (52) by

(g κ + ε) h κ-2 |ξ|≤rh -1 t|ξ| κ | f (ξ)|e -(1-ε)t|ξ| 2 dξ, while the integral over |ξ| ≥ r/h can be estimated by r -s h -s |ξ|≥1 | f (ξ)| |ξ| s dξ if h ≤ r. The theorem follows. If f (ξ) ∈ L 1 k,κ (R n ) for some k ∈ (κ -2, κ],
then the proof shows that ||u h (•, t)-u(•, t)|| A can be bounded by the first term of (60) plus

C ε h k ||f || k,κ .
We then have the following corollary to theorems 5.7 and 5.9.

Corollary 5.10. Let κ ≥ 2 and suppose that g κ := lim η→0 |G(η) -|η| 2 |/|η| κ exists, so that g κ = g κ =:

g κ . Let f | R n \0 ∈ L 1 k,κ (R n ) for some k ∈ (κ -2, κ]. Then lim h→0 h -(κ-2) ||u h (•, t)-u(•, t)|| A =      g κ t R n | f (ξ)| |ξ| κ e -t|ξ| 2 dξ, κ > 2, R n | f (ξ)| 1 -e -g 2 t|ξ| 2 e -t|ξ| 2 dξ, κ = 2.
Compare with corollary 4.5. It follows from proposition 5.11 below that g κ exists iff lim |η|→0 |η| κ ϕ(η) exists. One can also give a direct proof of this corollary using Lebesgue's dominated convergence theorem. Theorem 5.9 is only of interest if g κ and l κ respectively g κ are small, in which case it shows one might see a higher apparent rate of convergence than the actual rate for small but not too small h's if f (ξ) decays sufficiently rapidly. As in section 4, we can construct basis functions ϕ with small g κ (ϕ) by taking these of the form ϕ(x) = φ(c -1 x) and letting c → ∞. We start by deriving explicit formulas for g κ (ϕ) and g κ (ϕ). Recall the definition of A(ϕ) and A(ϕ) in proposition 4.4.

Proposition 5.11. We have

(61) g κ (ϕ) = 1 A(ϕ) k =0 |2πk| 2 ϕ(2πk), g κ (ϕ) = 1 A(ϕ) k =0 |2πk| 2 ϕ(2πk) Proof. G(η) -|η| 2 = k |η + 2πk| 2 ϕ(η + 2πk) k ϕ(η + 2πk) -|η| 2 = k =0 4π(η, k) + 4π 2 |k| 2 ϕ(η + 2πk) ϕ(η + 2πk) = g(η) ϕ(η) + h(η) , with g(η) := k =0 4π(η, k) + 4π
G(η) -|η| 2 |η| κ = lim sup η→0 |g(η)| |η| κ ϕ + |η| κ h(η) = g(0) A = k 4π 2 |k| 2 ϕ(2πk) A ,
with A = A(ϕ). The formula for g κ (ϕ) follows similarly.

Note that l κ (ϕ) ≤ a κ (ϕ). Also note that g κ > 0 since A < ∞ and g κ < ∞ since A > 0, by the ellipticity condition on ϕ at 0.

If we take ϕ(x)

:= φ c (x) = φ(x/c), with φ ∈ B κ,N (R n ), then ϕ(η) = c n φ(cη), and A(φ c ) = c n-κ A(φ). It follows that g κ (φ c ) = c κ A(φ) k =0 |k| 2 φ(2πck) ≤ Cc κ-N k =0 |k| 2-N ,
where the series converges since N > n + 2.

Corollary 5.12.

If φ ∈ B κ,N (R n ) with N > max(n+2, κ), then g κ (φ c ) → 0 as c → ∞.
Examples 5.13. (i) Hardy's multiquadric with shape parameter c is defined by

(62) ϕ(x) := -|x| 2 + c 2 , x ∈ R n .
where the minus sign serves to make ϕ(η) positive. Note that ϕ(x) = cφ(x/c) with φ(x) := -|x| 2 + 1, so that we are in the situation of corollary 5.12, except for an irrelevant multiplicative factor of c. The Fourier transform of ϕ on R n \ 0 is given by

ϕ(η) = π -1 (2πc) (n+1)/2 |η| -(n+1)/2 K (n+1)/2 (c|η|),
where K ν is the MacDonald function, or modified Bessel function of the 2-nd kind: see for example cf. Baxter [START_REF] Baxter | On the asymptotic cardinal function of the multiquadric ϕ(r) = (r 2 + c 2 ) 1/2 as c → ∞[END_REF]. The limiting form of K ν for small values of the argument implies that as η → 0, ϕ(η) A n |η| -n-1 (with

A n = 2 n π (n-1)/2 Γ n+1 2
), so that κ = n + 1, and our RBF-scheme for the heat equation will converge if n ≥ 2, at a rate of h n-1 . The MacDonald function is known to decay exponentially at infinity, so that we can apply corollary 5.12 to conclude that l κ (φ c ) and g κ (φ c ) → 0 as c → ∞. In fact, these will converge to 0 at an exponential rate.

If n = 1, then κ = 2, and the scheme will not converge. However, corollary 5.12 together with theorems 5.8 and 5.9 show that we can make the error arbitrarily small by taking the shape parameter c sufficiently large, with moreover an arbitrarily large apparent order of convergence for small but not-too-small h's if the Fourier transform of the initial value decays sufficiently rapidly at infinity. At first sight, this may seem strange, because we are after all simply performing an additional scaling by c, and we are already using scaled basis functions ϕ h (x) = ϕ(h -1 x) for our interpolation. Note, however, that we are interpolating with φ ch on hZ n , and not on chZ n .

(ii) If we take a homogeneous basis function, φ(x) = |x| p with p > 0, then φ(η) is proportional to |η| -p-n on R n \0, so that κ = n+p = N and corollary 5.12 does not apply, as indeed it shouldn't: if φ is homogeneous, then L 1 (φ c ) and G(φ c ) are independent of c, and therefore g κ (φ c ) and l κ (φ c ) also.

Convergence of the RBF scheme for pseudo-differential evolution equations

The results of the previous section remain valid for a large class of pseudodifferential evolution equations of the form (63)

∂ t u + a(D)u = 0, t > 0,
under suitable conditions on the symbol a = a(ξ), notably that Re a(ξ) ≥ 0.

Here a(D) is defined by (a(D)v) ∧ (ξ) = a(ξ) v(ξ), initially with domain S(R n ), for example. We are in fact restricting ourselves to a rather special class of pseudo-differential operators, the Fourier multiplier operators, which are also convolution operators: if a(ξ) is a tempered distribution and if f is a test function, then a(D)f is the convolution of f with the inverse Fourier transform of a. These can also be considered as constant coefficient pseudodifferential operators, since general pseudo-differential operators have symbols which also depend on x. The latter are outside of the scope of this paper, but the multiplier operators we consider here already contain many interesting examples, such as the fractional Laplacians or the generators of large classes of Lévy processes. For the latter the equation (63) occurs for example in mathematical finance, and has been treated numerically in [START_REF] Brummelhuis | A radial basis function scheme for option pricing in exponential Lévy models[END_REF] using the RBF scheme we investigate here, with good results. We note that, from a numerical point of view, convergence of our RBF scheme for a convolution operator is far from obvious, since these, as integral operators, are non-local, and one needs basis functions which grow polynomially at infinity to obtain good convergence. To understand the good performance of these RBF schemes was a main motivation for writing this paper.

As regards the symbol, we will only need the relatively weak condition that a ∈ S q 0 (R n ), the set of C ∞ -functions a on R n such that for each multiindex α there exists a constant C α such that

(64) |∂ α ξ a(ξ)| ≤ C α (1 + |ξ|) q on R n .
It is noteworthy that we will not need the faster (1+|ξ|) q-|α| -decay for the derivatives which is often a standard requirement in pseudo-differential theory and which for example is satisfied by the symbols of partial differential operators. We first examine the action of a(D) on L 1 :

Lemma 6.1. If ϕ ∈ B κ,N (R n ) with N > n + p, then a(D)L 1 is a bounded continuous function and there exists a constant C > 0 such that |a(D)L 1 (x)| ≤ C(1 + |x|) -κ-n .
The proof is similar to that of theorem 2.3. In fact, here, and in other results below, it would have sufficed to require (64) for |α| ≤ κ + n + 1.

The second condition we will need to put on the symbol is that it has a non-negative real part:

(65) Re a(ξ) ≥ 0.

Perhaps curiously, we do not need ellipticity (or hypo-ellipticity) of Re a(ξ), which means that our results below will also apply to the free Schrödinger operator, for which a(ξ) = i|ξ| 2 , or the "half-wave equation", with a(ξ) = |ξ|.

The heat equation obviously also falls within the class of allowed evolution equations, as do the Kolmogorov-Fokker-Planck equations associated to certain Lévy processes which we will consider in more detail at the end of this section. The proofs below will be similar to the ones for the classical heat equation in section 5, and we will only signal when there are differences.

As in the previous section, we will be interested in solving (63) with initial value f using a scheme which is the RBF-variant of the classical method of lines, looking for approximate solutions of the form (42), where L 1 is the Lagrange function on Z n associated with a basis function in B κ,N (R n ) with κ > 0 and N > n + q, in view of lemma 6.1. The coefficients c k (t; h) of u h are again determined by requiring that u h solve (63) exactly in the interpolation points: ∂ t u h (hj, t) = -a(D)u h (jh, t) for j ∈ Z n . This now leads to the (infinite) system of ODEs (66)

dc j (t; h) dt = - k a(h -1 D x )(L 1 )(j -k)c k (t; h)
where a(h -1 D x ) has symbol a(h -1 ξ) and where we have used that a(D) commutes with translations. We again have to solve this system with initial condition c k (0) = f (hj). One shows as in lemma 5.1 that if p < κ then there exists a unique solution in C ∞ ([0, ∞), ∞ -p ) and that, as a consequence,

u h [f ](•, t) is in L ∞ -p (R n ) if f ∈ L ∞ -p (R n
) with norm bounded by a constant times that of f. Remark 6.2. One noteworthy feature of the RBF-scheme is that we do not need to discretize the operator a(D), contrary to for example Finite Difference schemes, but only need to know its action on L 1 or ϕ (in the context of irregularly spaced interpolation points). This is an advantage when the operator is a singular integral operator, as for example for the generators of Lévy processes: see [START_REF] Brummelhuis | A radial basis function scheme for option pricing in exponential Lévy models[END_REF] for a concrete example and further discussion.

To further analyze the RBF scheme we introduce the auxiliary function

G a on R n × R >0 defined by G a (ξ; h) := k a(ξ + 2πh -1 k) L 1 (hξ + 2πk) (67) = k a(ξ + 2πh -1 k) ϕ(hξ + 2πk) ν ϕ(hξ + 2πν)
, where the series converges abosolutely, given that N > n + q. One shows analogously to lemma 5.2 that if the initial condition f is a Schwarz-class function and if a ∈ S q 0 satisfies (65), then the Fourier transform with respect to x of u h (x, t) is given by

(68) u h (ξ, t) = e -tGa(ξ;h) s h [f ](ξ). The function G a (ξ; h) is in C κ -1,κ-( κ -1) b (R n ),
which allows the extension of this formula to initial values f of polynomial growth strictly less than κ whose Fourier transform coincides on R n \0 with an element of L 1 (R n , (|ξ| κ ∧ 1)dξ).

We also note that G a (ξ; h) is 2π/h-periodic in ξ and non-negative. Its zero-set contains 2πh -1 Z \ 0 but may be larger, unless a(ξ) > 0 for all ξ, and it satisfies the following basic estimate which generalizes proposition 5.3(ii)). Proposition 6.3. Suppose that a ∈ S q 0 (R n ) for some q ≥ 0, and let ϕ ∈ B κ,N with N > q + κ. Then there exists a constant C such that if h < 1, then

(69) |G a (ξ; h) -a(ξ)| ≤ Ch κ-q |ξ| κ , |ξ| ≤ π/h.
Proof. We have

G a (ξ; h) -a(ξ) = a(ξ) L 1 (hξ) -1 + k =0 a ξ + 2π h L 1 (hξ + 2πk).
The first term is bounded by a constant times (1

+ |ξ|) q |hξ| κ ≤ Ch κ-q |ξ| κ if |hξ| ≤ π. As for the other terms, |ξ + 2πk/h| is comparable to |k|/h if |ξ| ≤ π/h, so |a(ξ + 2πk/h)| ≤ Ch -q |k| q . Next, by (10)
,

L 1 (hξ + 2πk) ≤ C|hξ| κ |k| -N , |hξ| ≤ π, so that k =0 |a ξ + 2π h L 1 (hξ + 2πk)| ≤ Ch κ-q |ξ| κ k =0 |k| q-N ≤ Ch κ-q |ξ| κ ,
which proves the proposition.

Suppose now that f ∈ L ∞ -p (R n ) is of poynomial growth of order at most p such that f | R n \0 ∈ L 1 (R n , (|ξ| κ ∧ 1)dξ). The unique solution of the initial value problem in the space of tempered distributions is given by u(ξ, t) = e -ta(ξ) f and it follows from the arguments in Appendix B that for each t ≥ 0, u(x, t) is a continuous function of polynomial growth of order at most p. Moreover, by the arguments of that Appendix, the Fourier transform of u h (x, t) -u(x, t) is given by

e -th -2 Ga(ξ;h) s h [f ](ξ) -f (ξ) + e -t(h -2 Ga(ξ;h)-a(ξ)) -1 e -ta(ξ) f (ξ).
We then have the following convergence theorem. Theorem 6.4. Suppose that a ∈ S q 0 (R n ) satisfies (65) and that κ ≥ q > 0. Then there exists a constant C such that for f of polynomial growth or order strictly less than

κ such that f | R n \0 ∈ L 1 κ (R n ) we have that (70) ||u h (•, t) -u(•, t)|| A ≤ C t • h κ-q || f || κ .
Proof. The proof is similar to the proof of theorem 5.5, with a small twist. By proposition 6.3 and the elementary inequality |e z -1| ≤ e max(Re z,0) , z ∈ C, we have that since

Re(a(ξ) -G(ξ; h)) ≤ Re a(ξ)(1 -L 1 (hξ)) ≤ Ch κ |ξ| κ Re a(ξ) ≤ 1 2 Re a(ξ),
if h|ξ ≤ (2C) -1 κ , there exists an r > 0 such that if h|ξ| ≤ r, then e -tG(ξ;h) -e -ta(ξ) = e -t Re a(ξ) e -t(G(ξ;h)-a(ξ) -1

≤ C t h κ-q |ξ| κ e -1 2 t Re a(ξ) ,
which in absence of further hypotheses on the symbol a(ξ) we simply bound by Ch κ-p |ξ| κ . The rest of the proof proceeds as before.

Note that, on comparing with theorem 5.5 where q = 2, we require a stronger decay of f at infinity, which translates in two additional degrees of smoothnes (two extra derivatives) of f. If we assume that Rea(ξ) is elliptic, then (71) sup

R n
t|ξ| q e -tRe a(ξ) < ∞, is independent of t and theorem 6.

4 remains valid if f | R n \0 ∈ L 1 (R n , |ξ| κ-q ∧ |ξ| κ
), on replacing Ct by C(t + 1).

One can finally formulate lower and upper bounds for lim h→0 h κ-q ||u h (•, t)u(•, t)|| A similar to those of section 5.3 on replacing g κ |ξ| κ and g κ |ξ| κ by g a,κ (ξ) and g a,κ (ξ), defined as the liminf respectively limsup of |G(ξ; h) -a(ξ)| h κ-q as h → 0. Computing these functions is more difficult with the generality we allow for our symbols. We state a result under the simplifying assumption that a(ξ) behaves as a homogeneous function of order q at infinity and ϕ(η) as a homogeneous function of order -κ at 0. Theorem 6.5. Let a be as in theorem 6.4 and suppose that (72) lim λ→∞ a(λη) λ q =: a ∞ (η) exists for all η ∈ R n \ 0. Suppose also that A := lim η→0 |η| κ ϕ(η) exists. Let

(73) g a,κ := 1 A k =0 a ∞ (2πk) ϕ(2πk). Then if κ > q and f | R n \0 ∈ L 1 κ (R n ), then (74)
lim h→0 h q-κ ||u h (•, t) -u(•, t)|| A = |g a,κ | R n t|ξ| κ e -tRe a(ξ) | f (ξ)| dξ,
while if κ = q this limit equals

(75) R n
1 -e -tga,κ|ξ| κ e -tRe a(ξ) | f (ξ)| dξ.

This can be easily proved using Lebesgue's dominated convergence theorem, first in its discrete form to verify that lim h→0 G a (ξ; h) -a(ξ) h κ-q |ξ| κ = g a,κ , (note the absence of absolute value signes here in contrast to the definitions of g a,κ (ξ) and g a,κ (ξ) above) and next for the integral of e -tGa(ξ;h) -e -ta(ξ) | f (ξ)| over |ξ| ≤ r/h. We can allow f ∈ L 1 k,κ (R n ) for some k ∈ (κ -2, κ] (which we recall allows to control both the integral over |ξ| ≥ c/h and || s

h [f ] -f || 1 by a term which is O(h k )).
We note that if Re a = 0 on R n , then g a,κ can be equal to 0 , e.g. if the function a ∞ (η) ϕ(η) is odd. This would for example apply if we would use a radial basis function scheme with an even basis function ϕ to solve the constant coefficient transport equation

∂ t u + v • ∇u = 0, v ∈ R n .
One can finally state and prove an approximate approximation analogous to theorems 5.8 and 5.9 when g a,κ and l κ are small and f (ξ) decays sufficiently rapidly at infinity. In particular, if κ = q then ||u h (•, t) -h(•, t)|| ∞ can be made arbitrarily small by an appropriate choice of basis function. We leave the details to the reader. Examples 6.6. We give some examples of evolution equations (63) which are of interest for applications.

(i) The fractional heat equation:

∂ t u + (-∆) s u = 0,
where s ∈ (0, 1). Here the symbol, a(ξ) = |ξ| 2s is not smooth in 0, but only the behaviour for large |ξ| matters.

(ii) The Kolmogorov -Fokker -Planck equation associated to a Lévy process (X t ) t≥0 on R n . Recall that according to the Lévy -Khintchine theorem such a process is completely characterized by its characteristic function, E e i(ξ,Xt) = e tψ(ξ) with

ψ(ξ) = i(µ, ξ) - 1 2 (Σ ξ, ξ) + R n \0 e ix,ξ) -1 -i(x, ξ)χ(x) dν(x),
where Σ is a positive semi-definite linear operator and where ν is a positive Borel measure on R n \ 0 such that

R n \0 (|x| 2 ∧ 1)dν(x) < ∞,
called the Lévy measure; χ is a compactly supported function which is equal to 1 on a neighborhood of 0, and which can be taken smooth, if necessary. If, for a given f , we let u(x, t) = E(f (x + X t )), then u satisfies (63) with a(ξ) := -ψ(ξ) and initial value f. Note that a(ξ) satisfies (65) since

Re ψ(ξ) = - 1 2 (Σ ξ, ξ) - R n \0
(cos(xξ) -1)dν(x) ≤ 0.

Under appropriate hypothese on the Lévy-measure ν one can derive symboltype estimates for a(ξ). For example, when dν(x) = |x| -q h(x)dx with q < n + 2, and h(x) a rapidly decreasing continuous function, then a ∈ S 2 0 if Σ = 0, and in S q-n 0 if V = 0: cf. remark A.4 in Appendix A below. Examples of such processes are the jump-diffusion processes and the CGMYprocesses of mathematical finance, which were treated numerically in [START_REF] Brummelhuis | A radial basis function scheme for option pricing in exponential Lévy models[END_REF], [START_REF] Chan | Adaptive Radial Basis Function Methods for Pricing Options Under Jump-Diffusion Models[END_REF] and [START_REF] Chan | A Numerical Study of Radial Basis Function Based Methods for Options Pricing under the One Dimension Jump-diffusion Model[END_REF] with different choices of basis functions (respectively the multiquadric, inverse multi-quadric and the cubic spline). calculus, except that the latter concern the behavior at infinity 4 instead of at 0. From this point of view, (4) corresponds to having an elliptic symbol, whence our terminology. Buhmann's definition of admissible basis functions required in addition that ϕ(η) = c|η| -κ + r(η), where c > 0 and where, for some ε > 0, |∂ α η r| ≤ C α |η| κ+ε as |η| → 0 for all relevant α. In the pseudodifferential analogy, this corresponds to having a homogeneous principal symbol. As already mentioned, [START_REF] Buhmann | Multivariate Cardinal Interpolation with Radial Basis Functions[END_REF] needed an additional restriction on ε which we manage to avoid.

We note that as a consequence of conditions (ii) and (iii) of definition 2.1, (76)

|∂ α η ( ϕ -1 )| ≤ C|η| κ-|α| , |η| ≤ 1, |α| ≤ n + κ + 1.
Turning to the proof of theorem 2.3, we start by defining L 1 as the inverse Fourier transform of the right hand side of (8): since the latter is an integrable function, by definition 2.1(iv), L 1 is a well-defined continuous function. We first show that L 1 (x) has the proper decay at infinity.

(77) L 1 := F -1 ϕ(•) k∈Z n ϕ(• + k) .
Then there exists a positive constant C such that

(78) |L 1 (y)| ≤ C(1 + |y|) -κ-n , y ∈ R n .
The proof will use the following lemma, which basically is a special case of a classical estimate for kernels of convolution operators: see e.g. Stein [START_REF] Stein | Harmonic Analysis: Real-Variable Methods, Orthogonality and Oscillatory Integrals[END_REF], proposition 2 of Chapter VI, section 4.4.

Lemma A.2. Let p > -n and let a ∈ C p +n+1 (R n \ 0) be supported in some ball B(0, R) such that 5 Stein actually proves a stronger result under stronger conditions: if (79) is satisfied at all orders, and without the condition on the support of a, then k can be identified with a C ∞ -function away from 0, satisfying |∂ α x k(x)| ≤ C α |x| -p-n-|α| for all α. This result is stated and proven for p = 0, but the proof generalizes to any p > -n. We only need this estimate for k(x) itself, in which case we only need (79) for the limited number of derivatives of a indicated, and we also only need it for large |x| (note that if a has compact support, k is continuous, even C ∞ , and Stein's estimate for k at 0 becomes 4 Indeed, if (4) were required for all orders α (with constants which may then depend on α), then χ(ξ) ϕ(ξ/|ξ| 2 ) ∈ S κ (R n ), where χ is a C ∞ -function such that 1 -χ is compactly supported, and S p (R n ) is the standard symbol class of order p (cf. [START_REF] Stein | Harmonic Analysis: Real-Variable Methods, Orthogonality and Oscillatory Integrals[END_REF]). 5 Note that p + n + 1 ≥ 1 since p > -n.

trivial). The proof in [START_REF] Stein | Harmonic Analysis: Real-Variable Methods, Orthogonality and Oscillatory Integrals[END_REF] uses the Paley-Littlewood decomposition. An elementary prove of lemma A.2 can be given by writing

k(x) = (2π) -n R n χ(|x|ξ)a(ξ)e i(x,ξ) dξ+(2π) -n R n
(1-χ(|x|ξ))a(ξ)e i(x,ξ) dξ.

where χ ∈ C ∞ (R n ) with bounded derivatives such that χ(ξ) = 0 for |ξ| ≤ 1, χ(ξ) = 1 for |ξ| ≥ 2, and integrating the first integral by parts p + n + 1.

Proof of theorem A.1. Let χ 0 ∈ C ∞ c (R n ) such that χ 0 (η) = 1 in a neighbourhood of 0 and supp(χ 0 ) ⊂ (-π, π) k . For k ∈ Z n , define χ k by χ k (η) := χ(η + 2πk) and note that the supports of the χ k are disjoint. Finally, let χ c := 1k χ k ("c" for "complement"), so that χ c together with the χ k 's form a partition of unit. Then (81)

L 1 (x) = c (x) + k∈Z n k (x),
where

(82) k = F -1 χ k (η) ϕ(η) ν ϕ(η + 2πν) , k ∈ Z n or k = c.
We examine the decay in x of the separate terms.

Decay of c . The function χ c (η)/ k ϕ(η + 2πk) is in C κ +n+1 b (R n ), not-
ing that the denominator is a strictly positive periodic function which is C κ +n+1 b on the complement of (2πZ) n and therefore on the support of χ c . Multiplying with ϕ, we find that c (η) is C κ +n+1 with integrable derivatives of all orders, which implies by the usual integration by parts argument that

| c (x)| ≤ C(1 + |x|) -( κ +n+1) ≤ C(1 + |x|) -κ-n .
Note that L 1 (η) is at best C κ in the points of 2πZ n , so integration by parts will not give the required decay for of k , k ∈ Z n . We use lemma A.2 instead.

Decay of

0 . Since 0 (η) -χ 0 (η) = χ 0 (η) L 1 (η) -1 = χ 0 (η) ϕ(η) -1 k =0 ϕ(η + 2πk) 1 + ϕ(η) -1 k =0 ϕ(η + 2πk)
and since k =0 ϕ(η + 2πk) is C κ +n+1 on the suport of χ 0 , the estimates (76) implies that 0 (η) -χ 0 (η) satisfies condition (79) of lemma A.2 with

p = κ. It follows that | 0 (x)| ≤ C(1 + |x|) -κ-n , since F -1 (χ 0 ) is rapidly decreasing.
Decay of k , k = 0, c. This is similar, except that we have to pay attention to the size of the constant in front of the (1 + |x|) -κ-n . The Fourier transform k (η) will now be supported near η = -2πk. Shifting by 2πk, we see that

k (η -2πk) = χ 0 (η)ϕ(η + 2πk) ϕ(η) -1 1 + ν =0 ϕ(η) -1 ϕ(η + 2πν)
is supported in a small neighbourhood of 0, with derivatives of order |α| ≤

κ + n + 1 bounded by C(1 + |k|) -N |η| κ-|α| , with C independent of k. Lemma A.2 then implies that | k (x)| = k (x)e 2πi(k,x) ≤ C(1 + |k|) -N (1 + |x|) -(κ+n)) .
Since N > n by assumption, summation over all k ∈ Z n gives the desired result.

We note that the above estimates for k also show that L 1 satisfies the Strang-Fix conditions [START_REF] Maz'ya | Approximate approximations[END_REF]. Once we have defined L 1 through its Fourier transform, it is immediate to check that L 1 (k) = δ 0k for k ∈ Z n : indeed, by the 2π-periodicity of the denominator, writing the integral over R n as a sum of integrals over translates of (-π, π) n ,

L 1 (k) = R n ϕ(η) ν ϕ(η + 2πν) e ikη dη (2π) n = (-π,π) n ν ϕ(η + 2πν ) ν ϕ(η + 2πν) e ikη dη (2π) n = (-π,π) n e ikη dη (2π) n = δ 0k .
It remains to recognise L 1 as a sum of translates of ϕ. This follows as in Buhmann's paper by writing the denominator in the expression for L 1 (η) as a Fourier series:

(83) k ϕ(η + 2πk) -1 = k c k e ikη .
One verifies by the similar arguments as those of the proof of theorem A.1 that (84)

|c k | ≤ C(1 + |k|) -κ-n ,
so that the series converges absolutely: write

c k = (2π) -n (-π,π) n χ 0 (η) ν ϕ(η + 2πν) e i(η,k) dη+(2π) -n (-π,π) n 1 -χ 0 (η) ν ϕ(η + 2πν) e i(η,k) dη,
and estimate the first integral using lemma A.2 and the second by integrating by parts.

We finally claim that

(85) L 1 (x) = k c k ϕ(x -k),
where the series converges absolutely, by (84), since ϕ(x) grows at most as (1 + |x ) κ-ε , by assumption. Formally, this follows by writing

L 1 (x) = R n k c k e ikη ϕ(η)e iηx dη (2π) n = k c k ϕ(x + k),
except that the final step does not make sense since ϕ 1 (η) might not even be integrable in 0 and even if it is, when κ < n, ϕ might differ from integration against ϕ 1 (η) by a distribution supported in 0.

We have to carefully distinguish between the tempered distribution ϕ and the locally integrable function η → ϕ(η) with which it can be identified on R n \ 0. The relation between the two is given by the following identity: there exist constants c α , |α| ≤ κ -1 such that for all ψ ∈ S(R n ),

ϕ, ψ = |η|≤1 ϕ(η)   ψ(η) - |α|≤ κ -n ψ (α) (0) α! η α   dη + |η|≥1 ϕ 1 (η)ψ(η) dη + |α|≤ κ -1 (-1) |α| c α ψ (α) (0), (86)
where the sum is interpreted as empty if κ < n. Indeed, the first integral converges since |η| κ -n+1 ϕ(η) has an integrable singularity at 0. The sum of the two integrals on the right defines a tempered distribution. If we designate this distribution by Λ ϕ then the restriction of Λ ϕ to R n \ 0 can be identified with the function ϕ(η). The difference ϕ -Λ ϕ is then supported in 0, and therefore a linear combination |α|≤p c α δ (α) 0 of derivatives of the delta distribution in 0. To bound p, we use the following lemma, whose proof we postpone till the end of his section:

Lemma A.3. If κ ≥ n, then the inverse Fourier transform F -1 Λ ϕ is a continuous function which is bounded by C(|x| κ-n +1) for non-integer κ and by C(|x| κ-n log |x| + 1) if κ is a positive integer.
Since the inverse Fourier transform of |α|≤N c α δ (α) 0 is a polynomial of order p, and since, by assumption, ϕ(x), has polynomial growth of order strictly less than κ, it follows that p < κ, which is equivalent to p ≤ κ -1 (which is κ if κ is non-integer, and κ -1 otherwise.

We will now use this identity to prove the equality (85), as tempered distributions. Let ψ ∈ S(R n ) and put

Ψ(η) := ψ(η) k ϕ 1 (η + 2πk)
.

Then Ψ is C κ if κ / ∈ N, and C κ-1,1 if κ ∈ N * , with all its derivatives rapidly decreasing. To obtain a function in the Schwartz class S(R n ) we convolve with χ

ε (x) := ε -n χ(x/ε), where χ ∈ C ∞ c (R n ) with integral 1. Let Ψ ε := χ ε * Ψ. Then we first claim that (87) ϕ, Ψ ε → R n L 1 (η)ψ(η) dη,
To show this it suffices to consider the case that κ ≥ n. By using the familiar remainder estimates for the Taylor expansion one shows that if we assume for example that supp(χ) ⊂ B(0, 1) then there exists a constant C > 0 such that for all ε ≤ 1,

Ψ ε (η) - |α|≤ κ -n Ψ (α) ε (0) α! η α ≤ C max |β|= κ -n+1 sup B(0,1) |Ψ (β) ε | • |η| κ -n+1 ≤ C max |β|= κ -n+1 sup B(0,2) |Ψ (β) | • |η| κ -n+1 ,
where we note that if n ≥ 2 or if κ / ∈ N * , then derivatives of Ψ of order κ -n + 1 exist, while if n = 1 and κ ∈ N * , these derivatives exist a.e. but are uniformly bounded, and the estimate remains true. Next, Ψ

α) ε (x) → Ψ (α) (x) for |α| ≤ κ -1 since Ψ is C κ -1 (
, and Ψ (α) (0) = 0 for such α, since ( k ϕ(η + 2πk)) -1 vanishes of order κ in 0. Hence (87) follows by dominated convergence, Since Ψ ε is Schwartz-class, we have ϕ, Ψ ε = ϕ, Ψ ε . By (83) Ψ = k c k e -i(k,η) ψ(η), which can be interpreted as the product of a tempered distribution and a test function, and its Fourier transform equals

Ψ(x) = k c k ψ(x -k). One easily verifies that| Ψ(x)| ≤ C(1 + |x|) -κ-n . Since Ψ ε (x) = χ(εx) Ψ(x), and since |ϕ(x)| ≤ C(1 + |x|) κ-ρ for some ρ > 0, Lebesgue's dominated convergence theorem shows that ϕ, Ψ ε = R n ϕ(x) Ψ(x) χ(εx) dx → R n ϕ(x) k c k ψ(x -k) dx.
Finally, one checks that the functions (x, k) → c k ϕ(x) ψ(x -k) and (x, k) → c k ϕ(x + k) ψ(x) are integrable on R n × Z n with respect to the product of the Lebesgue measure and the counting measure. A double application of Fubini's theorem then shows that the right hand side equals

R n k c k ϕ(x + k) ψ(x) dx,
which proves (85).

Proof of lemma A.3. The lemma is classical, but we sketch a proof for convenience of the reader. For κ < n, the inverse Fourier transform is a bounded function, so suppose that κ ≥ n. Since 1 {|η|≥1} ϕ(η) is integrable, its inverse Fourier transform is a bounded continuous function, and it therefore suffices to examine the inverse Fourier transform of the tempered distribution defined by the first integral on the right hand side of (86). This distribution being of compact support, its inverse Fourier transform is the function k(x) obtained by taking ψ(η) = (2π) -n e i(x,η) :

(88) k(x) := (2π) -n |η|≤1 ϕ(η)   e i(x,η) - k≤ν i k (x, η) k k!   dη,
where ν := κ -n. This can be bounded by

|k(x)| ≤ C |η|≤1 |η| -κ e i(x,η) - j≤ν i j (x, η) j j! dη = C|x| κ-n |η|≤|x| |η| -κ e i( x |x| ,η) - j≤ν i j ( x |x| , η) j j! dη.
Split the integral into one over |η| ≤ c and one over the complement, where c > 0 is some fixed number and where we assume wlog that |x| > c. For the first integral, since

e i( x |x| ,η) - j≤ν i j ( x |x| , η) j j! ≤ 1 ν! |( x |x| , η)| ν+1 ≤ |η| ν+1 ν! ,
the integral converges at 0 and we can bound its contribution to k(x) by C|x| κ-n . As for the second integral, it can be bounded by a constant times

|x| κ-n ν j=0 |x| c r -κ+j+n-1 dr = |x| κ-n ν j=0 1 j -κ + n |x| j-κ+n -c j-κ+n ,
assuming that κ / ∈ N. Since j -κ + n ≤ ν -κ + n ≤ 0 by the definition of ν, this will be bounded by C|x| κ-n .

Finally, if κ ∈ N, κ ≥ n, then ν = κ -n and the first integral is still O(|η| κ-n while the second integral gives a contribution of

|x| κ-n κ-n j=0 |x| c r j-(κ-n)-1 dr = |x| κ-n κ-n-1 j=0 1 j -κ + n |x| j-(κ-n) -c j-(κ-n) + log(|x|/c) ≤ C|x| κ-n (log |x| + 1).
Remark A.4. The only hypotheses on ϕ(η) we needed for this lemma is that it be integrable on {|η| ≥ 1} and that ϕ(η) = O(|η| -κ ) near 0. If we strengthen the first assumption to

(89) |η| r | ϕ(η)|1 {|η|≥1} ∈ L 1 (R n ),
where r ∈ N, then k will be r-times differentiable, and the proof will provide estimates

|∂ α x k(x)| ≤
C(|x| max(κ-n-|α|,0) + 1) κ / ∈ N C(|x| max(κ-n-|α|,0) log |x| + 1) κ ∈ N, for the derivatives. For the proof it suffices to observe that if k(x) is given by (88) then its derivative of order α is given by the same formula with ϕ(η) replaced by (iη) α ϕ(η).

These estimates can be used to obtain symbol estimates for the generator of pure-jump Lévy processes, in which case ϕdη would be replaced by a Lévy measur of the form dν(η) = h(η) |η| q dη, with q < n + 2, and h(η) a rapidly decreasing continuous function satisfying (89) for all r. The inverse Fourier transform of Λ ϕ(•) in the lemma then is, modulo a function in C ∞ b , equal to the symbol of the generator of the Lévy process, and the estimates show this symbol to be in S max(q-n,0) 0 if q / ∈ N, and in S max(q-n,0)+ε 0 for any ε > 0 otherwise (even a bit better, since the first few derivatives will decay relative to the symbol itself). Examples are given by the CGMY-processes which are used in financial modeling. We can, in particular, let Λ F act on the imaginary exponentials ξ → e i(x,ξ) . The function F : x → (2π) -n Λ F , e i(x,ξ) . We next check that Σ h ( f ) is the Fourier transform, in distribution sense, of s h [f ]. This is done by a standard approximation argument, with some care with the spaces in which the approximating sequence converges. We first note that we can assume without loss of generality that f is compactly supported: indeed, we can write f = f 1 + f 2 with f 1 compactly supported and f 2 ∈ L 1 (R n ), and we know already that s h [f 2 ] = Σ h ( f 2 ). So let f be compactly supported, and let χ ∈ C ∞ c (R n ) be a non-negative symmetric function with The lemma immediately implies that if ψ ∈ S(R n ), then f * χ ε , Σ h (ψ) → f , Σ h (ψ) , so Σ h ( f * χ ε ) → Σ h ( f ) in S (R n ) and even in (C K,λ ) with K and λ as above.

R n χdη = 1. Let χ ε (η) := ε -n χ(η/ε). Then f * χ ε ∈ C ∞ c (R n ).
On the other hand, if we let f ε be the inverse Fourier transform of f * χ ε , then f ε ∈ S(R n ) since f * χ ε is, and s h [f ε ] = Σ h ( f * χ ε ). We have that f ε (x) = (2π) -n f (x) χ(εx), with χ the inverse Fourier transform of χ, so χ ∈ S(R n ) and χ(0) = 1. By hypotheses, f ∈ L ∞ -p for some p < κ. Then if a > 0 such that p + a < κ, then

||s h [f ε ] -s h [f ]|| ∞,-(p+a) ≤ C||f ( χ(ε•) -1) || ∞,-(p+a) ≤ C||f || ∞,-p sup x∈R n | χ(εx) -1| (1 + |x|) a → 0, as ε → 0. This certainly implies that s h [f ε ] → s h [f ] in S (R n ), so we con- clude that s h [f ε ] = Σ h ( f * χ ε ) → s h [f ] and therefore s h [f ] = Σ h ( f ) as distributions.
We finally show that Σ h ( f ) = f +F , where F is the (distribution obtained by integrating against the) L 1 function (95)

F (ξ) = f (ξ)( L 1 (hξ) -1) + k =0 f (ξ + 2πh -1 k) L 1 (hξ).
We first check that F is well-defined: first of all, each of the terms on the right hand side is in L 1 , on account of the Fix-Strang condition for L 1 at ξ = 0 and the integrability of (|ξ| κ ∧ 1) f (ξ). Next, the function Φ : (ξ, k) → f (ξ +2πh -1 k)( L 1 (hξ)-δ 0k ) is absolutely integrable on R n ×Z n with respect to the product of Lebesgue measure and the counting measure, since

k R n | f (ξ + 2πh -1 k)| |( L 1 (hξ) -δ 0k )| dξ = R n (1 -L 1 (hξ))| f (ξ)|dξ + k =0 L 1 (hξ + 2πk)| f (ξ)|dξ = 2 R n (1 -L 1 (hξ))| f (ξ)|dξ.
Fubini's theorem then implies that F (ξ) is well-defined for almost all ξ ∈ R n and that F ∈ L 1 (R n ). If ψ ∈ S(R n ), then a double application of Fubini will show that

R n F (ξ)ψ(ξ)dξ = R n   ψ(ξ)( L 1 (hξ) -1) + k =0 ψ(ξ + 2πh -1 k) L 1 (hξ + 2πk)   f (ξ) dξ = R n (Σ h (ψ) -ψ) f (ξ)dξ.
Since, by the Fix-Strang conditions on L 1 , all derivatives of order ≤ κ -1 of Σ h (ψ) -ψ in 0 are 0, the last integral is equal to f , Σ h (ψ) -ψ = Σ h ( f ) -f , ψ , and therefore Σ h ( f ) -f = F , which finishes the proof of lemma 3.5.

Remark B.2. The lemma and its proof generalizes to f 's such that f | R n \0 is a finite Borel measure with respect to which the function |ξ| κ ∧1 is integrable, provided that κ / ∈ N (the reason being that we then no longer have (92)).

B.2. Proof of lemma 5.4. It again suffices to consider the case of compactly supported f 's. Let χ ε = ε -n χ(•/ε) be an approximation of the identity, as in the proof of lemma 3.5 and let f ε be the inverse Fourier transform of f * χ ε . We have seen that Σ h ( f ε ) → Σ h ( f ) in C K,λ . Since e -h -2 tG(h•) ∈ C K,λ , this implies that e -h -2 tG(h•) f ε → e -h -2 tG(h•) f in C K,λ and hence in S (R n ).

On the other hand, we have seen in the proof of lemma 3.5 that f ε → f in L ∞ -p-a if a > 0. Hence by lemma 5.1, if a < κ -p then u

h [f ε ] → u h [f ] in L ∞
-p-a and therefore as tempered distributions. This implies that

e -h -2 tG(h•) f ε u h [f ε ] → u h [f ],
where we used lemma 5.2. Hence u h [f ] = e -h -2 tG(h•) f as tempered distributions, as claimed.

We finally Prove (48): suppose that f ∈ • L 1 κ-2 (R n ) and define g(ξ, t, h) := e -t(h -2 G(h•)-|ξ| 2 ) -1.

Then g is a C

κ -1,λ b -function which we have shown vanishes to order |ξ| κ in 0. The representation f = Λ f + |α|≤ κ -1 c α δ (α) from the proof of lemma 3.5 then shows that the distribution g(•, t, h) f can be identified with the locally integrable function ξ → g(ξ, t, h) f (ξ).

  |α|≤K ||f (α) || ∞ + |α|=K ||f (α) || 0,λ , where ||g|| 0;λ := sup ξ =η |g(ξ) -g(η)|/|ξ -η| λ .

Theorem 4 . 3 .

 43 Let f satisfy the hypothesis of theorem 4.1. Then

Corollary 4 . 5 .

 45 38) and (39) follow upon letting η → 0. If lim η→0 |η| -κ ϕ(η) exists, then l κ (ϕ) = l κ (ϕ) = l κ (ϕ), and

5. 2 .

 2 Convergence of the scheme in Wiener norm. We start by computing the Fourier transform of u h [f ]. Let us introduce the auxiliary function G(η) on R n by

  s h k by corollary 3.8, the theorem follows.

Theorem A. 1 .

 1 If ϕ ∈ B κ,N , and if

  |∂ α ξ a(ξ)| ≤ C|ξ| p-|α| , , ξ ∈ R n , |α| ≤ p + n + 1. Then the inverse Fourier transform k = F -1 (a) satisfies (80) |k(x)| ≤ C 1 (1 + |x|) -p-n , x = 0, with a constant C 1 ≤ c n C, where c n only depends on n.

( 1

 1 Appendix B. Some technical proofs B.1. Proof of lemma 3.5. Let F ∈ L 1 (R n \ 0, (|ξ| κ ∧ 1)dξ), where a∧b := min(a, b) and κ ≥ 0. Then F gives rise to a tempered distribution ΛF ∈ S (R n ) defined as follows: if g ∈ C ∞ c (R n ) be equal to 1 on a neighbourhood of 0, we put Λ F , ψ := -g(ξ))F (ξ)ψ(ξ) dξ, ψ ∈ S(R n ). The integral converges since ψ -|α|≤ κ -1 ψ (α) (0)ξ α /α! = O(|ξ| κ ) = O(|ξ| κ) in a neighbourhood of 0 and defines a distribution of order κ . Note that Λ F coincides on R n \ 0 with the function F which is in L 1 loc (R n \ 0). We next observe that Λ F extends to a continuous linear functional on the Hölder spaceC κ -1,λ b := C κ -1,λ b (R n ) with λ = κ -( κ -1). Indeed, if ψ ∈ C K,λ (R n ),we have the Taylor remainder estimate:(91) ψ(ξ) -|α|≤K ψ (α) (0)ξ α /α! ≤ C   |β|=K ||ψ (β) || 0,λ   |ξ| K+λ ,which shows, with K = κ -1 and λ = κ -( κ -1), that Λ F , ψ is well-defined and continuous.

  is then found to be bounded by C(1 + |x|) κ , since ||e i(x,ξ) || K,λ ≤ C(1 + |x| K+λ ), and one checks that the inverse Fourier transform of Λ F coincides with F . In fact,(92) | F (x)| = o(|x| κ ), |x| → ∞,which can be seen as follows: writing F = χF + (1 -χ)F with χ the characteristic function of a small ball around 0, and observing that (1 -χ)F

Lemma B. 1 .

 1 f * χ ε → f in the dual of C K,λ , with K = κ -1 and λ = κ -K.Proof. On account of the symmetry of χ,f * χ ε , ψ = f , ψ * χ ε , which is valid both for Schwarz-class functions ψ ∈ S and for ψ ∈ C K,λ . Write ψ ε := ψ * χ ε . If ψ ∈ C K,λ , then ψ (α) ε (x) → ψ (α) (x) pointwise on R n for all |α| ≤ K, while a trivial estimate shows that ||ψ (α) ε || 0,λ ≤ ||ψ (α) || 0,λ , uniformly in ε > 0, for |α| = K.This, together with the remainder estimate (91), the integrability of f (ξ)(|ξ| κ ∧1) and Lebesgue's dominated convergence theorem, implies that Λ f , ψ ε → Λ f , ψ . Since also δ (α) 0 , ψ ε → δ (α) 0 , ψ for all |α| ≤ K, the lemma follows.

  BRAD BAXTER, DEPARTMENT OF ECONOMICS, MATHEMATICS AND STATISTICS, BIRKBECK, UNIVERSITY OF LONDON, MALET STREET, LON-DON WC1E 7HX, UK, e-mail: b.baxter@bbk.ac.uk RAYMOND BRUMMELHUIS, LABORATOIRE DE MATH ÉMATIQUES DE REIMS, UNIVERSIT É DE REIMS-CHAMPAGNE-ARDENNE, FR 3399 CNRS, BP 1039, 51687 CEDEX 2, REIMS, FRANCE, e-mail: raymondus.brummelhuis@univreims.fr

The index κ is a reminder of the degree of the singularity of ϕ at 0, and therefore of the natural convergence rate of the RBF interpolants.

Appendix A. Proof of theorem 2.3 on the existence of a cardinal function

We prove the existence and main properties of the cardinal function associated to a basis function ϕ ∈ B κ,N (R n ) as stated in theorem 2.3. This was done by Buhmann [START_REF] Buhmann | Multivariate Cardinal Interpolation with Radial Basis Functions[END_REF], [START_REF] Buhmann | Radial Basis Functions[END_REF] for a more restricted class of radial basis functions. The main difference in our treatment and that of Buhmann is the use of a simple lemma, lemma A.2 below, which relates decay at infinity of the Fourier transform of a function with its behavior in 0, and which allows us to go beyond the case of ϕ's whose Fourier transform has a homogeneous singularity in 0. We also fill in what we believe to be a minor gap in the original proof.

Before embarking upon the proof, it may be interesting to observe that the estimates (3) are analogus to the symbol conditions of pseudodifferential is integrable, we can we can wlog assume that F is supported in {g = 1}. If we apply (90) with ψ(ξ) = e i(x,ξ) then 6

where Fα (x) is the inverse Fourier transform of the L 1 -function ξ → ξ α F (ξ). By the Riemann-Lebesgue lemma, F α (sx) → 0 as x → ∞, for all s ∈ (0, 1], and the same is true for the integral over s ∈ [0, 1], by the dominated convergence theorem. Hence F (x)/|x| κ → 0 for x → ∞, as claimed.

Now let f be a measurable function on R n of polynomial growth of order strictly less than κ, such that its Fourier transform f (in the sense of distributions) satisfies In follows that

0 also extends to a continuous linear functional on C κ -1,κ-( κ -1) . We exploit this to define Σ h ( f ) by duality.

Note that Σ h is the formal adjoint of Σ h . By lemma 2.6, Σ h (ψ) is C κ -1,λ b with λ = κ -( κ -1) and uniformly bounded together with all its derivatives, since 2πh -1 -periodic. In fact, this is true even if ψ ∈ C κ -1,λ b with the same λ, on account of the decay at infinity of L 1 . We can then define Σ h ( f ), as a tempered distribution and, more generally, as a bounded linear functional on C