An unconditionally convergent method for computing zeros of splines and polynomials
HTML articles powered by AMS MathViewer
- by Knut Mørken and Martin Reimers;
- Math. Comp. 76 (2007), 845-865
- DOI: https://doi.org/10.1090/S0025-5718-07-01923-0
- Published electronically: January 9, 2007
- PDF | Request permission
Abstract:
We present a simple and efficient method for computing zeros of spline functions. The method exploits the close relationship between a spline and its control polygon and is based on repeated knot insertion. Like Newton’s method it is quadratically convergent, but the new method overcomes the principal problem with Newton’s method in that it always converges and no starting value needs to be supplied by the user.References
- W. Boehm. Inserting new knots into B-spline curves. Computer Aided Design, 12:199–201, 1980.
- G. Dahlquist and A. Björck. Numerical Methods. Wiley-Interscience, 1980.
- Thomas A. Grandine, Computing zeroes of spline functions, Comput. Aided Geom. Design 6 (1989), no. 2, 129–136. MR 992731, DOI 10.1016/0167-8396(89)90016-2
- T. Lyche and K. Mørken. Spline Methods, draft. Deparment of Informatics, University of Oslo, http://heim.ifi.uio.no/˜knutm/komp04.pdf, 2004.
- T. Nishita, T. W. Sederberg, and M. Kakimoto. Ray tracing trimmed rational surface patches. In Proceedings of the 17th annual conference on Computer graphics and interactive techniques, pages 337–345. ACM Press, 1990.
- A. Rockwood, K. Heaton, and T. Davis. Real-time Rendering of Trimmed Surfaces. Computer Graphics, 23(3), 1989.
- L. L. Schumaker. Spline functions: Basic theory. Prentice Hall, 1974.
- M. R. Spencer. Polynomial real root finding in Bernstein form. Ph.D. thesis, Brigham Young University, 1994.
Bibliographic Information
- Knut Mørken
- Affiliation: Department of Informatics and Center of Mathematics for Applications, P.O. Box 1053, Blindern, 0316 Oslo, Norway
- Email: knutm@ifi.uio.no
- Martin Reimers
- Affiliation: Center of Mathematics for Applications, P.O. Box 1053, Blindern, 0316 Oslo, Norway
- Email: martinre@ifi.uio.no
- Received by editor(s): April 1, 2005
- Received by editor(s) in revised form: November 27, 2005
- Published electronically: January 9, 2007
- © Copyright 2007
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 76 (2007), 845-865
- MSC (2000): Primary 41A15, 65D07, 65H05
- DOI: https://doi.org/10.1090/S0025-5718-07-01923-0
- MathSciNet review: 2291839