Algorithms for Finding Zeros and Extrema of Functions Without Calculating Derivatives
STANFORD UNIV CA DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
Theorems are given concerning the order i.e., rate of convergence of a successive interpolation process for finding simple zeros of a function or its derivatives, using only function evaluations. Special cases include the successive linear interpolation process for finding zeros, and a parabolic interpolation process for finding turning points. Results on interpolation and finite differences include weakening the hypotheses of a theorem of Ralston on the derivative of the error in Lagrangian interpolation. The theoretical results are applied to given algorithms for finding zeros or local minima of functions of one variable, in the presence of rounding errors. The algorithms are guaranteed to converge nearly as fast as would bisection or Fibonacci search, and in most practical cases convergence is superlinear, and much faster than for bisection or Fibonacci search.
- Theoretical Mathematics
- Computer Programming and Software
- Computer Hardware