Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

An unconditionally convergent method for computing zeros of splines and polynomials


Authors: Knut Mørken and Martin Reimers
Journal: Math. Comp. 76 (2007), 845-865
MSC (2000): Primary 41A15, 65D07, 65H05
Published electronically: January 9, 2007
MathSciNet review: 2291839
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 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. Thomas A. Grandine, Computing zeroes of spline functions, Comput. Aided Geom. Design 6 (1989), no. 2, 129–136. MR 992731 (90a:65115), http://dx.doi.org/10.1016/0167-8396(89)90016-2
  • 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.

Similar Articles

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

Retrieve articles in all journals with MSC (2000): 41A15, 65D07, 65H05


Additional 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

DOI: http://dx.doi.org/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
Published electronically: January 9, 2007
Article copyright: © Copyright 2007 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.