Conte, de Boor - Elementary Numerical Analysis. An Algorithmic Approach (523140), страница 19
Текст из файла (страница 19)
It may happen, for example, that f’(x), though it does notvanish, is very small near the zero. In this case, we can expect that anyerrors in f(x) will be magnified when f(x)/f’(x) is computed. In such cases,it will be difficult to obtain good accuracy.There are two major disadvantages to Newton’s method. First, one hasto start “close enough” to a zero of f(x) to ensure convergence to (SeeExercise 3.5-6 but also 3.3-4 and 3.3-5.) Since one usually does not knowthis might be difficult to do in practice, unless one has already obtained agood estimatefor by some other method.
If, for example, one has108THE SOLUTION OF NONLINEAR EQUATIONScalculated an approximationto by the bisection method or some otheriterative method which is good to two or three places, one might startNewton’s method withand carry out two or three iterations toobtain quickly an accurate approximation to In this way, Newton’smethod is often used to improve a good estimate of the zero obtained bysome other means.A second disadvantage of Newton’s method is the necessity to calculate f’(x). In some cases, f’(x) may not be available explicitly, and evenwhen one can evaluate f’(x), this may require considerable computationaleffort.
In the latter case, one can decide to compute f’(xn ) only every ksteps, using the most recently calculated value at every step. But in bothcases, it is usually better to use the secant method instead.The secant method uses only values of f(x), and only one functionevaluation is required per step, while Newton’s method requires twoevaluations per step. On the other hand, when the secant method converges, it does not converge quite as fast as does Newton’s method;although it usually converges much faster than linear.The more rapid rate of convergence of Newton’s method over thesecant method is demonstrated in Example 3.2.In this chapter we have considered six algorithms for finding zeros offunctions.
In comparing algorithms for use on computers one should takeinto account various criteria, the most important of which are assurancesof convergence, the rate of convergence, and computational efficiency. Noone method can be said to be always superior to another method. Thebisection method, for example, while slow in convergence, is certain toconverge when properly used, while Newton’s method will frequentlydiverge unless the initial approximation is carefully selected. The term“computational efficiency” used above attempts to take into account theamount of work required to produce a given accuracy. Newton’s method,although it generally converges more rapidly than the secant method, isnot usually as efficient, because it requires the evaluation of both f(x) andf’(x) for each iteration. In cases where f’(x) is available and easilycomputable, Newton’s method may be more efficient than the secantmethod, but for a general-purpose routine, the secant method will usuallybe more efficient and should be preferred.Algorithms 3.1 to 3.3 all have the advantage that they bracket the zeroand thus guarantee error bounds on the root.
Of these, Algorithm 3.2(regula falsi) should never be used because it fails to produce a contractinginterval containing the zero. In general, of these three, the modified regulafalsi method (Algorithm 3.3) should be preferred.Fixed-point iteration is effective when it converges quadratically, as inNewton’s method. In general, fixed-point iteration converges only linearly,hence offers no real competition to the secant method or the modifiedregula falsi. Even with repeated extrapolation, as in the Steffensen iteration*3.5CONVERGENCE OF THE NEWTON AND SECANT METHODS109algorithm 3.8, convergence is at best only quadratic.
Since one step of theSteffensen iteration costs two evaluations of the iteration function g(x),Steffensen iteration is therefore comparable with Newton’s method. Butsince the extrapolation part of one step of Steffensen iteration is the sameas one step of the secant method applied to the function f(x) = x - g(x),it would seem more efficient to forgo Steffensen iteration altogether, andjust use the secant method on f(x) = x - g(x).The main purpose of discussing fixed-point iteration at all was to gaina simple model for an iterative procedure which can be analyzed easily.The insight gained will be very useful in the discussion of several equationsin several unknowns, in Chap. 5.EXERCISES3.5-l From the definition of fixed-point iteration with iteration function g(x), we know thatthe error of the nth iterate satisfiesWe showed in the text that ifand g”(x) is continuous atthe iterationx - g(x) converges quadratically.
State conditions under which one can expect an iterationto converge cubically.3.5-2 For Newton’s method show that ifand if f(x) is twice continuouslyAlso show thatdifferentiable, then3.5-3 For each of the following functions locate an interval containing the smallest positivezero and show that the conditions of Theorem 3.2 are satisfied.3.5-4 Solve each of the examples in Exercise 3.5-3 by both the secant method and Newton’smethod and compare your results.3.5-5 Ifis a zero of f(x) of order 2, thenShow that in this caseNewton’s method no longer converges quadraticallyAlso showthat ifand f'''(x) is continuous in the neighborhood ofthe iterationdoes converge quadratically. {Hint: For the calculation ofuse the fact thatand L’Hospital’s rule.)3.5-6 Find the root of the equationwhich is closest to 100, by Newton’s method.
(Note: Unless x 0 is very carefully chosen,Newton’s method produces a divergent sequence.)3.5-7 Supply the details of the proof of Theorem 3.2.3.5-8 Prove that, under the conditions of Theorem 3.2, the secant method converges for anychoice of x 0 , x l in the interval [a,b]. Also show that the mode of convergence is either110THE SOLUTION OF NONLINEAR EQUATIONSmonotone or waltzing, depending on the location of two successive iterates. [Hint: Use theerror equation (3.39) and proceed as in the proof for convergence of Newton’s method.]3.5-9 Show that ifis a zero of f(x) of multiplicity m the iterationconverges quadratically under suitable continuity conditions.3.6 POLYNOMIAL EQUATIONS: REAL ROOTSAlthough polynomial equations can be solved by any of the iterativemethods discussed previously, they arise so frequently in physical applications that they warrant special treatment.
In particular, we shall presentsome efficient algorithms for finding real and complex zeros of polynomials. In this section we discuss getting (usually rough) information about thelocation of zeros of a polynomial, and then give Newton’s method forfinding a real zero of a polynomial.A polynomial of (exact) degree n is usually written in the form(3.43)Before discussing root-finding methods, a few comments about polynomialroots may be in order.
For n = 2, p(x) is a quadratic polynomial and ofcourse the zeros may be obtained explicitly by using the quadratic formulaas we did in Chap. 1. There are similar, but more complicated, closed-formsolutions for polynomials of degrees 3 and 4, but for n > 5 there are ingeneral no explicit formulas for the zeros. Hence we are forced to consideriterative methods for finding zeros of general polynomials. The methodsconsidered in this chapter can all be used to find real zeros and some canbe adapted to find complex zeros. Often we are interested in finding all thezeros of a polynomial. A number of theorems from algebra are useful inlocating and classifying the types of zeros of a polynomial.First we have the fundamental theorem of algebra (see Theorem 1.10)which allows us to conclude that every polynomial of degree n withhas exactly n zeros, real or complex, if zeros of multiplicity r are counted rtimes.
If the coefficients a k of the polynomial p(x) are all real and ifz = a + ib is a zero, then so is the numberA useful methodfor determining the number of real zeros of a polynomial with realcoefficients is Descartes’ rule of signs. The rule states that the number np ofpositive zeros of a polynomial p(x) is less than or equal to the number ofvariations in sign of the coefficients of p(x). Moreover, the differenceis an even integer. To determine the number of sign variations, onesimply counts the number of sign changes in the nonzero coefficients ofp(x).
Thus if p(x) = x4 + 2x2 - x - 1; the number of sign changes is oneand by Descartes’ rule p(x) has at most one positive zero, but since3.6POLYNOMIAL EQUATIONS: REAL ROOTS111must be a nonnegative even integer, it must have exactly one positive zero.Similarly the number of negative real zeros of p(x) is at most equal to thenumber of sign changes in the coefficients of the polynomial p(-x) =- x3 - 2x2 - x - 1; there are no sign changes in p(-x) and hence there areno real negative zeros.Example 3.8 Determine as much as you can about the real zeros of the polynomialSince there are three sign changes in the coefficients of p(x), there are either threepositive real zeros or one. Now p(-x) = x4 + x3 - x2 - x - 1, and since there is onlyone sign change there must be one negative real zero.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
