Как найти значение методом интерполяции

Была ли эта статья полезной?

Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 9 июля 2022 года; проверки требует 1 правка.

У этого термина существуют и другие значения, см. Интерполяция.

О функции, см.: Интерполянт.

Интерполя́ция, интерполи́рование (от лат. inter–polis — «разглаженный, подновлённый, обновлённый; преобразованный») — в вычислительной математике нахождение неизвестных промежуточных значений некоторой функции, по имеющемуся дискретному набору её известных значений, определенным способом. Термин «интерполяция» впервые употребил Джон Валлис в своём трактате «Арифметика бесконечных» (1656).

В функциональном анализе интерполяция линейных операторов представляет собой раздел, рассматривающий банаховы пространства как элементы некоторой категории^[1].

Многим из тех, кто сталкивается с научными и инженерными расчётами, часто приходится оперировать наборами значений, полученных опытным путём или методом случайной выборки. Как правило, на основании этих наборов требуется построить функцию, на которую могли бы с высокой точностью попадать другие получаемые значения. Такая задача называется аппроксимацией. Интерполяцией называют такую разновидность аппроксимации, при которой кривая построенной функции проходит точно через имеющиеся точки данных.

Существует также близкая к интерполяции задача, которая заключается в аппроксимации какой-либо сложной функции другой, более простой функцией. Если некоторая функция слишком сложна для производительных вычислений, можно попытаться вычислить её значение в нескольких точках, а по ним построить, то есть интерполировать, более простую функцию. Разумеется, использование упрощенной функции не позволяет получить такие же точные результаты, какие давала бы первоначальная функция. Но в некоторых классах задач достигнутый выигрыш в простоте и скорости вычислений может перевесить получаемую погрешность в результатах.

Следует также упомянуть и совершенно другую разновидность математической интерполяции, известную под названием «интерполяция операторов». К классическим работам по интерполяции операторов относятся теорема Рисса — Торина и теорема Марцинкевича^[en], являющиеся основой для множества других работ.

Определения[править | править код]

Рассмотрим систему несовпадающих точек () из некоторой области . Пусть значения функции известны только в этих точках:

Задача интерполяции состоит в поиске такой функции из заданного класса функций, что

</math>A(x)

Пример[править | править код]

1. Пусть мы имеем табличную функцию, наподобие описанной ниже, которая для нескольких значений определяет соответствующие значения :

0	0
1	0,8415
2	0,9093
3	0,1411
4	−0,7568
5	−0,9589
6	−0,2794

Интерполяция помогает нам узнать, какое значение может иметь такая функция в точке, отличной от указанных точек (например, при x = 2,5).

К настоящему времени существует множество различных способов интерполяции. Выбор наиболее подходящего алгоритма зависит от ответов на вопросы: как точен выбираемый метод, каковы затраты на его использование, насколько гладкой является интерполяционная функция, какого количества точек данных она требует и т. п.

2. Найти промежуточное значение (способом линейной интерполяции).

6000	15.5
6378	?
8000	19.2

Способы интерполяции[править | править код]

Интерполяция методом ближайшего соседа[править | править код]

Простейшим способом интерполяции является интерполяция методом ближайшего соседа.

Интерполяция многочленами[править | править код]

На практике чаще всего применяют интерполяцию многочленами. Это связано прежде всего с тем, что многочлены легко вычислять, легко аналитически находить их производные и множество многочленов плотно в пространстве непрерывных функций (теорема Вейерштрасса).

• Линейная интерполяция
• Интерполяционная формула Ньютона
• Метод конечных разностей
• ИМН-1 и ИМН-2
• Многочлен Лагранжа (интерполяционный многочлен)
• Схема Эйткена
• Сплайн-функция
• Кубический сплайн

Обратное интерполирование (вычисление x при заданной y)[править | править код]

• Полином Лагранжа
• Обратное интерполирование по формуле Ньютона
• Обратное интерполирование по формуле Гаусса

Интерполяция функции нескольких переменных[править | править код]

• Билинейная интерполяция
• Бикубическая интерполяция

Другие способы интерполяции[править | править код]

• Рациональная интерполяция
• Тригонометрическая интерполяция

Смежные концепции[править | править код]

• Экстраполяция — методы нахождения точек за пределами заданного интервала (продление кривой)
• Ретрополяция — методы нахождения по известным значениям переменной её неизвестных значений в начале динамического ряда.
• Аппроксимация — методы построения приближённых кривых

См. также[править | править код]

• Интерполяционные формулы
• Регрессия (математика)
• Метод наименьших квадратов
• Сглаживание данных эксперимента

Примечания[править | править код]

Литература[править | править код]

• Й. Берг, Й. Лёфстрём. Интерполяционные пространства. Введение. — М.: Мир, 1980. — 264 с.
• Ибрагимов И. И. Методы интерполяций функций и некоторые их применения. — М.: Высшая школа, 1971. — 520 c.
• Уолш Дж. Л.^[en] Интерполяция и аппроксимация рациональными функциями в комплексной области. — М.: Иностранная литература, 1961. — 508 c.
• Трибель Х. Теория интерполяции, функциональные пространства, дифференциальные операторы. — М.: Мир, 1980. — 664 c.

     Интерполяция – способ определения промежуточных значений по дискретному (Дискретность – разделённый, прерывистый) набору данных.

     Линейная интерполяция – самый простой и наиболее часто используемый ее тип.

     Уравнение линейной интерполяции имеет вид:

     y = y1 + ((x – x1)/(x2 – x1) * (y2 – y1)),

     где

     y – искомое;

     x – показатель для которого определяется значение (искомое);

     x1 – наименьший показатель;
     x2 – наибольший показатель;

     y1 – значение наименьшего показателя;
     y2 – значение наибольшего показателя.

Пример определения промежуточного значения,
методом линейной интерполяции

     Необходимо найти коэффициент перехода – C от веса снегового покрова на горизонтальной поверхности земли, к нормативной нагрузке на покрытие, для угла наклона кровли – 35°. Известно, что для угла наклона кровли 30° коэффициент C = 1, а для угла наклона кровли 60° коэффициент C = 0.

     Получаем значения для формулы:

     y = ? (искомое, коэффициент С для угла наклона кровли – 35°);

     x = 35 (угол наклона кровли – 35°, для которого находим коэффициент С);

     x1 = 30 (наименьший угол наклона кровли – 30°);

     x2 = 60 (наибольший угол наклона кровли – 60°).

     y1 = 1 (коэффициент С для наименьшего угла наклона кровли – 30°);

     y2 = 0 (коэффициент С для наибольшего угла наклона кровли – 60°);

     Подставляем в формулу значения:

     1 + ((35 – 30) / (60 – 30) х (0 – 1)) = 0,8333

     Получаем коэффициент С = 0,83.

From Wikipedia, the free encyclopedia

In the mathematical field of numerical analysis, interpolation is a type of estimation, a method of constructing (finding) new data points based on the range of a discrete set of known data points.^[1][2]

In engineering and science, one often has a number of data points, obtained by sampling or experimentation, which represent the values of a function for a limited number of values of the independent variable. It is often required to interpolate; that is, estimate the value of that function for an intermediate value of the independent variable.

A closely related problem is the approximation of a complicated function by a simple function. Suppose the formula for some given function is known, but too complicated to evaluate efficiently. A few data points from the original function can be interpolated to produce a simpler function which is still fairly close to the original. The resulting gain in simplicity may outweigh the loss from interpolation error and give better performance in calculation process.

Example[edit]

This table gives some values of an unknown function .

	0		0
	1		0	.	8415
	2		0	.	9093
	3		0	.	1411
	4		−0	.	7568
	5		−0	.	9589
	6		−0	.	2794

Interpolation provides a means of estimating the function at intermediate points, such as

We describe some methods of interpolation, differing in such properties as: accuracy, cost, number of data points needed, and smoothness of the resulting interpolant function.

Piecewise constant interpolation[edit]

The simplest interpolation method is to locate the nearest data value, and assign the same value. In simple problems, this method is unlikely to be used, as linear interpolation (see below) is almost as easy, but in higher-dimensional multivariate interpolation, this could be a favourable choice for its speed and simplicity.

Linear interpolation[edit]

One of the simplest methods is linear interpolation (sometimes known as lerp). Consider the above example of estimating f(2.5). Since 2.5 is midway between 2 and 3, it is reasonable to take f(2.5) midway between f(2) = 0.9093 and f(3) = 0.1411, which yields 0.5252.

Generally, linear interpolation takes two data points, say (x_a,y_a) and (x_b,y_b), and the interpolant is given by:

This previous equation states that the slope of the new line between and is the same as the slope of the line between and

Linear interpolation is quick and easy, but it is not very precise. Another disadvantage is that the interpolant is not differentiable at the point x_k.

The following error estimate shows that linear interpolation is not very precise. Denote the function which we want to interpolate by g, and suppose that x lies between x_a and x_b and that g is twice continuously differentiable. Then the linear interpolation error is

In words, the error is proportional to the square of the distance between the data points. The error in some other methods, including polynomial interpolation and spline interpolation (described below), is proportional to higher powers of the distance between the data points. These methods also produce smoother interpolants.

Polynomial interpolation[edit]

Polynomial interpolation is a generalization of linear interpolation. Note that the linear interpolant is a linear function. We now replace this interpolant with a polynomial of higher degree.

Consider again the problem given above. The following sixth degree polynomial goes through all the seven points:

Substituting x = 2.5, we find that f(2.5) = ~0.59678.

Generally, if we have n data points, there is exactly one polynomial of degree at most n−1 going through all the data points. The interpolation error is proportional to the distance between the data points to the power n. Furthermore, the interpolant is a polynomial and thus infinitely differentiable. So, we see that polynomial interpolation overcomes most of the problems of linear interpolation.

However, polynomial interpolation also has some disadvantages. Calculating the interpolating polynomial is computationally expensive (see computational complexity) compared to linear interpolation. Furthermore, polynomial interpolation may exhibit oscillatory artifacts, especially at the end points (see Runge’s phenomenon).

Polynomial interpolation can estimate local maxima and minima that are outside the range of the samples, unlike linear interpolation. For example, the interpolant above has a local maximum at x ≈ 1.566, f(x) ≈ 1.003 and a local minimum at x ≈ 4.708, f(x) ≈ −1.003. However, these maxima and minima may exceed the theoretical range of the function; for example, a function that is always positive may have an interpolant with negative values, and whose inverse therefore contains false vertical asymptotes.

More generally, the shape of the resulting curve, especially for very high or low values of the independent variable, may be contrary to commonsense; that is, to what is known about the experimental system which has generated the data points. These disadvantages can be reduced by using spline interpolation or restricting attention to Chebyshev polynomials.

Spline interpolation[edit]

Remember that linear interpolation uses a linear function for each of intervals [x_k,x_k+1]. Spline interpolation uses low-degree polynomials in each of the intervals, and chooses the polynomial pieces such that they fit smoothly together. The resulting function is called a spline.

For instance, the natural cubic spline is piecewise cubic and twice continuously differentiable. Furthermore, its second derivative is zero at the end points. The natural cubic spline interpolating the points in the table above is given by

In this case we get f(2.5) = 0.5972.

Like polynomial interpolation, spline interpolation incurs a smaller error than linear interpolation, while the interpolant is smoother and easier to evaluate than the high-degree polynomials used in polynomial interpolation. However, the global nature of the basis functions leads to ill-conditioning. This is completely mitigated by using splines of compact support, such as are implemented in Boost.Math and discussed in Kress.^[3]

Mimetic interpolation[edit]

Depending on the underlying discretisation of fields, different interpolants may be required. In contrast to other interpolation methods, which estimate functions on target points, mimetic interpolation evaluates the integral of fields on target lines, areas or volumes, depending on the type of field (scalar, vector, pseudo-vector or pseudo-scalar).

A key feature of mimetic interpolation is that vector calculus identities are satisfied, including Stokes’ theorem and the divergence theorem. As a result, mimetic interpolation conserves line, area and volume integrals.^[4] Conservation of line integrals might be desirable when interpolating the electric field, for instance, since the line integral gives the electric potential difference at the endpoints of the integration path.^[5] Mimetic interpolation ensures that the error of estimating the line integral of an electric field is the same as the error obtained by interpolating the potential at the end points of the integration path, regardless of the length of the integration path.

Linear, bilinear and trilinear interpolation are also considered mimetic, even if it is the field values that are conserved (not the integral of the field). Apart from linear interpolation, area weighted interpolation can be considered one of the first mimetic interpolation methods to have been developed.^[6]

Function approximation[edit]

Interpolation is a common way to approximate functions. Given a function with a set of points one can form a function such that for (that is, that interpolates at these points). In general, an interpolant need not be a good approximation, but there are well known and often reasonable conditions where it will. For example, if (four times continuously differentiable) then cubic spline interpolation has an error bound given by where and is a constant.^[7]

Via Gaussian processes[edit]

Gaussian process is a powerful non-linear interpolation tool. Many popular interpolation tools are actually equivalent to particular Gaussian processes. Gaussian processes can be used not only for fitting an interpolant that passes exactly through the given data points but also for regression; that is, for fitting a curve through noisy data. In the geostatistics community Gaussian process regression is also known as Kriging.

Other forms[edit]

Other forms of interpolation can be constructed by picking a different class of interpolants. For instance, rational interpolation is interpolation by rational functions using Padé approximant, and trigonometric interpolation is interpolation by trigonometric polynomials using Fourier series. Another possibility is to use wavelets.

The Whittaker–Shannon interpolation formula can be used if the number of data points is infinite or if the function to be interpolated has compact support.

Sometimes, we know not only the value of the function that we want to interpolate, at some points, but also its derivative. This leads to Hermite interpolation problems.

When each data point is itself a function, it can be useful to see the interpolation problem as a partial advection problem between each data point. This idea leads to the displacement interpolation problem used in transportation theory.

In higher dimensions[edit]

Multivariate interpolation is the interpolation of functions of more than one variable.
Methods include bilinear interpolation and bicubic interpolation in two dimensions, and trilinear interpolation in three dimensions.
They can be applied to gridded or scattered data. Mimetic interpolation generalizes to dimensional spaces where .^[8][9]

• 

  Nearest neighbor

• 

  Bilinear

• 

  Bicubic

In digital signal processing[edit]

In the domain of digital signal processing, the term interpolation refers to the process of converting a sampled digital signal (such as a sampled audio signal) to that of a higher sampling rate (Upsampling) using various digital filtering techniques (for example, convolution with a frequency-limited impulse signal). In this application there is a specific requirement that the harmonic content of the original signal be preserved without creating aliased harmonic content of the original signal above the original Nyquist limit of the signal (that is, above fs/2 of the original signal sample rate). An early and fairly elementary discussion on this subject can be found in Rabiner and Crochiere’s book Multirate Digital Signal Processing.^[10]

[edit]

The term extrapolation is used to find data points outside the range of known data points.

In curve fitting problems, the constraint that the interpolant has to go exactly through the data points is relaxed. It is only required to approach the data points as closely as possible (within some other constraints). This requires parameterizing the potential interpolants and having some way of measuring the error. In the simplest case this leads to least squares approximation.

Approximation theory studies how to find the best approximation to a given function by another function from some predetermined class, and how good this approximation is. This clearly yields a bound on how well the interpolant can approximate the unknown function.

Generalization[edit]

If we consider as a variable in a topological space, and the function mapping to a Banach space, then the problem is treated as “interpolation of operators”.^[11] The classical results about interpolation of operators are the Riesz–Thorin theorem and the Marcinkiewicz theorem. There are also many other subsequent results.

See also[edit]

References[edit]

External links[edit]

• Online tools for linear, quadratic, cubic spline, and polynomial interpolation with visualisation and JavaScript source code.
• Sol Tutorials – Interpolation Tricks
• Compactly Supported Cubic B-Spline interpolation in Boost.Math^{[permanent dead link]}
• Barycentric rational interpolation in Boost.Math
• Interpolation via the Chebyshev transform in Boost.Math