How many roots exist for the following single variable polynomial equation?
2x^5 - x^4 - 1 4x^3 - 6 x^2 + 24x + 40 = 0
To find out the the number of roots of a single polynomial equation, we find out the degree of the polynomial i.e. highest exponent of the variable in given polynomial equation.
The exponents here are 5, 4, 3, 2, 1, and 0 (zero). The highest exponent is 5. Hence, the given equation has total five number of roots. This is nothing but the fundamental theorem of Algebra. It is stated as every non-zero, single-variable, degree n polynomial with complex coefficients has, counted with multiplicity, exactly n complex roots. It holds true for real coefficients too because every real number is an imaginary number with the imaginary part as zero.
Now, we have the value of total number of roots for the given polynomial equation. Let us understand more by asking following questions.
What is the meaning of multiplicity of a root of polynomial equation?
Can we determine the nature of the roots i.e. the number of positive real roots, negative real roots or complex roots for the given polynomial equation? If yes, how?
What is the advantage of knowing the nature of the roots beforehand since we can always tell it once the equation is solved?
Multiplicity is the number of times a root of the polynomial is repeated.
For the polynomial equation x^5 - 9 x^4 - 9 x^3 + 157 x^2 - 132 x - 288 = 0, the total number of roots are 5 by the fundamental theorem of Algebra. Let us see what the roots are.
x^5 - 9x^4 - 9x^3 + 157x^2 - 132x - 288 = (x-3)(x-8)(x-3)(x+4)(x+1)Hence, the roots of the given polynomial are as follows,
x=-4, x=-1, x=8, and x=3 with multiplicity as 2.
Moving to the answer of next question, yes, we can determine the nature of the roots of polynomial beforehand. Instead of looking into how, first we will quickly go through why it is needed to understand or what advantage we get. Now-a-days, programs and computers are used widely to solve the equations. Fundamentally, the algorithms which are used to develop the equation solvers use root finding techniques in Numerical Analysis. A lot of these root finding techniques and algorithms have iterative approach. And, these algorithms should have less computational complexity for better performance. In layman's term, computational complexity is a measurement of the effort to perform the computations. More often, we are interested in real solution of the polynomial equation in practical world of application and engineering. In the average, a polynomial of degree n has n complex roots, and only log n real roots. So, it is good if we know about the nature of the roots and number of real (positive or negative) roots before we apply the root finding algorithms to get the solutions. It gives an upper hand for the algorithms as one of the stopping criteria, and hence, helps in achieve better computational complexity of the algorithms. This technique of identifying real roots is known as real-root isolation.
Now, we are remained with an important question of how to determine the nature of the roots. The first real root isolation algorithm was resulted from Sturm's algorithm which was discovered in 1829. Let us understand the Sturm's algorithm step by step.
STEP 1: Call the equation for which roots are to be calculated as f0(x)STEP 2: Calculate f1(x) by taking derivative of f0(x). STEP 3: Calculate the remainder r(x) by dividing f0(x) by f1(x).STEP 4: Multiply the remainder r(x) by (-1) and call it as f2(x).STEP 5: Repeat STEP 3 and STEP 4 for subsequent calculations of fn(x) until it is reached to a constant term.STEP 6: f0(x),f1(x),f2(x),...,fn(x) is called as Sturm sequence. Calculate the values as f(−∞) and f(∞) for each expression of Sturm sequence and note down the sign (either positive or negative) of values for each Sturm sequence. STEP 7: Determine how many times sign has changed for f(−∞) and f(∞) until the constant term has reached. STEP 8: Calculate k = V(−∞) - V(∞) where V is the number of sign change. STEP 9: f(x) has k real roots. Let us apply Sturm algorithm for 2x^5 - x^4 - 1 4x^3 - 6 x^2 + 24x + 40 = 0
Step 1 :
f0(x) = 2x^5 - x^4 - 1 4x^3 - 6 x^2 + 24x + 40
f0(−∞) has - sign.
f0(+∞) has + sign.
Step 2:
f1(x) = f '(x) = 10 x^4 - 4 x^3 - 12 x^2 - 12 x + 24
f1(−∞) has + sign.
f1(+∞) has + sign.
Step 3:
Divide f0(x) by f1(x) and calculate remainder r(x).
r(x)= (1/25) (-42 x^3 - 96 x^2 + 474 x+ 1012)
Step 4:
Multiply the remainder(x) by (-1) to get f2(x).
f2(x) = (1/25) (42 x^3 + 96 x^2 - 474 x - 1012)
f2(−∞) has - sign.
f2(+∞) has + sign.
[Repeat] Step 3 and Step 4 to get f3(x):
Divide f1(x) by f2(x) and calculate remainder r(x).
r(x) = (198750 x^2)/49 - (272500 x)/147 - 2290000/147
Multiply the remainder(x) by (-1) to get f3(x).
f3(x) = (-198750 x^2)/49 + (272500 x)/147 + 2290000/147
f3(−∞) has + sign.
f3(+∞) has - sign.
[Repeat] Step 3 and Step 4 to get f4(x):
Divide f2(x) by f3(x) and calculate remainder r(x).
r(x) = (1/75843)(-19722598 x- 43198204)
Multiply the remainder(x) by (-1) to get f4(x).
f4(x) = (1/75843)(19722598 x + 43198204)
f4(−∞) has - sign.
f4(+∞) has + sign.
[Repeat] Step 3 and Step 4 to get f5(x):
Divide f3(x) by f4(x) and calculate remainder r(x).
r(x) = -1195218644351802300000/1984596285049
Multiply the remainder(x) by (-1) to get f5(x).
f5(x) = 1195218644351802300000/1984596285049
f5(−∞) has + sign.
f5(+∞) has + sign.
Since we have reached to the constant term, we stop the process and what we get f0(x), f1(x),f2(x), f3(x), f4(x) and f5(x) expressions for Sturm sequence for the given polynomial.
Step 6:
We have already found out f(−∞) and f(∞) for each expression of Sturm's sequence.
Step 7 :
Let us write the signs in one line.
f(−∞) has signs as [-, +, -, +, -, + ]
Number of signs changed V(−∞) = 5
f(∞) has signs as [+, +, +, -, +, + ]
Number of signs changed V(∞) = 2
Step 8 :
k= V(−∞) - V(∞) = 5-2 = 3
Hence, f0(x) = 2x^5 - x^4 - 1 4x^3 - 6 x^2 + 24x + 40 = 0 has 3 real roots.
If we calculate the roots of 2x^5 - x^4 - 1 4x^3 - 6 x^2 + 24x + 40 = 0, they come out as
x=-2,
x=2,
x=5/2,
x=-1-i
and
x=-1+i
Out of all five roots, the number of real roots are 3.
We can see the computations for Sturm's sequence is a bit tedious process, It is also proven and experienced practically that the algorithms derived from Sturm's theorem are less efficient than Descartes' rule of signs in terms of computational complexity. Let us see what Descartes' rule of signs is.
Descartes' rule of signs
The rule states that if the nonzero terms of a single variable polynomial with real coefficients are ordered by descending variable exponent, then the number of positive roots of the polynomial is either equal to the number of sign changes between consecutive (nonzero) coefficients, or is less than it by an even number.Positive roots
Let us see what it is by considering the same example polynomial used above.
f(x) = +2x^5 - x^4 - 1 4x^3 - 6 x^2 + 24x + 40 = 0
The signs are [+, -, -, -, +, +].
The number of times the sign has changed = 2.
Thus, the +2x^5 - x^4 - 1 4x^3 - 6 x^2 + 24x + 40 = 0 has two or zero positive real roots.
Negative roots
It is corollary of the rule itself. The negative roots of f(x) are the positive roots of f(-x).
We will calculate f(-x) and find the number of positive roots by Descartes' rule of signs.
f(-x) = -2x^5 - x^4 +1 4x^3 - 6 x^2 - 24x + 40 = 0
The signs are [-, -, +, -, -, +].
The number of times the sign has changed = 3.
Thus, -2x^5 - x^4 +1 4x^3 - 6 x^2 - 24x + 40 = 0 has three or one positive real roots.
Thus, the +2x^5 - x^4 - 1 4x^3 - 6 x^2 + 24x + 40 = 0 has three or one negative real roots.
The following table lays out all combinations of the roots for the given single variable polynomial equation.
We can see that Descartes' rule of signs is a lot easy to work with. Also, it is widely used in developing the real root isolation algorithms. It's been an active research area in the field of Numerical Analysis and Computer Algebra for improvements of such algorithms derived from Descartes' rule of signs.