StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The key here is to realize that you can bound the error on your linear interpolation in terms of the second derivative of the function. I.e. if we approximate <code>f(x) \approx f(x_0) + f'(x_0)*(x-x_0)</code>, then the error in this approximation is less than <code>abs[ 0.5*f''(x_0)(x-x_0)^2 ]</code>. </p> <p>The outline of an iterative approach could look like this:</p> <ol> <li>Construct an initial, e.g. uniformly spaced, grid</li> <li>Compute the second derivative of the function on this grid.</li> <li>Compute the bound on the error using the second-derivative and the inter-sample spacing</li> <li>Move the samples closer together where the error is large; move them further apart where the error is small.</li> </ol> <p>I'd expect this to be an iterative solution that loops on steps 2,3,4.</p> <p>Most of the details are in step 4. For a fixed number of sample points one could use the median of the error bounds to select where finer/coarser sampling is required (i.e. those locations where the error is larger than the median error will have the sample points pulled closer together). </p> <p>Let <code>E_0</code> be this median of the error bounds; then we can, for each sample in the point, compute a new desired sample spacing <code>(dx')^2=2*E_0/f''(x)</code>; then you'd need some logic to go through and change the grid spacing so that it is closer to these ideal spacings.</p> <p>My answer is influenced by having used the "Self-Organizing Map" algorithm on data; this or related algorithms may be relevant for your problem. However, I can't recall ever seeing a problem like yours where the goal is to make your estimates of the error uniform across the grid.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload