tag:blogger.com,1999:blog-5824590.post6565849977356832709..comments2014-02-26T07:06:58.868-05:00Comments on Avoid Spikes: Math problem #1 - piecewise approximating functionsKnarfianhttp://www.blogger.com/profile/14149452918414200882noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-5824590.post-3008775608356515222010-03-18T23:54:49.669-04:002010-03-18T23:54:49.669-04:00I previously posted the suggestion about using the...I previously posted the suggestion about using the 2nd derivative, but realised that this would not work for functions that are changing at a constant rate. ie. y = x^2, since the 2nd derivative is constant, in this case 2. <br /><br />However, if you take the slope (ie. dy/dx) and compare that to the change in y. <br /><br />ie. <br /><br />[dydx2 - dydx1] / [y2 - y1]<br /><br />and look at the absolute value that generates, it seems to project the kind of thing that I was originally trying to suggest. <br /><br />You get higher values as the function starts to curve faster. So, using this I think you might be able to space your X values in inverse proportion to these numbers.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5824590.post-50496181764235585222010-03-18T23:31:43.545-04:002010-03-18T23:31:43.545-04:00Not sure if this helps you with your problem, but ...Not sure if this helps you with your problem, but you could try using the 2nd derivitive of the function (ie. the rate-of-change of the rate-of-change) which gives you a number that shows you how much the function is changing slope. You could perhaps use this to proportionally change the spacing of your X control points. ie. the faster the slope is changing, the closer the spacing.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5824590.post-51399246336814062562010-03-11T07:16:48.653-05:002010-03-11T07:16:48.653-05:00Thought about this some more since yesterday's...Thought about this some more since yesterday's posting:<br /><br />Let's define "best" approximation. I'm going to define it as having the least difference in the area below the function and the area below the piecewise approximation. <br /><br />Going from here: Find the derivative of the function. Evaluate the function and its derivative at a set number of equally spaced points, preferably a significant multiple of the number of break points you want to end up with.<br /><br />Wherever the derivative changes sign between values of x, set a break point. If the derivative goes from positive to negative, set the point at the higher of the two Y values, negative to positive, use the lower of the two Y values of the original function. Also set break points where the derivative passes 1.<br /><br />Now, follow me here. We want to minimize the area difference between the function and the piecewise approximation. Evaluate the difference in area between the function and the approximation between each break point. Call the segment where the difference in area is greatest n. Set a test break point at the first value of x you have after n's begining break point, and calculate the difference in areas between the function and the approximation for the segments from the n's first break point to the test point and from the test point to n's second break point. Advance the test point to the next value of x and repeat. When you have calculated this for all the x values between n's first and last break point, set a break point at the x value where the area difference was the least. Repeat this entire procedure until the desired number of break points is reached.<br /><br />How's that?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5824590.post-62657120299055778052010-03-10T12:58:26.184-05:002010-03-10T12:58:26.184-05:00The comment about using more break points where th...The comment about using more break points where the function is curvier is probably a good start- I'd begin by taking the derivative of the function and finding the Y values (slope of the original function) at regular intervals. Wherever the slope of the initial function changes from positive to negative, set a break point. Then wherever the greatest changes in slope occur, set additional break points for approximating the original function. <br /><br />Is this a clear explanation? I think this approach would work well, but then again it's been many years since I actually had to use calculus.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5824590.post-16325077975132351762010-02-11T16:36:18.910-05:002010-02-11T16:36:18.910-05:00Hi "me" - thanks for your comment and th...Hi "me" - thanks for your comment and the link. These are the kinds of methods I alluded to, which work fine (and fast) if you do not want a piecewise approximation. And it also works if you set up the piecewise approximation yourself, using breakpoints you choose. <br /><br />The last line of your first web link is telling - "If necessary, the problem should be solved piecewise, each time choosing an interval in which the solution and its derivatives are known to be continuous and sufficiently smooth (with a limited number of 'wiggles')."<br /><br />I am looking for a method or algorithm that can choose the breakpoints for a piecewise approximating function, even assuming you already know the original function.Knarfianhttp://www.blogger.com/profile/14149452918414200882noreply@blogger.comtag:blogger.com,1999:blog-5824590.post-28722210978755411282010-02-11T14:58:25.175-05:002010-02-11T14:58:25.175-05:00http://www.numericalmathematics.com/approximation_...http://www.numericalmathematics.com/approximation_of_functions.htm<br /><br />There is also some things about this in Knuths books<br />http://www-cs-faculty.stanford.edu/~knuth/taocp.html<br /><br />It has been a few years but there are some fairly simple formulas you can apply to get functions that approximate pretty closely or at the very least 'hit their marks'. The problem is when you 'go off the ends' the functions go wild.<br /><br />I for the life of me can not remember them. Even after learning the things 5 different ways in school.menoreply@blogger.com