Homework 3. Assigned: Thu Feb 8. Due: Tue Feb 20 at midnight.

  1. Show that the square root algorithm you implemented in Homework 1 is actually Newton's method: what is the function f(x) to which, when you apply Newton's method, you get the iteration that you implemented? First write down a function f(x) whose root x*, satisfying f(x*)=0, is the square root of 2, and figure out the Newton iteration for this function: do you get the same thing you implemented in homework 1? Show the details. More generally define such an f that works for computing the square root of any number, say a. Now recall the definition of quadratic convergence on p.55 of Ascher-Greif, and recall that in class we showed that the quadratic convergence constant M for Newton's method is f''(x*)/(2 f'(x*)). To answer the question: is the square root iteration always quadratically convergent no matter what a you apply it to, you need to find the value of M, and make sure it is finite -- in particular make sure f'(x*) is not 0: is this the case for all a? By the way, this method is used to implement the square root function in practice.

  2. Implement a MATLAB function findzero for finding a root of a continuous function f on an interval [a,b], with the following requirements: Test your program on lots of examples, for example constructing functions from combining basic math functions such as exp(x)+sin(x) or log(x)+cos(x). Graph the functions using plot so you have some idea what input values to use for a and b. Compare the results you get with findzero to the built-in function fzero, but bear in mind that if f has more than one root in [a,b] the two routines may return different answers.

    Note: the reason we care about iters is that in real applications, the evaluation of f might take a long time.

Email your m-file implenting findzero as an attachment directly to the grader, zz299@nyu.edu, with a cc to me. Your grade will depend on how completely findzero satisfies the requirements, so be sure you test it thoroughly: the grader will test it on a variety of input. Answer question 1 in plain text in the body of the email or, if you prefer, in a separate attachment.

Reading: Chapters 3-4 of Ascher-Greif (skip Section 3.2).