MATH2071: LAB #2: Norms, Errors and Condition NumbersIntroduction Exercise 1Vector Norms Exercise 2Matrix Norms Exercise 3Compatible Matrix Norms Exercise 4More on the Spectral Radius Exercise 5Types of Errors Exercise 6Condition Numbers Exercise 71 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.From the definitions of norms and errors, we can define the condition number of a matrix, which will giveus an objective way of measuring how “bad” a matrix is, and how many digits of accuracy we can expectwhen solving a particular linear system.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 three common vector norms in n dimensions:• The L1vector normkxk1=nXi=1|xi|• The L2(or “Euclidean”) vector normkxk2=vuutnXi=1x2i• The L∞vector normkxk∞= maxi=1,...,n|xi|To compute the norm of a vector x in Matlab:• kxk1= norm(x,1);• kxk2= norm(x,2)= norm(x);• kxk∞= norm(x,inf)(Recall that inf is the Matlab symbol corresponding to ∞.)1Exercise 1: For each of the following vectors:x1 = [ 1; 2; 3 ]x2 = [ 1; 0; 0 ]x3 = [ 1; 1; 1 ]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:kAxk ≤ kAk kxkThere are five common matrix norms:• The L1or “max column sum” matrix norm:kAk1= maxj=1,...,nnXi=1|Ai,j|• The L2matrix norm:kAk2= maxj=1,...,npλiwhere λiis a (necessarily real) eigenvalue of A>A orkAk2= maxj=1,...,nµiwhere µiis a singular value of A;• The L∞or “max row sum” matrix norm:kAk∞= maxi=1,...,nnXj=1|Ai,j|• The “Frobenius” matrix norm:kAkF=sXi,j=1,...,n|Ai,j|2• The “spectral” matrix norm;kAkspec= maxi=1,...,n|λi|(only defined for a square matrix), where λiis a (possibly complex) eigenvalue of A.2To compute the norm of a matrix A in Matlab:• kAk1= norm(A,1);• kAk2= norm(A,2)=norm(A);• kAk∞= norm(A,inf);• kAkF= norm(A,’fro’)• kAkspec= (see below)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.kAk = maxx6=0kAxkkxk(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:kAxk ≤ kAk kxk (1)but this expression is not true for an arbitrary chosen pair of matrix and vector norms. If it is true, thenthe 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 difficult(expensive) 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 easier to compute than the L2matrix norm.• The spectral matrix norm is not vector-bound to any vector norm, but it “almost” is. This norm isuseful because we often want to think about the behavior of a matrix as being determined by its largesteigenvalue, and it often is. But there is no vector norm for which it is always true thatkAxk ≤ kAkspeckxkExercise 2: Consider each of the following column vectors:x1 = [ 1, 2, 3 ]’x2 = [ 1, 0, 0 ]’x3 = [ 1, 1, 1 ]’For the same matrix A you used above:3A=[ 4 1 10 -2 20 5 -4 ]verify that the compatibility condition holds by comparing the values of kAk that you computed inthe previous exercise with the ratios of kAxk/kxk. The final column refers to satisfaction of thecompatibility relationship (1).Matrix Vector norm(A*x1) norm(A*x2) norm(A*x3)norm(A) ---------- ---------- ---------- OK?norm norm norm(x1) norm(x2) norm(x3)1 1 _________ __________ __________ __________ ___2 2 _________ __________ __________ __________ ___’fro’ 2 _________ __________ __________ __________ ___inf inf _________ __________ __________ __________ ___5 More on the Spectral RadiusIn the above text there is a statement that the spectral radius is not vector-bound with any norm, but thatit “almost” is. In this section we will see by example what this means.In the first place, let’s try to see why it isn’t vector-bound to the L2norm. Consider the following false“proof ”. Given a matrix A, for any vector x, break it into a sum of eigenvectors of A asx =Xxieiwhere eiare the eigenvectors of A, normalized to unit length. Then, for λithe eigenvalues of A,kAxk22= kXλixieik22≤ maxi|λi|2X|xi|2≤ kAk2speckxk2and taking square roots completes the “false proof.”Why is this “proof” false? The error is in the statement that all vectors can be expanded as sumsof