Nonnegativity, monotonicity, or convexitypreserving cubic and quintic Hermite interpolation
Authors:
Randall L. Dougherty, Alan S. Edelman and James M. Hyman
Journal:
Math. Comp. 52 (1989), 471494
MSC:
Primary 41A05; Secondary 65D05
MathSciNet review:
962209
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: The Hermite polynomials are simple, effective interpolants of discrete data. These interpolants can preserve local positivity, monotonicity, and convexity of the data if we restrict their derivatives to satisfy constraints at the data points. This paper describes the conditions that must be satisfied for cubic and quintic Hermite interpolants to preserve these properties when they exist in the discrete data. We construct algorithms to ensure that these constraints are satisfied and give numerical examples to illustrate the effectiveness of the algorithms on locally smooth and rough data.
 [1]
Carl
de Boor, A practical guide to splines, Applied Mathematical
Sciences, vol. 27, SpringerVerlag, New YorkBerlin, 1978. MR 507062
(80a:65027)
 [2]
J. Butland, "A method of interpolating reasonableshaped curves through any data," Computer Graphics 80 (R.J. Lansdown, ed.), Online Publications, Northwood Hills, Middlesex, 1980, pp. 409422.
 [3]
Carl
de Boor and Blair
Swartz, Piecewise monotone interpolation, J. Approximation
Theory 21 (1977), no. 4, 411–416. MR 0481727
(58 #1826)
 [4]
R.
E. Carlson and F.
N. Fritsch, Monotone piecewise bicubic interpolation, SIAM J.
Numer. Anal. 22 (1985), no. 2, 386–400. MR 781326
(87a:65032), http://dx.doi.org/10.1137/0722023
 [5]
P.
Costantini and R.
Morandi, An algorithm for computing shapepreserving cubic spline
interpolation to data, Calcolo 21 (1984), no. 4,
295–305 (1985). MR 799994
(86j:65016), http://dx.doi.org/10.1007/BF02576168
 [6]
B.
Dimsdale, Convex cubic splines, IBM J. Res. Develop.
22 (1978), no. 2, 168–178. MR 0494833
(58 #13617)
 [7]
Alan
Edelman and Charles
A. Micchelli, Admissible slopes for monotone and convex
interpolation, Numer. Math. 51 (1987), no. 4,
441–458. MR
902100 (89b:65031), http://dx.doi.org/10.1007/BF01397546
 [8]
S.
C. Eisenstat, K.
R. Jackson, and J.
W. Lewis, The order of monotone piecewise cubic interpolation,
SIAM J. Numer. Anal. 22 (1985), no. 6,
1220–1237. MR 811195
(87d:65014), http://dx.doi.org/10.1137/0722075
 [9]
J. C. Ferguson, Shape Preserving Parametric Cubic Curve Interpolation, Ph. D. thesis, University of New Mexico, 1984.
 [10]
J. C. Ferguson & K. Miller, Characterization of Shape in a Class of Third Degree Algebraic Curves, TRW report 532235, 1969.
 [11]
F. N. Fritsch, Use of the Bernstein Form to Derive Sufficient Conditions for Shape Preserving Piecewise Polynomial Interpolation, Lawrence Livermore National Laboratory report UCRL91392, March 1984.
 [12]
F.
N. Fritsch and J.
Butland, A method for constructing local monotone piecewise cubic
interpolants, SIAM J. Sci. Statist. Comput. 5 (1984),
no. 2, 300–304. MR 740848
(85h:65022), http://dx.doi.org/10.1137/0905021
 [13]
F.
N. Fritsch and R.
E. Carlson, Monotone piecewise cubic interpolation, SIAM J.
Numer. Anal. 17 (1980), no. 2, 238–246. MR 567271
(81g:65012), http://dx.doi.org/10.1137/0717021
 [14]
James
M. Hyman, Accurate monotonicity preserving cubic
interpolation, SIAM J. Sci. Statist. Comput. 4
(1983), no. 4, 645–654. MR 725659
(85a:65021), http://dx.doi.org/10.1137/0904045
 [15]
J. M. Hyman, Accurate ConvexityPreserving Cubic Interpolation, informal report, Los Alamos Scientific Laboratory document, LAUR803700, Los Alamos, NM, November 1980.
 [16]
James
M. Hyman and Bernard
Larrouturou, The numerical differentiation of discrete functions
using polynomial interpolation methods, Appl. Math. Comput.
10/11 (1982), 487–506. Numerical grid generation
(Nashville, Tenn., 1982). MR
675799, http://dx.doi.org/10.1016/00963003(82)902041
 [17]
David
F. McAllister, Eli
Passow, and John
A. Roulier, Algorithms for computing shape
preserving spline interpolations to data, Math.
Comp. 31 (1977), no. 139, 717–725. MR 0448805
(56 #7110), http://dx.doi.org/10.1090/S00255718197704488050
 [18]
David
F. McAllister and John
A. Roulier, An algorithm for computing a shapepreserving
osculatory quadratic spline, ACM Trans. Math. Software
7 (1981), no. 3, 331–347. MR 630439
(82h:65009), http://dx.doi.org/10.1145/355958.355964
 [19]
David
F. McAllister and John
A. Roulier, Interpolation by convex quadratic
splines, Math. Comp. 32
(1978), no. 144, 1154–1162.
MR
0481734 (58 #1833), http://dx.doi.org/10.1090/S00255718197804817346
 [20]
Holger
Mettke, Convex cubic HERMITEspline interpolation, J. Comput.
Appl. Math. 9 (1983), no. 3, 205–211. MR 715537
(86f:65038a), http://dx.doi.org/10.1016/03770427(83)900134
 [21]
Edward
Neuman, Convex interpolating splines of arbitrary degree. II,
BIT 22 (1982), no. 3, 331–338. MR 675667
(84i:41016), http://dx.doi.org/10.1007/BF01934446
 [22]
Eli
Passow and John
A. Roulier, Monotone and convex spline interpolation, SIAM J.
Numer. Anal. 14 (1977), no. 5, 904–909. MR 0470566
(57 #10316)
 [1]
 C. de Boor, A Practical Guide to Splines, SpringerVerlag, New York, 1978. MR 507062 (80a:65027)
 [2]
 J. Butland, "A method of interpolating reasonableshaped curves through any data," Computer Graphics 80 (R.J. Lansdown, ed.), Online Publications, Northwood Hills, Middlesex, 1980, pp. 409422.
 [3]
 C. de Boor & B. Swartz, "Piecewise monotone interpolation," J. Approx. Theory, v. 21, 1977, pp. 411416. MR 0481727 (58:1826)
 [4]
 R. E. Carlson & F. N. Fritsch, "Monotone piecewise bicubic interpolation," SIAM J. Numer. Anal., v. 22, 1985, pp. 386400. MR 781326 (87a:65032)
 [5]
 P. Costantini & R. Morandi, "Monotone and convex cubic spline interpolation," Calcolo, v. 21, 1984, pp. 281294; and "An algorithm for computing shapepreserving cubic spline interpolation to data," Calcolo, v. 21, 1984, pp. 295305. MR 799994 (86j:65016)
 [6]
 B. Dimsdale, "Convex cubic splines, " IBM J. Res. Develop., v. 22, 1978, pp. 168178. MR 0494833 (58:13617)
 [7]
 A. Edelman & C. A. Micchelli, "Admissible slopes for monotone and convex interpolation," Numer. Math., v. 51, 1987, pp. 441458. MR 902100 (89b:65031)
 [8]
 S. C. Eisenstat, K. R. Jackson & J. W. Lewis, "The order of monotone piecewise cubic interpolation," SIAM J. Numer. Anal., v. 22, 1985, pp. 12201237. MR 811195 (87d:65014)
 [9]
 J. C. Ferguson, Shape Preserving Parametric Cubic Curve Interpolation, Ph. D. thesis, University of New Mexico, 1984.
 [10]
 J. C. Ferguson & K. Miller, Characterization of Shape in a Class of Third Degree Algebraic Curves, TRW report 532235, 1969.
 [11]
 F. N. Fritsch, Use of the Bernstein Form to Derive Sufficient Conditions for Shape Preserving Piecewise Polynomial Interpolation, Lawrence Livermore National Laboratory report UCRL91392, March 1984.
 [12]
 F. N. Fritsch & J. Butland, "A method for constructing local monotone piecewise cubic interpolants", SIAM J. Sci. Statist. Comput., v. 5, 1984, pp. 300304. MR 740848 (85h:65022)
 [13]
 F. N. Fritsch & R. E. Carlson, "Monotone piecewise cubic interpolation," SIAM J. Numer. Anal., v. 17, 1980, pp. 238246. MR 567271 (81g:65012)
 [14]
 J. M. Hyman, "Accurate monotonicity preserving cubic interpolation," SIAM J. Sci. Statist. Comput., v. 4, 1983, pp. 645654. MR 725659 (85a:65021)
 [15]
 J. M. Hyman, Accurate ConvexityPreserving Cubic Interpolation, informal report, Los Alamos Scientific Laboratory document, LAUR803700, Los Alamos, NM, November 1980.
 [16]
 J. M. Hyman & B. Larrouturou, "The numerical differentiation of discrete functions using polynomial interpolation methods," Numerical Grid Generation for Numerical Solution of Partial Differential Equations (J.F. Thompson, ed.), Elsevier NorthHolland, New York, 1982, pp. 487506. MR 675799
 [17]
 D. F. McAllister, E. Passow & J. A. Roulier, "Algorithms for computing shape preserving spline interpolations to data," Math. Comp., v. 31, 1977, pp. 717725. MR 0448805 (56:7110)
 [18]
 D. F. McAllister & J. A. Roulier, "An algorithm for computing a shape preserving oscillatory quadratic spline," ACM Trans. Math. Software, v. 7, 1982, pp. 331347. MR 630439 (82h:65009)
 [19]
 D. F. McAllister & J. A. Roulier, "Interpolation by convex quadratic splines," Math. Comp., v. 32, 1978, pp. 11541162. MR 0481734 (58:1833)
 [20]
 H. Mettke, "Convex cubic Hermitespline interpolation," J. Comput. Appl. Math., v. 9, 1983, pp. 205211, and v. 11, 1984, pp. 377378. MR 715537 (86f:65038a)
 [21]
 E. Neuman, "Convex interpolating splines of arbitrary degree II," BIT, v. 22, 1982, pp. 331338. MR 675667 (84i:41016)
 [22]
 E. Passow & J. A. Roulier, "Monotonic and convex spline interpolation," SIAM J. Numer. Anal., v. 14, 1977, pp. 904909. MR 0470566 (57:10316)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
41A05,
65D05
Retrieve articles in all journals
with MSC:
41A05,
65D05
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198909622091
PII:
S 00255718(1989)09622091
Keywords:
Approximation theory,
convexity,
interpolation,
monotonicity,
shape preservation,
spline
Article copyright:
© Copyright 1989
American Mathematical Society
