On the numerical condition of BernsteinBézier subdivision processes
Authors:
R. T. Farouki and C. A. Neff
Journal:
Math. Comp. 55 (1990), 637647
MSC:
Primary 65D10; Secondary 65D15, 68T10, 68U05
DOI:
https://doi.org/10.1090/S00255718199010359330
MathSciNet review:
1035933
Fulltext PDF Free Access
Abstract  References  Similar Articles  Additional Information
Abstract: The linear map M that takes the Bernstein coefficients of a polynomial $P(t)$ on a given interval [a, b] into those on any subinterval $[\bar a,\bar b]$ is specified by a stochastic matrix which depends only on the degree n of $P(t)$ and the size and location of $[\bar a,\bar b]$ relative to [a, b]. We show that in the ${\left \ \bullet \right \_\infty }$norm, the condition number of M has the simple form ${\kappa _\infty }({\mathbf {M}}) = {[2f\max ({u_{\bar m}},{v_{\bar m}})]^n}$, where ${u_{\bar m}} = (\bar m  a)/(b  a)$ and ${v_{\bar m}} = (b  \bar m)/(b  a)$ are the barycentric coordinates of the subinterval midpoint $\bar m = \frac {1}{2}( {\bar a + \bar b} )$, and f denotes the "zoom" factor $(b  a)/(\bar b  \bar a)$ of the subdivision map. This suggests a practical ruleofthumb in assessing how far Bézier curves and surfaces may be subdivided without exceeding prescribed (worstcase) bounds on the typical errors in their control points. The exponential growth of ${\kappa _\infty }({\mathbf {M}})$ with n also argues forcefully against the use of highdegree forms in computeraided geometric design applications.

E. Cohen, T. Lyche, and R. Riesenfeld, Discrete Bsplines and subdivision techniques in computeraided geometric design and computer graphics, Comput. Graphics Image Processing 14 (1980), 87111.
 Mischa Cotlar and Roberto Cignoli, An introduction to functional analysis, NorthHolland Publishing Co., AmsterdamLondon; American Elsevier Publishing Co., Inc., New York, 1974. Translated from the Spanish by A. Torchinsky and A. González Villalobos; NorthHolland Texts in Advanced Mathematics. MR 0405049 P. de Casteljau, Courbes et surfaces à pôles, André Citroën Automobiles SA, Paris (unpublished notes), 1963.
 Gerald Farin, Curves and surfaces for computer aided geometric design, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1988. A practical guide; With contributions by P. Bézier and W. Boehm. MR 974109
 R. T. Farouki and V. T. Rajan, On the numerical condition of polynomials in Bernstein form, Comput. Aided Geom. Design 4 (1987), no. 3, 191–216. MR 917780, DOI https://doi.org/10.1016/01678396%2887%29900124
 R. T. Farouki and V. T. Rajan, Algorithms for polynomials in Bernstein form, Comput. Aided Geom. Design 5 (1988), no. 1, 1–26. MR 945302, DOI https://doi.org/10.1016/01678396%2888%29900167
 William Feller, An Introduction to Probability Theory and Its Applications. Vol. I, John Wiley & Sons, Inc., New York, N.Y., 1950. MR 0038583 R. N. Goldman, Markov chains and computeraided geometric design: Part I—problems and constraints, ACM Trans. Graphics 3 (1984), 204222. , Markov chains and computeraided geometric design: Part II—examples and subdivision matrices, ACM Trans. Graphics 4 (1985), 1240.
 Peter Henrici, Elements of numerical analysis, John Wiley & Sons, Inc., New YorkLondonSydney, 1964. MR 0166900 J. M. Lane and R. F. Riesenfeld, A theoretical development for the computer generation and display of piecewise polynomial surfaces, IEEE Trans. Pattern Anal. Mach. Intell. 2 (1980), 3546.
 Jeffrey M. Lane and R. F. Riesenfeld, Bounds on a polynomial, BIT 21 (1981), no. 1, 112–117. MR 616705, DOI https://doi.org/10.1007/BF01934076
 I. J. Schoenberg, On variation diminishing approximation methods, On numerical approximation. Proceedings of a Symposium, Madison, April 2123, 1958, Edited by R. E. Langer. Publication no. 1 of the Mathematics Research Center, U.S. Army, the University of Wisconsin, The University of Wisconsin Press, Madison, 1959, pp. 249–274. MR 0102167
 Elias M. Stein and Guido Weiss, Introduction to Fourier analysis on Euclidean spaces, Princeton University Press, Princeton, N.J., 1971. Princeton Mathematical Series, No. 32. MR 0304972
 G. W. Stewart, Introduction to matrix computations, Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New YorkLondon, 1973. Computer Science and Applied Mathematics. MR 0458818
 J. H. Wilkinson, Rounding errors in algebraic processes, PrenticeHall, Inc., Englewood Cliffs, N.J., 1963. MR 0161456
 J. H. Wilkinson, The algebraic eigenvalue problem, Monographs on Numerical Analysis, The Clarendon Press, Oxford University Press, New York, 1988. Oxford Science Publications. MR 950175
Retrieve articles in Mathematics of Computation with MSC: 65D10, 65D15, 68T10, 68U05
Retrieve articles in all journals with MSC: 65D10, 65D15, 68T10, 68U05
Additional Information
Article copyright:
© Copyright 1990
American Mathematical Society