Conte, de Boor - Elementary Numerical Analysis. An Algorithmic Approach (523140), страница 21
Текст из файла (страница 21)
Only five zeros are found, and some of these differ from the correspondingzeros in column A in the second place. In order to confirm that these changes are notjust due to roundoff, and to ascertain the fate of the two missing zeros, we also usedMüller’s method (to be discussed in the next section) which produced the seven zeroslisted in column C. These are accurate to all places shown. Note that zeros 5 and 6 havebeen changed into a complex conjugate pair. Thus a change of 1/100 of 1 percent in oneof the coefficients has led to a change of 10 percent in some of the zeros.
When thecoefficients of a polynomial have been obtained experimentally, errors of this magnitudeare easily encountered in the coefficients. We must, therefore, view with great cautionzeros of polynomials of high degree found in this manner, especially when there is somedoubt about the accuracy of the coefficients.The zeros of the second polynomial, (3.50), are 0.5, 1, 2, 4, and 8. Starting with theinitial guesses 0.45, 0.9, 1.8, 3.6, and 7.2, we computed the zeros in ascending order asshown in column D. Finally, in column E, we have listed the results of computing thesezeros in descending order, i.e., starting with the initial guess 7.2 to get the zero 8, thenusing the reduced polynomial and the initial guess 3.6 to obtain the zero 4, etc.
Althoughthe first zero found is accurate to nine places, subsequent zeros are found only to sixplaces. Moreover, the number of iterations required is greater. This illustrates the pointthat it is best to compute the zeros of smallest absolute value first.COMPUTER RESULTS FOR EXAMPLE 3.123.6POLYNOMIAL EQUATIONS: REAL ROOTS119Maehly has proposed a way of using the reduced polynomial whichavoids the difficulties illustrated above.
Letbe k zeros of apolynomial which have already been found. To find the next zero, onecarries out a Newton iteration on the reduced polynomialbut one does not determineby repeated synthetic division. Rather one leaves it in this form, in which casethe iteration then becomesThis technique appears to be quite effective in producing accurate successive zeros. See Exercise 3.6-7.EXERCISES3.6-1 Using Algorithm 3.9 and a hand calculator, find the real root ofcorrect to seven significant figures.
Determine the remaining zeros from the reduced polynomial, using the quadratic formula. How accurate are these solutions?3.6-2 Using Algorithm 3.9, find the real positive roots of the following polynomial equations:3.6-3 The polynomialusing Algorithm 3.9.has four real zeros. Find them,3.6-4 The polynomialhas the zerosFind these zeros on a computer in ascending order ofmagnitude, choosing initial approximations within 10 percent of the exact solutions. Thenchange the coefficient of x 2 to -39,710, and solve the problem once again.
Observe thechange in the solutions.3.6-5 Use Descartes’ rule of signs and the theorems on polynomial zero bounds to find out asmuch as you can about the location and type of zeros of the polynomial3.66 The polynomialhas a zeroThere is another real positive zero near x = 2. Use Maehly’s technique tofind this zero starting with x0 = 2.3.6-7 Write a program based on Maehly’s method for finding successive real zeros of apolynomial p(x).3.6-8 Find the zeros of the polynomial in Example 3.12 using Maehly’s method and comparewith the results given in Example 3.12.120THE SOLUTION OF NONLINEAR EQUATIONS*3.7 COMPLEX ROOTS AND MÜLLER’S METHODThe methods discussed up to this point allow us to find an isolated zero ofa function once an approximation to that zero is known.
These methodsare not very satisfactory when all the zeros of a function are required orwhen good initial approximations are not available. For polynomial functions there are methods which yield an approximation to all the zerossimultaneously, after which the iterative methods of this chapter can beapplied to obtain more accurate solutions. Among such methods may bementioned the quotient-difference algorithm [2] and the method of Graeffe[5].A method of recent vintage, expounded by Miiller [6], has been usedon computers with remarkable success.
This method may be used to findany prescribed number of zeros, real or complex, of an arbitrary function.The method is iterative, converges almost quadratically in the vicinity of aroot, does not require the evaluation of the derivative of the function, andobtains both real and complex roots even when these roots are not simple.Moreover, the method is global in the sense that the user need notsupply an initial approximation. In this section we describe briefly how themethod is derived, omitting any discussion of convergence, and we discussits use in finding both real and complex roots. We will especially emphasize the problem of finding complex zeros of polynomials with realcoefficients since this problem is of great concern in many branches ofengineering.Müller’s method is an extension of the secant method. To recall, in thesecant method we determine, from the approximations xi , xi-1 to a root off(x) = 0, the next approximation xi+1 as the zero of the linear polynomialp(x) which goes through the two points {x i f(x i )} and {x i-1 f(x i-1 )}.
InMüller’s method, the next approximation, xi+1, is found as a zero of theparabola which goes through the three points {x i , f(x i )}, {x i-1 , f(x i-1 },and {x i - 2 , f(x i - 2 )}.As shown in Chap. 2, the functionis the unique parabola which agrees with the function f(x) at the threepoints xi , xi-1 , xi-2 .
Sincewe can also write p(x) in the form(3.51)withI*3.7Thus any zeroCOMPLEX ROOTS AND MÜLLER'S METHOD121of the parabola p(x) satisfies(3.52)according to one version of the standard quadratic formula [see (1.20)]. Ifwe choose the sign in (3.52) so that the denominator will be as large inmagnitude as possible, and if we then label the right-hand side of (3.52) ashi+1, then the next approximation to a zero of f(x) is taken to beThe process is then repeated using xi-1 , xi , xi+1 as the three basicapproximations.
If the zeros obtained from (3.52) are real, the situation ispictured graphically in Fig. 3.8. Note, however, that even if the zero beingsought is real, we may encounter complex approximations because thesolutions given by (3.52) may be complex. However, in such cases thecomplex component will normally be so small in magnitude that it can beneglected. In fact, in the subroutine given below, any complex componentsencountered in seeking a real zero can be suppressed.Figure 3.8The sequence of steps required in Müller’s method is formalized inAlgorithm 3.10.Algorithm 3.10: Müller’s method1. Let x0, x1, x2 be three approximations to a zerof(x0 ), f(x1 ), f(x2 ).Compute122THE SOLUTION OF NONLINEAR EQUATIONS2. Compute3.
Set i = 24. Compute5. Computechoosing the sign so that the denominator is largest in magnitude.6. Set xi+1 = xi + hi+17. Compute8. Set i = i + 1 and repeat steps 4-7 until either of the followingcriteria is satisfied for prescribedor until the maximum number of iterations is exceeded.A complete subroutine based on this algorithm is given below. Thecalling parameters for the subroutine are explained in the comment cards.ZEROS(I) is a one-dimensional array containing initial estimates of thedesired zeros. The subroutine automatically computes two additional approximations to ZEROS(I) as ZEROS(I) + .5 and ZEROS(I) - .5 andthen proceeds with the Müller algorithm.SUBROUTINE MULLER ( FN, FNREAL, ZEROS, N, NPREV, MAXIT, EP1, EP2C DETERMINES UP TO N ZEROS OF THE FUNCTION SPECIFIED BY FN , USINGC QUADRATIC INTERPOLATION, I.E., MUELLER'S METHOD .EXTERNAL FNLOGICAL FNREALINTEGER MAXIT,N,NPREV, KOUNTREAL EP1,EP2, EPS1,EPS2COMPLEX ZEROS(N), C,DEN,DIVDF1,DIVDF2,DVDF1P,FZR,FZRDFLl ,FZRPRV,H,ZERO,SQRC****** I N P U T ******C FN NAME OF A SUBROUTINE, OF THE FORM FN(Z, FZ) WHICH, FOR GIVENZ , RETURNS F(Z) .
MUST APPEAR IN AN E X T E R N A L STATECMENT IN THE CALLING PROGRAM .CC FNREAL A LOGICAL VARIABLE. IF .TRUE., ALL APPROXIMATIONS ARE TAKENTO BE REAL, ALLOWING THIS ROUTINE TO BE USED EVEN IF F(Z) ISCONLY DEFINED FOR REAL Z .CC ZEROS(l),...,ZEROS(NPREV) CONTAINS PREVIOUSLY FOUND ZEROS (IF*3.7COMPLEX ROOTS AND MÜLLER’S METHOD123NPREV .GT. 0).CC ZEROS(NPREV+l),...,ZEROS(N) CONTAINS FIRST GUESS FOR THE ZEROS TO BEFOUND.
(IF YOU KNOW NOTHING, 0 IS AS GOOD A GUESS AS ANY.)CC MAXIT MAXIMUM NUMBER OF FUNCTION EVALUATIONS ALLOWED PER ZERO.C EP1 ITERATION IS STOPPED IF ABS(H) .LT. EP1*ABS(ZR), WITHH = LATEST CHANGE IN ZERO ESTIMATE ZERO .CC EP2 ALTHOUGH THE EP1 CRITERION IS NOT MET, ITERATION IS STOPPED IFCABS(F(ZER0)) .LT. EP2 .C N TOTAL NUMBER OF ZEROS TO BE FOUND .C NPREV NUMBER OF ZEROS FOUND PREVIOUSLY .C****** 0 U T P U T ******C ZEROS(NPREV+l), . . . . ZEROS(N) APPROXIMATIONS TO ZEROS .CINITIALIZATIONCEPS1 = MAX(EP1, 1.E-12)EPS2 = MAX(EP2, 1.E-20)CDO 100 I=NPREV+1,NKOUNT = 0CCOMPUTE FIRST THREE ESTIMATES FOR ZERO ASCZEROS(I)+5., ZEROS(I)-.5, ZEROS(I)1ZERO = ZEROS(I)H = .5CALL DFLATE(FN, ZERO+.5, I, KOUNT, FZR, DVDF1P, ZEROS, 1)CALL DFLATE(FN, ZERO-.5, I, KOUNT, FZR, FZRPRV, ZEROS, l)HPREV = -1.DVDF1P = (FZRPRV - DVDF1P)/HPREVCALL DFLATE(FN, ZERO, I, KOUNT, FZR, FZRDFL, ZEROS, l l)CDO WHILE KOUNT.LE.MAXIT OR H IS RELATIVELY BIGOR FZR = F(ZERO)IS NOT SMALLCOR FZRDFL = FDEFLATED(ZERO)IS NOT SMALL OR NOT MUCHCCBIGGER THAN ITS PREVIOUS VALUE FZRPRV40DIVDF1 = (FZRDFL - FZRPRV)/HDIVDF2 = (DIVDF1 - DVDF1P)/(H + HPREV)HPREV = HDVDF1P = DIVDF1C = DIVDF1 + H*DIVDF2SQR = c*c - 4.*FZRDFL*DIVDF2IF (FNREAL .AND.
REAL(SQR) .LT. 0.) SQR = 0.SQR = S Q R T ( S Q R )IF (REAL(C)*REAL(SQR)+AIMAG(C)*AIMAG(SQR) .LT. 0.) THENDEN = C - SQRELSEDEN = C + SQREND IFIF (ABS(DEN) .LE. 0.) DEN = 1.H = -2.*FZRDFL/DENFZRPRV = FZRDFLZERO = ZERO + HIF (KOUNT .GT. MAXIT)GO TO 99CCALLDFLATE(FN,ZERO,I,KOUNT,FZR, FZRDFL, ZEROS, *l)70CCHECK FOR CONVERGENCEIF (ABS(H) .LT. EPS1*ABS(ZERO)) GO TO 99IF (MAX(ABS(FZR),ABS(FZRDFL)) .LT. EPS2) GO TO 99CHECK FOR DIVERGENCECIF (ABS(FZRDFL) .GE. 10.*ABS(FZRPRV)) THENH = H/2ZERO = ZERO - HGO TO 70ELSEGO TO 40END IF99ZEROS(I) = ZERO100 CONTINUERETURNSUBROUTINE DFLATE ( FN, ZERO, I, KOUNT, FZERO, FZRDFLi ZEROS, * )C TO BE CALLED INM U L L E RINTEGER I,KOUNT, JCOMPLEXFZERO,FZRDFL,ZERO,ZEROS(I), DEN124THE SOLUTION OF NONLINEAR EQUATIONSKOUNT = KOUNT + 1CALL FN(ZER0, FZERO)FZRDFL = FZEROIF (I .LT.
2)DO 10 J=2,IDEN = ZERO - ZEROS(J-1)IF (ABS(DEN) .EQ. 0.) THENZEROS(I) = ZERO*1.001RETURNRETURNELSEFZRDFL = FZRDFL/DENEND IF10 CONTINUERETURNENDMüller’s method, like the other algorithms described in this chapter,finds one zero at a time. To find more than one zero it uses a procedureknown as deflation. If, for example, one zerohas already been found,the routine calculates the next zero by working with the function(3.53)We already met this technique when solving polynomial equations byNewton’s method, in which case the deflated or reduced function f1(x) wasa by-product of the algorithm.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
