Exercise 10: The minimization of a one-dimensional function by Newton's method.     continued...

(i)

Sketch and by making use of your basic knowledge of trigonometric and exponential functions.

(ii)

Write a program to implement Newton's method for root finding. Write it in a flexible way so that you can use it later for other problems. Choose your stopping criteria carefully. You should balance the desire to obtain as accurate a result as possible with the amount of computation involved. In other words, there is no point in continuing a loop when the answer can no longer be improved. What are reasonable evaluations of progress to use? Consider, for example, changes in the magnitudes of successive iterates x and the associated function values . Also consider the amount of progress realized (in terms of function value) in relation to the size of step taken. (Sketch a situation where this may be relevant).

(iii)

First find the largest root, i.e., the one furthest to the right on the x-axis. Experiment with different starting points. What can you say about the performance and accuracy of Newton's method? (Consider ). What convergence do you see in practice, in terms of digits of accuracy obtained in each step? Be sure to illustrate progress by listing , measures of error, and measures of progress between successive iterates for each step of the method. Print the results to as many digits as you think are relevant. What accuracy do you expect from Newton's method in terms of machine precision ?

(iv)

Now try to find a few of the next largest roots to the left. Select and experiment with different starting points by considering various regions on your function sketch. When convergence is satisfactory, is it as fast as you observed for the large root? Are there examples of points for which your method fails? Why? Can you suggest a class of strategies to improve the method in those cases? Implement the following modification: Newton's method with bisection safeguards. In this version, we will keep two points a and b for which f always has opposite signs (i.e, we will always bracket a root). Let if and b otherwise. The method then takes a Newton step, defined by the tangent to the curve through the point , if the Newton point lies in the interval and ; otherwise, a bisection step is taken. Make a sketch of this scheme so that you understand what it does. Compare performance now for finding several roots. Are there cases where the straightforward implementation of Newton's method failed but this version succeeds? Why? What can you say about performance?

(v)

Now that you understand some of the difficulties involved even in some very simple problems, you might appreciate available software tools better. Use a library package to minimize or find some roots of . You can use an appropriate routine from comprehensive libraries such as NAG or you might search for a minimizer in Netlib, a network of free numerical analysis software. To get started in Netlib, at the time of writing you can send the message ``send index'' to netlib@ornl.gov. (You may also refer to the introduction of netlib in the linear algebra chapter. You may want to search for a keyword such as Brent. You may also need to obtain other supporting software that may not be included in the file. Information on such requirements should be given with the code. Once you obtain a suitable code, describe briefly the algorithm, going back to the original cited literature if you must. Try some of the good and bad starting points you diagnosed earlier. What can you say about performance of the package?