数理解析研究所講究録 1456 巻 2005 年 49-57

49

On Computing Sum of Roots with Positive RealParts of Polynomials
穴井 宏和
HIROKAZU ANAI(株) 富士通研究所/(独) 科学技術振興機構
FUJITSU LABORATORIES LTD / CREST, JST *

横山和弘

原 辰次

KAZUHIRO YOKOYAMASHINJI BARA

立教大学/(独) 科学技術振興機構

東京大学/(独) 科学技術振興機構

RJKKYO UNIVERSITY/CREST, JST \dag er

TOKYO /CREST, JST \dager
THE UNIVERSITY OF Tokyo

Abstract

In this paper we present a method to compute or estimate the sum of roots with positive real parts(SORPRP) of a polynomial, which is related to a certain index of stability in optimal control, without
computing numerical values of the roots explicitly The method is based on symbolic computations andenables us to deal with polynomials with parametric coefficients for their SORPRP. This leads to provide
a novel systematic method to achieve optimal regulator design in control by combining with quantifier
elimination. We show some experimental result for a typical class of plants to confirm the effectiveness ofthe proposed method.

Introduction

1

In control and system theory, investigating location of roots of the characteristic polynom iai is one ofimportant and fundamental topics related to the stability of feedback control systems. For example, in
wherecontrolled by acontrollercase of atypical feedback system with aplant, $P(s)\in \mathbb{Q}[s]$ , the stability of the system is described as follows: The feedback system is,,locatestable if and only if all of the roots of the closed-loop characteristic polynomial
$Hu$
more
may
considerstability.
We
rwitz
is
This
calledplane.
within the left-half plane of the Gaussian
general notion of stability, called DInstability, which implies that all of the roots locate inside a restricted
region within the left-half plane of the Gaussian plane.
Control design problem is to find a controller $C(s)$ so that the system satisfies given specifications. As
has fixed-structure with some parameters , what we have to do is to seek feasible
the controller
controller parameters which satisfies the specifications. For such problems, techniques in computer$C(s)= \frac{7b_{\mathrm{C}}(\mathrm{S})}{d_{\mathrm{c}}(s)}$$P(s)= \frac{n_{q}(s\}}{d_{q}(s)}$$n_{q}(s)$$d_{q}(s)$$n_{c}(s)$$g(s)=n_{p}n_{\mathrm{c}}+d_{p}d_{p}$$\prime D$$C(s, \mathrm{q})$$\mathrm{q}$$\mathrm{q}$fujitsu com
Tyokoyama@rkmath.rikkyo ac.j$shinjiixara@ipc.i.u-tokyo ac jP$*\mathrm{a}\mathrm{n}\mathrm{a}\mathrm{i}@\mathrm{j}\mathrm{p}$$\mathrm{p}$soalgebra have been successfully applied [9, 13, 1, 2]. Stability is the first necessary requirement for control
system design. Assigning roots of a certain polynomial within a desired region is an essential problem
for stability study. Root assignm ent problem for Hurwitz stability is to find controller parameters sothat the system is Hurwitz stable. This is easily verified by the well-known Rout -Hurwitz criterion. In
the case of $D$-stabiiity, a wedge shape region or a circle is usually used as stability region . For root
assignment problems with such stability regions, controller design problem is reduced to check a sign
, see $[14, 12]$ . Applying real quantifier
definite condition (SDC) $\forall z>0$ , $f(z)>0$ where
elimination (QE) to the sign definite condition, we can obtain possible regions of controller parameters
to meet $D$-stability. For a sign definite condition we can utilize an efficient quantifier elimination
algorithm specialized to SDC $[1, 10]$ . These two controller synthesis methods with respect to stability
are implemented as functions in a MATLAB toolbox for robust parametric control [3]In this paper we focus on the sum of roots with positive real parts (SORPRP) of a given even polynomial, and provide another successful application of computer algebra to control design problem, where the
SORPRP is related to certain index of stability in optimal control. We call the index “stability index”.
Here we compute or estimate the SORPRP without computing explicit numerical values of roots. Hence,$\mathrm{q}$$/D$$f(z)\in \mathbb{Q}(\mathrm{q})[z]$$\mathrm{q}$we can handle polynomials with parametric coefficients for their SORPRP.
The key point of the method is that computing SORPRP is reduced to computation of the maxim alreal root of another univariate polynomial. Subsequently this enables us to achieve control system design
with respect to SORPRP systematically. In fact, since the actual control design problems treated arerecast as simple conditions on an univariate polynomial with parametric coefficients (one of them is asign definite condition), we can utilize an efficient quantifier elimination algorithm using Sturm-Habicht
sequence $[1, 10]$ . The proposed method is applied to an even polynomial derived from “Linear Quadratic
Regulator (LQR) problem” which is one of the main concerns in control theory.

SORPRP of even polynomials

2

First we consider an even polynomial $f(x)$ of degree $2m$ in,,,be roots of $f(x)$ with positive real parts andWe set{a 1, ... , }. So,$\alpha_{1}$$\ldots$$\alpha_{m+1}$$\alpha_{m}$$\Omega=$$\mathbb{Q}[x]$$\ldots$,

with non zero constant, and let
roots with negative real parts.

$\alpha_{2m}$$\alpha_{2m}$$\mathrm{f}(\mathrm{x})=a_{2m}x^{2m}+a_{2m-2}x^{2m-2}+\cdots+a_{2}x^{2}+a0=a_{2m}\prod_{i=1}^{2m}\langle x-\alpha_{i})$,for $0\leq k\leq m$ , $a_{2m}\neq 0$ and $a_{0}\neq 0$ . Our first target is to compute $W=\alpha_{1}+$ . . .
where
without computing all a . For simplicity, we call $W$ the SORPRP of . Since, for each non real root of$f(x)$ , its complex conjugate has the same real part, we have the following:$+\alpha_{m}$$a_{2k}\in \mathbb{Q}$$f$$i’ \mathrm{s}$Lemma 1
$W$ is a real number.

2.1
Let

Polynomial having SORPRP as its root
$B_{i_{1},\ldots,i_{m}}=\alpha_{\mathrm{i}_{1}}+\cdots+\alpha_{i_{m}}$for$\mathrm{i}_{1}<$...

$<\mathrm{i}_{m}$

, and

$B$

the set of all distinct values of$B_{i_{1},\ldots,i_{m}}$.

51
Definition 2
Gathering all sums
, ..,where is a new variable:$B_{i_{1}}$$i_{m}$, we can construct a polynom

and its square-tee part$\mathrm{i}alR_{m,f}(z)$$\overline{R}_{m,f}(z)$,$z$$R_{m,[}(z)= \prod_{i_{1}<\ldots<i_{\tau n}}(z-B_{i_{1},\ldots,i_{m}})$,$\overline{R}_{m,f}(z)=\prod_{B\in B}(z-B)$

.

,
and
for distinct , . . .,coincides with
, .
As there might be a case where
are algebraic number, it
might be smaller than $R_{m,f}(z)$ . Since ai7,
the square-free part$R_{m,f}(z)$the characteristic
and. We may calland sofollows thatpolynomial of sums of $m$ roots, and the minimal polynomial of sums of $m$ roots, respectively.
$(i_{1}$$Bj_{1}$$B_{i_{1},..,\iota_{m}}$’$B_{21}$$\overline{R}_{m,f}(z)$$R_{m,f}(z)\in \mathbb{Q}[y]$$\overline{R}_{m,f}(z)$$\mathrm{i}_{m})$$j_{m}$$(j_{1,\ldots\gamma}j_{m})$$..,i_{m}$$\overline{R}_{m,f}(z)$$\in \mathbb{Q}[y]$It is obvious that the SORPRP $W=\alpha_{1}+\cdots+\alpha_{m}$ of $f(x)$ coincides with the maximal real root of
and $R_{m,f}(z)$ , we use the following$\overline{R}_{m,f}(z)(R_{m,f}(z))$ , since $W$ is a real number.
To compute
triangular set related to Cauchy moduli [5] defined by $f(x)$ .
$\overline{R}_{m,f}(z)$Definition 3
Let $D$ be an arbitrary computable integral domain and $K$ its quotient field. For a polynomial $g(x)$of degree in $D[x]$ , we define the following polynomials: $\{g_{1}(x_{1}), g_{2}(x_{1},x_{2}), \ldots,g_{n}(x_{1}, \ldots,x_{n})\}$ , wherefor eachis the quotient of $g(x_{i})$ divided by, ...,
andquotient
of
with
the
coincides,Xi), ] and,$i>1$ . We note thatthe standard triangular set defined, Xi-i)divided by $x_{i}-x_{i-1}$ . Here we call( ,the k-th standard triangular set defined by $g(x)$ .
, and also callby$n$$g_{i}(x_{1}$$\mathrm{g}(\mathrm{x})=\mathrm{g}(\mathrm{x})$$g_{i}(x_{1}, \ldots, x_{i})\in \mathrm{D}[\mathrm{x}]$$g_{i-1}$$x_{1}$$\ldots$$9\mathrm{i}(\mathrm{x}\mathrm{i})\ldots$$x_{i}$$\{g_{1}, \ldots,g_{n}\}$$x_{i})$$\ldots$$(x_{\mathrm{i}}-x_{i-1})$$(\mathrm{x}\mathrm{i}-x_{1})\cdots$$x_{i})$$\{g_{1}, \ldots, g_{k}\}$$\mathrm{g}(\mathrm{x})$generated by itself
It is well-known that $\{g1, \ldots, gk\}$ forms a Grobner basis of the ideal
and the set of all its zeros with
with respect to the lexicographic order $x_{1}<$ . $..<x_{k}$ in$i_{k}\in\{1,\ldots,n\}$are distinct to each,,
multiplicities counted coincides with the set {other }, where , , are all roots of $g(x)$ in the algebraic closure of $K$ . Thus, when $g(x)$ is square free,with respect to the order
is a radical ideal. We note that for each its leading coefficient$F$$=\{f1(x_{1}),\ldots,f_{m}(x_{1},\ldots, x_{m})\}$ be thecoincides with the leading coefficient $lc(g)$ of $g(x)$ . Now let
can be computed by successive.
m-th standard triangular set defined by $f(x)$ in
can be computed as the minimal polynomial of $z=x_{1}+\cdots+x_{m}$resultant computation and(with square-free computation if necessary).
modulo the ideal I$\langle g_{1}, \ldots, g_{k}\rangle$$K[x_{1}, \ldots, x_{k}]$$(\beta_{\dot{\iota}_{1}}, \ldots, \beta_{i_{k}})|\mathrm{i}_{1}$$\beta_{1}$$\ldots$$\ldots$$\beta_{n}$$lc(g_{l})$$\langle g_{1}, \ldots, g_{k}\rangle$$g_{\dot{\mathrm{t}}}$$<$$R_{m,f}(z\rangle$$\mathbb{Q}[x_{1}, \ldots, x_{m}]$$\overline{R}_{m,f}(z)$$=\langle \mathcal{F}\rangle$

via resultant Let $T_{m}(z)=z-(x_{1}+\cdots+x_{m})$ and for each $k\leq m$ , weComputation of
successively as follows:
define$R_{m,f}(z\rangle$$T_{k}$$T_{k-1}(z,x_{1}, \ldots, x_{k-1})=res_{x_{k}}(f_{k}(x_{1}, \ldots, x_{k}),T_{k}(z,x_{1}, \ldots ,x_{k}))$,and $T_{0}(z)$ coincides
where resz means the resultant with respect to a variable 2. Thenof Sylvester
By
construction
follows:
as
shown
can
be
.
This
$a_{2m}^{d}R_{m,f}(z)$for some positive integer
with$ , where
respecttowithofleadingcoefficientthethatfollows
itcomputation,
matrices in resultant
same for,theand
for eachis considered as a univariate polynomial in Xj, is some powers of
have
resultant,
weofpropertybythethe leading coefficient of with respect to 2. Then,$T_{0}(z)\in \mathbb{Q}[y]$$d$$T_{i}$$a_{2m}$$T_{l}$$T_{i}$$T_{0}(z)$$=$$T_{1}(z,\alpha_{\mathrm{i}_{1}})$$=$$a_{2m}^{d_{1}} \prod_{i=1}^{2m}T_{1}$( , a ),$z$$t$

$a_{2m}^{d_{2}} \prod_{j_{2}\neq i_{1}}T_{2}(z, \alpha_{\iota_{1}}, \alpha_{i_{2}})$,$j$$j<\mathrm{i}$

52
.

.
$\cdot$(,...,a$i_{m-1}$ )$=$$T_{m}(z,\alpha_{i_{1}}, \ldots, \alpha_{i_{m}})$$=$$T_{m-1}$$z,\alpha_{i_{1}}.$

( ,a
$z$

$a_{2m}^{d_{m}} \prod_{i_{n\iota}\neq i,i_{m-1}},T_{m}$$i_{1},$,$\sim\cdot$$\alpha_{\iota_{m}}$),$z-(\alpha_{i_{1}}+\cdot\cdot +\alpha_{i_{m}})$is a positive integer. (See [8].) When $f(x)\in \mathbb{Z}[x]$ ,belongs to, In order to avoid “coefficient growth” in resultant
are integers,
or its factors for computing smaller factors
computation, we may apply factorization technique to eachof . (See \S 4.2 for usage of factors.) We note that multi-polynomial resultant can be also applied for.
computingwhere ,
that is, all$\mathrm{i}_{1}$$\ldots$,$\mathrm{i}_{m}$are distinct to each other and each
$T_{q}(z)$$a_{2k}$$d_{i}$$\mathbb{Z}[z]$$T_{k}$$T_{\mathrm{f}\mathrm{J}}$$T_{0}(z)$via minimal polynomial Let $z=x_{1}+\cdots+x_{m}$ and I
in
Computation of. Then, we consider a minim al polynomialof modulo , that is, $M(z)$ has the
such that $h(x_{1}+\cdots +x_{m})$ belongs to the ideal Z.
sm allest degree among all polynomials $h(z)$ in,,
Since the set of all zeros of I with multiplicities counted is {( , .. ., aim)aredistinct to each other }, it can be shown easily that $M(z)$ is a factor of $R_{m,f}(z)$ and hasas. ) Especially, when $f(x)$ is
its factor. (We may say that $M(z)$ stands between $R_{m,f}(z)$ and$M(z)/lc(I\sqrt
I(z))$$f(x)$, that is, all. Whensquare-free, thencoincides withare integers,
by removing denominators of coefficients appearing in $M(z)$ , we may assume that $M(z)$ belongs to.
Then the leading coeffici nt $lc(M)$ divides some power of. As we already, as $M(z)$ divides
know the Gr\"obner basisof , $M(z)$ can be computed rather easily.
$=\langle F\rangle$$\overline{R}_{m,f}(z)$$\mathbb{Q}[x_{1}, \ldots, x_{m}]$$M(\mathrm{z})$$\mathrm{I}$$z$$\mathbb{Q}[z]$$|\mathrm{i}_{1}$$\alpha_{i_{1}}$$\mathrm{i}_{m}\in\{1, \ldots, 2m\}$$\ldots$$\overline{R}_{m_{rf}}(z)$$\overline{R}_{m,f}(z)$$\in \mathbb{Z}[x]$$\overline{R}_{m,f}(z)$$a_{2k}$$\mathbb{Z}[z]$$T_{0}(z)$$a_{2m}$$\{f_{1}, \ldots , f_{m}\}$2.2$\mathrm{I}$Parametric caseNow we consider the case where each coefficient \^a is some polynomial in parameters
Thus, the even polynomial $f(x)$ is considered as a multivariate polynomialin, we can compute the m-th standard triangular setand$h$$f(x, \mathrm{p})$$D=\mathbb{Q}[\mathrm{p}]$$\mathrm{p}=\{p_{1\cdot)},.

$\mathbb{Q}[x, \mathrm{p}]$.p_{\mathrm{f}}\}$.

. Setting$K=\mathbb{Q}(\mathrm{p})$$F$ $=\{f_{1}(x_{1}, \mathrm{p}), \ldots, f_{m}(x_{1}, \ldots, x_{m\}}\mathrm{p})\}$

in $D[x_{1}, \ldots, x_{m}]$ . Then, as tc
for each
in $K[x_{1}, \ldots, x_{m}]$ . By $F$ , we can computebasis ofis the reduced Grobnerby successive resultant computation andas a minimal polynomial of 2 modulo the ideal { in. We note that using a blockorder $\{x_{m}>, .$. $>x_{1}\}>>z$ ,is found in a Grobner basis of $\langle F \cup\{z-(x_{1}+\cdots +x_{m})\}\rangle$ in$K[x_{1}, \ldots, x_{m}, z]$ . Then TO( , p) belongs to, and by removing denominators, we may assume that
also belongs to. As is the reduced Grobner basis ofand the denom inator coincides
with, the following holds. (See Exercises of Chapter 6.3 in [7].)$(f_{i})=a_{2m}(\mathrm{p})$$\mathrm{i},\overline{F}=\{f_{1}/a_{2m}, .

$\langle F\rangle$.

., f_{m}/a_{2m}\}$$T_{0}(z, \mathrm{p})$$M(z, \mathrm{p})$$\mathrm{T})$$\mathrm{Q}[\mathrm{x}\mathrm{i}, \ldots x_{m}]$$M(z, \mathrm{p})$$\mathbb{Q}[y, \mathrm{p}]$$z$$M(z, \mathrm{p})$$\overline{F}$$\mathbb{Q}[y, \mathrm{p}]$$\langle F\rangle$$\mathrm{a}2\mathrm{m}(\mathrm{p})$Theorem 4
For eachparametersconsider the poiynomial
obtained fromwith
. If the leading coefficient$(z)$ for some non-zero constantcoincides within,factor of $R_{m,fc}(z)$ and has
as its factor in.
$(c_{1}, \ldots, c_{t})\in \mathbb{Q}^{t})$$(p_{1}, \ldots,p_{t})$$T_{0}(z, c_{1}, \ldots , ct)$

$f_{c}(z)$$(c_{1}, \ldots, c_{l})$$cR_{m}$by substituting thedoes not vanisii, then, and $M(z, c_{1}, \ldots, c_{t})$ is a$f(x, \mathrm{p})$$a_{2m}(c_{1}, \ldots, c_{t})$$c$$f_{\mathrm{c}}$$\overline{R}_{m,f_{\mathrm{c}}}(z)$$\mathbb{Q}$$\mathbb{Q}[z]$By Theorem 4, we can handle the SORPRPs for polynomials with parametric coefficients. For the
total computational efficiency, computing
is much better than computing
in many cases$M(z, \mathrm{p})$$T_{0}(z, \mathrm{p})$533Formulation of Basic Problem
Here we explain the fundamental problem in this paper. We denote the polynomial obtained aboveis the following:. What we do after obtainingbyor$(T_{0}(z, \mathrm{p})$$\mathrm{H}(\mathrm{z})$$\mathrm{H}(\mathrm{z})$$\mathrm{H}(\mathrm{z})\mathrm{p}))$

Problem 1,
andin coefficients,
involving parameters
Given a polynom$W$ofsatisfies. Then find feasible ranges of parameters so that the maximal real root
. Here we exclude, and (c)the following each requirement: (a) $W<lVI_{1}$ , (b)vanishes.
constant
term
or itsranges where the leading coefficient of$\mathcal{R}(z)\in \mathbb{Q}(\mathrm{p})[z]$$\mathrm{i}al\mathcal{R}(z)$$\mathrm{p}$$M_{1}$$M_{2}\in \mathbb{Q}$$\mathcal{R}(z)$$(\mathit{1}1/I_{1}>NI_{2})$$\mathrm{p}$$f\downarrow/I_{2}<W<\mathrm{J}1/I_{1}$$W>\mathrm{M}_{2}$$\mathcal{R}(z)$In view of control theory the param term usually comes from controller or plant parameters of the control
system to be designed, and the above three requirem ents are originated from control design specificationsin terms of SORPRP. PROBLEM 1 is resolved by using quantifier elimination over the real closed field.
as follows:
Actually all of the requirements are reduced to simple first-order formulas for. This is,(a) $W<M_{1}$ : This requirem ent is equivalent to the first-order formulaalgorithm
elimination
quantifier
so called a sign definite condition [1], hence we can solve it by an efficient
using Sturm-Habicht sequence $[11, 6]$ .
(b) $W>M_{2}$ : This requirement is equivalent to the first-order formula: $\exists z>M_{2}$ , $\mathcal{R}(z)=0$ . We
can aiso solve it by an efficient quantifier elimination algorithm using turm-Habicht sequence [10].
This requirement is equivalent to the conjunction of (a) and (b), that is,(c) $f\vee I_{2}<W<M_{1}$ :). Hence, this is achieved by superposing both quantifier-free
A (lz Mx,$\mathrm{p}$$\mathcal{R}(z)\in \mathbb{Q}(\mathrm{p})[z]$$\forall z>M_{1}$$>$$(\forall z>l1/I_{1}, \mathcal{R}(z)\neq 0)$$\mathcal{R}(z)\neq 0$$\mathrm{H}(\mathrm{z})=0$

formulas obtained by performing quantifier elimination for (a) and (b).

4

LQR problem-

control application

We here consider a typical optimal control problem named Linear Quadratic Regulator (LQR) problem.
We will first briefly explain the problem in \S 5.1 and show some computational examples, by which we.
can confirm the effectiveness of our proposed
Here we briefly explain about Linear Quadratic Regulator (LQR) problem (see [18] for more details)
and introduce our target polynomial of which we want to estimate the SORPRP
Let us consider a linear time-invariant SISO (single-input simple output) system represented by$\mathrm{m}\mathrm{e}\mathrm{t}\mathrm{h}\mathrm{o}\mathrm{d}^{1\rangle}$$\mathrm{x}(\mathrm{t})$$y(t)$$=$$x(t)+bu(t)$ ,(1)$=cx(t)$ ,is theis the output,
is the control input,
is the state variable,
where
problem
LQR
the
Then
is the output matrix.
is the input matrix, andsystem matrix,
functionthecost
is to find a control input ze which minimizes$y\in \mathbb{R}$$u\in \mathbb{R}$$x\in \mathbb{R}^{m}$$A\in \mathbb{R}^{m\mathrm{x}m}$$c^{T}\in \mathbb{R}^{m}$$b\in \mathbb{R}^{m}$$J=l_{0}^{\infty}(qy^{2}(t)+ru^{2}(t))dt$,(2)

computations except quantifier elimination are done by using a computer algebra system $Risa/Asir$, see) All QE computations in this paPer were carried out by QEPCAD,.math. kobe-u.
.html, since QEPCAD succeeded in achieving all of QE computations for. .usna.
see http:
our examples in a very small amount of time. For the larger sized problems, we may use an efficient QE algorithm basedon turm-Habicht sequence $[1, 10]$ Some tyPes of QE methods using term-Habicht sequence are available in a Maple
RAC $[4, 17]$
Package$1)\mathrm{A}11$$\mathrm{a}\mathrm{c}.\mathrm{j}\mathrm{p}/\mathrm{A}\mathrm{s}\mathrm{i}\mathrm{r}/\mathrm{a}\mathrm{s}\mathrm{i}\mathrm{r}.\mathrm{h}\mathrm{t}\mathrm{m}\mathrm{l}$$\mathrm{h}\mathrm{t}\mathrm{t}\mathrm{p}://\mathrm{w}\mathrm{w}\mathrm{w}$$//\mathrm{w}\mathrm{w}\mathrm{w}$$\mathrm{S}\mathrm{y}\mathrm{N}$$\mathrm{c}\mathrm{s}$$\mathrm{e}\mathrm{d}\mathrm{u}/\mathrm{q}\mathrm{e}\mathrm{p}\mathrm{c}\mathrm{a}\mathrm{d}/\mathrm{B}/\mathrm{Q}\mathrm{E}\mathrm{P}\mathrm{C}\mathrm{A}\mathrm{D}$54
where $q>0$ and $r>0$ are called weights. If we take the lager value of , we can get the faster response
in general. On the other hands, the lager value of is required when we have a severe restriction on thevalue of , since reflects the penalty on $u(t)$ . Note that the ratio $q/r$ plays an essential role for finding
the optimal control input and determines the closed-loop poles.
Actually, it is well-known that the optimal closed-loop poles are determined by the corresponding
polynomial given by(3)$\varphi(s)=r$ . $d(s)d(-s)+q$ . $n(s)n(-s)$ ,
$q$

$r$

$r$

$u$

where $d(s)$ and $n(s)$ are the denominator and numerator of the transfer function of the plant (1) reP, where $d(s):=det(sI-A)$ , $n(s):=$resented by $P(s)=c(sI-A)^{-1}b$ . In other words,$cadj(sl-A)b$ . Note that $deg(d(s))=m$ , $deg(n(s))<m$ hold.
is our target polynomial with de9(\mbox{\boldmath $\varphi$}(s)) $=2m$ and it is an even polynomial It
The polynomialis strongly desired to establish a guiding principle to choose appropriate values of and or the ratio$q/r$ , since the closed-loop poles are all the poles ofwhich has negative real parts.
In the sequel we carry out an investigation of the weights and in terms of stability index, that is,. We can attain this by just aPPlying our
the sum of roots with negative real parts (SORNRP) of, where the polynomial
has SORPRP
previoustointhesections
method for SORPRP shown
is even, the value of SORPRP coincides with the absolute value ofofas its root. Because, as
SORPNP, and $R(-z)$ also has
SORPNP as its maximal real root.
Particularly we study some behaviors of a parameter involving in the plant $P(s)$ and feasible bounds
for SORPRP $W$ versus the ratio of weights $q/r$ or with $r=1$ under the specifications in \S 4. This kindof investigations is important in practice to see control performance limitations, since the stability index
is one of appropriate measures for the quickness of feedback control system .
$P(s)= \frac{n\langle s)}{d(n)}$$\varphi(s)$

$r$

$q$

$\varphi(s)$

$r$

$q$

$\varphi(s)$$\mathcal{R}(z)$$\mathcal{R}(-z)$$\psi(s)$$\varphi(s\rangle$$-1\mathrm{x}$$q$$\mathrm{s}$4.1

A sample plant:$2\mathrm{n}\mathrm{d}$-order system with time delay

Here we study the LQR problem for a class of typical second-order systems with time delay given by,$P(s)= \frac{\omega_{n}^{2}ke^{-Ls}}{s^{2}+2\zeta\omega_{n}s+\omega_{n}^{2}}\simeq\frac{k\omega_{n}^{2}}{s^{2}+2\zeta\omega_{n}s+\omega_{n}^{2}}\frac{1-\frac{1}{2}Ls}{1+\frac{1}{2}Ls}$

where the exponential
is transformed to a rational function by the Pade approximation. We consider
the case where $k=1$ , $=0.1$ , $\omega_{n}=30(kHz)$ , and $r=1$ . Here, initially we assume that $L>0$ , , $q>0$ .
Then the target even polynomial is expressed as$e^{-L\mathrm{s}}$$r$$\langle$$\varphi(s;q, L)$$=$$d(s)d(-s)+q\cdot n(s)n(-s)$$=$$-25L^{2}s^{6}+(-49L^{2}+100)s^{4}+$ ( $(-25q$

-

25)L

$+196$ ) $s^{2}+$ lOOq +100

remark that the leading coefficient $-25L^{2}$ ofnever vanish as $L>0$ , and the constant termlOOq +100 also never vanish as $q>0$ .
, );Let be the ideal generated by the 3rd standard triangular set of,,
g2 $(x_{1},x_{2},xa; q, L)\}$ , whereis the quotient ofdivided byandis the quotient of. Then we can obtained the following minimal
divided bypolynom ial in of $x_{1}+x_{2}+x_{3}$ with respect toimmediately$\mathrm{V}^{\gamma}\mathrm{e}$$\varphi(s)$$\varphi\langle s;q$$\mathrm{I}_{3}$$\varphi(x_{2}, q, L)$$\varphi_{1}(x_{1}, x_{2};q, L)$$\varphi_{1}(x_{3}, q, L)$$z$$(\mathrm{x}\mathrm{s}-x_{1})(x_{3}-x_{\mathit{2}})$$\mathrm{I}_{3}$$\mathcal{R}(z;q, L)=\mathcal{R}_{1}\mathcal{R}_{2}\mathcal{R}_{3}\mathcal{R}_{4}\mathcal{R}_{5}$$L$$\{\varphi(x_{1}; q, L)$$x_{2}-x_{1}$$\varphi_{1}(x_{1}, x_{2};q, L)$$\varphi_{2}(x_{1},x_{2};x_{3};q, L)$

55
where

$=Lz+2$ ,$=Lz-2$ ,$\mathcal{R}_{1}$R2$=625L^{4}z^{4}-5000L^{3}z^{3}+(2450L^{4}+15000L^{2})z^{2}+(-9800L^{3}$$\mathcal{R}_{3}$$-20000L\}z+$ $(-2500r\mathrm{q}k2 -99)L^{4}+9800L^{2}+10000$ ,$=625L^{4}z^{4}+5000L^{3}z^{3}+(2450L^{4}+15000L^{2})z^{2}+(9800L^{3}$$R_{4}$$+20000L)z+$ (-2500rg&2 -99)L $+9800L^{2}+$ 10000,$=-25z^{4}$ - $49z^{2}$ -2$rqk2- $25.$$\mathcal{R}_{5}$. Since we need to computecoincides with the SORPRP $W$ of
The maximal real root ofcomputing SORPRP
methodaPPly
weour
stability,
sum of roots with negative real parts in a sense of. But, it follows that $\mathcal{R}(-z;q, L)=\mathcal{R}(z;q, L)$ .
to
Relationship between
and : Here we consider the case where the bounds for the SORPRP
are fixed- Then we check the behavior of the plant parameter versus
andare given, that is,a change of . The possible regions of $(L, q)$ to meet the specifications in the $L-q$ parameter space is
as explained in Q4.
obtained by aPPlying quantifier elimination to$\varphi(s;q, L)$$\mathcal{R}(z)$$\mathcal{R}(-z;q, L)$$L$$M_{1}$$q$$L$$M_{2}$$q$$\mathcal{R}(z;q, L)$(a) $W<M_{1}$ : Let $M_{1}=500$ , then the specification (a) is equivalent to the following first-order formula:$\forall z>500$ , $\mathcal{R}(z;q, L)\neq 0$ . After performing quantifier elimination to this, we can obtain the following
equivalent quantifier-free formula in $(L, q)$ which describe feasible regions of $(L, q)$ for (a):( $q+625004\acute{9}0001>=0$ A $250L-1\geq 0$ A
$2500L^{4}q-39063112499901L^{4}+625004900000L^{3}-3750009800L^{2}+10000000L-10000\leq 0$ A
$2500L^{4}q-39063112499901L^{4}$-$625004900000L^{3}-3750009800L^{2}$–

IOOOOOOOL–$10000\leq 0$This is illustrated as a shaded region in Fig.l.

Figure 1: Feasible region of $L-q$ for (a) [Left] , (b) [Middle], and (a) A (b) [Right](b) $W>M_{2}$ : Let $M_{2}=300$ , then the specification (b) is equivalent to the following first-order formula:a following$\exists z>300$ , $\mathcal{R}(z;q, L)=0$ . After performing quantifier elimination to this, we can obtainequivalent quantifier-free formula in $(L, q)$ which describe feasible regions of $(L, q)$ for (b):$(q+8100176401 <0)\vee(L>0\mathrm{A}15\mathrm{O}\mathrm{L} -1<0)\vee$$(2500L^{4}q-5062720499901L^{4}-135002940000L^{3}-135000980\mathrm{O}L^{2}-6000000L-10000>0)\vee$$(250\mathrm{O}L^{4}\mathrm{q} - 5062720499901L^{4}+ 1350029400001^{3}-1350009800L^{2}+6000000L -10000>0)$This is illustrated as a shaded region in Fig.l.

58
if $lvI_{2}=300$ ,for the requirement (c), the problem is recast as the) A $(\exists z>300, \mathcal{R}(z;q, L)=0)$ . A formula
following first-order formula: (Vz $>500$ ,$(L,q)$
describing feasible regions offor the requirement (c) can be obtained by superposing above two
results for (a) and (b) in the parameter space $L-q$ as shown 1n Fig.3.
Control theoretical significance : Any system with parameter values of and within the feasible
regions shown in Figs. 1, 2 and 3 meets the above requirements in terms of the magnitude of SORPRP.
We can obtain the following knowledge from Fig. 3. The plant parameter is restricted within an interval
for a fixed value of under the specification of $300<W<500$ . The maximum and minimum edges ofthe feasible interval of are monotonically increasing. Thus, for instance for the value of around 0.01,
must be taken from the region which is larger than a certain value. We can obtain the exact thresholdvalue easily since we have the feasible region as a semi-algebraic set by virtue of quantifier elimination.
These greatly help control designers to choose appropriate value of the ratio of weights $q/r$ for theircontrol system more systematically.
(c)$lVI_{\mathit{2}}$$<W<il/f_{l}$ :$\mathit{1}\mathrm{V}I_{1}=500$$\mathcal{R}(z\cdot q\}’ L)\neq 0$

$L$

$q$

$L$

$q$

$L$

$L$

$q$

5

Conclusion

In this paper we have presented a method to compute or estimate the sum of roots with positive
real parts (SORPRP) of a polynomial with parametric coefficients based on symbolic and algebraic
computations. Since the method does not compute explicit num ericat values of the roots, we can treat
polynom ials with parametric coefficients for their SORPRP.
Combining the method with quantifier elimination, we succeeded in giving a novel systematic method
for achieving optimal regulator design in control. In order to see its effectiveness and practicality, we
made some experiments for a concrete example from optimal regulator control.
The method proposed here shall provide one of promising direction for an ad hoc part (i.e., choiceof weights) of optimal regulator design that is one of the main concerns in control and gives anothersuccessful application of computer algebra to control design problem.

References[1] H. Anai and S. Hara. Fixed-structure robust controller synthesis based on sign definite condition
by a special quantifier elimination. In Proceedings of American Control Conference 2000, pages
1312-1316, 2000.
[2] H. Anai and S. Hara. Linear programming approach to robust controller design by a quantifier
elim ination. In Proceedings of SICE Annual Conference 2002 (Osaka, Japan), pages 863-869 2002.

[3] H. Anai, H. Yanami, K. Sakabe, and S. Hara. Fixed-structure robust controller synthesis basedon symbolic-numeric computation: design algorithms with a CACSD toolbox (invited paper). In
Proceedings of $CCA/ISIC/CACSD$ 2004 (Taipei, Taiwan), pages 1540-1545, 2004.
[4] H. Anai and H. Yanami. SyNRAC: A maple-package for solving real algebraic constraints. In Proceedings of International Workshop on Computer Algebra Systems and their Applications (CASA)
2003 (Saint Petersburg, Russian Federation), P.M.A. Sloot et al. (Eds.): IOCS 2003, LNCS 2657,
pages 828-837. Springer, 2003

57
[5] P. Aubry and A. Valibouze. Using galois ideals for computing relative resolvents. Journal oj. Symbolic
Computation, 30:635-651, 2000.
[6] B. Caviness and J. Johnson, editors. Quantifier Elimination and Cylindrical Algebraic Decomposition.
Texts and Monographs in Symbolic Computation. Springer, Berlin, Heidelberg, New York, 1998.
[7] D. Cox, J. Little, and D. O’Shea. Ideals, Varieties and Algorithms. Undergraduate Texts in Mathematics. Springer-Verlag, New York, Berlin, Heidelberg, 1992.
[8] D. Cox, J. Little, and D. O’Shea. Using Algebraic Geometry. Graduate Texts in Mathematics 185.
Springer-Verlag, New York, Berlin, Heidelberg, 1998.
[9] P. Dorato, W. Yang, and C. Abdallah. Robust multi-objective feedback design by quantifier elimination. J. Symb. Comp. 24, pages 153-159, 1997.

[10] L. Gonz\’alez-Vega. A combinatorial algorithm solving some quantifier elimination problems. In B.F.
Caviness and J.R. Johnson, editors, Quantifier Elimination and Cylindrical Algebraic Decomposition,
Texts and Monographs in Symbolic Computation, pages 365-375. Springer, Wien, New York, 1998.
[11] L. Gonz\’alez-Vega, T. Recio, H. Lombardi, and M.-F. Roy. Sturm-habicht sequences determinants
and real roots of univariate polynomials. In B.F. Caviness and J.R. Johnson, editors, Quantifier
Elimination and Cylindrical Algebraic Decomposition, Texts and Monographs in Symbolic Computation, pages 300-316. Springer, Wien, New York, 1998.

control system design by a parameter space approach. In[12] S. Hara, T. Kimura, and R. Kondo.
Proceedings of MTNS-91, pages 287-292, Kobe, Japan, 1991.
$\mathrm{H}_{\infty}$[13] M. Jirstrand. Nonlinear control system design by quantifier elimination. Journal of Symbolic Computation, 24(2):137-152, August 1997. Applications of quantifier elimination (Albuquerque, NM,
1995).

[14] T. Kimura and S. Hara. A robust control system design by a parameter space approach based onsign definition condition. In Proceedings of KACC-91 pages 1533-1538, Soul, Korea, 1991.
[$15^{\tau}\rfloor$

B. Mishra. Algorithmic Algebra. Springer Verlag, 1993.

[16] T. Takagi. Lecture of Algebra (cDaisugaku Kougi’ in Japanese ). Kyoritsu Pub. Japan, 1930.

[17] H. Yanami and H. Anai. Development of synrac formula description and new functions. In
Proceedings of International Workshop on Computer Algebra Systems and their Applications ( CASA )2004 : ICCS 2004, LNCS 3039, pages 286-294. Springer, 2004.
–[18]$\mathrm{K}$Zhou, J.C Doyle, and K. Glover. Robust and Optimal Control Prentice Hall, 1995