Finding Multiple Roots of Equations

[trouty323]

Homework Statement

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!

 

[Dick]

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.

 

[Dickfore]

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 $\alpha$ is a root of the polynomial, then, by definition, $r \equiv P_n(\alpha) = 0$. 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.