**Unformatted text preview:**

MATH2071: LAB 5: Norms, Errors and WhatnotIntro duction Exercise 1Vector Norms Exercise 2Matrix Norms Exercise 3Compatible Matrix Norms Exercise 4More on the Spectral Radius Exercise 5Typ es of Errors Exercise 6A matrix example Exercise 7Extra credit: the determinant Exercise 8Exercise 9Extra Credit1 IntroductionThe objects we work with in linear systems are vectors and matrices. In order to make statements aboutthe size of these objects, and the errors we make in solutions, we want to be able to describe the “sizes” ofvectors and matrices, which we do by using norms.We then need to consider whether we can bound the size of the product of a matrix and vector, giventhat we know the “size” of the two factors. In order for this to happen, we will need to use matrix andvector norms that are compatible. These kinds of bounds will become very important in error analysis.We will then consider the notions of forward error and backward error in a linear algebra computation.We will then look at one useful matrix example: a tridiagonal matrix with well-known eigenvalues andeigenvectors.This lab will take two sessions. You may find it convenient to print the pdf version of this lab ratherthan the web page itself.2 Vector NormsA vector norm assigns a size to a vector, in such a way that scalar multiples do what we expect, and thetriangle inequality is satisfied. There are four common vector norms in n dimensions:• The L1vector norm∥x∥1=n∑i=1|xi|• The L2(or “Euclidean”) vector norm∥x∥2=vuutn∑i=1|xi|2• The Lpvector norm∥x∥p=(n∑i=1|xi|p)1/p• The L∞vector norm∥x∥∞= maxi=1,...,n|xi|To compute the norm of a vector x in Matlab:1• ∥x∥1= norm(x,1);• ∥x∥2= norm(x,2)= norm(x);• ∥x∥p= norm(x,p);• ∥x∥∞= norm(x,inf)(Recall that inf is the Matlab name corresponding to ∞.)Exercise 1: For each of the following column vectors:x1 = [ 4; 6; 7 ]x2 = [ 7; 5; 6 ]x3 = [ 1; 5; 4 ]compute the vector norms, using the appropriate Matlab commands. Be sure your answers are reason-able.L1 L2 L Infinityx1 __________ __________ __________x2 __________ __________ __________x3 __________ __________ __________3 Matrix NormsA matrix norm assigns a size to a matrix, again, in such a way that scalar multiples do what we expect,and the triangle inequality is satisfied. However, what’s more important is that we want to be able to mixmatrix and vector norms in various computations. So we are going to be very interested in whether a matrixnorm is compatible with a particular vector norm, that is, when it is safe to say:∥Ax∥ ≤ ∥A∥ ∥x∥There are four common matrix norms and one “almost” norm:• The L1or “max column sum” matrix norm:∥A∥1= maxj=1,...,nn∑i=1|Ai,j|• The L2matrix norm:∥A∥2= maxj=1,...,n√λiwhere λiis a (necessarily real and non-negative) eigenvalue of AHA or∥A∥2= maxj=1,...,nµiwhere µiis a singular value of A;• The L∞or “max row sum” matrix norm:∥A∥∞= maxi=1,...,nn∑j=1|Ai,j|2• There is no Lpmatrix norm.• The “Frobenius” matrix norm:∥A∥fro=√∑i,j=1,...,n|Ai,j|2• The spectral radius (not a norm):ρ(A) = max |λi|(only defined for a square matrix), where λiis a (possibly complex) eigenvalue of A.To compute the norm of a matrix A in Matlab:• ∥A∥1= norm(A,1);• ∥A∥2= norm(A,2)=norm(A);• ∥A∥∞= norm(A,inf);• ∥A∥fro= norm(A,’fro’)• See below for computation of ρ(A) (the spectral radius of A)4 Compatible Matrix NormsA matrix can be identified with a linear operator, and the norm of a linear operator is usually defined in thefollowing way.∥A∥ = maxx=0∥Ax∥∥x∥(It would be more precise to use sup rather than max here but the surface of a sphere in finite-dimensionalspace is a compact set, so the supremum is attained, and the maximum is correct.) A matrix norm definedin this way is said to be “vector-bound” to the given vector norm.In order for a matrix norm to be consistent with the linear operator norm, you need to be able to saythe following:∥Ax∥ ≤ ∥A∥ ∥x∥ (1)but this expression is not necessarily true for an arbitrarily chosen pair of matrix and vector norms. Whenit is true, then the two are “compatible”.If a matrix norm is vector-bound to a particular vector norm, then the two norms are guaranteed tobe compatible. Thus, for any vector norm, there is always at least one matrix norm that we can use. Butthat vector-bound matrix norm is not always the only choice. In particular, the L2matrix norm is diﬃcult(time-consuming) to compute, but there is a simple alternative.Note that:• The L1, L2and L∞matrix norms can be shown to be vector-bound to the corresponding vector normsand hence are guaranteed to be compatible with them;• The Frobenius matrix norm is not vector-bound to the L2vector norm, but is compatible with it; theFrobenius norm is much faster to compute than the L2matrix norm (see Exercise 5 below).• The spectral radius is not really a norm and is not vector-bound to any vector norm, but it “almost”is. It is useful because we often want to think about the behavior of a matrix as being determined byits largest eigenvalue, and it often is. But there is no vector norm for which it is always true that∥Ax∥ ≤ ρ(A)∥x∥.There is a theorem, though, that states that, for any matrix A, and for any chosen value of ϵ > 0, anorm can be found so that ∥Ax∥ ≤ (ρ(A) + ϵ)∥x∥. Note that the norm depends both on ϵ and A.3Exercise 2: Consider each of the following column vectors:x1 = [ 4; 6; 7 ];x2 = [ 7; 5; 6 ];x3 = [ 1; 5; 4 ];and each of the following matricesA1 = [38 37 8053 49 4923 85 46];A2 = [77 89 786 34 1065 36 26];Check that the compatibility condition (??) holds for each case in the following table by computingthe ratiosrp,q(A, x) =∥Ax∥q∥A∥p∥x∥qand filling in the following table. The third column should contain the letter “S” if the compatibilitycondition is satisfied and the letter “U” if it is unsatisfied.Suggestion: I recommend you write a script m-file for this exercise. If you do, please include it withyour summary.Matrix Vectornorm norm S/U r(A1,x1) r(A1,x2) r(A1,x3) r(A2,x1) r(A2,x2) r(A2,x3)(p) (q)1 1 ___ _________ __________ __________ __________ __________ __________1 2 ___ _________ __________ __________ __________ __________ __________1 inf ___ _________ __________ __________ __________ __________ __________2 1 ___ _________ __________ __________

View Full Document