An edge determination algorithm for exact computation of the frequency response of linear interval systems

Abstract

A novel algorithm, called the edge determination algorithm, for exact computation of the frequency response of a linear interval system is proposed. The algorithm formulates candidate curves for the frequency response boundaries as cubic Bezier curves. The edge determination algorithm operates on the cubic Bezier control points of these curves to obtain those, or their parts, that are on the frequency response boundaries. It presents the frequency response boundaries as an array whose entries are the cubic Bezier control points of the curves on the boundaries. Examples for two different cases are presented to illustrate the mechanics and validity of the algorithm.

Keywords

Frequency response linear interval systems cubic Bezier curve formulation

1 Introduction

Consider the transfer function

G (s, a, b) \overset{Δ}{=} \frac{N (s, a)}{D (s, b)} \overset{Δ}{=} \frac{a_{m} s^{m} + a_{m - 1} s^{m - 1} + \dots + a_{1} s + a_{0}}{b_{n} s^{n} + b_{n - 1} s^{n - 1} + \dots + b_{1} s + b_{0}}

(1)

where the coefficients of N and D belong to specified intervals such that $a_{i} \in [a_{i}^{-}, a_{i}^{+}],$ $i = 0, 1, \dots, m,$ $b_{j} \in [b_{j}^{-}, b_{j}^{+}],$ $j = 0, 1, …, n .$ The vectors $a$ and $b$ denote the numerator and denominator coefficients $(a_{0}, a_{1}, \dots, a_{m})$ and $(b_{0}, b_{1}, \dots, b_{n})$ respectively. Systems modeled by (1) are called interval systems. Under the assumption of properness (i.e. $m \leq n$ ) and stability (i.e. all the roots of its denominator lie strictly in the left half complex plane) conditions, $G (i w_{0}, a, b)$ , with $w_{0}$ a positive real number, is called the frequency response of (1). In a linear systems context it corresponds to the set of possible steady-state gains and phase shifts of (1) when subjected to a sinusoidal input at the frequency $w_{0}$ (Ogata, 2010). The frequency response computation is one of the major tools in the stability analysis of linear time invariant (LTI) systems. Noting that the uncertain systems with coefficients in specified intervals have Nyquist plots in the envelope form, to form the Nyquist plot for such systems, the frequency response of the system at each frequency of this envelope is needed. For the uncertain LTI systems, the stability test by encircling the point $- 1 + i 0$ on the complex plane is carried out using the envelope of the relevant transfer function (Bartlett et al., 1988). Various extensions of stability tests using frequency response methods are presented in Bhattacharyya et al. (1995). Here $G (i w_{0}, a, b)$ is a set of complex numbers which occupy a simply connected region in the complex plane. In this study we present a computationally efficient edge determination (ED) algorithm to represent the frequency response by the boundaries of the region it occupies. Given the transfer function (1) and the positive frequency $w_{0}$ , it is well known that the algorithm generates 16 line segments and 16 arcs which are candidates for representing the boundaries of the frequency response (Fu, 1989; Karamancıoğlu and Dzhafarov, 1998). In this article, the ED algorithm formulates these line segments and arcs as cubic Bezier curves, and in a finite number of steps, it keeps only those, or their parts, that are on the boundaries. In the algorithm it will be shown that each control point in every cubic Bezier curve has an important function, so that the cubic Bezier curve representation is the best-fitting formulation for the candidate lines.

It is well known that the frequency responses of $N (s, a))$ and $D (s, b))$ are independent rectangles with corner points corresponding to their certain extreme points (Minnichelli et al., 1989). For instance, at $s = i w_{0}$ , the rectangle $R_{N}$ corresponding to $N (s)$ is

R_{N} = {x + iy : N_{1} \leq x \leq N_{2}; N_{3} \leq y \leq N_{4}}

(2)

where

\begin{matrix} N_{1} = a_{0}^{-} - a_{2}^{+} {(w_{0})}^{2} + a_{4}^{-} {(w_{0})}^{4} \dots \\ N_{2} = a_{0}^{+} - a_{2}^{-} {(w_{0})}^{2} + a_{4}^{+} {(w_{0})}^{4} \dots \\ N_{3} = a_{1}^{-} w - a_{3}^{+} {(w_{0})}^{3} + a_{5}^{-} {(w_{0})}^{5} \dots \\ N_{4} = a_{1}^{+} w - a_{3}^{-} {(w_{0})}^{3} + a_{5}^{+} {(w_{0})}^{5} \dots \end{matrix}}

Calculating the extreme points as in (2), rectangles $R_{N}$ and $R_{D}$ corresponding to $N (i w_{0}, a)$ and $D (i w_{0}, b)$ can be formed. This leads to a formulation of the frequency response $G (i w_{0}, a, b)$ as

G (i w_{0}, a, b) = {\frac{z_{1}}{z_{2}} : z_{1} \in R_{N}, z_{2} \in R_{D}}

(3)

The rectangular regions $N (i w_{0}, a))$ and $D (i w_{0}, b))$ have extensively been used in the literature for an efficient computation of $G (i w_{0}, a, b)$ . In Bailey et al. (1988), a phase angle sweeping technique was applied to these rectangles for computation of the frequency response boundaries. Literature on this problem contains several examples of research using the fact that the computational work for the frequency response boundaries of (1) involves only the edges of the rectangles $R_{N}$ and $R_{D}$ as given below (Chen and Hwang, 1998; Fu, 1989; Karamancıoğlu and Dzhafarov, 1998)

\partial G (i w_{0}, a, b) \subset {\frac{z_{1}}{z_{2}} : z_{1} \in \partial R_{N}, z_{2} \in \partial R_{D}}

(4)

$where \partial$ denotes boundary of. It has also been shown that boundaries of the frequency response are concatenation of arcs and segments. In Fu (1989) the expression (4) is evaluated for the case when at least one of the terms in the quotient is a vertex point. In Karamancıoğlu and Dzhafarov (1998) these arcs and segments have been analyzed and a sectoring algorithm has been proposed to determine the arcs and segments lying on the frequency response boundaries. For this purpose, sectors created on the complex plane are searched for patterns that lead to elimination of interior arcs and segments. The present manuscript represents all of the arcs and segments in cubic Bezier form throughout the computations, so that the operations on them, including their clippings, sortings, and choosing those on the boundaries, are performed by using their cubic Bezier curve control parameters. For obtaining the arcs and segments on the boundaries, a modified Cohen–Sutherland and pivoting algorithms have been used in Chen and Hwang (1998). In this work, to find the boundary of $G (i w_{0}, a, b)$ by a pivoting procedure, the complex plane is divided into adjacent triangles and vertices of the triangles are assigned integers 0 or 1 depending on whether the intersection of $N (i w_{0}, a))$ and $v_{i} \times D (i w_{0}, b))$ is empty or not, where $v_{i}, i = 1, 2, 3,$ are complex numbers corresponding to the vertices of the triangle under consideration. In another research, in forming the overall frequency response of a transfer function, Gutman et al. (1994) utilized its frequency response templates of the elementary functions. This approach has allowed handling of the non-polynomial terms in the transfer function, such as exponential factors. A novel template generation algorithm for systems with affinely dependent parameters is presented in a recent work in which the principal points of the edges of the parameter box are defined (Yang, 2009). It is shown in some sufficiency theorems that considering only the principal points in forming the template boundaries results in a significant efficiency in computations. The same author in a subsequent paper presented an entirely different algorithm for the template boundary computation (Yang, 2010). In the proposed algorithm, template points are tested by using two inequalities, and the points passing these tests are used in an efficient pivoting procedure to form the template boundaries.

Evaluating (3) by a straightforward gridding approach obviously results a computational burden. Even though the expression (4) significantly reduces the burden, it still contains redundancies which are not part of the frequency response boundaries. As presented below, a further simplification reduces the right-hand side of (4) to 16 line segments and 16 arcs. Note that, evaluation of the right-hand side of (4) involves division of sides of $R_{N}$ into those of $R_{D}$ , that is, division of line segments into line segments. Let $L_{Ni}$ and $L_{Dj}$ denote ith side of the numerator rectangle and jth side of the denominator rectangle, respectively. For any $i, j \in {1, 2, 3, 4}$ , division of ith side of the numerator rectangle into jth side of the denominator rectangle generates an area whose boundaries are (Karamancıoğlu and Dzhafarov, 1998)

\partial (\frac{L_{Ni}}{L_{Dj}}) = \frac{L_{Ni}^{-}}{L_{Dj}} \cup \frac{L_{Ni}^{+}}{L_{Dj}} \cup \frac{L_{Ni}}{L_{Dj}^{-}} \cup \frac{L_{Ni}}{L_{Dj}^{+}}

(5)

where superscripts + and − denote endpoints of the line segments. It can be shown that the lines forming the boundaries in (5) are line segments and arcs (Fu, 1989). Using (5), a set that contains frequency response boundaries $\partial G (i w_{0}, a, b)$ , call it $S$ , is obtained as follows

S \overset{Δ}{=} {\partial (\frac{L_{Ni}}{L_{Dj}}) : i = 1, 2, 3, 4; j = 1, 2, 3, 4}

(6)

Thus, the set $S$ , by its construction above, has a total of 32 elements which are 16 line segments and 16 arcs. To eliminate the redundant elements of $S$ , the ED algorithm uses a cubic Bezier curve formulation to represent its elements and operates on them. The ED algorithm generates exact boundaries and presents them in the form of a matrix array. In the next section we briefly describe the cubic Bezier curve formulation, and the Bezier clipping algorithm to find intersections of any two cubic Bezier curve formulated lines. Following this we present the ED algorithm that discards members of $S$ , partially or completely, that are not on the frequency response boundaries and keeps those on the boundaries with their exact parametric representations in a matrix array form. In the case study section we illustrate the validity and performance of the ED algorithm for some linear interval systems. The last section is devoted to some conclusive remarks.

2 Cubic Bezier curve formulation of the frequency response

In the ED algorithm we represent the lines parametrically in cubic Bezier form. We next provide a brief description of this formulation. Bezier curves, introduced originally by de Casteljau, and then by Bezier, parametrize certain curves in a powerful way (Farouki, 2012). They are widely used in computer-aided design due to their ability to manipulate geometric shapes in a computationally efficient way. Its detailed history and underlying philosophy are discussed in Farouki (2012) and Yamaguchi (1988).

A cubic Bezier function $P (t) Δ = (x (t), y (t))$ is a polynomial with a range defined for $0 \leq t \leq 1$ . A cubic Bezier function is completely specified with four control points $(C_{0}, C_{1}, C_{2}, C_{3})$ corresponding to the parameter values $(0, t_{1}, t_{2}, 1) .$ The P values corresponding to these t parameters are denoted by $(P_{0}, P_{1}, P_{2}, P_{3})$ . The control points $C_{0}$ and $C_{3}$ are equal $P_{0}$ and $P_{3}$ , respectively. However, the control points $C_{1}$ and $C_{2}$ are on the tangent lines passing through $P_{0}$ and $P_{3}$ , respectively; that is, $C_{1}$ is the direction of the curve at $P_{0}$ , and to $P_{3}$ the curve comes from the direction $C_{2}$ . For use in the ED algorithm we call $\vec{C_{3} C_{2}}$ the bounding vector of the curve; likewise, we call $\vec{C_{0} C_{1}}$ the departing vector of the curve, where $\vec{C_{i} C_{j}}$ denotes a vector with initial point at $C_{i}$ and final point at $C_{j}$ . The cubic Bezier curve in terms of the control points is written as

P (t) = (1 - t)^{3} C_{0} + 3 (1 - t)^{2} t C_{1} + 3 (1 - t) t^{2} C_{2} + t^{3} C_{3}, t \in [0, 1]

where $t^{n} (1 - t)^{3 - n}, n = 0, 1, 2, 3,$ are called Bernstein basis polynomials for a cubic Bezier function.

For a more accurate representation of $S$ , it is augmented by replacing the large arcs with their partitions, that is, if any arc angle is bigger than $π / 2$ radians, we partition it into smaller arcs so that none will have an angle bigger than $π / 2$ radians. The reasoning for this partitioning is that the cubic Bezier curves have been shown to approximate circular arcs effectively for angles of $π / 2$ or less. It has been shown that a quarter of a unit circle ( $90^{\circ}$ arc) can be approximated by a cubic Bezier curve with an error $1.96 \times 10^{- 4}$ in the radius (Riskus, 2006). Depending on the rectangles $R_{N}$ and $R_{D}$ , following the augmentation, the set $S$ may have more than 32 members. Since, even in the extreme cases, one arc is not partitioned into more than four arcs, therefore, the number of elements in $S$ , call it q, is upper bounded by 80. For referencing in the sequel let us denote elements of $S$ by $s_{i}, i = 1, 2, \dots, q$ . Even though $S$ is a subset of the right-hand side of (4) it still contains redundant interior lines in addition to the boundary lines. Figure 1 is an illustrative example showing both boundary and interior elements of $S$ . The ED algorithm to be presented in this section determines the curves forming the frequency response boundaries $\partial G (i w_{0}, a, b)$ . In this process it not only determines elements of $S$ on the boundaries, but also their parts lying on the boundaries if any of them is partially on the boundaries and partially in the interior of the set $G (i w_{0}, a, b)$ . An element of $S$ has such partially boundary and partially interior feature if it is intersected by another element of the set. For this reason the ED algorithm needs a tool to find out whether any two curves intersect, and in the case of intersection, to find the intersection point or points. For this purpose a special case of a tool called the fatline algorithm (Sederberg and Nishita, 1990) is utilized in the following. Noting that the elements of $S$ are either line segments or arcs, in the case of interest where their ends are located at the same point (it will be shown that this will be the case in the ED algorithm), any two elements may intersect at most at one point, and taking this into account gives rise to a special case of the fatline algorithm which we present next.

Let two curves $P (t), 0 \leq t \leq 1$ and $Q (u), 0 \leq u \leq 1$ be represented with a cubic Bezier formulation where their control points correspond to the parameter values $t = 0, t = \frac{1}{3}, t = \frac{2}{3}$ , and $t = 1$ . To find the intersection of these two curves we form two parallel lines $L_{1}$ and $L_{2}$ that enclose control points of $Q (u)$ . Let the control points of Q be $(q_{0}, q_{1}, q_{2}, q_{3})$ , and define a straight line $\bar{L}$ passing through the points $q_{0}$ and $q_{3}$ . Denoting the signed distance of the ith control point of $Q (u)$ to $\bar{L}$ by $d_{i}$ , distances $d_{\min}$ and $d_{\max}$ of $L_{1}$ and $L_{2}$ respectively from $\bar{L}$ are calculated by

d_{\min} = \frac{3}{4} min {0, d_{1}, d_{2}}, d_{\max} = \frac{3}{4} max {0, d_{1}, d_{2}}

(7)

The region between the parallel lines is called the fatline. Following this we find parts of $P (t)$ lying outside the fatline, and clip those parts out. Let $r_{i}, i = 0, 1, 2, 3,$ denote the distance from the ith control point of P to $\bar{L}$ . Using the distances $r_{i}$ as the control points of a cubic Bezier function $r (t)$ , form a vector function $(t, r (t))$ and clip out its parts corresponding to the t values such that $r_{i} \geq d_{\max}$ or $r_{i} \leq d_{\min}$ . The clipped out parts are omitted from any further consideration. Note that, since $Q (u)$ is entirely contained in the fatline, it does not intersect with the clipped out parts of $P (t)$ . The second iteration starts with constructing a fatline bounding the control points of the remaining parts of $P (t)$ , and clip out the parts of $Q (u)$ that lie outside the fatline of $P (t)$ . In the following steps this procedure continues by reversing the roles of the remaining parts of the curves. It is reported that after three Bezier clips on each curve, six-digit accuracy is possible (Sederberg and Nishita, 1990). This special case of the Bezier clipping algorithm reasoned above is itemized below:

Iterate the following until there is no change in fatline width within six digits:

For $Q (u)$ , form the line $\bar{L}$ connecting $q_{0}$ and $q_{3}$ .

Form two lines $L_{1}$ and $L_{2}$ by (7).

Use $r_{i}, i = 0, 1, 2, 3,$ as the ith control point of P to $\bar{L}$ and form a cubic Bezier function $r (t)$ . Form a vector function $(t, r (t))$ and clip out its parts corresponding to the t values such that $r_{i} \geq d_{\max}$ or $r_{i} \leq d_{\min}$ . The clipped out parts are omitted from any further consideration.

Terminate the algorithm if the clipped out part contains all of the control points of $P (t)$ and report that no intersection exists.

Change the roles of Q and the remaining part of P.

In the algorithm above, because the curves of interest are line segments and arcs, the $d_{\min}$ and $d_{\max}$ formulas give the tightest possible fatlines. Of course, in the case of a line segment both $d_{\min}$ and $d_{\max}$ equal zero, the fatline equals the line itself. The algorithm also determines the case of no intersection point by clipping out $P (t)$ completely, in which case the algorithm terminates immediately with the report of no intersection.

We next present the ED algorithm that retains only the boundary elements, or their parts, in the set $S$ and discards the others. For the sake of simplicity in presenting the ED algorithm, a description of some initial settings is in order. Let $S$ be the set given by (6). First, for every arc in $S$ with angle bigger than $π / 2$ , partition it into sub-arcs with angles $π / 2$ or less. Revise the set $S$ by replacing such arc with its sub-arcs. Following this, represent every element $s_{i}$ of $S$ in the cubic Bezier form with control points $(s_{i, 0}, s_{i, 1}, s_{i, 2}, s_{i, 3})$ corresponding to the parameter values $(0, \frac{1}{3}, \frac{2}{3}, 1)$ . Consider the endpoints ${s_{1, 0}, s_{1, 3}, s_{2, 0}, s_{2, 3}, \dots, s_{q, 0}, s_{q, 3}}$ of the elements in $S$ and find the leftmost element (i.e. element with the smallest real part) in the set, call it the current node and for this node initialize the bounding vector as a vector directed towards the left (i.e. direction of the negative real axis). Let us define the departing angle for a cubic Bezier curve formulated curve $s_{i}$ as the angle of the vector from the control point $s_{i, 0}$ to the control point $s_{i, 1}$ . Using the settings above, the ED algorithm can be itemized below:

Form a set $D$ that contains elements of $S$ whose ends are at the current node.

At the current node, re-parametrize every line, if needed, so that in the cubic Bezier form representation, its end at the current node corresponds to the parameter’s zero value.

At the current node, calculate the departing angle for each element of $D$ .

Among the curves of $D$ , find the one whose departing angle is the closest angular neighbor to the bounding vector in the clockwise direction. Denote the so determined curve by $s^{*}$ .

Excluding the initial endpoint of $s^{*}$ , check whether it intersects with any other curve in $D$ by using the Bezier clipping algorithm. If it does not intersect then keep $s^{*}$ intact. If it intersects with any element of $D$ then partition it into parts so that the intersection point becomes the final endpoint of $s^{*}$ . Using this final endpoint, update $s^{*}$ and list it as a curve on the boundary.

Go to the final end of $s^{*}$ and set that end as the current node.

Terminate the algorithm if the current node is the initial current node.

8 In the current node, set the bounding vector to a vector with the initial and final points as $s_{i, 3}^{*}$ and $s_{i, 2}^{*}$ , respectively.

Go to Step 1.

In the algorithm above the first three steps are executed to determine the departing angles of the curves departing from the current node $D$ . Using these angles, an element of $D$ on the boundary is obtained. However, if it intersects with another element of $D$ , then its part beyond the intersection may or may not be on the boundary at all. The fourth through the sixth steps have the task to find an intersection if it exists. In the case of intersection, part of the curve up to the intersection is marked as a boundary curve. Iterations continue for the successive current nodes to determine the other curves on the boundaries. They terminate when the current node of the initial iteration is encountered. Note that the first and second control points of a cubic Bezier curve are used for calculating its departing vector, whereas the third and fourth control points are used for that of its bounding vector. Because all of the control points of the cubic Bezier formulation are essentially needed by the algorithm, this formulation may be viewed as best fitting to the ED of the frequency response of an interval system.

3 Case studies

In this section two illustrative examples, corresponding to two different $R_{N}$ and $R_{D}$ locations, are presented. In the first case, corner points of $R_{N}$ and $R_{D}$ are $((- 4, 3), (- 2, 3), (- 2, 1), (- 4, 1))$ and $((1, 4), (5, 4), (5, 2), (1, 2))$ , respectively. The rectangles and the corresponding set $S$ are depicted in Figure 1. Cubic Bezier coefficients of 32 curves forming the set $S$ are shown in Table 1. The bounding vectors of the current nodes for the first five iterations are indicated in Figure 2. The curves forming the boundaries in graphics form are shown in Figure 3 and the corresponding array of cubic Bezier coefficients are given in Table 2. It should be noted that the ED algorithm moves the curves of Table 2 that lie on the boundaries to Table 2. Also, the ED algorithm processes the curves in $S$ in the clockwise direction, consequently the parameter of every curve progresses in the same direction. For the curves that are partially on the boundary of the frequency response, the parts on the boundary are determined by the Bezier clipping routine of the ED algorithm and only the parts on the boundary take place in Table 2.

Table 1:

Cubic Bezier curve coefficients for the members of $S$ for Case 1.

No.	$x_{0}$	$y_{0}$	$x_{1}$	$y_{1}$	$x_{2}$	$y_{2}$	$x_{3}$	$y_{3}$
00	0.470588	1.117647	0.200550	1.164205	−0.087153	1.007952	−0.195122	0.756098
01	−0.195122	0.756098	−0.284554	0.796467	−0.386021	0.809521	−0.482759	0.793103
02	−0.482759	0.793103	−0.598323	1.397035	−0.194063	2.041325	0.400000	2.200000
03	0.400000	2.200000	0.502325	1.850160	0.526609	1.477814	0.470588	1.11764
04	0.588235	0.647059	0.415783	0.743527	0.182645	0.706324	0.048780	0.560976
05	0.048780	0.560976	−0.002345	0.609890	−0.068209	0.643119	−0.137931	0.655172
06	−0.137931	0.655172	−0.071571	1.093582	0.357955	1.434676	0.800000	1.400000
07	0.800000	1.400000	0.785620	1.137551	0.712769	0.878527	0.588235	0.647059
08	0.117647	0.529412	−0.004894	0.528294	−0.118983	0.436527	−0.146341	0.317073
09	−0.146341	0.317073	−0.188921	0.327681	−0.234611	0.325308	−0.275862	0.310345
10	−0.275862	0.310345	−0.375025	0.566830	−0.248694	0.882658	0.000000	1.000000
11	0.000000	1.000000	0.073010	0.854257	0.113483	0.692367	0.117647	0.529412
12	0.000000	1.000000	−0.220127	0.948972	−0.388781	0.738155	−0.390244	0.512195
13	−0.390244	0.512195	−0.471131	0.514257	−0.552422	0.491709	−0.620690	0.448276
14	−0.620690	0.448276	−0.901777	0.870283	−0.800712	1.489307	−0.400000	1.800000
15	−0.400000	1.800000	−0.210284	1.566866	−0.072678	1.291653	0.000000	1.000000
16	0.470588	1.117647	0.509804	0.960784	0.549020	0.803922	0.588235	0.647059
17	−0.195122	0.756098	−0.113821	0.691057	−0.032520	0.626016	0.048780	0.560976
18	−0.482759	0.793103	−0.367816	0.747126	−0.252874	0.701149	−0.137931	0.655172
19	0.400000	2.200000	0.533333	1.933333	0.666667	1.666667	0.800000	1.400000
20	0.588235	0.647059	0.431373	0.607843	0.274510	0.568627	0.117647	0.529412
21	0.048780	0.560976	−0.016260	0.479675	−0.081301	0.398374	−0.146341	0.317073
22	−0.137931	0.655172	−0.183908	0.540230	−0.229885	0.425287	−0.275862	0.310345
23	0.800000	1.400000	0.533333	1.266667	0.266667	1.133333	0.000000	1.000000
24	0.117647	0.529412	0.078431	0.686275	0.039216	0.843137	0.000000	1.000000
25	−0.146341	0.317073	−0.227642	0.382114	−0.308943	0.447154	−0.390244	0.512195
26	−0.275862	0.310345	−0.390805	0.356322	−0.505747	0.402299	−0.620690	0.448276
27	0.000000	1.000000	−0.133333	1.266667	−0.266667	1.533333	−0.400000	1.800000
28	0.000000	1.000000	0.156863	1.039216	0.313725	1.078431	0.470588	1.117647
29	−0.390244	0.512195	−0.325203	0.593496	−0.260163	0.674797	−0.195122	0.756098
30	−0.620690	0.448276	−0.574713	0.563218	−0.528736	0.678161	−0.482759	0.793103
31	−0.400000	1.800000	−0.133333	1.933333	0.133333	2.066667	0.400000	2.200000

Table 2:

Cubic Bezier coefficients for the boundaries for Case 1.

No.	$x_{0}$	$y_{0}$	$x_{1}$	$y_{1}$	$x_{2}$	$y_{2}$	$x_{3}$	$y_{3}$
00	−0.620690	0.448276	−0.901777	0.870283	−0.800712	1.489307	−0.400000	1.800000
01	−0.400000	1.800000	−0.268955	1.865523	−0.137909	1.931045	−0.006864	1.996568
02	−0.006864	1.996568	0.113261	2.089506	0.250631	2.160103	0.400000	2.200000
03	0.400000	2.200000	0.533333	1.933333	0.666667	1.666667	0.800000	1.400000
04	0.800000	1.400000	0.785620	1.137551	0.712769	0.878527	0.588235	0.647059
05	0.588235	0.647059	0.431373	0.607843	0.274510	0.568627	0.117647	0.529412
06	0.117647	0.529412	0.076486	0.529036	0.036278	0.518433	−0.000009	0.499989
07	−0.000009	0.499989	−0.048787	0.439017	−0.097564	0.378045	−0.146341	0.317073
08	−0.146341	0.317073	−0.188921	0.327681	−0.234611	0.325308	−0.275862	0.310345
09	−0.275862	0.310345	−0.390805	0.356322	−0.505747	0.402299	−0.620690	0.448276

As a second case, corner points of $R_{N}$ and $R_{D}$ are chosen as $((4, 3), (2, 3),$ (2,1),(4,1)) and $((1, 4), (5, 4), (5, 2), (1, 2))$ , respectively. The rectangles and the corresponding set $S$ are shown in Figure 4. Cubic Bezier coefficients of 32 curves forming the set $S$ is shown in Table 3. The bounding vectors of current nodes for the first five iterations are indicated in Figure 5. The boundary curves and their cubic Bezier coefficients are given in Figure 6 and Table 4, respectively. The cases presented in this section illustrates functioning and validity of the ED algorithm.

Table 3:

Cubic Bezier curve coefficients for the members of $S$ for Case 2.

No.	$x_{0}$	$y_{0}$	$x_{1}$	$y_{1}$	$x_{2}$	$y_{2}$	$x_{3}$	$y_{3}$
00	0.941176	−0.764706	1.061482	−0.518505	0.992037	−0.198560	0.780488	−0.024390
01	0.780488	−0.024390	0.844283	0.050161	0.885226	0.143914	0.896552	0.241379
02	0.896552	0.241379	1.508684	0.183220	2.014009	−0.385270	2.000000	−1.000000
03	2.000000	−1.000000	1.635503	−1.000277	1.271251	−0.919332	0.941176	−0.764706
04	0.823529	−0.294118	0.846249	−0.097828	0.722239	0.103068	0.536585	0.170732
05	0.536585	0.170732	0.562074	0.236738	0.567414	0.310316	0.551724	0.379310
06	0.551724	0.379310	0.981932	0.486674	1.461991	0.221378	1.600000	−0.200000
07	1.600000	−0.200000	1.352208	−0.287668	1.085090	−0.320046	0.823529	−0.294118
08	0.352941	−0.411765	0.425572	−0.313061	0.420611	−0.166729	0.341463	−0.073171
09	0.341463	−0.073171	0.375498	−0.045472	0.401012	−0.007496	0.413793	0.034483
10	0.413793	0.034483	0.678479	−0.040078	0.855343	−0.330640	0.800000	−0.600000
11	0.800000	−0.600000	0.639599	−0.570962	0.485804	−0.506206	0.352941	−0.411765
12	0.470588	−0.882353	0.640805	−0.733739	0.690409	−0.468357	0.585366	−0.268293
13	0.585366	−0.268293	0.657707	−0.232048	0.718824	−0.173898	0.758621	−0.103448
14	0.758621	−0.103448	1.205231	−0.343532	1.407361	−0.937288	1.200000	−1.400000
15	1.200000	−1.400000	0.922893	−1.283572	0.671964	−1.105493	0.470588	−0.882353
16	0.941176	−0.764706	0.901961	−0.607843	0.862745	−0.450980	0.823529	−0.294118
17	0.780488	−0.024390	0.699187	0.040650	0.617886	0.105691	0.536585	0.170732
18	0.896552	0.241379	0.781609	0.287356	0.666667	0.333333	0.551724	0.379310
19	2.000000	−1.000000	1.866667	−0.733333	1.733333	−0.466667	1.600000	−0.200000
20	0.823529	−0.294118	0.666667	−0.333333	0.509804	−0.372549	0.352941	−0.411765
21	0.536585	0.170732	0.471545	0.089431	0.406504	0.008130	0.341463	−0.073171
22	0.551724	0.379310	0.505747	0.264368	0.459770	0.149425	0.413793	0.034483
23	1.600000	−0.200000	1.333333	−0.333333	1.066667	−0.466667	0.800000	−0.600000
24	0.352941	−0.411765	0.392157	−0.568627	0.431373	−0.725490	0.470588	−0.882353
25	0.341463	−0.073171	0.422764	−0.138211	0.504065	−0.203252	0.585366	−0.268293
26	0.413793	0.034483	0.528736	−0.011494	0.643678	−0.057471	0.758621	−0.103448
27	0.800000	−0.600000	0.933333	−0.866667	1.066667	−1.133333	1.200000	−1.400000
28	0.470588	−0.882353	0.627451	−0.843137	0.784314	−0.803922	0.941176	−0.764706
29	0.585366	−0.268293	0.650407	−0.186992	0.715447	−0.105691	0.780488	−0.024390
30	0.758621	−0.103448	0.804598	0.011494	0.850575	0.126437	0.896552	0.241379
31	1.200000	−1.400000	1.466667	−1.266667	1.733333	−1.133333	2.000000	−1.000000

Table 4:

Cubic Bezier coefficients for the boundaries for Case 2.

No.	$x_{0}$	$y_{0}$	$x_{1}$	$y_{1}$	$x_{2}$	$y_{2}$	$x_{3}$	$y_{3}$
00	0.341463	−0.073171	0.360980	−0.048775	0.380497	−0.024379	0.400013	0.000016
01	0.400013	0.000016	0.405559	0.011092	0.410184	0.022628	0.413793	0.034483
02	0.413793	0.034483	0.459770	0.149425	0.505747	0.264368	0.551724	0.379310
03	0.551724	0.379310	0.910675	0.468891	1.304330	0.299039	1.505052	−0.004446
04	1.505052	−0.004446	1.808806	−0.238723	2.008887	−0.610059	2.000000	−1.000000
05	2.000000	−1.000000	1.733333	−1.133333	1.466667	−1.266667	1.200000	−1.400000
06	1.200000	−1.400000	0.922893	−1.283572	0.671964	−1.105493	0.470588	−0.882353
07	0.470588	−0.882353	0.431373	−0.725490	0.392157	−0.568627	0.352941	−0.411765
08	0.352941	−0.411765	0.425572	−0.313061	0.420611	−0.166729	0.341463	−0.073171

4 Conclusions

Arcs and line segments that are potentially on the frequency response boundary of linear interval systems have been modeled as cubic Bezier curves. A novel ED algorithm is used to find those, or their parts, on the boundaries. This algorithm uses a Bezier clipping routine as a tool for determining the intersection of any two curves if it exists. It has been shown that every control point in the cubic Bezier formulation has a geometric meaning which is essentially useful for the ED algorithm, therefore, the cubic Bezier curve formulation provides a good fitting to the frequency response boundary computation problem. Two examples corresponding to two different numerator and denominator rectangle locations have been presented to illustrate validity and mechanics of the algorithm.

Footnotes

Declaration of Conflicting Interests

The authors declare that there is no conflict of interests.

Funding

This research received no specific grant from any funding agency in the public, commercial, or not-for-profit sectors.

References

Bailey

Panzer

(1988) 2 algorithms for frequency domain design of robust control systems. International Journal of Control 48: 1787–1806.

Bartlett

Hollot

Lin

(1988) Root locations of an entire polytope of polynomials: it suffices to check the edges. Mathematics of Control, Signals, and Systems 1: 61–71.

Bhattacharyya

Keel

Chapellat

(1995) Robust Control: The Parametric Approach. Englewood Cliffs, NJ: Prentice-Hall.

Chen

Hwang

(1998) Computing frequency responses of uncertain systems. IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications 45: 304–307.

Farouki

(2012) The Bernstein polynomial basis: A centennial retrospective. Computer Aided Geometric Design 29: 379–419.

(1990) Computing frequency response of linear systems with parametric perturbation. Systems & Control Letters 15: 45–52.

Gutman

Baril

Neumann

(1994) An algorithm for computing value sets of uncertain transfer functions in factored real form. IEEE Transactions on Automatic Control 39: 1266–1273.

Karamancıoğlu

Dzhafarov

(1998) A sectoring algorithm for exact computation of the frequency response of linear interval systems. Circuits, Systems and Signal Processing 17: 483–493.

Minnichelli

Anagnost

Desoer

(1989) An elementary proof of Kharitonov’s stability theorem with extensions. IEEE Transactions on Automatic Control 34: 995–998.

10.

Ogata

(2010) Modern Control Engineering, 5th edn. Englewood Cliffs, NJ: Prentice-Hall.

11.

Riskus

(2006) Approximation of a cubic Bezier curve by a circular arcs and vice versa. Information Technology and Control 35: 371–378.

12.

Sederberg

Nishita

(1990) Curve intersection by Bezier clipping. Computer-Aided Design 22: 538–549.

13.

Yamaguchi

(1988) Curves and Surfaces in Computer Aided Geometric Design. Berlin: Springer-Verlag.

14.

Yang

(2009) An improvement of QFT plant template generation for systems with affinely dependent parametric uncertainties. Journal of the Franklin Institute 346: 663–675.

15.

Yang

(2010) Efficient algorithm for computing QFT bounds. International Journal of Control 83: 716–723.