Applications of Scientific Computation EAS205, Some Notes Jean Gallier Department of Computer and Information Science University of Pennsylvania Philadelphia, PA 19104, USA e-mail: [email protected] c Jean Gallier (cid:13) November 25, 2013 2 Contents 1 Introduction to Vectors and Matrices 7 1.1 Vectors and Matrices; Some Motivations . . . . . . . . . . . . . . . . . . . . 7 1.2 Linear Combinations, Linear Independence, Matrices . . . . . . . . . . . . . 17 1.3 The Dot Product (also called Inner Product) . . . . . . . . . . . . . . . . . . 26 1.4 Matrix Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 1.5 Inverse of a Matrix; Solving Linear Systems . . . . . . . . . . . . . . . . . . 40 2 Gaussian Elimination, LU, Cholesky, Echelon Form 49 2.1 Motivating Example: Curve Interpolation . . . . . . . . . . . . . . . . . . . 49 2.2 Gaussian Elimination and LU-Factorization . . . . . . . . . . . . . . . . . . 53 2.3 Gaussian Elimination of Tridiagonal Matrices . . . . . . . . . . . . . . . . . 75 2.4 SPD Matrices and the Cholesky Decomposition . . . . . . . . . . . . . . . . 78 2.5 Reduced Row Echelon Form . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 2.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 3 Vector Spaces, Bases, Linear Maps 99 3.1 Vector Spaces, Subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 3.2 Linear Independence, Subspaces . . . . . . . . . . . . . . . . . . . . . . . . . 104 3.3 Bases of a Vector Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 3.4 Linear Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 4 Matrices, Linear Maps, and Affine Maps 121 4.1 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 4.2 Haar Basis Vectors and a Glimpse at Wavelets . . . . . . . . . . . . . . . . . 136 4.3 The Effect of a Change of Bases on Matrices . . . . . . . . . . . . . . . . . . 151 4.4 Affine Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 5 Determinants 163 5.1 Definition Using Expansion by Minors . . . . . . . . . . . . . . . . . . . . . 163 5.2 Permutations and Permutation Matrices . . . . . . . . . . . . . . . . . . . . 171 5.3 Inverse Matrices and Determinants . . . . . . . . . . . . . . . . . . . . . . . 176 3 4 CONTENTS 5.4 Systems of Linear Equations and Determinants . . . . . . . . . . . . . . . . 178 5.5 Determinant of a Linear Map . . . . . . . . . . . . . . . . . . . . . . . . . . 179 5.6 The Cayley–Hamilton Theorem . . . . . . . . . . . . . . . . . . . . . . . . . 180 5.7 Further Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 6 Euclidean Spaces 183 6.1 Inner Products, Euclidean Spaces . . . . . . . . . . . . . . . . . . . . . . . . 183 6.2 Orthogonality, Gram–Schmidt Procedure, Adjoint Maps . . . . . . . . . . . 188 6.3 Linear Isometries (Orthogonal Transformations) . . . . . . . . . . . . . . . . 195 6.4 The Orthogonal Group, Orthogonal Matrices . . . . . . . . . . . . . . . . . . 198 6.5 QR-Decomposition for Invertible Matrices . . . . . . . . . . . . . . . . . . . 200 6.6 Some Applications of Euclidean Geometry . . . . . . . . . . . . . . . . . . . 202 6.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 7 Hermitian Spaces 205 7.1 Hermitian Spaces, Pre-Hilbert Spaces . . . . . . . . . . . . . . . . . . . . . . 205 7.2 Orthogonality, Gram–Schmidt Procedure, Adjoint Maps . . . . . . . . . . . 215 7.3 Linear Isometries (Also Called Unitary Transformations) . . . . . . . . . . . 218 7.4 The Unitary Group, Unitary Matrices . . . . . . . . . . . . . . . . . . . . . . 219 7.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 8 Eigenvectors and Eigenvalues 223 8.1 Eigenvectors and Eigenvalues of a Linear Map . . . . . . . . . . . . . . . . . 223 8.2 Reduction to Upper Triangular Form . . . . . . . . . . . . . . . . . . . . . . 230 8.3 Location of Eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 8.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234 9 Spectral Theorems 237 9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 9.2 The Spectral Theorem; The Hermitian Case . . . . . . . . . . . . . . . . . . 237 9.3 The Spectral Theorem; The Euclidean Case . . . . . . . . . . . . . . . . . . 239 9.4 Normal and Other Special Matrices . . . . . . . . . . . . . . . . . . . . . . . 240 9.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 10 Introduction to The Finite Elements Method 245 10.1 A One-Dimensional Problem: Bending of a Beam . . . . . . . . . . . . . . . 245 10.2 A Two-Dimensional Problem: An Elastic Membrane . . . . . . . . . . . . . . 256 10.3 Time-Dependent Boundary Problems . . . . . . . . . . . . . . . . . . . . . . 259 11 Singular Value Decomposition and Polar Form 267 11.1 The Four Fundamental Subspaces . . . . . . . . . . . . . . . . . . . . . . . . 267 11.2 Singular Value Decomposition for Square Matrices . . . . . . . . . . . . . . . 272 11.3 Singular Value Decomposition for Rectangular Matrices . . . . . . . . . . . . 277 CONTENTS 5 11.4 Ky Fan Norms and Schatten Norms . . . . . . . . . . . . . . . . . . . . . . . 280 11.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281 12 Applications of SVD and Pseudo-Inverses 283 12.1 Least Squares Problems and the Pseudo-Inverse . . . . . . . . . . . . . . . . 283 12.2 Data Compression and SVD . . . . . . . . . . . . . . . . . . . . . . . . . . . 291 12.3 Principal Components Analysis (PCA) . . . . . . . . . . . . . . . . . . . . . 292 12.4 Best Affine Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300 12.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303 13 Quadratic Optimization Problems 305 13.1 Quadratic Optimization: The Positive Definite Case . . . . . . . . . . . . . . 305 13.2 Quadratic Optimization: The General Case . . . . . . . . . . . . . . . . . . 313 13.3 Maximizing a Quadratic Function on the Unit Sphere . . . . . . . . . . . . . 317 13.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322 Bibliography 322 6 CONTENTS Chapter 1 Introduction to Vectors and Matrices 1.1 Vectors and Matrices; Some Motivations Linear algebra provides a rich language to express problems expressible in terms of systems of (linear) equations, and a powerful set of tools to solve them. A valuable feature this language is that it is very effective at reducing the amount of bookkeeping: variables and equations are neatly compressed using vectors and matrices. But it is more than a convenient language. It is a way of thinking. If a problem can be linearized, or at least approximated by a linear system, then it has a better chance to be solved! We begin by motivating the expressive power of the language of linear algebra on “the” typical linear problem: solving a system of linear equations. Consider the problem of solving the following system of three linear equations in the three variables x ,x ,x R: 1 2 3 ∈ x +2x x = 1 1 2 3 − 2x +x +x = 2 1 2 3 x 2x 2x = 3. 1 2 3 − − One way to approach this problem is introduce some “column vectors.” Let u,v,w, and b, be the vectors given by 1 2 1 1 − u = 2 v = 1 w = 1 b = 2         1 2 2 3 − −         7 8 CHAPTER 1. INTRODUCTION TO VECTORS AND MATRICES and write our linear system x +2x x = 1 1 2 3 − 2x +x +x = 2 1 2 3 x 2x 2x = 3. 1 2 3 − − as x u+x v +x w = b. 1 2 3 In writing the equation x u+x v +x w = b 1 2 3 we used implicitly the fact that a vector z can be multiplied by a scalar λ R, where ∈ z λz 1 1 λz = λ z = λz , 2 2     z λz 3 3     and two vectors y and and z can be added, where y z y +z 1 1 1 1 y +z = y + z = y +z . 2 2 2 2       y z y +z 3 3 3 3       For example 1 3 3u = 3 2 = 6     1 3     and 1 2 3 u+v = 2 + 1 = 3 .       1 2 1 − −       We define z by − z z 1 1 − z = z = z . 2 2 − −  −  z z 3 3 −     Observe that ( 1)z = z. − − Also, note that z + z = z +z = 0, − − 1.1. VECTORS AND MATRICES; SOME MOTIVATIONS 9 where 0 denotes the zero vector 0 0 = 0 .   0   If you don’t like the fact that the symbol 0 is used both to denote the number 0 and the zero vector, you may denote the zero vector by 0. Moregenerally, youmayfeelmorecomfortabletodenotevectorsusingboldface(zinstead of z), but you will quickly get tired of that. You can also use the “arrow notation” z , but −→ nobody does that anymore! Also observe that 0z = 0, i.e. 0z = 0. Then, 1 2 1 − x u+x v +x w = x 2 +x 1 +x 1 1 2 3 1 2 3       1 2 2 − −       x 2x x 1 2 3 − = 2x + x + x 1 2 3       x 2x 2x 1 2 3 − −       x +2x x 1 2 3 − = 2x +x +x . 1 2 3   x 2x 2x 1 2 3 − −   The set of all vectors with three components is denoted by M (some authors use R3 1). 3,1 × The reason for using the notation M rather than the more conventional notation R3 is 3,1 that the elements of M are column vectors; they consist of three rows and a single column, 3,1 which explains the subscript 3,1. On the other hand, R3 = R R R consists of all triples of the form (x ,x ,x ), with 1 2 3 x ,x ,x R, and these are row×vect×ors. 1 2 3 ∈ For the sake of clarity, in this introduction, we will denote the set of column vectors with n components by M . n,1 An expression such as x u+x v +x w 1 2 3 where u,v,w are vectors and the x s are scalars (in R) is called a linear combination. If we i let x ,x ,x vary arbitrarily (keeping u,v,w fixed), we get a set of vectors that forms some 1 2 3 kind of subspace of M . Using this notion, the problem of solving our linear system 3,1 x u+x v +x w = b 1 2 3 10 CHAPTER 1. INTRODUCTION TO VECTORS AND MATRICES is equivalent to determining whether b can be expressed as a linear combination of u,v,w. Now, if the vectors u,v,w are linearly independent, which means that there is no triple (x ,x ,x ) = (0,0,0) such that 1 2 3 (cid:54) x u+x v +x w = 0, 1 2 3 it can be shown that every vector in M can be written as a linear combination of u,v,w. In 3,1 fact, inthiscaseeveryvectorz M canbewrittenin a unique wayasalinearcombination 3,1 ∈ z = x u+x v +x w. 1 2 3 Then, our equation x u+x v +x w = b 1 2 3 has a unique solution, and indeed, we can check that x = 1.4 1 x = 0.4 2 − x = 0.4 3 − is the solution. But then, how do we determine that some vectors are linearly independent? One answer is to compute the determinant det(u,v,w), and to check that it is nonzero. In our case, 1 2 1 − det(u,v,w) = 2 1 1 = 15, (cid:12) (cid:12) (cid:12)1 2 2(cid:12) (cid:12) − − (cid:12) (cid:12) (cid:12) which confirms that u,v,w are linearly inde(cid:12)pendent. (cid:12) (cid:12) (cid:12) Other methods consist of computing an LU-decomposition or a QR-decomposition, or an SVD of the matrix consisting of the three columns u,v,w, 1 2 1 − A = u v w = 2 1 1 .   1 2 2 (cid:2) (cid:3) − −   The array 1 2 1 − A = 2 1 1   1 2 2 − −  