Shape-preservation conditions for cubic spline interpolation

V. V. Bogdanov ; Yu. S. Volkov

Matematičeskie trudy, Tome 22 (2019) no. 1, pp. 19-67.

Résumé

We consider the problem on shape-preserving interpolation by classical cubic splines. Namely, we consider conditions guaranteeing that, for a positive function (or a function whose $k$th derivative is positive), the cubic spline (respectively, its $k$th derivative) is positive. We present a survey of known results, completely describe the cases in which boundary conditions are formulated in terms of the first derivative, and obtain similar results for the second derivative. We discuss in detail mathematical methods for obtaining sufficient conditions for shape-preserving interpolation. We also develop such methods, which allows us to obtain general conditions for a spline and its derivative to be positive. We prove that, for a strictly positive function (or a function whose derivative is positive), it is possible to find an interpolant of the same sign as the initial function (respectively, its derivative) by thickening the mesh.

Bibliographie

[1] Alberg Dzh., Nilson E., Uolsh Dzh., Teoriya splainov i ee prilozheniya, Mir, M., 1972; Ahlberg J. H., Nilson E. N., Walsh J. L., The Theory of Splines and Their Applications, Academic Press, New York–London, 1967 | MR | Zbl

[2] Bogdanov V. V., “Dostatochnye usloviya komonotonnoi interpolyatsii kubicheskimi splainami klassa $C^2$”, Matem. tr., 14:2 (2011), 3–13 ; Bogdanov V. V., “Sufficient conditions for the comonotone interpolation of cubic $C^2$-splines”, Siberian Adv. Math., 22:3 (2012), 153–160 | DOI | Zbl | DOI | MR

[3] Bogdanov V. V., “Dostatochnye usloviya neotritsatelnosti resheniya sistemy uravnenii s nestrogo yakobievoi matritsei”, Sib. matem. zhurn., 54:3 (2013), 544–550 | MR | Zbl

[4] Bogdanov V. V., Volkov Yu. S., “Vybor parametrov obobschennykh kubicheskikh splainov pri vypukloi interpolyatsii”, Sib. zhurn. vychisl. matem., 9:1 (2006), 5–22 | Zbl

[5] Bogdanov V. V., Volkov Yu. S., “Ob usloviyakh formosokhraneniya pri interpolyatsii parabolicheskimi splainami po Subbotinu”, Tr. IMM UrO RAN, 22, no. 4, 2016, 102–113

[6] de Bor K., Prakticheskoe rukovodstvo po splainam, Radio i svyaz, M., 1985 ; C. de Boor, A Practical Guide to Splines, Spinger-Verlag, New York–Heidelberg–Berlin, 1978 | MR | MR

[7] Volkov Yu. S., “Primenenie ratsionalnykh kubicheskikh splainov dlya rascheta dinamicheskikh kharakteristik dvigatelya”, Splainy i ikh prilozheniya, Vychislitelnye sistemy, 154, IM SO RAN, Novosibirsk, 1995, 65–72

[8] Volkov Yu. S., “O postroenii interpolyatsionnykh polinomialnykh splainov”, Splain-funktsii i ikh prilozheniya, Vychislitelnye sistemy, 159, IM SO RAN, Novosibirsk, 1997, 3–18

[9] Volkov Yu. S., “O neotritsatelnom reshenii sistemy uravnenii s simmetricheskoi tsirkulyantnoi matritsei”, Matem. zametki, 70:2 (2001), 170–180 | DOI | Zbl

[10] Volkov Yu. S., “O monotonnoi interpolyatsii kubicheskimi splainami”, Vychisl. tekhnol., 6:6 (2001), 14–24 | MR | Zbl

[11] Volkov Yu. S., “Novyi sposob postroeniya interpolyatsionnykh kubicheskikh splainov”, Dokl. RAN, 382:2 (2002), 155–157 | MR | Zbl

[12] Volkov Yu. S., “Novyi sposob postroeniya interpolyatsionnykh kubicheskikh splainov”, Zh. vychisl. matem. i matem. fiz., 44:2 (2004), 231–241 | MR | Zbl

[13] Volkov Yu. S., “Vpolne neotritsatelnye matritsy v metodakh postroeniya interpolyatsionnykh splainov nechetnoi stepeni”, Matem. tr., 7:2 (2004), 3–34 ; Volkov Yu. S., “Totally positive matrices in the methods of constructing interpolation splines of odd degree”, Siberian Adv. Math., 15:4 (2005), 96–125 | MR | Zbl

[14] Volkov Yu. S., “O nakhozhdenii polnogo interpolyatsionnogo splaina cherez $B$-splainy”, Sib. elektron. matem. izv., 5 (2008), 334–338 | Zbl

[15] Volkov Yu. S., “Issledovanie skhodimosti protsessa interpolyatsii dlya proizvodnykh polnogo splaina”, Ukr. matem. visnik, 9:2 (2012), 278–296 | Zbl

[16] Volkov Yu. S., Bogdanov V. V., Miroshnichenko V. L., Shevaldin V. T., “Formosokhranyayuschaya interpolyatsiya kubicheskimi splainami”, Matem. zametki, 88:6 (2010), 836–844 | DOI | Zbl

[17] Volkov Yu. S., Galkin V. M., “O vybore approksimatsii v pryamykh zadachakh postroeniya sopla”, Zh. vychisl. matem. i matem. fiz., 47:5 (2007), 923–936 | MR | Zbl

[18] Volkov Yu. S., Miroshnichenko V. L., “O priblizhenii proizvodnykh skachkom interpolyatsionnogo splaina”, Matem. zametki, 89:1 (2011), 127–130 | DOI | MR | Zbl

[19] Volkov Yu. S., Subbotin Yu. N., “50 let zadache Shënberga o skhodimosti splain-interpolyatsii”, Tr. IMM UrO RAN, 20, no. 1, 2014, 52–67 ; Volkov Yu. S., Subbotin Yu. N., “Fifty years of Schoenberg's problem on the convergence of spline interpolation”, Proc. Steklov Inst. Math., 288, suppl. 1 (2015), 222–237 | DOI | MR

[20] Volkov Yu. S., Shevaldin V. T., “Usloviya formosokhraneniya pri interpolyatsii splainami vtoroi stepeni po Subbotinu i po Marsdenu”, Tr. IMM UrO RAN, 18, no. 4, 2012, 145–152

[21] Zhanlav T., “Nekotorye otsenki priblizheniya vtorykh proizvodnykh s pomoschyu kubicheskikh interpolyatsionnykh splainov”, Vychislitelnye sistemy, 81, IM SO AN SSSR, Novosibirsk, 1979, 12–20

[22] Zavyalov Yu. S., “O neotritsatelnom reshenii sistemy uravnenii s nestrogo yakobievoi matritsei”, Sib. matem. zhurn., 37:6 (1996), 1303–1307 | MR | Zbl

[23] Zavyalov Yu. S., Kvasov B. I., Miroshnichenko V. L., Metody splain-funktsii, Nauka, M., 1980 | MR

[24] Kvasov B. I., Metody izogeometricheskoi approksimatsii splainami, Fizmatlit, M., 2006

[25] Kollatts L., Funktsionalnyi analiz i vychislitelnaya matematika, Mir, M., 1969; Collatz L., Funktionalanalysis und Numerische Mathematik, Springer-Verlag, Berlin, etc., 1964 | MR | Zbl

[26] Miroshnichenko V. L., “Dostatochnye usloviya monotonnosti i vypuklosti dlya interpolyatsionnykh kubicheskikh splainov klassa $C^2$”, Priblizhenie splainami, Vychislitelnye sistemy, 137, IM SO AN SSSR, Novosibirsk, 1990, 31–57; Miroshnichenko V. L., “Sufficient conditions for monotonicity and convexity of cubic splines of class $C^2$”, Siberian Adv. Math., 2:4 (1992), 147–163 | MR

[27] Miroshnichenko V. L., “Dostatochnye usloviya monotonnosti i vypuklosti dlya interpolyatsionnykh parabolicheskikh splainov”, Splainy i ikh prilozheniya, Vychislitelnye sistemy, 142, IM SO AN SSSR, Novosibirsk, 1991, 3–14; Miroshnichenko V. L., “Sufficient conditions for monotonicity and convexity of parabolic spline interpolants”, Siberian Adv. Math., 3:4 (1993), 101–107 | MR

[28] Miroshnichenko V. L., “Optimizatsiya vida ratsionalnogo splaina”, Splain-funktsii i ikh prilozheniya, Vychislitelnye sistemy, 159, IM SO RAN, Novosibirsk, 1997, 87–109

[29] Pinchukov V. I., “Monotonnyi nelokalnyi kubicheskii splain”, Zh. vychisl. matem. i matem. fiz., 41:2 (2001), 200–206 | MR | Zbl

[30] Dauner H., Reinsch C. H., “An analysis of two algorithms for shape-preserving cubic spline interpolation”, IMA J. Numer. Anal., 9:3 (1989), 299–314 | DOI | MR | Zbl

[31] Dupin J.-C., Fréville A., “Shape preserving interpolating cubic splines with geometric mesh”, Appl. Numer. Math., 9:6 (1992), 447–459 | DOI | MR | Zbl

[32] Fiorot J. C., Tabka J. Shape-Preserving $C^2$ cubic polynomial interpolating splines, Math. Comput., 57:195 (1991), 291–298 | MR | Zbl

[33] Fritsch F. N., Carlson R. E., “Monotone piecewise cubic interpolation”, SIAM J. Numer. Anal., 17:2 (1980), 238–246 | DOI | MR | Zbl

[34] Galkin V. M., Volkov Yu. S., “Elements of nozzle design optimization”, Computational Optimization: New Research Developments, eds. R. F. Linton, T. B. Carroll, Jr., Nova Science Publishers, New York, 2010, 97–128

[35] Holladay J. C., “A smoothest curve approximation”, Math. Tables Aids Comput., 11:10 (1957), 233–243 | DOI | MR | Zbl

[36] Hornung U., “Monotone Spline-Interpolation”, Numerische Methoden der Approximationstheorie, Vortragsauszüge der Tagung über numerische Methoden der Approximationstheorie (Oberwolfach, 1977), v. 4, ISNM, 42, eds. L. Collatz, G. Meinardus, H. Werner, Birkhäuser, Basel, 1978, 172–191 | MR

[37] Hornung U., “Interpolation by smooth functions under restrictions on the derivatives”, J. Approx. Theory, 28:3 (1980), 227–237 | DOI | MR | Zbl

[38] Kvasov B. I., Methods of Shape-Preserving Spline Approximation, World Scientific, Singapore, 2000 | MR | Zbl

[39] Miroshnichenko V. L., “Convex and monotone spline interpolation”, Constructive Theory of Functions '84, Proc. Internat. Conf. (Varna), Publ. House of Bulgar. Acad. Sci., Sofia, 1984, 610–620

[40] Neuman E., “Convex interpolating splines of arbitrary degree”, Numerical Methods of Approximation Theory, Excerpts of the Conf. on Numerical Methods of Approximation Theory (Oberwolfach, 1979), v. 5, ISNM, 52, eds. L. Collatz, G. Meinardus, H. Werner, Birkhäuser, Basel, 1980, 211–222 | MR

[41] Opfer G., Oberle H. J., “The derivation of cubic splines with obstacles by methods of optimization and optimal control”, Numer. Math., 52:1 (1988), 17–31 | DOI | MR | Zbl

[42] Passow E., “Piecewise monotone spline interpolation”, J. Approx. Theory, 12:3 (1974), 240–241 | DOI | MR | Zbl

[43] Passow E., “Monotone quadratic spline interpolation”, J. Approx. Theory, 19:2 (1977), 143–147 | DOI | MR | Zbl

[44] Passow E., Roulier J. A., “Monotone and convex spline interpolation”, SIAM J. Numer. Anal., 14:5 (1977), 904–909 | DOI | MR | Zbl

[45] Popoviciu T., “Sur le prolongement des fonctions convexes d'ordre supérieur”, Bull. Math. Soc. Roum. Sci., 36:1 (1934), 75–108

[46] Schmidt J. W., “On the convex cubic $C^2$-splines interpolation”, Numerical Methods of Approximation Theory, Workshop on Numerical Methods of Approximation Theory (Oberwolfach, 1986), v. 8, ISNM, 81, eds. L. Collatz, G. Meinardus, G. Nürnberger, Birkhäuser, Basel, 1987, 213–228 | MR

[47] Schmidt J. W., Heß W., “Positivity of cubic polynomials on intervals and positive spline interpolation”, BIT, 28:2 (1988), 340–352 | DOI | MR | Zbl

[48] Schweikert D. G., “An interpolation curve using a spline in tension”, J. Math. Phys., 45:3 (1966), 312–317 | DOI | MR | Zbl

[49] Shisha O., “Monotone approximation”, Pacific J. Math., 15:2 (1965), 667–671 | DOI | MR | Zbl

[50] Späth H., Spline Algorithms for Curves and Surfaces, Ultilitas Mathematica Publishing, Winnipeg, 1974 | MR | Zbl

[51] Volkov Yu. S., “Obtaining a banded system of equations in complete spline interpolation problem via $B$-spline basis”, Cent. Eur. J. Math., 10:1 (2012), 352–356 | DOI | MR | Zbl

[52] Volkov Yu. S., Galkin V. M., “Optimal nozzle design with monotonicity constraints”, Computer Design and Computational Defense Systems, Computer Science, Technology and Applications, ed. Mastorakis N. E., Nova Science Publishers, New York, 2011, 93–125