Composition based staircase algorithm and constrained interpolation with boundary conditions

Summary. Weakly coupled systems of inequalities arise frequently in the consideration of so-called direct methods for shape preserving interpolation. In this paper, a composition based staircase algorithm for bidiagonal systems subject to boundary conditions is developed. Using the compositions of the corresponding relations instead of their projections, we are able to derive a necessary and sufficient solvability criterion. Further, all solutions of the system can be constructed in a backward pass. To illustrate the general approach, we consider in detail the problem of convex interpolation by cubic splines. For this problem, an algorithm of the complexity O(n) in the number n of data points is obtained. Received August 4, 1998 / Revised version received February 5, 1999 / Published online January 27, 2000