finding number of root determined interval

Question

I have n degree polynomial system ,just I want to learn number of root between previously determined interval .But I do not want to find root.I need number of root.I need to write python code. For example : x^8+2x^6+5x^4+x^2+45x+1=0 How many root have we between 3-5? emphasize=I do not want to find root,just I want to learn how many root I have.

what have you tried? look how many times the function changes sign within your interval. — Julien, Jul 28 '16 at 06:56
Firstly we want to find million degree polynomial problem and we want to write python code,secondly if we have tuple-root ,the sign will not change so the some roots will lost . And if it is easy please solve the example — harun eroğlu, Jul 28 '16 at 07:51
your example is a polynomial of degree 8 so can have 8 roots maximum. Easily solved. Where do you get your million degree polynomial from? How can you have a tuple root? Is it a multivariate polynomial? If your real problem is harder, please give an example that reflects the difficulty of your problem. — Julien, Jul 28 '16 at 08:02
I think by tuple root, @haruneroğlu means that there can be repeated roots and the function can have less than 8 real roots. For example, `(x-1)**2` has a tuple root at 1. — Saurav Gupta, Jul 28 '16 at 10:54
x^6-3x^5+2x^4=0 how many root we have between 2 to 4 ([2,4]) ? DO NOT SOLVE THE ROOTS. In here we have just 1 root between this interval.BUT WE WANT TO LEARN THİS INFORMATION WİTHOUT SOLVE THE EQUATION.(WITHOUT FİND THE ROOT) — harun eroğlu, Jul 28 '16 at 13:53
First, turn off your CAPS LOCK. Look at this [answer](http://stackoverflow.com/a/4518339/6495334). Try to implement the algorithm given. If you face any difficulties, ask here nicely. — Saurav Gupta, Jul 28 '16 at 14:59
I added an edit to the answer where "WE LEARN THİS INFORMATION WİTHOUT SOLVE THE EQUATION". Please take a look. — Saurav Gupta, Jul 28 '16 at 15:32
If you have confusion regarding how the code works, please do ask. — Saurav Gupta, Jul 28 '16 at 15:37

score 0 · Accepted Answer · edited May 23 '17 at 12:17

You can do this with numpy

import numpy as np
coeff = [1,0,2,0,5,0,1,45,1] #for the polynomial  x^8+2x^6+5x^4+x^2+45x+1=0
np.roots(coeff) 
 # array([ 1.37234708+0.91495949j,  1.37234708-0.91495949j,
 #   0.43013459+1.75225934j,  0.43013459-1.75225934j,
 #  -1.06175643+1.53395567j, -1.06175643-1.53395567j,
 #  -1.45921726+0.j        , -0.02223323+0.j        ])

Thus, as you can see, this one has zero real roots.

Edit: If you want to find the number of roots between an interval without finding the roots explicitly, you can use sturm's theorem. Using sympy,

from sympy import Sturm,Symbol
from sympy.abc import x
sturm_seq = sturm(x**6-3*x**5+2*x**4)
limits = [2,4]; x = Symbol('x')
values_at_start = [polynomial.subs(x,limits[0]).evalf() for polynomial in sturm_seq]
values_at_end = [polynomial.subs(x,limits[1]).evalf() for polynomial in sturm_seq]
import itertools
# Count number of sign changes in values_at_start
count_start = len(list(itertools.groupby(values_at_start, lambda values_at_start: values_at_start > 0)))
count_end = len(list(itertools.groupby(values_at_end, lambda values_at_end: values_at_end > 0)))
ans = count_start - count_end
print ans # ans = 1

finding number of root determined interval

1 Answers1