Đang chuẩn bị liên kết để tải về tài liệu:
Root Finding and Nonlinear Sets of Equations part 5

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. | 362 Chapter 9. Root Finding and Nonlinear Sets ofEquations a b Move last best guess to a. fa fb if fabs d toll Evaluate new trial root. b d else b SIGN tol1 xm fb func b nrerror Maximum number of iterations exceeded in zbrent return 0.0 Never get here. CITED REFERENCES AND FURTHER READING Brent R.P. 1973 AlgorithmsforMinimizationwithoutDerivatives Englewood Cliffs NJ PrenticeHall Chapters 3 4. 1 Forsythe G.E. Malcolm M.A. and Moler C.B. 1977 Computer Methods for Mathematical Computations Englewood Cliffs NJ Prentice-Hall 7.2. 9.4 Newton-Raphson Method Using Derivative Perhaps the most celebrated of all one-dimensional root-finding routines is Newton s method also called the Newton-Raphson method. This method is distinguished from the methods of previous sections by the fact that it requires the evaluation of both the function f x and the derivative f x at arbitrary points x. The Newton-Raphson formula consists geometrically of extending the tangent line at a current point x until it crosses zero then setting the next guess xi 1 to the abscissa of that zero-crossing see Figure 9.4.1 . Algebraically the method derives from the familiar Taylor series expansion of a function in the neighborhood of a point f x 5 f x f x S ff x62 . 9.4.1 For small enough values of S and for well-behaved functions the terms beyond linear are unimportant hence f x S 0 implies S _ f x 9 4 2 S f x . 9.4.2 Newton-Raphson is not restricted to one dimension. The method readily generalizes to multiple dimensions as we shall see in 9.6 and 9.7 below. Far from a root where the higher-order terms in the series are important the Newton-Raphson formula can give grossly inaccurate meaningless corrections. For instance the initial guess for the root might be so far from the true root as to let the search interval include a local maximum or minimum of the function. This can be death to the method see Figure 9.4.2 . If an iteration places a trial guess near such a local extremum so that the first .