Let $f:[0,1]\rightarrow \mathbb{R}$ be a continuously differentiable function that reaches a global maximum at $x^*\in(0,1)$. Now, consider its 'discrete' counterpart. That is, consider the collection $\{(x_1,f(x_1)),(x_2,f(x_2)),\ldots,(x_n,f(x_n)\}$ where $x_1<x_2<\cdots <x_n$, and $h=x_{n+1}-x_{n}$ 'small'.

Under what conditions on $h$ (or something else) can I claim that the maximum found using the continuous function $f$ approximates reasonably well the value $f(\hat{x})$ satisfying $f(\hat{x})\geq f(x_i)$ for all $x_i\in \{x_1,x_2,\ldots,x_n\}$?

Thanks for your help!

  • $\begingroup$ I don't understand what $ \hat{x} $ is. If I assume that it is it one of the $ x_i $, then roughly the error is related to the bound on the derivative of $ f $. $\endgroup$ – user58200 Jan 14 '13 at 4:16
  • $\begingroup$ @user58200: Yup. $\hat{x}$ is supposed to be one of the $x_i$'s in the grid. Would you mind elaborating on the argument about the error being related to the bound of the derivative of $f$? Thanks! $\endgroup$ – Cristian Jan 14 '13 at 4:17
  • $\begingroup$ @Cristian: blah essentially answers this. $ | \sup{f} - f(\hat{x}) | $ is bounded by $ h \sup | f' |$. $\endgroup$ – user58200 Jan 14 '13 at 4:36

This depends on "how continuous" $f$ is. It's possible to construct continuously differentiable functions that have arbitrarily narrow spikes (e.g. Gaussian as $\sigma \rightarrow 0$). For these functions, sampling at $h$ sized intervals can be arbitrarily wrong.

Using the $\epsilon$-$\delta$ definition of continuity, for any error tolerance $\epsilon > 0$ there exists $\delta > 0$ such that when $|x - \hat x| < \delta$, we have $|f(x) - f(\hat x)| < \epsilon$. In other words, you need to know about $f$ to determine a bound for $h$.

Using differentiability and the mean value theorem, we can deduce that $|f(x) - f(\hat x)| \le |x - \hat x| \sup_{x \in (0, 1)} |f'(x)|$.

  • $\begingroup$ I see, but then if the distance $x_{n+1}-x_{n}$ is small (though not infinitesimal), finding the value $x^*_i$ such that $f(x^*_i)>f(x_i)$ for all $x_i$ in the grid can be done using the continuous approximation, correct? $\endgroup$ – Cristian Jan 14 '13 at 4:28
  • 1
    $\begingroup$ Right, as long as $f$ is sufficiently well-behaved. If $f$ looks like a smooth interpolation of the discrete $f$, you should be fine. You might run into an off-by-one error where, for example, $f(0.1)$ is the maximum with $h = 0.1$, but $f(0.151)$ is the continuous maximum. Then you might round $0.151$ to $0.2$ and incorrectly conclude that $f(0.2)$ is the discrete maximum. $\endgroup$ – blah Jan 14 '13 at 4:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.