Exam 2 Cheatsheet PDF

Preview

Summary

Cheatsheet containing all material from the second-half of the course, up to the second midterm. Covers Orthogonality, Graham-Schmidt Process, QR and Cholesky factorizations, Orthogonal projection and Least Squares, Linear & Polynomial Regression, Complex Numbers and Hermitian Inner Products, Fourie...

Description

Math 545 Cheatsheet (Exam 2)

(Equivalence) Suppose k · k and k · k′ are norms in a vector space V . We say they are equivalent if there exist positive constants A, B ∈ R such that

u 1 = v1 Last Updated November 15, 2018 u 2 = v2 −

B(v2 , u1 ) u1 B(u1 , u1 )

′

Bkv k ≤ kv k ≤ Akv k

B(v3 , u2 ) B(v3 , u1 ) u1 − u 3 = v3 − u2 B(u1 , u1 ) B(u2 , u2 )

Orthogonality

. . . Orthogonal

Given a set of vectors S = {v1 , ..., vn } ∈ V , S is said to be an orthogonal set if for every vi , vj ∈ S, B(vi , vj ) = 0 for i 6= j and B(vi , vj ) > 0 for i = j.

Given an orthonormal basis {w1 , ..., wn } of V with an inner product B, we can write any vector v ∈ V as v = B (v, w1 )w1 + B (v, w2 )w2 + · · · + B (v, wn )wn

u ˆ = projV (u) =

We can transform this into an orthonormal basis by normalizing each vector in our orthogonal basis:

An orthogonal set of vectors is called orthonormal if each vector has length 1. An orthogonal/orthonormal basis of a subspace is a basis that consists of orthogonal/orthonormal vectors

X B(vn , ui ) B(ui , ui ) i=1



u1 un ,..., kun k ku1 k



A matrix Q is said to be orthogonal if and only if it satisfies any of the following: (1) QT Q = QQT = I

Let U = Pn = span{L0 , . . . , L n } be the subspace spanned by the first n + 1 monic Legendre polynomials of degree ≤ n. Then the orthogonal projection of any function f onto U is determined by

Symmetric

A symmetric n × n matrix S is said to be positive definite if for all v ∈ Rn

B(v1 , v2 )

B (vn , v2 )

...

...

B (v1 , vn )

B (vn , vn )

   

Given any vectors u, v ∈ V , we can compute the inner product as B(u, v) = uT Sv Graham-Schmidt (Theorem) Let (V, B) be an inner product space of dimension n, with {v1 , ..., vn } a basis of V . Then there exists an orthonormal basis {w1 , ..., wn } such that span{v1 , ..., vk } = span{w1 , ..., wk } for all k = 1, ..., n. (Graham-Schmidt Process ) Let (V, B) be an inner product space and let {v1 , ..., vn } a basis of V . Then we can find an orthogonal basis {u1 , ..., un } of V using the following process:

B(Lj , Lj )

Given an m × n matrix A with m ≥ n and rank(A) = n, we can find a unique vector v ˆ ∈ Col(A) such that for any v ∈ Rm , kv − v ˆk is minimized (Least Squares Solution)

Any symmetric positive-definite matrix S may be written as S = R T R where R is upper-triangular with positive diagonal entries

For v ∈ / Col(A), the best solution x ˆ to Ax = v is

After completing the Graham-Schmidt process, Q is the orthogonal matrix containing the columns of an orthonormal basis and R is an upper-triangular matrix containing the coefficients of each of the orthonormal basis vectors that sum to get each column of A

Lj

Least Squares

Cholesky Factorization

(b) kuk = kQuk (Q preserves length)

B(v1 , v1 ) . . . B (vn , v1 )

n X B(f, Lj ) j=0

Any matrix A may be written as A = QR where Q is an orthogonal matrix and R is upper-triangular. If A is invertible, this factorization is unique



ˆ f = projU (f ) =

Positive-Definite

QR Factorization

Given an inner product B and a basis {v1 , ..., vn } of V , the Gram matrix S is a symmetric, positive-definite matrix such that

wi

(Example)

Factorizations

(a) B(u, v) = B(Qu, Qv) (Q preserves inner product)

Gram Matrix

B(wi , wi )

i=1

T

If Q is an orthogonal matrix and (V, B) is an inner product space, then for any vectors u, v ∈ V ,

n X B(u, wi )

u ˆ = projV (u) =

v Sv ≥ 0

(3) The columns/rows of Q are orthonormal

B(u, wi )wi

Given an orthogonal basis {w1 , ..., wn } of a vector space V with inner product B, we can compute the orthogonal projection of some vector u ∈ / V onto V by

where kui k = B(ui , ui ).

(2) QT = Q−1

n X i=1

An n × n matrix S is said to be symmetric if and only if S = S T

Orthogonal Matrices

 S= 

Projections Given an orthonormal basis {w1 , ..., wn } of a vector space V with inner product B, we can compute the orthogonal projection of some vector u ∈ / V onto V by

n−1

u n = vn −

Given an inner product B over a vector space V , two vectors v1 , v2 ∈ V are orthogonal if and only if B(v1 , v2 ) = 0

′

* All norms in Rn are equivalent

−1

T

x ˆ = (A A)

T

A v

(Projection of v onto Col(A)) The vector closest to v in Col(A), v ˆ, is the projection of v onto Col(A) defined by −1

T

vˆ = Aˆ x = A(A A)

T

A v

(Projection Matrix )

Projection and Least Squares

The matrix P that takes a vector v and projects it onto the column space of A is given by

Norms

Linear Regression (Line of Best Fit)

T

−1

P = A(A A) A norm k · k in a vector space V is a map k · k : V → R such that (1) kvk ≥ 0 and kvk = 0 ⇐⇒ v = 0 (positive-definite) (2) kavk = |a|kv k (3) ku + vk ≤ kuk + kvk (triangle inequality)

Norms in Rn P kv k1 = j |vj | qP 2 kv k2 = j vj

kv k∞ = max{|v1 |, . . . , |vn |}

A

T

Given n pairs of data points (x1 , y1 ), . . . , (xn , yn ) we can use least squares to determine the line that best fits these data points (or two numbers m, b ∈ R such that the sum of the squared distance between mxi + b and yi is minimal for all i). We can do this by setting up the following system  1 1  . . . 1

   x1 y1 x2     y2   b =   m .   .  . xn yn A

Using a least-squares solution, we get



ˆ b

m ˆ

T

−1

= (A A)

A

T

A subset U of a complex vector space V is said to be a subspace if and only if it is closed under vector addition and multiplication by complex numbers

 y1 y2    .   .. 

Hermitian Inner Products If V is a vector space over C, then a Hermitian Inner Product is a map B : V × V → C such that

yn

Polynomial Regression We can extend the idea of linear regression to best fit polynomials for a set (x1 , y1 ), . . . , (xn , yn ) of data points. A polynomial approximation of degree k is specified by the least-squares solution to x21 x22

x1 x2

x2n A

xn

... ...

...

xk1 xk2

1F −1 = n (2) F n n DFT Matrix Factorization

The 2n × 2n Fourier matrix can be factorized in the following form:

(1a) B is linear in the first argument: B(au + bu′ , v) = aB (u, v) + bB (u′ , v)

where A is the matrix whose ith row is [1, xi ]

 1 1  . . . 1

The n × n Fourier Matrix Fn satisfies

(1) Fn Fn = nIn



y  a 0 1   a 1  y2      .  =  .    .   ..   . yn ak xkn

F2n =

 aˆ  0

y  1

 y2   aˆ1     T −1 T   .  = (A A) A  .   ..   ..  yn aˆk

1   0  Dn =  .. . 0

(3) B is positive definite: B(u, u) ≥ 0∀u ∈ V and B(u, u) = 0 ⇐⇒ u = 0

Fourier Analysis

Let V be a vector space consisting of all continuous functions in the range [0, 2π]. Let U be the subspace of V consisting of all integer frequencies of sines and cosines:

k

fˆ = projU (f ) = a0 +

z z

=1

(7) eiθ = 1 (8) z = |z |eiθ (9) z1 · z2 = |z1 ||z2 |ei(θ1 +θ2 ) Complex Subspaces

0

...



0 . . .

ω2n

P2n

ωn−1 2n

      

P2n

0 0 1 0 0 0

0 0 0 0 1 0

... ... ... ... ... ... . . .

0 1 0 0 0 0

0 0 0 1 0 0

0 0 0 0 0 1

 ... . . . . . .  . . .  . . .  . . .  .  . .

∞ X

aj sin(jx) +

∞ X

bj cos(jx)

j=1

Determinant The Determinant is a unique function D : Cn × · · · × Cn → C that satisfies (1) D is mult-linear: D(u1 , . . . , aui + bui′ , . . . un ) = aD(u1 , . . . , ui , . . . , un ) + bD(u1 , . . . , u′i , . . . , un ) (2) D is skew-symmetric: D(u1 , . . . , ui , uj , . . . , un ) = −D(u1 , . . . , uj , ui , . . . , un ) (3) D(e1 , . . . , en ) = 1

aj = bj =

Z

1 2π Z 1

Permutation Formula Let σ = {σ1 , σ2 , . . . , σn! } be the set of all permutations of {1, . . . , n}. Let Pσi be the permutation matrix corresponding to the permutation σi . Then the gross formula for the determinant of a matrix A is

f (x)dx

0 2π

π 0 Z 2π 1 π

(*) Property (2) implies that if ui = uj for some i 6= j, then D = 0

2π

f (x)sin(jx)dx f (x)cos(jx)dx

det(A) =

0

X

Y

aj det(Pσi )

σi ∈σ aj ∈σi

For a finite number of terms, fˆ is known as a trigonometric polynomial.

Determinant Properties Let A and B be n × n matrices. Then

Fourier Matrix We can denote the nth primitive root of 1 as the complex number n ωn , such that ωn = 1. Defined in polar representation, we have wn = e

z |z |2

(6) For z 6= 0,

...



f (x)g(x)dx

j=1

(Notation)

(5) z −1 =

0 Fn

Determinants

2π

where

A complex number z = a + bi ∈ C has real coefficients a, b. We say that Re(Z) = a and Im(z ) = b. Addition and multiplication of complex numbers work exactly as they do over the real numbers.

(4) z · z = a2 + b2

0

Fn 0

0

Then the basis of U consisting of all frequencies of sines and cosines is an orthogonal basis. We can use this fact to find the projection of any function f onto the subspace U . This is given by

Properties

(3) z = a − ib

Z

B(f, g) =

a0 =

(1) z = a + bi √ a2 + b2

1 0 0  0 = 0  0  . . . 

where A is the matrix whose ith row is [1, xi , x2i , . . . , xi ]

(2) |z| =



and

U = span{1, sin(x), cos(x), sin(2x), cos(2x), . . . }

Complex Numbers

Dn −Dn



(2) B is conjugate-symmetric: B(v, u) = B(u, v)

If we consider the inner product defined by

(Interpolating Polynomial) A special case of polynomial regression is when we are approximating a set of data points (x1 , y1 ), . . . , (xn+1 , yn+1 ) using a polynomial of degree n. In this case, there exists a unique polynomial p(x) such that p(x1 ) = y1 , p(x2 ) = y2 , . . . , p(xn+1 ) = yn+1 . In other words, there is a distinct polynomial that passes through all n + 1 data points. This is known as an interpolating polynomial.

In In

where

(1b) B is conjugate-linear in the second argument: B(u, av + bv ′ ) = aB (u, v) + bB (u, v ′ )

Fourier Series which gives us the coefficient vector of the best-fit kth degree polynomial



2πi n

1 1  . Fn =  . .

1

1 ωn

ωnn−1

1 ωn2

(n−1) ωn

... ...

2

det (B) = det (A) (2) If B is obtained by performing a row exchange on A, then

Given a positive integer n, we can define the n × n Fourier Matrix Fn as 

(1) If B is obtained by performing a row operation on A, then

...

1 ω n−1 n . . . ω(n−1) n

(n−1)

     

det (B) = −det (A) (3) If B is obtained by multiplying a row of A by a constant k, then det (B) = k · det (A)

(4) The determinant of a product is the product of the determinants det (AB ) = det (A)det (B)

(5) If A is lower/upper triangular, then det(A) is the product of elements on the diagonal

3

det(A) =

n Y

A(i, i)

Where Cii = det(Mii ) is the determinant of the 2 × 2 matrix obtained by removing row i and column i.

i=1

−1

)=

1

B=M

T

det (A) = det (A ) (8) Similar matrices have the same determinant −1

(3) If A and B are similar matrices, they have the same characteristic polynomial and hence the same eigenvalues (the converse is NOT true)

det(A)

(7) Determinant of a matrix is the determinant of its transpose

B=M

−1

We can compute the determinant of a matrix by choosing any row or column and taking the sum over each entry in that row multiplied by the determinant of the matrix obtained by removing the given row and column. For any row i = 1, . . . , n n X i+j (−1) aij det (Mij ) j=1

Similarly, for any column j = 1, . . . , n: n X i+j det(A) = (−1) aij det(Mij ) i=1

Where Mij is the matrix obtained by removing the ith row and jth column from A

Eigenvalues and Eigenvectors

where the ith row of the matrix A corresponds to the coefficients in the equation

AM =⇒ PB (λ) = PA (λ)

(4) A matrix A has an eigenvalue of 0 if and only if det(A) = 0 (5) Any n × n matrix A and its transpose have the same characteristic polynomial and thus the same eigenvalues (but NOT necessarily the same eigenvectors)

AM =⇒ det (B) = det (A)

Cofactor Expansion

det(A) =

 y1 (t)  y1′ (t) ′ y2 (t)   y2 (t)       .  = A .   ..   ..  ′ yn (t) yn (t) ~ y (t) y~′ (t) 

2

PA (λ) = λ − tr(A)λ + (C11 + C22 + C33 )λ − det(A)

(6) Determinant of the inverse is the inverse of the determinant det(A

We can solve linear systems of ODEs of the form y~′ (t) = Ay~′ (t)

(2) For any 3 × 3 matrix A:

PA (λ) = PAT (λ) (6) If λ is an eigenvalue of A, then λn is an eigenvalue of An (7) If A is invertible and λ is an eigenvalue of A, then eigenvalue of A−1

1 λ

is an

Multiplicities (Algebraic Multiplicity) Suppose we have the characteristic polynomial PA (x) and the binomial (x − λ) divides PA (x). If k is the largest power of (x − λ) dividing PA (x), then we say that λ has algebraic multiplicity mλ = k. In other words, if a root λ is repeated k times in PA , it has algebraic multiplicity k. (Geometric Multiplicity) Suppose we have some eigenvalue λ of a matrix A. Then the geometric multiplicity dλ of λ is the dimension of the kernel of A − λI . In other words, dλ = dim(ker(A − λI)). (Theorem* ) The geometric multiplicity of any eigenvalue is always less than or equal to its algebraic multiplicity

~ yi′ (t) = ai1 y~1 (t) + ai2 y~2 (t) + · · · + ain y~n (t) We can use the following theorem to solve systems of Diff-Eqs: (Theorem* ) If v is an eigenvector of A with eigenvalue λ, then y (t) ~ y (t) = veλt is a solution of y~′ (t) = A~ In general, given n distinct eigenvalues λ1 , . . . , λn and corresponding eigenvectors v1 , . . . , vn the full solution set is specified by X λt λ t λ t ci vi e ~ y (t) = c1 v1 e 1 + · · · + cn vn e n = i

Linear Recurrence Relations Let f be a function of some integer n. If the value of f (n) can be defined in terms of a linear combination of f (n − 1), f(n − 2), . . . , f (n − k) for some k ≥ 1, we say f can be represented by a linear recurrence of order k. This has the form f (n) = a1 f (n − 1) + a2 f (n − 2) + · · · + ak f (n − k)

For real constants a1 , . . . , ak ∈ R. (Solving Linear Recurrences ) We can represent each successive computation of the recurrence as a linear transformation by some matrix A. Consider the following 2nd order example:

and let

f (n) = a1 f (n − 1) + a2 f (n − 2)

Let A be an n × n matrix over C. Then a complex number λ is an eigenvalue of A if there exists v 6= 0 ∈ Cn such that Av = λv, or (A − λI )v = 0

A real n × n matrix is called diagonalizable over R if and only if there exists a basis of Rn consisting of eigenvectors of A. In such a basis, the matrix of T (x) = Ax is diagonal. In other words, A is similar to a diagonal matrix

(Characteristic Polynomial)

A = MDM

The characteristic polynomial of an n × n matrix A is defined as PA (λ) = det (A − λI ) n

n

n−1

= (−1) λ + (−1)

tr(A)λ

n−1

+ · · · + det(A)

The roots of the characteristic polynomial are exactly the eigenvalues of the matrix A

−1

(Finding Eigenvalues )

(Theorem* ) Let A be a real n × n matrix and suppose {v1 , . . . , vk } are eigenvectors corresponding to distinct eigenvalues λ1 , . . . , λk . Then {v1 , . . . , vk } are linearly independent.

To find the eigenvalues of a given n × n matrix A,

(Corollary) If A is n × n and has n distinct eigenvalues, then A is diagonalizable.

(1) Compute the characteristic polynomial PA (λ) = det(A − λI ) (2) Find the roots of the characteristic polynomial Properties

Then we can rewrite v(n) in terms of v(n − 1) multiplied on the left by the matrix A of the linear transformation from v(n − 1) to v(n) v(n) =

where D is a diagonal matrix with the eigenvalues of A along the diagonal, and M is a matrix consisting of the eigenvectors of A. (Key Theorem* ) An n × n matrix A is diagonalizable if and only if for every eigenvalue, its algebraic multiplicity equals its geometric multiplicity.

Linear ODEs and Recurrences

2

PA (λ) = λ − tr(A)λ + det (A)

First-Order ODEs

 a2 v(n − 1) 0

 a1 1 A

Now let’s say we are given the vector v(0). Then we can use powers of the matrix A to compute v(n) for any n: v(1) = Av(0) 2

v(2) = Av(1) = A v(0) . . . n

v (n) = Av(n − 1) = A v (0)

If A is diagonalizable, this computation is trivial: n

(1) For any 2 × 2 matrix A:



 f (n) f (n − 1)   f (n − 1) v(n − 1) = f (n − 2) v(n) =

Diagonalization

Eigenvalues

−1 n

n

−1

A = (MDM ) = MD M So all we need to do is find the matrix M of eigenvalues, and then compute Dn (which is done by computing the nth power of every element on its diagonal)....