Composition based staircase algorithm and constrained interpolation with boundary conditions

Weakly coupled systems of inequalities arise frequently in the consideratio n of so-called direct methods for shape preserving interpolation. In this p aper, a composition based staircase algorithm for bidiagonal systems subjec t to boundary conditions is developed. Using the compositions of the corres ponding relations instead of their projections, we are able to derive a nec essary and sufficient solvability criterion. Further, all solutions of the system can be constructed in a backward pass. To illustrate the general app roach, we consider in detail the problem of convex interpolation by cubic C -1 splines. For this problem, an algorithm of the complexity O(n) in the nu mber n of data points is obtained.