An Algorithm for Exact Geometric Search of Polynomials Complex Roots Sergey P. Trofimov Ural Federal University, 19, Mira Str., 620002, Eraterinburg tsp61@mail.ru Abstract. A graph of an n-th order polynomial on the real plane allows us to define 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 1 Introduction Complex numbers were introduced as an auxiliary tool for finding 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 find and illustrated on the graph. Complex roots do not possess this property. There are several exact algebraic and iterative numerical methods for finding the roots ([1] —[4]). Precise methods for polynomials with arbitrary coefficients, 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 definition of fN (x) coincides with the projection of the gluing set Sf onto the axis Ox. To find 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 131 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 find the intersection points with the glueing set. Then through each such point, we draw a vertical line and find the points of intersection with the carrier graph. These last points are complex roots of the equation f (x) = ∆. When the free coefficient ∆ 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 fp N (x) is expressed in terms of the derivative of the original polynomial fN (x) = f 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 coefficient ∆ and the problem is to find all the poles of the characteristic polynomial of a closed system ([5] —[8]). 2 Basic concepts Definition 1. Let f (x) be a polynomial of order n with real coefficients. 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, ∆) ∈ Sf , then the equation f (x) = ∆ (1) has one real and two different complex conjugate roots, and the real part of the complex roots is equal to a. Proof. Since (a, ∆)∈Sf , 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) = a0 x3 + a1 x2 + a2 x + a3 be a polynomial of the third order with real coefficients, 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 ). 132 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 , ∆)∈Sf and construct the equation (1). By Lemma 1 , equation (1) has exactly one real root. Denote this real root z1 (∆) and find other two complex roots z2 and z3 . Obviously, numbers z2 and z3 are the roots of the polynomial of the second order f (x) − ∆ f (x) − f (z1 ) = x − z1 x − z1 a0 (x3 − z13 ) + a1 (x2 − z12 ) + a2 (x − z1 ) = x − z1 = a0 (x2 + xz1 + z12 ) + a1 (x + z1 ) + a2 = A·x2 + B·x + C, where A = a0 , B = a0 z1 + a1 , C = a0 z12 + a1 z1 + a2 . Equation Az 2 + Bz + C = 0 √ B D has two roots z2,3 = − 2A ± 2A , where the discriminant D = B 2 −4·A·C depends on z1 and hence on ∆. Thus, equation (1) has three roots: one real z1 and two complex conjugated ones √ √ z1 a1 D z1 a1 D z2 = − − + , z3 = − − − . 2 2a0 2A 2 2a0 2A By the definition of the set Sf , for the point (x0 , ∆)∈Sf there exist different complex conjugate numbers z20 and z30 such that f (z20 ) = f (z30 ) = ∆ and Rez20 = Rez30 = x0 . It follows that z20 and z30 are complex roots of equation (1) and, in particular, they differ from the real root z1 . Therefore, the roots z2 and z3 coincide with the numbers z20 and z30 . So, if (x0 , ∆)∈Sf , then z1 (∆) a1 x0 = − − . (2) 2 2a0 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 a1 z1 (∆1 ) = z1 (∆2 ) = −2x0 − . a0 133 Since z1 (∆1 ) and z1 (∆2 ) are the roots of the corresponding equation (1), then ∆1 = f (z1 , (∆2 )) = f (z1 , (∆2 )) = ∆2 . Thus, the set Sf lies on the graph of a single-valued conjugate function y = fs (x), and fs (x0 ) = ∆, that is, z1 (∆) a1 fs (− − ) = ∆. (3) 2 2a0 Replace t = − z1 (∆) 2 a1 − 2a 0 . Then z1 (∆) = −2t − aa01 . Since z1 is the root of (1), then a1 f (−2t − ) = f (z1 (∆)) = ∆. (4) a0 Comparing relations (3) and (4), we obtain fs (t) = f (−2t − aa01 ). Lemma 2 is proved. 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 inflection point and turn it around the same axis. Lemma 3. Let f (x) be a cubic polynomial with real coefficients. Then the graph of the conjugate function fs (x) passes through points of local extrema f (x), if they exist. In addition, the unique inflection points of the functions f and fs coincide. Proof. Assume that x∗ is a local extremum point of f (x). One can find 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 a1 a1 by r = − 3a 0 to the left using the substitution x = u + r = u + (− 3a 0 ), and vertically down by a3 . a1 We obtain g(u) = f (u + (− 3a 0 )) − a3 . The function g(u) is a cubic parabola, for which the inflection 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 suffices to prove Lemma 3 for the function g(u). We assume that A > 0 and suppose q there are local extremum points for g. Then they have the form u1,2 = ± −C 3A , from which, in particular, C < 0. Substituting, for example, u1 into the functions g(u) and gs (u), we obtain r r C C g(u1 ) = A( − )3 + C( − ) 3A 3A r r r C C C 2 C =− − +C − = C − , 3 3A 3A 3 3A 134 r r C 3 C gs (u1 ) = g(−2u1 ) = A(−2 − ) + C(−2 − ) 3A 3A r r r −C C C 2 C = (−8) · − − 2·C − = C − . 3 3A 3A 3 3A Thus, the extremal points of the graph g(u) lie on the graph of its conjugate function gs (u). It is obvious that the inflection point of the function gs (u) = −8u3 − 2Cu coincides with the inflection 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) = a0 x3 + a1 x2 + a2 x + a3 , where a0 > 0. The graph of a cubic polynomial f (x) can be of two types (Fig. 1): a) b) Fig. 1. Two types of graphs of a cubic polynomial: a) without local extrema, b) with two local extrema By Lemma 3, the graph of the conjugate function fs (x) passes through the extremum points and the inflection 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 discrim- inant of the cubic polynomial D = 4(a21 − 3a0 ·a2 ). Indeed, the abscissas of the points of local extrema of the function f (x) are real roots of its derivative f 0 (x) = 3a0 x2 + 2a1 x + a2 . 135 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 ± D y1 > y2 , x1,2 = 6 Take ∆0 ∈ [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 ) ∈/ 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). a) b) Fig. 2. Two types of gluing set for a third-order polynomial: a) without local extrema, b) with local extrema 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 + a1 x2 + a2 x + a3 = ∆ (5) 136 for an arbitrary real ∆. We assume that a0 = 1. Otherwise, the final results of this section can easily be modified by replacing the coefficients 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 = a + 3a2 bi − 3ab2 − b3 + a1 a2 + 2abi − b2 + a2 [a + bi] + a3  3    = a3 − 3ab2 + a1 a2 − a1 b2 + a2 a + a3 + 3a2 b − b3 + 2a1 ab + a2 b i     = R(a, b) + I(a, b)·i = ∆ + 0·i. Equate to zero the imaginary part of I(a, b) of the complex number f (a + bi) 3a2 b − b3 + 2a1 ab + a2 b = 0. Dividing by b6=0, we obtain 3a2 − b2 + 2a1 a + a2 = 0, (6) whence b2 = 3a2 + 2a1 a + a2 . (7) Transform the real part R(a, b) of the number f (a + bi) R(a, b) = [a3 + a1 a2 + a2 a + a3 ] − [3a + a1 ]·b2 = [a3 + a1 a2 + a2 a + a3 ] − [3a + a1 ] · [3a2 + 2a1 a + a2 ] = a3 + a1 a2 + a2 a + a3 − [9a3 + 6a1 a2 + 3a2 a + 3a1 a2 + 2a21 a + a1 a2 ] = −8a3 − 8a1 a2 + (−2a2 − 2a21 )a + (a3 − a1 a2 ) = [−8a3 − 12a2 a1 − 6aa21 − a31 ] + a1 ·[4a2 + 4aa1 + a21 ] + a2 ·[−2a − a1 ] + a3 = (−2a − a1 )3 + a1 (−2a − a1 )2 + a2 (−2a − a1 ) + a3 = f (−2a − a1 ) a1 = f (−2a − ) = fs (a) = ∆. a0 Thus, it is proved Lemma 4. If the complex number x = a + bi is a root of the equation (5), then fs (a) = ∆. (8) 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 a = fs−1 (∆). (9) Relation (9) gives a geometric algorithm of finding the real part a of the complex root x = a + bi of the equation f (x) = ∆. Now we show how to find the complex component b of the root x. 137 Definition 2. The carrier set Nf of a polynomial f (x) is defined to be the set of all complex numbers u with nonzero complex part, for which f (u) is a real number, that is Nf = {u ∈ C : Im(u) 6= 0, f (u) ∈ R}. (10) 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 p p y = fN (x) = ± 3x2 + 2a1 ·x + a2 = ± f 0 (x). The domain of fN (x) coincides with the projection of the set Sf onto the axis Ox. Proof. Fix an arbitrary ∆ ∈ 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 satisfies relation (7). Therefore, p b = ± 3a2 + 2a1 ·a + a2 . Lemma 4 is proved. It is easy to see that the conjugate function fN (x) has two slope asymptotes √ a1 √ a1 y= 3x + √ , y = − 3x − √ . 3 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 coefficient of cubic equation a0 = 1. 1. Choose an arbitrary ∆∈R. 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 find the two complex roots, go to step 3. 138 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 different 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. a) c) b) Fig. 3. a) Always one real and two complex roots, b)one real and two complex roots, c)three real roots 5.1 Mathematical modeling The results presented in this paper were obtained with the help of a previ- ously 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 self- intersections for such graphs. The application is built in the MatLab system. To find complex roots of polynomials, the algorithm was also realized in MatLab. It allows us to trace the dynamics of complex roots when the free coefficient of the polynomial changes. References 1. Zaguskin, V. L.: Handbook of numerical methods for solving algebraic and tran- scendental 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) 139 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. Trofimov, S. P., Rusinov, P. V., Trofimova, O. G.: Computer model of a four- dimensional graph of a function of a complex variable. Certificate of state regis- tration of the computer program No. 2017615380, 2017/5/15.