2 10 2012 Computational Methods CMSC AMSC MAPL 460 Vectors Matrices Linear Systems LU Decomposition Ramani Duraiswami Dept of Computer Science Ways to implement a matrix vector product Access matrix Element by element along rows Element by element along columns As column vectors As row vectors Discuss advantages 1 2 10 2012 Vector norms v x x x 1 2 n Two norm Euclidean norm n v 2 x2 i i 1 If v 2 1 v is a unit vector Infinity norm max x 1 x 2 x n One norm Manhattan distance n v 2 x 1 i i 1 v For a 2 dimensional vector x sketch the set of vectors with two one and infinity norm equal to unity Matrix norms Can be defined using corresponding vector norms Two norm One norm Infinity norm Two norm is hard to define need to find maximum singular value related to idea that matrix acting on unit sphere converts it in to an ellipsoid Frobenius norm is defined just using matrix elements 2 2 10 2012 Condition Number of a Matrix A measure of how close a matrix is to singular cond A A A A 1 i maximum stretch max i maximum shrink min i i cond I 1 cond singular matrix Matrix Transformations A sequence or composition of linear transformations corresponds to the product of the corresponding matrices Note the matrices to the right affect vector first Note order of matrices matters The identity matrix I has no effect in multiplication Some not all matrices have an inverse M 1 M v v 3 2 10 2012 Solving Linear Systems One idea compute inverse Not usually a good idea unless inverse is computable easily and accurately using some matrix property Leads to increased errors and is more expensive usually Easy systems to solve Diagonal system Triangular system On board and then matlab Cost of diagonal solve is O n x zeros n 1 for k 1 n x k b k A k k end 4 2 10 2012 Solving a triangular system Cost of solving a triangular system Loop of size n Each loop has a cost of k or n k So total cost is 1 2 n 1 n n2 Representing linear systems as matrix vector equations Represent it as a matrix vector equation linear system We will apply the familiar elimination technique and then see its matrix equivalent 5