Construction Techniques for Highly Accurate Quasi-Interpolation Operators

Robert Schaback

Institut für Numerische und Angewandte Mathematik

Universität Göttingen 37083 Göttingen, Germany

Zongmin Wu ^{1} Department of Mathematics

Fudan University 200433 Shanghai, China

December 14, 1995

1The work was done during the author’s visit to Göttingen under support of a DAAD-Wong fellowship.

Highly Accurate Quasi-Interpolation

Robert Schaback & Zongmin Wu

Mail Address:

R. Schaback Institut für Numerische und Angewandte Mathematik Lotzestr. 16–18 37083 Göttingen Germany

Abstract: Under mild additional assumptions this paper constructs quasi -interpolants in the form

f_{h}(x) = ∑_{j=−∞}^{+∞} f(hj)φ_{h} (\frac{x}{h} − j) , x ∈ IR, h > 0  (0.1)

with approximation order ℓ, where φ_{h}(x) is a linear combination of translates ψ(x − jh) of a function ψ in C^{ℓ(IR}). Thus the order of convergence of such operators can be pushed up to a limit that only depends on the smoothness of the function ψ. This approach can be generalized to the multivariate setting by using discrete convolutions with tensor products of odd-degree B–splines.

AMS classifications: 41A15, 41A25, 41A30, 41A63, 65D10.

Keywords: Radial Basis Function, Quasi -Interpolation, Strang -Fix conditions, Smoothness, Order of Convergence.

List of Symbols

ψ  3,5  C^{ℓ+1}  3,5
f_{h}(x)  3,5  φ_{h}  3,5
ψ̂  5  φ  5
Qf_{h}(x)  5  C_{k}(ψ)  6
I_{k,h}(x, t)  6  c_{k,h,j}(t)  6
B_{k}(f)  7  ℓ_{0}  7
ℓ_{1}  7  ℓ_{2}  7
D_{k,m}(ψ)  7  T (e^{it})  10
χ  10  χ_{[−1/2,1/2]}  10
B_{m−1}  10  φ_{m}  10
φ_{ℓ,h}^{(k)}  12  φ_{ℓ}  12
φ_{ℓ}^{(k)}  12  Q_{h}^{(k)}f  12
Q̃_{h}^{(k)}f  12

1 Introduction

If the Fourier transform ψ̂ of a function ψ : IR → IR with certain additional properties has zeros of order ℓ at 2πj ≠ 0 j ∈ ZZ , then Strang -Fix theory implies that there is a linear combination φ of the translates ψ(x − j) of ψ such that the quasi-interpolation

Qf_{h}(x) = ∑_{j∈Z} f(jh)φ(\frac{x}{h} − j)  (1.1)

is convergent and has approximation order ℓ with respect to h → 0. This paper treats two problems :

1. Is the special quasi- interpolation

∑_{j∈Z} f(jh)ψ(\frac{x}{h} − j)  (1.2)

defined by ψ itself convergent and what is its order of approximation? We will investigate the influence of the behaviour of the Fourier transform ψ̂ of ψ near zero to the approximation order of (1.2).

2. The classical Strang-Fix condition [10] is a necessary and sufficient condition for a quasi- interpolant of the above form (1.1) to have a certain approximation order. But can we construct other quasi- interpolants from ψ with higher approximation order? How far can the approximation order of variations of (1.2) be increased for a fixed given ψ?

In the second situation, we shall leave the classical “stationary” setup for quasi–interpolants of the form (1.1). This idea is not new. It was indicated in [9] by Dyn and Ron. See also [6] and [1], where similar estimates to those of our Section 2 were established. Usually, the sampling distance h of the data f(jh) is identical to both the shift distance δ and the scaling parameter σ for the basic function ψ in the sense that the quasi–interpolant is in the span of translates ψ (\frac{· − jδ}{σ} ). In contrast to this, we finally use shift δ = h^{2} and scale h with the sampling distance h, and we are interested in explicit constructions of quasi–interpolants

Qf_{h}(x) = ∑_{j∈ZZ} f(jh)ϕ_{h} (\frac{x}{h} − j) ,  (1.3)

where φ_{h} is a linear combination of translates ψ(· − kh), such that we altogether work in the span of functions

ψ (\frac{· − jh − kh^{2}}{h} ) , j, k ∈ ZZ

to recover data f(jh), j ∈ ZZ.

In the sense of the literature on principal shift–invariant spaces ([5], [6], [14]) we thus work in the scale of spaces {S_{h^{2}}(ψ(·/h))}_{h}, but our special quasi–interpolation operators do not attain the optimal approximation orders (in terms of distances) that are possible in this scale. Those orders are independent of special operators, but we want to stick to simple operators like (1.3) based on sampling at distance h. Thus we do not study the general approximation orders in these spaces, since we confine ourselves to the special quasi–interpolants (1.3), where φ_{h} is based on “other” shifts and dilates of ψ. Nor is it relevant at the outset that we finally end up with shifts δ = h^{2}: our main ingredient is the data sampling at distance h, and this is why we keep h as an index to the quasi–interpolants (1.3). Our results imply

that the attainable order of convergence for quasi–interpolants (1.3) mainly depends on the smoothness of the function ψ, and we provide an explicit construction that makes full use of this fact. Applications include the construction of quasi–interpolants based on data f(jh) that achieve arbitrarily high approximation orders, if ψ is chosen to be a multiquadric or a Gaussian.

2 Convergence Orders of Quasi–Interpolants

We first consider quasi–interpolants of the special form

f_{h}(x) = ∑_{j=−∞}^{+∞} f(hj)ψ (\frac{x}{h} − j) , x ∈ IR, h > 0  (2.1)

for functions f ∈ C(IR) that are inverse Fourier transforms

f(x) = \frac{1}{2π} ∫_{−∞}^{+∞} f̂(t)e^{ixt}dt, x ∈ IR  (2.2)

of functions f̂ ∈ L_{1}(IR). The quasi–interpolant (2.1) is supposed to use a basic function ψ ∈ C^{ℓ}(IR) with

C_{k}(ψ) := max_{0≤ξ≤1} ∑_{j=−∞}^{+∞} |ψ^{(k)}(ξ − j)| < ∞  (2.3)

for 0 ≤ k ≤ ℓ.

In the terminology of shift–invariant spaces this is a specific form of approximation in a scale {S_{h}} of principal shift–invariant subspaces

S_{h} := {g ∈ S : g = f_{h} for f ∈ S}

of the shift–invariant space

S := {f ∈ C(IR), f̂ ∈ L_{1}(IR), (2.2)}.

Note that we do not attempt to characterize S_{h} in an intrinsic way, e.g. by a summability condition on coefficients in (2.1). For our purposes it suffices to provide L_{∞} bounds for the error of quasi–interpolation of f ∈ S by f_{h} ∈ S_{h}.

We start with an integral representation for f{(k) \atop h} that is based on Fourier transform techniques as used in [1] and [6] for instance, and we skip over the proof, which can be reduced to an application of Poisson’s summation formula to the function whose Fourier transform is ψ^{(k)}(x + ·). If f ∈ C(IR) satisfies (2.2) with f̂ ∈ L_{1}(IR) and if ψ ∈ C^{ℓ}(IR) is a function with (2.3) for 0 ≤ k ≤ ℓ, then the quasi–interpolant (2.1) exists and has derivatives up to order ℓ that can be expressed by

f{(k) \atop h} (x) = \frac{1}{2π} ∫_{−∞}^{+∞} f̂(t)e^{ixt}I_{k,h}(x, t)dt  (2.4)

with a continuous h–periodic function

I_{k,h}(x, t) := h^{−k} ∑_{j=−∞}^{+∞} e^{−i(x−hj)t}ψ^{(k)} (\frac{x}{h} − j)  (2.5)

that has a Fourier series representation

I_{k,h}(x, t) = ∑_{j=−∞}^{+∞} c_{k,h,j}(t)e^{2πijx/h}

with coefficients

c_{k,h,j}(t) = (\frac{i}{h} )^{k} (2πj + ht)^{k}ψ̂(2πj + ht).  (2.6)

Now we assume f to satisfy

B_{k}(f) := ∫_{−∞}^{+∞} |f̂(t)t^{k}|dt < ∞  (2.7)

for 0 ≤ k ≤ L. Then

f^{(k)}(x) = \frac{1}{2π} ∫_{−∞}^{+∞} f̂(t)(it)^{k}e^{ixt}dt

for 0 ≤ k ≤ L and

f{(k) \atop h} (x) − f^{(k)}(x) = \frac{1}{2π} ∫_{−∞}^{+∞} f̂(t)e^{ixt}(I_{k,h}(x, t) − (it)^{k})dt  (2.8)

for 0 ≤ k ≤ min(ℓ, L). A similar error representation was used in [17] and [20] to prove error bounds for radial basis function interpolation. Note that this means that we work in a subspace

S^{k} := {f ∈ C^{k}(IR), f̂ ∈ L_{1}(IR) and (2.7)}

measuring smoothness of functions in S.

To get a bound for this representation of the error, we require additional assumptions on ψ. Let the Fourier transform ψ̂ of ψ have zeros of order ℓ_{1} in 2πj for all j ≠ 0. Furthermore, let ψ̂ − 1 have a zero of order ℓ_{0} in 0.

More specifically we require ψ̂ ∈ C^{ℓ_{2}}(IR), ℓ_{2} ≥ max(ℓ_{0}, ℓ_{1}) and use Taylor’s formula to write

ψ̂(2πj + t) = ψ̂^{(ℓ_{1})}(2πj + tτ_{j}(t))t^{ℓ_{1}}/ℓ_{1}!,  (2.9)
ψ̂(t) − 1 = ψ̂^{(ℓ_{0})}(tτ_{0}(t))t^{ℓ_{0}}/ℓ_{0}!  (2.10)

with τ_{m}(t) ∈ [0, 1] for all m ∈ ZZ and all t ∈ IR. Finally, we define

D_{k,m}(ψ) := max_{|η|≤1^{|ξ|≤1}} ∑_{j≠0} |2πj + ξ|^{k}|ψ̂^{(m)}(2πj + η)|  (2.11)

for 0 ≤ m ≤ ℓ_{2} and assume

D_{k,m}(ψ) < ∞, 0 ≤ k ≤ K

for some nonnegative integer K.

Theorem 2.1 Assume the quasi–interpolant (2.1) to be generated by a function ψ ∈ C^{ℓ}(IR) with a Fourier transform ψ̂ satisfying (2.9), (2.10), and (2.11). If the quasi–interpolant is evaluated for functions f ∈ C(IR) with B_{k}(f) < ∞, 0 ≤ k ≤ L, then

∥f{(k) \atop h} − f^{(k)}∥_{∞} ≤ Ch^{d}

for 0 ≤ k ≤ min(ℓ, L − ℓ_{0}, K, ℓ_{1}),

d = min(ℓ_{0}, ℓ_{1} − k),

and all h > 0. The constant C is the maximum of

\frac{1}{2π} (B_{L}(f)(1 + C_{k}(ψ)) + \frac{B_{k+ℓ_{0}}(f)}{ℓ_{0}!} ∥ψ^{(ℓ_{0})}∥_{∞,[−1,+1]} + \frac{B_{ℓ_{1}}(f)D_{k,ℓ_{1}}(ψ)}{ℓ_{1}!} )

for 0 ≤ k ≤ min(ℓ, L − ℓ_{0}, K, ℓ_{1}).

Proof: We first consider the integrand (2.8) on |t| > h^{−1}. If we use (2.3) to get a uniform bound

|I_{k,h}(x, t)| ≤ C_{k}(ψ)h^{−k}, 0 ≤ k ≤ ℓ

for all x, t ∈ IR and h > 0, then we have

\frac{1}{2π} ∫_{|t|≥1/h} |f̂(t)e^{ixt}(I_{k,h}(x, t) − (it)^{k})|dt

≤ \frac{1}{2π} ∫_{|t|≥1/h} |f̂(t)|(C_{k}(ψ)h^{−k} + |t|^{k})dt
≤ \frac{1}{2π} ∫_{|t|≥1/h} |f̂(t)|(C_{k}(ψ) + 1)|t|^{k}dt
≤ \frac{1}{2π} (C_{k}(ψ) + 1) ∫_{|t|≥1/h} |f̂(t)| · |t|^{k}|ht|^{L−k}dt
≤ \frac{1}{2π} (C_{k}(ψ) + 1)h^{L−k}B_{L}(f)

for 0 ≤ k ≤ min(ℓ, L) and all h > 0.

For |t| < 1/h we split the integrand via

I_{k,h}(x, t) − (it)^{k} = c_{k,h,0}(t) − (it)^{k} + ∑_{j≠0} c_{k,h,j}(t)e^{2πijx/h}.

The first part is bounded by

\frac{1}{2π} ∫_{|t|<1/h} |f̂(t)| |c_{k,h,0}(t) − (it)^{k}|dt

= \frac{1}{2π} ∫_{|t|<1/h} |f̂(t)| |t|^{k}|ψ̂(ht) − 1|dt
≤ \frac{h^{ℓ_{0}}}{2πℓ_{0}!} ∫_{|t|<1/h} |f̂(t)| |t|^{k+ℓ_{0}}| ψ̂^{(ℓ_{0})}(htτ_{0}(t))|dt
≤ \frac{h^{ℓ_{0}}}{2πℓ_{0}!} B_{k+ℓ_{0}}(f) · max_{|ξ|≤1} |ψ̂^{(ℓ_{0})}(ξ)|

for k + ℓ_{0} ≤ L. The second part is

\begin{aligned}& \frac{1}{2π} ∫_{|t|<1/h} |f̂(t)| | ∑_{j≠0} c_{k,h,j}(t)|dt \\ = & \frac{h^{−k}}{2π} ∫_{|t|<1/h} |f̂(t)| ∑_{j≠0} |2πj + ht|^{k}|ψ̂(2πj + ht)|dt \\ = & \frac{h^{−k+ℓ_{1}}}{2πℓ_{1}!} ∫_{|t|<1/h} |f̂(t)| |t|^{ℓ_{1}} ∑_{j≠0} |2πj + ht|^{k}|ψ̂^{(ℓ_{1})}(2πj + htτ_{j}(ht))|dt \\ ≤ & \frac{h^{ℓ_{1}−k}}{2πℓ_{1}!} B_{ℓ_{1}}(f)D_{k,ℓ_{1}}(ψ). \end{aligned}  (2.12)

Now everything combines into the assertion of the theorem. □

Remarks: The principal consequence of Theorem 2.1 is that the rate of convergence of derivatives is mainly tied to ℓ_{0}, while the admissible orders of derivatives are mainly controlled by ℓ_{1}. Thus, a small value of ℓ_{0} together with a large value of ℓ_{1} will provide slow convergence of high–order derivatives, and vice versa. The next section will provide techniques for modification of given quasi–interpolants in order to yield higher values of ℓ_{0} and ℓ_{1}.

3 Increase of Approximation Order

We first consider simple techniques to improve the approximation order of a quasi–interpolant by suitable modifications that imply an increase of ℓ_{0}. This has been done already by [3], [4], [8], [16] and possibly others, but we shall include the explicit construction recipe for completeness and in order to be able to refer to it in the next section.

Let a quasi–interpolant (2.1) be generated by a given symmetric function ψ with ψ̂ ∈ C^{ℓ_{2}}(IR), and let the assumptions of Theorem 2.1 be satisfied. Then ℓ_{0} ≤ ℓ_{2} holds by definition, but there is a finite linear combination φ of translates of ψ such that φ satisfies Theorem 2.1 with ℓ_{0} replaced by ℓ_{2} and with an appropriately modified constant C. In other words: By taking fixed linear combinations of ψ one can always push ℓ_{0} up to ℓ_{2}.

Indeed, by Taylor’s formula we have

ψ̂(t) = q(t^{2}) + O(t^{ℓ_{2}}) for t → 0

with a polynomial q satisfying q(0) = 1. Then there is another polynomial p with p(0) = 1 and

p(t^{2})q(t^{2}) = 1 + O(t^{ℓ_{2}}) for t → 0,

which implies

p(t^{2})ψ̂(t) = 1 + O(t^{ℓ_{2}}) for t → 0.

Now let the trigonometric polynomial

T (e^{it}) = ∑_{j} d_{j}e^{ijt} = p(t^{2}) + O(t^{ℓ_{2}})

be a sufficiently good approximation of p around the origin. Then one defines

φ(x) = ∑_{j} d_{j}ψ(x + j)

to get

\begin{aligned}φ̂(t) & = & ψ̂(t) · T (e^{it}) \\ & = & 1 + O(t^{ℓ_{2}}) for t → 0. \end{aligned}

This makes Theorem 2.1 applicable for ℓ_{0} replaced by ℓ_{2}, and the constants C_{k} and D_{k,m} of the preceding section will take an additional factor ∑_{j} |d_{j}|.

4 Increase of the Order of Derivatives

We now want to modify a function ψ in such a way that ℓ_{1} is increased. This will boost up the bound on the order of convergent derivatives, and it will be done via smoothing by convolution. We shall first consider convolution with B–splines, and later we shall employ discrete convolution to get a numerically accessible quasi–interpolant based on the introduction of additional shifts of ψ with spacing h^{2}. Our assumptions on ψ will be much weaker than those required by Theorem 2.1, but the quasi -interpolation constructed by function φ, resulting from our construction, will have the same error bounds as given by Theorem 2.1 with ℓ_{1} = ℓ.

Theorem 4.1 Let ψ ∈ C^{ℓ} with ψ̂ ∈ Ł_{1}(IR) be a basis function for quasi–interpolation, and assume

C^{0}(ψ) = max_{0≤ξ≤1} ∑_{j=−∞}^{+∞}|ψ(ξ − j)| < ∞, .

If B_{ℓ} is the ℓ–th order symmetric uniform B–spline, then the basis function φ_{ℓ} = ψ ∗ B_{ℓ−1} satisfies Theorem 2.1 with ℓ_{1}(φ_{ℓ}) = ℓ. Thus φ_{ℓ} satisfies the Strang -Fix condition of order ℓ and

C_{k}(φ_{ℓ}) < ∞, 0 ≤ k ≤ ℓ.  (4.1)

Proof: Let χ = χ_{[−1/2,1/2]} be the characteristic function on [−1/2, 1/2], and define the B–spline

B_{m−1} = χ ∗ ⋯ ∗ χ

as the m–fold convolution of χ with itself. Now we define

φ_{m} := B_{m−1} ∗ ψ = χ ∗ φ_{m−1}

for 1 ≤ m ≤ ℓ, φ_{0} := ψ . Then

φ̂_{ℓ}(t) = B̂_{ℓ−1}(t) · ψ̂(t) = ψ̂(t) · sinc^{ℓ} (\frac{t}{2} )

has the required behaviour at all points 2πj, j ∈ ZZ \ {0}. It remains to show (4.1), and this

follows from

\begin{aligned}C_{k}(φ_{ℓ}) & = & C_{0}(D^{k}φ_{ℓ}) = C_{0} (ψ ∗ B_{ℓ−1}^{(k)}) \\ & ≤ & C_{0}(ψ)∥B_{ℓ−1}^{(k)}∥_{1}, \end{aligned}

where we interpret the norm in the last line as the total mass of the measure B_{k−1}^{(k)} for k = ℓ.

Now we have constructed a function φ_{ℓ} from the function ψ by convolution such that the function φ_{ℓ} satisfies the Strang - Fix condition of order ℓ and Theorem 2.1 with ℓ_{1}(φ) = ℓ. Unfortunately, the function φ_{ℓ} is defined by convolution and is not expressible via translates of the original function ψ. Thus we now pick a B-spline of sufficiently high order and take the discrete convolution instead of the usual convolution. If we replace the integration by a high-order quadrature formula for equidistant data, we can replace φ_{ℓ} by a function φ_{ℓ,h}, depending on ℓ and h, which is a linear combination of translates ψ(x − jh), such that

||φ_{ℓ,h}^{(k)} − φ_{ℓ}^{(k)}||_{∞} = O(h^{ℓ+1})  (4.2)

holds for h → 0. Note that for this construction we have to take a B-spline of order m ≥ ℓ + k + 2 in order to make the right-hand side of (4.2) independent of k by maintaining C^{ℓ} smoothness of the integrand ψ(·)B_{m}^{(k)}(x − ·). We get an additional factor h from the length O(h) of the domain of integration. If we define Q_{h}f as the quasi- interpolation of (2.1) with ψ := φ_{ℓ,h} and Q̃_{h}f with ψ := φ_{ℓ}, then for f ∈ L_{1}(IR) we find

\begin{aligned}& ||Q_{h}^{(k)}f − Q̃_{h}^{(k)}f||_{∞} \\ = & max_{x} | ∑_{j=−∞}^{∞} f(jh)(φ_{ℓ,h}^{(k)}(\frac{x}{h} − j) − φ_{ℓ}^{(k)}(\frac{x}{h} − j))| \\ ≤ & ( ∑_{j=−∞}^{∞} |f(jh)|) max_{y}(|φ_{ℓ,h}^{(k)}(y) − φ_{ℓ}^{(k)}(y)|) h^{−k} \\ = & O(h^{ℓ−k}). \end{aligned}  (4.3)

We summarize the above discussion to our main theorem

Theorem 4.2 If ψ(x) ∈ C^{ℓ}, ||ψ^{(ℓ)}||_{∞} < ∞, C_{0}(ψ) < ∞, and ψ̂ ∈ L_{1}(IR), then there is a function φ_{ℓ,h} consisting of linear combinations of the translates ψ(x − jh), such that the quasi interpolation (2.1) with ψ := φ_{ℓ,h} has the error estimate

||f_{h}^{(k)}(x) − f^{(k)}(x)||_{∞} = O(h^{ℓ−k}), 0 ≤ k ≤ ℓ

for any function f ∈ L_{1} with B_{2ℓ}(f) < ∞.

Proof : By the construction of Section 3 there is a trigonometric polynomial

T (e^{it}) = ∑ d_{j}e^{ijt},

and by Theorem 4.1 there is a B-spline of degree ℓ such that the function

φ_{ℓ} = ∑ d_{j}B^{ℓ} ∗ ψ(· − j)

satisfies the complete Strang - Fix condition of order ℓ, in other words it satisfies the conditions of Theorem 2.1 with ℓ_{0} = ℓ_{1} = ℓ. Using discrete convolution with a quadrature formula we get a function φ_{ℓ,h} such that the order of the approximation is estimated as in (4.3). Then Theorem 2.1 yields our assertion.

Remark : Our construction can be summarized as follows: If ψ ∈ C^{ℓ} satisfies the mild additional conditions of Theorem 4.2, we can construct quasi -interpolants in the form

\begin{aligned}Qf_{h}(x) & = & ∑_{j=−∞}^{+∞} f(hj)φ_{ℓ,h} (\frac{x}{h} − j) , x ∈ IR, h > 0 \\ & = & ∑_{j=−∞}^{+∞} f(hj) · ∑_{k} c{(ℓ) \atop k} (h)ψ (\frac{x}{h} − j − kh) \end{aligned}  (4.4)

with approximation order ℓ, where φ_{ℓ,h}(x) is a linear combination of translates ψ(x − jh) of the function ψ but depends on h. Note that the data are still sampled at points with distance h, while the set of scaled translates of ψ now uses shifts h and h^{2}. In the terminology of approximation from shift–invariant spaces these functions live in a scale {S_{h^{2}}} instead of {S_{h}}, and therefore a general optimal approximation in these spaces can and will have a better approximation order. However, our special linear quasi–interpolant uses function values of spacing h only. The increase of approximation order, as described in this section, is achieved by using more basis functions, not by using more data. The order of convergence of such operators can be pushed up to a limit that only depends on the smoothness of the function ψ. This approach can be generalized to the multivariate setting by using discrete convolutions with tensor products of odd-degree B -splines.

Example 1: For multiquadrics ϕ(x) = \sqrt{c^{2} + x^{2}}, we choose at first ψ(x) = (ϕ(x+1)−2ϕ(x)+ ϕ(x − 1)). Then ℓ_{1}(ψ) = 2, and with the Strang-Fix condition we get the approximation order 2, which is similar to results in [2] [7] [19]. But references [11] [20] imply that the order of approximation by interpolation exceeds any ℓ, if the function f is very smooth and if c is fixed. Note here that the usual Strang- Fix theory scales c like O(h) for h → 0. Our result bridges the gap between these two approaches. Since ψ^{(k)}(x) = O(x^{−(k+3)}), we can construct for any ℓ a quasi-interpolant with approximation order ℓ for functions f ∈ L_{1} with B_{2ℓ}(f) < ∞.

Example 2: (see also [1]). The Gaussian distribution ψ(x) = e^{−a^{2}x^{2}} is often criticized in the literature on radial basis functions, because it fails to satisfy the Strang-Fix conditions. But by [17] for some very smooth functions f the order of approximation can exceed any ℓ. Using Theorem 4.2 for any ℓ we can always construct a quasi-interpolant with approximation order ℓ for f ∈ L_{1} and B_{2ℓ}(f) < ∞.

Example 3: The function ψ(x) = (1 − x^{2})_{+}^{ℓ+1} satisfies no Strang-Fix condition, but from our approach the approximation order of the quasi- interpolation (4.4) is at least ℓ. We can get a similar result for B -splines, too. Acknowledgement: The authors thank the referees for a shortcut to the proof of (4.1) and for several suggestions that helped to avoid some serious misunderstandings in relation to previous work on approximation orders.

References

[1] Beatson, R.K., & W.A. Light, Quasi–interpolation in the obsence of polynomial reproduction. In: Numerical Methods of Approximation Theory, Vol. 9, Birkhäuser, D. Braess and L.L. Schumaker (eds.), 1992, 21–39.

[2] Beatson, R. K. & M. J. D. Powell, Univariate multiquadric approximation: quasi interpolation to scattered data, DAMTP 1990/NA, University of Cambridge.

[3] Boor, C. de, The polynomials in the linear space of integer translates of a compactly supported function. Constructive Approximation 3 (1987), 199–208.

[4] Boor, C. de, Quasi–interpolants and approximation power of multivariate splines. In: Computation of Curves and Surfaces, Kluwer, Dordrecht, W. Dahmen, M. Gasca and C.A. Micchelli (eds.), 1990, 313–345.

[5] Boor, C. de, R.A. DeVore, & A. Ron, Approximation from shift–invariant subspaces of L_{2}(IR^{d}). Trans. Amer. Math. Soc. 341 (1994), 787–806.

[6] Boor, C. de & A. Ron, Fourier analysis of approximation orders from principal shift– invariant spaces. Constructive Approximation 8 (1992), 427–462.

[7] Buhmann, M. D., Multivariable interpolation using Radial Basis Functions. Ph.D. dissertation, University of Cambridge 1989.

[8] Chui, C.K. & H. Diamond, A natural formulation of quasi–Interpolation by multivariate splines, Proc. Am. Math. Soc. 99 (1987), 643–646.

[9] Dyn, N. & A. Ron, Local approximation by certain spaces of multivariate exponential polynomials, approximation order of exponential box splines and related interpolation problems, Trans. Amer. Math. Soc. 319 (1990), 381–404.

[10] Light, W. A., Some aspects of radial basis function approximation. In: Approximation Theory, Spline Functions and Applications, S.P.Singh (ed.), NATO ASI Series 356 (1992), 163-190.

[11] Madych, W. A. & S. A. Nelson, Error Bounds for multiquadric Interpolation. In: Approximation Theory VI: vol 2, C. K. Chui, L. L. Schumaker and J.D. Ward (eds.) 1989, 413-416.

[12] Micchelli, C. A., Interpolation of scattered data: distance matrix and conditionally positive definite functions. Constructive Approximation 2 (1986), 11-22.

[13] Powell, M. J. D., Radial basis functions for multivariable interpolation: a review. In: Numerical Analysis, D. F. Griffiths and G. A. Watson (eds.), Longman Scientific & Technical (Harlow), 1987, 223-241.

[14] Ron, A, Approximation orders from principal shift–invariant spaces generated by a radial basis function. In: Numerical Methods of Approximation Theory, Vol. 9, Birkhäuser, D. Braess and L.L. Schumaker (eds.), 1992, 245–268.

[15] Schaback, R., Error estimates and condition numbers for radial basis function interpolation. Advances in Computational Mathematics 3 (1995), 251–264.

[16] Strang, G., & G. Fix,, A Fourier analysis of the finite element variational method, C.I.M.E. II Ciclo 1971. In: Constructive Aspects of Functional Analysis, G. Geymonat (ed.), 1973, 793–840.

[17] Wu, Z., Die Kriging Methode zur Lösung mehrdimensionaler Interpolationsprobleme. Ph. D. dissertation, Universität Göttingen 1986.

[18] Wu, Z., Hermite-Birkhoff interpolation of scattered data by radial basis function. Approx. Theory & its Appl. 8:2 (1992), 1–10.

[19] Wu, Z., & R. Schaback, Shape preserving properties and convergence of univariate multiquadric quasi–interpolation. Acta Mathematicae Applicatae Sinica 10:4 (1994), 441–446.

[20] Wu, Z. & R. Schaback, Local error estimates for radial basis function interpolation of scattered data, IMA Journal of Numerical Analysis 13 (1993), 13-27.