- Sketch and by making use of your basic
knowledge of trigonometric and exponential functions.
- 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).
- 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 ?
- 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
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?
- 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
firstname.lastname@example.org. (You may also refer to the introduction of netlib
in the linear algebra chapter.
You may want to search for a keyword such as
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