Trigonometric Interpolation and Quadrature in Perturbed Points
The trigonometric interpolants to a periodic function $f$ in equispaced points converge if $f$ is Dini-continuous, and the associated quadrature formula, the trapezoidal rule, converges if $f$ is continuous. What if the points are perturbed? With equispaced grid spacing $h$, let each point be perturbed by an arbitrary amount $\le \alpha h$, where $\alpha\in [\kern .5pt 0,1/2)$ is a fixed constant. The Kadec 1/4 theorem of sampling theory suggests there may be be trouble for $\alpha\ge 1/4$. We show that convergence of both the interpolants and the quadrature estimates is guaranteed for all $\alpha<1/2$ if $f$ is twice continuously differentiable, with the convergence rate depending on the smoothness of $f$. More precisely it is enough for $f$ to have $4\alpha$ derivatives in a certain sense, and we conjecture that $2\alpha$ derivatives is enough. Connections with the Fejér--Kalmár theorem are discussed.
\section{Introduction and summary of results}

The basic question of robustness of mathematical algorithms is,
what happens if the data are perturbed?  Yet little
literature exists on the effect on interpolants, or on quadratures,
of perturbing the interpolation points.

The questions addressed in this paper arise in two almost equivalent
settings: interpolation by algebraic polynomials (e.g., in
Gauss or Chebyshev points) and periodic interpolation by
trigonometric polynomials (e.g., in equispaced points).
Although we believe essentially the same results hold in
the two settings, this paper deals with just the trigonometric case.
Let $f$ be a real or complex function on $[-\pi,\pi)$, which we take
to be $2\pi$-periodic in the sense that any assumptions of
continuity or smoothness made for $f$ apply periodically at $x=-\pi$ as
well as at interior points.
For each $N\ge 0$, set $K = 2N+1$, and consider the
centered grid of $K$ equispaced points in $[-\pi,\pi)$,
\begin{equation}
x_k^{} = kh, \quad -N \le k \le N, \quad h = {2\pi\over K}.
\end{equation}
There is a unique degree-$N$ trigonometric
interpolant through the data $\{f(x_k^{})\}$, by which we mean a function
\begin{equation}
t_N^{}(x) = \sum_{k=-N}^N c_k^{} e^{ikx}
\end{equation}
with $t_N^{}(x_k^{}) = f(x_k^{})$ for each $k$.
If $I$ denotes the integral of $f$,
\begin{equation}
I = \int_{-\pi}^\pi f(x) \,dx,
\end{equation}
the associated quadrature approximation
is the integral of $t_N^{}(x)$, which can be shown to be
equal to the result of applying the trapezoidal rule to $f$:
\begin{equation}
I_N^{} = h\!\sum_{k=-N}^N f(x_k^{}) = \int_{-\pi}^\pi t_N^{}(x) \,dx = 2\pi c_0^{} .
\label{traprule}
\end{equation}
It is known that if $f$ is continuous, then
\begin{equation}
\lim_{N\to\infty} | I - I_N^{} | = 0,
\label{quadconv}
\end{equation}
and if $f$ is Dini-continuous, for which H\"older or Lipschitz continuity
are sufficient conditions, then
\begin{equation}
\lim_{N\to\infty} \| f - t_N^{} \| = 0 .
\label{approxconv}
\end{equation}
Moreover, the convergence rates are tied to the
smoothness of $f$, with exponential convergence
if $f$ is analytic.  Here and throughout,
$\|\cdot\|$ is the maximum norm on $[-\pi,\pi)$.

The problem addressed in this paper is the generalization of
these results to configurations in which
the interpolation points are perturbed. For fixed
$\alpha\in ( 0,1/2)$, consider a set of points
\begin{equation}
\tilde x_k^{} = x_k^{} + s_k^{} h, \quad -N\le k \le N,
\quad |s_k|\le \alpha \, .
\label{ppoints}
\end{equation}
Note that since $\alpha < 1/2$, the $\tilde x_k^{}$ are necessarily
distinct.  Let $\tilde t_N^{}(x)$ be the unique degree-$N$
trigonometric interpolant to $\{f(\tilde x_k^{})\}$, and let
$\tilde I_N^{} = \int \tilde t_N^{}(x) \kern .7pt dx$ be the
corresponding quadrature approximation.  As in (\ref{traprule}),
this will be a linear combination of the function values, although
no longer with equal weights in general.

Let $\sigma>0$ be any positive real number, and write $\sigma
= \nu + \gamma$ with $\gamma\in (\kern .5pt 0,1]$.  We say
that $f$ {\em has $\sigma$ derivatives} if $f$ is $\nu$
times continuously differentiable and, moreover, $f^{(\nu)}$
is H\"older continuous with exponent $\gamma$.  Note that
if $\sigma$ is an integer, then for $f$ to ``have $\sigma$
derivatives'' means that $f$ is $\sigma-1$ times continuously
differentiable and $f^{(\sigma-1)}$ is Lipschitz continuous.
We will prove the following main theorem, whose central estimate
is the bound on $\|f-\tilde t_N^{}\|$ in (\ref{thmrate2}).
The estimates (\ref{thmconv})--(\ref{thmrate2}) are new, whereas
(\ref{thmrate3}) follows from the work of Kis~\cite{kis}, as
discussed in Section~\ref{confluent}.  Numerical illustrations
of these bounds can be found in~\cite{austin}.

\medskip

\begin{theorem}
\label{thm1}
For any $\alpha\in (\kern .5pt 0,1/2)$,
if $f$ is twice continuously differentiable, then
\begin{equation}
\lim_{N\to\infty} | I - \tilde I_N^{} | =
\lim_{N\to\infty} \| f - \tilde t_N^{} \| = 0.
\label{thmconv}
\end{equation}
More precisely, if
$f$ has $\sigma$ derivatives for some $\sigma > 4\alpha$, then
\begin{equation}
| I - \tilde I_N^{} | ,
\| f - \tilde t_N^{} \| = O(N^{4\alpha-\sigma}).
\label{thmrate2}
\end{equation}
If $f$ can be analytically continued
to a $2\pi$-periodic
function for $-a < {\rm Im}\kern 2pt x < a$ for some $a>0$, then
for any\/ $\hat a < a$,
\begin{equation}
| I - \tilde I_N^{} | ,
\| f - \tilde t_N^{} \| = O(e^{-\hat aN}).
\label{thmrate3}
\end{equation}
\end{theorem}

\medskip

Our proofs are based on combining standard estimates of
approximation theory, the Jackson theorems, with a new bound
on the Lebesgue constants associated with perturbed grids,
Theorem~\ref{thmbound}.  Our bounds are close to sharp,
but not quite.  Based on extensive numerical experiments
presented in Section 3.3.2 of~\cite{austin}, we conjecture that
$4\alpha$ can be improved to $2\alpha$ in (\ref{thmrate2}) and
(\ref{bigestimate}); for (\ref{bigestimate}) the result would
probably then be sharp, but for (\ref{thmrate2}) a slight further
improvement may still be possible.  For the quadrature problem
in particular, further experiments presented in Section 3.5.2
of~\cite{austin} lead us to conjecture that $\tilde I_N^{}
\to I$ as $N\to\infty$ for all continuous functions $f$ for
all $\alpha<1/2$.  This conjecture is based on the theory of
P\'olya in 1933~\cite{polya}, who showed that such convergence
is ensured if and only if the sums of the absolute values of the
quadrature weights are bounded as $N\to\infty$.  Experiments
indicate that for all $\alpha<1/2$, these sums are indeed bounded
as required.  On the other hand, $\tilde I_N^{}\to I$ cannot be
guaranteed for any $\alpha\ge 1/2$, since in that case the
interpolation points may come together, making the quadrature
weights unbounded.

Theorems~\ref{thm1} and~\ref{thmbound} suggest that from the
point of view of approximation and quadrature, $\alpha = 1/4$
is not a special value.  In Section~\ref{sampling} we
comment on the significance of the appearance of this number
in the Kadec 1/4 theorem and more generally on the relationship
between approximation theory and sampling theory, two subjects
that address closely related questions and yet have little
overlap of literatures or experts.

All the estimates reported here were worked out by the first
author and presented in his D.\ Phil.\ thesis~\cite{austin}.
This work was motivated by work of the second author with
Weideman in the review article ``The exponentially convergent
trapezoidal rule''~\cite{tw}.  It is well known that on an
equispaced periodic grid, the trapezoidal rule is exponentially
convergent for periodic analytic integrands~\cite{davis,tw}.
With perturbed points, it seemed to us that exponential
convergence should still be expected, and we were surprised
to find that there seemed to be no literature on this subject.
A preliminary discussion was given in~\cite[Sec.~9]{tw}.

Section~\ref{lebesguesec} reduces Theorem~\ref{thm1} to a
bound on the Lebesgue constant, Theorem~\ref{thmbound}.
Sections~\ref{confluent} and \ref{sampling} are devoted
to comments on problems with $\alpha\ge 1/2$ and on
the link with sampling theory and Kadec's theorem,
respectively.  Section~\ref{bound} outlines the proof of
Theorem~\ref{thmbound}.

\section{\label{lebesguesec}Reduction to a Lebesgue constant estimate}

A fundamental tool of approximation theory is the Lebesgue
constant: for any linear projection $L:f\mapsto t$, the
Lebesgue constant is the operator norm $\Lambda = \|L\|$.
For our problem the operator is the map $\tilde L_N^{}$ from a
function $f$ to its trigonometric interpolant $\tilde t_N^{}$
through the values $\{f(\tilde{x}_k^{})\}$, and the norm on $L$
is the operator norm induced by $\|\cdot\|$, the $\infty$-norm
on $[-\pi,\pi)$.  We denote the Lebesgue constant by $\tilde
\Lambda_N$.

Lebesgue constants are linked to quality of approximations
by the following well-known bound.  If
$\tilde \Lambda_N^{}$ is the Lebesgue constant
associated with the projection $\tilde L_N^{}:
f \mapsto \tilde t_N^{}$ and $t_N^*$ is the best approximation to
$f$ of degree $N$, then
\begin{equation}
\|f-\tilde t_N^{}\| \le (1+\tilde \Lambda_N^{}) \| f-t_N^*\| .
\label{basicbound}
\end{equation}
It follows that if $\tilde \Lambda_N^{}$ is small, then $\tilde
t_N^{}$ is a near-optimal approximation to $f$.  If $f$ has
a certain smoothness property for which the optimal approximations
$t_N^*$ are known to converge at a certain rate, this
implies that the interpolants $\tilde t_N^{}$ converge at nearly
the same rate.

Applying (\ref{basicbound}), we prove Theorem~\ref{thm1}
by combining a bound on the Lebesgue constants $\tilde
\Lambda_N^{}$ with bounds on the best approximation errors $\|f-
t_N^*\|$.  Our estimates of best approximations are standard
Jackson theorems, going back to Dunham Jackson in 1911 and 1912.
The nonstandard part of the argument, which from a technical
point of view is the main contribution of this paper, is the
following estimate of the Lebesgue constant, the proof of which
is outlined in Section~\ref{bound}.

\medskip

\begin{theorem}
\label{thmbound}
There is a universal constant $C$ such that
\begin{equation}
\tilde \Lambda_N^{} \le {C(N^{4\alpha}-1)\over \alpha(1-2\alpha)}
\label{bigestimate}
\end{equation}
for all\/ $\alpha\in [\kern .5pt 0,1/2)$ and $N> 0$.
For $\alpha=0$ this bound is to be interpreted by its
limiting value given, for example, by L'Hopital's rule,
$\tilde\Lambda_N^{} \le 4\kern1pt C\log N$.
\end{theorem}

\medskip

The $\log N$ bound for an equispaced grid with $\alpha = 0$
is standard, so the substantive result here concerns $\alpha\in
(0,1/2)$.  This is what we can prove, but as mentioned in the
previous section, based on numerical experiments, we conjecture that
(\ref{bigestimate}) actually holds with $N^{4\alpha}$ replaced
by $N^{2\alpha}$.

Given Theorem~\ref{thmbound}, we prove Theorem~\ref{thm1} as follows.

\medskip

{\em Proof of Theorem\/~$\ref{thm1}$, given Theorem\/~$\ref{thmbound}$.}
The Jackson theorems of approximation theory relate the smoothness
of a function $f$ to the accuracy of its best
approximations~\cite{jackson,meinardus}.
According to one of these theorems, given for example as
Theorem~41 of~\cite{meinardus},
if $f$ is a periodic function
on $[-\pi,\pi)$ that has $\sigma$ derivatives for
some $\sigma>0$ in the sense defined in Section 1, then
\begin{equation}
\| f-t_N^*\|  = O(N^{-\sigma}).
\end{equation}
Combining this with Theorem~\ref{thmbound}
gives (\ref{thmrate2}).  The bound (\ref{thmrate3})
follows similarly from the estimate
\begin{equation}
\| f-t_N^*\|  = O(e^{-\hat aN})
\end{equation}
for any $2\pi$-periodic function $f$ analytic and bounded in
the strip of half-width $\hat a>0$ about the real axis; see, for
example, eq.~(7.17) of~\cite{tw}. \endproof

\section{\label{confluent}\boldmath $\alpha \ge 1/2$, confluent
points, and analytic functions} Our framework (\ref{ppoints}) for
perturbed points can be generalized to values $\alpha \ge 1/2$.
For $\alpha\in [1/2, 1)$, two grid points may coalesce, so one
must assume that $f'$ exists in order to ensure that there are
appropriate data to define an interpolation problem (in this case,
trigonometric Hermite interpolation).  Similarly for $\alpha\in
[1,3/2)$, three points may coalesce, so one must assume $f''$
exists; and so on analogously for any finite value of $\alpha$.
(We wrap grid points around as necessary if the perturbation moves
them outside of $[-\pi, \pi)$; equivalently, one could extend $f$
periodically.)

Looking at the statement of Theorem~\ref{thm1} but considering
values $\alpha \ge 1/2$, one notes that the assumption of
$\sigma>4\alpha$ derivatives is enough to ensure that the necessary
derivatives exist for the interpolation problem to make sense; the
conjectured sharper condition of $\sigma> 2\alpha$ derivatives is
also (\kern .7pt just) enough.  This coincidence seems suggestive,
and we consider it possible that Theorem~\ref{thm1} and its
conjectured improvement with $2\alpha$ may in fact be valid for
arbitrary $\alpha>0$, not just $\alpha \in (\kern .5pt 0,1/2)$.
We have not attempted to prove this, however.  As a practical
matter, trouble can be expected in floating-point arithmetic as
sample points coalesce, so we regard the case $\alpha \ge 1/2$
as somewhat theoretical.

Going further, what if we allow arbitrary perturbations of the
interpolation points, so that each $\tilde x_k^{}$ may lie
anywhere in $[-\pi,\pi)$?  Doing so makes sense mathematically
if $f$ is infinitely differentiable; so in particular, it
makes sense if $f$ is analytic, which implies that it can be
analytically continued to a $2\pi$-periodic function on the
whole real line.  We are now in an area of approximation theory
(and potential theory) going back to the work of Runge~\cite{runge}
and Fej\'er~\cite{fejer}, in which a major contributor was Joseph
Walsh~\cite{gaier,walsh}.  For arbitrary $x_k^{}$, convergence
will occur if $f$ is analytic in a sufficiently wide strip around
the real axis in the complex $x$-plane.  Repeated points
are permitted, with interpolation at such points interpreted
in the Hermite sense involving values of both the function
and its derivatives.  If the points $x_k$
are {\em uniformly distributed\/} in the sense that the fraction
of points falling in any interval $[a,b)\subseteq [-\pi,\pi)$
converges to $(b-a)/2\pi$ as $N\to\infty$, then it is enough for
$f$ to be analytic in {\em any\/} strip around the real axis.
Such results were first developed for polynomial approximation
on the unit circle of functions analytic in the unit disk, the
so-called Fej\'er--Kalm\'ar theorem~\cite{fejer,kalmar,walsh}.
The extension to functions analytic in an annulus was considered by
Hlawka~\cite{hlawka}, and the equivalent problem of trigonometric
interpolation of $2\pi$-periodic functions on $[-\pi,\pi)$ was
considered by Kis~\cite{kis}.  All these results may fail in
practice because of rounding errors on the computer, however.
For example, Figure~3.7 of~\cite{austin} shows an example with
uniformly distributed random interpolation points in $[-\pi,\pi)$,
with rounding errors beginning to take over at $N\approx 20$.
For the case of interpolation by algebraic polynomials, this
kind of effect is familiar in the context of the Runge phenomenon,
where polynomial interpolants in equispaced points in $[-1,1]$
will diverge on a computer as $N\to\infty$ even for a function
like $f(x) = \exp(x)$ for which in principle they should converge.

\section{\label{sampling}Sampling theory and the Kadec \boldmath$1/4$
theorem} The field of approximation theory
goes back to Borel, de la Vall\'ee Poussin, Fej\'er, Jackson,
Lebesgue, and others at the beginning of the 20th century, and
its central question might be characterized like this:

\medskip

\begin{quotation}
\noindent
\em Given a function $f$ of a certain regularity, how
fast do its approximations of a given kind converge?
\end{quotation}

\medskip

\noindent
For example, if $f$ is periodic and analytic on $[-\pi, \pi)$, then
its equispaced trigonometric interpolants converge exponentially.
The same holds if $f$ is analytic in a strip surrounding the
whole real line and satisfies a decay condition at $\infty$,
with trigonometric interpolants generalized to interpolatory
series of sinc functions.

The field of sampling theory goes back to Gabor, Kotelnikov,
Nyquist, Paley, Shannon, J. M. and E. T. Whittaker, and Wiener a
few years later.  Its central question might be characterized
like this:

\medskip

\begin{quotation}
\noindent
\em Given a function $f$ of a certain regularity, which of
its approximations of a given kind are
exactly equal to $f\kern 1pt ?$
\end{quotation}

\medskip

\noindent
For example, if $f$ is periodic and analytic on $[-\pi,\pi)$,
then its equispaced trigonometric interpolant is exact if $f$
is band-limited (has a Fourier series of compact support) and
the grid includes at least two points per wavelength for each
wave number present in the series.  The same holds if $f$ is a
band-limited analytic function on the whole real line, with the
Fourier series generalized to the Fourier transform, and again
with trigonometric interpolation generalized to sinc interpolation.

Obviously we have worded these characterizations to highlight
the similarities between the two fields, which in fact differ in
significant ways.  Still, it is remarkable how little interaction
there has been between the two.  What makes this relevant to the
present paper is that our theorems and orientation are very much
those of approximation theory, whereas most of the scientific
interest in perturbed grids in the past has been from the side
of sampling theory, and the Kadec 1/4 theorem is the known result
in this general area.

Kadec's theorem is an answer to a question of sampling theory that
originates with Paley and Wiener~\cite{pw}.  The exponentials
$\{\exp(i\lambda_k^{} x)\}$, $-\infty < k < \infty$, form an
orthonormal basis for $L^2[-\pi,\pi]$ if $\lambda_k^{} = k$
for each $k$.  Thus, the sampling theorist would say that one can
recover a function $f\in L^2[-\pi,\pi]$ from its inner products
with the functions $\{\exp(i\lambda_k^{} x)\}$.  Now suppose these
wave numbers are perturbed so that $|\tilde \lambda_k^{} - k | \le
\alpha$ for some fixed $\alpha$.  Can one still recover the signal?
Specifically, does the family $\{\exp(i\tilde \lambda_k^{} x)\}$
form a {\em Riesz basis} for $L^2[-\pi,\pi]$, that is, a basis
that is related to the original one by a bounded transformation
with a bounded inverse?  Paley and Wiener showed that this is
always the case for $\alpha < 1/\pi^2$, and Levinson showed it
is not always the case for $\alpha \ge 1/4$.  Kadec's theorem
shows that Levinson's construction was sharp: for any $\alpha <
1/4$, the family $\{\exp(i\tilde \lambda_k^{} x)\}$ forms a Riesz
basis~\cite{aldgro,christensen,kadec,young}.

Note that the standard setting of Kadec's theorem involves
perturbation of wave numbers from equispaced values, in contrast
to the results of this paper, which involve perturbation of
interpolation points from equispaced values.  In view of
the Fourier transform, however, these settings are related, so one might
imagine, based on Kadec's theorem, that $\alpha = 1/4$ might be a
critical value for trigonometric interpolation in perturbed points.
Instead, we have found that the critical value is $\alpha = 1/2$.

We explain this apparent discrepancy as follows.  The Paley--Wiener
theory and Kadec's theorem are results concerning the $L^2$
norm, which in many applications would represent energy.  In our
application of trigonometric interpolation, something related to
the $L^2$ norm does indeed happen at $\alpha = 1/4$.  Suppose we
look at a {\em $2$-norm Lebesgue constant} $\tilde\Lambda_N^{(2)}$
for the perturbed grid interpolation problem, defined as the
operator norm on $L: f\mapsto \tilde t_N^{}$ induced by the
discrete $\ell^2$-norm on the data $\{f(\tilde x_k^{})\}$ and
on the Fourier coefficients of the interpolant $\tilde t_k^{}$.
Numerical experiments reported in Section 3.4.3 of~\cite{austin}
indicate that whereas the usual $\infty$-norm Lebesgue constant
is unbounded for all $\alpha$, $\tilde\Lambda_N^{(2)}$ is bounded
as $N\to\infty$ for any $\alpha < 1/4$ but not always bounded for
$\alpha \ge 1/4$.  (Indeed Kadec's theorem may imply this result.)
For $\alpha \in (1/4,1/2)$, we conjecture
$\tilde \Lambda_N^{(2)} = O(N^{4\alpha - 1})$.

Thus a sampling theorist might say that for $\alpha \in
[1/4,1/2)$, trigonometric interpolation is {\em unstable} in
the sense that it may amplify signals unboundedly in $\ell^2$
as $N\to\infty$.  On the other hand the approximation theorist
might note that the instability is very weak, involving not
even one power of $N$.  Assuming that the conjectured sharpening of
the estimate (\ref{thmrate2}) of Theorem~\ref{thm1} is valid,
one derivative of smoothness of $f$ is enough to suppress the
instability, ensuring $\|f-\tilde t_N^{}\|\to 0$ as $N\to\infty$
for all $\alpha < 1/2$.  The numerical analyst might add that on a
computer, amplification of rounding errors by $o(N)$ is unlikely
to cause trouble.  For $\alpha \ge 1/2$, in strong contrast,
the amplification is unbounded in any norm even for finite $N$,
and trouble is definitely to be expected.

\section{\label{bound}Proof of the Lebesgue constant estimate,
Theorem~\ref{thmbound}} A full proof of Theorem~\ref{thmbound},
filling 20 pages, is the subject of Chapter~4 of the first author's
D.\ Phil.\ thesis~\cite{austin}.  Many detailed trigonometric estimates
are involved, and we do not know how to shorten it significantly.
For readers interested in full details, that chapter has been made
available in the Supplementary Materials attached to this paper.

Here, we outline the argument.
To prove the bound (\ref{bigestimate}) on the Lebesgue constant,
\begin{equation}
\tilde \Lambda_N^{} \le {C(N^{4\alpha}-1)\over \alpha(1-2\alpha)},
\label{bigestimateagain}
\end{equation}
we begin by noting that $\tilde \Lambda_N^{}$ is given by
\begin{equation}
\tilde \Lambda_N^{}= \max_{x\in[-\pi,\pi]} \tilde L(x),
\label{maxdef}
\end{equation}
where $\tilde L$ is the Lebesgue function
\begin{equation}
\tilde L(x) = \sum_{k=-N}^N |\tilde \ell_k^{}(x) |,
\label{basicsum}
\end{equation}
where $\tilde{\ell}_k^{}$ is the $k$th
Lagrange cardinal trigonometric polynomial for the perturbed grid,
\begin{equation}
\tilde \ell_k^{}(x) = \prod_{j\ne k}\left.
\sin\Big({x-\tilde x_j^{}\over 2}\Big)
\right/ \sin\Big({\tilde x_k^{}-\tilde x_j^{}\over 2}\Big).
\end{equation}
The function $\tilde\ell_k^{}(x)$ takes the values $1$ at $\tilde
x_k^{}$ and $0$ at the other grid points $\tilde x_j^{}$, and the
sum (\ref{basicsum}) adds up contributions at a point $x$ from
all the $2N+1$ cardinal functions associated with grid points to
its left and right.

The argument begins by showing that on the interval $[x_{-(k + 1)}^*,
x_{-k}^*]$, $\tilde{\ell}_0$ satisfies the bound
\begin{equation}
|\tilde{\ell}_0(x)| \leq M_k, \quad x\in [x_{-(k + 1)}^*, x_{-k}^*], \quad 0 \leq k \leq N,
\label{Mbounds}
\end{equation}
for certain numbers $M_0, \ldots, M_N$, independently of the choice of
perturbed points $\{\tilde{x}_k\}$.  The points $x_k^*$ are defined by $x_0^* =
0$, $x_{-(N + 1)}^* = -\pi$, and
\[
x_k^* = 2\arctan\left(\frac{\cos(kh) - \cos(\alpha h) + \tan(\tilde{x}_0/2)\sin(kh)}{\tan(\tilde{x}_0/2)\bigl(\cos(kh) + \cos(\alpha h)\bigr) - \sin(kh)}\right), \quad -N \leq k \leq N, k \neq 0;
\]
the most important fact about them is that they satisfy the inequalities
\[
(k - \alpha)h \leq x_k^* \leq (k + \alpha)h, \quad -N \leq k \leq N.
\]
Thus, (\ref{Mbounds}) bounds $\tilde{\ell}_0$ on certain subintervals of
$[-\pi, 0]$.  By exploiting symmetry, these bounds yield similar bounds on
$\tilde{\ell}_0$ on similar subintervals of $[0, \pi]$ as well as bounds on the
other $2N$ contributions to $\tilde{L}$ in (\ref{basicsum}).  We are eventually
led to the estimate
\[
\tilde{L}(x) \leq 9 \sum_{k = 0}^N M_k,
\]
which holds uniformly for $x \in [-\pi, \pi]$.

For sufficiently large $N$, the $M_k$ satisfy
\begin{equation}
M_k^{} \le {10 \pi\over 1-2\alpha}, \quad k = 0, 1
\label{Mineq1}
\end{equation}
and
\begin{equation}
M_k^{} \le {3 \pi (k+1)^{2\alpha}\over (1-2\alpha) (k-1)^{1-2\alpha}}, \quad 2 \le k \le N.
\label{Mineq2}
\end{equation}
The bound (\ref{bigestimateagain}) follows by an estimation of the sums of
(\ref{Mineq1}) and (\ref{Mineq2}) over all $k$.  The numbers $M_k^{}$ are
defined by
\begin{equation}
M_k^{} =
\max_{x \in [-\pi, 0] \cap R_k^{}} \frac{P_k^{}(x)}{Q_k^{}},
\quad 0 \le k \le N,
\label{Mdef}
\end{equation}
with
\begin{displaymath} P_k^{}(x)
= \prod_{i=1}^N \left|\sin\left(\frac{x - (i -
\alpha)h}{2}\right)\right|  \times\prod_{i=1}^k
\left|\sin\left(\frac{x + (i - \alpha)h}{2}\right)\right|
 \times\prod_{i = k + 1}^N \left|\sin\left(\frac{x + (i +
\alpha)h}{2}\right)\right|
\end{displaymath}
and
\begin{displaymath}
 Q_k^{} = \prod_{i = 1}^N \left|\sin\left(\frac{(2\alpha
- i)h}{2}\right)\right|  \times\prod_{i = 1}^k
\left|\sin\left(\frac{ih}{2}\right)\right|
\times\prod_{i = k + 1}^N \left|\sin\left(\frac{(2\alpha +
i)h}{2}\right)\right|.
\end{displaymath}
The set $R_k^{}$ in the definition of the range of
the maximum in (\ref{Mdef}) is the interval
\begin{displaymath}
R_k^{} = [(-k - 1 - \alpha)h, (-k + \alpha)h].
\end{displaymath}

\section*{Acknowledgements}

Many friends and colleagues have helped us along the way.  In
particular, we thank Stefan G\"uttel, Andrew Thompson, Alex Townsend,
and Kuan Xu.  Thompson showed us how we could improve $N^{4\alpha}$ to
$N^{4\alpha}-1$ in our main estimate (\ref{bigestimate}).

\vskip .1in

~~



2016-12-14T02:02:46.000
1612
1612.04018
en
https://arxiv.org/abs/1612.04018
The trigonometric interpolants to a periodic function $f$ in equispaced points converge if $f$ is Dini-continuous, and the associated quadrature formula, the trapezoidal rule, converges if $f$ is continuous. What if the points are perturbed? With equispaced grid spacing $h$, let each point be perturbed by an arbitrary amount $\le \alpha h$, where $\alpha\in [\kern .5pt 0,1/2)$ is a fixed constant. The Kadec 1/4 theorem of sampling theory suggests there may be be trouble for $\alpha\ge 1/4$. We show that convergence of both the interpolants and the quadrature estimates is guaranteed for all $\alpha<1/2$ if $f$ is twice continuously differentiable, with the convergence rate depending on the smoothness of $f$. More precisely it is enough for $f$ to have $4\alpha$ derivatives in a certain sense, and we conjecture that $2\alpha$ derivatives is enough. Connections with the Fejér--Kalmár theorem are discussed.
Numerical Analysis (math.NA)
Trigonometric Interpolation and Quadrature in Perturbed Points
Qwen/Qwen-72B
1. YES
2. YES