×

On the numerical condition of polynomials in Bernstein form. (English) Zbl 0636.65012

The Bernstein-Bézier curve and surface forms play an important part in approximation theory and computer aided design. From the point of view of condition numbers of polynomials, the authors discuss the advantages of the polynomials in Bernstein form over the polynomial in other forms. Generally speaking, the authors prove the following fact that, among a large family of polynomial bases, the Bernstein basis shows optimal root conditioning. At last, some examples are used to illustrate these results.
Reviewer: Cui Dayong

MSC:

65D10 Numerical smoothing, curve fitting
41A10 Approximation by polynomials
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Bernstein, S.N., On the best approximation of continuous functions by polynomials of a given degree, Comm. kharkow math. soc., series 2, 13, 49-194, (1912), (in Russian)
[2] Bézier, P., Procédé de définition numérique des courbes et surfaces non mathématiques; système UNISURF, Automatisme, 13, 391-407, (1968)
[3] Bézier, P., Numerical control — mathematics and applications, (1972), Wiley New York · Zbl 0251.93002
[4] Bézier, P., Essai de définition numérique des courbes et des surfaces expérimentales, () · Zbl 0157.42201
[5] Boehm, W.; Farin, G.; Kahmann, J., A survey of curve and surface methods in CAGD, Computer aided geometric design, 1, 1, 1-60, (1984) · Zbl 0604.65005
[6] Cargo, G.T.; Shisha, O., The Bernstein form of a polynomial, J. res. nat. bur. standards, 70B, 1, 79-81, (1966) · Zbl 0139.10003
[7] Chang, G.; Wu, J., Mathematical foundations of Bézier’s technique, Computer-aided design, 13, 133-136, (1981)
[8] Davis, P.J., Interpolation and approximation, (1963), Blaisdell New York · Zbl 0111.06003
[9] de Casteljau, P., Courbes et surfaces à Pôles, (1963), André Citroën Automobiles SA Paris, (unpublished notes)
[10] Farin, G., Konstruktion und eigenschaften von Bézier-kurven und Bézier-flächen, ()
[11] Farouki, R.T., The characterization of parametric surface sections, Computer vision, graphics and image processing, 33, 209-236, (1986) · Zbl 0631.65012
[12] Farouki, R.T.; Rajan, V.T., Algorithms for polynomials in Bernstein form, (1987), in preparation · Zbl 0636.65012
[13] Forrest, A.R., Interactive interpolation and approximation by Bézier polynomials, Computer J., 15, 1, 71-79, (1972) · Zbl 0243.68015
[14] Gautschi, W., The condition of orthogonal polynomials, Math. comput., 26, 120, 923-924, (1972) · Zbl 0261.33009
[15] Gautschi, W., On the condition of algebraic equations, Numer. math., 21, 405-424, (1973) · Zbl 0278.65044
[16] Gautschi, W., The condition of polynomials in power form, Math. comput., 33, 145, 343-352, (1979) · Zbl 0399.41002
[17] Gautschi, W., Questions of numerical condition related to polynomials, (), 140-177 · Zbl 0584.65020
[18] Goldman, R.N., Markov chains and computer-aided geometric design: part I — problems and constraints, ACM trans. graphics, 3, 3, 204-222, (1984) · Zbl 0592.68081
[19] Goldman, R.N., Polya’s urn model and computer aided geometric design, SIAM J. algebraic discrete methods, 6, 1, 1-28, (1985) · Zbl 0602.68103
[20] Gordon, W.J.; Riesenfeld, R.F., Bernstein-Bézier methods for the computer aided design of free-form curves and surfaces, J. ACM, 21, 2, 293-310, (1974) · Zbl 0276.68041
[21] Jenkins, M.A.; Traub, J.F., Principles for testing polynomial zerofinding programs, ACM trans. math. software, 1, 1, 26-34, (1975) · Zbl 0311.65039
[22] Kajiya, J.T., Ray tracing parametric patches, (), 245-254, (3)
[23] Knuth, D.E., (), 290-292
[24] Lane, J.M.; Riesenfeld, R.F., A theoretical development for the computer generation and display of piecewise polynomial surfaces, IEEE trans. pattern anal. machine intell., 2, 1, 35-46, (1980) · Zbl 0436.68063
[25] Lane, J.M.; Riesenfeld, R.F., Bounds on a polynomial, Bit, 21, 112-117, (1981) · Zbl 0472.65041
[26] Lorentz, G.G., Bernstein polynomials, (1953), University of Toronto Press Toronto · Zbl 0051.05001
[27] Mesztenyi, C.; Witzgall, C., Stable evaluation of polynomials, J. res. nat. bur. standards, 71B, 1, 11-17, (1967) · Zbl 0218.65016
[28] Ostrowski, A., On two problems in abstract algebra connected with Horner’s rule, (), 40-48 · Zbl 0056.35204
[29] Peters, G.; Wilkinson, J.H., Practical problems arising in the solution of polynomial equations, J. institute for mathematics and its applications, 8, 16-35, (1971) · Zbl 0232.65041
[30] Prautzsch, H., Unterteilungsalgorithmen für Bézier und B-spline flächen, ()
[31] Preparata, F.P.; Shamos, M.I., Computational geometry, (1985), Springer New York · Zbl 0759.68037
[32] Reimer, M., Bounds for the horner sums, SIAM J. numer. anal., 5, 3, 461-469, (1968) · Zbl 0205.17204
[33] Rice, J.R., On the conditioning of polynomial and rational forms, Numer. math., 7, 426-435, (1965) · Zbl 0139.10101
[34] Rice, J.R., A theory of condition, SIAM J. numer. anal., 3, 2, 287-310, (1966) · Zbl 0143.37101
[35] Rivlin, T.J., Bounds on polynomial, J. res. nat. bur. standards, 74B, 1, 47-54, (1970) · Zbl 0197.34704
[36] Rivlin, T.J., The Chebyshev polynomials, (1974), Wiley New York · Zbl 0291.33012
[37] Salmon, G., Lessons introductory to the modern higher algebra, (1885), Chelsea New York, (reprint)
[38] Schoenberg, I.J., On variation diminishing approximation methods, (), 249-274 · Zbl 0171.31001
[39] Sederberg, T.W.; Parry, S.R., Comparison of three curve intersection algorithms, Computer-aided design, 18, 1, 58-63, (1986)
[40] Sederberg, T.W.; Spencer, M.R.; de Boor, C., Root approximation of Bernstein polynomials, (1987), in preparation
[41] Sterbenz, P.H., Floating point computation, (1974), Prentice-Hall Englewood Cliffs, NJ
[42] Uspensky, J.V., Theory of equations, (1948), McGraw-Hill New York · Zbl 0005.11104
[43] Wilkinson, J.H.; Wilkinson, J.H., The evaluation of the zeros of ill-conditioned polynomials. parts I and II, Numer. math., Numer. math., 1, 167-180, (1959) · Zbl 0202.43701
[44] Wilkinson, J.H., Error analysis of floating-point computation, Numer. math., 2, 319-340, (1960) · Zbl 0091.29605
[45] Wilkinson, J.H., Rounding errors in algebraic processes, (1963), Prentice-Hall Englewood Cliffs, NJ · Zbl 0868.65027
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.