Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Finding Multiple Roots of Equations

  1. Feb 21, 2012 #1
    1. The problem statement, all variables and given/known data

    Hello everyone. My task is to find the largest positive root in a specific interval of a function using the bisection method, Newton-Raphson method, and secant method. I've written code for all three of these methods, but the only way I can find all of the roots is to hard code different intervals. I know that is horrible practice, but the teacher never explained how to find them all using a different approach. However, I did read online that it can be done using Horner's algorithm (synthetic division). Basically, from my understanding, all of the roots can be found if one root is known. However, I could not find examples of code using Horner's algorithm specific to my purpose. I'm not asking for code, but a logical explanation as to how this can be accomplished. I originally posted this in the Computer Science forum, but was directed here. Thanks in advance!
  2. jcsd
  3. Feb 21, 2012 #2


    User Avatar
    Science Advisor
    Homework Helper

    Finding one root doesn't mean you can find all roots. Take x^3+2x^2-x-2. If you find one root, say x=1, then you know (x-1) must divide x^3+2x^2-x-2. Indeed (x^3+2x^2-x-2)/(x-1)=x^2+3x+2. Now the remaining roots must be roots of x^2+3x+2. You've cut the degree of the polynomial you have to solve down by one.
  4. Feb 21, 2012 #3
    AFAK, Horner's method is the division of a polynomial by a linear binomial:
    \left( a_0 \, x^n + a_1 \, x^{n - 1} + \ldots + a_{n - 1} + a_n \right) = (x - \alpha) \, \left( b_0 x^{n - 1} + b_1 \, x^{n - 2} + \ldots + b_{n - 2} \, x + b_{n - 1} \right) + r

    The recursion is as follows:
    b_0 = a_0
    b_{k} = \alpha \, b_{k - 1} + a_{k}, \ k = 1, \ldots, n - 1
    r = \alpha \, b_{n - 1} + a_{n}

    Now, if [itex]\alpha[/itex] is a root of the polynomial, then, by definition, [itex]r \equiv P_n(\alpha) = 0[/itex]. In a numerical procedure, r should be sufficiently small.

    If you managed to find the root of a polynomial largest by absolute value, then you may find the quotient polynomial that is one order lower and repeat the same procedure. In this way, you can enumerate all the roots of the polynomial.

    For non-polynomial functions, I don't know what Horner's method means.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook