Interpolation

In the numerical analysis, the term interpolation refers to a class of problems and procedures. For given discrete data (eg measured values) is a continuous function (called the interpolant or interpolant ) be found that maps this data. We then say, the function interpolates the data.

• 3.1 Linear interpolation
• 3.2 Higher grade polynomials
• 3.3 Piecewise interpolation
• 3.4 Hermiteinterpolation
• 3.5 Trigonometric Interpolation
• 3.6 Logarithmic interpolation

Introduction

Sometimes a function of individual dots known, but no analytical description of the function in order to evaluate it at any point can. One example are points as a result of a physical measurement. Could you connect the dots by a (possibly smooth ) curve, it would be possible to estimate the unknown function at the intermediate locations. In other cases, a difficult -to-handle function should be approximately represented by a simpler one. An interpolation function can satisfy this requirement of simplicity. This task is referred to as interpolation problem. There are several solutions to the problem, the user must first select the appropriate shape functions. Depending on the shape functions, we get a different interpolant.

The interpolation is a kind of approximation: The considered function is exactly represented by the interpolating function in the interpolation points and the remaining points at least approximately. The approximation depends on the approach. To appreciate it, additional information about the function are needed. This also arise from ignorance of most naturally: boundedness, continuity or differentiability can often provide.

In other approximation methods as of adjustment is not required that the measurement data are accurately reproduced. Thus, these methods are different from the interpolation. In the related problem of extrapolation values ​​are estimated, which go beyond the domain of the data.

Interpolationsprobleme

The general interpolation problem

Given pairs of real or complex numbers. This is called analog for computing with functions. Than interpolation points as the data points and the pairs bases Now, you select a trial function which depends on both as well as other parameters. As interpolation problem refers to the task to be selected such that is.

The linear interpolation problem

One speaks of a linear interpolation problem when only linearly with the, ie

In particular, the polynomial is such a linear interpolation problem. For the polynomial

For special cases, and is called linear, quadratic and cubic interpolation. In two dimensions, one speaks accordingly of bilinear, biquadratic and bicubic.

In addition, the trigonometric interpolation is a linear interpolation:

Nonlinear Interpolationsprobleme

Among the most important non-linear Interpolationsproblemen

• Rational:

Interpolation

Linear interpolation

The substantiated by Isaac Newton linear interpolation is the simplest and is probably used in practice most often. Here two given data points ( ) and () are connected by a path. The following applies:

This corresponds to a convex combination of the endpoints and.

Detailed explanations see General linear interpolation

Higher grade polynomials

There exists a unique interpolation polynomial of degree that matches the specified nodes with the prescribed reference values ​​to pairwise distinct data points. The determination of the coefficients requires the solution of a linear system of equations. The existence of such an interpolation polynomial can be seen, for example, using the formula of Lagrange

.

Uniqueness follows from the known fact that a polynomial of degree at most has zeros.

Other methods for polynomial interpolation see there.

Piecewise interpolation

Since polynomials with increasing degree are always unstable, ie swing heavily between the interpolation, are rarely used in practice polynomials of degree greater than 5. Instead, one interpolates a large data piecewise. In the case of linear interpolation, this would be a polygon, for polynomials of degree 2 or 3 is referred to generally by spline interpolation. In sections defined interpolant is the issue of continuity and differentiability at the support points of great importance.

Hermiteinterpolation

If, in addition to the support points also to interpolate the derivations, it is called a Hermite interpolation problem. The solution of this problem can be analogously also given in closed form for the Lagrangian method.

Trigonometric interpolation

If you choose the trial function a trigonometric polynomial, we obtain a trigonometric interpolation. The interpolation formula

Corresponds to a Fourier expansion of the unknown interpolant. The Fourier coefficients and are calculated as follows

And.

It is assumed that the sampling points in the interval, and equidistantly distributed outside that interval are periodic. The coefficients can be computed efficiently using fast Fourier transform.

Logarithmic interpolation

Suspected or known that the data is based on a logarithmic function, this method is recommended.

With the logarithmic interpolation two known data points and by a logarithmic curve are connected. The following applies:

Or in other words:

Example: χ ² test

General linear interpolation

It should be a real or complex continuously differentiable function with zero set, all zeros must be simple. Here, the index set can be a finite set, such as, or a countable set, or how to be. So that the interpolation kernels are given as

And steadily continuing with the value 1 in place. The auxiliary function is defined as the off-diagonal

Now it is easily seen that applies to the zero locations, the Kronecker delta was used.

Now there are values ​​given for each, as an interpolation function is defined by

In the case of a countable set of zeros of the convergence condition must

Be satisfied.

• With prescribed reference points and a real function with the function can be formed. Then one obtains

• With the cyclotomic polynomial, ie the roots of unity, as interpolation points, the Discrete Fourier transform results as a method for calculating the coefficients of the interpolating polynomial. It applies generally and so

• With and the zeros, is obtained as the cardinal series interpolation

This plays a central role in the Nyquist -Shannon sampling theorem. The convergence condition is

Nodes representation of polynomials

Be a polynomial. This polynomial can be represented by defining the vector in the so-called coefficient representation. An alternative analysis that does not require the coefficients is to support points representation. In this case, the polynomial is evaluated for values ​​of and, ie, the function values ​​are computed. The pair of vectors is called the support points of the polynomial representation. A major advantage of this representation is that two polynomials to be multiplied in the support points illustrated in steps. In contrast coefficient representation steps are required. The transformation of the coefficient in the support points representation is of particular importance and will be referred to as a Fourier transform. The reverse transformation is obtained by interpolation.

Applications

In many applications of interpolation is claimed that by interpolation new information from existing data is gained. But this is wrong. By interpolation, only the curve of a continuous function between known sample points can be estimated. This estimation is usually based on the assumption that the course is reasonably "smooth", which leads in most cases to plausible results. However, the assumption is not necessarily true. Higher frequency components that are lost in the digitization of a signal due to the sampling theorem, can not be reconstructed by subsequent interpolation.

A known application of interpolation, the digital signal processing. In the conversion of a signal from a low sampling rate in a high ( see sampling conversion), the samples of the output signal to be interpolated from that of the input signal. A special case is the scaling of images in computer graphics.