Notes on the solutions to HW3:
-----------------------------

A. Problem 1(c).  The convergence of this "secant" variation on
bisection will be superlinear [as suggested in the solutions] if the
derivative of f(x) near the root is bounded away from zero.  However if
the derivative goes to zero near the root [e.g., finding the root of
f(x) = x^3] then the convergence can be very much slower than linear.
For people who thought about this possibility, a positive analytic 
answer to 1(c) was more difficult to come by.  [Thanks to Jeff L. for 
pointing this out!]

B. Problem 3(d).  One of the fascinating things about iterative
minimization using the iterates

      xnew = xold - u * M * grad f(xold)

is how insensitive the method is to "minor" programming errors.  As long
as the error preserves positive-definiteness of M, you will be working
toward a minimum.   In problem 3(d) where M is the inverse hessian, if
you do all the calculations right you will find that u=1 and the
algorithm converges in one step (because f(x) itself is quadratic, so
the quadratic approximation of newton's method is *exact* for f).
However, if you only mess up the Hessian a little bit (as some people
did), so that your (incorrect) H^{-1} is still positive definite, you 
will still find the root in several iterations, and probably with less 
zigzagging than with the pure gradient method.  That is only a nuisance
in this small problem, but it means that programming errors (or errors
in analytic calculation of the Hessian) can be very difficult to catch
in big complicated problems: if the error preserves positive-
definiteness everything will seem to be working fine, and you may only
catch much later when you try to use the same code to minimize a new
function g(x) for which the erroneous inverse hessian is no longer
positive-definite.

-BJ