Algorithms for piecewise polynomials and splines with free knots

Meinardus, G.; Nürnberger, G.; Sommer, M.; Strauss, H.

doi:10.1090/S0025-5718-1989-0969492-7

Algorithms for piecewise polynomials and splines with free knots
HTML articles powered by AMS MathViewer

by G. Meinardus, G. Nürnberger, M. Sommer and H. Strauss PDF

Math. Comp. 53 (1989), 235-247 Request permission

Abstract:

We describe an algorithm for computing points $a = {x_0} < {x_1} < \cdots < {x_k} < {x_{k + 1}} = b$ which solve certain nonlinear systems $d({x_{i - 1}},{x_i}) = d({x_i},{x_{i + 1}})$, $i = 1, \ldots ,k$. In contrast to Newton-type methods, the algorithm converges when starting with arbitrary points. The method is applied to compute best piecewise polynomial approximations with free knots. The advantage is that in the starting phase only simple expressions have to be evaluated instead of computing best polynomial approximations. We finally discuss the relation to the computation of good spline approximations with free knots.

References

Carl de Boor, Good approximation by splines with variable knots, Spline functions and approximation theory (Proc. Sympos., Univ. Alberta, Edmonton, Alta., 1972) Internat. Ser. Numer. Math., Vol. 21, Birkhäuser, Basel, 1973, pp. 57–72. MR 0403169
Carl de Boor, Good approximation by splines with variable knots. II, Conference on the Numerical Solution of Differential Equations (Univ. Dundee, Dundee, 1973) Lecture Notes in Math., Vol. 363, Springer, Berlin, 1974, pp. 12–20. MR 0431606
Carl de Boor, A practical guide to splines, Applied Mathematical Sciences, vol. 27, Springer-Verlag, New York-Berlin, 1978. MR 507062
Hermann G. Burchard, Splines (with optimal knots) are better, Applicable Anal. 3 (1973/74), 309–319. MR 399708, DOI 10.1080/00036817408839073

Optimal Order Approximation by Polynomial Spline Functions

Charles L. Lawson, Characteristic propertiesof the segmented rational minmax approximation problem, Numer. Math. 6 (1964), 293–301. MR 176278, DOI 10.1007/BF01386077
Günter Meinardus, Approximation of functions: Theory and numerical methods, Expanded translation of the German edition, Springer Tracts in Natural Philosophy, Vol. 13, Springer-Verlag New York, Inc., New York, 1967. Translated by Larry L. Schumaker. MR 0217482
Günter Meinardus and Gerhard Merz, Praktische Mathematik. I, Bibliographisches Institut, Mannheim, 1979 (German). Für Ingenieure, Mathematiker und Physiker. MR 535443
Günther Nürnberger and Manfred Sommer, A Remez type algorithm for spline functions, Numer. Math. 41 (1983), no. 1, 117–146. MR 696554, DOI 10.1007/BF01396309
G. Nürnberger, M. Sommer, and H. Strauss, An algorithm for segment approximation, Numer. Math. 48 (1986), no. 4, 463–477. MR 834333, DOI 10.1007/BF01389652
Theodore J. Rivlin, An introduction to the approximation of functions, Blaisdell Publishing Co. [Ginn and Co.], Waltham, Mass.-Toronto, Ont.-London, 1969. MR 0249885