Re: Root condition for polynomials

In article <1125378334.872722.51600@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
temper3243@xxxxxxxxx wrote:

> http://groups.google.com/group/sci.math.num-analysis/browse_thread/thread/d2b5
> 4d8a4d11f45f/98d955f9feef7a7f?tvc=2&q=Root+condition+for+polynomials#98d955f9f
> eef7a7f
>
> In the thread one of the authors give conditions
> Polynomial is p = a0 x^4 + a1 x^3 + a2 x^2 + a3 x^1 + a4
>
> 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
>
> How do you derive such a formula for quintic ?

Apply the Routh-Hurwitz Criterion to a quintic and then use the mapping
in the above thread to transform to the interior of the unit circle.

> I am not sure if this formula works for all polynomials of degree n
> where n <=4.
> ( i tried applying the criterion for quadratic and it failed with a0 =
> 0 and a1=0).
> Can someone give me similar formula for 3rd degree and 2nd degree.
> How do i derive them ? If it can be done on mathematica what are the
> commands ?

Refer to the original thread. All the code is there, except that the
code for the Routh-Hurwitz Criterion is restricted to degree 4. Here is
code that works for arbitrary degree:

Delta[k_, n_][a_List] := Det[Table[
SparseArray[{{i_, j_} /; n >= 2 i - j >= 0 :> a[[2 i - j + 1]]},
{k, k}]]]

RouthHurwitzCriterion[poly_, z_] :=
Module[{a = Reverse[CoefficientList[poly, z]],
n = Exponent[poly, z]},
Reduce[Join[{First[a] > 0}, Table[Delta[i, n][a] > 0, {i, n}]]]]

This criterion solves the classical stability problem of finding if the
roots are all inside L = {z: Re[z]<0}. The mapping

f[z_] = (2z + 1)/(2z - 1);

transforms to the interior of the unit circle, leading to the following:

CircleCriterion[poly_, x_] := RouthHurwitzCriterion[poly, x] /.
Thread[Reverse[CoefficientList[poly, x]] -> Reverse[CoefficientList[
Numerator[Together[poly /. x -> f[x]]], x]]]

The general degree n polynomial (with leading coefficient unity) can be
written

P[n_][z_] := z^n + Sum[b[n - i] z^i, {i, 0, n-1}]

So, for example, here are the resulting conditions for n = 2:

CircleCriterion[P[2][z], z] // Simplify

b[2] < 1 && b[1] < b[2] + 1

See also,

Tóth, J.; Szili, L.; Zachár, A.: Stability of polynomials, Mathematica
in Education and Research 7 (2) (1998), 5-12.

This paper, as a Zipped Mathematica notebook, is available at

http://www.math.bme.hu/~jtoth/pubtexts/stabpoly.zip

There is another approach that may be useful to you: for real
coefficients, the roots are real or come in complex-conjugate pairs. The
most general 4-th order polynomial with complex roots can be written in
factored form as

c[z_] = (z-r E^(I t))(z-r E^(-I t))(z-s E^(I u))(z-s E^(-I u));

where 0 <= s < 1 and 0 <= t < 1 (to be inside the unit circle),
0 <= t < Pi and 0 <= u < Pi. Equating this to P[4][z], we can solve for
the coefficients as follows:

Solve[P[4][z]-c[z]+O[z]^5 == 0, Table[b[i], {i,1,4}]] // FullSimplify

obtaining

{{b[1] -> -2 (r Cos[t] + s Cos[u]),
b[2] -> r^2 + 4 s Cos[t] Cos[u] r + s^2,
b[3] -> -2 r s (s Cos[t] + r Cos[u]),
b[4] -> r^2 s^2}}

This is a _parametric_ description of the coefficients, subject to the
constraints, 0 <= s < 1, 0 <= t < 1, 0 <= t < Pi, 0 <= u < Pi. Clearly,
this is simpler than the _explicit_ conditions given above.

It is easy to extend this to polynomials of arbitrary degree. And using
this approach one can easily generate random polynomials whose roots all
lie in the unit circle.

Cheers,
Paul

_______________________________________________________________________
Paul Abbott Phone: 61 8 6488 2734
School of Physics, M013 Fax: +61 8 6488 1014
The University of Western Australia (CRICOS Provider No 00126G)
AUSTRALIA http://physics.uwa.edu.au/~paul
.

Relevant Pages

  • Re: Coefficients of the Cyclotomic Polynomials
    ... Say we offset the roots of the unit circle by a complex number ... I know that for a0 and b=0 the coefficients are polynomials built by ... Defining the coefficients of the degree 5 polynomial using Pascal's ...
    (sci.math)
  • Re: factorization of multivariate polynomials
    ... the case of univariate factorization, why arent the zeroes of the polynomial ... Sure -- if it's a polynomial with small integer coefficients and low degree. ... complicated to consider all partitions of the roots looking for rational ... discriminant=0 variety there are subvarieties corresponding to polynomials ...
    (sci.math.symbolic)
  • Re: Some math, algebraic integers
    ... >> be related to the coefficients of their irreducible polynomials. ... > Roots of polynomials are not related to each other. ... There is a remarkable analogy with quantum mechanics. ...
    (sci.math)
  • Re: ALGABRIC SOLUTION
    ... satisfies a quartic vpoly4 over Q) ... We express the seven roots ... # Using Qallows many intermediate polynomials to ... # have rational coefficients rather then coefficients in Q ...
    (sci.math.symbolic)
  • Coefficients of the Cyclotomic Polynomials
    ... Say we offset the roots of the unit circle by a complex number ... I know that for a0 and b=0 the coefficients are polynomials built by ... Defining the coefficients of the degree 5 polynomial using Pascal's ...
    (sci.math)