sturm's theorem

In mathematics, Sturm's theorem is a symbolic procedure to determine the number of unique real roots of a polynomial. It was named for its discoverer, Jacques Charles Franois Sturm. Whereas the fundamental theorem of algebra readily yields the number of real or complex roots of a polynomial, counted according to their multiplicities, Sturm's theorem deals with real roots and disregards their multiplicities. To apply Sturm's theorem, you first construct a Sturm chain from a polynomial

X=a_n x^n+\ldots a_1 x+a_0

. A sturm chain is the sequence of intermediary results when applying Euclid's algorithm to

X

and its derivative

X_1=X'

. To obtain the Sturm chain, you compute

\begin{matrix}

X_2&=&-{\rm rem}(X,X_1)\\ X_3&=&-{\rm rem}(X_1,X_2)\\ &\ldots&\\ 0&=&-{\rm rem}(X_{r-1},X_r), \end{matrix} i.e., you successively take the remainders with a polynom division and change theirs signs. Each

X_i

is a polynom of at least degree one, hence the algorithm will stop at last.

X_r

then is the GCD of

X

and its derivative. If

X

only had simple roots, it will be a constant. The Sturm chain then is

X,X_1,X_2,\ldots,X_r

. Let

w(\xi)

be the number of sign changes (zeroes are not counted) in the sequence

X(\xi), X_1(\xi), X_2(\xi),\ldots, X_r(\xi)

. Sturm's theorem then states that for two real numbers

a that are

not roots of

X

, one has that the number of roots in the interval

a,b

w(b)-w(a)

. This can be used to compute the total number of real roots a polynom has (e.g., as an input to a numerical root finder) by choosing

a

and

b

appropriately -- for example, all real root of a polynomial with cofficients

a_i

are in the interval

-M,M

, where

M=\max(1, \sum |a_i|)

. Alternatively, you can use the fact that for large

x

, the sign of a polynom

P(x)=a_n x^n+\ldots

\sgn(a_n)

, wheras

\sgn(P(-x))=\sgn({(-1)^n} a_n)

. In this way, simply counting the sign changes in the leading coefficients in the sturm chain readily gives the number of distinct real roots of a polynomial.

<< Previous

Word Browser

Next >>

viscount, alexander edward murray fincastle
peter scawen watkinson roberts
george murray rolland
charles graham robertson
banqiao dam
frederick george room
john readitt
interceptor corporation
ssangyong rodius(stavic)
john (or o'niell) o'neill
cecil griffiths

roderick mcgregor
bbc radio 1 live in concert
theodore bailey hardy
george burdon mckean
lope de rueda
prop jets inc
self coup
guillermo francella
functionality assurance
dioptrics
university of cambridge esol examination

mercedes benz citaro
namli maira
warhellride
walter richard pollock hamilton
donald edward garland
minden, ontario
charles john melliss
tiong hiew king
hector lachlan stewart maclean
stanley robert mcdougall
narciso lpez

mahaparinibbana sutta
philip john gardner
olympia marble
ha ki rak
thomas james harris
john macgregor (vc)
john chipman kerr
john carstairs mcneill
john dunlay
space corps directives
john ainsworth davies