LINR ALG & NUM ANLY
LINR ALG & NUM ANLY AMATH 352
Popular in Course
Otilia Murray I
verified elite notetaker
Popular in Applied Mathematics
This 10 page Class Notes was uploaded by Mossie Pfannerstill V on Wednesday September 9, 2015. The Class Notes belongs to AMATH 352 at University of Washington taught by Staff in Fall. Since its upload, it has received 27 views. For similar materials see /class/192279/amath-352-university-of-washington in Applied Mathematics at University of Washington.
Reviews for LINR ALG & NUM ANLY
Report this Material
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: 09/09/15
AMATH 3527 LECTURE 10 JULY 167 2008 1 Solving systems with a nontrivial null space In the last lecture7 we looked at how to nd bases for the null space and range of a transformation Now Id like to start applying this to some linear systems The easiest thing to look at is linear systems TX b where the transfor mation T has a nontrivial null space This just means that NullspaceT 74 1 In other words7 NullspaceT contains nonzero vectors 1711 start off with the same transformation from the rst example of last lecture 4 12 32 T 1 43 756 2 3 71 52 We found that 712 NullspaceT span 1 3 1 and 12 32 RangeT span 43 7 756 7 4 71 52 with the right hand side of each providing a basis Now say I want to solve the equation 7174 Txb 196 5 78 And I happen to already know that 0 x17 12 6 i3 is a particular solution This comes from writing b as a linear combination of my basis vectors for RangeT 1 12 32 b7 43 73 756 7 2 71 52 Thing is7 since T has a nontrivial null space7 there are in nitely many solu tions To get the general solution of this system7 l have to take my particular solution and add a generic vector from NullspaceT 712 xgm X17 04 1 8 1 The scalar 04 here is allowed to take any value This is a general feature of transformations with a nontrivial null space The idea is simply general particular arbitrary vector i i i 9 solution solution in the null space lf 1 were dealing with a transformation with a two dimensional null space7 then the rightmost term here would be a generic linear combination of its two basis vectors If the null space were three dimensional7 it would be a linear combination of the three basis vectors And so on 2 How do I tell if TX b is solvable Everything ljust did was assuming that I already had one solution But how do I nd that one solution in the rst place How do I know that my system has any solutions to begin with My starting point is the fact that TX b has solutions if and only if b E RangeT There7s nothing subtle to this 7 its simply that RangeT is the set of possible outputs of T7 and b had better be a possible output if there7s going to be a solution How7 then7 can I check whether b E RangeT7 Say l7ve used the methods we7ve looked at to construct a basis for RangeT call it f17f27 7fn Say I can extract the part of b that7s orthogonal to f17f27 7f This is called orthogonalizmg b with respect to f17f27 7f39n 2 If this part is nonzero then b can7t possibly be in spanf1 f2 fn On the other hand if that orthogonal part turns out to be zero then l7ll know that b E spanf1 f2 fn meaning that the system TX b is solvable More formally here7s what l7m doing l7m trying to decompose b as bO 1f1O 2f2OlnfnE where the leftover piece E for error7 is orthogonal to all the vectors fi Then b E RangeT if and only if E 0 11 To be honest this would be a lot of work if I were just using it to check whether TX b is solvable However it leads up to the so called QR algorithm which is one of the cornerstones of numerical algebra Here are some of the things it can do o It lets me check for the solvability of a system 0 Say I need to solve a lot of systems TX b using the same matrix T while the right hand side changes This is pretty typical in modeling The QR algorithm lets me pay a lot of the computational effort as a one time cost o It lets me nd a best possible77 solution to a system that is technically unsolvable This is a key part of curve tting 21 Orthogonalizing with respect to one vector For starters say l7m just trying to orthogonalize b with respect to a single vector f1 That is l7m trying to write b Ollfl E where E f1 0 The key to this is the orthogonal projection Pfl pictured below But Pf b is the part of b that7s parallel to f1 This time we7re after b 7 Pf b which is the part of b that7s orthogonal to f1 f1 Pf1b In the past we7ve been after Pvu Conveniently the projection formula we7ve used before in R2 stays the same in higher dimensions So b f Mb 7 1 lt13 llflll regardless of how many components these vectors have In the end my error7 is E b 7 Pub lt14 b f1 b i 7 f1 15 Hflllz lt7s worth mentioning that if f1 has unit length this formula simpli es nicely to Ebibf1f1 16 22 Orthogonalizing with respect to two vectors Now lets tackle orthogonalizing with respect to two vectors f1 and f2 This case is more complicated but the method we7ll come up with works for orthogonalizing with respect to any number of vectors Here7s what Id like to do I gure that Pf b measures how much of b lies along f1 while PVZu says how much lies along f2 So l7d hope that I can get my error vector E by subtracting away these two projections 4 Unfortunately there7s a catch This only works if f1 and f2 are orthogonal Pages 7 and 8 illustrate this graphically You should understand the algebraic details l7rn about to give for why this does work if f1 and f2 are orthogonal although this overlaps with Lecture 11 However7 dont feel obligated to know the algebra behind why this doesn t work if f1 and f2 aren7t orthogonal l7ve written down the details7 but its just there in case you7re interested First off7 suppose that f1 and f2 are orthogonal To get started7 l7ll write the decomposition l7rn after b Otlfl 04ng But I dont know much of anything about this 041 042 and E are all unde terrnined Now lets see what happens when 1 project both sides of this equation onto f1 Pfi Pf1a1f1 Pf1a2f2 The left side of this equation is something I know how to compute The right side7 though7 involves a lot of unknowns My airn7 then7 is to simplify the right side so I can relate these unknowns to Pf1 The rst step is to simply plug in the formula for Pfl f1 f1 f2 f1 E f Pf 0417 f1 042 f1 041 1 f1 1 Hflllz Hflllz Hflllz This looks pretty ugly But l7rn assuming that f2 and E are both orthogonal to f1 which lets me kill off the second and third terms from the right side f1 39 f1 Pf1b 041 2 f1 llflll And this gets even nicer since f1 f1 HfHZ Pf1 Otlfl Sweet So7 calculating Pf1 b actually gives me the rst term in the decom position 18 Next l7ll project both sides of 18 onto f2 Going through the exact same steps again7 1 wind up with Pf2 Otgfg This is great Now I can go back to 18 and subtract off both of these projections to get b 7 Pf1 b 7 H2 E 24 This agrees with 177 which is exactly what I was hoping 17d getl Now suppose that f1 and f2 aren7t orthogonal I start off the exact same way as before7 by writing out b Otlfl 04ng Then 1 project both sides of this equation onto f1 Pfi Pf1a1fl Pf1a2f2 Pf1E f1f1 f2f1 0417 f1 0427 f1 0417 f1 Hflll2 Hflll2 Hflll2 I can still simplify the rst term on the right since f1 f1 Hflllz And I can still kill of the last term since l7rn assuming that E is orthogonal to f1 But I dont have any such luck with the next to last term since f2 f1 31 0 17m stuck with f f Pf1b aifi 0427 1 f1 28 flll2 When I go through the same steps while projecting onto f2 1 get 2 f f Pf2 041W f2 Otgfg 2 When I subtract both projections from 257 I get f1f2 f1f2 17041 1 2 HM2 Hlel2 f2 30 Instead ofjust getting my error vector E7 1 also have these terms with f1 f2 oating around making my life miserable 6 span V17V2 perpendicular d O onto spanned and PW u part of V2 shadow gives the the PV2 u Subtracting off this u casts a shadow plane by a Q D d D H E 5 D Q Cquot ltlt u that is Orthogonalizing With respect to orthogonal vectors V1 and V22 Failing to orthogonalize When V1 and V2 aren t orthogonal The shadow of u dark red isn t the same thing as PV1u l PV2u dark blue The end result green isn t perpen dicular to the plane spanned by V1 and V2 Al V HANK l l 2 2 1 23 An example This may not seem like such a great place to be but it turns out not to be so bad Even if f1 and f2 aren7t orthogonal to begin with I can make them be orthogonal without changing their span For now though lets go through an example in which f1 and f2 are orthogonal to begin with Say that 0 72 For whatever reason l7d like to know if 5 b 71 E spanf1f2 74 First l7ll project b onto f1 b 39 f1 5 1 Pf b 7 f1 f1 BE 1 HleZ 2 Next l7ll project b onto f2 b f 5 i 1 8 Pf2b i 72 f f2 2f2 HszZ 2 114 When I subtract both projections from b I get 5 1 binbin2b 71 73 71 i2 74 0 72 0 0 0 31 32 33 34 35 36 For one thing this tells me that b E spanf1f2 But at the same time l7ve gured out how to write b as a linear combination of f1 and f2 1 just found that b 7 Pf b 7 Pf2b 0 37 which I can rearrange to get bawmw so Then I can plug in what I found for the projections to get b 3f1 2f2 39 If f1f2 is a basis for the range of a transformation T then this gives me a solution to TX b 24 Orthogonalizing with respect to large sets of or thogonal vectors If I7rn looking at a larger set of orthogonal vectors say f1f2 fn this orthogonalization process works the exact same way Once again the idea is to look for the part of b that7s orthogonal to all the vectors Ie b aifi CYsz anfn E 40 where E is orthogonal to all the fk Much like I did for two vectors its not so hard to show that Pfkb akfk for all k 41 So if I subtract all n of these projections I get Eweawemwememw m At the same time if it turns out that E 0 the projections show me exactly how to write b as a linear combination of f1 f2 fn 3 Endnote When I gave this lecture I moved onto Grarnrn Schrnidt orthonorrnalization from here I think I did it a lot better in the next lecture though after talking about orthonorrnal sets of vectors in their own right So instead of having Grarnrn Schrnidt show up twice like it did in the lectures I7ll just put that off until the Lecture 11 notes
Are you sure you want to buy this material for
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'