# Efficiently approximating derivative of a well-behaved function

I need an algorithm for adaptive sampling a well-behaved function and computing its derivative in the sampling range with prescribed accuracy. The function has no more than one minimum in the sampling range. If it has no minimum in the sampling range it is monotonic. The derivatives of the first and of the second order exist in any point in the sampling range and are continuous as well as the function itself. The algorithm must take the minimum number of points of the objective function and allow computing its derivative in any point in the sampling range with prescribed accuracy (number of precise digits of the derivative). Probably such an algorithm is already developed and well-tested. Please help me to find it. The algorithm is supposed to be implemented in the Wolfram Mathematica system.

• what sort of query complexity are you expecting for your algorithm? A function defined on $1, ... , n$ that outputs $f_k(k) = 0$ and $f_k(i) = 1$ (if $i \neq k$) would satisfy your condition. Note that knowing the derivative of this function requires solving unordered search. Or would this count as having a 'break'? If you want, we can smooth this function without changing its behavior to be continuous in the calculus sense. – Artem Kaznatcheev May 25 '12 at 19:12
• @Artem The objective function is a real-valued continuous function in the calculus sense. – Alexey Popkov May 26 '12 at 4:21
• Such problems are studied in Computable Analysis, see the book by Pour-El and Richards with the same title, or by Ker-I Ko, Computability and Complexity in Analysis. Without any further assumptions your problem is not solvable at all. There is a monotone computable $C^1$ function such that its derivative is not computable. On the other hand, every computable $C^2$ has a computable derivative. This model assumes that you have oracle access to the given function and get approximations of any desired accuracy. – Markus Bläser May 26 '12 at 23:05
• @Tsuyoshi I meant that the function is continuous. I updated the question with more clear description (I hope). – Alexey Popkov May 28 '12 at 3:59
• The subbranch of computable analysis that deals with minimizing the number of function evaluation/queries is called "information-based complexity", see ibc-research.org for some more pointers. – Markus Bläser May 28 '12 at 18:54