Bounds for Polynomial’s Roots from Hessenberg Matrices and Gershgorin’s Disks ()
1. Introduction
The estimation of complex roots of a polynomial is a long standing classical problem. A convenient way to obtain information on the location of the zeros of a polynomial is by locating the eigenvalues of its companion matrix. A well-known and easy tool to obtain such information is that of the Gershgorin disks, centered at the diagonal elements of the matrix, however, the classical form of the Gershgorin’s theorem doesn’t take into account the structure of the matrix [1].
This is why some methods, such as the modified disks of Gershgorin, through some geometrical figures called Ovals of Cassini, prospect estimation of bounds by looking in details of the elements in the matrix.
We first present Frobenius companion matrices and some important properties such as Frobenius decomposition’s theorem. Secondly, we will introduce Fiedler matrices and the Gershgorin’s theorem in its general form. We introduce classical bounds for roots like Cauchy’s bounds, Montel’s bounds, Dehmer’s bounds and Carmichel-Mason’ bounds, which are going to be used for comparisons. Some applications to classical companion matrices are presented to estimate bounds for roots of polynomials. We introduce furthermore, bounds for roots with Hessenbeg matrices. We have seen that, the Hessenbeg matrix form is appropriated to estimate good bounds for roots of polynomials as far as it gives improved bounds for high values of polynomial’s coefficients. But it is more indicated for estimation of bounds for small values of coefficients for a given polynomial [2].
Indeed, as principal issue of this work, we present some studies on polynomials in case of very small values of polynomial’s coefficients when
.
In the third part, through illustrative examples, we make a comparison of classical bounds to those obtained with the special hessenberg matrix form in order to compare the pertinence of the studied property. We can see that, the used classical methods always provide bounds higher than 1.
2. Generalities on Frobenius Companion Matrices Gershgorin’s Theorem
2.1. Forms of the Frobenius Companion Matrices
Let
be a polynomial:
(
, because when
, then we have an evident root which is 0, we exclude this case, to studie non obvious cases).
Let
be a matrix:
(1)
Let
be, the characteristic polynomial of the matrix
,
is the identity matrix of degree n. The characteristic polynomial
of the matrix
coincides with
:
With the help of the expansion with respect to the first column it is easy to verify by induction that:
.
The given
matrix
is called “Frobenius matrix” or the “standard Frobenius companion matrix of the polynomial
”.
Definition 1. [3]
We define a “companion matrix” to be an
matrix A over
with
entries constant in
and the remaining entries
such that the characteristic polynomial of A is
. We say that two companion matrices A and B are equivalent if either A or AT can be obtained from B via a permutation similarity.
There are many other Frobenius companion matrices. In this paper, we notice:
is the classical Frobenius companion matrix associated to the polynomial
:
(2)
is the first Frobenius companion matrix associated to the polynomial
:
(3)
is the second Frobenius companion matrix associated to the polynomial
:
(4)
Companion matrices have a great interest in that they offer the possibility of elegant demonstrations.
2.2. Statement of the Gershgorin’s Theorem
A common way to obtain inclusion areas for the zeros of a polynomial is to find eigenvalue inclusion areas for a companion matrix of the polynomial, whose eigenvalues are precisely the zeros of the polynomial.
In this section, it is about locating zeros of polynomials from the Gershgorin’s disks. These disks are estimated by using the diagonal elements of the matrix. The radii are then calculated from the polynomial’s coefficients. Gershgorin’s theorem states that the union of these disks contains all eigenvalues.
We formally state here Gershgorin’s theorem as lemma and its application to companion matrices.
Lemma 1. For a given matrix A of dimension
with complex elements
, all the eigenvalues are located in the union of the following n disks so that: [1].
Considering the rows:
(5)
Considering the columns:
(6)
Proof. Let
be an eigenvalue of a complex
matrix A and whose corresponding eigenvectors are x.
So we have
.
If x is an eigenvector, it has at least one of its components that is non-zero. Let
be the component of x having the greatest absolute value, such that
for all
and
.
As
, we have:
,
hence
.
We will take the absolute value on either side of the equality and use the triangular inequality while dividing by
.
Since
for every
, we become:
is then located in the disk
.
Without knowing the eigenvectors, we do not know to which k each eigenvalue corresponds. We must therefore take the union of all these disks to obtain a region which guarantees to contain all the eigenvalues in a safe way.
2.3. Application to Classical Companion Matrices
The proof of the theorem doesn’t take into account any particular property of the matrix A. It can be then interesting to consider some properties of matrices and to study the advantages related to these particularities.
Since our study concerns Fiedler companion matrices, we will first consider the particular properties of companion matrices by using explicit forms.
We consider the classical companion matrix
:
(7)
It is already known that the eigenvalues of the matrix
are roots of its characteristic polynomial
:
,
.
Gershgorin’s theorem applies to the matrix
guarantees that all the zeros of the polynomial
belong to
which is the union of n disks such as:
.
where:
Let
be a zero of the polynomial
.
The inequalities allow us to say that for any zero
of
, we have:
(8)
The obtained bound is better than the bound of Cauchy namely:
Example 1:
Let
be a complex polynomial.
By applying Gershgorin’s theorem, we have:
So
.
Then, all the zeros of the polynomial
are therefore included in the disk:
.
3. Modified Disks of Gershgorin
3.1. Improved Bounds for Roots of Polynomials by Modifying the Disks of Gershgorin for Companion Matrices
The general form of the Gershgorin’s theorem doesn’t exploit the specific structure of the matrix. By rewriting the equations from which we obtain the Gershgorin’s disks and by exploiting them, we can obtain improved forms of those disks. More generally, we consider x and
respectively eigenvalue and eigenvector of the companion matrix
, we have:
.
From this equality follows the equations:
This set of equations is used to modify the
disks of Gershgorin in order to obtain
which allows to obtain an improvement of the bounds of the roots for polynomials. For this, we first make changes on
to
and then
to
respectively. Each step produces a new set of zero inclusions that are summarized in the following theorem [1].
Theorem 2. Let
,
, be a polynomial
. All the zeros
of
can be found in the set
where:
We then have:
where
.
Likewise, all the zeros
of
can be found in the set
where:
We also then have:
where
.
Proof. In order to change respectively
to
and then
to
, some steps are required. Each step allows to calculate a bound on the moduli of the zeros for the obtained modified set.
First modified disk
We consider the vector x to be the eigenvector with the greatest absolute value. About this modification, we start from the equation
. We eliminate
in the equation
.
It gives:
. So if
has the greatest coefficient’s absolute value of the eigenvector x, we obtain
in addition to the inequality.
We obtain another inequality that must be satisfied by
precisely
.
We then define:
.
.
The limit of
is a quartic curve known as the oval of Cassini. It consists of either one or two loops. Ovals of Cassini also appear in a different and slightly more complicated eigenvalue inclusion set. We can therefore choose to replace
by
in Gershgorin’s theorem.
Since
, we clearly have
. The new obtained set of inclusions is smaller than
. We can expect this to happen when
is large enough for
to dominate
.
By changing
to
, from
, we then get:
Let
, so that
. It follows that from equation 8 we can conclude that:
.
Hence the first part of the theorem.
Second modified disk
In the same way, we use the equation
. We eliminate
in the equation
. Then, we use it to replace
by
in the equation
.
It gives
.
Since
for every j, then we have
.
When we divide by
, it gives
.
This helps to define a new set
and
.
However, since we have
for every j, we have from
that
. It is a disk centered at the origin with radius
.
We conclude that, in this case,
. We define a set
so that
. Similarly to the set
, from the equality
, we can deduce that:
where
and
.
The theorem is proved.
From this theorem, we consider estimated values of the litteratur for our illustrative examples.
3.2. Improved Bound from the Hessenberg Matrices and Classical Usal Bounds of Roots for Polynomials
We announce the following theorem as principal result of this work. The first part of the theorem was already part of former issued paper [2]. The originality of the theorem comes from the fact that, by using the Hessenberg form, in the special case that
, we can automatically deduce a general constant bound for this kind of polynomials.
Theorem 3. (Hessenberg [2], [4] ).
Let
,
, be a polynomial
. Any zero
of
satisfies the relation:
where
,
if
.
When:
then
.
Proof. The estimation of the general bound for
can be found in [2].
What to be proved is the case:
then
?
In this case, since
, from the first part of the theorem, we have for the matrix
:
.
It follows that:
.
We introduce the following theorem as a specific case of the modified disks of Gershgorin in which
and
are computed. It will be followed by other theorems of the litteratur that will be used for comparison to estimate bounds for roots of some given polynomials.
Theorem 4. (Ovals of Cassini [1] ).
Let
,
, be a polynomial
. Any zero
of
satisfies the relation
where:
(9)
Proof. The Equation (9) comes from the theorem 2. Values of
and
have been taken from [1] for our illustrative examples.
Theorem 5. (Dehmer [5] ).
Let
,
, be a polynomial
. Any zero
of
satisfies the relation:
Proof. This bound is the usual bound found in the litteratur as Dehmer bound. It can be found in [5].
Theorem 6. (Cauchy, Montel and Carmichel-Mason [6] ).
Let
,
, be a polynomial
. Any zero
of
satisfies the relation:
• Cauchy’s bound:
• Montel’s bound:
• Carmichel-Mason’s bound:
Proof. Cauchy’s bound, Montel’s bound and Carmichel-Mason’s bound are classical bounds that are usually found in the litteratur. We do not prove them in this paper [6].
3.3. Illustrative Examples for Polynomials by Degree n = 5
In this section we will take some examples to illustrate the sharpness of the theorems on modified disks of Gershgorin for companion matrices. We will make a particular study on polynomial for degree
by using following bounds: Ovals of Cassini, Hessenberg, Dehmer, Cauchy, Montel and Carmichel-Mason. All the bounds that are going to be used are listed in Figure 1. Illustrative examples have been given in this section.
Example 2. Let
. We have:
.
The roots and their bounds of polynomial
are illustrated in Table 1 and Table 2.
Example 3. Soit
. The roots and their bounds of the polynomial
are illustrated in Table 3 and Table 4.
Example 4. Soit
. The roots and their bounds of polynomial
are illustrated in Table 5 and Table 6.
Table 1. Bounds for roots of polynomial
.
Table 2. Roots of
computed with Scilab.
Table 3. Summary of the bounds of the polynomial
.
Table 4. Estimation of the bounds of the zeros of
(Traces matrices of Graeffe [7] ).
Figure 1. Summary of bounds for roots by degree
.
Table 5. Summary of the bounds of the polynomial for
.
Table 6. Estimation of the bounds of the zeros of
(Traces Matrices of Graeffe [7] ).
We can see that the sparse companion matrices become interesting for use, in case of small values of the coefficients of polynomials. This is why we make a closer look at these cases.
Example 5. Let
.
if
, then
,
and
.
The roots and their bounds of the polynomial
are illustrated in Table 7 and Table 8.
Example 6. Let
.
We have:
.
The roots and their bounds of the polynomial
are illustrate in Table 9 and Table 10.
Table 7. Summary of the bounds of the polynomial for
.
Table 8. Roots of polynomial
computed with Scilab.
Table 9. Summary of the bounds of the polynomial for
.
Table 10. Roots of polynomial
computed with Scilab.
4. Conclusions
We have studied several methods of estimating bounds for zeros of a polynomial. We first present different matrices that are used in this paper. We begin by presenting companion matrices and cyclic matrices in order to introduce Frobenius companion matrices and Frobenius decomposition’s theorem of matrices into diagonal block of companion matriices. We also present Fiedler matrices and then we introduce the Gershgorin’s theorem. As the standard Gershgorin’s theorem doesn’t exploit the specific structure of the matrix, we apply it to a Frobenius companion matrix, that is also a Fiedler matrix after modifying the first and the second Gershgorin disks. The obtained new union of disks after the modification, called ovals of Cassini, allows us to estimate news expression of bounds for roots for a given polynomials [1].
Furthermore, the classical bounds resulting from the application of Gershgorin’s theorem like Cauchy’s bounds, Montel’s bounds and Carmichel-Mason’s bounds are presented.
Otherwise explicit expressions of bounds of the zeros of the polynomials have been presented by using Hessenberg matrices for the
-norm. The estimation of bound in the Hessenberg form is made through the estimation of the variable
. We have already found in precedent studies that the more the coefficents are closed to zeros with a norm lower than 1, the more the approach by the Hessenberg matrices is indicated. This justifies why we study forms of polynomials in special cases of polynomial’s coefficients when
. In this cases, the roots of the polynomials satisfy automatically the relation
. All the forms of the bounds have been listed in a table in order to start a comparison through manual computation.
As experimental part of this paper, we take many illustrative examples of polynomials for degrees
, in order to compare our obtained bounds to absolute values of the exact roots. Bounds for the roots from our improved methods of the given polynomials have been manually computed. The exact roots have been computed with the software SCILAB and the Traces matrices of Graeffe [7] and then compared to our computed bounds. From our examples, we confirm that none of the classical methods gives alone the best value for both small values and high values of the polynomial’s coefficients. Some methods are indicated for small values while others are indicated for high values of these coefficients. But the Hessenberg method makes it possible to obtain good estimation of the bounds especially for small values of the coefficients. The Dehmer’s bound belongs also to the best in cases of some high value of polynomial’s coefficients. In all the cases, we note that no method makes it possible to estimate a bound which is lower than 1. However, in the case when
, we need to be able to estimate bounds strictly less than 1 since the absolute values of the roots are less than 1. Hence a study on polynomials to find special formula that gives a bound less than 1 is indicated. As future research topic, it will be interesting to find forms of matrices and methods that can provide bounds strictly less than 1 for a polynomials if there is any.