Conte, de Boor - Elementary Numerical Analysis. An Algorithmic Approach (523140), страница 20
Текст из файла (страница 20)
Thus we must have either threepositive real zeros and one negative real zero, or one positive real zero, one negative realzero, and two complex conjugate zeros.We now quote several theorems which give bounds on the zeros ofpolynomials. One of these states that if p(x) is a polynomial withcoefficients ak as in (3.43), then p(x) has at least one zero inside the circledefined by min{p1, pn } where(3.44)andExample If the polynomial is(3.45)Hence there must be at least one zero, real or complex, inside the circle |x| < 1.46 · · · .Actually we consider this polynomial (3.45) in more detail in the next section where weshow that the exact zeros areand 1.7.A second useful theorem, attributable to Cauchy, allows us to establishbounds on the zeros of p(x) as follows.
If p(x) is the polynomial (3.43), wedefine two new polynomials as follows:(3.46)(3.46 a )By Descartes’ rule of signs, (3.46) has exactly one real positive zero Rand (3.46a) has exactly one real positive zero r. The Cauchy theorem then112THE SOLUTION OF NONLINEAR EQUATIONSstates that all the zeros of p(x) lie in the annular regionExample Consider again the polynomial (3.45). Then we havewhose positive zeros are R = 5.6 · · · , r = 0.63 · · · respectively. Hence all the zeros ofp(x) must satisfyA final theorem of this type states that if p(x) is a polynomial of theform (3.43) and ifthen every zero of p(x) lies in the circular region defined by |x| < r.Example If we consider the polynomial (3.2),then r = 1 + 1/1 = 2.0 so that all zeros of p(x) lie in a disk centered at the origin withradius 2.
In Sec. 3.1 we found one real zero to beThe other two zerosare complex but still inside the circle |x| < 2.We now turn to the consideration of iterative methods for finding realzeros of polynomials. In any iterative method we shall have to evaluate thepolynomial frequently and so this should be done as efficiently as possible.As shown in Chap. 2, the most efficient method for evaluating a polynomial is nested multiplication as described in Algorithm 2.1.In Algorithm 2.1, the polynomial was assumed given in the Newtonform (2.3) with centers c1, . . .
, cn. If the centers are all equal to zero, theNewton form (2.3) reduces to the standard power form (3.43). If now weare given a point z, Algorithm 2.1 for determining p(z) specializes to(3.47)The auxiliary quantitiesare of independent interest for we3.6POLYNOMIAL EQUATIONS: REAL ROOTS113have from (2.4), by again setting all the ck to zero, that(3.48)Hence,are the coefficients of the quotient polynomial q(x)obtained by dividing p(x) by the linear polynomial (x - z) andis theremainder. In particular if we set x = z in (3.48) we get anew thatExample 3.9: Converting a binary integer into a decimal integer In Sec.
1.1, we presentedAlgorithm 1.1 for converting a binary integer into a decimal integer. By convention, thebinary integerwith the ai either zero or one, represents the numberIts decimal equivalent can therefore be found by evaluating the polynomialat x = 2, using the nested multiplication Algorithm 2.1. This shows Algorithm 1.1 to bea special case of Algorithm 2.1. As an application, the binary integer aisconverted to its decimal equivalent, as follows:Our immediate goal is to adapt Newton’s method to the problem offinding real zeros of polynomials. To do this, we must be able to evaluatenot only p(x) but also p’(x). To find p’(x) at x = z, we differentiate (3.48)with respect to x and obtainHence, on setting x = z,Since q(x) is itself a polynomial whose coefficients we know, we can applyAlgorithm 2.1 once more to find q(z), and therefore p’(z).
This gives thefollowing algorithm.Algorithm 3.9: Newton’s method for finding real zeros of polynomialsGiven the n + 1 coefficients a o , . . . , a n of the polynomial p(x) in114THE SOLUTION OF NONLINEAR EQUATIONS(3.43) and a starting point x0.Example 3.10 Find all the roots of the polynomial equation p(x) = x3 + x - 3 = 0.This equation has one real root and two complex roots. Since p(1) = - 1 andp(2) = 7, the real root must lie between x = 1 and x = 2. We choose x0 = 1.1 and applyAlgorithm 3.9, carrying out all calculations on a hand calculator and retaining fiveplaces after the decimal point.Note thatis approaching zero and that theare converging.
No furtherimprovement is possible in the solution or in theconsidering the precision to whichwe are working. We therefore accept x 3 = 1.21341, which is correct to at least fivesignificant figures, as the desired real root. To find the remaining complex roots, weapply the quadratic formula to the polynomial equationThis yields the results3.6POLYNOMIAL EQUATIONS: REAL ROOTS115for the remaining roots. As a comparison, the zeros of this polynomial will be foundagain in Sec. 3.7, using a complex-root finder.Example 3.11 Find the real positive root of the polynomial equationIt is easily verified that the root lies between 1 and 2. We choose x0 = 1.5.
TheFORTRAN program and machine results are given below. The exact root is 1.7, so thatthe machine result is correct to eight figures.FORTRAN PROGRAM FOR EXAMPLE 3.11C NEWTON'S METHOD FOR FINDING A REAL ZERO OF A CERTAIN POLYNOMIAL.C THE COEFFICIENTS ARE SUPPLIED IN A DATA STATEMENT. A FIRST GUESSCX FOR THE ZERO IS READ IN .PARAMETER N=6INTEGER J,KREAL A(N),B,C,DELTAX,XDATA A /-6.8, 10.8, -10.8, 7.4, -3.7, l./1 READ 500, X500 FORMAT(E16.8)PRINT 601601 FORMAT('1NEWTONS METHOD FOR FINDING A REAL ZERO OF A POLYNOMIAL'//4X,'I' ,10X,'X',14X,'AP(0)',12X,'APP(1)'/)*DO 10 J=1,20B = A(N)C = BDO 5 K=N,3,-1B = A(K-1) + X*BC = B + X*C5CONTINUEB = A(1) + X*BPRINT 605,J,X,B,C605FORMAT(I5,3(1PE17.7))DELTAX = B/CIF (ABS(DELTAX) .LT.
l.E-7 .OR. ABS(B) .LT. l.E-7) STOPX = X - DELTAX10 CONTINUEPRINT 610610 FORMAT(' FAILED TO CONVERGE IN 20 ITERATIONS')GO TO 1ENDCOMPUTER RESULTS FOR EXAMPLE 3.11Although in the examples above we encountered no real difficulties inobtaining accurate solutions, the student is warned against assuming that116THE SOLUTION OF NONLINEAR EQUATIONSpolynomial root finding is without pitfalls. We enumerate some of thedifficulties which may be encountered.1. In Newton’s method the accuracy of the zero is limited by the accuracyto which the correction term p(x i )/p'(x i ) can be computed.
If, forexample, the error in computing p(xi ), due to roundoff or other causes,is then the computed zero can be determined only up to the actualzero plusFigure 3.1 shows dramatically the magnitude ofpossible errors. Substantial errors will also arise if p(x) has a doublefor then p’(x) will vanish asand any round-offzero aterrors in computing p(xi ) will be magnified.To illustrate the behavior of Newton’s method around a doubleroot, we consider the polynomialwhich has a double zero at x = 2.
Choosing x0 = 1.5, we obtain, usingt h e I B M 7 0 9 4 ( a m a c h i n e with 27-binary-digit floating-pointarithmetic), the results in Table 3.1.The numbers after E indicate the exponents of 10. The underlineddigits are known to be incorrect because of loss of significance incomputing p(xi ) and p'(xi ).
From this table we may make the followingobservations (see Exercise 3.5-5 in this connection):a. The iterates are converging in spite of the fact that p'(2) = 0.Table 3.13.62.3.4.5.POLYNOMIAL EQUATIONS: REAL ROOTS117b. The rate of convergence is linear, not quadratic, as is normally thecase for Newton’s method. An examination of the correctionsp(x i )/p'(x i ) shows that the error is being reduced by a factor ofabout with each iteration, up to iteration 12.c. After iteration 13 we can expect no further improvement in thesolution.
This is because there are no correct figures left in p(xi ), andat the same time p'(xi ) is of the order of 10-3 . Thus the quotientp(x i )/p'(x i ) will produce an incorrect result in the fifth decimalplace, making it impossible to improve the solution.In some cases an improper choice of the initial approximation will causeconvergence to a zero other than the one desired.For some polynomials an improper choice of x0 may lead to a divergentsequence. In Example 3.2, for instance, if we take x0 = 0, we obtain thesuccessive approximationsx5 = - 1.40, which certainly do not appear to be converging to the zeroobtained before.
An examination of the graph of the polynomial p(x) =x3- x - 1 (see Fig. 3.7) will help to explain this behavior. The successive iterates may oscillate indefinitely about the pointatwhich p(x) has a maximum value.Some polynomials, especially those of high degree, are very unstable, inthe sense that small changes in the coefficients will lead to large changesin the zeros (see Example 3.12 below).Once we have found a zero of a polynomial p(x), the nested multiplication Algorithm (3.47) supplies us with the coefficientsof thepolynomial q(x) which has all the remaining zeros of p(x) as zeros. Tofind these zeros it would therefore seem simpler to deal with the reducedor deflated polynomial q(x) rather than with p(x).
But we can expect aloss of accuracy in the later zeros because the coefficients in thereduced polynomials will contain errors from incomplete convergenceFigure 3.7118THE SOLUTION OF NONLINEAR EQUATIONSand from roundoff. To minimize such loss of accuracy, the zeros shouldbe obtained in increasing order of magnitude (see Example 3.12). Also,the accuracy of a zero found from a reduced polynomial can beimproved by iterating with the original polynomial.Example 3.12 To illustrate some of the dangers in polynomial zero finding, we considerthe two polynomials(3.49)and(3.50)We have used Newton’s method (on a CDC 6500) to find all the zeros of thesepolynomials, working with the reduced polynomial at each stage, with roughly 10percent error in the initial guess, and with the termination criterion |x i - x i - 1 | <10 - 7 |x i |.The zeros of the first polynomial, (3.49), are 1, 2, 3, 4, 5, 6, and 7.
Column A in thetable below contains the approximations found, starting with the initial guesses 0.9, 1.9,2.9, 3.9, 4.9, 5.9, and 6.9. The number of iterations required is listed after each zero.The zeros in column B are those obtained when the coefficient of x2 in (3.49) isreplaced by - 13,133, i.e., after a change of one unit in the fifth place of one coefficientis made.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
