Shape preserving properties and convergence of univariate multiquadric quasi–interpolation

Zong–min Wu

Robert Schaback

Abstract: With a suitable modification at the endpoints of the range, quasi–interpolation with univariate multiquadrics ϕ(x) = \sqrt{c^{2} + x^{2}} is shown to preserve convexity and monotonicity. If h is the maximum distance of centres, convergence of the quasi–interpolant is of order O(h^{2}| log h|) if c = O(h). The log term can not be removed by introducing different boundary conditions or special placements of the centres.

Keywords: multiquadric, quasi–interpolation, shape preservation, approximation rate.

Classification: 65D05, 65D07, 41A05, 41A63

1 Introduction

Quasi–interpolation of a function f : [a, b] → IR with multiquadrics on the scattered points

a = x_{0} < x_{1} < … < x_{n} = b h := max_{1≤i≤n}(x_{i} − x_{i−1})  (1.1)

has the form

(M_{D}f)(x) = ∑_{j=0}^{n} f(x_{j})ψ_{j}(x),  (1.2)

where ψ_{j}(x) are linear combinations of the multiquadrics

ϕ_{j}(x) = \sqrt{c^{2} + (x − x_{j})^{2}}.  (1.3)

These functions were proposed by Hardy (1971), and they performed well in many calcalculations including the numerical experiments that were reported by Franke (1980). The existence of the solution of the associated interpolation problem was shown by Micchelli (1986), while Buhmann (1988) discussed the accuracy of quasi–interpolation for infinite regular grid data. Error estimates for the interpolation of scattered data in IR^{k} were proven by Madych and Nelson (1990) and Wu and Schaback (1990) for a restricted class of interpolated functions f, while Beatson and Powell (1990) derived general error bounds of type O(h^{2} log h) for quasi– interpolation to univariate scattered data from C^{2} functions.

1File : usr/nam/rschaba/tex/fertig/wu rs 2.tex, TEXed 17. Mai 1994, Status : Not submitted

Since \sqrt{c^{2} + x^{2}} tends to |x| as c tends to zero, and radial basis interpolation (as well as quasi– interpolation) based on |x| is piecewise linear interpolation, the shape–preserving properties of piecewise linear interpolation can be expected to hold for quasi–interpolation with multiquadrics, too. In the next section we show that the quasi–interpolation operator L_{C} of Beatson and Powell (1990) is indeed convexity preserving. It requires the derivatives of the function f at the endpoints. In section 3 we give a quasi–interpolation (denoted as L_{D}) based on the data {f(x_{j}^{n})}_{j=0}^{n} only, and show that L_{D} preserves convexity, linearity, and monotonicity. Beatson and Powell (1990) proved that the accuracy of L_{C} is O(h^{2} log h) if c varies as c = O(h). In section 4 we shall show a similar error bound for L_{D}, employing a different proof technique.

2 The convexity preserving property of L_{C}

For f ∈ C^{1}[x_{0}, x_{n}] the quasi–interpolation operator L_{C} of Beatson and Powell (1990) is defined as

(L_{C}f)(x) = f′_{0}γ_{0}(x) + f_{0}β_{0}(x) + ∑_{j=1}^{n−1} f_{j}ψ_{j}(x) + f_{n}β_{n}(x) + f′_{n}γ_{n}(x)  (2.1)

where ϕ_{j} are defined in (1.3) and

ψ_{j}(x) = \frac{ϕ_{j+1}(x) − ϕ_{j}(x)}{2(x_{j+1} − x_{j})} − \frac{ϕ_{j}(x) − ϕ_{j−1}(x)}{2(x_{j} − x_{j−1})}, 1 ≤ j ≤ n − 1,  (2.2)

β_{0}(x) = \frac{1}{2} + \frac{ϕ_{1}(x) − ϕ_{0}(x)}{2(x_{1} − x_{0})}, β_{n}(x) = \frac{1}{2} + \frac{ϕ_{n−1} − ϕ_{n}(x)}{2(x_{n} − x_{n−1})}  (2.3)
γ_{0}(x) = \frac{1}{2} (x − x_{0}) − \frac{1}{2} ϕ_{0}(x), γ_{n}(x) = \frac{1}{2} ϕ_{n}(x) − \frac{1}{2} (x_{n} − x)  (2.4)
f_{j} = f(x_{j}), 0 ≤ j ≤ n, f′_{i} = f′(x_{i}), i = 0, n.

Theorem 1: If the data {f(x_{j})}_{j=0}^{n}, f′(x_{0}), f′(x_{n}) stem from a convex (concave, linear) function f ∈ C^{1}[x_{0}, x_{n}], then L_{C}f(x) is a convex (concave, linear) function.

Proof. Using

ϕj^{′′}(x) = \frac{c^{2}}{(c^{2} + (x − x_{j})^{2})^{3/2}} ≥ 0  (2.5)

and (2.1) to (2.4) we can write (L_{C}f)′′(x) as

(L_{C}f)′′(x) = f′_{0}γ0^{′′}(x) + f_{0}β0^{′′}(x) + ∑_{j=1}^{n−1} f_{j}ψj^{′′}(x) + f_{n}βn^{′′}(x) + f′_{n}γn^{′′}(x)

= −f′_{0} \frac{ϕ0^{′′}(x)}{2} + f_{0} \frac{ϕ1^{′′}(x) − ϕ0^{′′}(x)}{2(x_{1} − x_{0})} + f_{n} \frac{ϕn−1^{′′}(x) − ϕn^{′′}(x)}{2(x_{n} − x_{n−1})} + f′_{n} \frac{ϕn^{′′}}{2}

+\frac{1}{2} ∑_{j=1}^{n−1} f_{j} [\frac{ϕj+1^{′′}(x) − ϕj^{′′}}{x_{j+1} − x_{j}} − \frac{ϕj^{′′}(x) − ϕj−1^{′′}(x)}{x_{j} − x_{j−1}}]

\begin{aligned}= & \frac{1}{2} [\frac{f_{1} − f_{0}}{x_{1} − x_{0}} − f′_{0}] ϕ0^{′′}(x) + \frac{1}{2} ∑_{j=1}^{n−1} [\frac{f_{j+1} − f_{j}}{x_{j+1} − x_{j}} − \frac{f_{j} − f_{j−1}}{x_{j} − x_{j−1}} ] ϕj^{′′}(x) \\ & +\frac{1}{2} [f′_{n} − \frac{f_{n} − f_{n−1}}{x_{n} − x_{n−1}} ] ϕn^{′′}(x) \end{aligned}  (2.6)

If the data {f(x_{j})}_{j=0}^{n}, f(x_{0}), f′(x_{n}) stem from a convex function f, all the terms in square brackets of (2.6) are nonnegative. The other cases are similar. □

The quasi–interpolation operators L_{A} and L_{B} by Beatson and Powell (1990) do not contain linear functions, and therefore they cannot preserve both linearity and convexity.

3 The shape preserving properties of L_{D}

The quasi–interpolation operator L_{C} of (2.1) requires derivatives of f at endpoints. It is not very convenient for practical purposes. Therefore we define a new quasi–interpolation operator L_{D} as

(L_{D}f)(x) = f_{0}α_{0}(x) + f_{1}α_{1}(x) + ∑_{j=2}^{n−2} f_{j}ψ_{j}(x) + f_{n−1}α_{n−1}(x) + f_{n}α_{n}(x)  (3.1)

where

\begin{matrix}α_{0}(x) = \frac{1}{2} + \frac{ϕ_{1}(x) − (x − x_{0})}{2(x_{1} − x_{0})}, α_{1}(x) = \frac{ϕ_{2}(x) − ϕ_{1}(x)}{2(x_{2} − x_{1})} − \frac{ϕ_{1}(x) − (x − x_{0})}{2(x_{1} − x_{0})} \\ α_{n−1}(x) = \frac{(x_{n} − x) − ϕ_{n−1}(x)}{2(x_{n} − x_{n−1})} − \frac{ϕ_{n−1}(x) − ϕ_{n−2}(x)}{2(x_{n−1} − x_{n−2})}, α_{n}(x) = \frac{1}{2} + \frac{ϕ_{n−1}(x) − (x_{n} − x)}{2(x_{n} − x_{n−1})}. \end{matrix}

(3.2)

Then

\begin{aligned}(L_{D}f)′′(x) & = & f_{0}α0^{′′}(x) + f_{1}α1^{′′}(x) + ∑_{j−2}^{n−2} f_{j}ψj^{′′}(x) + f_{n−1}αn−1^{′′}(x) + f_{n}αn^{′′}(x) \\ & = & \frac{1}{2} ∑_{j=1}^{n−1} [\frac{f_{j+1} − f_{j}}{x_{j+1} − x_{j}} − \frac{f_{j} − f_{j−1}}{x_{j} − x_{j−1}} ] ϕj^{′′}(x) \end{aligned}  (3.3)

proves

Theorem 2: If the data {f(x_{j})}_{j=0}^{n} stem from a convex (concave, linear) function, then the quasi–interpolant L_{D}f(x) as defined by (3.1) and (3.2) is a convex (concave, linear) function. □

The first order derivative of ϕ(x) is x·(c^{2}+x^{2})^{−1/2}. It is monotonic because of (2.5) and satisfies

lim_{x→±∞} ϕ′(x) = ±1.  (3.4)

Thus, for all x ∈ IR,

− 1 ≤ ϕ′_{j}(x) ≤ ϕ′_{j−1}(x) ≤ 1.  (3.5)

The derivative of (L_{D}f)(x) can be calculated as

\begin{aligned}(L_{D}f)′(x) & = & \frac{ϕ1^{′}(x) − 1}{2(x_{1} − x_{0})} f_{0} + [\frac{ϕ′_{2}(x) − ϕ′_{1}(x)}{2(x_{2} − x_{1})} − \frac{ϕ′_{1}(x) − 1}{2(x_{1} − x_{0})}] f_{1} \\ & & +∑_{j=2}^{n−2} [\frac{ϕ′_{j+1}(x) − ϕ′_{j}(x)}{x_{j+1} − x_{j}} − \frac{ϕ′_{j}(x) − ϕ′_{j−1}(x)}{x_{j} − x_{j−1}} ] f_{j} \\ & & +[−\frac{1 + ϕ′_{n−1}(x)}{2(x_{n} − x_{n−1})} − \frac{ϕ′_{n−1}(x) − ϕ′_{n−2}(x)}{2(x_{n−1} − x_{n−2})}] f_{n−1} + [\frac{ϕ′_{n−1}(x) + 1}{2(x_{n} − x_{n−1})}] f_{n} \\ & = & (\frac{1 − ϕ′_{1}(x)}{2(x_{1} − x_{0})}) (f_{1} − f_{0}) + ∑_{j=1}^{n−2} (\frac{ϕ′_{j}(x) − ϕ′_{j+1}(x)}{2(x_{j+1} − x_{j})}) (f_{j+1} − f_{j}) \\ & & + (\frac{1 + ϕ′_{n−1}(x)}{2(x_{n} − x_{n−1})}) (f_{n} − f_{n−1}) \end{aligned} (3.6)

If the data {f_{j}}_{j=0}^{n} satisfy f_{j} ≤ f_{j+1} then all the terms are nonnegative. This proves

Theorem 3: The quasi–interpolation L_{D} is monotonicity preserving. □

Remark. Comparison of (2.6) and (3.3) shows that L_{C} is just a Hermite–Birkhoff variation of L_{D}. □

4 The accuracy of the quasi–interpolation L_{D}

The results of Beatson and Powell (1990) suggest a O(h^{2}| log h|) behaviour of the error of quasi–interpolation by multiquadrics, if c(h) = O(h). Their proof technique, however, can not be directly generalized to the case considered here, because the basis functions of L_{D} are not generally positive (consider x_{0} → x_{1} for c > 0 in α_{1}(x) of (3.2)). A rather simple direct technique will be applied to get, as can be expected,

Theorem 4. For f ∈ C^{2}[a, b] the quasi–interpolant L_{D}f defined by (3.1) on the points (1.1) satiesfies an error estimate of type

∥f − L_{D}f∥_{∞} ≤ K_{1}h^{2} + K_{2}ch + K_{3}c^{2} log h

for h → 0 with suitable positive constants K_{1}, K_{2}, and K_{3}, independent of h and c.

Proof. The quasi–interpolation operator L_{D} can be rearranged as

\begin{aligned}2(L_{D}f)(x) & = & ∑_{j=1}^{n−1} ϕ_{j}(t)(x_{j+1} − x_{j−1})Δ^{2}(x_{j−1}, x_{j}, x_{j+1})f + f_{0} + f_{n}+ \\ & + & (x − x_{0})Δ^{1}(x_{0}, x_{1})f − (x_{n} − x)Δ^{1}(x_{n−1}, x_{n})f \end{aligned}

with divided differences Δ^{1} and Δ^{2} of first and second order, respectively. The difference to the piecewise linear interpolant Lf of f then is

2(L_{D}f − Lf)(x) = ∑_{j=1}^{n−1}(ϕ_{j}(x) − |x − x_{j}|)(x_{j+1} − x_{j−1})Δ^{2}(x_{j−1}, x_{j}, x_{j+1})f,  (4.1)

and we want to bound the function

\begin{aligned}0 ≤ φ(x) & := & ∑_{j=1}^{n−1}(ϕ_{j}(x) − |x − x_{j}|)(x_{j+1} − x_{j−1}) \\ & = & ∑_{j=1}^{n−1}(\sqrt{c^{2} + |x − x_{j}|^{2}} − |x − x_{j}|)(x_{j+1} − x_{j−1}). \end{aligned}

Splitting the sum in one part with |x − x_{j}| ≤ h and the rest, the two estimates

\begin{aligned}\sqrt{c^{2} + y^{2}} − |y| & ≤ & c, & c & ≥ & 0, & y & ≥ & 0 \\ \sqrt{c^{2} + y^{2}} − |y| & ≤ & \frac{c^{2}}{2|y|}, & c & ≥ & 0, & y & > & 0 \end{aligned}

are applied to get

\begin{aligned}φ(x) & ≤ & c ∑_{|x−x_{j}|≤h^{j=1}}^{n−1}(x_{j+1} − x_{j−1}) + \frac{c^{2}}{2} ∑_{|x−x_{j}|>h^{j=1}}^{n−1} \frac{x_{j+1} − x_{j−1}}{|x − x_{j}|} \\ & ≤ & 8ch + c^{2}(∫_{|x−t|≥h} \frac{1}{|x − t|} dt + O(h)) , \end{aligned}

because at most four of the x_{i} remain in the first sum and the second sum is a O(h) approximation to the integral. Consequently,

φ(x) ≤ 8ch + O(c^{2} log h) + O(c^{2}h),

and this proves the assertion. □

Corollary. The quasi–interpolant L_{D}f can have an O(h^{2}) error only if at least c^{2}| log c| = O(h^{2}).

Proof. Due to (4.1) and the O(h^{2}) convergence of Lf, it suffices to bound φ(x) from below for small c tending to zero for h → 0. For this we use

\sqrt{1 + y} − 1 ≥ \frac{y}{2} − \frac{y^{2}}{4} for |y| ≤ y_{0} > 0

and keep only the terms of φ(x) with |x − x_{j}| ≥ cy_{0}^{−1}. Then

φ(x) ≥ \frac{1}{2} ∑_{|x−x_{j}|≥cy_{0}^{−1}^{j=1}}^{n−1}(x_{j+1} − x_{j−1}) (\frac{c^{2}}{|x − x_{j}|} − \frac{1}{2} \frac{c^{4}}{|x − x_{j}|^{3}} )

and this sum has the behaviour

(c^{2} ∫_{|x−t|≥cy_{0}^{−1}} \frac{1}{|x − t|} dt − \frac{c^{4}}{2} ∫_{|x−t|≥cy_{0}^{−1}} \frac{1}{|x − t|^{3}} dt) (1 + O(h))

which is dominated by c^{2}| log c| as a function of c. If c ≥ c_{0} > 0, the function φ will asymptotically have the lower bound

2 ∫_{a}^{b}(\sqrt{c_{0}^{2} + (x − t)^{2}} − |x − t|)dt > 0. □

Remark. The technique of this paper clearly shows that no improvement towards O(h^{2}) convergence is possible just by changes of end conditions or knot placements, provided that the ψ_{j}(x) are used in the interior of the domain.

5 References

R.K. Beatson and M.J.D. Powell (1990). Univariate multiquadric approximation: quasi– interpolation to scattered data. DAMTP 1990 / NA7, University of Cambridge M.D. Buhmann (1988). Multivariate interpolation with radial basis functions. Report DAMTP 1988/NA8. University of Cambridge R. Franke (1982). Scattered data interpolation: tests of some methods. Math. Comp., Vol. 38, pp. 181–200 R.L. Hardy (1971). Multiquadric equations of topography and other irregular surfaces. J. Geophysical Res., Vol. 76, pp. 1905–1915 Madych, W.R.; and Nelson, S.A., Error Bounds for Multiquadric Interpolation, in: C.K. Chui, L.L. Schumaker, and J.D. Ward (eds.), Approximation Theory VI, Vol. 2, 413–416 C.A. Micchelli (1986). Interpolation of scattered data: distance matrices and conditionally positive definite functions. Constr. App., Vol. 2, pp 11–22 Z. Wu and R. Schaback: Local Errror Estimates for Radial Basis Function Interpolation of Scattered Data, Preprint

Author’s addresses: Zong–min Wu, Dept. of Mathematics Fudan University, Shanghai, China

Robert Schaback, Institut für Numerische und Angewandte Mathematik Universität Göttingen Lotzestr. 16–18 D – 3400 Göttingen