### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# AMATH352 Final Study Guide AMATH 352

UW

GPA 3.72

### View Full Document

## About this Document

## 152

## 3

## Popular in APPLIED LINEAR ALEGRA AND NUMERICAL ANALYSIS

## Popular in Applied Mathematics

This 16 page Study Guide was uploaded by Jeremy Dao on Monday March 7, 2016. The Study Guide belongs to AMATH 352 at University of Washington taught by Aleksandr Y. Aravkin in Winter 2016. Since its upload, it has received 152 views. For similar materials see APPLIED LINEAR ALEGRA AND NUMERICAL ANALYSIS in Applied Mathematics at University of Washington.

## Popular in Applied Mathematics

## Reviews for AMATH352 Final Study Guide

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 03/07/16

AMATH 352 Final Review Practice problems and concept list. Important vocabulary/concepts from the ﬁrst half of the course (1) Vocabulary (a) Linear combination ▯ A Linear Combination of vectors v1;v2;v3;:::;vnin V is any vector w such that w = ▯ v + ▯ v + ▯▯▯ + ▯ v , where ▯ ;▯ ;:::;▯ in R (any 1 1 2 2 n n 1 2 n real number). ▯ ▯ically,▯ ▯is a sum▯ ▯ com▯ ▯ationof vectors in V . 1 2 1 2 ▯ Example: v 1 ;v2= , then 6 ▯2 is a linear combination 3 5 3 5 of 1 ;2 . ▯ Note that not all vectors in V need to be used, i.e some ▯’s can be equal to zero. ▯ Note that if we take ▯ = ▯ = ▯▯▯ = ▯ = 0, we will get 1 2 n 0v1+ 0v 2 ▯▯▯ + 0vn= 0 for ANY v1;v2;:::;vn (b) Linear dependence ▯ v1;v2;:::;vnare calledlinearly dependent if there exists any linear combination besides all 0’s to make 1 1 + ▯2 2+ ▯▯▯ + ▯n n= 0, meaning ▯ 1 ▯ =2▯▯▯ = ▯ = n cannot be the only linear combination that makes the▯ ▯ove sta▯eme▯t true. ▯ ▯ ▯ ▯ ▯ ▯ 1 ▯1 1 ▯1 0 ▯ Example: v 1 ;v2= , then 11 + 1v2= + = . 2 ▯2 2 ▯2 0 In this case,1▯ = 2 = 0. Thus, v1;v2are linearly dependent. ▯ Note that this implies that one vector is a copy or some scalar multiple of another. In the case above,2v = ▯1 , so the1v and2v were not unique. ▯ If 2 or more vectors in a set are linearly dependent, then the whole set is linearly dependent as well (c) Linear independence ▯ v1;v2;:::;vnare calledlinearly independent if they are not dependent, or precisely the only linear combination such that ▯1 1+ ▯ 2 2 ▯▯▯ ▯ ▯ n n ▯ ▯s ▯ =1▯ = 2▯▯ = ▯ = n 1 1 ▯ Example: v 1 ;v2= ▯ ▯ ▯ ▯ 2▯ ▯ ▯ 0 ▯ ▯ ▯ 1 ▯1 0 ▯ ▯ ▯ +▯ = ! + 2▯ = 0 ! ▯ = 0;▯+▯ = 0 ! ▯ = 0 2 ▯2 0 2▯ 0 Thus only ▯ = ▯ = 0 works and v 1v2are linearly independent. ▯ We can also look at the linear dependence of functions. Ex. are ;ex independent? We want ▯e ▯x +▯e = 0 for all x. So we can simply plug in some points to get equations and solve for ▯ and ▯. 1 2 (x = 1) ▯ + ▯ = 0 ▯ = 0 (x = 1)▯e▯1 + ▯e = 0 ! ▯ + ▯e = 0 ▯ = 0 ▯x x Since ▯ = ▯ = 0;e and e are linearly independent functions. ▯ Theorem: If functions f (1);f (2);:::;f (n) are linearly independent, 0 0 0 then so are their derivative1 f (x2;f (x);::n;f (x). So to solve the example we can also take the derivative: ▯▯e ▯x + ▯e = 0. Combining the two equations we obtain 2▯e = 0 ! ▯ = 0. Thus ▯ = 0 as well and the two functions are linearly independent. (d) Subspace (of a linear space) ▯ V is a subspace of W is V is a subset of W (V is in W) and V is a linear space. ▯ V is a linear space if it satisﬁes the follow 2 properties: (i) Closure under addition: If1v 2v are in V , the1 v +2v is also in V . (ii) Closure under scalar multiplication: If v is in V , then ▯v is also 1 1 in V for any real ▯ ▯ These two properties imply some simpler ones that are useful for easily showing that a space is not a linear space. For example, notice that if for closure under scalar multiplication we let ▯ = 0, we get the zero vector. Thus the zero vector MUST be in every linear space. This is a good ﬁrst check when determining if a space is a linear space or not. ▯ Important Note: Every subspace of a linear space is itself a linear space ▯ Functions from R ! R form a linear space (e) Span (of a set of vectors) ▯ The span of vectors v 1v 2:::;v n is the set of all linear combinations ▯1 1+ ▯ 2 2 ▯▯▯ + ▯ vn nr any ▯ ;▯1;:2:;▯ 2 n ▯ In English, basically the span is every possible combination of the vectors. ▯ Note that the span of any vector(s) in R is a subspace of Rn (f) Basis (of a subspace) ▯ A basis B = fv ;1::;v gkfor a subspace S is a minimal set of vectors v1;:::;vkso that S = span{v 1:::;v k. ▯ "Minimal" means v ;1::;v ake linearly independent . 8 2 3 2 3 2 3 9 2 3 2 3 < 1 2 0 = 1 0 ▯ Example, let S = span 415 ; 524 ; 0 , then415 ; 50 form a basis : ; 0 0 1 0 1 2 3 2 3 1 2 4 5 4 5 for S because they are linearly independent. Notice that 1 and 2 0 0 were multiples of each other and were thus linearly dependent, or not "minimal". So the original set was not a basis. (g) Norms 3 ▯ A norm is an abstract notion of a certain kind of distance. n ▯ kxk is a function from R ! R and is a norm when: (i) kxk ▯ 0 for all x 2 R (ii) kxk = 0 if and only if x = 0 (iii) k▯xk = j▯jkxk. If we scale x by ▯, the norm is also scaled by ▯. Notice that we take the absolute value of ▯ because the norm(length) is independent of direction. n (iv) kx+yk ▯ kxk+kyk for all x;y 2 R called the "triangle inequality". ▯ The 1;2;3;:::;1 norms (called the p-norms) are given by the equation P 1 kxkp:= ( n jxij ) . i=1 P n ▯ For p = 1 we get the 1-norm, which is just kxk1= i=1 jxij, the sum of the absolute value of all the elements of x. ▯ For p = 2 we get the 2-norm, which is our traditionally understanding of the norm in that is gives the Euclidean distance (or the magnitude of p 2 2 2 the vector). kxk2= x1+ x 2 ▯▯▯ + x .nNote that if the subscript is omitted from the norm (kxk) this is generally taken to be the 2-norm. We canpalso deﬁne the 2- norm in terms of the inner dot product: kxk = x ▯ x ▯ The 1-norm is deﬁned as kxk 1 = max(jx 1;:::;jx n) the maximum of the absolute value of the elements. ▯ Note that these are NOT the only norms. Any function that satisﬁes the above 4 properties is considered a norm. Look at the review sheet problems for some examples of this. ▯ There is also the notion of norm balls : The p-norm ball B p fx : kxk ▯ pg is the surface which contains all vectors whose p-norm is less than 1. So the 2-norm ball in R is a circle of radius 1 3 (sphere of radius 1 if in R ). Here are some pictorial depictions of the p-norm balls: (h) Linear functions ▯ A linear function should really be considered as a Linear Map. A linear map f from V to W satisﬁes f(▯v +▯v ) = ▯f(v )+▯f(v ) (the linear 1 2 1 2 4 map has linearity, meaning that it is closed under addition and scalar multiplication. n m ▯ Consider the maps from R to R . We can deﬁne them as an n ▯ m matrix A, where A 2 R▯n , as a rectangular array from real numbers. 2 3 a11 a12 ▯▯▯ a1n 6 ... .. 7 A = 6 a21 a2n7 aij is the entry in the row and the jh 4 . ... .. . 5 . . am1 ▯▯▯ ▯▯▯ amn column of A. ▯ We can use the idea of linear maps to deﬁne matrix-ve2to3 multiplica- 2 3 v1 1 2 1 1 6v27 tion in 2 ways. For example, let A = 2 1 3 0 5 ;v = 4 5 with 1 0 0 1 v3 v4 m▯n 4 A 2 R ;v 2 R We can write Av to mean: 2 3 2 3 v1 2 3 1 2 1 1 6v 7 r1▯ v (i)4 2 1 3 0 5 6 27 = 4r2▯ v5, where i denotes the irow of A. 1 0 0 1 4v35 r ▯ v v4 3 This is expressing Av in terms of the dot product of the rows and v. 2 3 2 3 v 2 3 2 3 2 3 2 3 1 2 1 1 6 17 1 2 1 1 (ii) 2 1 3 0 5 6v27 = v 425 + v 4 1 + v 4 3 + v 405 4v35 1 2 3 4 1 0 0 1 v 1 0 0 1 4 = v1 1+ v2 2+ v3 3+ v 4 4 where i denotes the icolumn of A. This is expressing Av as a linear combination of columnsith weights given by entries of v. ▯ Any linear function F from R to Rcan be written as F(x) = Wx for some matrix W. m▯n n m ▯ Never forget to think of A 2 R as a map from R ! R . (i) Dimension ▯ The dimension of8a2 3 2 3 2 3 t9e numb8r2 3 2 3t9rs in any basis of S < 1 2 0 = < 1 0 = ▯ Thus if S = span 415 ; 2 ; 50 , and 415 ; 0 forms a basis : ; : ; 0 0 1 0 1 for S, then the dimension of S is 2. (j) Range (of a matrix) m▯n ▯ The range of a matrix A 2 R is the span of the columns of A. 5 ▯ To state this explicitly: For a matrix A, b is in its range if and only if there exists a x suchm▯nat Ax = b m ▯ Note that since A 2 R , the columns and thus the range is in R ▯ The range of A is a subspace of Rm ▯ The range of A is denoted range(A) (k) Rank (of a matrix) ▯ The rank of a matrix A is the dimension of range(A) ▯ The rank of A is denoted rank(A) ▯ The row rank of A is equal to the column rank of A (l) Nullspace (of a matrix) m▯n ▯ The nullspace of A 2 R is the set of vectors x satisfying Ax = 0. This set is denotes nullspace(A). n ▯ The nullspace of A is a subspace of R . ▯ Note: Since Ax = 0, by the row deﬁnition of matrix-vector multiplication (see Linear Functions above), x is orthogonal to the rows of A (since the dot product of the rows of A and x is 0). ▯ null(A) is the dimension of the nullspace of A ▯ Rank-Null Theorem: Let A 2 R m▯n , then: n (the number of columns) = rank(A) + null(A)) (m) Elementary vectors e 1:::;e nn R n n n ▯ The elementary vectors e1;:::;enin R are vectors in R with 1 in the ithspot and zeroes2 3erywhere2 3se. 1 0 6 7 6 7 6 7 6 7 ▯ For example, e = 6 7 ;e = 6 7 1 6 . 2 6.7 4 . 4.5 0 0 ▯ An important thing to notice is that the elementary vectors form a basis for Rn ▯ ▯ ▯ The matrix whose columns are the elementary vectors, m2aning e1 e2 3▯▯▯ en 1 0 ▯▯▯ 0 6 7 60 1 ▯▯▯ 07 is called theidentity matrix. This is denoted I n = 4 . . ... .5 . . . 0 0 ▯▯▯ 1 where there are n 1’s along the diagonal and zeroes everywhere else. – The main property of the identity matrix is that any square matrix A times the identity produces A (hence the name identity). Explic- itly, this means AI = I A = A (remember that A 2 R n▯n in order n n for the multiplication to make sense. See matrix multiplication be- low for more detail) (2) Concepts and skills 6 (a) Equivalence of linear functions from R toand matricies ▯ We can write a system of linear functions as a function of matrices. ▯ For example, take the system: 2x + y + z = 2 x ▯ y ▯ z = 1 x + 2y + 0z = 3 2 32 3 2 3 2 1 1 x 2 This is equivalent to: ▯1 ▯1 54 y = 415, or Ax = b, where 2 3 12 3 02 3 z 3 2 1 1 x 2 4 5 4 5 4 5 A = 1 ▯1 ▯1 ;x = y ;b = 1 1 2 0 z 3 (b) Solving linear systems of equations ▯ An easy way to solve linear systems is put them into matrix form then perform row operations. ▯ For example, take the system: 2x + y + z = 2 x ▯ y ▯ z = 1 x + 2y + 0z = 3 Putting this into an augmented matrix (only take the coeﬃcients and the solutions) we get: 2 3 2 1 1 2 4 1 ▯1 ▯1 1 5 which we can then perform row operations on to get 1 2 0 3 2he matrix to be3triangula2. 3 2 3 2 1 1 2 1 1 1 1 1 1 1 1 1 4 5 R1= 2 1 4 2 2 5 R2=R2▯R 1 4 2 2 5 1 ▯1 ▯1 1 ▯▯▯▯▯! 1 ▯1 ▯1 1 R =R ▯R! 0 1 1 0 1 2 0 3 1 2 0 3 3 3 1 0 3 ▯ 1 2 2 1 1 3 1 1 2 2 R =R ▯1:5R 1 2 2 1 x + 2 + z2= 1 ▯▯▯▯▯▯▯▯▯ ! 4 0 1 1 0 5 ! y + z = 0 1 0 0 ▯2 2 z = ▯:25 We can then just back-substitute to solve for x;y;z. ▯ This process is called Gaussian Elimination, or row reduction. ▯ When performing Gaussian elimination, there is the possibility that we would end up with free variables, which we can choose to be anything. For example, take the system: 7 2 3 x 1 x +2x = 3 1 ▯1 1 0 2x1+ x 2 x =30 ! 4 2 1 ▯1 0 5 ▯x 1 2x ▯22x = 3 ▯1 2 ▯2 0 2 3 1 ▯1 1 0 4 5 After performing Gaussian elimination we obtain: 0 3 ▯3 0 0 0 0 0 Notice that the last row is simply 0=0, so we only have 2 meaningful equations. We don’t have an equation for just x 3 (as we did in the triangular case above), so we will make x a3free variable. If we let x 3 1, we get 3x =23x ! 3 = 1 1nd x = x ▯1x = 2. 3 2 3 2 3 0 0 So a solution is4 1 , but also c415 for any c 2 R is a solution as well. 1 1 8 2 3 9 < 0 = Thus, the solution space is span 4 1 : 1 ; ▯ We can tell which variables are free and which are ﬁxed by looking at the columns of the matrix. In the above example, we can see that 1 and x 2re the ﬁrst non-zero elements in rows 1 and 2 respectively. Thus, x 1nd x a2e ﬁxed variables. Whatever is left (in this case x3) are free variables. ▯ Note: Row operations or even column operations do not aﬀect the row space, column space, or the dimensions of either of the matrix. ▯ A system of equations is consistent if it has at least one solution, i.e b is in the range of A. ▯ We can get a hint about the solutions of Ax = 0 by looking at the columns of A. – If rank(A) = n, then the columns of A are linearly independent, thus the only solution is x = 0. – If m < n, rank(A) ▯ m < n, so there must be at least one other non-zero solution. (c) Matrix multiplication ▯ Using our deﬁnitions of matrix-vector multiplication (see Linear Maps above) we can deﬁne matrix-matrix multiplication. ▯ Let A 2 R m▯n and B 2 R n▯k, then AB is: 2 3 2 . . . .3 2 . . . . 3 . . . . . . . . 4 5 6 7 6 7 A 4b1 b2 ▯▯▯ bn5 = 4Ab 1 Ab2 ▯▯▯ Ab n5 . . . . . . . . . . . . . . . . ▯ Note that not all matrices can be multiplied by each other! Matrix- matrix multiplication only makes sense if the inner dimensions of the matrices are equal. In the above example, A had dimensions m ▯ n 8 and B and dimensions n ▯ k. Notice that m ▯ n ! n ▯ k the inner dimensions (n) are equal. The solution will have the outer dimensions of the 2 matrices (m ▯ k) (d) Finding a basis for a subspace ▯ First ﬁnd a set of vectors that span the subspace, then put them into a matrix A. Row reduce the matrix, then take the ﬁrst columns containing the ﬁrst non-zero elements of each row. The corresponding columns in the original matrix A forms a b▯▯ ▯ ▯ ▯ ▯ ▯ ▯ ▯▯pace. 1 2 1 1 ▯ Example. Find a basis for S = spa2 ; 4 ; 3 ; 2 ▯ ▯ ▯ ▯ A = 1 2 1 1 ▯▯▯▯! 1 2 1 1 The ﬁrst and second columns 2 4 3 4 reduce 0 0 1 2 have the ﬁrst non-zero element of each row, thus the ﬁrst and second ▯▯ ▯ ▯ ▯▯ column of A form a basis for the subspace. A basis for ; is 2 3 ▯ Note that we can do this because row operations do not change the space or even the dimension. (e) Finding a basis for the range of a matrix ▯ Since the range of a matrix A is a subspace, we can follow the above procedure. ▯ Just row reduce A, take the columns containing that ﬁrst non-zero ele- ment of each row, and the corresponding columns in A form a basis for the range. (f) Finding a basis for the nullspace of a matrix ▯ Solve the equation Ax = 0 and examine the result. The number of free variables in the solution will correspond to the number of vectors in the basis. ▯ ▯xamp▯e: ▯o fr▯e variables 1 2 1 0 3 4 ! 0 1 Thus, the vectors are linearly independent, and only the zero vector is in the nullspace ▯ ▯xamp▯e: ▯ fre▯ variable ▯▯ ▯▯ 1 2 1 2 1 ! . Thus x1= ▯2x 2 so the nullspace = span . 1 2 0 0 ▯2 1 free variable means 1 vector in the span. ▯ 2xample:32 f2ee vari3bles 2 3 2 3 1 2 3 1 2 3 ▯2 ▯3 4 5 4 5 4 5 4 5 1 2 3 ! 0 0 0 , so 1 = ▯2x2▯ 3x3! 1 x2+ 0 x3; 1 2 3 0 0 0 0 1 2▯23 2 ▯3 3 so 4 15 ; 0 5 forms a basis. 2 free variables, 2 vectors in the basis. 0 1 9 Important vocabulary/concepts from second half (1) Formulating linear regression as a least squares problem ▯ Recall the least squares problem: min kAx ▯ bk 2 x 2 and that the solution is found by setting the gradient to be zero, which gives the following linear system to solve: A Ax = A b T ▯ Suppose we have some response y and some predictions x. Let i index the indi- viduals (in a study).iy is the observed response from an individual (e.g annual salary). For each individual, we also has some data: a years of education i;1 and ai;2height of the individual. Then the response y ian be predicted by yi= ▯ 0▯ a1 i;1+▯ 2 i;2for some constants ▯0;▯ 1▯ 2 Putting this into matrix form to represent all individuals(the observation vector y) we obtain: 2 3 2 3 ▯ 0 1 a11 a12 4 5 6 . . . 7 y = A ▯ 1 ;A = 4 . . . 5 ▯ 2 1 a a n1 n2 2 3 ▯ 0 ▯ We can estimate ▯ = 4▯ 15 by solving: ▯ 2 min 1ky ▯ A▯k 2 ▯ 2 So we solve A A▯ = A y for the ▯ (2) Formulating ridge regression as a least squares problem ▯ Ridge regression is linear regression with an extra regularization piece added on ▯ We look at the solution to: min 1kAx ▯ bk + ▯R(x) x 2 where ▯ is a constant and R(x) is the regularization function. ▯ We still solve this by setting the gradient to zero and solving the resulting system. Since the gradient is a linear function (the gradient of the sum is sum of the gradients) this leads to the system: A Ax + rR(x) = A b T – We choose diﬀerent regularization functions for diﬀerent purposes. For example, R(x) = kxk wi1l tell us who the most important predictors are. 10 (3) Formulating polynomial ﬁtting as a least squares problem ▯ Given a set of points, we can ﬁt a polynomial curve to those points using least squares. ▯ For example, to ﬁt the points (1 ;1 );(2 ;2 );(3 ;3 ) to a parabola, we want 2 to be able to represent each point in the form of: y = ax + bx + c for some constants a;b;c. We ﬁnd a;b;c through least squares. 2 2 3 2 2 32 3 y 1 ax +1bx + 1 y1 x1 x1 1 a y 2 ax + bx + 2 ! 4y25 = 4x2 x2 154 5b ! Y = Xa ▯ 2 2 y 3 ax +3bx + 3 y3 x3 x3 1 c So the least squares problem becomes: min kXa ▯ ▯ Y k ▯ 2 T T Solve the system X Xa ▯ = X Y (4) Matrices with orthogonal and orthonormal columns ▯ A matrix is orthogonal if its columns are orthonormal, meaning that each column is orthogonal to the others (dot product is zero) and is a unit vector (2-norm of each column is 1). 2 3 2 ▯2 1 ▯ Example: 14 1 2 2 5 3 2 1 ▯2 ▯ Properties of orthogonal matrices: If A is an orthogonal matrix, then: T T (a) AA = A A = I (b) A▯1 = A T (5) QR decomposition, and computing it via Gram-Schmidt ▯ The (reduced) QR decomposition decomposes a matrix A in two matrices QR (A = QR) where Q is an orthogonal matrix and and R is upper triangular. ▯ Note: The reduced QR assumes that A is of full rank ▯ If A is m ▯ n then Q is m ▯ n and R is n ▯ m ▯ Computing the QR decomposition via Gram-Schmidt T – Notice that if we know Q, we can ﬁnd R by R = Q A (Q is an orthogonal matrix, so its inverse is guaranteed to exist and Q= Q T 2 3 2 3 – Let A = 4a 1 a2 ▯▯▯ an5 ;Q = 4 q1 q2 ▯▯▯ qn5 (a) 1 = a1 (normalize to make kq1k = 1) k1 k (b) Want to make a o2thogonal to q . 1et p 2 = a 2 ha ;2 i2 .1Then q = p2 2 k2 k (c) Let 3 = a 3 ha 3q 1q 1 ha 3q 2q 2 then q3= p3 k3 k 11 (d) In general, p X▯1 qk= k , where pk= hak;q iqi kpkk i=1 (6) Orthogonal projections QQ T and I ▯ QQ T obtained from A = QR 2 ▯ P is a projector if P = P ▯ P is an orthogonal projector is P is a projector and P = P T ▯ QQ T is an orthogonal projector onto Range(A) T T T T T T ▯1 T – (QQ ) = (QQ )(QQ ) = QQ (Q = Q , so Q Q = I) ▯ I ▯ QQ T is an orthogonal projector onto Range(A ) T T T T T T T – (I ▯ QQ )(I ▯ QQ ) = I ▯ 2QQ + QQ QQ = I ▯ QQ – (I ▯ QQ ) = I ▯ (QQ ) = I ▯ QQ T ▯ Using orthogonal projectors in least squares: – Suppose we want to solve the least squares problem min kAx▯bk with 2 T the extra constraint that x must satisfy x V = 0 where V is a 1 ▯ n vector. ? – We want to build a projector onto V – The QR decomp. of V is V = qr = kV kkV k T We want I▯qq , which projects onto the range of V , so we use I▯ V V T kV k – Let P = (I ▯ V V2), then min xAx ▯ bk becomes: kV k 2 mynkAPy ▯ bk So we can get the solution by solving PA APy = PA b T (7) Diﬀerence between conditioning and stability ▯ Conditioning is a property of a problem of a function. Given "input" x and "output" y (f(x) = y), conditioning looks at how much does the y change if x is perturbed slightly. A problem is well-conditioned if the output doesn’t change very much. – The Absolute Condition Number is deﬁned as the number C(x) that sat- isﬁes jf(^) ▯ xj ▯ j^ ▯ xj (where x^ it the perturbed input). If f(x) is a diﬀerentiable function, then C(x) = jf (x)j. – The Relative Condition Number is deﬁned as the number ▯(x) that sat- isﬁes: ▯ ▯ ▯ ▯ ▯f(^) ▯ f(x) ▯ ▯^ ▯ x ▯ ▯ ▯ ▯ ▯(x) ▯ ▯ f(x) x ▯ ▯ ▯xf (x)▯ If f(x) is a diﬀerentiable function, then ▯(x) = ▯ f(x) ▯ ▯ ▯ Example: Conditioning of computing sin(x) at x = 4 12 (a) Absolute Condition Number: 0 f(x) = sin(x) ! f (x) = cos(x) jf (x)j = jcos(x)j ▯ 1 ) jsin(^) ▯ sin(x)j ▯ ^ ▯ xj ! C(x) = 1 Notice that in this case C(x) does not depend on x (b) Relative Condition Number: xf (x) xcos(x) = = xcot(x) f(x) sin(x) ▯ At x = 4 ! sin(x) = cos(x) ! cot(x) = 1 ▯ ▯ ▯ ▯ ▯sin^) ▯ sin(x)▯ ▯ ▯^ ▯ x▯ ▯ ▯ ) ▯ sin(x) ▯▯ 4 ▯ x ▯! ▯( )4= 4 (8) Counting basic arithmetic operations for diﬀerent functionalities ▯ We can count the number of operations precisely, or approximately, meaning we are only concerned about the "order". Big O notation only cares about the biggest step, or the piece that has the largest impact. ▯ Example: Inner product of x;y;2 R n hx;yi = x1 1+ x 2 2 ▯▯▯ + x n n There are n multiplications, and n ▯ 1 additions. Precise: 2n ▯ 1 operates Big O: O(n) (we ignore -1 and 2) m▯n n ▯ 2xample A 2 R32 3;x 22R , oper3tions to compute Ax r1 x1 hx1;r1i 6 r 76 x 7 6 hx ;r i7 6 2 76 27 = 6 2 2 7 4 . . . 54 .5 4 . 5 rm xn hxn;rmi There are m dot products Precise: m(2n ▯ 1) Big O: O(mn) (9) Determinant, and its properties ▯ The determinant is a property of a square matrix ▯ It is calculated recursively: Expand upon any row, take the ﬁrst element in that row and multiply it by the determinant of the matrix created by eliminating the row and column that that element is in. Do the same for each element in the chosen row and sum all the results up to get the determinant. ▯ This method is very long-winded and confusing. Since I don’t believe Prof. Arvarkin will ask us to do any determinant by hand that is bigger than 3 ▯ 3, here are some easy tricks for determinants of 2 ▯ 2 and 3 ▯ 3 13 ▯ 2 ▯ ▯▯deter▯▯nan▯: ▯ a c ▯a c▯ det b d = ▯b d▯ = ad ▯ bc (The downward diagonal minus the upward diagonal) ▯ ▯ ▯ 3 det▯rminant: ▯a b c▯ a b c a b ▯e f g▯! e f g e f = afj + bgh + cei ▯ hfc ▯ iga ▯ jeb ▯ ▯ h i j h i j h i Write the ﬁrst two columns on the right of the matrix, then sum the 3 downward diagonals and subtract the 3 upward diagonals. ▯ Properties of the determinant: (a) The determinant is the product of all the matrix’s eigenvalues. (b) If the determinant of A 2 Rn▯n is 0, then the following are true: (i) A has a non-trivial null space (ii) A is "singular" (meaning that its inverse does not exist) (iii) rank(A) ▯ n (10) Eigenvectors and eigenvalues n▯n ▯ For any square matrix A 2 R , a non-zero vector x is called an eigenvector if Ax = ▯x for some constant ▯, which is theeigenvalue associated with x. ▯ The eigenvalues are calculated by ﬁnding the roots of the "characteristic poly- nomial", which is the determinant of A ▯ ▯I ▯ The eigenvectors are then found by ﬁnding the nullspace of A ▯ ▯I for each ▯ (eigenvalue) ▯ ▯ 2 7 ▯ Example: Find the eigenvalues and eigenvectors of A = ▯1 ▯6 ▯ ▯ det(A ▯ ▯I) = ▯ ▯ ▯ ▯ 7 ▯= (2 ▯ ▯)(▯6 ▯ ▯) + 7 = ▯ + 4▯ ▯ 5 = ▯ ▯1 ▯6 ▯ ▯ ▯ (▯ + 5)(▯ ▯ 1) = 0 ) ▯ 1 ▯5;▯ = 2 ▯ 1 ▯5 : ▯ ▯ ▯ ▯ 7 7 0 0 0 0 (A + 5Ij0) = ! ▯1 ▯1 0 ▯ ▯ 1 1 0 (1) 1 x 1 ▯x 2 ▯ = ▯1 (Any vector that sati▯ﬁes x1= ▯x i2▯als▯ an eigenv▯ctor for ▯1= ▯5) 1 7 0 1 7 0 ▯ = 1 : (A ▯ 1Ij0) = ▯1 ▯7 0 ! 0 0 0 ▯ ▯ 7x = ▯x ▯(2)= ▯7 2 1 1 (Any vector that statisﬁes 7x = ▯x is also an eigenvector for ▯ = ▯5) 2 1 1▯ ▯ ▯ ▯ So the eigenvalues of A are -5 and 1 with corresponding eigenvectors ; ▯7 ▯1 1 respectively. 14 ▯ If x is an eigenvector of A with eigenvalue ▯, then cx is also an eigenvector with the same eigenvalue for c 2 R. So every eigenvalue has inﬁnitely many eigenvectors, which form the eigenspace of the eigenvalue. ▯▯ ▯▯ – In the above example,1▯ has eigenspace span1 and ▯2has eigenspace ▯1 ▯▯ ▯7 ▯▯ span 1 ▯ A is non-singular (its inverse exists) exactly when 0 is notvector. ▯ If A is a triangular matrix (upper or lower), then its eigenvalues are just the diagonal entries. (11) Geometric vs. algebraic multiplicity ▯ The algebraic multiplicity of an eigenvalue is the algebraic multiplicity of the corresponding root of the characteristic polynomial. The geometric mul- tiplicity is the dimension of the eigenspace of the eigenvector. 2 3 1 3 ▯3 2 ▯ A = 4 ▯3 7 ▯3 5 ! char. poly. = (4 ▯ ▯) (▯2 ▯ ▯) = 0 ▯6 6 ▯2 ) ▯ = 4;▯ = ▯2 1 2 ▯1has algebraic multi2 3city of 2, a2d ▯ has algebraic multiplicity of 1. 1 An eigenvector for ▯ is1 , so its geometric multiplicity is 1. However we can 2 2 2 3 2 3 1 1 ﬁnd two linearly independent eigenvectors for ▯ ; 0 5, so its eigenspace 1 8 2 3 2 39 0 ▯1 < 1 1 = 4 5 4 5 is spa: 1 ; 0 ; , and its geometric multiplicity is 2 0 ▯1 ▯ Fact: 0 < geometric multiplicity ▯ algebraic multiplicity ▯ Eigenvalues can be ▯omple▯ even if all entries ar▯ real▯ 0 ▯1 ▯▯ 1▯ – Example: A = 1 0 det(▯I ▯ A) = ▯1 ▯ ▯ 2 = ▯ + 1 = 0 ! ▯ = ▯i – Fact: If ▯ is a complex eigenvalue of A, thenmplex conjugate of ▯) is also an eigenvalue. Accordingly, if x is an eigenvector▯ is an x ▯ eigenvector for ▯ (12) Eigenvalue decomposition: A = V SV1, its use for solving ODEs ▯ If each eigenvalue of A has geometric multiplicity that is equal to its algebraic multiplicity, then A isiagonlizable", meaning we can do an eigenvalue decomposition of the form A = V SV1 ▯ The columns of V contain eigenvectors for each eigenvalue of A. S is a diagonal matrix with eigenvalues on the diagonal. 15 ▯ For matrices with eigenvalues that have algebraic multiplicity higher than 1, repeat the eigenvalue as many tim2s at its 3lgebr2ic mult3plicity. 1 1 1 1 0 0 – Using the example above: V =41 1 0 5;S = 4 0 2 0 5 2 0 ▯1 0 0 2 (13) Simple markov chain modeling (no cycles) ▯ A Markov Chain is a chain of states and possible probabilities to change states. Each Markov Chain has a probability matrix P that represents the probability of going from one state to another. ▯ Example (14) ’Steady state’ distribution as left eigenvector with eigenvalue 1 ▯ The steady state distribution of the Markov Chain (distribution of time spent in each state over a long period of time) is the left eigenvector of P that has eigenvalue 1. – The left eigenvalue is deﬁned as: x A = ▯x , where x is a column vector. – The left eigenvalues of A are the right eigenvalues of A . 1 ▯ Taking P to a high power (like P 000) will also give the steady state distribu- tion, just as a matrix of repeated values rather than a single vector. T (15) Singular value decomposm▯non A = U▯V ▯ For any matrix A 2 R , with rank k ▯ min(m;n) has a (reduced)gular Value Decomposition(SVD) A = U▯V T m▯k ▯ U 2 R has orthonormal columns ▯ ▯ 2 Rk▯k is diagonal with positive values on the diagonal (called the singular values) T n▯k ▯ V 2 R has orthonormal columns ▯ The diagonal entries of ▯ are the square roots of the eigenvalues of A A, since T A A is square symmetric, which guarantees positive real eigenvalues. 16 ▯ SVD gives a rank-revealing representation, and allows us to obtain a low-rank approximation. 2 32 32 T 3 ▯1 v1 4u u ▯▯▯56 ▯2 76 vT 7 1 2 4 . 54 . 5 .. . ▯ By convention, ▯1> ▯ 2 ▯ >3▯▯▯ ▯ A = ▯ 1 1 1 ▯ u 2 2 2▯▯ Taking n terms in the above equation gives a rank n approximation of A

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.