| Finding Multiple Roots |
Article Index for Finding |
Website Links For Finding |
Information AboutFinding Multiple Roots |
|
ALGORITHM 1. First, we need to determine whether p(x) has a multiple root. If p(x) has a multiple root at r, then its derivative p'(x) will also have a root at r (one fewer root(s) than p(x) does). So we calculate the greatest common divisor of the polynomials p(x) and p'(x); take the leading coefficient to be one and call it g(x). If g(x)=1, then p(x) has no multiple roots and we can safely use those other root-finding algorithms which work best when there are no multiple roots. 2. Now suppose that there is a multiple root. Notice that g(x) will have the same number of roots at r that p'(x) does and the degree of the polynomial g(x) will generally be much less than that of p(x). Recursively call this routine, i.e. go back to step #1 above, using g(x) in place of p(x). Now suppose that we have found the roots of g(x), i.e. we have factored it. 3. Since r has been found, we can factor (x-r) out of p(x) repeatedly until we have all of the multiple roots at r removed. Repeat this for any other multiple roots until there are no more multiple roots. Then the quotient, i.e. the remaining part of p(x), can be factored in the usual way with one of the other root-finding algorithms. EXAMPLE Suppose p(x)=x^3+x^2-5x+3 is the function whose roots we want to find. We calculate p'(x)=3x^2+2x-5. Now divide p'(x) into p(x) to get p(x)=p'(x)·((1/3)x+(1/9))+((-32/9)x+(32/9)). Divide the remainder by -32/9 to get x-1 which is monic. Divide x-1 into p'(x) to get p'(x)=(x-1)·(3x+5)+0. Since the remainder is zero, g(x)=x-1. So the multiple root of p(x) is r=1. Dividing p(x) by (x-1)^2, we get p(x)=(x+3)(x-1)^2 so the other root is -3, a single root. SEE ALSO |
|
|