Convex interval interpolation using a three-term staircase algorithm (Q1294028)

For given real nodes \(x_0<\cdots<x_n\) and data intervals \([l_i,u_i]\subset {\mathbb R}\), \(i=0,1,\dots,n\), the convex interval interpolation problem is to find a function \(s\) which is convex in \([x_0,x_n]\) and satisfies \(s(x_i)\in[l_i,u_i]\), \(i=0,1,\dots,n\). The existence of a convex interval interpolating function \(s\) is equivalent to the existence of numbers \(y_i\in[l_i,u_i]\), \(i=0,1,\dots,n\), which solve a certain tridiagonal system of inequalities. In order to solve this existence problem, the authors propose a so-called three term staircase algorithm. Moreover, this algorithm can be used to compute all solutions of the system of inequalities. The three term staircase algorithm extends previous methods by \textit{P. Costantini} and \textit{R. Morandi} [Calcolo 21, 281-294 (1984; Zbl 0565.41006)] and \textit{J. W. Schmidt} and \textit{W. Heß} [Elem. Math. 39, 85-95 (1984; Zbl 0533.65038)]. For any admissible \(y_0,\dots,y_n\), known convexity preserving interpolation schemes lead to solutions of the convex interpolation problem. In particular, the authors discuss strategies for computing spline functions \(s\) (quadratic \(C^1\) and quartic \(C^2\)) with knots in \(x_0,\dots,x_n\) and with variable additional knots by optimization procedures, in particular by minimizing suitable smoothness functionals.