c9-5 (779535)
Текст из файла
9.5 Roots of Polynomials3699.5 Roots of PolynomialsDeflation of PolynomialsWhen seeking several or all roots of a polynomial, the total effort can besignificantly reduced by the use of deflation. As each root r is found, the polynomialis factored into a product involving the root and a reduced polynomial of degreeone less than the original, i.e., P (x) = (x − r)Q(x). Since the roots of Q areexactly 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 successiveroots. Even more important, with deflation we can avoid the blunder of having ouriterative method converge twice to the same (nonmultiple) root instead of separatelyto two different roots.Deflation, which amounts to synthetic division, is a simple operation that actson the array of polynomial coefficients.
The concise code for synthetic division by amonomial factor was given in §5.3 above. You can deflate complex roots either byconverting that code to complex data type, or else — in the case of a polynomial withreal 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 knownwith only finite accuracy, errors creep into the determination of the coefficients ofthe successively deflated polynomial. Consequently, the roots can become more andmore inaccurate. It matters a lot whether the inaccuracy creeps in stably (plus orSample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.
Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).Here we present a few methods for finding roots of polynomials. These willserve for most practical problems involving polynomials of low-to-moderate degreeor for well-conditioned polynomials of higher degree.
Not as well appreciated as itought to be is the fact that some polynomials are exceedingly ill-conditioned. Thetiniest changes in a polynomial’s coefficients can, in the worst case, send its rootssprawling all over the complex plane. (An infamous example due to Wilkinson isdetailed by Acton [1].)Recall that a polynomial of degree n will have n roots. The roots can be realor complex, and they might not be distinct. If the coefficients of the polynomial arereal, then complex roots will occur in pairs that are conjugate, i.e., if x1 = a + biis 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 numericalalgorithms (see Figure 9.5.1). For example, P (x) = (x − a)2 has a double real rootat x = a. However, we cannot bracket the root by the usual technique of identifyingneighborhoods where the function changes sign, nor will slope-following methodssuch as Newton-Raphson work well, because both the function and its derivativevanish at a multiple root. Newton-Raphson may work, but slowly, since largeroundoff errors can occur. When a root is known in advance to be multiple, thenspecial methods of attack are readily devised. Problems arise when (as is generallythe case) we do not know in advance what pathology a root will display.370Chapter 9.Root Finding and Nonlinear Sets of Equationsf (x)f (x)(a)x(b)Figure 9.5.1.
(a) Linear, quadratic, and cubic behavior at the roots of polynomials. Only under highmagnification (b) does it become apparent that the cubic has one, not three, roots, and that the quadratichas two roots rather than none.minus a few multiples of the machine precision at each stage) or unstably (erosion ofsuccessive significant figures until the results become meaningless). Which behavioroccurs depends on just how the root is divided out.
Forward deflation, where thenew polynomial coefficients are computed in the order from the highest power of xdown to the constant term, was illustrated in §5.3. This turns out to be stable if theroot of smallest absolute value is divided out at each stage. Alternatively, one can dobackward deflation, where new coefficients are computed in order from the constantterm up to the coefficient of the highest power of x. This is stable if the remainingroot of largest absolute value is divided out at each stage.A polynomial whose coefficients are interchanged “end-to-end,” so that theconstant becomes the highest coefficient, etc., has its roots mapped into theirreciprocals. (Proof: Divide the whole polynomial by its highest power xn andrewrite it as a polynomial in 1/x.) The algorithm for backward deflation is thereforevirtually identical to that of forward deflation, except that the original coefficients aretaken in reverse order and the reciprocal of the deflating root is used.
Since we willuse forward deflation below, we leave to you the exercise of writing a concise codingfor backward deflation (as in §5.3). For more on the stability of deflation, consult [2].To minimize the impact of increasing errors (even stable ones) when usingdeflation, it is advisable to treat roots of the successively deflated polynomials asonly tentative roots of the original polynomial. One then polishes these tentative rootsby taking them as initial guesses that are to be re-solved for, using the nondeflatedoriginal polynomial P . Again you must beware lest two deflated roots are inaccurateenough that, under polishing, they both converge to the same undeflated root; in thatcase you gain a spurious root-multiplicity and lose a distinct root.
This is detectable,since you can compare each polished root for equality to previous ones from distincttentative roots. When it happens, you are advised to deflate the polynomial justonce (and for this root only), then again polish the tentative root, or to use Maehly’sprocedure (see equation 9.5.29 below).Below we say more about techniques for polishing real and complex-conjugateSample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.
Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).x3719.5 Roots of PolynomialsMuller’s MethodMuller’s method generalizes the secant method, but uses quadratic interpolationamong three points instead of linear interpolation between two. Solving for thezeros of the quadratic allows the method to find complex pairs of roots.
Given threeprevious guesses for the root xi−2 , xi−1 , xi , and the values of the polynomial P (x)at those points, the next approximation xi+1 is produced by the following formulas,xi − xi−1xi−1 − xi−2A ≡ qP (xi ) − q(1 + q)P (xi−1 ) + q 2 P (xi−2 )q≡(9.5.2)B ≡ (2q + 1)P (xi ) − (1 + q)2 P (xi−1 ) + q 2 P (xi−2 )C ≡ (1 + q)P (xi )followed byxi+1 = xi − (xi − xi−1 )2C√B ± B 2 − 4AC(9.5.3)where the sign in the denominator is chosen to make its absolute value or modulusas large as possible. You can start the iterations with any three values of x that youlike, e.g., three equally spaced values on the real axis.
Note that you must allowfor the possibility of a complex denominator, and subsequent complex arithmetic,in implementing the method.Muller’s method is sometimes also used for finding complex zeros of analyticfunctions (not just polynomials) in the complex plane, for example in the IMSLroutine ZANLY [3].Laguerre’s MethodThe second school regarding overall strategy happens to be the one to whichwe belong. That school advises you to use one of a very small number of methodsthat will converge (though with greater or lesser efficiency) to all types of roots:real, complex, single, or multiple.
Use such a method to get tentative values for alln roots of your nth degree polynomial. Then go back and polish them as you desire.Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.
Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).tentative roots. First, let’s get back to overall strategy.There are two schools of thought about how to proceed when faced with apolynomial of real coefficients.
One school says to go after the easiest quarry, thereal, distinct roots, by the same kinds of methods that we have discussed in previoussections for general functions, i.e., trial-and-error bracketing followed by a safeNewton-Raphson as in rtsafe. Sometimes you are only interested in real roots, inwhich case the strategy is complete. Otherwise, you then go after quadratic factorsof the form (9.5.1) by any of a variety of methods.
One such is Bairstow’s method,which we will discuss below in the context of root polishing. Another is Muller’smethod, which we here briefly discuss.372Chapter 9.Root Finding and Nonlinear Sets of EquationsPn (x) = (x − x1 )(x − x2 ) . . . (x − xn )ln |Pn (x)| = ln |x − x1 | + ln |x − x2 | + . .
. + ln |x − xn |(9.5.4)(9.5.5)111P0d ln |Pn (x)|=+++...+= n ≡ G (9.5.6)dxx − x1x − x2x − xnPnd2 ln |Pn (x)|111−=+++...+dx2(x − x1 )2(x − x2 )2(x − xn )2 0 2P 00Pn=− n ≡H(9.5.7)PnPnStarting from these relations, the Laguerre formulas make what Acton [1] nicely calls“a rather drastic set of assumptions”: The root x1 that we seek is assumed to belocated some distance a from our current guess x, while all other roots are assumedto be located at a distance bx − x1 = a ;x − xi = b i = 2, 3, .
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
