Abstract
An efficient algorithm for computing a smoothing polynomial splines under inequality constraints on derivatives is introduced where both order and breakpoints ofs can be prescribed arbitrarily. By using the B-spline representation ofs, the original semi-infinite constraints are replaced by stronger finite ones, leading to a least squares problem with linear inequality constraints. Then these constraints are transformed into simple box constraints by an appropriate substitution of variables so that efficient standard techniques for solving such problems can be applied. Moreover, the smoothing term commonly used is replaced by a cheaply computable approximation. All matrix transformations are realized by numerically stable Givens rotations, and the band structure of the problem is exploited as far as possible.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
L.-E. Andersson and T. Elfving.Interpolation and approximation by monotone cubic splines. J. Approx. Theory, 66:302–333, 1991.
P. M. Anselone and P. J. Laurent.A general method for the construction of interpolating or smoothing spline functions. Numer. Math., 12:66–82, 1968.
I. Barrodale and F. D. K. Roberts.Algorithm 552. Solution of the constrained 1 1 linear approximation problem. ACM Trans. Math. Software, 6: 231–235, 1980.
Å. Björck.Least squares methods. In P. G. Ciarlet and J. L. Lions, editors,Handbook of Numerical Analysis, volume 1, pages 589–652. Elsevier/North-Holland, 1987.
K. Böhmer.Spline-Funktionen. Teubner, Stuttgart, 1974.
M. G. Cox.The least squares solution of overdetermined linear equations having band or augmented band structure. IMA J. Numer. Anal., 1:3–22, 1981.
M. G. Cox, P. M. Harris, and H. M. Jones.Strategies for knot placement in least squares data fitting by splines. In Mason and Cox [23], pages 37–45.
M. G. Cox and H. Jones.Shape-preserving spline approximation in the l 1 norm. In J. C. Mason M. G. Cox, editors,Algorithms for approximation, pages 115–129. Clarendon Press, Oxford, 1987.
C. de Boor.Splines as linear combination of B-splines. In G. G. Lorentz, C. K. Chui, and L. L. Schumaker, editors,Approximation Theory II, pages 1–47. Academic Press, New York, 1976.
C. de Boor.A Practical Guide to Splines. Springer, New York, 1978.
L. Eldén.A note on weighted pseudoinverses with application to the regularization of Fredholm integral equations of the first kind. BIT, 22:487–502, 1982.
L. Eldén.An algorithm for the regularization of ill-conditioned banded least squares problems. SIAM J. Sci. Stat. Comput., 5: 237–254, 1984.
T. Elfving and L.-E. Andersson.An algorithm for computing constrained smoothing spline functions. Numer. Math., 52:583–595, 1988.
F. N. Fritsch.Montoone piecewise cubic data fitting. In Mason and Cox [23], pages 99–106.
R. Hettich and P. Zencke.Numerische Methoden der Approximation und semi-infiniten Optimierung. Teubner, Stuttgart, 1982.
B. Hofmann, R. Hausding, and R. Wolke.Regularization of a Volterra integral equation by linear inequalities. Computing, 43:361–375, 1990.
U. Hornung.Monotone Spline-Interpolation. In L. Collatz, G. Meinardus, and W. Werner, editors,Numerische Methoden der Approximationstheorie, volume 4, ISNM 42, pages 172–191. Birkhäuser, Basel-Stuttgart, 1978.
U. Hornung.Interpolation by smooth functions under restrictions on the derivatives. J. Approx. Theory, 28:227–237, 1980.
L. D. Irvine, S. P. Marin, and P. W. Smith.Constrained interpolation and smoothing. Constr. Approx., 2:129–151, 1986.
T. Lyche and K. Mørken.A data reduction strategy for splines with applications to the approximation of functions and data. IMA J. Numer. Anal., 8:185–208, 1988.
T. Lyche and L. L. Schumaker.Computation of smoothing and interpolating natural splines via local bases. SIAM J. Numer. Anal., 10:1027–1038, 1973.
J. C. Mason and M. G. Cox, editors.Algorithms for Approximation II. Chapman and Hall, London-New York, 1988.
C. A. Michelli, P. W. Smith, J. Swetits, and J. D. Ward.Constrained l p approximation. Constr. Approx., 1:93–102, 1985.
C. H. Reinsch.Smoothing by spline functions. Numer. Math., 10:177–183, 1967.
C. H. Reinsch.Smoothing by spline functions II. Numer. Math., 16:451–454, 1971.
J. W. Schmidt.Beiträge zur konvexen Interpolation, Histopolation und Approximation durch Spline-Funktionen. Mitt. Math. Gesellsch. Hamburg, 12, 1991.
J. W. Schmidt and I. Scholz.A dual algorithm for convex-concave data smoothing by cubic C 2-splines. Numer. Math., 57:333–350, 1990.
I. J. Schoenberg.On interpolation by spline functions and its minimal properties. In P. L. Butzer and J. Korevaar, editors,On Approximation Theory, ISNM 5, pages 109–129. Birkhäuser, Basel-Stuttgart, 1964.
M. von Golitschek and L. L. Schumaker.Data fitting by penalized least squares. In Mason and Cox [23], pages 210–227.
R. Wolke. Lineare Quadratmittelprobleme mit Monotonie- und Konvexitätsnebenbedingungen (LSIMC). Wiss. Z. Pädagog. Hochsch. Halle-Köthen, XXVIII(4):16–24, 1990.
L.-E. Andersson and T. Elfving.An algorithm for constrained approximation. SIAM J. Sci. Stat. Comput., 8:1012–1025, 1987.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Schwetlick, H., Kunert, V. Spline smoothing under constraints on derivatives. BIT 33, 512–528 (1993). https://doi.org/10.1007/BF01990532
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01990532