9.5 Roots of Polynomials 369 9.5 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 sprawling all over the complex plane.(An infamous example due to Wilkinson is detailed by Acton [1].) Recall that a polynomial of degree n will have n roots.The roots can be real 81 or complex,and they might not be distinct.If the coefficients of the polynomial are real,then complex roots will occur in pairs that are conjugate,i.e.,if=a+bi 虽2 is a root then z2 =a-bi will also be a root.When the coefficients are complex, the complex roots need not be related. Multiple roots,or closely spaced roots,produce the most difficulty for numerical algorithms (see Figure 9.5.1).For example,P(x)=(x-a)2 has a double real root at z=a.However,we cannot bracket the root by the usual technique of identifying neighborhoods where the function changes sign,nor will slope-following methods 9 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 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. 超% 9 Deflation of Polynomials When seeking several or all roots of a polynomial,the total effort can be 6 significantly reduced by the use of deftation.As each root r is found,the polynomial is factored into a product involving the root and a reduced polynomial of degree one less than the original,i.e.,P(x)=(x-r)Q(z).Since the roots of are exactly the remaining roots of P,the effort of finding additional roots decreases, because we work with polynomials of lower and lower degree as we find successive 10621 roots.Even more important,with deflation we can avoid the blunder of having our iterative method converge twice to the same(nonmultiple)root instead of separately "hg2 Numerical Recipes 43106 to two different roots. Deflation,which amounts to synthetic division,is a simple operation that acts (outside on the array of polynomial coefficients.The concise code for synthetic division by a monomial factor was given in 85.3 above.You can deflate complex roots either by North converting that code to complex data type,or else-in the case of a polynomial with real coefficients but possibly complex roots-by deflating by a quadratic factor, [x-(a+b)][x-(a-b)]=x2-2ax+(a2+b2) (9.5.1) The routine poldiv in 85.3 can be used to divide the polynomial by this factor. Deflation must,however,be utilized with care.Because each new root is known with only finite accuracy,errors creep into the determination of the coefficients of the successively deflated polynomial.Consequently,the roots can become more and more inaccurate.It matters a lot whether the inaccuracy creeps in stably (plus or9.5 Roots of Polynomials 369 Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machine￾readable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). 9.5 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 sprawling all over the complex plane. (An infamous example due to Wilkinson is detailed by Acton [1].) Recall that a polynomial of degree n will have n roots. The roots can be real or complex, and they might not be distinct. If the coefficients of the polynomial are real, then complex roots will occur in pairs that are conjugate, i.e., if x1 = a + bi is a root then x2 = a − bi will also be a root. When the coefficients are complex, the complex roots need not be related. Multiple roots, or closely spaced roots, produce the most difficulty for numerical algorithms (see Figure 9.5.1). 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 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 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. Deflation of Polynomials 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 is factored into a product involving the root and a reduced polynomial of degree one less than the original, i.e., P(x)=(x − r)Q(x). Since the roots of Q are exactly the remaining roots of P, the effort of finding additional roots decreases, because we work with polynomials of lower and lower degree as we find successive roots. Even more important, with deflation we can avoid the blunder of having our iterative method converge twice to the same (nonmultiple) root instead of separately to two different roots. Deflation, which amounts to synthetic division, is a simple operation that acts on the array of polynomial coefficients. The concise code for synthetic division by a monomial factor was given in §5.3 above. You can deflate complex roots either by converting that code to complex data type, or else — in the case of a polynomial with real coefficients but possibly complex roots — by deflating by a quadratic factor, [x − (a + ib)] [x − (a − ib)] = x2 − 2ax + (a2 + b2) (9.5.1) The routine poldiv in §5.3 can be used to divide the polynomial by this factor. Deflation must, however, be utilized with care. Because each new root is known with only finite accuracy, errors creep into the determination of the coefficients of the successively deflated polynomial. Consequently, the roots can become more and more inaccurate. It matters a lot whether the inaccuracy creeps in stably (plus or