Algorithms for Finding Zeros and Extrema of Functions Without Calculating Derivatives

Abstract

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 1971
Accession Number
AD0726170

Entities

People

  • Richard P. Brent

Organizations

  • Stanford University

Tags

Communities of Interest

  • Materials and Manufacturing Processes
  • Space

DTIC Thesaurus Topics

  • Algorithms
  • Artificial Intelligence
  • Computational Fluid Dynamics
  • Computational Science
  • Computations
  • Computer Programming
  • Computer Programs
  • Computer Science
  • Computers
  • Differential Equations
  • Floating Point Operations
  • Linear Programming
  • Mathematical Programming
  • Nonlinear Programming
  • Numerical Analysis
  • Optimization
  • Simplex Method

Readers

  • Calculus or Mathematical Analysis
  • Graph Algorithms and Convex Optimization.