# Data Interpolation by Near-Optimal Splines with Free Knots Using Linear Programming
## 4 Numerical Testing
### Numerical Examples  
In this section, five examples are presented. Example 1 provides a step by step walk-through of the algorithm. Examples 2-4 illustrate the performance of the algorithm in terms of the CPU time for different test functions. Scalability as well as accuracy results are presented in Example 5. In addition, Example 5 gives computational evidence that the optimal value of formulation (4) approaches the optimal value of (1) and (2) as \(O\left(h^{2}\right)\). **Example 1**. : _Walk-Through Example. Consider a problem with five data points: (\(x_{1}=1\), \(y_{1}=3\)), (\(x_{2}=2\), \(y_{2}=5\)), (\(x_{3}=3\), \(y_{3}=4.5\)), (\(x_{4}=4\), \(y_{4}=6.6\)), and (\(x_{5}=5\), \(y_{5}=2.6\)) and let \(r=3\). We want to find a near-optimal cubic spline while illustrating all steps of the formulation very clearly and providing all basic details._  
We divide each interval into two subintervals, so \(n=5\), \(m=2,l=(n-1)m=8\) and \(h=0.5\) with the resulting subintervals \([\hat{x}_{1},\hat{x}_{2}]=[1,1.5]\), \([\hat{x}_{2},\hat{x}_{3}]=[1.5,2]\), \([\hat{x}_{3},\hat{x}_{4}]=[2,2.5]\), \([\hat{x}_{4},\hat{x}_{5}]=[2.5,3]\), \([\hat{x}_{5},\hat{x}_{6}]=[3,3.5]\), \([\hat{x}_{6},\hat{x}_{7}]=[3.5,4]\), \([\hat{x}_{7},\hat{x}_{8}]=[4,4.5]\), and \([\hat{x}_{8},\hat{x}_{9}]=[4.5,5]\). Note that some of the \(\hat{x}_{j},j=1,\ldots,9\) are problem data values \(x_{i},i=1,\ldots,5\): \(\hat{x}_{1}=x_{1}\), \(\hat{x}_{3}=x_{2}\), \(\hat{x}_{5}=x_{3}\), \(\hat{x}_{7}=x_{4}\), and \(\hat{x}_{9}=x_{5}\). Formulation (4) takes the following form:  
\[ \begin{array}{c}f(\hat{x}_{1}),f(\hat{x}_{2}),f(\hat{x}_{3}),f(\hat{x}_{4}), f(\hat{x}_{5}),f(\hat{x}_{6}),f(\hat{x}_{7}),f(\hat{x}_{8}),f(\hat{x}_{9})\\ s.t.\ \ -k\leq\frac{f(\hat{x}_{1})-3f(\hat{x}_{2})+3f(\hat{x}_{3})-f(\hat{x}_{4})}{0.5 }\leq k;\ \ \ -k\leq\frac{f(\hat{x}_{2})-3f(\hat{x}_{3})+3f(\hat{x}_{4})-f(\hat{x}_{5})}{0.5 }\leq k;\\ \ \ -k\leq\frac{f(\hat{x}_{3})-3f(\hat{x}_{4})+3f(\hat{x}_{5})-f(\hat{x}_{6})}{0.5 }\leq k;\ \ \ -k\leq\frac{f(\hat{x}_{4})-3f(\hat{x}_{5})-3f(\hat{x}_{6})-f(\hat{x}_{9})}{0.5 }\leq k;\\ \ \ -k\leq\frac{f(\hat{x}_{5})-3f(\hat{x}_{6})+3f(\hat{x}_{7})-f(\hat{x}_{8})}{0. 5}\leq k;\ \ \ -k\leq\frac{f(\hat{x}_{6})-3f(\hat{x}_{7})+3f(\hat{x}_{8})-f(\hat{x}_{9})}{0.5 }\leq k;\\ f(\hat{x}_{1})=y_{1}=3;\ f(\hat{x}_{3})=y_{2}=5;f(\hat{x}_{5})=y_{3}=4.5;f( \hat{x}_{7})=y_{4}=6.6;f(\hat{x}_{9})=y_{5}=2.6;\end{array} \]  
where \(\hat{x}_{1}=x_{1},\hat{x}_{2}=\frac{x_{1}+x_{2}}{2},\hat{x}_{3}=x_{2},\hat{x }_{4}=\frac{x_{2}+x_{3}}{2},\hat{x}_{5}=x_{3},\hat{x}_{6}=\frac{x_{3}+x_{4}}{2 },\hat{x}_{7}=x_{4},\hat{x}_{8}=\frac{x_{4}+x_{5}}{2}\), and \(\hat{x}_{9}=x_{5}\). The decision variables are: \(f(\hat{x}_{1}),f(\hat{x}_{2}),f(\hat{x}_{3}),f(\hat{x}_{4}),f(\hat{x}_{5}),f( \hat{x}_{6}),f(\hat{x}_{7}),f(\hat{x}_{8})\), and \(f(\hat{x}_{9})\), but \(f(\hat{x}_{1}),f(\hat{x}_{3}),f(\hat{x}_{5}),f(\hat{x}_{7})\) and \(f(\hat{x}_{9})\) are known to be \(y_{1}\), \(y_{2}\), \(y_{3}\), \(y_{4}\) and \(y_{5}\), respectively, so the actual decision variables are only \(f(\hat{x}_{2})\), \(f(\hat{x}_{4})\), \(f(\hat{x}_{6})\), and \(f(\hat{x}_{8})\). The solution is \(f(\hat{x}_{2})=4.9625\), \(f(\hat{x}_{4})=4.4125\), \(f(\hat{x}_{6})=5.6625\), \(f(\hat{x}_{8})=6.0125\), and \(k=10.4\). Figures 1 and 2 present a near-optimal cubic spline, and the cubic polynomials comprising the spline. The splines are represented by discrete points, interpolating the above data points by using \(m=10\). **Example 2**. : _Exponential Function. Consider a problem with \(n=20\) and \(m=50\) and a \"test\" function \(f(x)=e^{x/10}\)._  
**Example 3**. : _Trigonometric Function. Consider a problem with \(n=20\) and \(m=50\) and a \"test\" function \(f(x)=sin(x)\)._  
**Example 4**. : _Polynomial Function. Consider a problem with \(n=20\) and \(m=50\) and a \"test\" function:  
Figure 1: Near-optimal cubic spline for Example 1 with \(m=10\).