Editing Interpolation (section)

==Example==
This table gives some values of an unknown function <math>f(x)</math>.
[[File:Interpolation Data.svg|right|thumb|230px|Plot of the data points as given in the table]]
{| cellpadding=0 cellspacing=0
|width="20px"|
! <math>x</math>
|width="10px"|
!colspan=3 align=center| <math>f(x)</math>
|-
| || 0 || ||align=right| 0
|-
| || 1 || ||align=right| 0 || . || 8415
|-
| || 2 || ||align=right| 0 || . || 9093
|-
| || 3 || ||align=right| 0 || . ||1411
|-
| || 4 || ||align=right| &minus;0 || . || 7568
|-
| || 5 || ||align=right| &minus;0 || . || 9589
|-
| || 6 || ||align=right| &minus;0 || . || 2794
|}
Interpolation provides a means of estimating the function at intermediate points, such as <math>x=2.5.</math>

We describe some [[algorithm|methods]] of interpolation, differing in such properties as: accuracy, cost, number of data points needed, and [[smooth function|smoothness]] of the resulting [[interpolant]] function.
{{clear}}

===Piecewise constant interpolation===
[[File:Piecewise constant.svg|thumb|right|Piecewise constant interpolation, or [[nearest-neighbor interpolation]]]]
{{Further|Nearest-neighbor interpolation}}
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.
{{clear}}

===Linear interpolation===
[[File:Interpolation example linear.svg|right|thumb|230px|Plot of the data with linear interpolation superimposed]]
{{Main|Linear interpolation}}
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''<sub>''a''</sub>,''y''<sub>''a''</sub>) and (''x''<sub>''b''</sub>,''y''<sub>''b''</sub>), and the interpolant is given by:
:<math> y = y_a + \left( y_b-y_a \right) \frac{x-x_a}{x_b-x_a} \text{ at the point } \left( x,y \right) </math>

:<math> \frac{y-y_a}{y_b-y_a} = \frac{x-x_a}{x_b-x_a} </math>

:<math> \frac{y-y_a}{x-x_a} = \frac{y_b-y_a}{x_b-x_a} </math>

This previous equation states that the slope of the new line between <math> (x_a,y_a) </math> and <math> (x,y) </math> is the same as the slope of the line between <math> (x_a,y_a) </math> and <math> (x_b,y_b) </math>

Linear interpolation is quick and easy, but it is not very precise. Another disadvantage is that the interpolant is not [[derivative|differentiable]] at the point ''x''<sub>''k''</sub>.

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''<sub>''a''</sub> and ''x''<sub>''b''</sub> and that ''g'' is twice continuously differentiable. Then the linear interpolation error is

:<math> |f(x)-g(x)| \le C(x_b-x_a)^2 \quad\text{where}\quad C = \frac18 \max_{r\in[x_a,x_b]} |g''(r)|. </math>

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.
{{clear}}

===Polynomial interpolation===
[[File:Interpolation example polynomial.svg|right|thumb|230px|Plot of the data with polynomial interpolation applied]]
{{Main|Polynomial interpolation}}
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 of a polynomial|degree]].

Consider again the problem given above. The following sixth degree polynomial goes through all the seven points:
:<math> f(x) = -0.0001521 x^6 - 0.003130 x^5 + 0.07321 x^4 - 0.3577 x^3 + 0.2255 x^2 + 0.9038 x. </math>
<!-- Coefficients are 0, 0.903803333333334, 0.22549749999997, -0.35772291666664, 0.07321458333332, -0.00313041666667, -0.00015208333333. -->
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''&minus;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 theory|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 [[division by zero|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]].
{{clear}}

===Spline interpolation===
[[File:Interpolation example spline.svg|right|thumb|230px|Plot of the data with spline interpolation applied]]
{{Main|Spline interpolation}}

Linear interpolation uses a linear function for each of intervals [''x''<sub>''k''</sub>,''x''<sub>''k+1''</sub>]. 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

: <math> f(x) = \begin{cases}
-0.1522 x^3 + 0.9937 x, & \text{if } x \in [0,1], \\
-0.01258 x^3 - 0.4189 x^2 + 1.4126 x - 0.1396, & \text{if } x \in [1,2], \\
0.1403 x^3 - 1.3359 x^2 + 3.2467 x - 1.3623, & \text{if } x \in [2,3], \\
0.1579 x^3 - 1.4945 x^2 + 3.7225 x - 1.8381, & \text{if } x \in [3,4], \\
0.05375 x^3 -0.2450 x^2 - 1.2756 x + 4.8259, & \text{if } x \in [4,5], \\
-0.1871 x^3 + 3.3673 x^2 - 19.3370 x + 34.9282, & \text{if } x \in [5,6].
\end{cases} </math>

In this case we get ''f''(2.5)&nbsp;=&nbsp;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.<ref>{{cite book|last1=Kress|first1=Rainer|title=Numerical Analysis|url=https://archive.org/details/springer_10.1007-978-1-4612-0599-9|year=1998|publisher=Springer |isbn=9781461205999}}</ref>
{{Clear}}

=== Mimetic interpolation ===
{{Main|Mimetic interpolation}}
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.<ref>{{Cite journal |last1=Pletzer |first1=Alexander |last2=Hayek |first2=Wolfgang |date=2019-01-01 |title=Mimetic Interpolation of Vector Fields on Arakawa C/D Grids |url=https://journals.ametsoc.org/view/journals/mwre/147/1/mwr-d-18-0146.1.xml |journal=Monthly Weather Review |language=EN |volume=147 |issue=1 |pages=3–16 |doi=10.1175/MWR-D-18-0146.1 |bibcode=2019MWRv..147....3P |s2cid=125214770 |issn=1520-0493 |access-date=2022-06-07 |archive-date=2022-06-07 |archive-url=https://web.archive.org/web/20220607041035/https://journals.ametsoc.org/view/journals/mwre/147/1/mwr-d-18-0146.1.xml |url-status=live }}</ref> 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.<ref>{{Citation |last1=Stern |first1=Ari |title=Geometric Computational Electrodynamics with Variational Integrators and Discrete Differential Forms |date=2015 |url=http://link.springer.com/10.1007/978-1-4939-2441-7_19 |work=Geometry, Mechanics, and Dynamics |volume=73 |pages=437–475 |editor-last=Chang |editor-first=Dong Eui |place=New York, NY |publisher=Springer New York |doi=10.1007/978-1-4939-2441-7_19 |isbn=978-1-4939-2440-0 |access-date=2022-06-15 |last2=Tong |first2=Yiying |last3=Desbrun |first3=Mathieu |last4=Marsden |first4=Jerrold E. |series=Fields Institute Communications |s2cid=15194760 |editor2-last=Holm |editor2-first=Darryl D. |editor3-last=Patrick |editor3-first=George |editor4-last=Ratiu |editor4-first=Tudor|arxiv=0707.4470 }}</ref> 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 interpolation|Linear]], [[Bilinear interpolation|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.<ref>{{Cite journal |last=Jones |first=Philip |title=First- and Second-Order Conservative Remapping Schemes for Grids in Spherical Coordinates |journal=Monthly Weather Review |year=1999 |volume=127 |issue=9 |pages=2204–2210|doi=10.1175/1520-0493(1999)127<2204:FASOCR>2.0.CO;2 |bibcode=1999MWRv..127.2204J |s2cid=122744293 |doi-access=free }}</ref>