Computing roots of polynomials by quadratic clipping. (English) Zbl 1171.65395

Bartoň, Michael; Jüttler, Bert

Comput. Aided Geom. Des. 24, No. 3, 125-141 (2007).

Summary: We present an algorithm which is able to compute all roots of a given univariate polynomial within a given interval. In each step, we use degree reduction to generate a strip bounded by two quadratic polynomials which encloses the graph of the polynomial within the interval of interest. The new interval(s) containing the root(s) is (are) obtained by intersecting this strip with the abscissa axis. In the case of single roots, the sequence of the lengths of the intervals converging towards the root has the convergence rate 3. For double roots, the convergence rate is still superlinear (\(\frac32\)). We show that the new technique compares favorably with the classical technique of Bézier clipping.

MSC:

65H05

Numerical computation of solutions to single equations

Keywords:

root finding; polynomial; Bézier clipping

Software:

Axel

References:

[1]	Ahn, Y. J.; Lee, B.-G.; Park, Y.; Yoo, J., Constrained polynomial degree reduction in the \(L_2\)-norm equals best weighted Euclidean approximation of Bézier coefficients, Computer Aided Geometric Design, 21, 181-191 (2004) · Zbl 1069.41504
[2]	Ciesielski, Z., The basis of B-splines in the space of algebraic polynomials, Ukrainian Math. J., 38, 311-315 (1987) · Zbl 0614.41013
[3]	Eck, M., Degree reduction of Bézier curves, Computer Aided Geometric Design, 10, 237-251 (1992) · Zbl 0786.65016
[4]	Efremov, A.; Havran, V.; Seidel, H.-P., Robust and numerically stable Bézier clipping method for ray tracing NURBS surfaces, (Proc. 21st Spring Conference on Computer Graphics (2005), ACM Press: ACM Press New York), 127-135
[5]	Elber, G., Kim, M.-S., 2001. Geometric constraint solver using multivariate rational spline functions. In: The Sixth ACM/IEEE Symposium on Solid Modeling and Applications, Ann Arbor, MI, pp. 1-10; Elber, G., Kim, M.-S., 2001. Geometric constraint solver using multivariate rational spline functions. In: The Sixth ACM/IEEE Symposium on Solid Modeling and Applications, Ann Arbor, MI, pp. 1-10
[6]	Farouki, R. T.; Goodman, T. N.T., On the optimal stability of the Bernstein basis, Math. Comp., 65, 1553-1566 (1996) · Zbl 0853.65051
[7]	Gatellier, G.; Labrouzy, A.; Mourrain, B.; Técourt, J., Computing the topology of three-dimensional algebraic curves, (Dokken, T.; Jüttler, B., Computational Methods for Algebraic Spline Surfaces (2003), Springer: Springer Berlin), 27-43 · Zbl 1077.14089
[8]	Gautschi, W., Numerical Analysis (1997), Birkhäuser: Birkhäuser Boston, MA · Zbl 0877.65001
[9]	Gonzalez-Vega, L.; Necula, I., Efficient topology determination of implicitly defined algebraic plane curves, Computer Aided Geometric Design, 19, 719-743 (2002) · Zbl 1043.68105
[10]	Hoschek, J.; Lasser, D., Fundamentals of Computer Aided Geometric Design (1993), AK Peters: AK Peters Wellesley, MA · Zbl 0788.68002
[11]	Jüttler, B., The dual basis functions of the Bernstein polynomials, Adv. Comput. Math., 8, 345-352 (1998) · Zbl 0913.41004
[12]	Kim, M.-S.; Elber, G.; Seong, J.-K., Geometric computations in parameter space, (Proc. 21st Spring Conference on Computer Graphics (2005), ACM: ACM New York), 27-32
[13]	Lee, K., Principles of CAD/CAM/CAE Systems (1999), Prentice-Hall
[14]	Li, T., Numerical solution of polynomial systems by homotopy continuation methods, (Cucker, F., Special Volume: Foundations of Computational Mathematics. Special Volume: Foundations of Computational Mathematics, Handbook of Numerical Analysis, vol. XI (2003), North-Holland: North-Holland Amsterdam), 209-304 · Zbl 1059.65046
[15]	Lutterkort, D.; Peters, J.; Reif, U., Polynomial degree reduction in the \(L_2\)-norm equals best Euclidean approximation of Bézier coefficients, Computer Aided Geometric Design, 16, 607-612 (1999) · Zbl 0993.41016
[16]	McNamee, J. M., Bibliographies on roots of polynomials, J. Comp. Appl. Math. 47, 391-394; 78, 1-1; 110, 305-306; 142, 433-434, available at · Zbl 0788.65056
[17]	Mourrain, B.; Pavone, J.-P., Subdivision methods for solving polynomial equations, Technical Report, no. 5658, INRIA Sophia Antipolis
[18]	Nishita, T.; Sederberg, T. W.; Kakimoto, M., Ray tracing trimmed rational surface patches, ((1990), Siggraph Proceedings: Siggraph Proceedings ACM), 337-345
[19]	Nishita, T.; Sederberg, T. W., Curve intersection using Bézier clipping, Computer-Aided Design, 22, 9, 538-549 (1990) · Zbl 0716.65005
[20]	Patrikalakis, N. M.; Maekawa, T., Intersection problems, (Farin, G.; Hoschek, J.; Kim, M.-S., Handbook of Computer Aided Geometric Design (2002), Elsevier: Elsevier Amsterdam), 623-649, (Chapter 25) · Zbl 1003.68179
[21]	Patrikalakis, N. M.; Maekawa, T., Shape Interrogation for Computer Aided Design and Manufacturing (2002), Springer: Springer Berlin · Zbl 1035.65016
[22]	Sherbrooke, E. C.; Patrikalakis, N. M., Computation of the solutions of nonlinear polynomial systems, Computer Aided Geometric Design, 10, 379-405 (1993) · Zbl 0817.65035
[23]	Sommese, A. J.; Wampler, C. W., The Numerical Solution of Systems of Polynomials Arising in Engineering and Science (2005), World Scientific: World Scientific Singapore · Zbl 1091.65049
[24]	Sunwoo, H., Matrix representation for multi-degree reduction of Bézier curves, Computer Aided Geometric Design, 22, 261-273 (2005) · Zbl 1087.65014
[25]	Wang, H.; Kearney, J.; Atkinson, K., Robust and efficient computation of the closest point on a spline curve, (Lyche, T.; etal., Curve and Surface Design. Curve and Surface Design, Saint Malo 2002 (2003), Nashboro Press: Nashboro Press Brentwood), 397-405 · Zbl 1043.65046