Descartes' rule of signs

Last updated

In mathematics, Descartes' rule of signs, first described by René Descartes in his work La Géométrie , is a technique for getting information on the number of positive real roots of a polynomial. It asserts that the number of positive roots is at most the number of sign changes in the sequence of polynomial's coefficients (omitting the zero coefficients), and that the difference between these two numbers is always even. This implies in particular that, if this difference is zero or one, then there is exactly zero or one positive root, respectively. Mathematics includes the study of such topics as quantity, structure, space, and change. René Descartes was a French philosopher, mathematician, and scientist. A native of the Kingdom of France, he spent about 20 years (1629–1649) of his life in the Dutch Republic after serving for a while in the Dutch States Army of Maurice of Nassau, Prince of Orange and the Stadtholder of the United Provinces. He is generally considered one of the most notable intellectual figures of the Dutch Golden Age. La Géométrie was published in 1637 as an appendix to Discours de la méthode, written by René Descartes. In the Discourse, he presents his method for obtaining clarity on any subject. La Géométrie and two other appendices, also by Descartes, La Dioptrique (Optics) and Les Météores (Meteorology), were published with the Discourse to give examples of the kinds of successes he had achieved following his method.

Contents

By a homographic transformation of the variable, one may use Descartes' rule of signs for getting a similar information on the number of roots in any interval. This is the basic idea of Budan's theorem and Budan–Fourier theorem. By repeating the division of an interval into two intervals, one gets eventually a list of disjoints intervals containing together all real roots of the polynomial, and containing each exactly one real root. Descartes rule of signs and homographic transformations of the variable are, nowadays, the basis of the fastest algorithms for computer computation of real roots of polynomials (see Real-root isolation).

In mathematics, Budan's theorem is a theorem for bounding the number of real roots of a polynomial in an interval, and computing the parity of this number. It was published in 1807 by François Budan de Boislaurent.

In mathematics, and, more specifically in numerical analysis and computer algebra, real-root isolation of a polynomial consist of producing disjoint intervals of the real line, which contain each one real root of the polynomial, and, together, contain all the real roots of the polynomial.

Descartes himself used the transformation x → –x for using his rule for getting information of the number of negative roots.

Descartes' rule of signs

Positive roots

The rule states that if the 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 differences between consecutive nonzero coefficients, or is less than it by an even number. Multiple roots of the same value are counted separately. In mathematics, a polynomial is an expression consisting of variables and coefficients, that involves only the operations of addition, subtraction, multiplication, and non-negative integer exponents of variables. An example of a polynomial of a single indeterminate, x, is x2 − 4x + 7. An example in three variables is x3 + 2xyz2yz + 1. In mathematics, a real number is a value of a continuous quantity that can represent a distance along a line. The adjective real in this context was introduced in the 17th century by René Descartes, who distinguished between real and imaginary roots of polynomials. The real numbers include all the rational numbers, such as the integer −5 and the fraction 4/3, and all the irrational numbers, such as 2. Included within the irrationals are the transcendental numbers, such as π (3.14159265...). In addition to measuring distance, real numbers can be used to measure quantities such as time, mass, energy, velocity, and many more.

In mathematics, a coefficient is a multiplicative factor in some term of a polynomial, a series, or any expression; it is usually a number, but may be any expression. In the latter case, the variables appearing in the coefficients are often called parameters, and must be clearly distinguished from the other variables.

Negative roots

As a corollary of the rule, the number of negative roots is the number of sign changes after multiplying the coefficients of odd-power terms by −1, or fewer than it by an even number. This procedure is equivalent to substituting the negation of the variable for the variable itself. For example, to find the number of negative roots of $f(x)=ax^{3}+bx^{2}+cx+d$ , we equivalently ask how many positive roots there are for $-x$ in

A corollary is a statement that follows readily from a previous statement.

$f(-x)=a(-x)^{3}+b(-x)^{2}+c(-x)+d=-ax^{3}+bx^{2}-cx+d\equiv g(x).$ Using Descartes' rule of signs on $g(x)$ gives the number of positive roots $x_{i}$ of g, and since $g(x)=f(-x)$ it gives the number of positive roots $(-x_{i})$ of f, which is the same as the number of negative roots $x_{i}$ of f.

Example: real roots

The polynomial

$f(x)=+x^{3}+x^{2}-x-1$ has one sign change between the second and third terms (the sequence of pairs of successive signs is ++, +, ). Therefore it has exactly one positive root. Note that the sign of the leading coefficient needs to be considered. To find the number of negative roots, change the signs of the coefficients of the terms with odd exponents, i.e., apply Descartes' rule of signs to the polynomial $f(-x)$ , to obtain a second polynomial

$f(-x)=-x^{3}+x^{2}+x-1$ This polynomial has two sign changes (the sequence of pairs of successive signs is +, ++, +), meaning that this second polynomial has two or zero positive roots; thus the original polynomial has two or zero negative roots.

In fact, the factorization of the first polynomial is

$f(x)=(x+1)^{2}(x-1),$ so the roots are 1 (twice) and +1 (once).

The factorization of the second polynomial is

$f(-x)=-(x-1)^{2}(x+1),$ So here, the roots are +1 (twice) and 1 (once), the negation of the roots of the original polynomial.

Nonreal roots

Any nth degree polynomial has exactly n roots in the complex plane, if counted according to multiplicity. So if f(x) is a polynomial which does not have a root at 0 (which can be determined by inspection) then the minimum number of nonreal roots is equal to In mathematics, the complex plane or z-plane is a geometric representation of the complex numbers established by the real axis and the perpendicular imaginary axis. It can be thought of as a modified Cartesian plane, with the real part of a complex number represented by a displacement along the x-axis, and the imaginary part by a displacement along the y-axis.

$n-(p+q),$ where p denotes the maximum number of positive roots, q denotes the maximum number of negative roots (both of which can be found using Descartes' rule of signs), and n denotes the degree of the equation.

Example: zero coefficients, nonreal roots

The polynomial

$f(x)=x^{3}-1\,,$ has one sign change, so the maximum number of positive real roots is 1. From

$f(-x)=-x^{3}-1\,,$ we can tell that the polynomial has no negative real roots. So the minimum number of nonreal roots is

$3-(1+0)=2\,.$ Since nonreal roots of a polynomial with real coefficients must occur in conjugate pairs, we can see that x3 − 1 has exactly 2 nonreal roots and 1 real (and positive) root.

Special case

The subtraction of only multiples of 2 from the maximal number of positive roots occurs because the polynomial may have nonreal roots, which always come in pairs since the rule applies to polynomials whose coefficients are real. Thus if the polynomial is known to have all real roots, this rule allows one to find the exact number of positive and negative roots. Since it is easy to determine the multiplicity of zero as a root, the sign of all roots can be determined in this case.

Generalizations

If the real polynomial P has k real positive roots counted with multiplicity, then for every a > 0 there are at least k changes of sign in the sequence of coefficients of the Taylor series of the function eaxP(x). For a sufficiently large, there are exactly k such changes of sign.  

In the 1970s Askold Georgevich Khovanskiǐ developed the theory of fewnomials that generalises Descartes' rule.  The rule of signs can be thought of as stating that the number of real roots of a polynomial is dependent on the polynomial's complexity, and that this complexity is proportional to the number of monomials it has, not its degree. Khovanskiǐ showed that this holds true not just for polynomials but for algebraic combinations of many transcendental functions, the so-called Pfaffian functions.