## 3 Approximation Algorithm  
Let \(x_{j}:[0,T]\to\mathbb{R}\) be any component of the solution vector \(x\) of (1); assume that \(x_{j}\) is a Lipschitz continuous function and \(\Lambda\) is an estimate of its Lipschitz constant, i.e.,  
\[|x_{j}(t_{1})-x_{j}(t_{2})|\leq\Lambda|t_{1}-t_{2}|,\qquad\forall\ t_{1},t_{2 }\in[0,T]. \tag{16}\]  
Furthermore, let \(I\) be the integral of \(x_{j}\) over \([0,T]\) and, to begin with, assume that we only know the value of \(x_{j}\) at the two endpoints \(0,T\). We wish to construct an approximation of \(x_{j}\) in the interval \([0,T]\) and also obtain an estimate \(\hat{I}\) of the value of \(I\), together with an estimate of the error \(|I-\hat{I}|\). The Lipschitz continuity of \(x_{j}\) allow us to localize its graph by drawing four lines passing trough the points \((0,x_{j}(0))\) and \((T,x_{j}(T))\), with slopes \(\Lambda\) and \(-\Lambda\). We thus construct a parallelogram \(P_{0,T}\) containing the unknown graph of the function (see Figure 1, left). Specifically, the two upper and the two lower sides of the parallelogram (dashed lines) correspond, respectively, to an _upper bound_\(x_{j}^{u}\) and a _lower bound_\(x_{j}^{l}\) for \(x_{j}\). The functions \(x_{j}^{u}\) and \(x_{j}^{l}\) can be written as follows:  
\[x_{j}^{u}(t) = \min\{\,x_{j}(0)+\Lambda t,\,x_{j}(T)-\Lambda(t-T)\,\},\] \[x_{j}^{l}(x) = \max\{\,x_{j}(0)-\Lambda t,\,x_{j}(T)+\Lambda(t-T)\,\}.\]  
Denote now with \(\hat{x}_{j}(t)\) an approximation of the value of \(x_{j}\) at some \(t\in[0,T]\), with \(\delta(t)=|x_{j}(t)-\hat{x}_{j}(t)|\) the error on the estimate, and with \(e_{w}(t)=\max\{x_{j}^{u}(t)-\hat{x}_{j}(t),\,\hat{x}_{j}(t)-x_{j}^{l}(t)\}\) the largest possible absolute error on the estimate, whence:  
\[\delta(t)\leq e_{w}(t),\]  
Figure 1: Upper and lower bounds (dashed lines) and best approximation (solid line) of a Lipschitz continuous function evaluated at \(t=0\) and \(t=T\) (left), and same curves after the evaluation at the midpoint \(t=T/2\). where the equality sign holds when \(x_{j}\) coincides with its upper or lower bound. The case where \(\delta(t)=e_{w}(t)\) can be called the _worst case_, and the value of \(\hat{x}_{j}(t)\) that minimizes \(e_{w}(t)\) is the mean value  
\[\hat{x}_{j}(t)=\frac{x_{j}^{n}(t)+x_{j}^{l}(t)}{2}, \tag{17}\]  
which yields  
\[e_{w}(t)=\frac{x_{j}^{n}(t)-x_{j}^{l}(t)}{2}. \tag{18}\]  
The graph of \(\hat{x}_{j}(t)\), in the worst case, is represented by the solid line in Figure 1, on the left. In order to obtain a global measure of the error in the interval \([0,T]\), in the worst case, it is then natural to define:  
\[E_{w}(0,T)=\int_{0}^{T}e_{w}(t)\,dt=\int_{0}^{T}\frac{x_{j}^{n}(t)-x_{j}^{l}(t )}{2}\,dt, \tag{19}\]  
which is equal to the half of the area of \(P_{0,T}\), denoted by \(A(0,T)\), and thus \(E_{w}(0,T)=A(0,T)/2\). We thus have an approximation \(\hat{x}_{j}\) of the function \(x_{j}\), together with the estimates \(e_{w}\) and \(E_{w}\) of the _worst case_ local and total error, respectively. The average worst case error is defined as \(E_{w}(0,T)/T\). We want now to approximate the integral \(I\) of \(x_{j}\) over \([0,T]\). Notice that lower and upper bounds for \(I\) are given, respectively, by  
\[I^{l} =\int_{0}^{T}x_{j}^{l}(t)\,dt=\frac{(x_{j}(0)-x_{j}(T))^{2}}{4 \Lambda}-\frac{\Lambda}{4}T^{2}+\frac{T(x_{j}(0)+x_{j}(T))}{2},\] \[I^{u} =\int_{0}^{T}x_{j}^{u}(t)\,dt=-\frac{(x_{j}(0)-x_{j}(T))^{2}}{4 \Lambda}+\frac{\Lambda}{4}T^{2}+\frac{T(x_{j}(0)+x_{j}(T))}{2}.\]  
The estimate of \(I\) that differs the less from the two extreme \(I^{l}\) and \(I^{u}\) is the average value  
\[x_{j}^{u}(t) = \min\{\,x_{j}(0)+\Lambda t,\,x_{j}(T)-\Lambda(t-T)\,\},\]0  
For this choice of \(\hat{I}\), the error \(|I-\hat{I}|\) can reach the value of \(E_{I}=(I^{u}-I^{l})/2\) in the worst case. It follows from (17) that \(\hat{I}\) is equal to the integral of the approximating function \(\hat{x}_{j}\). We remark from (19) that the total worst case error \(E_{w}\) coincides with the estimate of the error \(E_{I}\) on the integral \(\hat{I}\).