In mathematics, Vincent's theorem—named after
Alexandre Joseph Hidulphe Vincent Alexandre may refer to:
* Alexandre (given name)
* Alexandre (surname)
* Alexandre (film)
See also
* Alexander
* Xano (disambiguation) Xano is the name of:
* Xano, a Portuguese hypocoristic of the name "Alexandre (disambiguation) Alexandre may re ...
—is a theorem that isolates the real roots of polynomials with rational coefficients.
Even though Vincent's theorem is the basis of the fastest method for the isolation of the real roots of polynomials, it was almost totally forgotten, having been overshadowed by
Sturm's theorem
In mathematics, the Sturm sequence of a univariate polynomial is a sequence of polynomials associated with and its derivative by a variant of Euclid's algorithm for polynomials. Sturm's theorem expresses the number of distinct real roots of loca ...
; consequently, it does not appear in any of the classical books on the theory of equations (of the 20th century), except for
Uspensky's book. Two variants of this theorem are presented, along with several (continued fractions and bisection) real root isolation methods derived from them.
Sign variation
:Let ''c''
0, ''c''
1, ''c''
2, ... be a finite or infinite sequence of real numbers. Suppose ''l'' < ''r'' and the following conditions hold:
# If ''r'' = ''l''+1 the numbers ''c
l'' and ''c
r'' have opposite signs.
# If ''r'' ≥ ''l''+2 the numbers ''c''
''l''+1, ..., ''c''
''r''−1 are all zero and the numbers ''c
l'' and ''c
r'' have opposite signs.
: This is called a ''sign variation'' or ''sign change'' between the numbers ''c
l'' and ''c
r''.
: When dealing with the polynomial ''p''(''x'') in one variable, one defines the number of sign variations of ''p''(''x'') as the number of sign variations in the sequence of its coefficients.
Two versions of this theorem are presented: the ''
continued fractions
In mathematics, a continued fraction is an expression obtained through an iterative process of representing a number as the sum of its integer part and the reciprocal of another number, then writing this other number as the sum of its integer ...
'' version due to Vincent,
and the ''
bisection
In geometry, bisection is the division of something into two equal or congruent parts, usually by a line, which is then called a ''bisector''. The most often considered types of bisectors are the ''segment bisector'' (a line that passes through ...
'' version due to Alesina and Galuzzi.
Vincent's theorem: Continued fractions version (1834 and 1836)
If in a polynomial equation with rational coefficients and without multiple roots, one makes successive transformations of the form
:
where
are any positive numbers greater than or equal to one, then after a number of such transformations, the resulting transformed equation either has zero
sign variation
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.
A similar theorem was publishe ...
s or it has a single
sign variation
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.
A similar theorem was publishe ...
. In the first case there is no root, whereas in the second case there is a single positive real root. Furthermore, the corresponding root of the proposed equation is approximated by the finite continued fraction:
:
Moreover, if infinitely many numbers
satisfying this property can be found, then the root is represented by the (infinite) corresponding continued fraction.
The above statement is an exact translation of the theorem found in Vincent's original papers;
however, the following remarks are needed for a clearer understanding:
*If
denotes the polynomial obtained after ''n'' substitutions (and after removing the denominator), then there exists ''N'' such that for all
either
has no sign variation or it has one sign variation. In the latter case
has a single positive real root for all
.
* The continued fraction represents a positive root of the original equation, and the original equation may have more than one positive root. Moreover, assuming
, we can only obtain a root of the original equation that is > 1. To obtain an arbitrary positive root we need to assume that
.
* Negative roots are obtained by replacing ''x'' by −''x'', in which case the negative roots become positive.
Vincent's theorem: Bisection version (Alesina and Galuzzi 2000)
Let ''p''(''x'') be a real polynomial of degree deg(''p'') that has only simple roots. It is possible to determine a positive quantity δ so that for every pair of positive real numbers ''a'', ''b'' with
, every transformed polynomial of the form
has exactly 0 or 1
sign variation
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.
A similar theorem was publishe ...
s. The second case is possible if and only if ''p''(''x'') has a single root within (''a'', ''b'').
The Alesina–Galuzzi "a_b roots test"
From equation () the following criterion is obtained for determining whether a polynomial has any roots in the interval (''a'', ''b''):
Perform on ''p''(''x'') the substitution
:
and count the number of
sign variations in the sequence of coefficients of the transformed polynomial; this number gives an ''upper bound'' on the number of real roots ''p''(''x'') has inside the open interval (''a'', ''b''). More precisely, the number ''ρ''
''ab''(''p'') of real roots in the open interval (''a'', ''b'')—multiplicities counted—of the polynomial ''p''(''x'') in R
'x'' of degree deg(''p''), is bounded above by the number of
sign variations ''var''
''ab''(''p''), where
:
:
As in the case of
Descartes' rule of signs
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 i ...
if var
''ab''(''p'') = 0 it follows that ρ
''ab''(''p'') = 0 and if var
''ab''(''p'') = 1 it follows that ρ
''ab''(''p'') = 1.
A special case of the Alesina–Galuzzi "a_b roots test" is
Budan's "0_1 roots test".
Sketch of a proof
A detailed discussion of Vincent's theorem, its extension, the geometrical interpretation of the transformations involved and three different proofs can be found in the work by Alesina and Galuzzi.
A fourth proof is due to
Ostrowski who rediscovered a special case of a theorem stated by
Obreschkoff,
p. 81, in 1920–1923.
To prove (both versions of) Vincent's theorem Alesina and Galuzzi show that after a series of transformations mentioned in the theorem, a polynomial with one positive root eventually has one sign variation. To show this, they use the following corollary to the theorem by
Obreschkoff of 1920–1923 mentioned earlier; that is, the following corollary gives the necessary conditions under which a polynomial with one positive root has exactly one sign variation in the sequence of its coefficients; see also the corresponding figure.
:Corollary. (
Obreschkoff's cone or sector theorem, 1920–1923
p. 81): If a real polynomial has one simple root , and all other (possibly multiple) roots lie in the sector
::
:then the sequence of its coefficients has exactly one sign variation.
![Sketch of proof](https://upload.wikimedia.org/wikipedia/commons/4/46/Sketch_of_proof.jpg)
Consider now the
Möbius transformation
In geometry and complex analysis, a Möbius transformation of the complex plane is a rational function of the form
f(z) = \frac
of one complex variable ''z''; here the coefficients ''a'', ''b'', ''c'', ''d'' are complex numbers satisfying ''ad'' ...
:
and the three circles shown in the corresponding figure; assume that
*The (yellow) circle
::
:whose diameter lies on the real axis, with endpoints and is mapped by the inverse Möbius transformation
::
:onto the imaginary axis. For example the point
::
:gets mapped onto the point The exterior points get mapped onto the half-plane with .
*The two circles (only their blue crescents are visible) with center
::
:and radius
::
:are mapped by the inverse Möbius transformation
::
:onto the lines . For example the point
::
:gets mapped to the point
::
:The exterior points (those outside the eight-shaped figure) get mapped onto the
sector.
From the above it becomes obvious that if a polynomial has a single positive root inside the eight-shaped figure and all other roots are outside of it, it presents one sign variation in the sequence of its coefficients. This also guarantees the termination of the process.
Historical background
Early applications of Vincent's theorem
In his fundamental papers,
Vincent presented examples that show precisely how to use his theorem to
isolate real roots of polynomials with
continued fractions
In mathematics, a continued fraction is an expression obtained through an iterative process of representing a number as the sum of its integer part and the reciprocal of another number, then writing this other number as the sum of its integer ...
. However the resulting method had
exponential
Exponential may refer to any of several mathematical topics related to exponentiation, including:
*Exponential function, also:
**Matrix exponential, the matrix analogue to the above
* Exponential decay, decrease at a rate proportional to value
*Exp ...
computing time, a fact that mathematicians must have realized then, as was realized by
Uspensky p. 136, a century later.
![Vincent method](https://upload.wikimedia.org/wikipedia/commons/9/9f/Vincent_method.jpg)
The
exponential
Exponential may refer to any of several mathematical topics related to exponentiation, including:
*Exponential function, also:
**Matrix exponential, the matrix analogue to the above
* Exponential decay, decrease at a rate proportional to value
*Exp ...
nature of Vincent's algorithm is due to the way the partial
quotient
In arithmetic, a quotient (from lat, quotiens 'how many times', pronounced ) is a quantity produced by the division of two numbers. The quotient has widespread use throughout mathematics, and is commonly referred to as the integer part of a ...
s ''a
i'' (in
Vincent's theorem In mathematics, Vincent's theorem—named after Alexandre Joseph Hidulphe Vincent—is a theorem that isolates the real roots of polynomials with rational coefficients.
Even though Vincent's theorem is the basis of the fastest method for the isola ...
) are computed. That is, to compute each partial
quotient
In arithmetic, a quotient (from lat, quotiens 'how many times', pronounced ) is a quantity produced by the division of two numbers. The quotient has widespread use throughout mathematics, and is commonly referred to as the integer part of a ...
''a
i'' (that is, to locate where the roots lie on the ''x''-axis) Vincent uses
Budan's theorem
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.
A similar theorem was publishe ...
as a
"no roots test"; in other words, to find the integer part of a root Vincent performs successive substitutions of the form ''x'' ← ''x''+1 and stops only when the polynomials ''p''(''x'') and ''p''(''x''+1) differ in the number of
sign variation
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.
A similar theorem was publishe ...
s in the sequence of their coefficients (i.e. when the number of
sign variation
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.
A similar theorem was publishe ...
s of ''p''(''x''+1) is decreased).
See the corresponding diagram where the root lies in the interval (5, 6). It can be easily inferred that, if the root is far away from the origin, it takes a lot of time to find its integer part this way, hence the
exponential
Exponential may refer to any of several mathematical topics related to exponentiation, including:
*Exponential function, also:
**Matrix exponential, the matrix analogue to the above
* Exponential decay, decrease at a rate proportional to value
*Exp ...
nature of Vincent's method.
Below
Below may refer to:
*Earth
*Ground (disambiguation)
*Soil
*Floor
*Bottom (disambiguation)
Bottom may refer to:
Anatomy and sex
* Bottom (BDSM), the partner in a BDSM who takes the passive, receiving, or obedient role, to that of the top or ...
there is an explanation of how this drawback is overcome.
Disappearance of Vincent's theorem
Vincent was the last author in the 19th century to use his theorem for the
isolation of the real roots of a polynomial.
The reason for that was the appearance of
Sturm's theorem
In mathematics, the Sturm sequence of a univariate polynomial is a sequence of polynomials associated with and its derivative by a variant of Euclid's algorithm for polynomials. Sturm's theorem expresses the number of distinct real roots of loca ...
in 1827, which solved the
real root isolation problem in
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
time, by defining the precise number of real roots a polynomial has in a real open interval (''a'', ''b''). The resulting (Sturm's) method for computing the real roots of polynomials has been the only one widely known and used ever since—up to about 1980, when it was replaced (in almost all
computer algebra system
A computer algebra system (CAS) or symbolic algebra system (SAS) is any mathematical software with the ability to manipulate mathematical expressions in a way similar to the traditional manual computations of mathematicians and scientists. The de ...
s) by
methods derived from Vincent's theorem, the fastest one being the
Vincent–Akritas–Strzeboński (VAS) method.
Serret included in his Algebra,
pp 363–368,
Vincent's theorem In mathematics, Vincent's theorem—named after Alexandre Joseph Hidulphe Vincent—is a theorem that isolates the real roots of polynomials with rational coefficients.
Even though Vincent's theorem is the basis of the fastest method for the isola ...
along with its proof and directed all interested readers to Vincent's papers for examples on how it is used. Serret was the last author to mention
Vincent's theorem In mathematics, Vincent's theorem—named after Alexandre Joseph Hidulphe Vincent—is a theorem that isolates the real roots of polynomials with rational coefficients.
Even though Vincent's theorem is the basis of the fastest method for the isola ...
in the 19th century.
Comeback of Vincent's theorem
In the 20th century
Vincent's theorem In mathematics, Vincent's theorem—named after Alexandre Joseph Hidulphe Vincent—is a theorem that isolates the real roots of polynomials with rational coefficients.
Even though Vincent's theorem is the basis of the fastest method for the isola ...
cannot be found in any of the theory of equations books; the only exceptions are the books by
Uspensky and
Obreschkoff,
where in the second there is just the statement of the theorem.
It was in
Uspensky's book
that Akritas found
Vincent's theorem In mathematics, Vincent's theorem—named after Alexandre Joseph Hidulphe Vincent—is a theorem that isolates the real roots of polynomials with rational coefficients.
Even though Vincent's theorem is the basis of the fastest method for the isola ...
and made it the topic of his Ph.D. Thesis "Vincent's Theorem in Algebraic Manipulation",
North Carolina State University, USA, 1978. A major achievement at the time was getting hold of Vincent's original paper of 1836, something that had eluded
Uspensky—resulting thus in a
great misunderstanding. Vincent's original paper of 1836 was made available to Akritas through the commendable efforts (interlibrary loan) of a librarian in the Library of the
University of Wisconsin–Madison, USA.
Real root isolation methods derived from Vincent's theorem
Isolation of the real roots of a polynomial is the process of finding open disjoint intervals such that each contains exactly one real root and every real root is contained in some interval. According to the French school of mathematics of the 19th century, this is the first step in computing the real roots, the second being their approximation to any degree of accuracy; moreover, the focus is on the positive roots, because to isolate the negative roots of the polynomial ''p''(''x'') replace ''x'' by −''x'' (''x'' ← −''x'') and repeat the process.
The
continued fractions
In mathematics, a continued fraction is an expression obtained through an iterative process of representing a number as the sum of its integer part and the reciprocal of another number, then writing this other number as the sum of its integer ...
version of
Vincent's theorem In mathematics, Vincent's theorem—named after Alexandre Joseph Hidulphe Vincent—is a theorem that isolates the real roots of polynomials with rational coefficients.
Even though Vincent's theorem is the basis of the fastest method for the isola ...
can be used to isolate the positive roots of a given polynomial ''p''(''x'') of degree deg(''p''). To see this, represent by the
Möbius transformation
In geometry and complex analysis, a Möbius transformation of the complex plane is a rational function of the form
f(z) = \frac
of one complex variable ''z''; here the coefficients ''a'', ''b'', ''c'', ''d'' are complex numbers satisfying ''ad'' ...
:
the continued fraction that leads to a transformed polynomial with one
sign variation
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.
A similar theorem was publishe ...
in the sequence of its coefficients. Then, the single positive root of ''f''(''x'') (in the interval (0, ∞)) corresponds to ''that'' positive root of ''p''(''x'') that is in the open interval with endpoints
and
. These endpoints are ''not'' ordered and correspond to ''M''(0) and ''M''(∞) respectively.
Therefore, to isolate the positive roots of a polynomial, all that must be done is to compute—for ''each'' root—the variables ''a'', ''b'', ''c'', ''d'' of the corresponding
Möbius transformation
In geometry and complex analysis, a Möbius transformation of the complex plane is a rational function of the form
f(z) = \frac
of one complex variable ''z''; here the coefficients ''a'', ''b'', ''c'', ''d'' are complex numbers satisfying ''ad'' ...
:
that leads to a transformed polynomial as in equation (), with one
sign variation
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.
A similar theorem was publishe ...
in the sequence of its coefficients.
Crucial Observation: The variables ''a'', ''b'', ''c'', ''d'' of a
Möbius transformation
In geometry and complex analysis, a Möbius transformation of the complex plane is a rational function of the form
f(z) = \frac
of one complex variable ''z''; here the coefficients ''a'', ''b'', ''c'', ''d'' are complex numbers satisfying ''ad'' ...
:
(in
Vincent's theorem In mathematics, Vincent's theorem—named after Alexandre Joseph Hidulphe Vincent—is a theorem that isolates the real roots of polynomials with rational coefficients.
Even though Vincent's theorem is the basis of the fastest method for the isola ...
) leading to a transformed polynomial—as in equation ()—with one
sign variation
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.
A similar theorem was publishe ...
in the sequence of its coefficients can be computed:
*either by ''
continued fractions
In mathematics, a continued fraction is an expression obtained through an iterative process of representing a number as the sum of its integer part and the reciprocal of another number, then writing this other number as the sum of its integer ...
'', leading to the ''
Vincent–Akritas–Strzebonski (VAS)'' continued fractions method,
*or by ''
bisection
In geometry, bisection is the division of something into two equal or congruent parts, usually by a line, which is then called a ''bisector''. The most often considered types of bisectors are the ''segment bisector'' (a line that passes through ...
'', leading to (among others) the ''
Vincent–Collins–Akritas (VCA)'' bisection method.
The "bisection part" of this all important observation appeared as a special
theorem
In mathematics, a theorem is a statement that has been proved, or can be proved. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to establish that the theorem is a logical consequence of th ...
in the papers by Alesina and Galuzzi.
All methods described below (see the article on
Budan's theorem
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.
A similar theorem was publishe ...
for their historical background) need to compute (once) an upper bound, ''ub'', on the values of the positive roots of the polynomial under consideration. Exception is the
VAS method where additionally lower bounds, ''lb'', must be computed at almost every cycle of the main loop. To compute the lower bound ''lb'' of the polynomial ''p''(''x'') compute the upper bound ''ub'' of the polynomial
and set
.
Excellent (upper and lower) bounds on the values of just the positive roots of polynomials have been developed by Akritas, Strzeboński and Vigklas based on previous work by Doru Stefanescu. They are described in P. S. Vigklas' Ph.D. Thesis
and elsewhere.
These bounds have already been implemented in the
computer algebra system
A computer algebra system (CAS) or symbolic algebra system (SAS) is any mathematical software with the ability to manipulate mathematical expressions in a way similar to the traditional manual computations of mathematicians and scientists. The de ...
s
Mathematica
Wolfram Mathematica is a software system with built-in libraries for several areas of technical computing that allow machine learning, statistics, symbolic computation, data manipulation, network analysis, time series analysis, NLP, optimizat ...
,
SageMath
SageMath (previously Sage or SAGE, "System for Algebra and Geometry Experimentation") is a computer algebra system (CAS) with features covering many aspects of mathematics, including algebra, combinatorics, graph theory, numerical analysis, numbe ...
,
SymPy,
Xcas
Xcas is a user interface to Giac, which is an open source computer algebra system (CAS) for Windows, macOS and Linux among many other platforms. Xcas is written in C++. Giac can be used directly inside software written in C++.
Xcas has a com ...
etc.
All three methods described below follow the excellent presentation of François Boulier,
p. 24.
Continued fractions method
Only one
continued fractions
In mathematics, a continued fraction is an expression obtained through an iterative process of representing a number as the sum of its integer part and the reciprocal of another number, then writing this other number as the sum of its integer ...
method derives from
Vincent's theorem In mathematics, Vincent's theorem—named after Alexandre Joseph Hidulphe Vincent—is a theorem that isolates the real roots of polynomials with rational coefficients.
Even though Vincent's theorem is the basis of the fastest method for the isola ...
. As stated
above, it started in the 1830s when Vincent presented, in the papers
several examples that show how to use his theorem to
isolate the real roots of polynomials with
continued fractions
In mathematics, a continued fraction is an expression obtained through an iterative process of representing a number as the sum of its integer part and the reciprocal of another number, then writing this other number as the sum of its integer ...
. However the resulting method had
exponential
Exponential may refer to any of several mathematical topics related to exponentiation, including:
*Exponential function, also:
**Matrix exponential, the matrix analogue to the above
* Exponential decay, decrease at a rate proportional to value
*Exp ...
computing time. Below is an explanation of how this method evolved.
Vincent–Akritas–Strzeboński (VAS, 2005)
This is the second method (after
VCA) developed to handle the
exponential
Exponential may refer to any of several mathematical topics related to exponentiation, including:
*Exponential function, also:
**Matrix exponential, the matrix analogue to the above
* Exponential decay, decrease at a rate proportional to value
*Exp ...
behavior of Vincent's method.
The VAS continued fractions method is a ''direct'' implementation of Vincent's theorem. It was originally presented by Vincent from 1834 to 1938 in the papers
in a exponential form; namely, Vincent computed each partial
quotient
In arithmetic, a quotient (from lat, quotiens 'how many times', pronounced ) is a quantity produced by the division of two numbers. The quotient has widespread use throughout mathematics, and is commonly referred to as the integer part of a ...
''a
i'' by a series of ''unit'' increments ''a
i'' ← ''a
i'' + 1, which are equivalent to substitutions of the form ''x'' ← ''x'' + 1.
Vincent's method was converted into its
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
complexity form by Akritas, who in his 1978 Ph.D. Thesis (''Vincent's theorem in algebraic manipulation'', North Carolina State University, USA) computed each partial
quotient
In arithmetic, a quotient (from lat, quotiens 'how many times', pronounced ) is a quantity produced by the division of two numbers. The quotient has widespread use throughout mathematics, and is commonly referred to as the integer part of a ...
''a
i'' as the lower bound, ''lb'', on the values of the positive roots of a polynomial. This is called the ''ideal'' positive lower root bound that computes the integer part of the smallest positive root (see the corresponding figure). To wit, now set ''a
i'' ← ''lb'' or, equivalently, perform the substitution ''x'' ← ''x'' + ''lb'', which takes about the same time as the substitution ''x'' ← ''x'' + 1.
![VAS method example](https://upload.wikimedia.org/wikipedia/commons/2/2e/VAS_method_example.jpg)
Finally, since the ideal positive lower root bound does not exist, Strzeboński
introduced in 2005 the substitution
, whenever
; in general
and the value 16 was determined experimentally. Moreover, it has been shown
that the VAS (
continued fractions
In mathematics, a continued fraction is an expression obtained through an iterative process of representing a number as the sum of its integer part and the reciprocal of another number, then writing this other number as the sum of its integer ...
) method is faster than the fastest implementation of the VCA (bisection) method,
a fact that was confirmed
independently; more precisely, for the Mignotte polynomials of high degree VAS is about 50,000 times faster than the fastest implementation of VCA.
In 2007, Sharma
removed the hypothesis of the ideal positive lower bound and proved that VAS is still
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
in time.
VAS is the default algorithm for root isolation in
Mathematica
Wolfram Mathematica is a software system with built-in libraries for several areas of technical computing that allow machine learning, statistics, symbolic computation, data manipulation, network analysis, time series analysis, NLP, optimizat ...
,
SageMath
SageMath (previously Sage or SAGE, "System for Algebra and Geometry Experimentation") is a computer algebra system (CAS) with features covering many aspects of mathematics, including algebra, combinatorics, graph theory, numerical analysis, numbe ...
,
SymPy,
Xcas
Xcas is a user interface to Giac, which is an open source computer algebra system (CAS) for Windows, macOS and Linux among many other platforms. Xcas is written in C++. Giac can be used directly inside software written in C++.
Xcas has a com ...
.
For a comparison between Sturm's method and VAS use the functions realroot(poly) and time(realroot(poly)) of
Xcas
Xcas is a user interface to Giac, which is an open source computer algebra system (CAS) for Windows, macOS and Linux among many other platforms. Xcas is written in C++. Giac can be used directly inside software written in C++.
Xcas has a com ...
. By default, to isolate the real roots of poly realroot uses the VAS method; to use Sturm's method write realroot(sturm, poly). See also the
External links
An internal link is a type of hyperlink on a web page to another page or resource, such as an image or document, on the same website or domain.
Hyperlinks are considered either "external" or "internal" depending on their target or destination ...
for an application by A. Berkakis for Android devices that does the same thing.
Here is how VAS(''p'', ''M'') works, where for simplicity Strzeboński's contribution is not included:
*Let ''p''(''x'') be a polynomial of degree deg(''p'') such that ''p''(0) ≠ 0. To isolate its positive roots, associate with ''p''(''x'') the
Möbius transformation
In geometry and complex analysis, a Möbius transformation of the complex plane is a rational function of the form
f(z) = \frac
of one complex variable ''z''; here the coefficients ''a'', ''b'', ''c'', ''d'' are complex numbers satisfying ''ad'' ...
''M''(''x'') = ''x'' and repeat the following steps while there are pairs to be processed.
*Use
Descartes' rule of signs
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 i ...
on ''p''(''x'') to compute, if possible, (using the number ''var'' of
sign variations in the sequence of its coefficients) the number of its roots inside the interval (0, ∞). If there are no roots return the empty set, ∅ whereas if there is one root return the interval (''a'', ''b''), where ''a'' = min(''M''(0), ''M''(∞)), and ''b'' = max(''M''(0), ''M''(∞)); if ''b'' = ∞ set ''b'' = ''ub'', where ''ub'' is an upper bound on the values of the positive roots of ''p''(''x'').
*If there are two or more sign variations
Descartes' rule of signs
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 i ...
implies that there may be zero, one or more real roots inside the interval (0, ∞); in this case consider separately the roots of ''p''(''x'') that lie inside the interval (0, 1) from those inside the interval (1, ∞). A special test must be made for 1.
**To guarantee that there are roots inside the interval (0, 1) the ideal lower bound, ''lb'' is used; that is the integer part of the smallest positive root is computed with the help of the lower bound,
, on the values of the positive roots of ''p''(''x''). If
, the substitution
is performed to ''p''(''x'') and ''M''(''x''), whereas if
use substitution(s) ''x'' ← ''x''+1 to find the integer part of the root(s).
**To compute the roots inside the interval (0, 1) perform the substitution
to ''p''(''x'') and ''M''(''x'') and process the pair
:::
::whereas to compute the roots in the interval (1, ∞) perform the substitution ''x'' ← ''x'' + 1 to ''p''(''x'') and ''M''(''x'') and process the pair . It may well turn out that 1 is a root of ''p''(''x''), in which case, ''M''(1) is a root of the original polynomial and the isolation interval reduces to a point.
Below is a
recursive
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
presentation of VAS(''p'', ''M'').
VAS(''p'', ''M''):
Input: A univariate, square-free polynomial
, of degree deg(''p''), and the
Möbius transformation
In geometry and complex analysis, a Möbius transformation of the complex plane is a rational function of the form
f(z) = \frac
of one complex variable ''z''; here the coefficients ''a'', ''b'', ''c'', ''d'' are complex numbers satisfying ''ad'' ...
:
Output: A list of isolating intervals of the positive roots of ''p''(''x'').
1 ''var'' ← the number of
sign variations of ''p''(''x'') //
Descartes' rule of signs
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 i ...
;
2 if ''var'' = 0 then RETURN ∅;
3 if ''var'' = 1 then RETURN // ''a'' = min(''M''(0), ''M''(∞)), ''b'' = max(''M''(0), ''M''(∞)), but if ''b'' = ∞ set ''b'' = ''ub'', where ''ub'' is an upper bound on the values of the positive roots of ''p''(''x'');
4 ''lb'' ← the ''ideal'' lower bound on the positive roots of ''p''(''x'');
5 if ''lb'' ≥ 1 then ''p'' ← ''p''(''x'' + ''lb''), ''M'' ← ''M''(''x'' + ''lb'');
6 ''p''
01 ← (''x'' + 1)
deg(''p'') ''p''(), ''M''
01 ← ''M''() // Look for real roots in (0, 1);
7 ''m'' ← ''M''(1) // Is 1 a root?
8 ''p''
1∞ ← ''p''(''x'' + 1), ''M''
1∞ ← ''M''(''x'' + 1) // Look for real roots in (1, ∞);
9 if ''p''(1) ≠ 0 then
10 RETURN VAS(''p''
01, ''M''
01) ∪ VAS(''p''
1∞, ''M''
1∞)
11 else
12 RETURN VAS(''p''
01, ''M''
01) ∪ ∪ VAS(''p''
1∞, ''M''
1∞)
13 end
Remarks
*For simplicity Strzeboński's contribution is not included.
*In the above algorithm with each polynomial there is associated a
Möbius transformation
In geometry and complex analysis, a Möbius transformation of the complex plane is a rational function of the form
f(z) = \frac
of one complex variable ''z''; here the coefficients ''a'', ''b'', ''c'', ''d'' are complex numbers satisfying ''ad'' ...
''M''(''x'').
*In line 1
Descartes' rule of signs
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 i ...
is applied.
*If lines 4 and 5 are removed from VAS(''p'', ''M'') the resulting algorithm is Vincent's exponential one.
*Any substitution performed on the polynomial ''p''(''x'') is also performed on the associated
Möbius transformation
In geometry and complex analysis, a Möbius transformation of the complex plane is a rational function of the form
f(z) = \frac
of one complex variable ''z''; here the coefficients ''a'', ''b'', ''c'', ''d'' are complex numbers satisfying ''ad'' ...
''M''(''x'') (lines 5 6 and 8).
*The isolating intervals are computed from the
Möbius transformation
In geometry and complex analysis, a Möbius transformation of the complex plane is a rational function of the form
f(z) = \frac
of one complex variable ''z''; here the coefficients ''a'', ''b'', ''c'', ''d'' are complex numbers satisfying ''ad'' ...
in line 3, except for integer roots computed in line 7 (also 12).
Example of VAS(''p'', ''M'')
We apply the VAS method to (note that: ).
Iteration 1
VAS(''x''
3 − 7''x'' + 7, ''x'')
1 ''var'' ← 2 // the number of
sign variation
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.
A similar theorem was publishe ...
s in the sequence of coefficients of ''p''(''x'') = ''x''
3 − 7''x'' + 7
4 ''lb'' ← 1 // the ideal lower bound—found using ''lb
computed'' and substitution(s) ''x'' ← ''x'' + 1
5 ''p'' ← ''x''
3 + 3''x''
2 − 4''x'' + 1, ''M'' ← ''x'' + 1
6 ''p''
01 ← ''x''
3 − ''x''
2 − 2''x'' + 1, ''M''
01 ←
7 ''m'' ← 1
8 ''p''
1∞ ← ''x''
3 + 6''x''
2 + 5''x'' + 1, ''M''
1∞ ← ''x'' + 2
10 RETURN VAS(''x''
3 − ''x''
2 − 2''x'' + 1, ) ∪ VAS(''x''
3 + 6''x''
2 + 5''x'' + 1, ''x'' + 2)
List of isolation intervals:
List of pairs to be processed:
:
Remove the first and process it.
Iteration 2
VAS(''x''
3 − ''x''
2 − 2''x'' + 1, )
1 ''var'' ← 2 // the number of
sign variation
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.
A similar theorem was publishe ...
s in the sequence of coefficients of ''p''(''x'') = ''x''
3 − ''x''
2 − 2''x'' + 1
4 ''lb'' ← 0 // the ideal lower bound—found using ''lb
computed'' and substitution(s) ''x'' ← ''x'' + 1
6 ''p''
01 ← ''x''
3 + ''x''
2 − 2''x'' − 1, ''M''
01 ←
7 ''m'' ←
8 ''p''
1∞ ← ''x''
3 + 2''x''
2 − ''x'' − 1, ''M''
1∞ ←
10 RETURN VAS(''x''
3 + ''x''
2 − 2''x'' − 1, ) ∪ VAS(''x''
3 + 2''x''
2 − ''x'' − 1, )
List of isolation intervals:
List of pairs to be processed:
:
Remove the first and process it.
Iteration 3
VAS(''x''
3 + ''x''
2 − 2''x'' − 1, )
1 ''var'' ← 1 // the number of
sign variation
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.
A similar theorem was publishe ...
s in the sequence of coefficients of ''p''(''x'') = ''x''
3 + ''x''
2 − 2''x'' − 1
3 RETURN
List of isolation intervals:
List of pairs to be processed:
:
Remove the first and process it.
Iteration 4
VAS(''x''
3 + 2''x''
2 − ''x'' − 1, )
1 ''var'' ← 1 // the number of
sign variation
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.
A similar theorem was publishe ...
s in the sequence of coefficients of ''p''(''x'') = ''x''
3 + 2''x''
2 − ''x'' − 1
3 RETURN
List of isolation intervals:
List of pairs to be processed:
:
Remove the first and process it.
Iteration 5
VAS(''x''
3 + 6''x''
2 + 5''x'' + 1, ''x'' + 2)
1 ''var'' ← 0 // the number of
sign variation
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.
A similar theorem was publishe ...
s in the sequence of coefficients of ''p''(''x'') = ''x''
3 + 6''x''
2 + 5''x'' + 1
2 RETURN ∅
List of isolation intervals:
List of pairs to be processed: .
Finished.
Conclusion
Therefore, the two positive roots of the polynomial lie inside the isolation intervals and }. Each root can be approximated by (for example) bisecting the isolation interval it lies in until the difference of the endpoints is smaller than ; following this approach, the roots turn out to be and .
Bisection methods
There are various
bisection method
In mathematics, the bisection method is a root-finding method that applies to any continuous function for which one knows two values with opposite signs. The method consists of repeatedly bisecting the interval defined by these values and the ...
s derived from
Vincent's theorem In mathematics, Vincent's theorem—named after Alexandre Joseph Hidulphe Vincent—is a theorem that isolates the real roots of polynomials with rational coefficients.
Even though Vincent's theorem is the basis of the fastest method for the isola ...
; they are all presented and compared elsewhere.
Here the two most important of them are described, namely, the
Vincent–Collins–Akritas (VCA) method and the
Vincent–Alesina–Galuzzi (VAG) method.
The
Vincent–Alesina–Galuzzi (VAG) method is the simplest of all methods derived from Vincent's theorem but has the most time consuming test (in line 1) to determine if a polynomial has roots in the interval of interest; this makes it the slowest of the methods presented in this article.
By contrast, the
Vincent–Collins–Akritas (VCA) method is more complex but uses a simpler test (in line 1) than
VAG. This along with certain improvements
have made
VCA the fastest bisection method.
Vincent–Collins–Akritas (VCA, 1976)
This was the first method developed to overcome the
exponential
Exponential may refer to any of several mathematical topics related to exponentiation, including:
*Exponential function, also:
**Matrix exponential, the matrix analogue to the above
* Exponential decay, decrease at a rate proportional to value
*Exp ...
nature of Vincent's
original approach, and has had quite an interesting history as far as its name is concerned. This method, which isolates the real roots, using Descartes' rule of signs and
Vincent's theorem In mathematics, Vincent's theorem—named after Alexandre Joseph Hidulphe Vincent—is a theorem that isolates the real roots of polynomials with rational coefficients.
Even though Vincent's theorem is the basis of the fastest method for the isola ...
, had been originally called ''modified Uspensky's algorithm'' by its inventors Collins and Akritas.
After going through names like "Collins–Akritas method" and "Descartes' method" (too confusing if ones considers Fourier's article
), it was finally François Boulier, of Lille University, who gave it the name ''Vincent–Collins–Akritas'' (VCA) method,
p. 24, based on the fact that "Uspensky's method" does not exist
and neither does "Descartes' method".
The best implementation of this method is due to Rouillier and Zimmerman,
and to this date, it is the fastest bisection method. It has the same worst case
complexity
Complexity characterises the behaviour of a system or model whose components interaction, interact in multiple ways and follow local rules, leading to nonlinearity, randomness, collective dynamics, hierarchy, and emergence.
The term is generall ...
as Sturm's algorithm, but is almost always much faster. It has been implemented in
Maple
''Acer'' () is a genus of trees and shrubs commonly known as maples. The genus is placed in the family Sapindaceae.Stevens, P. F. (2001 onwards). Angiosperm Phylogeny Website. Version 9, June 2008 nd more or less continuously updated since http ...
's RootFinding package.
Here is how VCA(''p'', (''a'', ''b'')) works:
*Given a polynomial ''p''
orig(''x'') of degree deg(''p''), such that ''p''
orig(0) ≠ 0, whose positive roots must be isolated, first compute an upper bound,
''ub'' on the values of these positive roots and set ''p''(''x'') = ''p''
orig(''ub'' * ''x'') and (''a'', ''b'') = (0, ''ub''). The positive roots of ''p''(''x'') all lie in the interval (0, 1) and there is a
bijection
In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...
between them and the roots of ''p''
orig(''x''), which all lie in the interval (''a'', ''b'') = (0, ''ub'') (see the corresponding figure); this
bijection
In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...
is expressed by ''α''
(''a'',''b'') = ''a'' +''α''
(0,1)(''b'' − ''a''). Likewise, there is a
bijection
In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...
between the intervals (0, 1) and (0, ''ub'').
![VCA Algorithm](https://upload.wikimedia.org/wikipedia/commons/4/4b/VCA_Algorithm.jpg)
*Repeat the following steps while there are pairs to be processed.
*Use Budan's
"0_1 roots test" on ''p''(''x'') to compute (using the number ''var'' of
sign variations in the sequence of its coefficients) the number of its roots inside the interval (0, 1). If there are no roots return the empty set, ∅ and if there is one root return the interval (''a'', ''b'').
*If there are two or more sign variations Budan's
"0_1 roots test" implies that there may be zero, one, two or more real roots inside the interval (0, 1). In this case cut it in half and consider separately the roots of ''p''(''x'') inside the interval (0, )—and that correspond to the roots of ''p''
orig(''x'') inside the interval (''a'', (''a'' + ''b'')) from those inside the interval (, 1) and correspond to the roots of ''p''
orig(''x'') inside the interval ((''a'' + ''b''), ''b''); that is, process, respectively, the pairs
::
:(see the corresponding figure). It may well turn out that is a root of ''p''(''x''), in which case (''a'' + ''b'') is a root of ''p''
orig(''x'') and the isolation interval reduces to a point.
![VCA Example](https://upload.wikimedia.org/wikipedia/commons/b/be/VCA_Example.jpg)
Below is a
recursive
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
presentation of the original algorithm VCA(''p'', (''a'', ''b'')).
VCA(''p'', (''a'', ''b''))
Input: A univariate, square-free polynomial ''p''(''ub'' * ''x'') ∈ Z
'x'' ''p''(0) ≠ 0 of degree deg(''p''), and the open interval (''a'', ''b'') = (0, ''ub''), where ''ub'' is an upper bound on the values of the positive roots of ''p''(''x''). (The positive roots of ''p''(''ub'' * ''x'') are all in the open interval (0, 1)).
Output: A list of isolating intervals of the positive roots of ''p''(''x'')
1 ''var'' ← the number of
sign variation
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.
A similar theorem was publishe ...
s of (''x'' + 1)
deg(''p'')''p''() // Budan's
"0_1 roots test";
2 if ''var'' = 0 then RETURN ∅;
3 if ''var'' = 1 then RETURN ;
4 ''p''
0 ← 2
deg(''p'')''p''() // Look for real roots in (0, );
5 ''m'' ← (''a'' + ''b'') // Is a root?
6 ''p''
1 ← 2
deg(''p'')''p''() // Look for real roots in (, 1);
7 if ''p''() ≠ 0 then
8 RETURN VCA (''p''
0, (''a'', ''m'')) ∪ VCA (''p''
1, (''m'', ''b''))
9 else
10 RETURN VCA (''p''
0, (''a'', ''m'')) ∪ ∪ VCA (''p''
1, (''m'', ''b''))
11 end
Remark
*In the above algorithm with each polynomial there is associated an interval (''a'', ''b''). As shown elsewhere,
p. 11, a
Möbius transformation
In geometry and complex analysis, a Möbius transformation of the complex plane is a rational function of the form
f(z) = \frac
of one complex variable ''z''; here the coefficients ''a'', ''b'', ''c'', ''d'' are complex numbers satisfying ''ad'' ...
can also be associated with each polynomial in which case VCA looks more like
VAS.
*In line 1 Budan's
"0_1 roots test" is applied.
Example of VCA(''p'', (''a'',''b''))
Given the polynomial and considering as an upper bound
on the values of the positive roots the arguments of the VCA method are: and .
Iteration 1
1 ''var'' ← 2 // the number of
sign variation
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.
A similar theorem was publishe ...
s in the sequence of coefficients of (''x'' + 1)
3''p''() = 7''x''
3 − 7''x''
2 − 35''x'' + 43
4 ''p''
0 ← 64''x''
3 − 112''x'' + 56
5 ''m'' ← 2
6 ''p''
1 ← 64''x''
3 + 192''x''
2 + 80''x'' + 8
7 ''p''() = 1
8 RETURN VCA(64''x''
3 − 112''x'' + 56, (0, 2)) ∪ VCA(64''x''
3 + 192''x''
2 + 80''x'' + 8, (2, 4))
List of isolation intervals:
List of pairs to be processed:
:
Remove the first and process it.
Iteration 2
VCA(64''x''
3 − 112''x'' + 56, (0, 2))
1 ''var'' ← 2 // the number of
sign variation
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.
A similar theorem was publishe ...
s in the sequence of coefficients of (''x'' + 1)
3''p''() = 56''x''
3 + 56''x''
2 − 56''x'' + 8
4 ''p''
0 ← 64''x''
3 − 448''x'' + 448
5 ''m'' ← 1
6 ''p''
1 ← 64''x''
3 + 192''x''
2 − 256''x'' + 64
7 ''p''() = 8
8 RETURN VCA(64''x''
3 − 448''x'' + 448, (0, 1)) ∪ VCA(64''x''
3 + 192''x''
2 − 256''x'' + 64, (1, 2))
List of isolation intervals:
List of pairs to be processed:
:
Remove the first and process it.
Iteration 3
VCA(64''x''
3 − 448''x'' + 448, (0, 1))
1 ''var'' ← 0 // the number of
sign variation
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.
A similar theorem was publishe ...
s in the sequence of coefficients of (''x'' + 1)
3''p''() = 448''x''
3 + 896''x''
2 + 448''x'' + 64
2 RETURN ∅
List of isolation intervals:
List of pairs to be processed:
:
Remove the first and process it.
Iteration 4
VCA(64''x''
3 + 192''x''
2 − 256''x'' + 64, (1, 2))
1 ''var'' ← 2 // the number of
sign variation
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.
A similar theorem was publishe ...
s in the sequence of coefficients of (''x'' + 1)
3''p''() = 64''x''
3 − 64''x''
2 − 128''x'' + 64
4 ''p''
0 ← 64''x''
3 + 384''x''
2 − 1024''x'' + 512
5 ''m'' ←
6 ''p''
1 ← 64''x''
3 + 576''x''
2 − 64''x'' + 64
7 ''p''() = −8
8 RETURN VCA(64''x''
3 + 384''x''
2 − 1024''x'' + 512, (1, )) ∪ VCA(64''x''
3 + 576''x''
2 − 64''x'' − 64, (, 2))
List of isolation intervals:
List of pairs to be processed:
:
Remove the first and process it.
Iteration 5
VCA(64''x''
3 + 384''x''
2 − 1024''x'' + 512, (1, ))
1 ''var'' ← 1 // the number of
sign variation
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.
A similar theorem was publishe ...
s in the sequence of coefficients of (''x'' + 1)
3''p''() = 512''x''
3 + 512''x''
2 − 128''x'' − 64
3 RETURN
List of isolation intervals:
List of pairs to be processed:
:
Remove the first and process it.
Iteration 6
VCA(64''x''
3 + 576''x''
2 − 64''x'' − 64, (, 2))
1 ''var'' ← 1 // the number of
sign variation
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.
A similar theorem was publishe ...
s in the sequence of coefficients of (''x'' + 1)
3''p''() = −64''x''
3 − 256''x''
2 + 256''x'' + 512
3 RETURN
List of isolation intervals:
List of pairs to be processed:
:
Remove the first and process it.
Iteration 7
VCA(64''x''
3 + 192''x''
2 + 80''x'' + 8, (2, 4))
1 ''var'' ← 0 // the number of
sign variation
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.
A similar theorem was publishe ...
s in the sequence of coefficients of (''x'' + 1)
3''p''() = 8''x''
3 + 104''x''
2 + 376''x'' + 344
2 RETURN ∅
List of isolation intervals:
List of pairs to be processed: .
Finished.
Conclusion
Therefore, the two positive roots of the polynomial lie inside the isolation intervals and }. Each root can be approximated by (for example) bisecting the isolation interval it lies in until the difference of the endpoints is smaller than ; following this approach, the roots turn out to be and .
Vincent–Alesina–Galuzzi (VAG, 2000)
This was developed last and is the simplest
real root isolation method derived from
Vincent's theorem In mathematics, Vincent's theorem—named after Alexandre Joseph Hidulphe Vincent—is a theorem that isolates the real roots of polynomials with rational coefficients.
Even though Vincent's theorem is the basis of the fastest method for the isola ...
.
Here is how VAG(''p'', (''a'', ''b'')) works:
*Given a polynomial ''p''(''x'') of degree deg(''p''), such that ''p''(0) ≠ 0, whose positive roots must be isolated, first compute an upper bound,
''ub'' on the values of these positive roots and set (''a'', ''b'') = (0, ''ub''). The positive roots of ''p''(''x'') all lie in the interval (''a'', ''b'').
*Repeat the following steps while there are intervals (''a'', ''b'') to be processed; in this case the polynomial ''p''(''x'') stays the same.
*Use the Alesina–Galuzzi
"a_b roots test" on ''p''(''x'') to compute (using the number ''var'' of
sign variations in the sequence of its coefficients) the number of its roots inside the interval (''a'', ''b''). If there are no roots return the empty set, ∅ and if there is one root return the interval (''a'', ''b'').
*If there are two or more sign variations the Alesina–Galuzzi
"a_b roots test" implies that there may be zero, one, two or more real roots inside the interval (''a'', ''b''). In this case cut it in half and consider separately the roots of ''p''(''x'') inside the interval (''a'', (''a'' + ''b'')) from those inside the interval ((''a'' + ''b''), ''b''); that is, process, respectively, the intervals (''a'', (''a'' + ''b'')) and ((''a'' + ''b''), ''b''). It may well turn out that (''a'' + ''b'') is a root of ''p''(''x''), in which case the isolation interval reduces to a point.
Below is a
recursive
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
presentation of VAG(''p'', (''a'', ''b'')).
VAG(''p'', (''a'', ''b''))
Input: A univariate, square-free polynomial ''p''(''x'') ∈ Z
'x'' ''p''(0) ≠ 0 of degree deg(''p'') and the open interval (''a'', ''b'') = (0, ''ub''), where ''ub'' is an upper bound on the values of the positive roots of ''p''(''x'').
Output: A list of isolating intervals of the positive roots of ''p''(''x'').
1 ''var'' ← the number of
sign variation
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.
A similar theorem was publishe ...
s of (''x'' + 1)
deg(''p'') ''p''() // The Alesina–Galuzzi
"a_b roots test";
2 if ''var'' = 0 then RETURN ∅;
3 if ''var'' = 1 then RETURN ;
4 ''m'' ← (''a'' + ''b'') // Subdivide the interval (''a'', ''b'') in two equal parts;
5 if ''p''(''m'') ≠ 0 then
6 RETURN VAG(''p'', (''a'', ''m'')) ∪ VAG(''p'', (''m'', ''b''))
7 else
8 RETURN VAG(''p'', (''a'', ''m'')) ∪ ∪ VAG(''p'', (''m'', ''b''))
9 end
Remarks
*Compared to
VCA the above algorithm is extremely simple; by contrast, VAG uses the time consuming
"a_b roots test" and that makes it much slower than
VCA.
*As Alesina and Galuzzi point out,
p. 189, there is a variant of this algorithm due to Donato Saeli. Saeli suggested that the ''
mediant In music, the mediant (''Latin'': to be in the middle) is the third scale degree () of a diatonic scale, being the note halfway between the tonic and the dominant.Benward & Saker (2003), p.32. In the movable do solfège system, the mediant note i ...
'' of the endpoints be used instead of their midpoint . However, it has been shown
that using the
mediant In music, the mediant (''Latin'': to be in the middle) is the third scale degree () of a diatonic scale, being the note halfway between the tonic and the dominant.Benward & Saker (2003), p.32. In the movable do solfège system, the mediant note i ...
of the endpoints is in general much slower than the "mid-point" version.
Example of VAG(''p'', (''a'',''b''))
Given the polynomial ''p''(''x'') = ''x''
3 − 7''x'' + 7 and considering as an upper bound
on the values of the positive roots ''ub'' = 4 the arguments of VAG are: ''p''(''x'') = ''x''
3 − 7''x'' + 7 and (''a'', ''b'') = (0, 4).
Iteration 1
1 ''var'' ← 2 // the number of
sign variation
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.
A similar theorem was publishe ...
s in the sequence of coefficients of (''x'' + 1)
3''p''() = 43''x''
3 − 35''x''
2 − 7''x'' + 7
4 ''m'' ← (0 + 4) = 2
5 ''p''(''m'') = 1
8 RETURN VAG(''x''
3 − 7''x'' + 7, (0, 2)) ∪ VAG(''x''
3 − 7''x'' + 7, (2, 4)
List of isolation intervals: .
List of intervals to be processed: .
Remove the first and process it.
Iteration 2
VAG(''x''
3 − 7''x'' + 7, (0, 2))
1 ''var'' ← 2 // the number of
sign variation
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.
A similar theorem was publishe ...
s in the sequence of coefficients of (''x'' + 1)
3''p''() = ''x''
3 − 7''x''
2 + 7''x'' + 7
4 ''m'' ← (0 + 2) = 1
5 ''p''(''m'') = 1
8 RETURN VAG(''x''
3 − 7''x'' + 7, (0, 1)) ∪ VAG(''x''
3 − 7''x'' + 7, (1, 2)
List of isolation intervals: .
List of intervals to be processed: .
Remove the first and process it.
Iteration 3
VAG(''x''
3 − 7''x'' + 7, (0, 1))
1 ''var'' ← 0 // the number of
sign variation
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.
A similar theorem was publishe ...
s in the sequence of coefficients of (''x'' + 1)
3''p''() = ''x''
3 + 7''x''
2 + 14''x'' + 7
2 RETURN ∅
List of isolation intervals: .
List of intervals to be processed: .
Remove the first and process it.
Iteration 4
VAG(''x''
3 − 7''x'' + 7, (1, 2))
1 ''var'' ← 2 // the number of
sign variation
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.
A similar theorem was publishe ...
s in the sequence of coefficients of (''x'' + 1)
3''p''() = ''x''
3 − 2''x''
2 − ''x'' + 1
4 ''m'' ← (1 + 2) =
5 ''p''(''m'') = −
8 RETURN VAG(''x''
3 − 7''x'' + 7, (1, )) ∪ VAG(''x''
3 − 7''x'' + 7, (, 2))
List of isolation intervals: .
List of intervals to be processed: .
Remove the first and process it.
Iteration 5
VAG(''x''
3 − 7''x'' + 7, (1, ))
1 ''var'' ← 1 // the number of
sign variation
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.
A similar theorem was publishe ...
s in the sequence of coefficients of 2
3(''x'' + 1)
3''p''() = ''x''
3 + 2''x''
2 − 8''x'' − 8
3 RETURN (1, )
List of isolation intervals: .
List of intervals to be processed: .
Remove the first and process it.
Iteration 6
VAG(''x''
3 − 7''x'' + 7, (, 2))
1 ''var'' ← 1 // the number of
sign variation
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.
A similar theorem was publishe ...
s in the sequence of coefficients of 2
3(''x'' + 1)
3''p''() = 8''x''
3 + 4''x''
2 − 4''x'' − 1
3 RETURN (, 2)
List of isolation intervals: .
List of intervals to be processed: .
Remove the first and process it.
Iteration 7
VAG(''x''
3 − 7''x'' + 7, (2, 4))
1 ''var'' ← 0 // the number of
sign variation
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.
A similar theorem was publishe ...
s in the sequence of coefficients of (''x'' + 1)
3''p''() = 344''x''
3 + 376''x''
2 + 104''x'' + 8
2 RETURN ∅
List of isolation intervals: .
List of intervals to be processed: ∅.
Finished.
Conclusion
Therefore, the two positive roots of the polynomial lie inside the isolation intervals and }. Each root can be approximated by (for example) bisecting the isolation interval it lies in until the difference of the endpoints is smaller than ; following this approach, the roots turn out to be and .
See also
*
Properties of polynomial roots
Property is the ownership of land, resources, improvements or other tangible objects, or intellectual property.
Property may also refer to:
Mathematics
* Property (mathematics)
Philosophy and science
* Property (philosophy), in philosophy and ...
*
Root-finding algorithm
In mathematics and computing, a root-finding algorithm is an algorithm for finding zeros, also called "roots", of continuous functions. A zero of a function , from the real numbers to real numbers or from the complex numbers to the complex numbers ...
*
Vieta's formulas
In mathematics, Vieta's formulas relate the coefficients of a polynomial to sums and products of its roots. They are named after François Viète (more commonly referred to by the Latinised form of his name, "Franciscus Vieta").
Basic formulas
A ...
*
Newton's method
In numerical analysis, Newton's method, also known as the Newton–Raphson method, named after Isaac Newton and Joseph Raphson, is a root-finding algorithm which produces successively better approximations to the roots (or zeroes) of a real-valu ...
References
{{reflist
External links
* Berkakis, Antonis: RealRoots, a free App for Android devices to compare Sturm's method and VAS
* https://play.google.com/store/apps/details?id=org.kde.necessitas.berkakis.realroots
Mathematical theorems