From: Robin Becker Subject: Re: Question : Root condition for polynomials Date: Mon, 1 Feb 1999 14:24:51 +0000 Newsgroups: sci.math.num-analysis Keywords: Routh-Hurwitz criterion In article <36B2679D.A6AFCA1A@gong.snu.ac.kr>, Chae Dong Suk writes >Hi everyone. > >I have some question regarding to root condition of polynomials. I can't >find the solution as far as my mathematical knowledge is concerned. >Somebody suggests me reference or solution. > >Let's suppose the polynomial of degree less than 5 like > >P(x) = x^4 + a1 x^3 + a2 x^2 + a3 x^1 + a4 > >then what is range of coefficients satisfying the root condition that >the their magnitude are all confined in the unit circle on complex >plane? > >I study this problem for zero-stability of numerical time integration >for ODE. >Thanks in advance. > > this is a well known problem of control theory. For continuous time problems the Hurwitz criterion is used. This gives structural conditions on the coefficients such that re[zero(p(s)]<0; the required conditions for the discrete time case can be determined by transforming the dt poly into continuous time via p(s) := pn s^n + pn-1 s(n-1)+.....p(0) has all zeros in |s|<1 <=> q(s) := (1-s)^n * p[(1+s)/(1-s)] has all zeros in Re[s] < 0 R Brocket gives references to this and the Lienard-Chipart criterion. -- Robin Becker ============================================================================== From: spellucci@mathematik.tu-darmstadt.de (Peter Spellucci) Subject: Re: Question : Root condition for polynomials Date: 1 Feb 1999 11:29:56 GMT Newsgroups: sci.math.num-analysis In article <36B2679D.A6AFCA1A@gong.snu.ac.kr>, Chae Dong Suk writes: |> Hi everyone. |> |> I have some question regarding to root condition of polynomials. I can't |> find the solution as far as my mathematical knowledge is concerned. |> Somebody suggests me reference or solution. |> |> Let's suppose the polynomial of degree less than 5 like |> |> P(x) = x^4 + a1 x^3 + a2 x^2 + a3 x^1 + a4 |> |> then what is range of coefficients satisfying the root condition that |> the their magnitude are all confined in the unit circle on complex |> plane? the problem is not that simple. you also must assure that roots on the boundary are simple. but, for a polynomial of degree four, it is possible to express all roots in terms of 2nd, 3rd and 4th roots of polynomials formed from the coefficients. then write down the absolute values of the roots ,set this <=1 and you are done. but the outcome will not be "ranges" since the formulae itself depend on the actual values of the coefficients (think about the simple case of degree 2), you will obtain a very complicated set of conditions finally. hope this helps peter ============================================================================== From: rusin@vesuvius.math.niu.edu (Dave Rusin) Subject: Re: Question : Root condition for polynomials Date: 1 Feb 1999 22:58:54 GMT Newsgroups: sci.math.num-analysis Chae Dong Suk wrote: >I have some question regarding to root condition of polynomials. I can't >find the solution as far as my mathematical knowledge is concerned. >Somebody suggests me reference or solution. > >Let's suppose the polynomial of degree less than 5 like > >P(x) = x^4 + a1 x^3 + a2 x^2 + a3 x^1 + a4 > >then what is range of coefficients satisfying the root condition that >the their magnitude are all confined in the unit circle on complex >plane? > >I study this problem for zero-stability of numerical time integration >for ODE. I don't really know the answer but this has come up before; see e.g. 96/roots.ge1 For some reason this doesn't seem to be treated as an algebraic problem, which is unusual since algebraic number theorists have shown a lot of interest in the related (algebraic) numbers which are greater than 1 but all of whose conjugates are at most equal to 1 in magnitude; these are the Salem and Pisot numbers. There is interest in polynomials all of whose roots have magnitude exactly equal to 1, too; these obviously include products of cyclotomic polynomials but there are others. So it's possible that there's more algebraic information about the polynomials you seek (e.g. an easy characterization of the 4-tuples [a1,a2,a3,a4] ) but I haven't seen it. dave Polynomials as analytic functions: index/26CXX.html Polynomials as generators of algebraic extension fields: index/12FXX.html ============================================================================== From: "Allan Hayes" Subject: Re: Question : Root condition for polynomials Date: Tue, 2 Feb 1999 14:36:06 -0000 Newsgroups: sci.math.num-analysis Chae Dong Suk wrote in message <36B2679D.A6AFCA1A@gong.snu.ac.kr>... >Hi everyone. > >I have some question regarding to root condition of polynomials. I can't >find the solution as far as my mathematical knowledge is concerned. >Somebody suggests me reference or solution. > >Let's suppose the polynomial of degree less than 5 like > >P(x) = x^4 + a1 x^3 + a2 x^2 + a3 x^1 + a4 > >then what is range of coefficients satisfying the root condition that >the their magnitude are all confined in the unit circle on complex >plane? > >I study this problem for zero-stability of numerical time integration >for ODE. >Thanks in advance. > > Chae: Convert to classical stability problem of finding if the roots are all inside L = {z: Re[z]<0} as follows (there is an excellent, up-to-date discussion of the general problem in Mathematica in Education and Research Vol 7, No2, Spring, 1998 by Janos Toth, Laszlo Szili and Andras Zachar, that includes the general Mathematica code needed: http://www.telospub.com/journal/MIER/) f[z_] = (2z + 1)/(2z - 1); Is a (1-1) mapping of the extended complex numbers onto themselve with 1/2 -> Infinity and takig L onto the interior of the unit circle, C. So its inverse function invf maps C onto L For any polynomial p[z] the following are equivalent p[z]= 0 => z inside C p[f[z]]=0 => f[z] inside C p[f[z]]=0 => z inside invf[C] (= L) For the polynomial p = a0 x^4 + a1 x^3 + a2 x^2 + a3 x^1 + a4; The Routh-Hurwitz Criterion for all roots to be inside L is RH[{a0_, a1_, a2_, a3_, a4_}] := a0 > 0 && a1 > 0 && Det[{{a1, a0}, {a3, a2}}] > 0 && Det[{{a1, a0, 0}, {a3, a2, a1}, {0, a4, a3}}] > 0 && Det[{{a1, a0, 0, 0}, {a3, a2, a1, a0}, {0, a4, a3, a2}, {0, 0, 0, a4}}] > 0 We can easily define a Mathematica function to produce this for any degree 4 polynomial. RHCriterion[poly_, x_] := RH[Reverse[CoefficientList[poly, x]]]; RHCriteria[p[x], x] \!\(a0 > 0 && a1 > 0 && a1\ a2 - a0\ a3 > 0 && a1\ a2\ a3 - a0\ a3\^2 - a1\^2\ a4 > 0 && a1\ a2\ a3\ a4 - a0\ a3\^2\ a4 - a1\^2\ a4\^2 > 0\) and from this to get the criterion for all the roots being inside the unit circle C. CircleCriterion[poly_, x_] := RHCriterion[poly /. x -> f[x] // Together // Numerator, x] CircleCriterion[p, x] 16*a0 + 16*a1 + 16*a2 + 16*a3 + 16*a4 > 0 && 32*a0 + 16*a1 - 16*a3 - 32*a4 > 0 && 640*a0^2 + 320*a0*a1 + 64*a1^2 - 384*a0*a2 - 64*a1*a2 - 576*a0*a3 + 64*a2*a3 - 64*a3^2 + 576*a1*a4 + 384*a2*a4 - 320*a3*a4 - 640*a4^2 > 0 && 4096*a0^3 - 4096*a0^2*a2 + 4096*a0*a1*a3 - 4096*a0*a3^2 - 4096*a0^2*a4 - 4096*a1^2*a4 + 8192*a0*a2*a4 + 4096*a1*a3*a4 - 4096*a0*a4^2 - 4096*a2*a4^2 + 4096*a4^3 > 0 && (a0 - a1 + a2 - a3 + a4)*(4096*a0^3 - 4096*a0^2*a2 + 4096*a0*a1*a3 - 4096*a0*a3^2 - 4096*a0^2*a4 - 4096*a1^2*a4 + 8192*a0*a2*a4 + 4096*a1*a3*a4 - 4096*a0*a4^2 - 4096*a2*a4^2 + 4096*a4^3) > 0 Lets test this ( we have to use Chop to get rid of small comples numbers produced by multiplying out) poly2 = Times @@ ( x - {-.3, .2 Exp[.5I], .2 Exp[-.5I], .7}) // Expand // Chop; CircleCriterion[poly2, x] True poly3 = Times @@ ( x - {-3, .2 Exp[.5I], .2 Exp[-.5I], .7}) // Expand // Chop; CircleCriterion[poly3, x] False --------------------- Allan Hayes Mathematica Training and Consulting www.haystack.demon.co.uk hay@haystack.demon.co.uk Voice: +44 (0)116 271 4198 Fax: +44 (0)870 164 0565 ============================================================================== From: Andrzej Lewandowski Subject: Re: Question : Root condition for polynomials Date: Tue, 02 Feb 1999 17:32:11 -0500 Newsgroups: sci.math.num-analysis Robin Becker wrote: [see above -- djr] See the classical books on discrete control systems (that time called "impulse control systems") written by E. Jury. Try to find the library that keeps old stuff; these books were published in late 60' - early 70'. A.L.