MA/CS/EGR 537: Assignment 6

This is due Thursday, November 6 in class. You may use anything from your midterm that you want to copy (xeroxing is just fine). Please be brief.

Suppose we want to solve the nonlinear system of equations

where x,0 are in RN and F: RN -> RN. Newton's method is where J(x) is the Jacobian of F(x) and x0 is sufficiently close to a solution for convergence. Another method for solving (1) is starting from y0=x0. Under appropriate conditions, (2) converges quadratically and (3) converges linearly.

(a) Suppose (2) converges in C2 steps and (3) converges in C3 steps. Assume that

where the superscripts in the error terms refer to the method. Write down what happens to the error in (2) for iterations 2, 3, and 4 in terms of the error after the first iteration. Write down what happens to the error in (3) for iterations 2-9 in terms of the error after the first iteration. Now prove that C3 is approximately 2C2.

(b) Both (2) and (3) can be computed efficiently each iteration. If the cost of computing

Write down what both (2) and (3) do on the first iteration (which is the same). Write down what both (2) and (3) do on the second iteration (which are now different from each other). Be brief.

What is the cost of (2) each iteration (which is the same as the cost of (3) only in its first iteration)? After the first iteration, (3) costs less per iteration than (2); what is the cost of (3) in this case?

(c) Based on (a) and (b), is (2) or (3) computationally more efficient when N is small? large? Each of these cases has 2 cases: when C2 is either small or large. Investigate all 4 cases and determine whether (2) or (3) is more efficient.

Hint: The first iteration costs the same for both (2) and (3) and can be ignored (you get the same x1 and y1, too). How many steps does (3) have to take before its lower cost is as great as the the cost of (3) (using O(N) notation makes this easier to determine)?

Cheers,
Craig C. Douglas