An Algorithm for Exact Geometric Search of Polynomials Complex Roots

Abstract

A graph of an n-th order polynomial on the real plane allows us to de ne geometrically all the real roots. Number of real roots varies from 0 to n. The rest of the roots are complex and not determined by the graph. In the article, in addition to the graph of the basic polynomial, two auxiliary graphs are constructed, which allow us to represent all complex roots on the same real plane. The application of this method is considered in detail for the solution of a cubic polynomial. In this case the method has exceptional features in comparison with polynomials of other degrees. Taking into account the well-known expressions for the roots of polynomials of order 3 and 4, the auxiliary graphs of the method have exact formulas for polynomials with order n 10.

Keywords

• polynom
• complex roots
• function graph
• exact algorythm

Introduction

Complex numbers were introduced as an auxiliary tool for nding the real roots of polynomials 3 rd and 4 th orders. The basic algebraic theorem proves that the number of complex and real roots is equal to order of the polynomial. The real roots are easy to nd and illustrated on the graph. Complex roots do not possess this property. There are several exact algebraic and iterative numerical methods for nding the roots ([1] |[4]). Precise methods for polynomials with arbitrary coe cients, as is known, exist only for polynomials of order n 4. These are the well-known Cardano (n = 3) and Torriceli (n = 4) formulas.

In this article, the exact geometric method is understood as the use of graphs of functions that have an exact analytical expression, and a one-sided ruler with the ability to draw parallel lines. Along with the graph of the original polynomial f (x), we construct a graph of auxiliary multivalued \conjugate" function fS (x). On this graph, a subset is distinguished, which is called the gluing set and is denoted Sf . Then the second auxiliary multivalued \carrier" function fN (x) is constructed. The domain of de nition of fN (x) coincides with the projection of the gluing set Sf onto the axis Ox. To nd the complex roots of the equation f (x) = , where is an arbitrary real number, we use the same real plane. The Ox axis is associated with the real part of the complex number, and the Oy axis is joined with the imaginary part. Both auxiliary functions fS (x) and fN (x) have an exact analytic notation for n 10. For polynomials of higher degrees, the graphs of the auxiliary functions must be constructed numerically. The algorithm assumes drawing the straight lines. First, we draw a horizontal line with the equation y = and nd the intersection points with the glueing set. Then through each such point, we draw a vertical line and nd the points of intersection with the carrier graph. These last points are complex roots of the equation f (x) = . When the free coe cient changes, the method shows the migration way [8], in which the roots move. We can see how a real root splits into two complex ones, and vice versa, two complex conjugate roots join into one real root. The geometric method for solving the cubic equation is studied in detail in the article. In this case, the method has exceptional features in comparison with polynomials of other degrees, namely, the auxiliary functions are expressed in terms of the original polynomial f (x). It is shown that the conjugate function fS (x) = f ( 2x a1=a0), and the carrier function fN (x) is expressed in terms of the derivative of the original polynomial fN (x) = pf 0(x). Moreover, the conjugate function is a single-valued function, while for other degrees it is multivalued.

The developed method can be used, for example, for an exact geometric representation of the root locus in the study of control systems with feedback, in which there is a parametric block multiplier k. The parameter k plays the role of the free coe cient and the problem is to nd all the poles of the characteristic polynomial of a closed system ([5] |[8]). 2

Basic concepts

De nition 1. Let f (x) be a polynomial of order n with real coe cients. The gluing set of f (x) is called the set Sf of points (x; y) of the real plane R2, for which there are distinct complex mutually conjugate numbers z1 and z2 such that Re z1 = Re z2 = x and f (z1) = f (z2) = y.

The gluing set is the set of intersection points (or gluing) of the four-dimensional graph of the complex function f (z) of the complex variable z ([9]). Lemma 1. Let f (x) be a polynomial of the third order. If the point (a; ) 2 Sf , then the equation f (x) = ( 1 ) has one real and two di erent complex conjugate roots, and the real part of the complex roots is equal to a.

Proof. Since (a; )2Sf , then there exist complex conjugate numbers z1 = a + bi and z2 = a bi such that f (z1) = and f (z2) = .

Therefore, z1, z2 are the complex roots of the equation ( 1 ), so, the third root is real. Lemma 1 is proved.

Lemma 2. Let f (x) = a0x3 + a1x2 + a2x + a3 be a polynomial of the third order with real coe cients, a0 6= 0. Then the gluing set Sf of the polynomial f (x) lies on the graph of the function fs(t), where fs(t) = f ( 2t a1=a0). where

Equation

The function fs(t) is said to be conjugate to the function f (t).

Proof. Obviously, fs(t) is also a polynomial of the third order. Take an arbitrary point (x0; )2Sf and construct the equation ( 1 ). By Lemma 1 , equation ( 1 ) has exactly one real root. Denote this real root z1( ) and nd other two complex roots z2 and z3. Obviously, numbers z2 and z3 are the roots of the polynomial of the second order f (x) x z1 f (x) f (z1)

x z1 = x

z1 = a0(x3 z13) + a1(x2 z12) + a2(x z1) = a0(x2 + xz1 + z12) + a1(x + z1) + a2 = A x2 + B x + C;

A = a0; B = a0z1 + a1; C = a0z12 + a1z1 + a2:

Az2 + Bz + C = 0 has two roots z2;3 = 2BA on z1 and hence on .

Thus, equation ( 1 ) has three roots: one real z1 and two complex conjugated ones p 2AD , where the discriminant D = B2 4 A C depends

By the de nition of the set Sf , for the point (x0; )2Sf there exist di erent complex conjugate numbers z20 and z30 such that f (z20) = f (z30) = Rez20 = Rez30 = x0:

It follows that z20 and z30 are complex roots of equation ( 1 ) and, in particular, they di er from the real root z1. Therefore, the roots z2 and z3 coincide with the numbers z20 and z30.

So, if (x0; )2Sf , then The set Sf has the single-valued property: if (x0; 1) and (x0; 2) belong to Sf , then 1 = 2. Indeed, from ( 2 ) we obtain z1( 1 ) = z1( 2 ) = Thus, the set Sf lies on the graph of a single-valued conjugate function y = fs(x), and fs(x0) = , that is, fs( z1( ) 2 a1 ) = : 2a0 a1 a0 f ( 2t

) = f (z1( )) = :

Replace t = ( 1 ), then ( 3 ) ( 4 )

Comparing relations ( 3 ) and ( 4 ), we obtain fs(t) = f ( 2t proved. aa10 ). Lemma 2 is

The graph of the conjugate function fs(x) is formed from the graph of the cubic parabola f (x) in the following way. We compress the graph f (x) twice with respect to the vertical axis passing through the in ection point and turn it around the same axis.

Lemma 3. Let f (x) be a cubic polynomial with real coe cients. Then the graph of the conjugate function fs(x) passes through points of local extrema f (x), if they exist. In addition, the unique in ection points of the functions f and fs coincide. u1;2 = Proof. Assume that x is a local extremum point of f (x). One can nd x from the equation f 0(x) = 0 and verify the equality fs(x ) = 0 by a direct substitution. We simplify the calculations by changing the variable.

It is known that with parallel shifts the shape of the function graph does not change. Let us shift the graphs of the functions f (x) and fs(x): horizontally by r = 3aa10 to the left using the substitution x = u + r = u + ( 3aa10 ), and vertically down by a3 .

We obtain g(u) = f (u + ( 3aa10 )) a3. The function g(u) is a cubic parabola, for which the in ection point coincides with the coordinates origin. This easily implies that g(u) = A u3 + C u. Obviously, the function g(u) is odd and passes through the coordinates origin.

It su ces to prove Lemma 3 for the function g(u). We assume that A > 0 and suppose there are local extremum points for g. Then they have the form q

3AC , from which, in particular, C < 0. Substituting, for example, u1 into the functions g(u) and gs(u), we obtain = g(u1) = A(

Thus, the extremal points of the graph g(u) lie on the graph of its conjugate function gs(u).

It is obvious that the in ection point of the function gs(u) = 8u3 2Cu coincides with the in ection point of the function g(u). Lemma 3 is proved. 3

Construction of a gluing set for a polynomial of order 3

Consider the polynomial f (x) = a0x3 + a1x2 + a2x + a3, where a0 > 0. The graph of a cubic polynomial f (x) can be of two types (Fig. 1):

By Lemma 3, the graph of the conjugate function fs(x) passes through the extremum points and the in ection point of the function f (x).

We construct the gluing set Sf , which by Lemma 2 is contained in the graph of the conjugate function fs(x).

The type of the cubic parabola (Fig. 1) depends on the sign of the discriminant of the cubic polynomial

D = 4(a12

3a0 a2):

Indeed, the abscissas of the points of local extrema of the function f (x) are real roots of its derivative

The discriminant of the quadratic equation f 0(x) = 0, which determines the presence of real roots of f (x), coincides with D.

If D 0, then f (x) does not have local extrema (Fig. 1a) and by Lemma 2 for any the equation f (x) = has one real and two complex roots. Therefore, gluing set Sf coincides with the entire graph of the conjugate function fs(x) (Fig. 1a).

Let D > 0. Then the graph of f (x) has the form Fig 1b), where A(x1; y1) and B(x2; y2) are extreme points of the graph, and 2a1 pD

Take 0 2 [y2; y1]. Then the cubic equation f (x) = 0 has three real roots. If 0 = y2 or 0 = y1, then two of them are multiple. Therefore, by Lemma 2, for any x the point (x; 0) 2= Sf . Consequently, the horizontal line y = 0 passing through the point (0; 0) does not intersect the set Sf . Thus, gluing set Sf is formed from the graph of the conjugate function fs(x) by removing the closed fragment of the graph from A to B (Fig 2b).

Thus, on the same plane R2 three sets are constructed: the graph of the initial polynomial f (x), the graph of the conjugate function fs(x), and the gluing set Sf , which is contained in second set. 4

Main results

We consider the cubic equation f (x) x3 + a1x2 + a2x + a3 = ( 5 ) for an arbitrary real . We assume that a0 = 1. Otherwise, the nal results of this section can easily be modi ed by replacing the coe cients ak by aak0 for k = 1; 2; 3. The real roots of equation ( 5 ) can be found from the graph of the original polynomial. We shall seek the complex roots of this equation in the form x = a + bi; b 6= 0:

Substituting x into ( 5 ), we obtain

f (a + bi) = (a + bi)3 + a1(a + bi)2 + a2(a + bi) + a3

b3 + a1 a2 + 2abi b2 + a2 [a + bi] + a3 = [a3 + a1a2 + a2a + a3] [3a + a1] [3a2 + 2a1a + a2] = a3 + a1a2 + a2a + a3

[9a3 + 6a1a2 + 3a2a + 3a1a2 + 2a12a + a1a2] 8a3 8a1a2 + ( 2a2 2a12)a + (a3 a1a2) = [ 8a3 6aa12 a31] + a1 [4a2 + 4aa1 + a12] + a2 [ 2a

a1] + a3 a1)2 + a2( 2a a1 a0 = f ( 2a ) = fs(a) = : a1) + a3 = f ( 2a a1)

Thus, it is proved

Lemma 4. If the complex number x = a + bi is a root of the equation ( 5 ), then fs(a) = : a = fs 1( ): ( 6 ) ( 7 ) ( 8 ) ( 9 )

From Fig. 2 we can see, that under the conditions of Lemma 4 the function fs is invertible. Therefore, equality ( 8 ) can be written in the form

Relation ( 9 ) gives a geometric algorithm of nding the real part a of the complex root x = a + bi of the equation f (x) = . Now we show how to nd the complex component b of the root x.

De nition 2. The carrier set Nf of a polynomial f (x) is de ned to be the set of all complex numbers u with nonzero complex part, for which f (u) is a real number, that is

Nf = fu 2 C : Im(u) 6= 0; f (u) 2 Rg:

On the real plane Oxy, we associate the axis Ox with the real part, and Oy with the imaginary part of the complex number u = a + bi.

Lemma 5. The carrier set Nf of the polynomial f (x) coincides with the graph of the multivalued mapping (10) y = fN (x) = p3x2 + 2a1 x + a2 = pf 0(x): The domain of fN (x) coincides with the projection of the set Sf onto the axis Ox.

Proof. Fix an arbitrary 2 R. Let z0 = a + bi; b 6= 0, be a complex root of the equation f (x) = . Then, by Lemma 4, the real part of this root is a = fs 1( ), and the imaginary part satis es relation ( 7 ). Therefore, b =

p3a2 + 2a1 a + a2:

Lemma 4 is proved.

It is easy to see that the conjugate function fN (x) has two slope asymptotes y = p3x + pa1 ; y = 3 p3x a1 p : 3

The slope of theese asymptotes is

60o with respect to Ox. 5

Algorythm for the exact geometric search of all roots of a cubic equation

For simplicity of calculations, we shall assume that the elder coe cient of cubic equation a0 = 1: 1. Choose an arbitrary 2R. 2. Find the intersection of the graph y = f (x) and the line y = . There are two possible cases: (a) The intersection consists of 3 points, of which two or three can coincide when the function graph and the line are touched. Then the abscissas z1; z2; z3 of these points are obviously real roots (possibly multiples) of equation ( 1 ) (Fig. 3c). The algorithm is complete. (b) The intersection consists of one point. The abscissa z1 of this point is the unique real root of equation ( 1 ). To nd the two complex roots, go to step 3. 3. Find the intersection point of the line y = and the gluing set Sf . This point is unique. Its abscissa a is the real part of the required pair of complex conjugate roots. 4. Find the intersection of the vertical line x = a and the carrier set Nf , which lies on graph of fN . This intersection consists of two di erent points. The ordinates of these points are equal to +b and b, where b 0 and are imaginary components of the required pair of complex-conjugate roots of equation ( 1 ). 5. Thus, we have obtained two real numbers a and b, which yield complex conjugate roots of equation ( 1 ) (Fig. 3a, 3b). The algorithm is complete. The results presented in this paper were obtained with the help of a previously developed application ([9], which allows one to plot the graphs of complex functions of a complex variable. The auxiliary gluing set Sf is the set of selfintersections for such graphs. The application is built in the MatLab system. To nd complex roots of polynomials, the algorithm was also realized in MatLab. It allows us to trace the dynamics of complex roots when the free coe cient of the polynomial changes.

References

1. Zaguskin , V. L. : Handbook of numerical methods for solving algebraic and transcendental equations . FIZMATGIZ , Moscow ( 1988 )

2. Lapchik , M. P. : Numerical methods . Publishing Center "Academy" , Moscow: ( 2005 )

3. Bakhvalov , N. S.: Numerical methods . Higher School , Moscow ( 2002 )

4. Kornyushin , P. N. : Numerical methods . Far Eastern University Publishing House, Vladivostok ( 2002 )

5. Uderman , E. G. : The root hodograph method in the theory of automatic systems . Nauka, Moscow ( 1972 )

6. Tracksel , J.: Synthesis of automatic control systems . Mashgiz, Moscow ( 1959 )

7. Lin , S. N. : Method of successive approximations of evaluating the real and complex roots of cubic and higher-order equations . J. Mathem. Phys . Vol. 20 , No. 3 ( 1941 )

8. Bendrikov , G. A. , Theodorchik , K. F. : The laws of migration of the roots of linear algebraic equations of the third and fourth degree for the continuous variation of the free term . Autom. and Telem. , Vol. XIV, No. 3 . ( 1955 )

9. Tro mov, S. P. , Rusinov , P. V. , Tro mova , O. G.: Computer model of a fourdimensional graph of a function of a complex variable. Certi cate of state registration of the computer program No. 2017615380 , 2017 /5/15.