Finding Roots of Polynomials by the Routh Array

Comparisons with other Methods

Existing Root Finding Methods  |  Bairstow's Method  |  Examples  |  Conclusions

EXISTING ROOT FINDING METHODS

Some of the more popular methods for finding roots of polynomials include the Newton-Raphson method, Muller’s method, Lin’s method, Bairstow’s method, the Secant method and the Bisection method [2]. Lin and Bairstow’s methods have proved to be the more popular techniques in control engineering since these methods extract complex conjugate root pairs quite easily which is of great importance in that field. The Secant and Bisection methods are generally ineffective when it comes to finding complex conjugate root pairs, while the Newton-Raphson method and Muller’s method use complex arithmetic which is awkward when using hand calculation but possible in a computer program.

BAIRSTOW’S METHOD

Bairstow’s method [2] is one of the most popular and efficient root finding algorithms for polynomials. The method proves to be very good for extracting complex conjugate root pairs from real polynomials, and its quadratic convergence rate is also favourable compared to other methods.

The method works by finding quadratic factors associated with complex conjugate root pairs. This is why the technique has proved to be very popular with control engineers. A quick overview of how the method works now follows.

Consider the polynomial

F(s) = ansn + an-1sn-1 + ... + a1s + a0    (5.2.1)

If the polynomial (5.2.1) has a known quadratic factor

s2 - us - v

then equation (5.2.1) can be written as

F(s) = (s2 - us - v)g(s) + h(s)    (5.2.2)

This means that if (s2-us-v) is an exact divisor of F(s) then the remainder term, h(s), will vanish. The quotient, g(s), and the remainder polynomials

g(s) = bnsn-2 + bn-1sn-3 + ... + b3s + b2    (5.2.3)
h(s) = b1(s - u) + b0

are calculated using the recursive definition

bk = ak + ubk+1 + vbk+2        k = 0,1,...,n
bn+1 = bn+2 = 0   nbsp;         (5.2.4)

So using the above definition it can be seen that b0 and b1 are both functions of u and v, and so for the remainder to vanish the following two equations must be true:

b0(u,v) = 0
b1(u,v) = 0

Bairstow’s method solves this pair of simultaneous non-linear equations by Newtons method, where the partial derivatives

are obtained using the recurrence relation

ck = bk+1 + uck+1 + vck+2      cn+1 = cn = 0      k = 0,1,...,n
dk = bk+1 + udk+1 + vdk+2      dn+1 = dn = 0                 (5.2.5)

Both of the above definitions are the same, so only the first one is needed.

The process is to then assign starting values to u and v, and to then seek corrections, denoted by du and dv, so that

bo(u + du,v + dv) = b1(u + du,v + dv) = 0    (5.2.6)

These equations are then linearised so that

This system then becomes

{where ci are the above partial derivatives)

which has the solution

du = (c1b1 - c2b0) / J
dv = (c1b0 - c0b1) / J     (5.2.7)

where J = c0c2 - c1c1

J is the Jacobian determinant for the pair of non-linear functions b0(u,v) and b1(u,v).

The above equations are then used to successively re-evaluate the values for u and v, by adding on some correction values, du and dv calculated using equation (5.2.7), until equation (5.2.6) is satisfied, and hence the required quadratic factor is found. The method is perhaps best seen in an example

Example 5.2.1 Consider the polynomial

F(s) = s4 - 1.1s3 + 2.3s2 + 0.5s + 3.3

Then using initial values of u=-1 and v=-1 (for a quadratic factor of (s2+s+1)), equation (5.2.4) gives

b4=1    b3=-2.1    b2=3.4 b1=-0.8    b0=0.7

and then using these values in equation (5.2.5) gives

c4=0    c3=1    c2=-3.1    c1=5.5    c0=-3.2

These values are then substituted into equation (5.2.7) to give the correction figures as

du = 0.11 and dv = -0.06

This then gives the new values for u and v as

u = -1 + 0.11 = -0.89 and v = -1 - -0.06 = -1.06

This gives a new trial quadratic factor of (s2+0.89s+1.06).

A second trial then yields the following values

b4=1    b3=-1.99    b2=-3.01    b1=-0.07    b0=0.17
c4=0    c3=1    c2=-2.08    c1=4.51    c0=-1.03
du=-0.010    dv=-0.040

so that the new values for u and v are given by

u = -0.89 -0.010 = -0.900
v = -1.06 -0.040 = -1.100

These new values of u and v satisfy equation (5.2.6) and so a quadratic factor has been found as (s2+0.9s+1.1). The other quadratic factor may be found by dividing the original polynomial through by the quadratic factor. When this is done, the original polynomial is factorised as

F(s) = (s2 + 0.9s + 1.1)(s2 - 2s + 3)

The above example shows how Bairstow’s method may be used for finding quadratic factors of polynomials. The example shows how relatively straight forward the method is to use, and also how well it copes with finding complex conjugate root pairs, as well as real root pairs.

EXAMPLES

Turnbull [7] in his Ph.D. thesis used Bairstow’s method in the analysis of vowel sound recognition. Some typical polynomials are taken from this source, and were used for the Routh array method.

Due to properties of these polynomials, it is known that all the roots lie in a radius of unity about the origin of the s-plane. This means that when the polynomials are tested in the computer program, real part bounds would be established straight away between s=-1 and s=1. Thus, the convergence rates may be compared for each method after all the roots of the polynomials are found.

Example 5.3.1

The first polynomial to be considered is

F(s) = s8 - 1.569s7 + 0.671s6 - 0.444s5 + 0.464s4 - 0.514s3 + 0.185s2 + 0.761s - 0.533

Table 5.3.1.1 below summarises the results which were obtained applying Bairstow’s method to the above polynomial. The table shows the values for u and v, which make up the quadratic factor (s2-us-v), the associated roots and also the number of iterations which were required to come to those values.

Table 5.3.1.1 Table for Bairstow’s iteration

u

v

Root pair (s)

F(s)

Iterations

1.931

-0.953

0.9655± 0.144255i

-0.0005+|0.0095|i

13

0.084

0.652

-0.766556, 0.850556

0.0010, -0.0003

9

0.668

-0.920

0.334± 0.899135i

-0.0005+|0.0013|i

16

-1.115

-0.932

-0.5775± 0.788158i

0.0012+|0.0025|i

0

The above table shows how Bairstow’s technique found all eight roots of the polynomial after 38 iterations.

When the above polynomial is tested using the Routh array method, with the secant method built in, the number of iterations which were required to find all of the roots is lower. Table 5.3.1.2 below shows the number of iterations that was required to find the roots.

Table 5.3.1.2 Table for Routh array iteration

Root pair (s)

F(s)

Iterations

-0.776584, 0.850833

0.0692, -0.0002

6

-0.965748± 0.141695i

-0.0003+|0.0001|i

8

0.334024± 0.899567i

0.0005+|0.0005|i

6

-0.557396± 0.788376i

0.0002+|0.0001|i

0

This shows that the Routh array method found all the roots after only 20 iterations, which is quite a difference from the 38 with Bairstow’s method. This example may be quite misleading, because overall it may be that for certain polynomials Bairstow’s method may converge a bit quicker than that of the Routh array method. The only other difference in the two methods for this example, is that the pair of real roots were extracted first.

Example 5.3.2

The second polynomial considered was

F(s) = s8 - 1.746s7 + 0.402s6 + 0.049s5 + 1.2134 - 0.839s3 - 0.152s2 - 0.132s + 0.239

Again, Bairstow’s method gives the results in table 5.3.2.1.

Table 5.3.2.1 Table for Bairstow’s iteration

u

v

Root pair (s)

F(s)

Iterations

1.846

-0.871

0.92325± 0.136416i

0.0001+|0.0001|i

7

1.721

-0.952

0.8605± 0.459934i

0.0001+|0.0001|i

7

-0.818

-0.489

-0.409± 0.567202i

-0.0003+|0.0001|i

15

-1.003

-0.590

-0.5015± 0.581805i

0.0003+|0.0003|i

0

This shows that overall, Bairstow’s method converged after a total of 29 iterations. The accuracy of the roots is also very good. When the polynomial is used in the Routh array method with the secant method running, the following results in table 5.3.2.2 were obtained.

Table 5.3.2.2 Table for Routh array iteration

Root pair (s)

F(s)

Iterations

0.923360± 0.136907i

-0.0001+|0.0001|i

7

0.860379± 0.459951i

-0.0001+|0.0001|i

6

-0.500000± 0.582762i

0.0006+|0.0012|i

2

-0.410739± 0.565140i

0.0002+|0.0004|i

0

Again, this polynomial has found all of the roots after a smaller number of iterations. For this example there was a total of only 15 iterations that were needed until all of the roots were found. Even though this example has shown that the Routh array method has converged quicker overall, it does not imply that the Routh array method is better overall. For example, it may be that the root distribution for this example may be better suited to using the Routh array method than Bairstow’s method. Nevertheless, it still shows that if this method is used properly then it can prove to be very powerful, and also quite a quick method, for finding roots of polynomials.

The last two examples have shown the Routh array method to converge quicker than that of Bairstow’s. The next example actually shows that Bairstow’s method can converge marginally quicker than the Routh array method.

Example 5.3.3

This is a degree 8 polynomial with all the roots lying within the unit circle;

F(s) = s8 - 1.806s7 + 1.247s6 - 1.016s5 + 1.425s4 - 1.228s3 + 0.857s2 - 0.898s + 0.489

The roots and the number of iterations using Bairstow’s technique are shown in table 5.3.3.1.

Table 5.3.3.1 Table for Bairstow’s iteration

u

v

Root pair (s)

F(s)

Iterations

1.867

-0.893

0.9335± 0.146893i

0.0010+|0.0011|i

7

-0.218

-0.698

-0.109± 0.828322i

-0.0002+|0.0005|i

15

1.485

-0.919

0.7425± 0.606377i

0.0005+|0.0018|i

6

-1.327

-0.853

-0.6635± 0.642470i

-0.0007+|0.0006|i

0

For this example, Bairstow’s method found all eight roots after a total of 28 iterations. The results when testing this polynomial using the Routh array method are given below in table 5.3.3.2.

Table 5.3.2.2 Table for Routh array iteration

Root pair (s)

F(s)

Iterations

0.742284± 0.606883i

-0.0002+|0.0013|i

15

0.932567± 0.147877i

0.0008+|0.0003|i

7

-0.108807± 0.827776i

0.0014+|0.0010|i

7

-0.663044± 0.642619i

0.0003+|0.0002|i

0

This time, the Routh array method found all the roots after a total of 29 iterations. This is only slightly smaller than that gained from Bairstow’s method but it would seem to indicate that in certain cases, Bairstow’s method will work faster.

CONCLUSIONS

What this chapter has shown is that the Routh array method is a potentially powerful way of finding roots of polynomials, rivalling methods such as Bairstow’s method. Some examples were studied to compare how well the Routh array method coped with certain polynomials, comparing results that had previously been obtained.

From this evidence it is seen that the Routh array method copes very well with difficuilt polynomials. The convergence rate, which is an important part of any method, also proved to be very good. This appears to be due to the "secant-type" procedure mentioned in chapter 4, being a big improvement over the "bisection" procedure used by Lucas [5].

Further, a big advantage of the Routh method over methods such as Bairstow’s and Lin’s is that it guarantees convergence once real part bounds are found. This property makes the method attractive to use.

Chapter 4 - Examples Using the Routh Array Method  |  Chapter 6- Conclusions

Routh  | Home