×

### Let's log you in.

or

Don't have a StudySoup account? Create one here!

×

or

## Numerical Analysis I

by: Melvina Keeling

74

0

8

# Numerical Analysis I MATH 561

Melvina Keeling
CSU
GPA 3.78

Staff

These notes were just uploaded, and will be ready to view shortly.

Either way, we'll remind you when they're ready :)

Get a free preview of these Notes, just enter your email below.

×
Unlock Preview

COURSE
PROF.
Staff
TYPE
Class Notes
PAGES
8
WORDS
KARMA
25 ?

## Popular in Mathematics (M)

This 8 page Class Notes was uploaded by Melvina Keeling on Monday September 21, 2015. The Class Notes belongs to MATH 561 at Colorado State University taught by Staff in Fall. Since its upload, it has received 74 views. For similar materials see /class/210091/math-561-colorado-state-university in Mathematics (M) at Colorado State University.

×

## Reviews for Numerical Analysis I

×

×

### What is Karma?

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

Date Created: 09/21/15
Lecture 1 MatrixVector Multiplication You already know the formula for matrix vector multiplication Nevertheless the purpose of this rst lecture is to describe a way of interpreting such prod ucts that may be less familiar If I 2 A36 then b is a linear combination of the columns ofA Familiar De nitions Let c be an n dimensional column vector and let A be an m gtltn matrix m rows n columns Then the matrix vector product I 2 A36 is an m dimensional column vector de ned as follows lgza xj ilm 11 j1 Here I denotes the ith entry of b aij denotes the ij entry of A 2th row jth column and cj denotes the jth entry of c For simplicity we assume in all but a few lectures of this book that quantities such as these belong to D the eld of complex numbers The space of m vectors is Em and the space of m x n matrices is Cm The map 6 H A36 is linear which means that for any cy E C and any at E U Amy AHAy Ao c 061417 4 PART I FUNDAMENTALS Conversely every linear map from C to Um can be expressed as multiplication by an m x 72 matrix A Matrix Times a Vector Let aj denote the jth column of A an m vector Then 11 can be rewritten b 2 Ax Zacjaj 12 j1 This equation can be displayed schematically as follows b a1 a2 an 3 551 611 332 12 n an In 12 b is expressed as a linear combination of the columns aj Nothing but a slight change of notation has occurred in going from 11 to 12 Yet thinking of A56 in terms of the form 12 is essential for a proper understanding of the algorithms of numerical linear algebra One way to summarize these different ways of viewing matrix vector prod ucts is like this As mathematicians we are used to viewing the formula Ax b as a statement that A acts on c to produce b The formula 12 by contrast suggests the interpretation that 6 acts on A to produce b Example 11 Fix a sequence of numbers 331 Up and q are polyno mials of degree lt n and ac is a scalar then p q and op are also polynomials of degree lt Moreover the values of these polynomials at the points 6 satisfy the following linearity properties pqc pcqc mm Oltpc Thus the map from vectors of coef cients of polynomials p of degree lt n to vectors pc1pc2 pcm of sampled polynomial values is linear Any linear map can be expressed as multiplication by a matrix this is an example In fact it is expressed by an m x n Vandermonde matrix 1 61 61 2 n71 A 1 62 62 62 2 n71 1 56m 56m xm LECTURE 1 MATRIX VECTOR MULTIPLICATION 5 If c is the column vector of coef cients of p c C2 pc 2 Co else c2562 cn1cquot 1 Cnil then the product Ac gives the sampled polynomial values That is for each i from 1 to m we have Ac 2 Co c136 c236 cmlscy l pc 13 In this example it is clear that the matrix vector product Ac need not be thought of as m distinct scalar summations each giving a different linear combination of the entries of c as 11 might suggest Instead A can be viewed as a matrix of columns each giving sampled values of a monomial A 1 6 62 scn l 14 and the product Ac should be understood as a single vector summation in the form of 12 that at once gives a linear combination of these monomials Ac c0clscc2sc2cn1c 1 pc D The remainder of this lecture will review some fundamental concepts in linear algebra from the point of view of 12 A Matrix Times a Matrix For the matrix matrix product B 2 AC each column ofB is a linear com bination of the columns of A To derive this fact we begin with the usual formula for matrix products If A is 6 x m and C is m x n then B is 6 x n with entries de ned by bij I aikckj 15 1 Here bi am and cm are entries of B A and C respectively Written in terms of columns the product is c1 c2 cn 6 PART I FUNDAMENTALS and 15 becomes m bj ch Ecwak 16 Thus bj is a linear combination of the columns ak with coef cients ckj Example 12 A simple example of a matrix matrix product is the outer product This is the product of an m dimensional column vector u with an n dimensional row vector v the result is an m x n matrix of rank 1 The outer product can be written 01 U2 0 vlul anal u vlu v2u vnu Ulum h Unum The columns are all multiples of the same vector u and similarly the rows are all multiples of the same vector v D Example 13 As a second illustration consider B 2 AR where R is the upper triangular n x n matrix with entries rij 1 for i g j and rij 0 for z39 gt j This product can be written 1 1 b on a an i 1 1 1 The column formula 16 now gives j bj Arj 261 17 1 That is the jth column of B is the sum of the rst j columns of A The matrix R is a discrete analogue of an inde nite integral operator D Range and Nullspace The range of a matrix A written rangeA is the set of vectors that can be expressed as A36 for some at The formula 12 leads naturally to the following characterization of rangeA Theorem 11 rangeA is the space spanned by the columns ofA H LECTURE 1 MATRIX VECTOR MULTIPLICATION r Proof By 12 any Ax is a linear combination of the columns of A Con versely any vector y in the space spanned by the columns of A can be written as a linear combination of the columns y 2341ch Forming a vector at out of the coef cients at we have y 2 A36 and thus y is in the range of A D In view of Theorem 11 the range of a matrix A is also called the column space of A The nvllspace of A 6 CW written nullA is the set of vectors 6 that satisfy Ax 0 where 0 is the O vector in Cm The entries of each vector at E nullA give the coef cients of an expansion of zero as a linear combination of columns of A 0 sclal 2a2 Jinan Rank The column rank of a matrix is the dimension of its column space Similarly the row rank of a matrix is the dimension of the space spanned by its rows Row rank always equals column rank among other proofs this is a corollary of the singular value decomposition discussed in Lectures 4 and 5 so we refer to this number simply as the rank of a matrix An m x n matrix of full rank is one that has the maximal possible rank the lesser of m and n This means that a matrix of full rank with m 2 n must have n linearly independent columns Such a matrix can also be characterized by the property that the map it de nes is one to one Theorem 12 A matrix A E Cm with m 2 n has full rank if and only if it maps no two distinct vectors to the same vector Proof gt If A is of full rank its columns are linearly independent so they form a basis for rangeA This means that every I E rangeA has a unique linear expansion in terms of the columns of A and therefore by 12 every I E rangeA has a unique at such that b 2 A36 lt Conversely if A is not of full rank its columns aj are dependent and there is a nontrivial linear combination such that 2 cjaj 0 The nonzero vector c formed from the coef cients cj satis es Ac 2 0 But then A maps distinct vectors to the same vector since for any at Ax Ac c D Inverse A nonsingular or invertible matrix is a square matrix of full rank Note that the m columns of a nonsingular m x m matrix A form a basis for the whole space Um Therefore we can uniquely express any vector as a linear 8 PART I FUNDAMENTALS combination of them In particular the canonical unit vector with 1 in the jth entry and zeros elsewhere written ej can be expanded m ej Z z ai 18 i1 Let Z be the matrix with entries 2 and let zj denote the jth column of Z Then 18 can be written ej Azj This equation has the form 16 it can be written again most concisely as e1 em IAZ The matrix Z is the inverse of A Any square nonsingular matrix A has a unique inverse written A that satis es AA 1 A lA I The following theorem records a number of equivalent statements that hold when a square matrix is nonsingular These conditions appear in linear algebra texts and we shall not give a proof here Concerning f see Lecture 5 Theorem 13 For A E Um n the following conditions are equivalent a A has an inverse A b rankA m c rangeA 0 a nu11ltAgt 0 e 0 is not an eigenvalue of A f 0 is not a singular value of A g detltAgt e 0 Concerning g we mention that the determinant though a convenient notion theoretically rarely nds a useful role in numerical algorithms A Matrix Inverse Times a Vector When writing the product at 2 A41 it is important not to let the inverse matrix notation obscure what is really going on Rather than thinking of c as the result of applying A 1 to b we should understand it as the unique vector that satis es the equation Ax b By 12 this means that c is the vector of coef cients of the unique linear expansion of b in the basis of columns of A This point cannot be emphasized too much so we repeat A lb is the vector of coe lcients of the expansion ofl in the basis of columns ofA LECTURE 1 MATRIX VECTOR MULTIPLICATION 9 Multiplication by 4 1 is a change of basis operation Multiplication by A4 b coef cients of the expansion of b in 81 em A711 coef cients of the expansion of b in a1am Multiplication by A In this description we are being casual with terminology using 1 in one instance to denote an m tuple of numbers and in another as a point in an abstract vector space The reader should think about these matters until he or she is comfortable with the distinction A Note on m and n Throughout numerical linear algebra it is customary to take a rectangular matrix to have dimensions m x We follow this convention in this book What if the matrix is square The usual convention is to give it dimensions n x n but in this book we shall generally take the other choice m x m Many of our algorithms require us to look at rectangular submatrices formed by taking a subset of the columns of a square matrix If the submatrix is to be m x n the original matrix had better be m x m Exercises Let B be a 4 x 4 matrix to which we apply the following operations double column 1 halve row 3 add row 3 to row 1 interchange columns 1 and 4 subtract row 2 from each of the other rows replace column 4 by column 3 delete column 1 so that the column dimension is reduced by 1 a Write the result as a product of eight matrices b Write it again as a product ABC same B of three matrices Tlg gthNt Suppose masses m1 m2 m3 m4 are located at positions x1x2x3x4 in a line and connected by springs with spring constants k12k23k34 whose natural 10 PART I FUNDAMENTALS lengths of extension are 612623634 Let f1f2f3f4 denote the rightward forces on the masses eg f1 k12c2 61 612 a Write the 4 x 4 matrix equation relating the column vectors f and ac Let K denote the matrix in this equation b What are the dimensions of the entries of K in the physics sense eg mass times time distance divided by mass etc c What are the dimensions of detK 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 centime ters grams and seconds What is the relationship of K to K What is the relationship of detK to detK Generalizing Example 13 we say that a square or rectangular matrix R with entries rij is uppertriangular if rij 0 for z39 gt j By considering what space is spanned by the rst n columns of R and using 18 show that if R is a nonsingular m x m upper triangular matrix then R is also upper triangular The analogous result also holds for lower triangular matrices Let f1f8 be a set of functions de ned on the interval 18 with the property that for any numbers d1d8 there exists a set of coef cients C1 c8 such that 8 chfjigtdp i18 j1 a Show by appealing to the theorems of this lecture that d1 d8 determine C1 C8 uniquely b Let A be the 8 x 8 matrix representing the linear mapping from data d1 d8 to coef cients C1 68 What is the z39j entry of A4

×

×

### BOOM! Enjoy Your Free Notes!

×

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

Bentley McCaw University of Florida

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

Anthony Lee UC Santa Barbara

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

Bentley McCaw University of Florida

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

Parker Thompson 500 Startups

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!
×

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