Chapter 10 Function Interpolation
In this chapter, we study the problem of approximating a given function \(f(x)\) using simpler functions \(y(x)\text{.}\) This process is called function approximation. The function \(f(x)\) is called the target function, and \(y(x)\) is called the approximating function. The difference \(R(x) = f(x) - y(x)\) is called the approximation error or remainder term.
By "simpler functions," we typically mean functions that can be computed using basic arithmetic operations (addition, subtraction, multiplication, and division). The most general form of such functions is a rational function—a ratio of two polynomials. However, the most commonly used approximating functions are polynomials or piecewise polynomials.
Measuring the Quality of Approximation: How can we measure whether an approximation is "good" or "bad"? This depends on how we measure the approximation error. Two commonly used standards are:
-
Uniform (Maximum) Norm:\begin{equation*} \|f(x) - y(x)\|_{\infty} = \max_{x \in [a,b]} |f(x) - y(x)| \end{equation*}Function approximation under this measure is called uniform approximation or minimax approximation. If \(\|f(x) - y(x)\|_{\infty} \leq \varepsilon\text{,}\) then when we replace \(f(x)\) with \(y(x)\text{,}\) the absolute error at any point \(x \in [a,b]\) does not exceed \(\varepsilon\text{.}\)
-
Mean Square Norm:\begin{equation*} \|f(x) - y(x)\|_2 = \sqrt{\int_a^b |f(x) - y(x)|^2 \, dx} \end{equation*}Function approximation under this measure is called least squares approximation. Even if \(\|f(x) - y(x)\|_2 \leq \varepsilon\text{,}\) we cannot guarantee that the absolute error at any specific point \(x \in [a,b]\) is less than \(\varepsilon\text{.}\) However, the average squared error is at most \(\frac{\varepsilon^2}{b-a}\text{.}\)
Interpolation versus Least Square Regression: In particular, if we know the values of the target function \(f(x)\) at some discrete points \(x_i\) (\(i = 0, 1, \ldots, n\)), and we require that the approximating function \(y(x)\) matches the target function exactly at these points (possibly matching derivatives up to a certain order as well), this is called function interpolation. We require:
\begin{equation*}
\max_{0 \leq i \leq n} |f(x_i) - y(x_i)| = 0
\end{equation*}
On the other hand, if we want to minimize the expression
\begin{equation*}
\sum_{i=0}^n |f(x_i) - y(x_i)|^2
\end{equation*}
this is called least square regression.
Both function interpolation and approximation arise from practical needs. In real-world problems, functions often depend on experiments and observations, so we can usually only obtain values at discrete points within a certain interval, without an explicit mathematical formula. Therefore, we hope to use simple mathematical expressions to approximately describe the overall behavior of such functions—in other words, to build continuous models from discrete data using simple functions.
On the other hand, even when we have an explicit formula for a function, it may be too complicated for practical computation, such as evaluating function values, computing derivatives, or calculating integrals. In such cases, we also need to replace them with simpler approximating functions.
Choice of Basis Functions: Whether for interpolation or approximation, we must first determine the type of simple function to use. Generally, we select a set of linearly independent simple known functions
\begin{equation*}
\varphi_0(x), \varphi_1(x), \ldots, \varphi_n(x)
\end{equation*}
and use all their linear combinations to span a linear space
\begin{equation*}
\mathscr{Y} = \operatorname{Span}(\varphi_0(\cdot), \varphi_1(\cdot), \ldots, \varphi_n(\cdot))
\end{equation*}
as the class of interpolating or approximating functions. In other words, we use functions of the form
\begin{equation*}
y(x) = a_0\varphi_0(x) + a_1\varphi_1(x) + \cdots + a_n\varphi_n(x)
\end{equation*}
for interpolation or approximation.
Thus, the problem reduces to determining the unknown coefficients \(a_0, a_1, \ldots, a_n\) so that the relevant error measure is minimized. These known functions \(\varphi_0(\cdot), \varphi_1(\cdot), \ldots, \varphi_n(\cdot)\) are called the basis functions of the linear space \(\mathscr{Y}\text{.}\)
