Description
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.
-
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.
-
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).
-
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.
-
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.
-
Compute the following determinant by hand to demonstrate that you can apply expansion in minors:
-
31
1 2 3
-
-
-
-
-
-
-
4
5
6
:
det @47
8
95A
-
-
-
-
-
-
-
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?)
-
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.
-
Numerical determinants should not be used to measure invertibility of ma-trices. (Use the condition number instead.)
-
Numerical determinants should not be computed by expansion in minors. (Use an LU decomposition instead; it is far more efficient.)
-
Never use Cramer’s rule. (And don’t learn it if you don’t know it.)
-
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.