Numerical Analysis Lab, Section 3.5

M467 Lab, Section 3.5 (Feb 4) Before working with Matlab: 1. A “norm” is a special function from a vector space to the real numbers. Write the mathematical equivalents of the following: (a) The norm must be nonnegative. The norm is zero if and only if the vector is zero. (b) Something about the norm of a scalar multiple of a vector (c) The triangle inequality 2. The norms we will work with are the 1−, 2−, and ∞− norms. (a) Compute the 1−, 2− and ∞ norms for x = (1, 0, −1, 2)T . (b) Compute the distance between the vectors x and y under the 1−, 2− and ∞ norms: x = (−1, 0, 1, 0)T and y = (0, 1, 1, 1)T 3. The formal definition of the induced matrix norm: Given the vector space IRn , and given a norm k · k, and a matrix A, the matrix norm is defined to be: kAxk = max kAxk kAk = maxn x∈IR kxk=1 kxk This is too complicated to compute numerically. We will show later that: • kAk1 = Max abs col sum = max 1≤j≤n • kAk2 = n X |aij | i=1 q λmax , where λ’s are the eigenvalues of AT A. • kAk∞ = Max abs row sum = max 1≤i≤n n X |aij | j=1 4. Here is a matrix norm that is not induced by a vector norm. It is called the Frobenius1 norm, and it comes up when a matrix A is treated as a “vector” in IRmn : kAkF = sX X i a2ij j 5. In Matlab, matrix and vector norms are called by the same command: norm(x,p); %p-norm of the vector x (p>=1) norm(A,1); norm(A,2); norm(A, inf); norm(A,’fro’); 1 %Matrix norms Ferdinand Georg Frobenius was a German mathematician in the last half of the 1800’s. He was “occasionally choleric, quarrelsome, and given to invectives”, but they say that of a lot of the German mathematicians of that time. (http://www-groups.dcs.st-and.ac.uk/∼history/Mathematicians/Frobenius.html) Lab Questions: 1. (Problem 6, p. 45) A parachutist jumps from a plane and the distance of his drop is measured. Suppose that the distance of descent s as a function of time t can be modeled by: s = at + bt2 e−0.1t Find values of a, b that are reasonable given the data below: t 5 10 15 20 25 30 s 30 83 126 157 169 190 Plot the resulting model over time, showing the original data points as well. 2. Matlab uses the following: kAkF =sqrt(sum(diag(X’*X))) Where diag(A) returns a vector with the diagonal elements of A, sum(x) sums the elements of a vector, and sqrt is the square root. Show that this does give a valid computation of the Frobenius norm. You might start with a 3 × 3 matrix. 3. Use Maple to plot the set of points in IR2 where k(x, y)T kp = 1, for p = 1, 2, 10, 100. Here’s how to plot kxk1 = 1 and kxk2 = 1: with(plots): d1 := abs(x)+abs(y) = 1; d2:=(x^2+y^2)^(1/2)=1; A:=implicitplot(d1,x=-1.5..1.5, y=-1.5..1.5,grid=[30,30]): B:=implicitplot(d2,x=-1.5..1.5, y=-1.5..1.5,grid=[30,30],color=black): display({A,B}); Notice how the sets of points are nested, and as p → ∞, the limit seems to be kxk∞ . 4. In Maple, construct a graph of the function kAxkp , where A = x ∈ IR → kxkp 2 " −0.54 −1 −2 3 # in the unit square. Estimate kAk1 , kAk2 , and kAk100 from your graphs, and compare with the actual values (use kAk∞ for kAk100 ). 5. What does it mean to say that a matrix is close to being singular? 6. The condition number of a matrix A is defined to be: cond(A) = kAk kA−1 k in Matlab: cond(A, p) It is said that, in general, matrices with large condition numbers should be avoided (that is, large condition numbers can lead to numerical errors in solving the associated matrix equation). In using the induced p−norms, the condition number will always be greater than 1. So what matrices have the “ideal” condition number? It turns out that orthogonal2 matrices have the perfect condition number. Verify the statement above in Matlab for a few random orthogonal matrices, and for various dimensions. You can get a “random” orthogonal matrix in the following way: A=randn(3,3); [Q,S,V]=svd(A); %Q is an orthogonal matrix- We won’t use S, V Since the determinant of an orthogonal matrix is 1, we might be led to think that the condition number is related to the determinant. Unfortunately, it isn’t. Try the following: (a) Let the matrix Bn be an n × n matrix defined as having all 10 s along its diagonal, zeros below the diagonal, and −1’s above the diagonal. • Have Matlab compute the inverse of B, for n = 2, 3, 4. • From this, what will kBk∞ be? What will kB −1 k∞ be? • What is the determinant of B? Purpose of this question: The determinant can be small, but the condition number can grow arbitrarily large. (b) Define Dn = diag(10−1 , 10−1 , . . . , 10−1 ) • What is the determinant of Dn ? • What will the condition number of Dn be under the 1, 2 or ∞ norms? Purpose of this question: The determinant of the matrix can go to zero (singular), and still have a good condition number. So if the condition number is not a measure of “how invertible” a matrix is, what is it a measure of? The condition number is like a derivative in the sense that it tells us how stable our results are. That is, if we have the equation Ax = b, and b is changed very slightly, how much change is there in our solution? If the condition number is large, there may be a substantial change in the solution. 2 A matrix that is orthogonal is square with orthonormal columns