### Create a StudySoup account

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

Already have a StudySoup account? Login here

# NUMERICALMATRIXANALYSIS MATH543

SDSU

GPA 3.72

### View Full Document

## 58

## 0

## Popular in Course

## Popular in Mathematics (M)

This 25 page Class Notes was uploaded by Burnice Ratke on Tuesday October 20, 2015. The Class Notes belongs to MATH543 at San Diego State University taught by P.Blomgren in Fall. Since its upload, it has received 58 views. For similar materials see /class/225266/math543-san-diego-state-university in Mathematics (M) at San Diego State University.

## Reviews for NUMERICALMATRIXANALYSIS

### 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: 10/20/15

Numerical Matrix Analysis Lecture Notes 2 Introduction Review Peter Blomgren blomgren peter gmail com Department of Mathematics and Statistics ynamicai Systems roup Computationai Sciences Research Center San Diego State University San Diego CA 9218277720 httpterminussdsuedu Spring 2010 Peter Blon ren Lecture Notes ntroduction Review Outline 0 Linear Algebra 0 Intro Review Crash Course Peter Blom Lecture Note 2 Introduction Review Linear Algebra Intro Review Crash Course Linear Algebra Introduction Review Crash Course We start off by a quick review of basic linear algebra concepts and algorithms Depending on your background this will either be a review of things you know possibly in a new notation framework or a crash course 0 O O O C An n dimensional vector i is an n tuple of either real i E R or complex 52 E C numbers in this class all vectors are column vectors 139 e X1 X2 XERquotgtX 7whereX RIl2n Lecture Nolez 2 nlroduclion Review eview Crash Course Vectors Transpose Addition amp Subtraction We express a row vector using the transpose ie iERniiTX1 X2 Xn Vector addition and subtraction X1 Y1 X1 in X2 yz xz i yg x7y6R xi i Xn yn Xn iyn zX i y7 i12n 7 425 Lecture Notes 2 7 Introduction Review Linear Alge Intro Review Crash Course Matrices Matrix Vector Product An In x n matrix In rows n columns A with real or complex entries is represented an 312 313 31n A 321 322 323 32n 30 E R7 or 2 2 39 39 aa 6 C l am1 amZ am3 arnn l Sometimes we write A E Rm or A E men If A E Rm and i E R then the matrix vector product b A52 is well defined and b E Rm where n bE aijxj i12m 11 Lecture Notes 2 eview Crash Course Matrix Vector ProdL t Functional Definition X1 b1 311 312 313 a1n x2 b2 321 322 323 azn X3 brn am1 amZ am3 arnn L I J Xn b2 321X1 322X2 323X3 32an Note We need n multiplications and n71 additions to compute each entry in In total we need In n multiplications and mn71 additions We say that the matrix vector product requires 9m n operations 5351 Lecture Notes 2 7 Introduction Review 7 525 Linear Algebra Intro Review Crash Course Matrix Vector Product as a Linear Combination X1 b1 311 312 313 i i 31n X2 b2 321 322 323 i i aZn X3 bm 3m1 amZ 3m3 amn Xn 311 312 313 am 321 322 323 aZn X1 X2 X3 Xn aml 3mg 3m3 amn X151 X252 X353 39 39 39 Xn5n Peter Blom Lecture Note 2 Introduction Review Linear Algebra Intro Review Crash Course Matrix Vector Product Linearity The map 2 a A from R to Rm or from C to Cm is linear e v19 6 R C and 043 6 R C Ai AiA 14034 04A AM 69 aAi 6A9 Note Every linear map from R to Rm can be expressed as mul tiplication by an m x n matrix Peter Blomgren Lecture Notes 2 7 Introduction Review Linear Algebra Intro Review Crash Course Example The Vandermonde Matrix Given a set of points thz7 Xm we can express the evaluation of the polynomial px Co 61X 62X2 Cn71x 1 at those points using the m x n Vandermonde matrix A and the vector 6 containing the polynomial coefficients CO 1 X1 X12 X1 1 7 Cl 1 X2 X22 X5 1 A 7 C C ii x xiii Mr Forming l3 AE gives us an m vector containing the values of pxi i12m Lecture Notes 2 Linear Algebra Intro Review Crash Course The Vandermonde Matrix Linear Least Squares Evaluating polynomials using matrix notation may seem cute and useless But wait a minute this notation looks vaguely familiar from the discussion of linear least squares LLSQ problems from Math 541 In case you forgot or never studied LLSQ The goal is to find the best model in a class ie low dimensional polynomials to measured data observations y made at the points X The discrepancy error between the model and the observations is measured in the sum of squares norm Peter Blomgren Lecture Notes 2 7 Introduction Review 7 nu25 Linear Algebra Intro Review Crash Course Linear Least Squares Explicit Example Find the best straight line px Q l 61X fitting the observations Xry E 0717 1727 27239573747 477 We have the 5 x 2 Vandermonde matrix A the 2 vector E of polynomial coefficients and the 5 vector 9 of measurements 10 1 11 2 A 12 aloof y 25 13 Cl 4 14 7 The Linear Least Squares Problem Find the E Which minimizes the least squares error HA5 7 5351 Peter Blomgrei Lecture Notes 2 7 Introduction Review 7 1125 Linear Algebra Intro Review Crash Course Linear Least Squares Explicit Example 7 i i i i i i i i i i i i i 0 1 2 3 4 Figure The data points Xy and the straight line corresponding to the best fit in the leastesquareysense ie pX 63 cfx m Peter Blom Lecture Note 2 Introduction Review Linear Algebra Linear Least Squares Explicit Example Intro Review Crash Course Given a model 6 we can evaluate to corresponding linear polynomial px 0 l 61X at the points X 3 A6 The pointwise error in the model is e l3 7 9 Co 061 Co 161 Co 261 Co 361 Co 4C1 395 l l D 006171 016172 0261725 036174 l604 1775l The least squares error is given by 5 LSQ 91 llAE 11 Peter Blomgren 7 1325 Lecture Notes 2 7 Introduction Review Linear Algebra Intro Review Crash Course Linear Least Squares Explicit Example In order to identify the optimal choice of 6 we compute the partial derivatives with respect to the model parameters and set those expressions to be zero in order to identify the optimum 8rLSQ 7 artsQ O 860 861 After some work which is not central to this discussion we get the Normal Equations ATAE ATy cgt ATAe 7 y 0 Even though the matrix A is usually tall and skinny here 5 x 2 the matrix ATA is square here 2 x 2 The formal solution E ATA 1AT9 to this linear system gives us the coefficients for the optimal polynomial the red line on slide 12 Peter Blomgren Lecture Notes 2 7 Introduction Review 7 1425 Linear Algebra Intro Review Crash Course Unanswered Questions to be Revisited The previous LLSQ example raises more questions than it answers the most important one Would anyone in hisher right mind form the matrix ATA then invert it ATA 1 then multiply the vector ATy by the inversequot The answer is No which raises even more questions This class is all about how to solve linear systems taking issues like speed accuracy and stability into consideration We will revisit the questions raised by the example in more detail later However we will use the example to introduce some further linear algebra functionality and terminology Peter Blomgren Lecture Notes 2 7 Introduction Review 7 1525 eview Crash Course Matrix Matrix Product The matrix matrix product B AC is well defined if the matrix C has as many rows as the matrix A has columns Ban Aka Can The elements of B are defined by rn bij Z 3ch k1 Sometimes it is useful to think of the columns of B bj as linear combinations of the columns of A rn bj Aej Z ckjak k1 Lecture Notes 2 7 Introduction Review Linear Algebra Intro Review Crash Course The Transpose of a Matrix AT The transpose of a matrix A 30 is the matrix AT 3J7 eg 311 312 313 314 311 321 331 341 A 321 322 323 324 7 AT 312 322 332 342 331 332 333 334 313 323 333 343 l 341 342 343 344 i l 314 324 334 344 i The operation is intellectually simple just mirror across the diagonal but can be quite memory access expensive especially for large matrices For complex matrices C the complex Hermitian transpose is given by CH where c is the complex conjugate of c ca l bi7 caibi 53g Peter Blon ren Lecture Notes nlroduclion Review 7 1725 Linear Algebra Intro Review Crash Course The Range and Nullspace of a Matrix A The range of a matrix written rangeA is the set of vectors that can be expressed as a linear combination of the columns of Aan ie rangeA y E Rm 9 Ax for some i E R we say rangeA is the space spanned by the columns of Aquot The nullspace of a matrix A written nullA is the set of vectors that satisfy Ax 0 ie nullA x E R Ax O Peter Blomgren Lecture Notes 2 7 Introduction Review 7 1325 Linear The Rank of a Matrix Aan Intro eview Crash Course The column rank of a matrix is the dimension of rangeA its column space The row rank of a matrix is the dimension of its row space or rangeAT The column rank is always equal to the row rank we will see the proof of this in a few lectures hence we only refer to the Rank of a matrix rankA An In x n matrix is of full rank if it has the maximal possible rank minm7 n An In x n m 2 n matrix A with full rank must have n linearly independent columns Lecture Notes 2 7 Introduction Review 7 1925 Linear Algebra Intro Review Crash Course Recall The Normal Equations ATAE ATy cgt ATAe 7 y 0 Due to the tall and skinniness of A the equation A6 7 y 0 does not have a solution Given a vector E we can define the residual FE A6 7 9 which measures how far from solving the system we are We notice that the solution to the normal equations requires that the residual is in the nullspace of AT The solution is in rangeA such that the residual is orthogonal perpendicular to range AT Peter Blomgren Lecture Notes 2 7 Introduction Review 7 Zn25 Linear Algebra Intro Review Crash Course The Inverse of a Matrix A An invertible or nonsingular matrix A is a square matrix of full rank The In columns of an invertible matrix form a basis for the whole space Rm or Cm any vector x E Rm can be expressed as a unique linear combination of the columns of A In particular we can express the unit vector j which has a 1 in positionj and zeros in all other positions rn ej E Zija 7 ltgt ej AZJ39 If we play this game forj 1 m we get l g mAL2122 2m v Imxm Z Lecture Notes 2 Linear Algebra Intro Review Crash Course The Inverse of a Matrix A We have ImeAZ The In x m matrix mm which has ones on the diagonal and zeros everywhere else is the identity matrix The matrix Z is the inverse of A Any square nonsingular matrix A has a unique inverse written A l which satisfies AA 1A 1AI Lecture Notes 2 eview Crash Course m X m Equivalent Statements for a Square Matrix A e For a matrix A E mem the following are equivalent 0 A has an inverse A 1 o rankA m o rangeA Cm nullA 6 o O is not an eigenvalue of A o O is not a singular value of A o detA 7 0 Note The determinant is rarely useful in numerical algorithms it is usually too expensive to compute m Lecture Notes 2 7 Introduction Review 7 2325 Linear Alkel Intro Review C Homework 1 e at 1234pm Friday February 5 TB712 Suppose the masses m1 m2 m3 m4 are located at positions X1 X2 X3 X4 in a line and connected by springs with spring constants kn k23 k34 whose natural lengths of extension are I12 23 I34 Let f1 f2 f3 f4 denote the rightward forces on the masses 5g 1 k12X2 X1 I12 a Write the 4 x 4 matrix equation relating the column vectors f and i Let K denote the matrix in this equation b What are the dimensions of the entries of K in the physics sense 5g mass gtlt time distance mass etc c What are the dimensions ofdetK again in the physics sense d Suppose K is given numerical values based on the units meters kilograms and seconds Now the system is rewritten with a matrix K based on centimeters grams and seconds What is the relationship of K to K What is the relationship of detK to detK 5351 Peter Blon ren Lecture Notes nlroduclion Review 7 2425 Linear Algebra Intro Review Crash Course Illustration Homework 1 Lecture Note 2 nlroduclion Review

### 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

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "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.