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 isolation of the real roots of polynomials, it was almost totally forgotten, having been overshadowed by Sturm's theorem; 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 c0, c1, c2, ... be a finite or infinite sequence of real numbers. Suppose l < r and the following conditions hold:
  1. If r = l+1 the numbers cl and cr have opposite signs.
  2. If rl+2 the numbers cl+1, ..., cr−1 are all zero and the numbers cl and cr have opposite signs.
This is called a sign variation or sign change between the numbers cl and cr.
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 version due to Vincent,[1][2] and the bisection version due to Alesina and Galuzzi.[3][4]

This statement of the continued fractions version can be found also in the Wikipedia article Budan's theorem.

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 variations or it has a single sign variation. 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:[1][2][5]

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;[1][2][5] however, the following remarks are needed for a clearer understanding:

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

 

 

 

 

(1)

has exactly 0 or 1 sign variations. 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 (1) 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 varab(p), where

As in the case of Descartes' rule of signs if varab(p) = 0 it follows that ρab(p) = 0 and if varab(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.[3][4] A fourth proof is due to Ostrowski[6] who rediscovered a special case of a theorem stated by Obreschkoff,[7] 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[7] p. 81): If a real polynomial has one simple root x0, and all other (possibly multiple) roots lie in the sector
then the sequence of its coefficients has exactly one sign variation.
Obreschkoff's sector and his famous eight-shaped figure (of circles).

Consider now the Möbius transformation

and the three circles shown in the corresponding figure; assume that a/c < b/d.

whose diameter lies on the real axis, with endpoints a/c and b/d, is mapped by the inverse Möbius transformation
onto the imaginary axis. For example the point
gets mapped onto the point id/c. The exterior points get mapped onto the half-plane with Re(x) < 0.
and radius
are mapped by the inverse Möbius transformation
onto the lines Im(x) = ±3 Re(x). 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 both his papers,[1][2] Vincent presented examples that show precisely how to use his theorem to isolate real roots of polynomials with continued fractions. However the resulting method had exponential computing time, a fact that mathematicians must have realized then, as was realized by Uspensky[8] p. 136, a century later.

Vincent's search for a root (applying Budan's theorem)

The exponential nature of Vincent's algorithm is due to the way the partial quotients ai (in Vincent's theorem) are computed. That is, to compute each partial quotient ai (that is, to locate where the roots lie on the x-axis) Vincent uses Budan's theorem as a "no roots test"; in other words, to find the integer part of a root Vincent performs successive substitutions of the form xx+1 and stops only when the polynomials p(x) and p(x+1) differ in the number of sign variations in the sequence of their coefficients (i.e. when the number of sign variations of p(x+1) is decreased).[1][2]

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 nature of Vincent's method. Below 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 1827, which solved the real root isolation problem in polynomial 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 systems) by methods derived from Vincent's theorem, the fastest one being the Vincent–Akritas–Strzeboński (VAS) method.[9]

Serret included in his Algebra,[10] pp 363–368, Vincent's theorem 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 the 19th century.

Comeback of Vincent's theorem

In the 20th century Vincent's theorem cannot be found in any of the theory of equations books; the only exceptions are the books by Uspensky[8] and Obreschkoff,[7] where in the second there is just the statement of the theorem.

It was in Uspensky's book[8] that Akritas found Vincent's theorem 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 version of Vincent's theorem 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

the continued fraction that leads to a transformed polynomial

 

 

 

 

(2)

with one sign variation 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

that leads to a transformed polynomial as in equation (2), with one sign variation in the sequence of its coefficients.

Crucial Observation: The variables a, b, c, d of a Möbius transformation

(in Vincent's theorem) leading to a transformed polynomial—as in equation (2)—with one sign variation in the sequence of its coefficients can be computed:

The "bisection part" of this all important observation appeared as a special theorem in the papers by Alesina and Galuzzi.[3][4]

All methods described below (see the article on Budan's theorem 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[12] and elsewhere.[13] These bounds have already been implemented in the computer algebra systems Mathematica, SageMath, SymPy, Xcas etc.

All three methods described below follow the excellent presentation of François Boulier,[14] p. 24.

Continued fractions method

Only one continued fractions method derives from Vincent's theorem. As stated above, it started in the 1830s when Vincent presented, in both his papers,[1][2] several examples that show how to use his theorem to isolate the real roots of polynomials with continued fractions. However the resulting method had exponential 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 behavior of Vincent's method.

The VAS continued fractions method is a direct implementation of Vincent's theorem. It was originally presented by Vincent in his 1834[1] and 1836[2] papers in an exponential form; namely, Vincent computed each partial quotient ai by a series of unit increments aiai + 1, which are equivalent to substitutions of the form xx + 1.

Vincent's method was converted into its polynomial 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 ai 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 ailb or, equivalently, perform the substitution xx + lb, which takes about the same time as the substitution xx + 1.

VAS searching for a root: The ideal lower bound is 5, hence xx + 5.

Finally, since the ideal positive lower root bound does not exist, Strzeboński[15] introduced in 2005 the substitution , whenever ; in general and the value 16 was determined experimentally. Moreover, it has been shown[15] that the VAS (continued fractions) method is faster than the fastest implementation of the VCA (bisection) method,[16] a fact that was confirmed[17] 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[18] removed the hypothesis of the ideal positive lower bound and proved that VAS is still polynomial in time.

VAS is the default algorithm for root isolation in Mathematica, SageMath, SymPy, Xcas.

For a comparison between Sturm's method and VAS use the functions realroot(poly) and time(realroot(poly)) of Xcas. 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 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:

whereas to compute the roots in the interval (1, ∞) perform the substitution xx + 1 to p(x) and M(x) and process the pair {p(1 + x), M(1 + x)}. 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 presentation of VAS(p, M).

VAS(p, M):

Input: A univariate, square-free polynomial , of degree deg(p), and the Möbius transformation

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;
2 if var = 0 then RETURN ∅;
3 if var = 1 then RETURN {(a, b)} // 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 pp(x + lb), MM(x + lb);
6 p01 ← (x + 1)deg(p) p(1/x + 1), M01M(1/x + 1) // Look for real roots in (0, 1);
7 mM(1) // Is 1 a root?
8 p1∞p(x + 1), M1∞M(x + 1) // Look for real roots in (1, ∞);
9 if p(1) ≠ 0 then
10 RETURN VAS(p01, M01) ∪ VAS(p1∞, M1∞)
11 else
12 RETURN VAS(p01, M01) ∪ {[m, m]} ∪ VAS(p1∞, M1∞)
13 end

Remarks

Example of VAS(p, M)

We apply the VAS method to p(x) = x3 − 7x + 7 (note that: M(x) = x).

Iteration 1

VAS(x3 − 7x + 7, x)
1 var ← 2 // the number of sign variations in the sequence of coefficients of p(x) = x3 − 7x + 7
4 lb ← 1 // the ideal lower bound—found using lbcomputed and substitution(s) xx + 1
5 px3 + 3x2 − 4x + 1, Mx + 1
6 p01x3x2 − 2x + 1, M01x + 2/x + 1
7 m ← 1
8 p1∞x3 + 6x2 + 5x + 1, M1∞x + 2
10 RETURN VAS(x3x2 − 2x + 1, x + 2/x + 1) ∪ VAS(x3 + 6x2 + 5x + 1, x + 2)

List of isolation intervals: { }.

List of pairs {p, M} to be processed:

Remove the first and process it.

Iteration 2

VAS(x3x2 − 2x + 1, x + 2/x + 1)
1 var ← 2 // the number of sign variations in the sequence of coefficients of p(x) = x3x2 − 2x + 1
4 lb ← 0 // the ideal lower bound—found using lbcomputed and substitution(s) xx + 1
6 p01x3 + x2 − 2x − 1, M012x + 3/x + 1
7 m3/2
8 p1∞x3 + 2x2x − 1, M1∞x + 3/x + 2
10 RETURN VAS(x3 + x2 − 2x − 1, 2x + 3/x + 2) ∪ VAS(x3 + 2x2x − 1, x + 3/x + 2)

List of isolation intervals: { }.

List of pairs {p, M} to be processed:

Remove the first and process it.

Iteration 3

VAS(x3 + x2 − 2x − 1, 2x + 3/x + 2)
1 var ← 1 // the number of sign variations in the sequence of coefficients of p(x) = x3 + x2 − 2x − 1
3 RETURN {(3/2, 2)}

List of isolation intervals: {(3/2, 2)}.

List of pairs {p, M} to be processed:

Remove the first and process it.

Iteration 4

VAS(x3 + 2x2x − 1, x + 3/x + 2)
1 var ← 1 // the number of sign variations in the sequence of coefficients of p(x) = x3 + 2x2x − 1
3 RETURN {(1, 3/2)}

List of isolation intervals: {(1, 3/2), (3/2, 2)}.

List of pairs {p, M} to be processed:

Remove the first and process it.

Iteration 5

VAS(x3 + 6x2 + 5x + 1, x + 2)
1 var ← 0 // the number of sign variations in the sequence of coefficients of p(x) = x3 + 6x2 + 5x + 1
2 RETURN

List of isolation intervals: {(1, 3/2), (3/2, 2)}.

List of pairs {p, M} to be processed: .

Finished.

Conclusion

Therefore, the two positive roots of the polynomial p(x) = x3 − 7x + 7 lie inside the isolation intervals (1, 3/2) and (3/2, 2)}. Each root can be approximated by (for example) bisecting the isolation interval it lies in until the difference of the endpoints is smaller than 10−6; following this approach, the roots turn out to be ρ1 = 1.3569 and ρ2 = 1.69202.

Bisection methods

There are various bisection methods derived from Vincent's theorem; they are all presented and compared elsewhere.[19] 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[16] have made VCA the fastest bisection method.

Vincent–Collins–Akritas (VCA, 1976)

This was the first method developed to overcome the exponential 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, had been originally called modified Uspensky's algorithm by its inventors Collins and Akritas.[11] After going through names like "Collins–Akritas method" and "Descartes' method" (too confusing if ones considers Fourier's article[20]), it was finally François Boulier, of Lille University, who gave it the name Vincent–Collins–Akritas (VCA) method,[14] p. 24, based on the fact that "Uspensky's method" does not exist[21] and neither does "Descartes' method".[22] The best implementation of this method is due to Rouillier and Zimmerman,[16] and to this date, it is the fastest bisection method. It has the same worst case complexity as Sturm's algorithm, but is almost always much faster. It has been implemented in Maple's RootFinding package.

Here is how VCA(p, (a, b)) works:

Bijection between the roots of porig(x) and p(x).
(see the corresponding figure). It may well turn out that 1/2 is a root of p(x), in which case 1/2(a + b) is a root of porig(x) and the isolation interval reduces to a point.
Bijections between the roots of p(x) and those of p(x/2) and p(x + 1/2).

Below is a recursive 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 variations of (x + 1)deg(p)p(1/x + 1) // Budan's "0_1 roots test";
2 if var = 0 then RETURN ∅;
3 if var = 1 then RETURN {(a, b)};
4 p01/2 ← 2deg(p)p(x/2) // Look for real roots in (0, 1/2);
5 m1/2(a + b) // Is 1/2 a root?
6 p1/21 ← 2deg(p)p(x + 1/2) // Look for real roots in (1/2, 1);
7 if p(1/2) ≠ 0 then
8 RETURN VCA (p01/2, (a, m)) ∪ VCA (p1/21, (m, b))
9 else
10 RETURN VCA (p01/2, (a, m)) ∪ {[m, m]} ∪ VCA (p1/21, (m, b))
11 end

Remark

Example of VCA(p, (a,b))

Given the polynomial porig(x) = x3 − 7x + 7 and considering as an upper bound[12][13] on the values of the positive roots ub = 4 the arguments of the VCA method are: p(x) = 64x3 − 28x + 7 and (a, b) = (0, 4).

Iteration 1

1 var ← 2 // the number of sign variations in the sequence of coefficients of (x + 1)3p(1/x + 1) = 7x3 − 7x2 − 35x + 43
4 p01/2 ← 64x3 − 112x + 56
5 m ← 2
6 p1/21 ← 64x3 + 192x2 + 80x + 8
7 p(1/2) = 1
8 RETURN VCA(64x3 − 112x + 56, (0, 2)) ∪ VCA(64x3 + 192x2 + 80x + 8, (2, 4))

List of isolation intervals: { }.

List of pairs {p, I} to be processed:

Remove the first and process it.

Iteration 2

VCA(64x3 − 112x + 56, (0, 2))
1 var ← 2 // the number of sign variations in the sequence of coefficients of (x + 1)3p(1/x + 1) = 56x3 + 56x2 − 56x + 8
4 p01/2 ← 64x3 − 448x + 448
5 m ← 1
6 p1/21 ← 64x3 + 192x2 − 256x + 64
7 p(1/2) = 8
8 RETURN VCA(64x3 − 448x + 448, (0, 1)) ∪ VCA(64x3 + 192x2 − 256x + 64, (1, 2))

List of isolation intervals: { }.

List of pairs {p, I} to be processed:

Remove the first and process it.

Iteration 3

VCA(64x3 − 448x + 448, (0, 1))
1 var ← 0 // the number of sign variations in the sequence of coefficients of (x + 1)3p(1/x + 1) = 448x3 + 896x2 + 448x + 64
2 RETURN

List of isolation intervals: { }.

List of pairs {p, I} to be processed:

Remove the first and process it.

Iteration 4

VCA(64x3 + 192x2 − 256x + 64, (1, 2))
1 var ← 2 // the number of sign variations in the sequence of coefficients of (x + 1)3p(1/x + 1) = 64x3 − 64x2 − 128x + 64
4 p01/2 ← 64x3 + 384x2 − 1024x + 512
5 m3/2
6 p1/21 ← 64x3 + 576x2 − 64x + 64
7 p(1/2) = −8
8 RETURN VCA(64x3 + 384x2 − 1024x + 512, (1, 3/2)) ∪ VCA(64x3 + 576x2 − 64x − 64, (3/2, 2))

List of isolation intervals: { }.

List of pairs {p, I} to be processed:

Remove the first and process it.

Iteration 5

VCA(64x3 + 384x2 − 1024x + 512, (1, 3/2))
1 var ← 1 // the number of sign variations in the sequence of coefficients of (x + 1)3p(1/x + 1) = 512x3 + 512x2 − 128x − 64
3 RETURN {(1, 3/2)}

List of isolation intervals: {(1, 3/2)}.

List of pairs {p, I} to be processed:

Remove the first and process it.

Iteration 6

VCA(64x3 + 576x2 − 64x − 64, (3/2, 2))
1 var ← 1 // the number of sign variations in the sequence of coefficients of (x + 1)3p(1/x + 1) = −64x3 − 256x2 + 256x + 512
3 RETURN {(3/2, 2)}

List of isolation intervals: {(1, 3/2), (3/2, 2)}.

List of pairs {p, I} to be processed:

Remove the first and process it.

Iteration 7

VCA(64x3 + 192x2 + 80x + 8, (2, 4))
1 var ← 0 // the number of sign variations in the sequence of coefficients of (x + 1)3p(1/x + 1) = 8x3 + 104x2 + 376x + 344
2 RETURN

List of isolation intervals: {(1, 3/2), (3/2, 2)}.

List of pairs {p, I} to be processed: .

Finished.

Conclusion

Therefore, the two positive roots of the polynomial p(x) = x3 − 7x + 7 lie inside the isolation intervals (1, 3/2) and (3/2, 2)}. Each root can be approximated by (for example) bisecting the isolation interval it lies in until the difference of the endpoints is smaller than 10−6; following this approach, the roots turn out to be ρ1 = 1.3569 and ρ2 = 1.69202.

Vincent–Alesina–Galuzzi (VAG, 2000)

This was developed last and is the simplest real root isolation method derived from Vincent's theorem.

Here is how VAG(p, (a, b)) works:

Below is a recursive 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 variations of (x + 1)deg(p) p(a + bx/1 + x) // The Alesina–Galuzzi "a_b roots test";
2 if var = 0 then RETURN ∅;
3 if var = 1 then RETURN {(a, b)};
4 m1/2(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)) ∪ {[m, m]} ∪ VAG(p, (m, b))
9 end

Remarks

Example of VAG(p, (a,b))

Given the polynomial p(x) = x3 − 7x + 7 and considering as an upper bound[12][13] on the values of the positive roots ub = 4 the arguments of VAG are: p(x) = x3 − 7x + 7 and (a, b) = (0, 4).

Iteration 1

1 var ← 2 // the number of sign variations in the sequence of coefficients of (x + 1)3p(4x/x + 1) = 43x3 − 35x2 − 7x + 7
4 m1/2(0 + 4) = 2
5 p(m) = 1
8 RETURN VAG(x3 − 7x + 7, (0, 2)) ∪ VAG(x3 − 7x + 7, (2, 4)

List of isolation intervals: {}.

List of intervals to be processed: {(0, 2), (2, 4)}.

Remove the first and process it.

Iteration 2

VAG(x3 − 7x + 7, (0, 2))
1 var ← 2 // the number of sign variations in the sequence of coefficients of (x + 1)3p(2x/x + 1) = x3 − 7x2 + 7x + 7
4 m1/2(0 + 2) = 1
5 p(m) = 1
8 RETURN VAG(x3 − 7x + 7, (0, 1)) ∪ VAG(x3 − 7x + 7, (1, 2)

List of isolation intervals: {}.

List of intervals to be processed: {(0, 1), (1, 2), (2, 4)}.

Remove the first and process it.

Iteration 3

VAG(x3 − 7x + 7, (0, 1))
1 var ← 0 // the number of sign variations in the sequence of coefficients of (x + 1)3p(x/x + 1) = x3 + 7x2 + 14x + 7
2 RETURN

List of isolation intervals: {}.

List of intervals to be processed: {(1, 2), (2, 4)}.

Remove the first and process it.

Iteration 4

VAG(x3 − 7x + 7, (1, 2))
1 var ← 2 // the number of sign variations in the sequence of coefficients of (x + 1)3p(2x + 1/x + 1) = x3 − 2x2x + 1
4 m1/2(1 + 2) = 3/2
5 p(m) = −1/8
8 RETURN VAG(x3 − 7x + 7, (1, 3/2)) ∪ VAG(x3 − 7x + 7, (3/2, 2))

List of isolation intervals: {}.

List of intervals to be processed: {(1, 3/2), (3/2, 2), (2, 4)}.

Remove the first and process it.

Iteration 5

VAG(x3 − 7x + 7, (1, 3/2))
1 var ← 1 // the number of sign variations in the sequence of coefficients of 23(x + 1)3p(3/2x + 1/x + 1) = x3 + 2x2 − 8x − 8
3 RETURN (1, 3/2)

List of isolation intervals: {(1, 3/2)}.

List of intervals to be processed: {(3/2, 2), (2, 4)}.

Remove the first and process it.

Iteration 6

VAG(x3 − 7x + 7, (3/2, 2))
1 var ← 1 // the number of sign variations in the sequence of coefficients of 23(x + 1)3p(2x + 3/2/x + 1) = 8x3 + 4x2 − 4x − 1
3 RETURN (3/2, 2)

List of isolation intervals: {(1, 3/2), (3/2, 2)}.

List of intervals to be processed: {(2, 4)}.

Remove the first and process it.

Iteration 7

VAG(x3 − 7x + 7, (2, 4))
1 var ← 0 // the number of sign variations in the sequence of coefficients of (x + 1)3p(4x + 2/x + 1) = 344x3 + 376x2 + 104x + 8
2 RETURN

List of isolation intervals: {(1, 3/2), (3/2, 2)}.

List of intervals to be processed: ∅.

Finished.

Conclusion

Therefore, the two positive roots of the polynomial p(x) = x3 − 7x + 7 lie inside the isolation intervals (1, 3/2) and (3/2, 2)}. Each root can be approximated by (for example) bisecting the isolation interval it lies in until the difference of the endpoints is smaller than 10−6; following this approach, the roots turn out to be ρ1 = 1.3569 and ρ2 = 1.69202.

See also

References

  1. 1 2 3 4 5 6 7 Vincent, Alexandre Joseph Hidulphe (1834). "Mémoire sur la résolution des équations numériques". Mémoires de la Société Royale des Sciences, de l' Agriculture et des Arts, de Lille: 1–34.
  2. 1 2 3 4 5 6 7 Vincent, Alexandre Joseph Hidulphe (1836). "Sur la résolution des équations numériques" (PDF). Journal de Mathématiques Pures et Appliquées. 1: 341–372.
  3. 1 2 3 Alesina, Alberto; Massimo Galuzzi (1998). "A new proof of Vincent's theorem". L'Enseignement Mathématique. 44 (3-4): 219–256.
  4. 1 2 3 4 Alesina, Alberto; Massimo Galuzzi (2000). "Vincent's Theorem from a Modern Point of View" (PDF). Categorical Studies in Italy 2000, Rendiconti del Circolo Matematico di Palermo, Serie II, n. 64: 179–191.
  5. 1 2 Vincent, Alexandre Joseph Hidulphe (1838). "Addition à une précédente note relative à la résolution des équations numériques" (PDF). Journal de Mathématiques Pures et Appliquées. 3: 235–243.
  6. Ostrowski, A. M. (1950). "Note on Vincent's theorem". Annals of Mathematics. Second Series. 52 (3): 702–707. doi:10.2307/1969443. JSTOR 10.2307/1969443.
  7. 1 2 3 Obreschkoff, Nikola (1963). Verteilung und Berechnung der Nullstellen reeller Polynome. Berlin: VEB Deutscher Verlag der Wissenschaften.
  8. 1 2 3 Uspensky, James Victor (1948). Theory of Equations. New York: McGraw–Hill Book Company.
  9. 1 2 Akritas, Alkiviadis G.; A.W. Strzeboński; P.S. Vigklas (2008). "Improving the performance of the continued fractions method using new bounds of positive roots" (PDF). Nonlinear Analysis: Modelling and Control. 13: 265–279.
  10. Serret, Joseph A. (1877). Cours d'algèbre supérieure. Tome I. Gauthier-Villars.
  11. 1 2 Collins, George E.; Alkiviadis G. Akritas (1976). Polynomial Real Root Isolation Using Descartes' Rule of Signs. SYMSAC '76, Proceedings of the third ACM symposium on Symbolic and algebraic computation. Yorktown Heights, NY, USA: ACM. pp. 272–275.
  12. 1 2 3 4 5 6 7 Vigklas, Panagiotis, S. (2010). Upper bounds on the values of the positive roots of polynomials (PDF). Ph. D. Thesis, University of Thessaly, Greece.
  13. 1 2 3 4 5 6 7 Akritas, Alkiviadis, G. (2009). "Linear and Quadratic Complexity Bounds on the Values of the Positive Roots of Polynomials". Journal of Universal Computer Science. 15 (3): 523–537.
  14. 1 2 Boulier, François (2010). Systèmes polynomiaux : que signifie " résoudre " ? (PDF). Université Lille 1.
  15. 1 2 Akritas, Alkiviadis G.; Adam W. Strzeboński (2005). "A Comparative Study of Two Real Root Isolation Methods" (PDF). Nonlinear Analysis: Modelling and Control. 10 (4): 297–304.
  16. 1 2 3 Rouillier, F.; P. Zimmerman (2004). "Efficient isolation of polynomial's real roots". Journal of Computational and Applied Mathematics. 162: 33–50. doi:10.1016/j.cam.2003.08.015.
  17. Tsigaridas, P.E.; I.Z. Emiris (2006). "Univariate polynomial real root isolation: Continued fractions revisited". LNCS. 4168: 817–828. doi:10.1007/11841036_72.
  18. Sharma, Vikram (2007). Complexity Analysis of Algorithms in Algebraic Computation (PDF). Ph.D. Thesis, Courant Institute of Mathematical Sciences, New York University,USA.
  19. 1 2 3 Akritas, Alkiviadis G.; Adam W. Strzeboński; Panagiotis S. Vigklas (2008). "On the Various Bisection Methods Derived from Vincent's Theorem". Serdica Journal of Computing. 2 (1): 89–104.
  20. Fourier, Jean Baptiste Joseph (1820). "Sur l'usage du théorème de Descartes dans la recherche des limites des racines" (PDF). Bulletin des Sciences, par la Société Philomatique de Paris: 156–165.
  21. Akritas, Alkiviadis G. (1986). There's no "Uspensky's Method". In: Proceedings of the fifth ACM Symposium on Symbolic and Algebraic Computation (SYMSAC '86, Waterloo, Ontario, Canada), pp. 88–90.
  22. 1 2 Akritas, Alkiviadis G. (2008). There is no "Descartes' method". In: M.J.Wester and M. Beaudin (Eds), Computer Algebra in Education, AullonaPress, USA, pp. 19–35.

External links

This article is issued from Wikipedia - version of the 11/14/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.