VideoPoints

• ••• • •• • ••••• • •
COSC 4364 Numerical Methods - Lecture22_SVD_Iterative_Equation_Solvers
Help Tour
© Distribution of this video is restricted by its owner
Transcript ×
Auto highlight
Font-size
00:00 uh mm hmm. I just wanted show. Yeah. That looks
00:14 yeah. I loved the first Yeah. What was the best show
00:27 him? I was so remarkable. now the stairs missing. Yeah.
00:37 . But that yeah, the first . Yeah, that's what he sees
00:46 . I was so attracted to the and I was okay. So
00:53 Mhm. Taking on adventure. your sister, did you tell
01:04 Yeah, interesting. I think that's D. R right now, but
01:19 think it was my more pieces because one it's one of those kids shows
01:24 the kim family. Yeah. Talk about this beauty and then you belong
01:34 equations overs. Again, that's a person. So if it works,
01:42 . So today, so tonight is they meet you talk more about the
01:51 to actually compute to think about their . I'll start with reminding you about
01:58 consuming about what the conversation is. then we'll talk a little bit about
02:02 example for you guys and move on this call the interactive questions.
02:11 So I'm just, it is useful flexes for any matrix. And it
02:18 basically this form where online and I value decomposition. So that's what's known
02:26 singular directors left and right. So not kind of symmetric in that case
02:33 the I. D. M. . So it's general. And uh
02:38 singular values. And this whole idea using this the composition is that it
02:45 you many properties about the matrix a shoulders, bridge, collapsed example.
02:55 if a represent the system. Chemical or something. And that kind of
03:02 . It gives you some notion of of resonant frequencies are frequencies you should
03:07 excite but things can make a There's singular values also said something about
03:15 number of agencies that are telling you about what doctors you can expect.
03:22 it also tells you a little bit how many dimensions kind of the opportunity
03:28 represent your problem be something accuracy. you can potentially reduce the size of
03:34 problem and consider without your knowledge. why I love this SPD in safari
03:42 to a lot of insights into systems they represent. Okay. And there
03:50 the two versions that we used to look at it. Ah no more
03:55 you actually need. So they may be a quadratic matrix that just like
04:03 . The book tends to talk mostly the full versions where you extend the
04:09 and extend also then the sigma But since this part is also zero
04:15 opinions when you do the modification it doesn't matter someone's coming extra
04:22 I don't like this. And I yes necessary for many applications. And
04:27 it was the gun rights for the values are very useful to find out
04:31 condition number. That's also that's actually get sound alright. What else for
04:38 And they're supposed kind of getting into I want to talk about. It's
04:43 bit of example of what might happen terms of our values. But the
04:47 point is we don't want to try frame here that they're both tend to
04:52 a lot of things in and so this straightforward why we derived the things
04:58 I did, that composition used in Product of anybody with itself and
05:04 so 80, 80 or 80. and that's forming this product is not
05:15 a good idea, not only big with the parking lot and then doing
05:20 but because the Mhm. Remember the values of a ta is the square
05:27 the Eigen values of E. And it sort of maps into the singular
05:33 and because the singular value is the root, oh the new values for
05:38 kind. But anyway, what I'm is so you can look at the
05:44 of singular values for a. Then ratio of the similar rest of the
05:51 number, the condition number called T. A. It's square On
05:56 condition # 4 8. So basically gets considerably worse than works in terms
06:03 the condition on with the work of entity than to work with the
06:08 So the map that I want to about is best for not doing
06:17 So I was like yes. Um this is one of the most common
06:22 of computing the single brother the Okay, so this stuff but basically
06:29 with the matrix. No surprise Then next step is and so the dominating
06:35 is to transform this matrix and to the original objects and for that one
06:43 householder transformations the word coast. And they show examples on the next
06:51 Yes but remember the householder transformation is way you're staring up a column with
06:58 diadem. So so by applying the household transformation you can do it for
07:06 equations and then the best from all for the next etcetera and think about
07:10 triangular matrix. But you're doing it little bit different than you have to
07:15 to figure out a single out And then I can do the next
07:20 here to do fewer iterations and turn by diagonal into diagonal and mixed economy
07:26 in terms of known in the same about the composition and using math lab
07:32 is cold and it gives you what the matrix and then it returns to
07:39 about the composition for this. There's kind of approach to completely, this
07:47 about the composition. I'm going to a little bit about the details of
07:53 two steps and you have to yeah think the violin and composition simple values
08:04 Okay so here is how it Um some of the P. And
08:11 . For these sets of slides are you buy a householder transformation to
08:20 Well what's going on there diagonal in first column here so you get to
08:27 stuff this the Xs are not the , but just try to emphasize what's
08:31 and what's not. So you have to this point and then once you
08:38 then is you kind of do it household the transformation from the back of
08:44 matrix. So now you you kind the linear combination of columns here within
08:51 linear combination of rose to throw things Now in the linear combination of columns
08:57 zero the rest of And this part the 1st group. Now, if
09:05 do that, you don't ruin anything did in the first problem. That's
09:09 feature of the house of transformation. you do best for left and then
09:14 do the right householder and then you back to doing your left to move
09:18 . So when you see a lot things up, do the right and
09:22 two goals and then your best to , okay, you're gonna have to
09:26 by. But that's again the reason I um included householder transformations early on
09:33 talking about the questions always, because can be used not only have a
09:39 method for solving systems of equations, was used in the calculation method of
09:45 Eigen values and Eigen vectors and it's used, it didn't seem to have
09:49 bad compositions about this, it's a good workhorse. So in front collapsed
09:58 the actions that I've done on the , this whole sequence when you're,
10:02 know, another expression. But it lots of peace on that. And
10:07 the middle of them is the by economic metrics. But you found through
10:13 transformations and then or the right side as well. So then this the
10:20 has a their composition ah into. this is what they did this,
10:32 and this whole thing. But you rewrite it basically as also a common
10:39 of hate. Doesn't guess what happened the next about this again or in
10:44 household the transformation that has this So and then take a and multiply
10:51 properly and with all the fees from left and all the s from the
10:56 and then what you're left with is Matrix speech. Oh, So this
11:01 under one. Oh and you can the product here. So now the
11:09 step on this slide was to do it to a diagonal matrix and then
11:15 is kind of more confidence in doing . I'm doing the household in the
11:21 part. Yeah, someone here. best of marking them. Um to
11:28 is set on the front side Seattle's to get the diagonal form. And
11:35 somebody discovered you can actually be very and you tend to work with the
11:43 that these tried to drag on matrix it's the metrics. So that's not
11:46 bad. So it's fairly simple to the Eigen values. And that means
11:52 the single violence for this guy When turns off the 23 too clever,
11:58 one doesn't have to form this thing productive on the Yeah, I'll just
12:07 you on the next slides exactly how works so on, then use
12:12 Now the givens rotation part stop. talked about that too in terms of
12:17 in misericordia Kobe method for finding value not to be confused. The local
12:22 don't want to talk about today in of equations over. So got his
12:29 Associated one on 1 thing. So there was this rotation things but involves
12:35 trying to steer things out. And here's this one we went through the
12:42 and hopefully remember that CNN actually physical sign, the geometric center. So
12:53 here is now despite diagonal matrix. then we're going to apply this given
13:02 on the backside. And we wanted kind of and anyway, this
13:09 Um now, so the best way think of this is this is the
13:15 left hand corner of this type being call sign and science and the rest
13:20 the zero except for the diagonal this best. And so this ends up
13:27 up in the corner and then there's once on the rest. So the
13:31 thing that is going to change is it melted back on the back and
13:36 the first two columns in the for . So I have the first column
13:45 1st 2 roles in the first Someone you do you guys play this
13:50 times the first column did you feel your combination of these two guys?
13:54 that the cns enters in the first that also applied for this one and
14:00 have chosen you see him. That's so that this question posed to be
14:05 . But that doesn't guarantee that this . So that's why it's a plus
14:14 . Now when we talked about the I am valued it was symmetric matrix
14:19 then it turned out two of them up being zero but this is obviously
14:24 a symmetric matrix. So in this you get that energy. So yes
14:31 changed basically 190 to 0 and non to 90. So it doesn't seem
14:38 be much of a win. But turns out it is anyway, so
14:43 still optimistic. So it continues scenario , this is the givens rotation of
14:49 householder but it's not applied from the . So now you live in a
14:54 of these two days in order to . After the things that you actually
14:59 up. So now I have been combination of these two roles. That
15:02 only thing that happens and empty that you just 20 things up. But
15:09 combination of these roles means that to something. So now I kind of
15:17 pretty much where you started and then have got one more element but it
15:22 this X. It's not the same we started with. So it's actually
15:26 . But so you keep doing this they call and they chased this plus
15:33 so he's moving here left, And then there's completely so now you
15:40 with these two roles and zero Um These two roles it's about 100
15:50 discard Youtube still operate with these So the new entry gets zeroed out
15:55 then do a linear combinations for So you keep doing this left and
16:02 and right. And um so eventually have to say start the boss is
16:09 . So now you have a back having him by a diagonal. But
16:13 turns out that an early all these above the diagonal are smaller than you
16:22 . So basically you have emphasized the and sort of boosted it and the
16:28 diagonal has gotten smaller. So then just repeat this until you basically have
16:36 the offering of elements that are small that you can basically treat them.
16:41 the diagram. So this is uh methods for doing. Yeah I can
16:49 some years just following the whole things events where you can collect all the
16:55 you need from the left. Um from the rights and then we can
17:02 stick in whatever you did for the . And eventually again the singular
17:07 the competition of A. This is we started with at least four to
17:13 and then we can pull it all . So now they have been thinking
17:16 the big composition all the metrics. it is quite an involved process to
17:24 single under the competition. But each is very simple. So that's
17:32 And it took a long time for to come up with these are here
17:37 to do it and that's why. , but now it's well known.
17:41 now they're starting to do it for . But it just tells you what
17:47 steps are. So the things I that wasn't in the book uh,
17:52 or at least not much is the and forgiveness transformation that works on major
17:59 . zero elements in ways that So two transformation methods are something that should
18:09 it and know all they're on the and Yeah, a little bit.
18:18 any questions on this, the only I wanted to know is exactly the
18:23 after all the detailed steps. But 10 years. So that's the problem
18:31 to basically things with. And then other board gave a lot of examples
18:39 motivate single about their conversation in the and then it's a little bit helpful
18:44 the vacuum and just show what it . So this is a settlement
18:49 understand progress. So that this example just five movies in this case.
18:57 the notion is that As the September rules. One of the group for
19:04 that we're supposed to rate whether they're fiction content and any one of these
19:11 movies. So the different members of group, they have different ratings in
19:17 of how much of it it was the stage I guess from 1-5.
19:22 the other group was trying to figure what was in a romantic content in
19:26 five movies and escorted. Ah yes provides scale according to that. So
19:33 thought there was some romantic content in area move whereas the first groups of
19:39 there is no scientific on science fiction . And they still so now what
19:45 that have to do with it? file in their composition. So you
19:50 do the same thing about the Then you've got something like this.
19:58 now I'm. And basically the number columns here as well as some
20:05 Um The com pronouncing the value matrix close in this case there were the
20:11 concepts science fiction and romance and then potential coupling. And that's what happens
20:18 problems. Ah yeah let's see. . So these are the concept and
20:25 the last one, The little financial between the two and then someone
20:32 So I just said yes so each role here then you know there's still
20:36 user. So one entry, 1 role for every user. And then
20:41 another thing too the concept and this to them. Yes. And the
20:47 spread for this particular reviewer and And as we can see there's kind
20:55 an increasing scale And you see the things here the number goes up stronger
21:00 somebody talked about that concept. Mm . And then this one tells them
21:08 overall kind of relative significance or strength scientific. Certainly didn't find fiction.
21:18 as we can see the values associated but generally higher than the values assumptions
21:23 . So then also different in the values the environment and then the last
21:32 and tells you that in terms of relationship between the different movies. Um
21:39 the particular concept that was used There's one so for each one of
21:44 distinct concepts and then one for the this is the way of trying to
21:50 in this particular example what the different of the singularity deposition means in terms
21:56 an application and that was it in of single mothers in the conversation for
22:06 try to give you against some intuition explain how real destiny codes do
22:18 Which topic for practice. All the again. And part of the reason
22:25 this happens at this stage in the . And why not talk about all
22:30 questions always up front when I was about direct solvers. Reason to understand
22:38 these guys work. doctor needs to , I think that so not the
22:49 , but this is where understanding condition and Eigen values. Oh, that's
22:57 . Comes back at this stage in book. So who has heard about
23:04 of these methods? We should have about? No. Oh,
23:14 Um first before I thought it's a simple method for solving systems of
23:23 Um, it's not necessarily good and and it made sense. It's a
23:32 to interactions. So it may take of iterations before you have the
23:38 So it's not very well much used it's so simple. So if you
23:43 care and have a small problem, the dominating that that could be used
23:49 this afternoon today is this kind of bar. So all right. So
23:58 is a idea about the but if matter's do so as the most expensive
24:06 right into your succession succession of approximation the solution. You're not saying that
24:13 fun from convergence. So every iteration you a little bit uh better approximation
24:21 smaller heritage actually solution, but it's always guaranteed this morning. But
24:27 it's the idea is to get a of approximations and then, you
24:34 if you are the patient did not , surely you get close enough to
24:39 solution if it does converge. But no guarantee that any one of the
24:45 for to find out whether there's a chance it will convert and as I
24:54 , the direct methods that don't give any approximate solutions on the way it
25:01 perhaps the grind through all the I think you get the solution that
25:06 have something about the solution is but have no approximation on the web.
25:14 other one reason that it got the I will say dominate is because it
25:21 to be that understand those problems out , projects carried by spores noticed forest
25:30 disease. Everyone knows about detectives as as matrices. So basically make disease
25:41 which Most elements are zero. So means you it may Some systems there
25:51 be 10-290 and two days in a . Even though the role has many
25:56 of others. So and and when in machine learning that people are trying
26:04 figure out how to use. Forrest because oh, it saves a lot
26:12 storage and computing computing the zeros is of not very efficient The products that
26:18 stuff holding the soft Zeros on my . So dealing with sparse matrices,
26:23 a big topic and it turns out the objectives are very efficient in terms
26:31 storage because we'll never need to work zeros if you um look at this
26:40 matter and you think about your and . So even if the loss of
26:46 and the matrix from the start, you do the elimination process like a
26:54 begin expectation today it's even much worse it got another nation things that are
27:01 when you start I tend not to zeros at the end. So the
27:06 we know it initially various first in on the end up being close to
27:12 full advancement. So when you have legacies, people try to stay away
27:18 these direct methods and go for this for computational and storage aspect. And
27:27 of course the hope that it converges quickly. So that means you may
27:33 you may even do unless work. . And that steps in a way
27:39 the steps you need to do So that's why learning about and understanding
27:47 method sees practically very important. Okay . That's pretty much what number he
27:57 in terms of um, so this great diabetes and stem cells and stem
28:05 . Some comments have done this processing so a lot of algorithms for instance
28:12 image processing, they tried to do detection and the best to look at
28:17 bunch of nearby pixels and it's kind a template to look at how to
28:22 many of our picture's pixel values to out that's that's sort of the hard
28:28 or not. But it's kind of neighborhood have complications and that's typically called
28:37 the same thing. It's either filters the processing that you do some combination
28:44 limited number of values typically found out cover stand. So um anyone that
28:54 learning and convolutional neural networks, what's end on CNN for short we do
29:01 combination of a limited number of It's a fixed rule for how the
29:06 stuff and that's the sense of and ends up being also reflecting this varsity
29:12 the matrix that you're actually representing system what I saw that was that now
29:21 terms of what does this actually mean terms of computing that So there you
29:28 something hit that the methods you have problems started trying to solve it and
29:33 your ex right 1840 and then somehow decided to nature their methods and universal
29:40 too. And on the right hand you have the q minus a and
29:47 oldest correct and all my little sense this point but I'll show you what
29:55 going to make sense. But at function if one does this thing and
30:00 the X okay converges to the same as the X. Star. Then
30:05 you get this equation and if you at this equation, it actually means
30:09 the stories solution to this equation because have this on the left hand side
30:15 you know this and on the right side there are the same. So
30:18 the end this is what you So that each of the methods generally
30:25 try to be clever and finding good such that this is because this and
30:32 eggs. Okay you need to solve equation because you have a matrix
30:37 So it's like you know elimination or or you want to talk about.
30:44 this that you have to solve this to get your next teacher. So
30:49 want to choose your cue. So this equation is tribute And that's what
30:55 Kobe is. one cents short. there's something that I said so you
31:00 to, I want to do this me is that that's all they want
31:05 rapidly and it should be easier for all the same question. So when
31:12 standing up behind you choose your cue there is this Kobe is one particular
31:19 of Q. That is one known well known choices. This cal sino
31:26 of fixing your cube and I want talk about those here. Uh you
31:33 principle on his mind. Here was right hand side in the hand,
31:38 save your roles or whatever the current of by um you compute the right
31:43 side. Then you solve this you get the new X. Value
31:48 then you compared with the previous one say well if it's small enough then
31:56 um it doesn't impress. It'll mean they're close to the solution. It
32:01 mean that the change is personal. have to be careful. So now
32:07 focused methods something it is so they this a right down and then for
32:15 details for each role of the It's kind of a in the product
32:22 roll away from the problem acts like general correspondent right cancer. Um Now
32:30 to do, It may not look clear what this is. Um but
32:34 we look at some details for the . Value, what they have is
32:40 shadow of A. So this is to and the sum here is of
32:47 column Memphis in Rome A or I you skipped the diagonal value. Ah
32:56 that that has has moved from the hand side. So and so if
33:01 makes it uh in the product rows columns for old time's comin accept his
33:08 , dying on the value and then have to evaluate. So it may
33:12 somewhat more clear if one goes back this formulation here. So Q is
33:18 fact the diagonal matrix. Was that or a. So that was a
33:25 up. Then the diagonal from That may skip the triangle in this
33:31 . And because you have the diagnosis matrix here on the left hand side
33:36 solve it is just simply to divide the so this is just, that's
33:44 , that's pretty much all there is um So I hope this method and
33:50 , it's not too good to divide zero. So if that happens you
33:53 to be careful maybe do some computational in column and electrics and so on
33:58 get them on stage I have done guess yes we start to computing this
34:08 personally making select products. Mhm. role of a transfer vector and then
34:15 all the roles finds the same So it's basically thank you so
34:21 So mr preserves the matrix as we it from. And then I think
34:29 there's an example here in terms of doing the appropriate corrections or this was
34:35 you're supposed to do. So if takes the first row here. Ah
34:41 we for eliminating and use the diagonal . That's Q. So yes they
34:47 left for the rest of the role and then there was miners on the
34:54 hand side. So they're sticking out previous restoration this value And then this
35:03 was zero and then yes no one and two was the diagonal value.
35:11 that's why you get divided by troops services exporters just like to say and
35:20 for the next role being. Now this volume three moves to the left
35:26 side. And then we have this investing that. Okay well next one
35:33 X really first component of X. third component of X. And then
35:39 have the right hand side for the of the mascot seven. So it's
35:46 simple. Ah And that's why sometimes shows up problem is small or you
35:56 need to worry too much about the and I'll come back to that.
36:01 I guess this is an example of the steps continuously following this procedure,
36:11 the patriots of acceptance changes and this about the solution. So on this
36:20 quite a number of steps of this problem. Uh huh. So already
36:29 thanks. This is true, but the basic starting points in talking about
36:35 attracted methods and against. Hmm this just um whatever it is shown that
36:43 kind of one slide and make you know, the paychecks to pick
36:48 dag diagonal, the universe is a matrix. Just the inverse of the
36:54 elements. That simple for um when look at this, you have to
37:00 through the queue formally you've got tested in verse and still, which is
37:06 identity matrix. And then you get inverse times A. But it's the
37:11 time here. And so it's interesting look at this matrix because then uh
37:18 particular matrix is constantly obliteration matrix because you're done substituting ex con and you've
37:26 the power of two of this So the properties of this final here
37:32 B is very important. So we confused to be and you get something
37:38 this, then I'll come back to . Right? So, and he
37:45 just Pacifica will no longer think that's badly. This one. Now the
37:51 one is 19 observation and um what does is it looks like this.
38:06 If we start from the top with question one and 2, etc.
38:09 so it computes comments the new components of the vector X one by
38:20 starting with the first and then the . Is that trying to do it
38:24 the order? Ah But that's What I mean is when you're computing
38:31 the second component of X, the one, you already know the first
38:38 . So the point is, if I know it, why not
38:41 it. So that's what method does the new estimates on the solution for
38:50 component X unknown along the beginning. now this matrix vector product is split
38:58 two. So the first part against many historical one and continued to do
39:06 . So, but this is the flowing role of a still X I
39:12 raw any, but for the first prior to where we are now.
39:20 what's already known is the X. is for J less than I for
39:28 someone's to use. Um And for part from and for the rest why
39:34 don't have enough computer them yet. still to split this matrix structure and
39:42 and otherwise it's fun of this So it's a little bit in terms
39:47 many times emphasize the computational part. is this ends up being eventually through
39:56 move through all the eyes. This a lower triangular matrix uh and this
40:02 an upper triangular but there's still essentially multiplication. It just happened to
40:10 The matrix vector multiplication along the So the lower part is the view
40:16 the after party. So and I that's just stuff. An example of
40:28 thing is going um So in this um but the first one um still
40:36 the diagonal, but Kobe has the side to start with, but then
40:41 also don't want to use the lower , but that's why someone is computed
40:46 first one, you don't have any one. So basically that's the same
40:53 stepped on it a phobic. But now when you start to work with
40:58 second roll that we have, this is now known otherwise It's the same
41:05 five entries as before. It's just used known values over So on this
41:17 you can look at the interest here now when Jacoby was 21 No,
41:24 got to a good approximation. Perfect in just nine steps. So so
41:34 just shows that by using in this the illiterate as it becomes known,
41:42 will get faster convert Oh, that's very simple modification of the marathon.
41:50 you see me better convergence And later , I will show you that it's
41:57 absolute figure out that that should be things not just for this prediction matrix
42:04 in general it's true. Like outsider faster and you can show that because
42:11 right volume value on the interaction matrix smaller but the time to show that
42:21 and here now okay making formulation again same thing. This is what I
42:26 the iteration matrix and we don't know come back and talk about this guy
42:32 but this is what it is. I can form this disease in configure
42:40 the substance slides coming up but the of values of this one is compared
42:45 the for instance the Kobe iteration projects most suitable and then there's another twist
42:57 both days to that is known as over relaxation but it's especially refinement or
43:07 Are these three methods for the voice the expression gets a little bit more
43:12 but not very messy. Uh It's under you know underlying is either
43:19 of these someone here is now what successive over relaxation method is and what
43:29 does is it kind of weights the computer values. So this can be
43:37 . No, this is for the split into two parts but they can
43:42 use a cobia tips that you prefer . So this computes kind of a
43:47 estimates and this is the old So what this is our method does
43:53 does a weighted sum old versus new the real neighbor. So depending on
44:02 you choose your so called relaxation parameter give me a bird fasting but if
44:10 don't use it carefully. So basically outside this range. Um You were
44:16 out of that and then it doesn't . So but at least you know
44:23 is a range in which it does . And then how much it grows
44:29 on on subsequent flights on the I values of the iteration matrix that corresponds
44:37 this value. Now just uh and is kind of an extra. So
44:48 had to figure out what I want use this thing at some point.
44:53 it's some reference just to figure out do you he was using Omega is
44:58 simple necessarily. That is an So it's a bit of a guessing
45:03 . People have sort of looked How do you choose it? There
45:06 some references for potentially to choose. relaxation but you only can always accept
45:14 you're interested. There's something, so guess there's a concrete example. Same
45:24 not using shor. Um so now I got this 1.1. This example
45:33 I want to get plugged in. is just a symbolic plantation first.
45:38 the linear combination. Again, this uh the from the classical underlying thing
45:45 see both using in the old um the steps and yeah, so in
45:55 case it's got the solution with the and several steps that we have 29
46:03 with a good oh my God. they got seven. So it's kind
46:08 refinement to start with it straightforward Kobe innocence to fill a little bit
46:15 Not particularly difficult to get Speidel used . I knew as you have completed
46:21 . And then a little bit more is to use the S.
46:24 R. By doing the weighted sum all the new and and the trick
46:30 to figure out what they would do that. Now, as I
46:36 trying to understand um the convergence of methods is now it's good to go
46:46 and look at this matrix formulation and mine iteration matrix. Mm hmm.
46:54 case will be for the guest star or so we have. Thank you
47:02 the Q -1 that was on the hand side and now we have to
47:08 the omega in here. So not simple numbers but um this is kind
47:17 iteration patrons a little bit. So thing I'm going to talk about
47:21 Now we have the situation matrix established this. Same a matrix for the
47:28 letters. Does the covid was citadel the castle. So and it was
47:36 , difficult. So alright, at this point a lot of times
47:42 questions so far. Mhm. So also make exploitation with this common and
47:52 to go. Not a good notation dealing with this method. So as
47:59 noticed um we kind of They're also matrix a as in their composition into
48:06 . Thank you sis or the We're only worried about the diagonal.
48:11 pulled it up automated sort of hue in terms of the gods. Adele
48:18 out D. And it turned out lower triangular part of taking. So
48:22 is now a triangle lower triangular matrix this is the upper triangular matrix.
48:28 outside down they use this one's for new um X. Values and this
48:34 we are heard and that was for old. Okay thank you. So
48:41 trying to um work for these methods there's they choose to do to use
48:49 negative sign because they end up on right hand side. No so then
48:55 kind of pass from the right hand and that's funny. There's nothing
49:00 It's just the definition of the what's the best Canadian values into the
49:09 ? So now Jacoby had this you question and he looked at the metrics
49:17 , this is what it was. was minus a on the right hand
49:20 . So now you get the positive the lower and upper triangle matrix.
49:25 this is basically a. We're all a. Without without the D.
49:33 and then the guy outside del method used as a servant mm hmm.
49:41 triangular especially after trying on the part A. For the old and the
49:49 oil and the lower triangular was used the so formally yeah and you can
49:59 this and solving this one is just to whether diagonal values for each
50:03 So that was this triangle is always of turns out to be very simple
50:09 ends up the gun being just the vector multiplication on the right. And
50:18 the store method, it gets a bit more involved. And when the
50:22 are but it's the same idea And now. So here's kind of
50:29 summary. I'm just so iteration made exist to be called to be in
50:36 book. But basically it's the Identity -2 -1008. And now when we
50:45 this form of a et cetera similar the go outside go and their
50:54 they got the corresponding iteration matrices and what look at iteration, matrix B
51:03 elements for it go upside down and script. Adele's to the substrate omega
51:11 the as far depending upon what the factories, it's not going to talk
51:22 . So The local wire around this and sort of ironman is 2 -1
51:30 as iteration matrix here. So of in talking about convergence is to try
51:41 figure out what is the error. how does the error change for the
51:46 ? Yes, but how this equation . And then we can subtract X
51:53 . So now we have this for error at the eighth iteration on the
51:56 hand side and manipulating the expressions either it and subjecting X on both
52:06 This is this the end funds So you can have an idea here
52:12 that X cameras on X and suggested rejects. And then we have
52:20 and use this relationship here for the as we modify the inverse. And
52:26 manipulating expressions we got now this thing . But this this is that the
52:32 then at the cake decoration is the , matrix times they had during the
52:38 situation. So now and we want look at the convergence best that they
52:46 to repeat this plug in. Ah there's one expression for X, K
52:52 in terms of the previous or Error indicates an error in that came on
52:58 one. And then I guess now expression here. So now it's kind
53:06 I am Venezuelan substitute second question often until you get to the starting error
53:13 still Sudan you have the power of situation. So in the usual
53:20 if you just think these are but if you think in terms of
53:27 regularity equation, investment says it's whatever thing is that we raced to the
53:33 is smaller than one in magnitude. so after it was sufficient many
53:42 multiplication of the number by itself. it's small enough that this guy gets
53:50 . So it's important that this thing less than one north korean state.
54:00 they use the matrix norm. That's so in the matrix norm this needs
54:06 be less than a month for the to convert and that's smaller. The
54:15 norm is the fastest growth. So is something wasn't right and it is
54:25 basically norman said so and that's so basically the norm and the norm
54:36 related to the Aryan values as You know, remember the norm of
54:43 matrix was, this is based on Inspector normals. Um and the
55:00 the norm of the matrix is related the so and we had this notion
55:13 the spectrum ranges that was um prevented the normal romantic spectral radius is all
55:25 is the commanders of this guy. radios was the investment. They are
55:41 member of this guy. So and for instance, if about after
55:50 but one thing was we look at , so try to find out first
55:56 then if the norm of the Eigen of the matrix um since less than
56:04 , one way was to that one use simple things that we step foreign
56:09 that tells about the item rather so but simple law built in a row
56:13 column sounds and absolute values and that you one thing and I'll give you
56:18 one in the company. So figuring whether this type of condition or this
56:24 is true, may not think of lot of work. They don't need
56:28 actually necessarily compute all the items and still taking off, there's any item
56:34 or even the largest Eigen value. wonder these conditions to their simple trick
56:41 is to figure out what is this is satisfied. Alright, so now
56:51 you're using this matrix sufficient from the slides um so this was the iteration
56:58 did for it's a program at them now what the values of the
57:06 the spectral radius is for this particular and this producing the characteristic for
57:14 typical other values and the solution. in that case the spectral radius is
57:19 maximum absolute value. So it's close .6 for this particular case. So
57:26 the next thing is to, to gods side method, we have a
57:31 decoration matrix here. So now you to try to figure out their young
57:36 for this guy and a spectral So here is the same idea,
57:41 we can do it again more or . So now the spectral radius Is
57:49 . So the spectral radius. So is much smaller. So that will
57:52 you you can expect this method to about faster and then the problematic because
57:58 venues is smaller, so and it um So the for this particular metrics
58:08 21 iterations to get to the So and then here is the and
58:18 I'm sorry that's so are based on , that's like that messed up.
58:24 in this case here they said the values and all the largest -10.
58:29 this tells you that you should expect convert the fastest one that we have
58:34 about and you're cool with this stuff that's okay and so somewhere on this
58:43 and maybe it's coming up but basically number of iterations was seven for this
58:49 or dying for so I don't know 21 freaking cold. So by looking
58:57 the Spectral Radius one they convinced one the let's be converted the bestest and
59:08 what I mentioned, the boring one is a bag of dominance.
59:13 people have Children for these two methods the matrix is diagonally dominant and that
59:19 of relates to the going to the circles were right in that case we
59:24 the during my body is the center the circle and the radius was some
59:29 the order. There are elements. the monster this is best for
59:35 So if this condition is true that diagonally dominant than you can guarantee
59:43 But this is a simple thing to . Um but you know, it's
59:51 . Yes, this is what I . So and this symmetric, positive
60:00 , it is symmetric. It's obviously definite means that this is too but
60:06 also means that um positive, not for the questions always, but in
60:17 of nature's profits but and there was this session. So I mean that's
60:23 order now this is what I already on the previous slide that their relaxation
60:29 Amanda needs to be in this interval it to pervert the speed of convergence
60:36 not obvious from where the people of again it's an animal. It's about
60:47 simple benefits faster than expected, but okay to talk about any questions on
60:55 methods. Okay. So they congregate but the uh is by far the
61:07 common methods and then comes in many variants um and where the software packages
61:20 . So we kind cover it in little bit. So you may be
61:30 with or for it all at least 1% that the um any one of
61:40 of us. Okay, okay, our best plan. Think of this
61:51 picture here as one of the level and the steepest percent. Trying to
61:58 out where the slope is if you to minimize something. Say so this
62:03 the bottom of this photograph then in status desserts or take a step here
62:11 start to figure out where the slope the steepest and hope that wouldn't even
62:16 so you take some step along direction steepest descent and before I end
62:24 just take a look finger off speakers the gradients and the speakers and then
62:32 go in that direction for him some and then keep thinking that forever,
62:38 stuff. They try to reassess where is agreement and that's where you go
62:44 take the Now with so called contradictory methods does things differently and trying to
62:57 a little bit more clever. it does not necessarily go along where
63:06 center is the steepest. They tried get things a little bit quicker and
63:12 that particular techniques. Okay. And of going and this direction hardly issues
63:19 available. And that's what this is things straight in. And if this
63:30 starts out the the different formulation of to solve the problem. Mm
63:41 And initially it was you the direct because that's why it's formulating is it
63:51 guaranteed to find the exact solution after no number of steps. People in
64:01 beginning, I just looked at it a direct method, as an alternative
64:08 mhm Dawson or other methods until somebody that in fact they get good
64:21 What's that? That's what became the of the particular, generates approximation one
64:29 . Okay, so now a bit all the formulas for talk about this
64:38 previous method. So matrix notation. , so it's works for other matrices
64:49 . But for now, just a case where a Selectric. Um,
64:58 then the tradition, it's being used best that they used angle brackets for
65:05 inner product of two vectors. You've to be. Um and of course
65:11 is. He will be a compliment take the transport to get their own
65:16 for transit column because you get the and the product is the number.
65:21 and in this case possible and all , the order in which you write
65:26 down doesn't matter. That's the 72nd . So no, I think some
65:36 arsenal that is an important aspect to it means that the product is zero
65:47 now so long that I'm trying to this notion of in the product.
65:56 by sticking basically a in the middle trump You can be invested in in
66:07 product eight and 2 or breast best just decayed in the middle. Um
66:16 dream, this is still this is know, making expected product of the
66:23 of this is still a number of . When we have these two
66:31 you can't be, they said they marginal if in the product zero.
66:39 it's kind of generalizes some of A conjugate. Yeah, A in
66:46 product example, so it's um. . Kind of a problem in a
66:56 sense because it depends on. Okay then and then coming back to this
67:02 definite thing that you know that basically , you know, a respect itself
67:11 respect to the agency. This is . So to get to this method
67:25 and look at this expression ah one to find um and X. That
67:37 this expression and it's comfortably cannot, if you do then you have a
67:43 to a so that's a certain the for the economy gradient that this difference
67:52 the formulation of how to find a but it was me and that's not
67:59 . Um So that's so we started this quadratic form and then trying to
68:12 find the minimal point say, of expression as usual. And we want
68:19 find minimum. You take the drivetrain put the driven to zero and then
68:23 for that. And I find this . So in this case we need
68:30 take the derivative of this expression. if you do that this expression here
68:38 have, wow xd context. So the infected derivative with respect to
68:46 On the front side. And you the extracts and then you take the
68:50 with respect from the backside and get um 35 cents. So you have
68:57 for this is the um don't ever with respect to X. Um This
69:03 and then the relative with respect to one is simple. It's just so
69:10 we wanted to find a solution. this finance solution for X.
69:17 It's 00. And then it's gonna that um And since a was symmetric
69:27 assumed in this case. So this basically the same thing, basically have
69:31 X minus B. And put it zero. So best to the minimum
69:36 for this expression. It's a solution it. Yeah. So that's now
69:48 basis for the continent's matters. And see what we got here. So
69:56 and then it's going to be but it looks and um that's
70:02 So again now. So it turns if it moves all the way to
70:09 , one has a cat solution. our best of lists a sequence of
70:15 um that the Senate's are a conjugate . And then look at the linear
70:29 of these supports. The directors. they continued with respect to each other
70:35 that's kind of an important part. and then um to find the projection
70:46 the solution. That's the answer. subcontractors, we need to find the
70:52 coefficients that project X R two. going to get direct manufacturers now.
71:02 yes. Um because these Right, , that sounds like, but If
71:19 look at eight times six. So the new multiply this expression by
71:26 So then you get the concept get out in front and 80.
71:34 there there is big directors. And um the the vectors are trying to
71:43 to respect each other. So when look at this product here, the
71:48 thing that will survive is the term has the Director of P K in
71:54 because DK is that they can get to all the other key records.
72:02 this thing hands of simply being this here and on the right hand side
72:11 this depression. And when visiting the that it does is quantity here.
72:19 , if you do this exercise what's left is basically Alpha as they
72:29 the product here and on the right side in this case. So you
72:34 out so it's an easy way to the output in this case. This
72:39 in your product. And this is of his ah little bit more complex
72:45 the matrix spectrum of location gives you output. Now we're going to this
72:58 a minimize er And so it's it , yes, this transformative stage,
73:07 . And then we discovered after um I said, they thought it was
73:12 direct method and not very useful. They worked not attractive on this from
73:21 cannot produce this, doesn't it? just a matter of you already went
73:26 this part. Um So now one instead or doing it was an extraction
73:37 . Mm hmm. Principal eight Actually people to be if they have
73:43 solution. So one looks kind of error. That is known as the
73:51 . Um That's what it is Are there's still a half hour of
73:56 matrix vector product of the current Dietrich the right hand side. So that's
74:01 field coming error in some success It's not X versus the previous illiterate
74:08 not expert versus the true solution. just how much the right conduction psychiatrist
74:16 in the state. That's the receipt then there is a way of using
74:23 thing you recognize from the previous life now works for the residual and living
74:29 the product instead of working with the that wasn't previously. So then that's
74:36 finds new iteration vectors P. Or direction vectors P. Based on the
74:44 current septic connected structures and the current . And then we can figure out
74:51 you want to verify that this new direction vector. Is that in
74:58 hey, can we get to of only the most recent but potential there
75:04 um the property also all the papers offers. So now we have a
75:11 of best confusing news going to get doctors and okay, some of
75:19 There it is. Ah I'm sorry but the best way I'll go through
75:35 action going again. Procedure method Done. Yes. Mm hmm.
75:44 forget the starting point tested. So you take the scaling of the current
75:51 rector and residual. But then here's you like to do. So you
75:57 making spectral products so that's really dominating that gives you a new actor.
76:04 that's one part of the a continent the product. Then reform this
76:15 Take time to get thanks for the iteration of P. We respect
76:20 So without this about the questions So this is basically what they are
76:27 spontaneity or responsibility that concludes to that happens here and then and then you
76:36 stated with the previous computed somewhere. Yes, so this is best to
76:45 in a product that were signaled by but computation procedure informer matrix director product
76:53 the product. And this is just scalar operation dividing two numbers. Students
76:59 form a new update of the solution moving his step outta here. That
77:06 from this expression along the when you inspector T so that's following the red
77:15 and the artists like daniel update for on this product and then, so
77:27 is the best and then you have converge when things are both. So
77:34 just here is the convergence condition. all as long as the square root
77:39 this card. So it's best for norman it's small, the disorder and
77:48 some scale version of the right hand then keep doing iteration on this.
77:57 , keep doing it working on. basically it's based on the residual converting
78:03 to zero. But then this code also scheduled. I spoke to the
78:08 of the right, so that is um Right and right. Mr said
78:20 the residual vectors in control against the of each other. Reform is being
78:27 product guaranteed to miss era if I J is different. And so this
78:36 , that's what it says in terms the complications necessary. So it's um
78:43 simple method in terms of Okay, , for example, so um so
78:52 matrix as before. Not using the gradient factors and there's unlike this
78:59 there is no trickery, you're finding relaxation parameter is straightforward, fully deterministic
79:05 to do. It's a well known . What the steps are in computing
79:11 in a product or a product and the scaling factors comes out of the
79:18 , how far on the left and hand side or a we are from
79:24 other And it turns out and this and three steps, Yes, you
79:32 ended up the servants. So I it's somewhere on the block and this
79:41 so they kinda get greater method is we should definitely remember. You
79:50 you need to remember necessarily all the , but it's a common minted
79:54 And yes, so you see for one, you know, um
80:06 so I intend to also them, wants a big conditioning. It's always
80:18 they convert it's faster. It's the A has nice properties. So sometimes
80:24 are clever. So they try to an approximate direct solver technological m and
80:30 the condition the matrix and known as precondition methods on how you do
80:36 You don't need to know but you understand what this emotional preconditioning means.
80:42 because like uh they talk about each them methods, right? The spectral
80:48 for smaller converges faster and it's the thing, someone trying to get this
80:53 to have um small respectful failures or partition number and then things from bird
81:01 well. In the past, it's the methods like there's about an old
81:09 that's from the old days. you can't see anything else. I'm
81:15 . Nothing installed. Mm hmm. really being one of this.
81:23 that might be something that's happening. it's friends. No, what?
81:40 this is one of them. So just kind of pulling on the bar
81:47 what you see this kind of lighter thing movement. That is in fact
81:52 happens in this method when you do facts that come up rotation, this
82:01 Moves one step from the left to right, this space for iteration
82:08 So when you look at this, this is pulling on the bar.
82:15 so when obviously you want the subjective to converge. But I don't know
82:21 there is a time to remember, the thing that happens, so you
82:27 to have a look at this And in the media, they realized
82:32 . So basically what happens is basically the boundary conditions of the force
82:39 from one end to the other Matrix vector multiplication. The error does
82:44 decrease. So when you see that is pretty much constant until it's appropriated
82:55 . So it's just to give you notion that thank you about the behavior
83:02 this happened many times, depending on to do. There is kind of
83:07 propagation face and then once the whole has seen what's going on, The
83:13 thing is confidence. So um people , you know how the area decreased
83:21 number of visitors and then you see thing and then and you've covered this
83:24 you want to know why but things . So to get some intuition
83:30 what goes on in this playing tricks there bro. I think some of
83:35 kinds of administrations. Okay? Thank . Thank you. Ah I'm
-
+