# Data Interpolation by Near-Optimal Splines with Free Knots Using Linear Programming
## 4 Numerical Testing
### Comparison with Other Methods  
Our method is compared with the methods implemented in MATLAB R2021a by using data for Example 1. With a mesh of discretization of 0.01, the default spline interpolation [59] computes splines within 0.0156 seconds and obtains the \(l_{\infty}\)-norm (max norm) of the third derivative of 12.15, while our method computed splines within 0.071 seconds and obtains the third derivative of 10.767, which is 12.84% lower than the value obtained by MATLAB. The spline interpolation with \"optimal\" knots [60] obtains the knot location at \(x=3\), which is one of the data points, and the \(l_{\infty}\)-norm of the third derivative is the same as that obtained within [59]. The difference is explained by the fact that results in [60] are motivated by works as in [47; 48]; therefore, optimality is with respect to knots selected from  
Figure 2: Polynomials comprising the near-optimal cubic spline for Example 1 with \(m=10\).  
an _a priori_ given points, while within our method, the position of knots is not restricted as being fixed, thereby leading to a lower objective function.  
\begin{table}
\begin{tabular}{c c c c} \hline \hline \(x\) & **Example 2** & **Example 3** & **Example 4** \\ \hline \(x_{1}=1\) & \(y_{1}=1.1051\) & \(y_{1}=0.8415\) & \(y_{1}=3\) \\ \hline \(x_{2}=2\) & \(y_{2}=1.2214\) & \(y_{2}=0.9093\) & \(y_{2}=3.3113\) \\ \hline \(x_{3}=3\) & \(y_{3}=1.3498\) & \(y_{3}=0.1411\) & \(y_{3}=3.74\) \\ \hline \(x_{4}=4\) & \(y_{4}=1.4918\) & \(y_{4}=-0.757\) & \(y_{4}=4.2219\) \\ \hline \(x_{5}=5\) & \(y_{5}=1.6487\) & \(y_{5}=-0.959\) & \(y_{5}=4.6928\) \\ \hline \(x_{6}=6\) & \(y_{6}=1.8221\) & \(y_{6}=-0.279\) & \(y_{6}=5.0883\) \\ \hline \(x_{7}=7\) & \(y_{7}=2.0137\) & \(y_{7}=0.6570\) & \(y_{7}=5.3443\) \\ \hline \(x_{8}=8\) & \(y_{8}=2.2255\) & \(y_{8}=0.9894\) & \(y_{8}=5.3963\) \\ \hline \(x_{9}=9\) & \(y_{9}=2.4596\) & \(y_{9}=0.4121\) & \(y_{9}=5.1947\) \\ \hline \(x_{10}=10\) & \(y_{10}=2.7183\) & \(y_{10}=-0.5440\) & \(y_{10}=4.7732\) \\ \hline \(x_{11}=11\) & \(y_{11}=3.0042\) & \(y_{11}=-1\) & \(y_{11}=4.196\) \\ \hline \(x_{12}=12\) & \(y_{12}=3.3201\) & \(y_{12}=-0.537\) & \(y_{12}=3.5274\) \\ \hline \(x_{13}=13\) & \(y_{13}=3.6693\) & \(y_{13}=0.4202\) & \(y_{13}=2.8317\) \\ \hline \(x_{14}=14\) & \(y_{14}=4.0552\) & \(y_{14}=0.9906\) & \(y_{14}=2.1731\) \\ \hline \(x_{15}=15\) & \(y_{15}=4.4817\) & \(y_{15}=0.6503\) & \(y_{15}=1.6159\) \\ \hline \(x_{16}=16\) & \(y_{16}=4.9530\) & \(y_{16}=-0.288\) & \(y_{16}=1.2244\) \\ \hline \(x_{17}=17\) & \(y_{17}=5.4739\) & \(y_{17}=-0.961\) & \(y_{17}=1.0628\) \\ \hline \(x_{18}=18\) & \(y_{18}=6.0496\) & \(y_{18}=-0.751\) & \(y_{18}=1.1953\) \\ \hline \(x_{19}=19\) & \(y_{19}=6.6859\) & \(y_{19}=0.1499\) & \(y_{19}=1.6863\) \\ \hline \(x_{20}=20\) & \(y_{20}=7.3890\) & \(y_{20}=0.9129\) & \(y_{20}=2.6\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Data for Examples 2–4.  
\begin{table}
\begin{tabular}{c c c c} \hline \hline  & **CPU Time (s)** & \(\hat{k}\) & **Actual \(k\)** \\ \hline
**Example 2 (Exp.)** & 0.25 & 0.0062 & 0.0073891 \\ \hline
**Example 3 (Sine)** & 0.24 & 0.8947 & 1 \\ \hline
**Example 4 (Polyn.)** & 0.2 & 0.0645 & 0.0642609 \\ \hline \hline \end{tabular}
\end{table}
Table 2: Computed optimal values and CPU time for Examples 2–4.  
\begin{table}
\begin{tabular}{c c c c} \hline \hline \(x\) & **Example 2** & **Example 3** & **Example 4** \\ \hline \(x_{1}=1\) & \(y_{1}=1.1051\) & \(y_{1}=0.8415\) & \(y_{1}=3\) \\ \hline \(x_{2}=2\) & \