Math problem #1 - piecewise approximating functions

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.