I am currently trying to linearise a convex function at hand (an M/M/1 curve) using piecewise linear functions. Since I wanted the approximation error to be as low as possible, I searched for some algorithms that do it and found the 'Recursive descent algorithm' by Imamoto to be the most suited one. The algorithm intends to find a minimax solution of PWL approximation.
However, I've run into some trouble implementing the algorithm. I don't understand a particular block of the algorithm which says
$\epsilon = 0.5 * max/min |^{N-1}_{i=0} \epsilon_{i,j}$
I'm really sorry for asking such a trivial question, but I don't know how to implement this particular block in my code. Could you please help me out?
The link to the paper is here.
Thank you all
This is just asking for the worst case error, keeping its sign: from the set $\{\varepsilon_{i,J} : 0 \leq i \leq N-1\}$, find the one with the maximum modulus, divide it by $2$, and set $\varepsilon$ equal to that. The $\dfrac{1}{2}$ is to transform the $g_i$ we have (as in figure 2) to the $g_i$ we want (as in figure 1). (If we remove half the endpoint error from the entire linear piece, the tangent point error increases to match the decreased endpoint error.)