Existence and Uniquness of Interpolants¶
Definition¶
The question of existence and uniqueness of an interpolant comes down to matching the number of parameters in the interpolant to the number of data points to be fit:
- If there are too little parameters, the interpolant won't exist
- If there are too many parameters, the interpolant does not exist
Formally speaking, for a given set of data points \((t_{i}, y_{i}), \ \ \ \ i=1, \dots, m\), an interpolant is chosen from the space of functions spanned by a suitable set of basis functions \(\phi_{1}(t), \dots, \phi_{n}(t)\). The interpolating function \(f\) is expressed as a linear combination of these basis functions,
where the parameters \(x_{j}\) need to be determined. Requiring that \(f\) interpolate the data \((t_{i}, y_{i})\) means that
which is a system of linear equations that can be written in matrix form as
where the \(m \times n\) entries of the basis matrix \(\mathbf{A}\) are given by \(a_{ij} = \phi_{j}(t_{i})\) (ie., \(a_{ij}\) is the value of the \(j\)th basis function evaluated at the \(i\)th datapoint).
The components of the right-hand-side \(m\)-vector \(\mathbf{y}\) are the known data values \(y_{i}\), and the components in the \(n\)-vector \(\mathbf{x}\) are the unknown parameters \(x_{j}\).
For a given family of functions, there may be multiple choices of basis functions. The particular choice of basis functions affects the conditioning of the linear system \(\mathbf{Ax = y}\), the amount of work required to solve it, and the ease in which the resulting interpolant can be evaluated or manipulated.
The Effects of Dimensions \(m \times n\) on the Existence and Uniqueness of the Interpolant¶
If we choose the number of basis functions \(n\) to be equal to the number of data points \(m\), then we obtain a square linear system, and hence the data points can be fit exactly, provided \(\mathbf{A}\) is nonsingular.
In other contexts \(m\) and \(n\) won't be the same. In a least squares approximation context, the number of basis functions \(n\) is less than the number of data points \(m\), thus giving us an overdetermined system so that the data can not be fit exactly.
On the other hand, sometimes it is beneficial to have an undetermined system, where there are more basis functions \(n\), than data points \(m\). We result in a non-unique interpolant which allows the freedom necessary to satisfy additional properties such as monotonicity, convexity, or a specified degree of smoothness.
In summary, the existence and uniqueness of an interpolant \(f\) to a given set of points depends on the nonsingularity of \(\mathbf{A}\), and the sensitivity of the parameters \(\mathbf{x}\) to perturbations in the data depend on the conditioning of \(\mathbf{A}\).
References¶
Interpolation (numerical analysis) Existence and Uniqueness of Matrices (and singular matrices) Linear Least Squares Problems Sensitivity and Conditioning of Square Matrices (and amplification factor) 1 Sensitivity and Conditioning of Rectangular Matrices (numerical analysis)