=Paper=
{{Paper
|id=Vol-2076/paper-15
|storemode=property
|title=An Algorithm for Exact Geometric Search of Polynomials Complex Roots
|pdfUrl=https://ceur-ws.org/Vol-2076/paper-15.pdf
|volume=Vol-2076
|authors=Sergey P. Trofimov
}}
==An Algorithm for Exact Geometric Search of Polynomials Complex Roots ==
https://ceur-ws.org/Vol-2076/paper-15.pdf
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.