Real-root isolation

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

Real-root isolation is useful because usual root-finding algorithms for computing the real roots of a polynomial may produce some real roots, but, cannot generally certify having found all real roots. In particular, if such an algorithm does not find any root, one does not know whether it is because there is no real root. Some algorithms compute all complex roots, but, as there are generally much fewer real roots than complex roots, most of their computation time is generally spent for computing non-real roots (in the average, a polynomial of degree $n$ has $n$ complex roots, and only $log n$ real roots; see Geometrical properties of polynomial roots § Real roots). Moreover, it may be difficult to distinguish the real roots from the non-real roots with small imaginary part (see the example of Wilkinson's polynomial in next section).

The first complete real-root isolation algorithm results from Sturm's theorem (1829). However, when real-root-isolation algorithms began to be implemented on computers it appeared that algorithms derived from Sturm's theorem are less efficient than those derived from Descartes' rule of signs (1637).

Since the beginning of 20th century there is an active research activity for improving the algorithms derived from Descartes' rule of signs, getting very efficient implementations, and computing their computational complexity. The best implementations can routinely isolate real roots of polynomials of degree more than 1,000.^[1]^[2]

Specifications and general strategy

For finding real roots of a polynomial, the common strategy is to divide the real line (or an interval of it where root are searched) into disjoint intervals until having at most one root in each interval. Such a procedure is called root isolation, and a resulting interval that contains exactly one root is an isolating interval for this root.

Wilkinson's polynomial shows that a very small modification of one coefficient of a polynomial may change dramatically not only the value of the roots, but also their nature (real or complex). Also, even with a good approximation, when one evaluates a polynomial at an approximate root, one may get a result that is far to be close to zero. For example, if a polynomial of degree 20 (the degree of Wilkinson's polynomial) has a root close to 10, the derivative of the polynomial at the root may be of the order of $10^{20};$ this implies that an error of $10^{-10}$ on the value of the root may produce a value of the polynomial at the approximate root that is of the order of $10^{10}.$ It follows that, except maybe for very low degrees, a root-isolation procedure cannot give reliable results without using exact arithmetic. Therefore, if one wants to isolate roots of a polynomial with floating-point coefficients, it is often better to convert them to rational numbers, and then take the primitive part of the resulting polynomial, for having a polynomial with integer coefficients.

For this reason, although the methods that are described below work theoretically with real numbers, they are generally used in practice with polynomials with integer coefficients, and intervals ending with rational numbers. Also, the polynomials are always supposed to be square free. There are two reasons for that. Firstly Yun's algorithm for computing the square-free factorization is less costly than twice the cost of the computation of the greatest common divisor of the polynomial and its derivative. As this may produce factors of lower degrees, it is generally advantageous to apply root-isolation algorithms only on polynomials without multiple roots, even when this is not required by the algorithm. The second reason for considering only square-free polynomials is that the fastest root-isolation algorithms do not work in the case of multiple roots.

For root isolation, one requires a procedure for counting the real roots of a polynomial in an interval without having to compute them, or, at least a procedure for deciding whether an interval contains zero, one or more roots. With such a decision procedure, one may work with a working list of intervals that may contain real roots. At the beginning, the list contains a single interval containing all roots of interest, generally the whole real line or its positive part. Then each interval of the list is divided into two smaller intervals. If one of the new intervals does not contain any root, it is removed from the list. If it contains one root, it is put in an output list of isolating intervals. Otherwise, it is kept in the working list for further divisions, and the process may continue until all roots are eventually isolated

Sturm's theorem

The first complete root-isolation procedure results of Sturm's theorem (1829), which expresses the number of real roots in an interval in terms of the number of sign variations of the values of a sequence of polynomials, called Sturm's sequence, at the ends of the interval. Sturm's sequence is the sequence of remainders that occur in a variant of Euclidean algorithm applied to the polynomial and its derivatives. When implemented on computers, it appeared that root isolation with Sturm's theorem is less efficient than the other methods that are described below.^[3] Consequently, Sturm's theorem is rarely used for effective computations, although it remains useful for theoretical purposes.

Descartes' rule of signs and its generalizations

Descartes' rule of signs asserts that the difference between the number of sign variations in the sequence of the coefficients of a polynomial and the number of its positive real roots is a nonnegative even integer. It results that if this number of sign variations is zero, then the polynomial does not have any positive real roots, and, if this number is one, then the polynomial has a unique positive real root, which is a single root. Unfortunately the converse is not true, that is, a polynomial which has either no positive real root or has a single positive simple root may have a number of sign variations greater than 1.

This has been generalized by Budan's theorem (1807), into a similar result for the real roots in a half-open interval $(a, b$ : If $f (x)$ is a polynomial, and $v$ is the difference between of the numbers of sign variations of the sequences of the coefficients of $f (x + a)$ and $f (x + b)$ , then $v$ minus the number of real roots in the interval, counted with their multiplicities, is a nonnegative even integer. This is a generalization of Descartes' rule of signs, because, for $b$ sufficiently large, there is no sign variation in the coefficients of $f (x + b)$ , and all real roots are smaller than $b$ .

Budan's may provide a real-root-isolation algorithm for a square-free polynomial (a polynomial without multiple root): from the coefficients of polynomial, one may compute an upper bound $M$ of the absolute values of the roots and a lower bound $m$ on the absolute values of the differences of two roots (see Properties of polynomial roots). Then, if one divides the interval into intervals of length less than $m$ , then every real root is contained in some interval, and no interval contains two roots. The isolating intervals are thus the intervals for which Budan's theorem asserts an odd number of roots.

However, this algorithm is very inefficient, as one cannot use a coarser partition of the interval , because, if Budan's theorem gives a result larger than 1 for an interval of larger size, there is no way for insuring that it does not contain several roots.

Vincent's and related theorems

Vincent's theorem (1834)^[4] provides a method for real-root isolation, which is at the basis of the most efficient real-root-isolation algorithms. It concerns the positive real roots of a square-free polynomial (that is a polynomial without multiple roots). If $a_{1},a_{2},\ldots ,$ is a sequence of positive real numbers, let

c_{k}=a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}+{\cfrac {1}{\ddots +{\cfrac {1}{a_{k}}}}}}}}}

be the $k$ th convergent of the continued fraction

a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}+{\cfrac {1}{\ddots }}}}}}.

Vincent's theorem — Let $p_{0}(x)$ be a square-free polynomial of degree $n$ , and $a_{1},a_{2},\ldots ,$ be a sequence of real numbers. For $i = 1, 2,...,$ consider the polynomial

p_{i}(x)=x^{n}p_{i-1}\left(a_{i}+1/x\right).

Then, there is an integer $k$ such that either $p_{k}(0)=0,$ or the sequence of the coefficients of $p_{k}$ has at most one sign variation.

In the first case, the convergent $c k$ is a positive root of $p_{0}.$ Otherwise, this number of sign variations (either 0 or 1) is the number of real roots of $p_{0}$ in the interval defined by $c_{k-1}$ and $c_{k}.$

For proving his theorem, Vincent proved a result that is useful on its own:^[4]

Vincent's auxiliary theorem — If $p (x)$ is a square-free polynomial of degree $n$ , and $a, b, c, d$ are nonnegative real numbers such that $\left|{\frac {a}{c}}-{\frac {b}{d}}\right|$ is small enough (but not 0), then there is at most one sign variation in the coefficients of the polynomial

q(x)=(cx+d)^{n}p\left({\frac {ax+b}{cx+d}}\right),

and this number of sign variations is the number of real roots of $p (x)$ in the open interval defined by ${\frac {a}{c}}$ and ${\frac {b}{d}}.$

For working with real numbers, one may always choose $c = d = 1$ , but, as effective computations are done with rational numbers, it is generally convenient to suppose that $a, b, c, d$ are integers.

The "small enough" condition has been quantified independently by Nikola Obreshkov,^[5] and Alexander Ostrowski:^[6]

Theorem (Obreschkoff–Ostrowski) — The conclusion of Vincent's auxiliary result holds if the polynomial $p (x)$ has at most one root $α + iβ$ such that

\left(\alpha -{\frac {a}{c}}\right)\left(\alpha -{\frac {b}{d}}\right)+\beta ^{2}\leq {\frac {1}{\sqrt {3}}}\left|\beta \left({\frac {a}{c}}-{\frac {b}{d}}\right)\right|.

In particular the conclusion holds if

\left|{\frac {a}{c}}-{\frac {b}{d}}\right|<{\frac {\operatorname {sep} (p)}{2{\sqrt {3}}}},

Navigácia: Veda >

Analytika
Antropológia
Aplikované vedy
Bibliometria
Dejiny vedy
Encyklopédie
Filozofia vedy
Forenzné vedy
Humanitné vedy
Knižničná veda
Kryogenika
Kryptológia
Kulturológia
Literárna veda
Medzidisciplinárne oblasti
Metódy kvantitatívnej analýzy
Metavedy
Metodika

Metodológia vedy
Náboženstvo a veda
Náučná literatúra
Podvody vo vede
Popularizácia vedy
Potravinárstvo
Prírodné vedy
Pseudoveda
Scientometria
Spoločenské vedy
Teórie
Teatrológia
Technické vedy
Technika
Terminológia
Umenie
Výskum

Veda
Veda a technika podľa štátu
Veda a technika podľa kontinentu
Veda a technika podľa roka
Veda v kozme
Vedci
Vedecká literatúra
Vedecké databázy
Vedecké experimenty
Vedecké konferencie
Vedecké metódy
Vedecké ocenenia
Vedecké organizácie
Vedecké parky
Vedeckí spisovatelia
Vzdelávanie
Záhady

Príbuzné výrazy:

Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky použitia.

[1]

[2]

[3]

[4]

[5]

[6]