Profile
Settings
Refer your friends
Sign out
Sturm’s theorem is less efficient than other methods based on Descartes’ rule of signs for computing over the reals. However, because it works on every real closed field, it is still important for the theoretical study of the computational difficulty of decidability and quantifier elimination in first-order real-number theory.
Sturm theorem differential equations
The Sturm sequence of a univariate polynomial p is a polynomial sequence connected with p and its derivative through a variation of Euclid’s polynomial technique. The number of unique real roots of p situated in an interval is expressed in terms of the number of changes in sign of the values of the Sturm sequence at the interval’s boundaries by Sturm’s theorem. It yields the total number of real roots of p when applied to the interval of all real numbers.
While the fundamental theorem of algebra easily reveals the total number of complex roots when multiplied, it does not provide a method for computing them. Sturm’s theorem counts how many distinct real roots there are and places them in intervals.
It isolates the roots by subdividing intervals containing some roots into arbitrarily small intervals, each having exactly one root. This produces the oldest real-root isolation algorithm as well as the arbitrary-precision root-finding technique for univariate polynomials.
After Jacques Charles François Sturm, who discovered the theory in 1829, the Sturm sequence and Sturm’s theorem were called.
The Sturm–Picone comparison theorem is a classical theorem in mathematics that provides criteria prior the oscillation and non-oscillation of solutions of certain linear differential equations in the real domain. It is named after Jacques Charles François Sturm and Mauro Picone.
Let pi and qi be real-valued continuous functions on the interval [a, b] for i = 1, 2 and let
1. (p1(x)y’)’+ q1(x)y = 0
2.(p2(x)y’)’+ q2(x)y = 0
Consider two self-adjoint homogeneous linear second-order differential equations.
0<p2(x)≤p1(x)
q1(x) ≤q2(x)
Let u be a non-trivial solution of (1) with successive roots at z1 and z2, and v be a non-trivial solution of (1) with successive roots at z1 and z2 (2). Then one of the attributes listed below applies.
There is an x in (z1, z2) for which v(x) = 0; or there is an in R for which v(x) = u. (x).
Sturm (1836) is responsible for the first half of the conclusion, while Picone (1910) is responsible for the second (alternative) section of the theorem, whose simple proof was given using his now famous Picone identity. The Sturm separation theorem is obtained in the specific case where both equations are identical.
Sturm’s theorem proof
Assertion (2): Since p0(c) = f(c) and p1(c) = f ′ (c), the recurrence defining the Sturm-Liouville equation is p1(c) = f’(c )
We’re done because the sequence implies that pj (c)=0 for every j ≥ 2.
Assertion (1): If a=b or f is a nonzero constant, then Nf (a, b)=Vf (a) is manifestly true.
Assertion (1) holds for Vf (b) = 0. Assume that a ,b and f are both positive of degree d.
Let us now focus on the unique scenario in which the following condition remains true:
(a, b] has at most one f root, with b non-degenerate if it is a f root.
Assume that f has roots in (a, b] and that they are in strictly increasing order.
Allowing (c1,…, cm) to be any sequence satisfying a c1 , c2 , cm , we can see that Vf (a) Vf (b) is precisely the same.
(Vf (a ,c1)) + (Vf (c1 ,c2)) + (Vf (c1 c2)) + (Vf (cm1 ,cm)) + (Vf (cm ,b)).
Nf (a, b] is exactly Nf (a, b] by definition.
Nf (a, c1] + Nf (c1, c2] + + Nf (cm1, cm] + Nf (cm, b] + Nf (cm, a]
It is therefore sufficient to demonstrate
Nf (a, c1)=Vf (a, c1), Nf (c1, c2)=Vf (c1 c2), Nf (cm1, cm)=Vf (cm1)Vf (cm2,cm),
Nf (cm, b]=Vf (cm ,cm) (b). In other words, we can determine whether f has roots in (a, b).
Assume that Condition .
Let us now consider a specific example in which the following somewhat stronger.
condition is true:
The values of p1,…, pd (as well as p0 =f) were also interlaced. We can reduce even further to the exceptional situation where (a, b) includes no roots of f and only one root of p1 pd using the same approach of cancellation in an alternating sum.
State and prove Sturm theorem
In two directions, Sturm sequences have been generalised. Sturm used the negative of the residue of the Euclidean division of the two preceding polynomials to define each one in the sequence. If the negative of the remainder is replaced by its product or quotient by a positive constant or the square of a polynomial, the theorem holds. Sequences, where the second polynomial is not the derivative of the first one, are also beneficial (see below).
A finite sequence of polynomials with real coefficients is known as a generalised Sturm sequence.
P0,P1,P2….
The last requirement indicates that no common real root exists between two consecutive polynomials. If (and only if) the polynomial has no multiple real roots, the original Sturm sequence is a generalise Sturm sequence (otherwise the first two polynomials of its Sturm sequence have a common root).
When computing the original Sturm sequence using Euclidean division, it’s possible to come across a polynomial with a factor that’s never negative, such as x2 or x2 + x + 1. In this scenario, if the polynomial is replaced by its quotient by the nonnegative component, a generalise Sturm sequence is obtained, which may also be used to compute the number of real roots since Sturm’s theorem is proved.
Generalized Sturm sequences allow you to count the roots of a polynomial in the presence of another polynomial that is positive (or negative). Knowing an isolating interval for a root of the first polynomial allows one to identify the sign of the second polynomial for that root of the first polynomial without having to compute a better approximation of the root.
Let P(x) and Q(x) be two real-coefficient polynomials with no common root and no multiple roots, respectively. P and P’ Q are coprime polynomials, in other words. This constraint has no effect on the generality of what follows because GCD computations allow us to reduce the general case to this example, and the cost of computing this case is minimal.
W(a) is the number of sign fluctuations at an in a generalised Sturm sequence starting with P and P’ Q. If a and b are two real integers, W(a) – W(b) is the number of roots of P in the interval (a,b)(a,b) such that Q(a) > 0 minus the number of roots in the same interval such that Q(a) =0. This, when combined with Sturm’s theorem’s total number of roots of P in the same interval, yields the number of roots of P such that Q(a) > 0 and the number of roots of P such that Q(a).
Root isolation for a polynomial with real coefficients entails finding an interval that contains only this root and no other roots for each real root.
This is useful for root finding because it allows for the selection of the root to be found and provides a good starting point for fast numerical algorithms like Newton’s method; it is also useful for certifying the result because if Newton’s method converges outside the interval, one can immediately deduce that it converges to the incorrect root.
When an interval without a root is encountered during this process, it may be removed from the list of intervals to consider. If you come across an interval with exactly one root, you can stop dividing it because it’s an isolation interval. When just isolating intervals remain, the process comes to an end.
Any method for determining the number of real roots in an interval can be utilised with this isolating process. Methods based on Descartes’ rule of signs are more efficient, according to theoretical complexity analysis and actual experience. As a result, Sturm sequences are rarely employed for root isolation currently.
Conclusion
In this article, we have learned about the Sturm theorem and its application which will help in further understanding the concept. We have also seen the proof of the following theorem which further helps in better understanding and question-solving. This article will clarify all the concepts related to the Sturm theorem. It also consists of all the differential equations which helps in logical understanding and a good concept clearing.
