Cheap and Secure Web Hosting Provider : See Now

Error estimates of piecewise-linear curve approximations

, , No Comments
Problem Detail: 

In order to plot a curve a set of points is usually calculated based on some formula. The function FPLOT in MATLAB also supports plotting with some error tolerance. Its help says the following about this functionality:

The FPLOT function begins with a minimum step of size (XMAX-XMIN)*TOL. The step size is subsequently doubled whenever the relative error between the linearly predicted value and the actual function value is less than TOL. 

So, if I plot a curve based on some expression and with some predefined tolerance TOL, is the error of the line segment approximation between any two calculated points always lower than TOL? Unfortunately, this is not obvious for me.

If not, how could one achieve a guaranteed (small) error of a piecewise-linear curve approximation (compared with the "exact" curve).

Asked By : Omicron_Persei_11
Answered By : Yuval Filmus

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/21376

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback