Using Constrained Optimization to Find Real Roots of Polynomial(RRP)
محورهای موضوعی : Operations Research
Hossein Jafari
1
(Young Researchers and Elite Club, Arak Branch, Islamic Azad University, Arak, Iran.)
Mohammad Ehsanifar
2
(Department of Industrial Engineering, Islamic Azad University of Arak, Arak, Iran.)
کلید واژه: Nonlinear Programming, Operation Research, Optimization, Lingo software, Polynomial,
چکیده مقاله :
The roots of a polynomial have many applications in various sciences. If the polynomial under study has a degree of 4 or more, it will be impossible to find its roots through the coefficients. In this situation, most researchers use numerical methods to find the roots. The purpose of this research is to introduce a relatively simple method for calculating the real roots of a polynomial. In fact, the proposed approach emphasizes the ability of operation research science in the area of finding roots. In the end, some numerical examples are solved with the help of lingo software to better understand the proposed method. The results indicated that the proposed method is remarkably effective in finding the roots of a polynomial.
The roots of a polynomial have many applications in various sciences. If the polynomial under study has a degree of 4 or more, it will be impossible to find its roots through the coefficients. In this situation, most researchers use numerical methods to find the roots. The purpose of this research is to introduce a relatively simple method for calculating the real roots of a polynomial. In fact, the proposed approach emphasizes the ability of operation research science in the area of finding roots. In the end, some numerical examples are solved with the help of lingo software to better understand the proposed method. The results indicated that the proposed method is remarkably effective in finding the roots of a polynomial.
Research Paper
Using Constrained Optimization to Find Real Roots of Polynomial(RRP)
| |||
Article Info Article history: Received 11 March 2022 Accepted 10 June 2022
Keywords: Nonlinear Programming, Operation Research, Optimization, Polynomial, Lingo Software. |
|
Abstract | |
The roots of a polynomial have many applications in various sciences. If the polynomial under study has a degree of 4 or more, it will be impossible to find its roots through the coefficients. In this situation, most researchers use numerical methods to find the roots. The purpose of this research is to introduce a relatively simple method for calculating the real roots of a polynomial. In fact, the proposed approach emphasizes the ability of operation research science in the area of finding roots. In the end, some numerical examples are solved with the help of lingo software to better understand the proposed method. The results indicated that the proposed method is remarkably effective in finding the roots of a polynomial. |
1.Introduction
It is one of the branches of applied mathematics that one of its practical aspects is significant in industrial engineering[1].
Operation Research is an interdisciplinary field of mathematics that uses fields such as mathematical programming, statistics and algorithm design to find the optimal point in optimization problems. Finding the optimal point based on problem type has different meanings and is used in decision making. Operation research issues focus on maximizing or minimizing one or more constraints. The main idea behind operation research is to find the best answer to complicated problems modeled with mathematical language and it leads to the improvement of or optimization of the performance of a system[2].
Operation research may consider a variety of variables, whether discrete, continuous, or both. For example, in optimizing the arrangement of the independent variables, the dependent variable has a discrete nature and the dependent variable (objective function) has a discrete or continuous nature[3].
One of the most powerful software in the field of variable optimization (discrete or continuous or both) is Lingo software[4].
Many problems in computer aided geometric design and computer graphics can be turned into a root-finding problem of a polynomial equation[5].
In this research we also try to use mathematical rules to define a particular problem (finding the true roots of a polynomial) as a model in the form of rules for operation research and finally solve it with the help of Lingo software which is one of the most powerful software in OR. In other words, this study adopted a step‑by‑step approach to find the real roots of a polynomial by using penalty functions in each step.
2.Polynomial
Polynomials consist of some monomials. These expressions are created by multiplying a constant number (called the coefficient) by the power of a variable. Each variable must have a constant numerical power. You see the mathematical form of a monomial:
(1)
Polynomial is a polynomial of degree
and the coefficient
is opposite to zero
[6].
2.1.Real polynomial
A real polynomial is a polynomial in which all the coefficients () of a monomial have a real value[6].
2.2.The zeros of polynomial
The zeros of polynomial are numbers for which the value of polynomials is zero[6].
3.Statement of problem
Polynomials are important in all mathematical disciplines and play a crucial role. Polynomials are used for approximate functions in numerical analysis and outside of mathematics, the basic equations of economics and physics are expressed by polynomials. Polynomials are also used in linear algebra for specific matrices equations[7].
There are various ways to find the roots of a real polynomial, most of which require a derivative condition. Some other methods that do not require derivation may also have errors, such as the drawing method. The purpose of this research is to present an optimization model to find the real roots of real polynomials. To put it simply, our research does not intend to criticize previous methods but rather, it aims to introduce a new approach to researchers by which they can reach the real roots of a polynomial and provide broader scope for future research. At the end of the discussion some numerical examples will be solved using the proposed method.
4.Literature review
The following are some of the most important researches that have been done in this area:
In 1970, Hirst and Macey in an article examined the boundaries of the roots of polynomials. The researchers eventually introduced a boundary for real and complex roots with the help of several algebraic theorems. The mentioned boundary is calculated based on the value of the polynomial coefficients[8].
In 2004, Deshuang and Zheru in an article proposed a new method for calculating the real roots of a polynomial. The time complexity of the proposed algorithm is as follows. Numerical examples solved by the proposed method illustrate the high accuracy of the new algorithm in root approximation[9].
In 1999, Sanchez et al. in an article investigated the roots of fuzzy cash flow using the fuzzy internal rate of return method[10].
In 2020, Jafari et al. presented a heuristic method (HM) to calculate real internal rates of return (RIRR). Their results showed that the new method was relatively effective and capable of calculating all of the real rates[11].
5.Introducing the proposed approach
In the proposed method, first we need a few theorems that will be discussed separately as follows. And then with the help of these theories the method will be fully introduced.
Theorem (1): Imagine is a real polynomial, then all the real zeros of
are put in the interval
as if
[8].
Theorem (2): Imagine is a real polynomial with degree
), as if then all the real zeros of
are put in the interval
, as if
.
Proof:
According to theorem , thus,
. It is clear that roots of
and
are equal , thus we define the new polynomial
as
, in which
). It is clear that
is a real polynomial of degree
with
and we can write
as
. Now according to theorem (1) it can be concluded that all the real zeros of
are put in the interval
as if
. Based on the previous findings, it can be concluded that all the real roots of the polynomial
are in the interval
. On the other hand, according to the hypothesis
, thus it is concluded that all the real roots of polynomial
are in the interval
.
So the proof is complete and the verdict is in place.
Theorem (3): Imagine is a real polynomial, then the polynomial
can have the maximum
real roots.
Proof by contradiction:
Imagine has
real roots as
, thus the criterion
can be written as
.(
)
By multiplying and rewriting the criterion it is determined that
is a polynomial with a degree more than
and the result is inconsistent with the assumption of the theorem, so the positive argument is invalid and the verdict is in place.
Lemma(1): If is a polynomial as
and the function
is defined as
Then the roots of
and
are equal.
Proof of the first part:
Imagine is a root for
, thus,
(2)
Thus is also the root of
.
Proof the second part:
Imagine is a root for
, thus,
(3)
Finally, the proof is complete.
6.The proposed method for finding real roots
Imagine that all the roots of the polynomial are in the interval
. If
, it is clear that amount of
in the point
is either positive, negative or zero
.
Consider function with the criterion
. If
is a root for the polynomial
, based on lemma(1) it can be concluded that
is a root for
and vice versa. Also the amount of
in the point
is either positive or zero.(
)
According to the previous points, it can be said that for finding the real roots of the polynomial we can define a mathematical model as follows:
(4)
Subject to:
(5)
(6)
(7)
According to theorem (2) the search interval can be set as . Thus, the previous mathematical model can be rewritten as:
(8)
Subject to:
(9)
(10)
(11)
Now if we solve the previous optimization model we will find a real root of which we call it
. After setting the value of the first root (
), we add a penalty function to the objective function criterion and the new objective function be comes
. This change causes the algorithm to not converge and avoid the roots of the previous discovery in subsequent searches. Now based on theorem (3), it is enough to stop this algorithm after
runs, since the maximum objective function can have
roots. The penalty function criterion must also be defined as such that when approaching to m previously discovered roots
, the value of the objective function (
) Will greatly increase. Following is an example of a penalty function.
(12)
Note: Given that the proposed mathematical model works to find the minimum ,
may not be zero for some solutions (That is, it is far from zero) and only minimized. Therefore, by examining the value of
in the discovered roots, incorrect roots can be removed from the total set of discovered roots. This step is called the root refinement step.
Numerical Example(1)
We intend to calculate the polynomial roots using the proposed method and Lingo software:
First, we calculate the boundaries of the roots as follows:
Now the problem-based mathematical model to find the first root is as follows:
Subject to:
After solving the previous mathematical model in Lingo software, the output is obtained as .
According to the Previously mentioned points, to find the second root we have to use the penalty function so that the algorithm used in the software does not converge to the previously discovered solution, so we change the previous mathematical model as follows:
Subject to:
After solving the previous mathematical model in Lingo software, the output is obtained as .
The following mathematical model is used to find the third root:
After solving the previous mathematical model in Lingo software, the output is obtained as .
To find the fourth root we need to use the following mathematical model:
Subject to:
After solving the previous mathematical model in Lingo software, the output is obtained as .
And finally, to find the fifth root, we have to use the following mathematical model:
Subject to:
The roots must now be refined. For this purpose, Table 1 presents the value of for the five discovered roots.
Table 1. value of for each root
|
|
| Decision | |||||||||||||||||||||||||||||||
|
|
| To be confirmed | |||||||||||||||||||||||||||||||
|
|
| To be confirmed | |||||||||||||||||||||||||||||||
|
|
| Not to be confirmed | |||||||||||||||||||||||||||||||
|
|
| Not to be confirmed | |||||||||||||||||||||||||||||||
|
|
| To be confirmed |
|
|
| Decision | |||
|
|
| To be confirmed | |||
|
|
| Not to be confirmed | |||
|
|
| Not to be conformed | |||
|
|
| Not to be confirmed | |||
|
|
| To be confirmed | |||
|
|
| Not to be confirmed |
© 2021. All rights reserved. |