An algorithm for piecewise linear approximations

ABSTRACT

An algorithm is described for approximating a function F(x) on a finite interval [a,b] whose second derivative is of constant sign on (a,b) by a continuous piecewise linear function, with any desired accuracy. Given a positive number ε, the algorithm finds a continuous piecewise linear functionL(x) = mi x + bi, xi-l ≤ × ≤ xi,i = 1,2 ...,nwhere a = xo < xl < ... < xn = b, such thatmax {|L(x) - F(x)|: xi-l ≤ x ≤ xi} ≈ = εfor i = 1,2,...,n-l, and|L(x) - F(x)| ≤ εfor xn-l ≤ × ≤ xn. In contrast to a method described by Phillips (1968), the derivative of F(x) is not used in the calculation of L(x). A computer implementation of the algorithm is discussed and an example of its use is provided.

REFERENCES

• 1: G. M. Phillips, Algorithms for piecewise straight line approximations, The Computer Journal 11 (1968), 211-212.