Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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 $. –  user58200 Jan 14 '13 at 4:16
    
@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! –  Cristian Jan 14 '13 at 4:17
    
@Cristian: blah essentially answers this. $ | \sup{f} - f(\hat{x}) | $ is bounded by $ h \sup | f' |$. –  user58200 Jan 14 '13 at 4:36
add comment

1 Answer

up vote 1 down vote accepted

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)|$.

share|improve this answer
    
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? –  Cristian Jan 14 '13 at 4:28
1  
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. –  blah Jan 14 '13 at 4:44
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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