Heath - Scientific Computing (523150), страница 48
Текст из файла (страница 48)
For systems of nonlinear equations, Newton’s method has served to motivate mostother methods, and it is the standard by which they are measured. Indeed, “Newton’smethod” has become as much a paradigm as a specific algorithm, synonymous with local linear approximations to nonlinear problems of many different types. Secant updatingmethods were first developed for optimization problems around 1959, but analogous methods were soon developed for solving systems of nonlinear equations; Broyden’s method waspublished in 1965.The basic methods for solving nonlinear equations in one variable are discussed in almost every general textbook on numerical methods. More detailed treatment of the classicalmethods can be found in [129, 197, 256].
For zero finding using linear fractional interpolation, see [135]; more general rational functions for this purpose are discussed in [161].Definitive references on solving systems of nonlinear equations are [57, 196]. For a survey ofrecent developments, see [147]. An incisive overview of the theory and convergence analysisof secant updating methods appears in [56]. Homotopy, or continuation, methods are thesubject of [6]. The MINPACK software for nonlinear equations is documented in [182].Review Questions5.1 True or false: If an iterative method forsolving a nonlinear equation gains more thanone bit of accuracy per iteration, then it is saidto have a superlinear convergence rate.nonlinear equations f (x) = o.5.2 True or false: For a given fixed level ofaccuracy, a superlinearly convergent iterativemethod always requires fewer iterations than alinearly convergent method to find a solutionto that level of accuracy.5.5 Suppose you are using an iterativemethod to solve a nonlinear equation f (x) = 0for a root that is ill-conditioned, and you needto choose a convergence test.
Would it be better to terminate the iteration when you find aniterate xk for which |f (xk )| is small, or when|xk − xk−1 | is small? Why?5.3 True or false: A small residual kf (x)kguarantees an accurate solution of a system of5.4 True or false: Newton’s method is an example of a fixed-point iteration scheme.174CHAPTER 5. NONLINEAR EQUATIONS5.6 (a) What is the definition of the convergence rate r of an iterative method?(b) Is it possible to have a cubically convergent method (r = 3) for finding a zero of afunction?(c) If not, why, and if so, how might such ascheme be derived?5.14 Which of the following behaviors arepossible in using Newton’s method for solvinga nonlinear equation?5.7 If the errors at successive iterations ofan iterative method are as follows, how wouldyou characterize the convergence rate?(a) 10−2 , 10−4 , 10−8 , 10−16 , .
. .(b) 10−2 , 10−4 , 10−6 , 10−8 , . . .5.15 What is the convergence rate for Newton’s method for finding the root x = 2 of eachof the following equations?5.8 What condition ensures that the bisection method will find a zero of a continuousnonlinear function f in the interval [a, b]?5.16 (a) What is meant by a fixed point of afunction g(x)?5.9 (a) If the bisection method for findinga zero of a function f : R → R starts with aninitial bracket of length 1, what is the lengthof the interval containing the root after six iterations?(b) Do you need to know the particular function f to answer the question in part a?(c) If we assume that it is started with abracket for the solution in which there is a signchange, is the convergence rate of the bisection method dependent on whether the solution sought is a simple root or a multiple root?Why?5.10 Suppose you are using the bisectionmethod to find a zero of a nonlinear function, starting with an initial bracketing interval [a, b].
Give a general expression for thenumber of iterations that will be required toachieve an error tolerance of tol for the lengthof the final bracketing interval.5.11 What is meant by a quadratic convergence rate for an iterative method?5.12 If an iterative method squares the errorevery two iterations, what is its convergencerate r?5.13 (a) What does it mean for a root of anequation to be a multiple root?(b) What is the effect of a multiple root on theconvergence rate of the bisection method?(c) What is the effect of a multiple root on theconvergence rate of Newton’s method?(a) It may converge linearly.(b) It may converge quadratically.(c) It may not converge at all.(a) f (x) = (x − 1)(x − 2)2 = 0(b) f (x) = (x − 1)2 (x − 2) = 0(b) Given a nonlinear equation f (x) = 0, howcan you determine an equivalent fixed-pointproblem, that is, a function g(x) such that afixed point x of g is a solution to the nonlinearequation f (x) = 0?(c) Specifically, what function g(x) resultsfrom this approach?5.17 In using the secant method for solving aone-dimensional nonlinear equation,(a) How many starting guesses for the solutionare required?(b) How many new function evaluations arerequired per iteration?5.18 Let g: R → R be a smooth function having a fixed point x∗ .(a) What condition determines whether the iteration scheme xk+1 = g(xk ) is locally convergent to x∗ ?(b) What is the convergence rate?(c) What additional condition implies that theconvergence rate is quadratic?(d ) Is Newton’s method for finding a zero of asmooth function f : R → R an example of sucha fixed-point iteration scheme? If so, what isthe function g in this case? If not, then explainwhy not.5.19 In bracketing a zero of a nonlinear function, one needs to determine if two functionvalues, say f (a) and f (b), differ in sign.
Is thefollowing a good way to test for this condition:if (f (a) ∗ f (b) < 0) . . .? Why?REVIEW QUESTIONS5.20 Let g: R → R be a smooth function, andlet x∗ be a point such that g(x∗ ) = x∗ .(a) State a general condition under whichthe iteration scheme xk+1 = g(xk ) convergesquadratically to x∗ , assuming that the starting guess x0 is close enough to x∗ .(b) Use this condition to prove that Newton’smethod is locally quadratically convergent to asimple zero x∗ of a smooth function f : R → R.5.21 List one advantage and one disadvantageof the secant method compared with the bisection method for finding a simple zero of a singlenonlinear equation.5.22 List one advantage and one disadvantageof the secant method compared with Newton’smethod for solving a nonlinear equation in onedimension.5.23 The secant method for solving a onedimensional nonlinear equation uses linear interpolation of the given function at two points.Interpolation at more points by a higherdegree polynomial would increase the convergence rate of the iteration.(a) Give three reasons why such an approachmight not work well.(b) What alternative approach using higherdegree interpolation in this context avoidsthese difficulties?1755.27 In solving a nonlinear equation f (x) = 0,if you assume that the cost of evaluating thederivative f 0 (x) is about the same as the costof evaluating f (x), how does the cost of Newton’s method compare with the cost of the secant method per iteration?5.28 Suppose that you are using fixed-pointiteration based on the fixed-point problem x =g(x) to find a solution x∗ to a nonlinear equation f (x) = 0.
Which would be more favorablefor the convergence rate: a horizontal tangentof g at x∗ or a horizontal tangent of f at x∗ ?Why?5.29 Suggest a procedure for safeguarding thesecant method for solving a one-dimensionalnonlinear equation so that it will still convergeeven if started far from a root.5.30 For what type of function is linear fractional interpolation a particularly good choiceof zero finder?5.31 Each of the following methods for computing a root of a nonlinear equation hasthe same asymptotic convergence rate. Foreach method, specify a situation in which thatmethod is particularly appropriate.(a) Regular quadratic interpolation(b) Inverse quadratic interpolation(c) Linear fractional interpolation5.24 For solving a one-dimensional nonlinear equation, how many function or derivativeevaluations are required per iteration of eachof the following methods?(a) Newton’s method(b) Secant method5.32 State at least one method for finding allthe zeros of a polynomial, and discuss its advantages and disadvantages.5.25 Rank the following methods 1 through 3,from slowest convergence rate to fastest convergence rate, for finding a simple root of anonlinear equation in one dimension:(a) Bisection method(b) Newton’s method(c) Secant method5.34 For solving an n-dimensional nonlinearequation, how many scalar function evaluations are required per iteration of Newton’smethod?5.26 In solving a nonlinear equation in one dimension, how many bits of accuracy are gainedper iteration of(a) Bisection method?(b) Newton’s method?5.33 Does the bisection method generalize tofinding zeros of multidimensional functions?Why?5.35 Relative to Newton’s method, which ofthe following factors motivate secant updatingmethods for solving systems of nonlinear equations?(a) Lower cost per iteration(b) Faster convergence rate(c) Greater robustness far from solution(d ) Avoidance of computing derivatives176CHAPTER 5.
NONLINEAR EQUATIONS5.36 Give two reasons why secant updatingmethods for solving systems of nonlinear equa-tions are often more efficient than Newton’smethod despite converging more slowly.Exercises5.1 Consider the nonlinear equationf (x) = x2 − 2 = 0.(a) With x0 = 1 as a starting point, what isthe value of x1 if you use Newton’s method forsolving this problem?(b) With x0 = 1 and x1 = 2 as starting points,what is the value of x2 if you use the secantmethod for the same problem?5.2 Write out Newton’s iteration for solvingeach of the following nonlinear equations:(a) x3 − 2x − 5 = 0.(b) e−x = x.(c) x sin(x) = 1.5.3 Newton’s method is sometimes used toimplement the built-in square root function ona computer, with the initial guess supplied bya lookup table.(a) What is the Newton iteration for computing the square root of a positive number y (i.e.,for solving the equation f (x) = x2 − y = 0,given y)?(b) If we assume that the starting guess has anaccuracy of 4 bits, how many iterations wouldbe necessary to attain 24-bit accuracy? 53-bitaccuracy?5.4 On a computer with no functional unitfor floating-point division, one might insteaduse multiplication by the reciprocal of the divisor.
Apply Newton’s method to produce aniterative scheme for approximating the reciprocal of a number y > 0 (i.e., to solve the equation f (x) = (1/x) − y = 0, given y). Considering the intended application, your formulashould not contain any divisions!(b) When implemented in finite precisionfloating-point arithmetic, what advantages ordisadvantages does the formula given in part ahave compared with the formula for the secantmethod given in Section 5.2.4)?5.6 Suppose we wish to develop an iterativemethod to compute the square root of a givenpositive number y, i.e., to solve the nonlinearequation f (x) = x2 − y = 0 given the value ofy.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
