Piecewise linear approximation of fuzzy numbers: algorithms, arithmetic operations and stability of characteristics

In what follows, we propose some convergence results for sequences of piecewise approximations. However, firstly, for given fuzzy number A, \( n\in {\mathbb {N}}\), and \({\varvec{\alpha }}_{n}=(\alpha _{n,0},\alpha _{n,1},\ldots ,\alpha _{n,n+1})\in {\mathfrak {A}}_{n}\), let us consider a fuzzy number \(N_{{\varvec{\alpha }}_{n}}^{n}(A)\in {\mathbb {F}}^{\pi _{n}( {\varvec{\alpha }})}(\mathbb {R)}\) defined byfor \(i=0,\dots ,n\) and \(\beta \in [\alpha _{i},\alpha _{i+1}]\). This is the so-called naïve approximator of A, i.e., an n-knot piecewise linear fuzzy number that interpolates both \(A_{L}\) and \(A_{U}\) at the knots (it minimizes the \(L_2\) metric exactly at finite number of points, while the approximator suggested in this paper minimizes the metric “globally” , i.e., at all alpha cuts). This operator was also proposed in Báez-Sánchez et al. (2012) where it was used as an approximator with respect to the Hausdorff metric. We will use this operator to obtain approximation results for the sequence \(\left( \Pi _{{\varvec{\alpha }}_{n}}^{n}\right) _{n\ge 1}\) with respect to the Euclidean metric. Please note that the convergence results can be deduced from Báez-Sánchez et al. (2012) using some simple inequalities between the Hausdorff and Euclidean metrics. However, we will use a direct approach which will give us precise estimations for the error of approximation. Clearly, \(N_{{\varvec{\alpha }}}^{n}(A)\) preserves the support and core of A. Since \(N_{{\varvec{\alpha }}_{n}}^{n}(A)\in {\mathbb {F}}^{\pi _{n}( {\varvec{\alpha }})}(\mathbb {R)}\) for any \(n\in {\mathbb {N}}\), let us find an estimation for \(d(N_{{\varvec{\alpha }}_{n}}^{n}(A),A)\) for some \(n\ge 1\). Let us choose arbitrary \(\beta \in [0,1]\). Then there exists \( i\in \{0,\dots ,n\}\) such that \(\beta \in [\alpha _{n,i},\alpha _{n,i+1}]\). If \(\left( N_{{\varvec{\alpha }}_{n}}^{n}(A)\right) _{L}(\beta )\ge A_{L}(\beta )\) thenOn the other hand, if \(\left( N_{{\varvec{\alpha }}_{n}}^{n}(A)\right) _{L}(\beta )<A_{L}(\beta )\) thenand therefore from the two inequalities we getBy similar reasonings, we obtainThis implies that in general, for \(\beta \in [0,1]\), we have

Recall that if \((X,d_{1})\) and \((Y,d_{2})\) are metric spaces then a function \(f:X\rightarrow Y\) is called lipschitzian, if there exists a real positive constant C such thatfor all \(x^{\prime },x^{\prime \prime }\in X\). It is well known that Lipschitz functions are continuous (thus, the property (iv) in Theorem 3 also implies the operator’s continuity).

From the above theorem, we easily get some important propositions for the case of equidistant knots.

Thus, we may conclude that in case of the fuzzy number approximation using equidistant knots the convergence rate is at most linear.

Another important consequence of Theorem 4 is the convergence with respect to some important characteristics of a fuzzy number such as its value, ambiguity, expected interval or expected value. Let us recall briefly their definitions.

The value of a fuzzy number A with respect to a nondecreasing function \(c:[0,1]\rightarrow [0,1]\), called reducing function, where usually \(c(0)=0\) and \(c(1)=1\), isand might be seen as a typical value of the magnitude represented by the fuzzy number A. The next index, called the ambiguity, is given byand characterizes the vagueness of A. These two characteristics were proposed for the first time by Delgado et al. (1988) to simplify the representation of fuzzy numbers.

The expected interval of a fuzzy number A is given by (see Dubois and Prade 1987)while the expected value of A is just the middle of its expected interval, i.e.,It is worth noting that the invariance of the above-mentioned characteristics applies a key role in the fuzzy number approximation (see Grzegorzewski and Mrówka 2005). Hence, the following result is of interest.

Fix \({\varvec{\alpha }}\). To perform the calculations, we should derive formulas for the elements \(\phi _{i,j}=\left\langle {\mathbf {e}}_{i},{\mathbf {e}} _{j}\right\rangle \), \(i,j=1,\dots ,2n+4\), of the Gram matrix \( \Phi =[\phi _{i,j}] \). It might be seen that we have:The \(\Phi \) matrix is, of course, symmetric and—as already stated—invertible. Note that the elements above the diagonal do not depend on the row index i.

Fix A. Let \({\mathbf {w}}=(w_1,\dots ,w_{2n+3})\), \(\mathbf {w^{\prime }} =(w^{\prime }_0,\dots ,w^{\prime }_{2n+3})\) be such that:It may be shown easily that \({\mathbf {b}}=(b_1,\dots ,b_{2n+4})\) such that \( b_{i}=\left\langle A,{\mathbf {e}}_{i}\right\rangle \), is determined by \(b_{1} := \sum _{i=1}^{2n+3} w_i\) and \(b_{i} := b_{i-1} - w_{i-2}^{\prime }- w_{i-1} + w_{i-1}^{\prime }\) for \(i=2,\dots ,2n+4\).

Moreover, if \(A\ge 0\) (i.e., if \(\inf \mathrm {supp}\,A\ge 0\)), then \(w_i\ge w_i^{\prime }\) and it follows \(b_1\ge b_2\ge \dots \ge b_{2n+4}\ge 0\). Note that \({\mathbf {b}}\) contains the whole information about A needed to solve our approximation problem. Moreover, it may be seen that for \(n=1\) the above derivations for \(\Phi \) and \({\mathbf {b}}\) are equivalent to those presented in our previous paper (Coroianu et al. 2013), and for \(n=0\) with those obtained by Ban (2009a).

Please note that if the solution to the system of \(2n+4\) linear equations \( \Phi \,{\breve{{\varvec{\delta }}}}{}^T={\mathbf {b}}^T\) is such that \(\breve{ \delta }_2,\dots ,\breve{\delta }_{2n+4}\ge 0\), then the problem of determining the nearest piecewise linear approximation is immediate: we have \( {\varvec{\delta }}^*=\breve{{\varvec{\delta }}}\).

However, if \(\breve{\delta }_{i}<0\) for some \(i>1\), then we have to find the index set \(K^{*}\subseteq \{2,\dots ,2n+4\}\) corresponding to the optimal solution. Intuitively, this set indicates between which knots (left or right) \(\alpha \)-cut bounds are constant functions. Generally, there are \( 2^{2n+3}\) possible selections of the index sets and we know that at least one of them (as situation with \(\delta _{k}^{*}=z_{k}^{*}=0\) is possible) leads to the solution fulfilling conditions from Theorem 2). Thus, although theoretically correct, in practice we cannot look for each possible K and check whether it gives the desired result. Below we postulate an algorithm that finds the solution in up to \(2n+4\) steps.

First, please note that if \(\mathrm {S}_d({\varvec{\alpha }},\breve{ {\varvec{\delta }}})\not \in {\mathbb {F}}^{\pi _n({\varvec{\alpha }})}({\mathbb {R}})\) then, by definition, we have \(\langle A, {\mathbf {e}}_i\rangle = \langle \mathrm {S}_d({\varvec{\alpha }},\breve{{\varvec{\delta }}}), {\mathbf {e}}_i\rangle = b_i\) for all i. Thus, finding the best linear approximation of A is the same as approximating the object \(\mathrm {S}_d({\varvec{\alpha }} ,\breve{{\varvec{\delta }}})\) (corresponding to a pair of two square integrable piecewise linear functions).

Please note that it may be tempting to assume that as \(n\rightarrow \infty \), then for all \({\varvec{\alpha }}_i\in {\mathfrak {A}}_i\) such that \({\varvec{\alpha }}_i\subset {\varvec{\alpha }}_{i+1}\) we necessarily approach the solution with \(z^*_{j,n}=0\) for all j. This is, unfortunately, not true, as a counterexample may easily be constructed (see Example 3).

It may be noted that if the conditions in Theorem 2 hold for a given index set \(K^*\), then \({\mathbf {z}}^*\) and \({\varvec{\delta }}^*\) may be obtained by solving the following system of \(2n+4\) linear equations for \( {\mathbf {x}}\):where \({\mathbf {1}}_p=1\) if p is true and 0 if p is false. This is done by setting \(\delta _i^* = x_i\,{\mathbf {1}}_{i\not \in K^*}\) and \(z_i^* = x_i\, {\mathbf {1}}_{i\in K^*}\). The above system of equations may be written aswhere the i-th column of \(\Phi ^{(K^*)}\) is exactly the same as in \(\Phi \) if \(i\not \in K^*\) and set to \((0,\dots ,0,\phi _{i,i}^{(K^*)}=-1,0,\dots ,0)^T\) otherwise. Moreover, \(\Phi ^{(K^*)}\) is always invertible.

The algorithm that finds the solution to the approximation problem of our interest is of “greedy” type. It relies on adding in each step to a temporary K set such index \(i>1\) at which an intermediate solution \(x_i\) has the smallest negative value.

Heuristic Algorithm for determining best piecewise linear approximation of A given n and \({\varvec{\alpha }}\) (cf. Coroianu et al. (2013):Note that \(\mathrm {S}_d({\varvec{\alpha }},{\varvec{\delta }}^*) =\mathrm {S}({\varvec{\alpha }}, \mathtt {cumsum}({\varvec{\delta }}^*))\), where \(\mathtt {cumsum}({\varvec{\delta }}^*) = (\delta _1^*,\delta _1^*+\delta _2^*,\dots , \delta _1^*+\delta _2^*+\dots +\delta _{2n+4}^*)\). Moreover, an example may be constructed easily for which at some step \(m < 0\), \(m > \arg \min _{i=2,3,\dots ,2n+4}\{ x_i \}\) and \(m\not \in K^*\).

Suppose we have a set of fuzzy numbers \(\{A_1,\ldots ,A_k\}\) and we would like to compute a series of operations on them, obtaining \( B=f(A_1,\ldots ,A_k)\). Let each operation be defined using the extension principle and rely on a proper transformations of their \(\alpha \) -cuts.

Most often such a task is performed numerically and not symbolically. Thus, the side functions of the fuzzy numbers must be discretized at a fixed, possibly large number of \(\alpha \)-cuts (see, e.g., Hanss 2005). Such a process involves nothing else than taking a naïve approximation of \(A_i\) , \(i=1,\dots ,k\). Here, the values of membership functions at given \(\alpha \) -cuts (e.g., equidistant ones) are exact (of course, up to numeric error involved in calculating the operations). Of course, the larger the number of knots, the lower the computation speed but higher the accuracy.

In practice, we are interested in finding a trade-off between these two factors. An important question is whether, for fixed n and \({\varvec{\alpha }}\in {\mathfrak {A}}_n\), by considering the nearest-Euclidean approximation we will obtain results of higher quality than in case of a naïve approximation.

Let \(N=N_{{\varvec{\alpha }}}^n(f(N_{{\varvec{\alpha }}}^n(A_1),\dots ,N_{{\varvec{\alpha }}}^n(A_k)))\) and \(\Pi = \Pi _{{\varvec{\alpha }}}^n(f(\Pi _{{\varvec{\alpha }}}^n(A_1),\dots ,\Pi _{{\varvec{\alpha }}}^n(A_k)))\) denote piecewise linear n-knot fuzzy numbers determined by taking, respectively, the naïve and nearest-Euclidean approximations of the input fuzzy numbers and then applying f only at given \({\varvec{\alpha }}\)-cuts. Moreover, let \(\Pi \text {-post}=\Pi _{{\varvec{\alpha }}}^n(B)\) denote the nearest-Euclidean piecewise linear approximation of the exact result, B. To verify this, let us perform a series of numerical experiments. First of all, one should be interested in:To investigate these two issues, we performed a large number of computer simulations involving the following randomly generated types of fuzzy numbers:Supports \([a_1,a_4]\) and cores \([a_2,a_3]\) were also generated by \((a_1,a_2,a_3,a_4):=\mathrm {sort}(a_1^{\prime },a_2^{\prime },a_3^{\prime },a_4^{\prime })\), with \(a_1^{\prime },a_2^{\prime },\)\(a_3^{\prime },a_4^{\prime }\) following the uniform distribution.

As all the considered scenarios exhibited the same patterns, below we will only present results for the scenario with \(f(A_1,\dots ,A_9)=(A_1+A_2)A_3-A_4(A_5-A_6)\log (A_7)+\exp (A_8)/2^{A_9}\), with \(M=1000\) Monte Carlo iterations, and \(n=3\) equidistant knots. Figure 3 depicts the boxplots of \(d(B, \Pi )\), d(B, N) and \(d(B,\Pi \text {-post})\), as well as \(d(\Pi , \Pi \text {-post})\). It is worth noting that \(d(B,\Pi )<d(B,N)\) in each case. In other words, applying computations on nearest-Euclidean approximated inputs leads to smaller errors (as measured by the Euclidean distance) than for the naïve approximations. Figure 4 depicts the difference between an exemplary exact output and ones that are computed using two types of piecewise linear approximations.

Next, Fig. 5 presents scatter plots for each pair of observations from \(\{d(B, \Pi ), d(B, N), d(B, \Pi \text {-post})\}\). Interestingly, we observe high linear association between the errors (Pearson’s \(r>0.99\)). Applying linear regression, we get the following relationships for \(n=3\):which are quite nicely fitted (\(R^2>0.99\)). Moreover, for \(n=10\) equidistant knots we haveWe see that the error induced by the nearest-Euclidean approximation is more than 2–3 times smaller than that accompanying the naïve approximation.

Moreover, in Table 1 we list basic summary statistics of the \(L_2\) error measure between the exact solution and ones obtained by means on acting on approximated fuzzy numbers. We see that with a large number of knots we get much more precise results and that the best \(L_2\) approximator is far better than the naïve one.

We might be also interested whether the nearest-Euclidean approximation preserves better some important characteristics of the concerned fuzzy numbers. Of course, the support and core of B and N are the same. To measure the error for \(\Pi \) and \(\Pi \text {-post}\), we will use the Moore’s interval metric Moore (1962), given by \(d_M([a,b],[c,d])=\max \{|a-c|,|b-d|\}\).

Table 2 shows some basic summary statistics for those measures of interest. We observe again the almost perfect correlation (\(r>0.999\)) between \(d_M(\mathrm {supp}\,B\), \(\mathrm {supp}\,\Pi )\) and \(d_M(\mathrm {supp}\,B,\mathrm {supp}\,\Pi \text {-post})\) as well as between \(d_M(\mathrm {core}\,B,\mathrm {core}\,\Pi )\) and \(d_M(\mathrm {core}\,B,\mathrm {core}\,\Pi \text {-post})\). IndeedThe above-mentioned results are very interesting especially that the stability of the support and core is very important in fuzzy number approximation (for more details we refer the reader to Coroianu et al. 2014a).

Lastly, let us investigate the difference between B’s ambiguity, width, expected value, or value and the corresponding characteristics of \(\Pi , N\), and \(\Pi \text {-post}\). The relevant boxplots are depicted in Figs. 6 and 7. We see that the nearest-Euclidean approximation preserves these fuzzy numbers characteristics much better than the naïve approximation. Although these characteristics are not ideally preserved, they are reconstructed quite accurately.