I am writing a program to determine the roots of polynomial functions.

I will be using the secant method to determine the roots.

The problem I am facing is that I have to know at least a bit of information about the function before I apply the secant method, namely:

  1. How many roots are there so I can know once Ive solved for all of them
  2. Where, approximately, are these roots so I can apply appropriate root finding intervals to the secant method

To address point 1, I am using the Fundamental Theorem of Algebra which tells me how many real and how many non-real, complex roots there are

To address point 2, I am using Descartes Rule of Signs which tells me all the possibilities on which side of x axis are the real and complex roots (which, coupled with point 1 above, should tell me exactly how many there are real and non-real, complex).

The problem I am facing is that this is still not enough for me to start guessing where to choose my root finding intervals. The only thing I can possibly think of is to randomly substitute pairs of x values in my f(x) function until I hit a pair of x values that change the sign of f(x). (Recall that if x1 and x2 yield opposite f(x1) and f(x2) values, there must be at least one root in between those values.)

Random sampling (even being complemented with fundamental theorem of algebra and Descartes rule of signs) seems very much like a brute force inefficient method which seems to cancel the benefits of the actual efficient root finding methods.

Are there any other ways I can get around random sampling? How do the proprietary mathematics software achieve finding appropriate intervals for roots?

  • 2
    $\begingroup$ Look at Sturm's theorem. $\endgroup$ – Lázaro Albuquerque Jul 13 '17 at 9:10
  • $\begingroup$ Thanks. I had a look at it. I'll read some more but at first glance it doesn't seem to provide more answers than the two rules above. $\endgroup$ – Dean P Jul 13 '17 at 9:22
  • $\begingroup$ @DeanP Sturm's theorem gives the number and location of real roots, which neither of the others do. $\endgroup$ – dxiv Jul 14 '17 at 23:38

(1). To narrow the search: For $x\in \mathbb C$ let $p(x)=\sum_{j=0}^n A_jx^j$ with $n>0$ and $A_n\ne 0.$ Let $M=\max \{|A_j|/|A_n|:0\leq j\leq n-1\}. $ If $|x|\geq 1+M$ then $p(x)\ne 0.$

Proof: WLOG asume $A_n=1.$ If $|x|\geq 1+M$ then $$|p(x)|\geq |x^n|-\left|\sum_{j=0}^{n-1}A_jx^j\right|\geq |x|^n-\sum_{j=0}^{n-1}|A_j|\cdot |x|^j\geq$$ $$\geq |x|^n-M\sum_{j=0}^{n-1}|x|^j=|x|^n-M\frac {|x|^n-1}{|x|-1} =\frac {|x|^n(|x|-(1+M))+1}{|x|-1|}>0.$$

A linear change of variable may give a narrower range for $|x|.$

Assuming $A_0\ne 0,$ let $y=1/x,$ and this method will give a positive lower bound for the modulus of a zero of $p.$

(2). You should also look at "Graeffe's method" in Wikipedia .


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.