## 3 Approximation Algorithm
Hence, both for the estimate of the function and of its integral, the quantity that measures the corresponding errors is the same, and it is exactly half the area of the parallelogram \(P_{0,T}\). It is easy to check (see [13; 14]) that, for any pair of points \(t_{1},t_{2}\) (with \(t_{1}<t_{2}\)), the area of parallelogram \(P_{t_{1},t_{2}}\) is  
\[x_{j}^{u}(t) = \min\{\,x_{j}(0)+\Lambda t,\,x_{j}(T)-\Lambda(t-T)\,\},\]1  
Now, we want to analyze how the evaluation of \(x_{j}\) in a further point improves the approximation procedure. For this, let \(t_{1}=0\), \(t_{2}=T\), let \(t_{3}\) be an arbitrary point in \((0,T)\) and repeat the previous procedure in the intervals \([0,t_{3}]\) and \([t_{3},T]\), respectively. The graph of \(x_{j}\) is now contained in the union of parallelograms \(P_{0,t_{3}}\) and \(P_{t_{3},T}\). Therefore, a new sample point allows to better locate the graph of \(x_{j}\). In this case, the bounding functions are computed as follows:  
\[x_{j}^{u}(t)= \begin{cases}\min\{x_{j}(0)+\Lambda^{\prime}t,\ x_{j}(t_{3})- \Lambda^{\prime}(t-t_{3})\}&\text{ if }t\in[0,t_{3}],\\ \min\{x_{j}(t_{3})+\Lambda^{\prime\prime}(t-t_{3}),\ x_{j}(T)-\Lambda^{\prime \prime}(t-T)\}&\text{ if }t\in[t_{3},T],\end{cases} \]\[x_{j}^{l}(t)= \begin{cases}\max\{x_{j}(0)-\Lambda^{\prime}t,\ x_{j}(t_{3})+\Lambda^ {\prime}(t-t_{3})\}&\text{ if }t\in[0,t_{3}],\\ \max\{x_{j}(t_{3})-\Lambda^{\prime\prime}(t-t_{3}),\ x_{j}(T)+\Lambda^{\prime \prime}(t-T)\}&\text{ if }t\in[t_{3},T],\end{cases} \]  
where \(\Lambda^{\prime}\) and \(\Lambda^{\prime\prime}\) denote the update estimates of the Lipschitz constant of \(x_{j}\) in the intervals \([0,t_{3}]\) and \([t_{3},T]\), respectively. For the two sub-intervals, we can provide approximations of \(x_{j}\) and of its integral, and estimates of the corresponding errors \(E_{w}(t_{1},t_{3})\) and \(E_{w}(t_{3},t_{2})\). We observe that the smaller the sum of the areas of the new parallelograms is, the better the new estimate of the function is. Hence, with the evaluation of \(x_{j}\) at new points and repeating the above procedure, we can further improve the approximation \(x_{j}\) and its integral, as specified by the following algorithm. **Step 0. (Initialization)**: Fix a positive constant \(\varepsilon_{tot}\), which represents the desired maximum error on the integral of \(x_{j}\) (or total worst case error in the estimate of \(x_{j}\) itself). Create a list of evaluation points, which initially contains the two endpoints \(0\) and \(T\), and the corresponding list of function values \(x_{j}(0),x_{j}(T)\). Calculate the area \(A(0,T)\) of parallelogram \(P_{0,T}\) by means of (20) and initialize a list of parallelograms' areas. **Step 1. (New evaluation)**: Locate the parallelogram having the largest area, and the corresponding interval, say \([t_{1},t_{2}]\) (at the first step, \([t_{1},t_{2}]\) coincides with the whole interval \([0,T]\)). Add the new evaluation point \(p=(t_{1}+t_{2})/2\), and update the lists of points and function values accordingly. Compute the two Lipschitz constants in the intervals \([t_{1},p]\) and \([p,t_{2}]\). Update the parallelograms' areas list by removing the area of parallelogram \(P_{t_{1},t_{2}}\) and inserting the areas of the two new parallelograms \(P_{t_{1},p}\) and \(P_{p,t_{2}}\). **Step 2. (Stopping rule)**: Compute the worst case error \(E_{tot}\) over the interval \([0,T]\): \[E_{tot}=\text{ (sum of the areas of all parallelograms) }/2.\] If \(E_{tot}\leq\varepsilon_{tot}\), then stop the procedure, otherwise go to Step 1. At the \(k\)-th iteration of the algorithm, we thus have divided the interval \([0,T]\) with \(k+2\) points, which we reorder as \(\{t_{1}=0,t_{2},\ldots,t_{k+1},t_{k+2}=T\}\), and we denote with \(\Lambda_{i}\) the estimate of the Lipschitz constant of \(x_{j}\) in \([t_{i},t_{i+1}]\).