Assignment #2 Solution

Please read Lectures 2, 3, and 4 in the textbook Numerical Linear Algebra by Trefethen and Bau. Then do the following exercises.

P5. This question requires nothing but calculus as a prerequisite. It shows a major source of linear systems from applications.

    (a) Consider these three equations, chosen for visualizability: x2 + y2 + z2 = 4
x = cos( y)

    • = y2

Sketch each equation individually as a surface in R3. (Do this by hand or in MATLAB. Accuracy is not important. The goal is to have a clear mental image of a nonlinear system as a set of intersecting surfaces.) Considering where all three surfaces intersect, describe informally why there are two solutions, that is, two points (x; y; z) 2 R3 at which all three equations are satisfied. Explain why both solutions are inside the closed box 1 x 1; 2 y 2; 0 z 2.

    (b) Newton’s method for a system of nonlinear equations is an iterative, approxi-mate, and sometimes very fast, method for solving systems like the one above.
Let x = (x1; x2; x3) 2 R3. Suppose there are three scalar functions fi(x) forming a (column) vector function f(x) = (f1; f2; f3), and consider the system

f(x) = 0:

(It is easy to put the part (a) system in this form.) Let
@fi
Jij =


be the Jacobian matrix: J 2 R3 3. The Jacobian generally depends on location, i.e. J = J(x), and it generalizes the ordinary scalar derivative.

Newton’s method itself is

(1)
J(xn) s =  f(xn);
(2)
xn+1 = xn + s

where s = (s1; s2; s3) is the step and x0 is an initial iterate. Equation (1) is a system of linear equations which determines s, and then equation (2) moves to the next iterate.
Using x0 = (  1; 1; 1), write out equation (1) in the n = 0 case, for the problem in part

(a), as a concrete linear system of three equations for the three unknown components of the step s = (s1; s2; s3).
2

    (c) Implement Newton’s method in MATLAB to solve the part (a) nonlinear system.

Show your script and generate at least five iterations. Use x0 = ( 1; 1; 1) as an initial iterate to find one solution, and also find the other solution using a different initial iterate. Note that format long is appropriate here.

    (d) In calculus you likely learned Newton’s method as a memorized formula, xn+1 =
xn    f(xn)=f0(xn). Rewrite equations (1), (2) for R1 to derive this formula.

P6. It is likely that you have learned a recursive method for computing determinants called “expansion in (by) minors.” If you do not know it, please look it up.

    (a) Compute the following determinant by hand to demonstrate that you can apply expansion in minors:
    2 31
1  2  3
4
5
6
:
det @47
8
95A

    (b) For any matrix A 2 Cm m, count the exact number of multiplication operations needed to compute det(A) by expansion in minors. (Hint: How much more work is
the m    m case than the (m    1)    (m    1) case?)

    (c) We know that if det(A) = 0 exactly then A is not invertible. However, rounding error makes an exact zero value extremely unlikely. On the other hand, the magnitude of det(A) does not measure invertibility of A. For instance, give a formula for det(A) when A is diagonal, and give a formula for A 1 if it exists. Show by example that det(A) is often very large or very small even for well-conditioned diagonal matrices.

From the above exercise I propose these four generalities about determinants.

    1. Numerical determinants should not be used to measure invertibility of ma-trices. (Use the condition number instead.)

    2. Numerical determinants should not be computed by expansion in minors. (Use an LU decomposition instead; it is far more efficient.)

    3. Never use Cramer’s rule. (And don’t learn it if you don’t know it.)

    4. Determinants are needed for changing variables in integrals. Typically the size of the matrix is small and this is numerically safe (or even exact).

In summary, determinants are a low priority in numerical linear algebra.

P7. Write a MATLAB program which draws the unit balls shown in (3.2) on page 18 of Trefethen & Bau. That is, draw clean pictures of the unit balls of k k1, k k2, k k1, and k kp. Following the aesthetic advice on page 18, use p = 4 for the last one.

Exercise 2.1 in Lecture 2.

Exercise 2.3 in Lecture 2.