Error estimates of piecewise-linear curve approximations
It is impossible to achieve a guaranteed small error for general functions. If the function is given to you as a black box, for all you know it could be the constant zero other than some specific point in $[0,1]$ in which it is very large. If you have bounds on the first two derivatives, however, then you should be able to use Taylor's formula to accomplish your guaranteed approximation.

Matlab's function probably uses some heuristic, which works for reasonable functions. The idea of this heuristic is to empirically estimate the derivative of a function at a point by computing $[f(x+\epsilon)-f(x-\epsilon)]/(2\epsilon)$ for some small $\epsilon &gt; 0$. When the derivative is large, the step size is small, and vice versa. Your worries are justified: in order to get a bound on the distance from the function, you need to have a global bound on the derivative in the entire interval being plotted, and then you can choose the tolerance accordingly. FPLOT is therefore just an optimization, choosing a larger step size when tolerable. From the description you gave it is not clear whether the step size is doubled once or keeps getting doubled &mdash; in the first case this optimization saves you at most half the time, and in the second case you could get large errors. (The first interpretation seems more reasonable.)