I'm the kind of person that can get very interested in things that others might not notice. For me, his seems to occur from time to time with math problems. I'll be thinking about an engineering problem, and I will get caught up with some mathematical aspect of it. Usually, it's some problem which is easy to state but not obvious to solve. (Then again, I'm not a mathematician)
Over the years, I've gathered up a list of these problems. And now, I'd like to share some of them on this blog. I hope some of you, at least, will find them as interesting as I do.
---
Today's problem is fairly simple to state - and I thought about it for the first time many years ago. Suppose I have a continuous function y=f(x), defined on an interval from x0 to xn. I know _everything_ there is to know about the function. Now, for some reason, I need to approximate the function using a "piecewise-linear" function. This is just a set of straight lines connected together at "break" points. (You can also think of this as an approximation based on splines.)
For say, a fixed number of break points, what is the "best" way to approximate the function? (BTW - this is something that is practically done all the time, in embedded computer programs, using "table lookups" to approximate functions)
Some clues:
For a given set of breakpoints located at each x_i, you can start by picking the breakpoints at (x_i, f(x_i)). In other words, points on the curve f(x), and connecting the points with straight lines. However, you will quickly notice that the approximation is biased, based on the concavity of the curve.
A better way for a given set of points at x_i, is to solve the linear least-squares problem to find the optimal y values, which minimize the error between the approximate curve and the actual one.
But the key question seems to be - how do I locate my points in x? I see no easy way to do this, without non-linear iteration. It seems strange that it is trivial to locate the points in Y given X values, but hard to locate the X values. I can imagine some heuristic rules like "I should use more breakpoints where the function is 'curvier'". But it's not at all clear what this means :) Maybe I need to think about the meaning of "best" a bit more.
So, to summarize, we have a situation where we have a function which we know everything about, and a simple space of approximating functions, but we seem unable to match the two together, without resorting to nonlinear iteration.
If this one is too easy for you, feel free to handle extensions to this problem with higher order piecewise splines, and/or multidimensional functions. :) I can imagine practical applications for a good algorithm in this area.
Subscribe to:
Post Comments (Atom)
Fun with FPGAs - recreating the Atari TIA, Part 1
I have been playing with recreating the Atari TIA chip as used in the original 2600 in an FPGA. I know this has been done a few times alrea...
-
I have been playing with recreating the Atari TIA chip as used in the original 2600 in an FPGA. I know this has been done a few times alrea... -
Well, I found time to make a few more discoveries. The Space Raider boardset is 3 PCB's. Two of them are full size and obviously two hal...
7 comments:
http://www.numericalmathematics.com/approximation_of_functions.htm
There is also some things about this in Knuths books
http://www-cs-faculty.stanford.edu/~knuth/taocp.html
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.
I for the life of me can not remember them. Even after learning the things 5 different ways in school.
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.
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')."
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.
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.
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.
Thought about this some more since yesterday's posting:
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.
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.
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.
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.
How's that?
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.
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.
However, if you take the slope (ie. dy/dx) and compare that to the change in y.
ie.
[dydx2 - dydx1] / [y2 - y1]
and look at the absolute value that generates, it seems to project the kind of thing that I was originally trying to suggest.
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.
Thank you for sharing thiis
Post a Comment