1

Suppose that we have a nonlinear $f(x)$ which may be convex/nonconvex. We want to linearize this function in $N$ points over an arbitrary interval $[a,b]$ in such a way that the resultant $N$ linear approximations gives the least deviation from the original function $f(x)$. Then we can say this set of lines provides the best approximation of $f(x)$ over $[a,b]$. Is this a standard problem which has been already investigated? If no, what is the cheapest way to model this problem?

Behnam Alizadeh
  • 11
  • 1
    Can you clarify what you mean by "to linearize this function in $N$ points in an arbitrary interval $[a,b]$"? Do you mean construct a piecewise linear, continuous function that agrees with $f$ at $N$ points in the interval? So the graph is a polygonal path (series of connected line segments)? – Sammy Black Feb 19 '21 at 08:54
  • 2
    Just to check if I understand this correctly... You presumably want $N-1$ internal points which would (together with $a$ and $b$) provide $N$ intervals, and then - do you want just $N$ separate linear functions on those intervals, or do you want one, piecewise linear function? (In other words: do the linear functions have to match when they meet at the internal $N-1$ points?) Finally, I guess the "least deviation" means in the sense of integral of the squared difference, is that correct? –  Feb 19 '21 at 08:55
  • @ Sammy: generally we are going to use the tangent line at each of these N points as the approximation. This line will be used till the intersection with the next line. The question is where to place these N points? – Behnam Alizadeh Feb 19 '21 at 09:06
  • @ Stinking Bishop: I want N distinct tangent line from f(x). But which N points? You mentioned a correct guide "the integral of the squared difference" but is not there a less computational method? – Behnam Alizadeh Feb 19 '21 at 09:10
  • I don't think using tangent lines instead of chords is a good idea. – Jean Marie Feb 19 '21 at 10:00
  • Thanks Jean, would you please introduce me a reference in which these two methods are compared? – Behnam Alizadeh Feb 19 '21 at 10:15

1 Answers1

0

If you place the points on the curve, and make a polyline by connecting these points, then you are doing approximation by a spline of degree 1. Spline approximations (of all degrees) are well understood. See for example deBoor’s book “A Practical Guide to Splines”. The error depends on the maximum value of the second derivative of the original function.

More generally, approximation by polylines has been studied extensively, and you’ll find lots of references by googling that term. However, I don’t recall ever seeing the tangent line technique that you suggested.

bubba
  • 43,483
  • 3
  • 61
  • 122
  • Thanks bubba, you have turned my mind to a different direction. The tangent line approximation is nothing but Taylor series. You just keep the first order derivative in the series and neglect the higher orders. Now the question is which one is more accurate: spline approximation of degree 1 or tangent line approximation? Both with $N$ points. – Behnam Alizadeh Feb 19 '21 at 10:08
  • Try both approaches on a quarter circle with three points. You’ll see that the spline approach is more accurate. But you can do even better by moving the middle point a short distance outside the circle. – bubba Feb 19 '21 at 23:31