Here we present a few methods for finding roots of polynomials. These will serve for most practical problems involving polynomials of low-to-moderate degree or for well-conditioned polynomials of higher degree. | Roots ofPolynomials 369 Roots of Polynomials Here we present a few methods for finding roots of polynomials. These will serve for most practical problems involving polynomials of low-to-moderate degree or for well-conditioned polynomials of higher degree. Not as well appreciated as it ought to be is the fact that some polynomials are exceedingly ill-conditioned. The tiniest changes in a polynomial s coefficients can in the worst case send its roots J sprawling all over the complex plane. An infamous example due to Wilkinson is detailed by Acton 1 . 8 S Recall that a polynomial of degree n will have n roots. The roots can be real g B g or complex and they might not be distinct. If the coefficients of the polynomial are g real then complex roots will occur in pairs that are conjugate . if x1 a bi is a root then x2 a bi will also be a root. When the coefficients are complex 8 the complex roots need not be related. Multiple roots or closely spaced roots produce the most difficulty for numerical 8 g algorithms see Figure . For example P x x a 2 has a double real root at x a. However we cannot bracket the root by the usual technique of identifying p s 3 neighborhoods where the function changes sign nor will slope-following methods such as Newton-Raphson work well because both the function and its derivative vanish at a multiple root. Newton-Raphson may work but slowly since large 8 roundoff errors can occur. When a root is known in advance to be multiple then special methods of attack are readily devised. Problems arise when as is generally - the case we do not know in advance what pathology a root will display. o Deflation of Polynomials sill e P- z When seeking several or all roots of a polynomial the total effort can be significantly reduced by the use of deflation. As each root r is found the polynomial g is factored into a product involving the root and a reduced polynomial of degree one less than the original . P x x r Q x . Since the roots
