Algorithm 828: DNSPLIN1: discrete nonlinear spline interpolation

ABSTRACT

We describe a new method and a Fortran-77 code for constructing discrete approximations to nonparametric interpolating nonlinear spline curves. Our approach consists of minimizing the discretized strain energy by a descent method with a Sobolev gradient in place of the standard gradient. It serves as a demonstration of the Sobolev gradient method, which is much more generally applicable. The effectiveness of the method in rapidly producing smooth interpolatory curves is demonstrated by test results for several challenging data sets.

REFERENCES

• 1: Brent, R. 1973. Algorithms for Minimization Without Derivatives. Prentice-Hall, Englewood Cliffs, NJ.
• 2: John A. Edwards, Exact equations of the nonlinear spline, ACM Transactions on Mathematical Software (TOMS), v.18 n.2, p.174-192, June 1992 [doi>10.1145/146847.146925]
• 3: Gill, P., Murray, W., , and Wright, M. 1981. Practical Optimization. Academic Press, Inc, NY.
• 4: Glass, J. 1966. Smooth curve interpolation: A generalized spline fit procedure. BIT 6, 277--293.
• 5: Golomb, M. and Jerome, J. 1982. Equilibria of the curvature functional and manifolds of nonlinear interpolating spline curves. SIAM J. Math. Anal. 13, 421--458.
• 6: B. K. P. Horn, The Curve of Least Energy, ACM Transactions on Mathematical Software (TOMS), v.9 n.4, p.441-460, Dec. 1983 [doi>10.1145/356056.356061]
• 7: Jou, E. and Han, W. 1990. Minimal-energy splines: I. plane curves with angle constraints. Math. Meth. Appl. Sci. 13, 351--372.
• 8: Lee, E. and Forsythe, G. 1973. Variational study of nonlinear spline curves. SIAM Review 15, 120--133.
• 9: Anders Linnér, Unified representations of nonlinear splines, Journal of Approximation Theory, v.84 n.3, p.315-350, March 1996 [doi>10.1006/jath.1996.0022]
• 10: Malcolm, M. 1977. On the computation of nonlinear spline functions. SIAM J. Num. Anal. 14, 254--282.
• 11: Mehlum, E. 1974. Nonlinear splines. In Computer Aided Geometric Design, R. E. Barnhill and R. F. Riesenfeld, Eds. Academic Press, Inc, Orlando, FL., 173--207.
• 12: Neuberger, J. 1997. Sobolev Gradients and Differential Equations. Springer Lecture Notes in Mathematics #1670. Springer-Verlag, NY.
• 13: Polak, E. 1971. Computational Methods in Optimization. Academic Press, Inc, NY.
• 14: R. J. Renka, Interpolatory tension splines with automatic selection of tension factors, SIAM Journal on Scientific and Statistical Computing, v.8 n.3, p.393-415, May 1, 1987 [doi>10.1137/0908041]
• 15: R. J. Renka , J. W. Neuberger, Minimal surfaces and Sobolev gradients, SIAM Journal on Scientific Computing, v.16 n.6, p.1412-1427, Nov. 1995 [doi>10.1137/0916082]
• 16: Woodford, C. 1969. Smooth curve interpolation. BIT 9, 69--77.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.1 Interpolation

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE

General Terms:
Algorithms

Keywords:
Interpolation, Sobolev gradient, minimum energy curve, nonlinear spline