Mathematics of Computation

An unconditionally convergent method for computing zeros of splines and polynomials

Author(s): Knut Mørken; Martin Reimers.
Journal: Math. Comp. 76 (2007), 845-865.
MSC (2000): Primary 41A15, 65D07, 65H05
Posted: January 9, 2007
Retrieve article in: PDF DVI PostScript

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.

1.: W. Boehm.
Inserting new knots into B-spline curves.
Computer Aided Design, 12:199-201, 1980.
2.: G. Dahlquist and A. Björck.
Numerical Methods.
Wiley-Interscience, 1980.
3.: T. A. Grandine.
Computing zeroes of spline functions.
Computer Aided Geometric Design, 6:129-136, 1989. MR 992731 (90a:65115)
4.: T. Lyche and K. Mørken.
Spline Methods, draft.
Deparment of Informatics, University of Oslo, http://heim.ifi.uio.no/~knutm/komp04.pdf, 2004.
5.: 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.
6.: A. Rockwood, K. Heaton, and T. Davis.
Real-time Rendering of Trimmed Surfaces.
Computer Graphics, 23(3), 1989.
7.: L. L. Schumaker.
Spline functions: Basic theory.
Prentice Hall, 1974.
8.: M. R. Spencer.
Polynomial real root finding in Bernstein form.
Ph.D. thesis, Brigham Young University, 1994.

Retrieve articles in Mathematics of Computation with MSC (2000): 41A15, 65D07, 65H05

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

DOI: 10.1090/S0025-5718-07-01923-0
PII: S 0025-5718(07)01923-0
Received by editor(s): April 1, 2005
Received by editor(s) in revised form: November 27, 2005
Posted: January 9, 2007
Copyright of article: Copyright 2007, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS