IRREMOVABLE ERROR OF INTERPOLATION BY TRIGONOMETRIC POLYNOMIALS

I. E. NAATS

(Presented by the scientific seminar of the computing laboratory)

It is known that the presence of uncertainty in the initial body of data leads, in problems of approximation of functions, to the emergence of additional errors, which have been called irremovable errors [1]. Here one distinguishes an irremovable error of the first kind, caused by uncertainty in the ordinates of the function \(f(x_i)\), and of the second kind, caused by inaccuracy in fixing the nodes, i.e., the abscissas of the ordinates \(x_i\) \((i=0,1\ldots)\). Determining the mean-square irremovable error of the first kind for trigonometric interpolation presents no special difficulty under the assumption of additivity of the measurement errors and of the values of the function \(f(x)\). In particular, for trigonometric polynomials on a discrete set of points \(\{x_i\}\) \((i=0,1\ldots 2n)\), the irremovable error of the first kind \(\sigma_1\) is equal to the mean-square error of measurement \(\sigma_0\) of the values of the function [2].

The purpose of the present work is to construct an estimate for the irremovable error of the second kind in problems of approximation by trigonometric polynomials.

Let there be given a sequence of values of some function \(f(x)\{y_i\}(i=0,1,\ldots,2n)\) in a system of points \(\{x_i\}\), the positions of which on the interval \([0,2\pi]\) are known with quadratic error \(d\). In doing so we shall assume that, over the set of \(p\) realizations (\(p\) measurements to determine the positions of the interpolation nodes), the points \(\{x_i\}\) on average form a system of equally spaced nodes. Then the system \(\{x_i\}\) on the set of realizations can be represented as a system of random variables of the form

\[ x_{iq}=x_{i0}+\varepsilon_{iq}, \tag{1} \]

where

\[ \begin{aligned} x_{iq}&\text{ — the value of the abscissa }x_i\text{ in the }q\text{-th measurement }(q=1,2\ldots p),\\ x_{i0}&\text{ — equally spaced points on the interval }(0,2\pi),\\ \varepsilon_{iq}&\text{ — the random displacement of }x_{iq}\text{ from }x_{i0}\text{ in the }q\text{-th measurement.} \end{aligned} \]

Since in the case under consideration the uncertainty in the position of the abscissas \(x_i\) is associated with measurement error, it is natural to assume that the system \(N\) \((N=2n+1)\) of random variables \(\varepsilon_i\) on the set of \(p\) measurements (a sample of size \(p\)) possesses the following properties:

\[ M[\varepsilon_i]=0, \]

\[ M[\varepsilon_i\cdot\varepsilon_j]= \begin{cases} d_i^2, & \text{for } i=j,\\ 0, & \text{for } i\ne j \end{cases} \tag{2} \]

for all \(i\) and \(j\) \((i,j=0,1\ldots 2n)\).

In what follows we shall assume that the measurement of the values of all abscissas is carried out by the same means, and therefore

\[ d_0=d_1\ldots=d_{2n}=d. \tag{3} \]

The quantity characterizes the root-mean-square deviation of the abscissas \(x_i\) \((i=0,1\ldots 2n)\) from the equidistant (fundamental) system of nodes \(x_{i0}\).

Let us consider the following problem: to estimate the root-mean-square deviation of the trigonometric interpolation polynomials constructed from the readings \(y_i\) \((i=0,1\ldots 2n)\) and the system of nodes (1), from the polynomial constructed from the same readings and the system of equidistant nodes \(\{x_{i0}\}\).

The deviation of the polynomial \(T_{nq}(x)\), constructed with respect to the nodes \(x_q^i\), from the polynomial \(T_n(x)\) with respect to the nodes \(x_{i0}\) is defined as the difference

\[ \Delta_{nq}(x)=T_{nq}(x)-T_n(x). \tag{4} \]

The deviation \(\Delta_{nq}(x)\) on a sample of random variables \(x_i\) \((i=0,1\ldots 2n)\) is a random function of \(x\) on the interval of approximation. Taking the number of nodes to be odd, i.e. \(N=2n+1\), we bring expression (4) to the form

\[ \Delta_{nq}(x)=\frac{2}{2n+1}\sum_{i=0}^{2n} y_i \left[ \sum_{k=1}^{n} \left( \cos k(x-x_{i0}-\varepsilon_{iq}) -\cos k(x-x_{i0}) \right) \right]. \tag{5} \]

Further we shall assume that the values of the deviations \(\varepsilon_i\) are sufficiently small in comparison with the interpolation step

\[ h=x_{i0}-x_{(i-1)0}=\frac{2}{2n+1} \]

for all \(q\) and \(i\). Then one may adopt the approximate equality

\[ \cos k(x-x_{i0}-\varepsilon_{iq})-\cos k(x-x_{i0}) =-\varepsilon_{iq}\cdot k\cdot \sin k(x-x_{i0}). \tag{6} \]

Taking (6) into account, (5) is rewritten in the form

\[ \Delta_{nq}(x)=\frac{2}{2n+1}\cdot \sum_{i=0}^{2n} y_i\cdot \varepsilon_{iq} \left( -\sum_{k=1}^{n} k\sin k(x-x_{i0}) \right). \tag{7} \]

From expressions (2) and (7) it follows that

\[ M[\Delta_n(x)]=0. \tag{8} \]

Thus, the polynomial \(T_n(x)\) is the mathematical expectation for the polynomials \(T_{nq}(x)\) in the first approximation.

Let us determine the variance for the deviation \(\Delta_n(x)\), i.e.

\[ D[\Delta_n(x)]=M(\Delta_n^2(x)). \tag{9} \]

Using (2) and carrying out the corresponding calculations, we obtain

\[ D[\Delta_n(x)]= \frac{4d^2}{(2n+1)^2} \sum_{i=0}^{2n} y_i^2 \left( \sum_{k=1}^{n} k\sin k(x-x_{i0}) \right)^2. \tag{10} \]

In what follows we shall assume that the sequence of readings \(\{y_i\}\) is bounded in its totality, i.e., there is a number \(M\) such that for all \(i\) the inequality

\[ |y_i| \leqslant M . \tag{11} \]

holds. Then, for \(D[\Delta_n(x)]\), one may write

\[ D[\Delta_n(x)] \leqslant \frac{4d^2M^2}{(2n+1)^2} \sum_{i=0}^{2n} \left( \sum_{k=1}^{n} k \sin k(x-x_{i0}) \right)^2 . \tag{12} \]

Since the nodes \(x_{i0}\) form a system of equally spaced points, we have

\[ \sum_{i=0}^{2n}\cos kx_{i0} = \sum_{i=0}^{2n}\sin kx_{i0} =0 . \]

Using these equalities, one can show that

\[ \sum_{i=0}^{2n} \left( \sum_{k=1}^{n} k \sin k(x-x_{i0}) \right)^2 = \frac{n(n+1)(2n+1)^2}{12}, \tag{13} \]

and for the variance of the quantity \(\Delta_n(x)\) we obtain the estimate

\[ D[\Delta_n(x)] \leqslant \frac{n(n+1)}{3}d^2M^2 . \tag{14} \]

It is interesting to note that \(D[\Delta_n(x)]\) does not depend on \(x\), i.e., the irremovable error of the second kind \(\sigma_2\) is uniformly distributed over the interpolation interval. This property is a consequence of the uniform distribution of the nodes \(x_{i0}\).

Taking as the irremovable error of the second kind the upper bound of the values of \(D[\Delta_n(x)]\), we obtain

\[ \sigma_2 = dM_1\sqrt{\frac{n(n+1)}{3}} . \tag{15} \]

For \(n \gg 1\),

\[ \sigma_2 = \frac{dMn}{\sqrt{3}} . \tag{16} \]

From (16) one can obtain the value of the relative error

\[ \xi_2=\frac{\sigma_2}{M}=\frac{dn}{\sqrt{3}} . \tag{17} \]

The results obtained lead to the following conclusion: the irremovable error of the second kind, caused by the inaccuracy in fixing the nodes, in trigonometric interpolation increases with an increase in the number of readings (respectively, the order of the polynomial). In other words, whereas the interpolation error (of the approximation method) decreases with an increase in the number \(N\) (also \(n\)), the total approximation error, taking into account irremovable errors, cannot be made

arbitrarily small, if at the same time the uncertainty associated with specifying the initial data is not substantially reduced. Therefore, when interpolating from a set of approximate data, one must approach the estimate of the required number of readings with great caution. The volume of data is determined not only by the required value of the approximation error, but also by the error with which these data are known. This applies especially to the abscissas of interpolation, since as \(N\) increases the interpolation process becomes unstable if, at the same time, \(d\) does not tend to zero.

In all likelihood, analogous conclusions will also be valid for an arbitrary arrangement of the interpolation nodes on the interval of approximation; however, at present this question has been little studied [3].

REFERENCES

1. I. S. Berezin, N. P. Zhidkov. Computational Methods, vol. 1. Fizmatgiz, Moscow, 1962.

2. I. E. Naatz. Application of trigonometric interpolation in problems of discrete measurement. Izv. TPI, vol. 168, 1967.

3. A. Zygmund. Trigonometric Series, vol. 2. Mir, Moscow, 1965.