VideoPoints

• ••• • •• • ••••• • •
COSC 4364 Intro to Numerical Analysis - Lecture03_Matlab_Hoerners_Rule
Help Tour
© Distribution of this video is restricted by its owner
Transcript ×
Auto highlight
Font-size
00:09 so I think it is time to lecture. So I will stuck with
00:20 a few of the slides that I not get to about Matlin last
00:26 And then so Josh will do the off the demo. He prepared that
00:31 did not get to last lecture, then I will continue with Mm
00:39 What relates to error, Propagation and start to talk about pulling no meals
00:49 , and the question came up and since if you have joined after I
00:57 it, so the first assignment should posted today, and it's a mixture
01:04 pencil and paper and meth lab exercises the pencil on papers Versions are a
01:18 about understanding floating point numbers that is , um, intrinsic to everything in
01:25 course and pretty much anything you do well that I will talk about the
01:34 slab slides that I did not So these are the few things that
01:40 left over, and they're not, think particularly difficulty. It's just a
01:48 thing to be aware off the There are some tricky, though,
01:58 try to cover and make sure that do. You understand that there's a
02:01 bit surprising. So first, is slide. Basically, I think I
02:08 that last time, and it just pie in it. And it's an
02:12 off one off the variable names that initialized in math lab. If you
02:24 something to those special variables, as call them, then they assume the
02:33 you assigned to them, so that obviously thio errors. If you
02:39 A sign something to pi and Try to be very accurate and you
02:43 a lower position or you use it something totally different than your code.
02:49 not behave as you expected it, the system doesn't consistently used by as
02:56 representation of the value or by, these are just another few, and
03:02 not much Thio comment on it. think it's pretty common. Maybe the
03:07 that are somewhat unique is Epps from Epsilon and it in the interactive
03:13 It tends Thio type out ends to you the answer of an expression that
03:18 may have Captain eso in terms of operations that math lab supports the common
03:27 operations on. There is not, think too much Thio comment on
03:34 The president's order is also the normal in math that, like in this
03:43 as you do multiple occasion or division you do the addition. So there's
03:50 in how to interpret expressions without introducing to force explicitly president's order. Of
03:58 , it's never bad to explicitly define using parenthesis. But if you don't
04:04 normal president's order, uh, prevents of this is the one it's actually
04:12 evaluated us, um, some of built in functions and, like in
04:17 programming languages, their functions for square , exponential logs and take functions and
04:26 mean etcetera. So there is no that sense. My flab is not
04:32 different from any other language. There some unique ones that I will talk
04:40 . And as it says on the of the slide here, you can
04:43 out what's included in the math lab . In terms of these functions,
04:49 are 15, um, so this . I'll start to show a little
04:59 about how in some sense operators as it's sometimes called, overloaded in
05:08 sense that, like in the first on this slide this is a plus
05:15 and that the surplus operator is applied every, um, corresponding pairs off
05:25 off a M B. So it's if you want to add,
05:29 two matrices, it's sufficient just to the name of the two matrices with
05:35 plus sign in between on the corresponding of it A and B then at
05:43 . So you don't have to write loop to make sure that all the
05:48 elements are added or subtracted. So is the notion of this very syntax
05:55 a language is that operators than can to entire race or segments ovary,
06:02 upon how you define things, transposed to use a symbol in Apostol
06:11 , a prime or apple strove ISS the transport of A. And then
06:16 are functions thio computing inverse of a by calling this I M D function
06:24 similar, there is another function for the determinant of a on extracting for
06:32 a diagonal of the area A. that's something we want to do in
06:37 convenient. So this is just examples a few of them, uh,
06:42 that are often used when using map or doing linear algebra operation simply,
06:53 , so this is somewhat special function far as I'm concerned. And that's
07:01 magic function that does some magic things the sense that for the magic it
07:09 a matrix where those sums, arms and some of the agonal elements
07:15 all Zames. So if you look the upper example of Magic three,
07:23 , the Generous and the Matrix and look at the first draw, it's
07:27 plus one plus six, which is . And you can also look at
07:30 first column. It just a plus , which is 11 plus forward.
07:33 15 again for that diagonal. it is also used in the scene
07:38 is 15, so I don't But maybe that's useful for something.
07:44 this since they created dysfunction. The thing that this, like shows,
07:51 the use off these dots proceeding an . So on the bottom half of
08:01 sliders shows that a, um, where you're open to the power of
08:09 , but it's an element wise, , operation on a sor every element
08:16 a get squared, as supposed to eight times eight. How is the
08:24 operator any useful? I honestly don't . I am never used it,
08:32 I don't know who is used but, um, they make you
08:38 out of it typically. So that's I inform you about it. But
08:43 don't know anyone that figures out where useful for Please pick up or let
08:48 know later on. It will be . So here's the difference between using
09:00 dot in front, off on And that's particularly obviously useful when it
09:07 to Uh huh, the operations of division or exponentially ation plus and minus
09:16 inherently our element wise. So that's no dot needed confront of those operators
09:27 then the logical operators are also there equal investor equal etcetera. So there's
09:36 their returns and whether true or whether the condition is true or
09:43 So this is something no particular And during this, since, basically
09:52 question with three is greater equal to one of the numbers. 12345 It's
09:57 array Tripplett notation in principle, but strikers submitted, so that means the
10:06 array is 12345 Um, And then the question. So for three years
10:14 than 12 or equal 12 and But it's not greater than four
10:20 So this is what and the result . So the whole DeRay gets
10:28 and the result is them again and true or false, Um, and
10:35 slide there's a little bit e Tricky in the sense together. These
10:43 already operations and how the Ami and functions operates on the rays.
10:55 uh, it says here that for a less recall Toby, when A
11:04 B are these two, Major sees operates Collins voice. And then the
11:15 , you know, works as if wasn't or so it's any off whether
11:19 condition is true for any of the and their respective columns. So we
11:28 see in this case. So to your the upper left hand corner elements
11:34 for a it's zero point for seven . And for B, it's
11:40 So the element of A is obviously smaller than that corresponding element of
11:46 But it is true for the lower hand corner elements. So that's why
11:51 column one year gap. Ah, the condition is true in the sense
11:57 any off the paradise comparisons is and it's not. It's a look
12:03 the second column. They're all is , the equivalent of an end
12:11 So obviously, since as I just through the first column, that means
12:17 not true for all terrorized elements off M B in neither the first nor
12:25 second column. So those are things of useful as a very expressions,
12:33 okay, definition is important. Then is no, I think different than
12:42 of the other programming language that you're with. There is in control statements
12:46 do in conditional, um, um so then loose and says
12:57 So I guess, um this, , iss about the logic operators and
13:08 can not you that I wanted thio to And this is one where I
13:17 , um, find it a bit on, but needs to be very
13:23 and understanding how lisa, um, expressions are evaluated people. So there
13:37 the case n, b, d, or four cases where for
13:43 X values. And the question kind is than what will be the outcome
13:50 what off running through this statement sequence statement for the different X values.
14:01 , um, if we look at first expressions as this x between zero
14:11 10 than the first statement is otherwise it's between 10 and 14,
14:18 you do the second condition. if none of these two years
14:24 then why should be 500 and One can go through the exercise for
14:32 , C and D. So now actually happens? I think I'm
14:39 Um, now that unfortunately, not way, um so let's see it
14:54 way I talked through it because, is that if first test that
15:02 whether access between zero and 10 which one is not then they would drop
15:09 of that they will go to the time, will drop out of that
15:12 then would end up with the last survive. One would expect to be
15:16 but it's not. So what? actually the true up Put for the
15:23 , lad. Code for this is shown us output. So the question
15:31 ? How come this makes sense? I think on the bottom of this
15:40 . Um, things are evaluated, it said at the bottom of the
15:46 here, that off the two, in an condition and liking where the
15:55 between zero and 10, the two operators are evaluated separately. So as
16:06 says on the banner on the And then it's a question whether,
16:11 , any of these conditions is And if any of the expressions is
16:18 than the conditional terms to as supposed false which iwas when I described
16:28 so so here is really walked how are evaluated. So if they do
16:38 , then found this would be the way, I would say, But
16:45 is not what, uh, again have a laptop math lab, does
16:53 ? So that's one thing to be conscious off how this kind of
16:58 um, operators indeed. So I would encourage want to to make sure
17:08 you get the results that you want it pretty much explicitly enforce the value
17:17 by doing them separately and then doing end, or or depending upon what
17:23 like they have come to be. then again, serious that kind of
17:28 loop have while expressions. And there's I think particular about that that is
17:39 to attack four loops, nothing you a swell, uh, there
17:50 There's three different file types that math uses that one should be.
18:00 So there's dot m dot matt on the 18 on that files. So
18:09 dot M files are the ones that scripts or functions on that in that
18:18 . Interprets and uses, um, versions off the files are the sort
18:28 Matt files Andi data in whatever form is, made the exported and were
18:35 and stock the teeth files. So think it may be, uh,
18:45 pointed out by ice traditional saying his . He may have least I think
18:51 of them and maybe it off mad And what the shots, the other
19:00 I think this may be in the few things, and they're not.
19:05 a few examples here all how you form up things for this place.
19:10 this is not defining data type, it is, uh, ways to
19:16 how you want things to appear when are displayed. So it can be
19:22 long, or you can have the or exponential based representation, and the
19:32 option is that sort of. My has some rules for a designing what
19:37 think is you want. So it it something that may not be to
19:42 liking. So you may want to fun of them or, UM,
19:49 format or control formats, short lung it's financial notation or rational. Then
19:59 started. If it's just an example of your strings, they can look
20:04 nothing, nothing in particular unique about . They're also functions for converting things
20:14 numbers and strings are illustrated on and resulting non point numbers are integers
20:25 . It may be useful in some , and it's a normal when that
20:31 also find that most programming languages harder define exact prince for months on
20:41 Hobson was an example. Slave. not nothing in particular. I don't
20:47 unique. That's a woman already know . So yeah, well, think
20:55 I don't know if so, there's something about it, but otherwise
21:01 the slide so you can look at you can look at. So this
21:07 just random errors. I said, you do that Houston toe pray interpreted
21:14 . Oh, math lab. Not does it tell you when you write
21:18 that doesn't make sense from at or sometimes it's also give you suggestions
21:23 terms of trying to correct an expression , at least when the syntax is
21:29 . So it has some helpful support fixing simple typos. And I think
21:40 was what I wanted to say about lab and accepting this slide deck.
21:45 also well, he says somewhere about have a number of examples that I
21:51 you to try to dio use, , play around with on your
21:56 And there is, you know, a dozen exercises form or here that
22:03 can play with and see what my does with these expressions or commands
22:11 With that, I will stop and questions, and I will stop sharing
22:17 . So suggestion presents. It's Matt ever used on production equipment. Or
22:26 it just testing? Only thing it like it's like testing only thing or
22:31 , people used it a lot, from my personal view of it is
22:44 it is a very useful advanced calculator has a lot s o is very
22:54 used again for yeah, yes, up to me what I would say
23:04 and a lot off the tool packages extensive is used in bioinformatics or signal
23:11 , where people, you know in in array and it has mapped Lab
23:16 very nice functions for then extracting useful for serious of data when it comes
23:25 other usage that is kind of close my own personal background or history and
23:31 computing than people tend to use. packages, I would say, for
23:39 differential, partial differential equations or doing , or even doing symbolic computing,
23:47 you can do in that lab. , uh, so there's Salam.
23:54 are quite extensive packages for for large problems, and they're not then using
24:02 code but to use compiled code. I intend to be considered amore efficient
24:08 math, uh, or kind of , I would say to try to
24:19 their codes or functions that they and even now I wouldn't say that
24:28 I wouldn't recommend using math lab for personally because it's not that it doesn't
24:34 . But for most instances, it's really optimized for parallels use. So
24:41 can be incredibly slow, which many noticed. So in that case off
24:49 , well, here's some other packages there are just to pick if you
24:56 called Let's See That again. It's free software package that is produced by
25:01 are gone that you probably like to . There is another group nag Numerical
25:07 group. There is also much more on, uh, solemnly. So
25:15 some sense, hard is their own but large scale problems that requires sort
25:24 recently size clusters to solve mhm Matlin extensively used to. But it's,
25:43 think, most people that use my , they use it on there single
25:47 or server, and don't necessarily use parallel versions of metal. Uh
26:03 Okay, so that's what you want . It's so everyone can see my
26:11 now. Okay, so just finishing the demo, I started last
26:22 so we saw Thio vectors last Just quick revision was variable assignments conditional
26:32 control structures, Luke vectors were That's still here. So today is just
26:41 from there so quickly going through some operations. So the first statement
26:48 As you can see, it's one off initializing a matrix and Matt
26:55 So initializing a matrix requires this uh, square bracket, uh,
27:03 . And as a matter of you define one a rule using elements
27:10 by either space or commas. And you define next unusual by separating the
27:17 using semi colors. So in this , when you run the script,
27:22 will get a as a four by . Matron's similar to vectors. You
27:29 also, uh, but from transport the Matrix by using the apostrophe operator
27:35 this case, the transpose will have transport off Imitrex, which will be
27:41 fight by four matrix. Again, like vectors. You can also use
27:47 Thio, uh, 0.2 different elements the in Santa metrics. So here
27:55 first index will be in the X , and second will be in the
28:00 directions off, third row and fourth in this case inside. Okay,
28:05 that's cargo and four problems. So six. So you get success the
28:11 for that, uh, then picking Scott sets from them from the Matrix
28:18 the Miller Victor here. In this , what I'm doing is using the
28:25 operator, which means he select all Rose. And then in the second
28:30 , I only fit columns from doing trick. So that's just a 2nd
28:36 3rd column from a So in this , this family, this column and
28:42 column. So that's, uh, have fought by two measures. You
28:49 just switch, switch that switch those and in the statement, What?
28:55 here doing this just picking up called one and two. So that's just
29:01 rows here on all the columns by the colon operator. So that's a
29:07 by five majors. That again, , just using just an asterisk here
29:16 will perform a matrix multiplication. So that case, your matrix shapes needs
29:22 be compatible. So here A and four by five and five by four
29:28 off matrix multiplication with Sultana four by matrix output. That's the Matrix
29:37 And then by using a period and as a stress operator. So that's
29:43 element wise multiplication. So in that , what you get is just an
29:48 wise multiplication off. I gave it . So that's just basically that in
29:54 kind of square element wise, mad also provides you with some inbuilt functions
30:02 calculating the inverse off the matrices eso you find another matrix A two.
30:09 can use the inverse function to calculate inverse use the determinant function to call
30:17 determinant of the matrix on instead off matrices by hand like this If you
30:25 to define larger matrices, you can use in bed function like zeros
30:30 define a initialized matrix matrix with all elemental zeros. So in this
30:37 if you just provide one dimension, Matlack will initialize the square metrics off
30:42 particular dimension. So in this case will be a three by three
30:45 Here you can provide multiple dimensions like as well. So every year,
30:51 by three matrix with all zeros in , you can define the midgets with
30:56 one's in it and we start just the slides. You can also use
31:00 random function to define matrix with values the random values. So these are
31:08 distributed randomly values and the interval is 0 to 1. So anybody use
31:14 unknown function, it's gonna be there be any negative values, so it's
31:19 be fun. So any questions from script E shows on on the tabs
31:35 . These air dot M files, ? Yes. These are taught and
31:39 . You can also change the extension dot Matt. I believe that's pretty
31:44 the same thing on a zone. comment to the previous question about Matt
31:50 uses. The one thing that came mind after I answer was that one
31:56 lab allows you to you easily import math lab lots of different file
32:02 So if you have data from some or some other program, uh,
32:09 want to do some additional analysis off for which there a nice math lab
32:14 you can quite easily, um, , right? You can. There
32:21 functions that you can use to basically data from huge askey files and just
32:28 all that data into matrices. And you can work on those mattresses.
32:33 I didn't put an example for e . Sorry. Uh, all
32:41 So moving onto the next one, , uh, since pretty much Everyone
32:47 works uses any programming languages you used defining functions, performed some complex
32:54 So here's how you can define functions Medlab. So this would be the
33:01 when you're trying to define a so it starts with the keyword
33:06 Then you need to provide the return that that will hold three output.
33:13 , uh when the function returns from it's called, then function name
33:19 then the parameter list inside the And then you can do all sorts
33:26 computations inside that function on. Once done, you have to use the
33:31 . Uh, Zel natures. That definition is finished. Uh, just
33:37 important note that in math lab, the function definitions they need to be
33:44 the end off the mat lab If you have any other,
33:49 statements after the function definition, Matt will give you an error, saying
33:55 you need to have definitions at the . So just calling the functions is
34:04 like any other programming language. You it, using the parenthesis syntax and
34:08 your parameters in it. If you to have multiple return values, you
34:14 the square bracket notation on. when defining the function, you also
34:20 square bracket syntax. It's not necessary the variable names, uh, in
34:28 function definition and the place where you calling it needs to be the
34:33 It just so happens that in my , those who have those names are
34:36 you can have a different countries. questions about the functions? It's not
34:49 one last example. It's sort of extra thing. Eso mad lib also
34:56 you to solve algebraic equations so you use. You can use the functions
35:04 thio. Just pass l geometric equation a parameter and that level provide you
35:12 solution for it. To do that , you need to define symbols that
35:18 would need in your you'll be using your equations. So in this case
35:23 was X, and we used the word seems to find it, and
35:28 just call Saul function on it to the solution, and you can provide
35:34 some higher, higher a evacuations Get a solution. In that
35:40 you will get the roots for You also calculate differentiation for for a given
35:50 , so in this case. This the function that I define using f
35:54 then just call the diff function that the difference differentiation off that function.
36:01 in this case, this is the . And once you have the
36:05 you can, uh, put in , uh, any parameter or a
36:09 space off values 40 and sort of cater for many of their operations.
36:16 this is symbolic differentiation. So you the new equation on. Similarly,
36:25 can also provide. You can also compute the integration off any,
36:31 it's symbolic equations by just using the uh, function. So in here
36:38 not in dangerous. You may be with using other programming language. It
36:43 for integration case off math lab. you do that, you get the
36:48 of those two functions. That's pretty what I had. Um hmm.
36:59 see if their questions. And then , yes. Give some Okay
37:04 see if you can comment on something . But maybe students have questions.
37:15 you Sorry. Go ahead. When integrating, Um, and you have
37:21 different variables in there. Um, do you indicate which one you'd like
37:26 integrate with respect Thio. Right? I think these functions also have a
37:34 parameter When you try Thio much sure for integral or different situation. But
37:41 do recall it was used for the function. So in this case,
37:47 just provide a second parameter as a name that you want to solve it
37:55 . I don't have a good answer you in terms of differentiation or
37:59 yet find that out, you Yeah, I'm quite certain about this
38:05 so you can just pass it as parameter. But I'll find out about
38:13 . I was also questioned about explaining the differentiation works. I don't know
38:22 you want to do it and what need to do it. I
38:31 eso lots of questions. So So a symbolic differentiation. So if you
38:40 at the equation that so your shots the slide that f equals three t
38:46 plus two t divided by T Yes, right on. And what
38:55 diff function does is symbolically do what would hopefully Dubai pencil and paper.
39:03 you want to do it, it a derivative symbolically on the first
39:06 and I detected everybody about three times squared We respect to the variable T
39:17 , uh makes you remember the math how to differentiate the power of
39:22 The exponents comes down and then the gets decreased by one. So the
39:31 derivative off three t squared is three to for the exponents that came down
39:38 t. So if you look on left hand side, the first term
39:43 the differentiated expression is three times to is six times team and similar,
39:49 does the same differentiation on the second . Yes, following the normal math
40:00 , can the integration function be used definite integration? Good question. I
40:11 think I think it's just again strictly in function is symbolic. There are
40:20 things I'll talk about in in a lectures that that was an American integration
40:26 expressions. So now whether you have bounce on the symbolic ones, what
40:36 does, I do not know. maybe we should try to find out
40:40 next lecture. Good question. And the other question mhm found
41:07 Keep your screen e thought there were questions. No, but I had
41:15 or comments or see if you So the one thing I thought might
41:20 useful. Also the comment on some the kind of functions that you see
41:29 the header off the display. You , the fact that meth lab sees
41:37 is that they can easily grab stuff what debugging functions, like great points
41:45 timing functions, I think are also available if you want to tie me
41:54 . So for for timing, it's very simple. You just use the
42:03 off keywords taking talk. Yes, that gives you the total time off
42:12 total run time off your script. you can even put it for different
42:17 as well. Just the combination of targets here took a long time.
42:25 , in terms, off break To be honest, I have never
42:29 used them. Uh, mostly dealt smaller scripts, so, uh,
42:35 yeah, there should be much complicated use you just right. You just
42:45 on the statement where you want to great points and then go to this
42:50 point of and use the set set clear button on. That puts a
42:56 point there on then. When you that theory, execution stops at That's
43:03 point. And then remember one? , yeah. Mhm. Monta.
43:14 , this one's not really relevant, you'll find out more commands. But
43:18 you can use in the during the debugging session Yeah, I remember myself
43:28 an earlier version of this class of around with both break points, and
43:33 the called Run and step on. can run in time and it gives
43:37 the timing. Uh huh. Without , Remember explicit to say, putting
43:44 timing statement for segments of cold? . Give me the whole thing.
43:49 are certain convenient services that they provide functions for who's I think running time
44:01 give you the time without those. , if you use the running
44:07 But rather than using safe run, sort of giving my breakdown off.
44:13 ? How much time? Yeah, of a provider. Services.
44:21 yeah. So yes, many nights . Seems support the beginning as
44:37 And the other questions on that Yeah, as Josh knows in my
44:57 the research are professional interest performance is instrument, and timing is an important
45:02 of understanding that part. So I in some one or two of the
45:10 you will be. I don't remember it's in the first assignment or some
45:14 assignment, but sometimes during somewhere along among the assignments for the course,
45:19 will Probably asked. They asked the something off? No, I didn't
45:30 any more questions from comments. let's take over. OK,
45:38 Um, there's a question and chat the recording. So yes, recordings
45:48 be available on video points dot old , absolutely. Mhm. And all
46:00 previous to lectures there are already available . So, uh, and it
46:10 records it in an internal, their format. And then when it's all
46:16 and done, it gets converted to four, which takes a little bit
46:20 time. So uh huh. But , sometimes before the end of the
46:28 of the lecture, the video will the video points the torque website.
46:40 see. All right, so it's normal questions than I will talk
46:50 The subjects are on the list in . Air analysis, Onus Rule and
46:54 serious. So air analysis is a dry topic but always give you a
47:05 of it and left in America, that is calls backward error analysis.
47:14 the examples are very complicated. If do it for complex problems, it's
47:19 difficult, but we won't do that this introductory course, so I'll just
47:25 kind of the principles behind what this area analysis, what it means and
47:31 it works. Then I'll start to about Paulino meals and three particular aspects
47:38 pulling all meals. One is known Horner's algorithm. Italian McLaurin Serious?
47:46 believe most of you have heard or them before about maybe you forgot about
47:54 , Andi. So I will remind about them now. So here is
48:02 a little bit of society Baptist Air that onto us in order to try
48:07 figure out what happens. And in first lecture, I kind of but
48:12 in one way by talking about loss position that happens when you kind of
48:20 . For instance, when you subtract that are almost the same, so
48:24 when they fixed number of digits in representation, that means that the leading
48:30 may be the same, so that you kind of end up losing position
48:36 the sense that after the subtraction you fewer number. They just stopped
48:41 No, are correct. So for error analysis, using relative error to
48:52 what happens and the notion that is used that, um, a letter
48:59 Z on this particular slide is a number that you want Thio have represented
49:11 what's known as, well, fl floating point, in this case,
49:16 representation. All the variables E then exactly the, but it has a
49:21 error of Delta. So this is of what the first equation says on
49:26 slide and then on you can figure , and they manipulate that equation and
49:34 out Delta, and then you get the relative error. And that's
49:41 at most in magnitude, that most to the machine Precision Epsilon. And
49:48 there's just simply plugging in some numbers see what happened in one case,
49:54 you around the number with, I 10 decimal digits of five and you
50:01 around it. And what the both and relative there is no, it
50:09 that the backward analysis is then trying figure out Walked, um, changes
50:19 alterations if the input put, in , generate the exact protective gaps.
50:26 that's what it's over taking what you and try Thio. Go back to
50:31 input and figure out how much the could have changed or varied for this
50:38 outcome. It gives you a little of it. Interval space for what
50:46 variables keeps you the same are put the position that you do have.
50:53 then I think on the next few , I have some examples.
50:59 so the first example is just taking machine represented Numbers are X plus Y
51:08 Z, um, are assumed to correct, or just figure out the
51:15 of doing arithmetic on these numbers. the first thing that you do is
51:25 with the normal left president's order. you have to add X and
51:30 and that may not be exactly And the machine. So there is
51:36 relative error in computing that I called the one So again, fl of
51:45 . Why is and machine number that or becomes the result of doing the
51:53 Operation on X and Y And if do things in Tripoli, single
52:00 We know that the machine Epsilon is to the 24 23 bits Mantis
52:07 But then there was his hidden on That's What. But it's again less
52:15 one in the following bit that follows the 23 bits, and then it's
52:23 , correctly rounded than the error is than the machine Epsom divided by two
52:31 on The next thing was to take machine number, the output of the
52:36 , correctly rounded and multiplied by And then we again potentially get.
52:42 there that it's in label Delta to relative error that is also off the
52:49 magnitude as the previous operation again bounded machine. Excellent. And then it
52:57 unplug it all in together. And what? You would see that,
53:01 fact, the end result is that off. There's a risk that the
53:09 incurred in each one of the operations accumulating. So in that sense,
53:15 the evaluation z Times X plus, the error is larger than what is
53:24 by the machine precision. So that's when you have large number of calculations
53:30 numbers. Uh, error may propagate get magnified. And again the And
53:40 is, I think, a little now I'm doing it more somewhat
53:45 Were first to get an error and machine representation, and then you get
53:50 errors in terms of doing arithmetic on machine representation. And if you play
53:56 with this numbers, you got something this case up to unfortunately, the
54:03 error may not be possible to down experts why if these numbers are almost
54:11 same But why you sort off say negative of X, then the X
54:18 y ends up being a number very to zero. Hopefully not zero because
54:25 then clearly the relative error in Kambia really larger as relative to the true
54:34 of experts wife, Right, So thing. And these are just plugging
54:40 some numbers off the consequences can be just showing up, even when
54:46 in this case, five decimal digits . Then if you go through the
54:53 , they will discover that even, that's something you would assume. Five
54:57 a position will give you the pretty results, but in this case,
55:01 this particular numbers. It turns out the results is potentially wrong with up
55:08 10%. So again, it's against of significance and lots of position.
55:17 that's why, in some competitions when do, for instance, summations are
55:23 , long sequence of numbers. It fun knows those numbers than the worst
55:32 you can do is kind of add large and a small number because on
55:37 may lose precision very quickly. So that case, you tried to first
55:43 relatively small numbers together, so or them so they kind of build up
55:49 become comparable to the larger numbers. that case, you get in the
55:54 some better position, but many times obviously may not know ones that come
56:00 . The values are, and you not be practical to try. Thio
56:05 such a principle. So that's what had about. Air propagation are backward
56:13 analysis. It's just to again make wear, or what may happen with
56:23 are rounded or truncated, or just find it. Representation in the machine
56:34 those are very again generic and important be aware of, So any questions
56:47 that. Otherwise I will know kind switch topic to talk about pulling no
56:58 on the question comes to mind. free to interrupt, so I will
57:03 . So what's the first couple of ? Simply just trying to tell you
57:08 polynomial czar important and very useful. they're useful in a bunch of different
57:16 . So one is interpolation and hopefully concept that's familiar. But it's basically
57:26 toe figure out what values the variable have between observations and for this particular
57:36 you may have made. So in case, there's kind of a table
57:40 X and my values that shows for for the collection of X values.
57:45 the corresponding by value waas, whether temperature or pressure or whatever experiment was
57:51 made. And then 1 may want try to figure out or estimate
58:00 say, a value why value would for the next value. That wasn't
58:04 of the observation sequence, and that's you can then try to fit Paula
58:11 to the measurement values you do have then use that polynomial thio because that's
58:18 for all the different text values and that plug it into the polynomial for
58:24 X value you're interested in and The outcome of the polynomial evaluation ist
58:29 estimate of what So interpellation is something pulling all males shows up as the
58:40 efficient or convenient way off. No or estimating values that you don't have
58:50 or computed another one is like and to find surface descriptions on computer
59:01 Poorly known effects extensively Used to try define surfaces in this case is quite
59:08 service because we're normal is degree, , but you can have whatever degree
59:13 pulling over all your likes. Thio , um, the proper representation of
59:19 surface that you have, um, authority kind of Well, the third
59:29 a third, uh, type of to polynomial XYZ if you have that
59:37 complex functions that I put on the of this light, that vessel functions
59:42 looks kind of messy, and many the things may not be so clear
59:46 they mean like gamma functions. you know, exponential Ximena science trick
59:53 and, um so this is not easy evaluation, and you may want
60:00 have something more simple that may be enough for the sub domain in which
60:09 special function is defined. So on bomb that just shows the polynomial that
60:13 a decent job in terms of representing vessel function on a limited interval.
60:21 it just shows up. I think agrees that's the bottom half is
60:28 more intuitive or simple to evaluate. that's not fun anyway. So this
60:34 just try to motivate you to, , pay attention and say that Paul
60:40 is something that is useful, and good to know how they were.
60:48 I'll talk about this. Horner's rule is used for economic evaluation and manipulation
60:55 Colonna wheels. So here is now of generic calling normal off an end
61:03 . Paula Normal on that means the Power X, including this polynomial,
61:11 the end power off the Variable And then there's a whole coefficients not
61:19 have for the various powers of This question. So this is just
61:24 basic storm of a polynomial. So of the things that's just coming in
61:34 book is how you, you carry out evaluation of pollen normal
61:43 That's it useful thing to know. the question is, how many operations
61:49 it take to do this evaluation? so the first thing is that we
61:59 the M plus one term. So it requires. In addition,
62:06 add this and plus one terms. there's also multiplication is involved. So
62:14 you do is straightforward evaluation on this . How many multiplication is does it
62:23 ? Have any volunteer? Well, you look at the first time is
62:33 it doesn't have any is just single number. The next time a one
62:41 has multiplication, a one needs to X. Then we go to the
62:48 term. Uh, and then there's time a to times X squared.
62:57 means we have to multiplication 82 times and X times X. So as
63:05 progress from left to right, then each term there is progressively more most
63:13 to carry out. So simply this what ends up being the case right
63:21 . There is, uh, the off applications for the terms forms in
63:31 . Serious? Hopefully remember, if some of the terms of another
63:38 then you'll get an expression like an and plus 1/2 sen number. That's
63:45 total sum off operations in the Serious. So doing this. It's
63:54 against and traditions and kind of end multiplication. So this is not particularly
64:09 . So any suggestions for how you they do it more efficiently?
64:27 um, so this is for So here's what you know, I
64:34 dynamic programming right for it. that's kind of overkill. But
64:41 in principle, this expression latricia it's kind of a dynamic programming
64:48 if you like. It's kind of nested evaluation, uh, so by
64:56 this nested evaluation for each parenthesis, is, basically is to operations one
65:04 and add. And that's just start the animals and go towards the
65:10 There's always kind of one Muslim woman and unraveling. They nested,
65:19 for emphasis, and in some ways dynamic programming does domestic recourse of
65:26 So yes, um, I'm just it's overkill in the sense that dynamic
65:35 may be perceived as the complex But hopefully the nesting off thes expressions
65:46 simple. So this is in terms the polynomial evaluation is known as Theis
65:52 Rule or foreigners algorithm. There's also call it synthetic division. That makes
66:01 at some future. Lecture by that may be used sometimes. So in
66:10 case, yes, thank you know all. This is the remark I
66:14 to do, though, since many you are computer scientists and the miracle
66:21 traditionally, when they look at whether are competition efficient, they tend to
66:31 on arithmetic. Operations on many algorithms been focused on minimizing the number of
66:39 athletic operations. That's not necessarily a thing that modern computer systems tends.
66:47 not be limited by arithmetic operations, , um, by memory operations.
66:55 just a little bit there, I . Alert that, Yes, it's
67:02 to the conscientious about arithmetic operations and to keep it down if nothing
67:08 as I just pointed out earlier for propagation, is because, um,
67:12 operations you do. It does have and I kind of impact on
67:21 So it's good thing to minimize for kinds of reasons, but it may
67:26 be directly reflected in execution. Times whatever competitions they're doing Warriors s.
67:40 I think next I have some simply all it works. Um,
67:47 this is just taking a simple Poland writing it in terms of this nested
67:56 . And there's just a simple How you can do they can book
68:02 tried to give cover, sort of aspects off the algorithms it talks
68:08 So and the spirit being consistent. in the book? I also put
68:15 surgical's in the slides. Um, , yeah, Horner's rule. He
68:30 useful in doing something that is called , which is essentially thio pull it
68:39 , factors off a polynomial and get remainder plus the polynomial or one degree
68:49 than the original polynomial zahn These kids polynomial p that was given as an
68:57 polynomial. And after this, factoring on ex miners are we get the
69:04 que that it's not off degree and one. So no, I think
69:14 the next time I will show hard and use this phone is ruled to
69:19 determine what to is and what the piece. Also, that what I
69:27 to point out with the slide so and try to evaluate, um,
69:35 World P, uh are then um the value of P at our
69:43 the remainder in this factoring out off term ex miners are and that I
69:50 use in some of the examples to hunt can be used for polynomial evaluation
69:57 of the direct, uh, method be overkill. I'm just using the
70:03 foreign schema. But there are other where this testing or deficient process turns
70:10 to be a useful way of doing . So horn is ruled it
70:17 So here's kind of a scheme on is kind of nice if you do
70:20 by and most of the time you're wouldn't for simple expressions that might still
70:26 useful. So this game I is you're right down there coefficients and the
70:37 polynomial p starting with the coefficient for highest or the term and the polynomial
70:45 then, from left to right, successively well, coefficients for the success
70:51 the lower over the terms off the of X and the polynomial. Then
70:57 have a second goal where you have the front the variable of value are
71:07 for the term you want for the , you want to extract out of
71:11 people in all male. And then schema works by something things and columns
71:21 they go from left to right. you do it successively from left to
71:27 . And then when you go to subsequent column multiplying the result from the
71:34 column with our in this case, right, for the term you want
71:41 factor out. And then you keep the terms and repeating this process until
71:47 get to the very end to the . So then, in fact,
71:54 have no started the coefficients in a polling normal as at the bottom of
72:03 simple schema on, then, yeah, you can dio identification of
72:12 and this is very simple procedure to with them. My cold.
72:20 And the other part is that the time B minus one, as is
72:27 here, is simply the remainder So here is now a couple of
72:35 examples. I believe I have so us to take this porno mill.
72:43 then I was written with the highest term from the left, and l
72:47 was toward the right, and the is clearly one minus four plus seven
72:54 five and minus two. And if want to evaluate the polynomial at four
72:59 equals three damages three instead of ours the symbol on the previous slide.
73:06 then we go through this thing. we have the first column, and
73:09 just the summation off one place, is one. Then the next thing
73:17 to multiply the outcome on the first the first column, which was one
73:23 three. So that's ends up being in the second role, and
73:27 you add minus four and three and Mine is one, and then you
73:31 the minus one and multiply it by again, and you get minus three
73:35 such exception. Then in the you get 19 as a value on
73:40 polynomial in this case, and you write down if factored on deflated polynomial
73:50 as ex ministry. And then you the coefficients directly from, um,
73:58 sort of bottom roll off this little or schema that is used and clearly
74:05 you plug in P equals three and deflated toe polynomial than the first X
74:13 three become zero. So clearly Mr Results. And if you're like
74:20 suspicious. Okay, fine. I also do that. Very direct
74:27 Yes. Plugging in three instead of in the original pulling. No.
74:32 . Yes, you'll find out. fact, the procedure getting the correct
74:36 , um um And this is just similar thing and just plugging in to
74:46 to value that. So instead of . And then it turns out that
74:50 reminder is, in fact zero. that means to our ex minister is
74:57 exact factor off the pollen normals. this case, the polling normal p
75:03 be factored into to pull enormous the degree, one with X minus
75:09 And the third degree one That is of the Cuba in this particular
75:16 Um, so this is again Okay, any questions or comments on
75:23 ? Before, I used to you and used Horner's rule in a slightly
75:30 complicated situation. Okay, so sometimes also want to evaluate derivatives are not
75:48 Nepali normal itself, but the derivative the polynomial. And so again,
75:54 you use this deflation process to kind factor out the term X minus or
76:00 factor. Ex miners are on that derivative. What we get that's the
76:07 off P s Que Relax. just use the, um They call
76:17 them rule for doing the relatives of production. Take the derivative of the
76:27 one times the second one, and you take the first one times the
76:31 of the second one. Um, if you take the derivative of explain
76:37 our Times Cube, the first thing get this again the derivative of explain
76:42 our is just simply want So you Q X and then you have next
76:49 is our times the derivative of So that's the second tournament Later that
76:55 see, for P prime p of is a constance of the derivative of
77:00 is zero. Then we can also that she want to evaluate the derivative
77:07 Piot, Or then it's simply to our. So this is one way
77:15 can also then go through and use process first, do the deflation of
77:25 and then repeated for Q and then Cuba again, the value are for
77:34 and then Yeah, Excuse me. you have the derivative. So now
77:42 here written out expression for s as . Then follow me over with coefficients
77:49 sees. So here is just the first step that symbolically, that already
77:56 . You got the coefficients of Q that is the bees. And then
78:03 use those bees. Thio Yeah, coefficients off the s polynomial on.
78:13 just the same Horner's schema again. then you have an expression for the
78:21 . P at next equals hard. the remainder term on, then I
78:33 I may have a concrete example for to do this. That was the
78:37 step. Thinks the same expression as . You recognize all the numbers on
78:44 ? Now we take, um those coefficients and then computer s polynomial at
78:53 bottom. And then we get the the term that it's a derivative of
79:01 people in normal at X Equal Yeah, So when there's just the
79:09 writing down on the various polling almost p and the Cuba and the S
79:14 and plugging in the value three and 37 and, um, you can
79:23 has me not trusting anything, double everything you take the formal symbolic derivative
79:28 P uh, the phenomenal tea and using the standard rules for the revision
79:36 get, Um, the expression you , the derivative X four is four
79:45 x three etcetera. And then you just plug in X in this
79:49 and then you get the correct number that my time is optical into my
79:56 here. So let's see if I one more sliding or if it's there's
80:00 for it. And I think that I guess a good stopping point
80:06 So that was about tornadoes rule for polynomial in their basic form and also
80:17 , uh, evaluating derivatives. And can compete repeating it to the higher
80:22 derivatives, obviously. So it's nothing and stopping at the first tree with
80:29 . So next time I will start talk about serious expansions in the form
80:34 Taylor and McClure and serious. But time is up for today? So
80:39 will end there today on will take . Yes, there are any
80:50 um, professor, I have a regarding to the last example.
80:57 Okay. So, um, there the the expression the first derivative with
81:06 to our equal to kill are so that a gift? Is that a
81:12 function or, um, how do do I they derive this one?
81:21 let me see if, um, can explain the question. What?
81:32 . Okay, so let me go this slide first, right? So
81:40 , so we haven't polynomial p to with. I was given to us
81:47 and then using this deflation idea to out ex miners are, uh,
81:59 gout, formerly an expression that is towards the top of this slide.
82:07 mine is our times and other polling . You reckless Pete. Um and
82:15 we need So this is symbolically sewn America. We need to put the
82:20 for our but symbolically, we have in this case, and symbolically
82:25 If X happens to be our in case, the X minus are turns
82:31 zero. So then so if we an expression for this factor symbolic
82:41 then we know that the reminder uh, is equal to the value
82:49 p for X equals R. So that's why these things up now,
83:00 were actually wanted the derivative. We to take a derivative of this
83:08 And then we have a new equation symbolic representation of the derivative off P
83:16 that is just following the change rule what? I was trying to find
83:21 word for last time in taking a of this expression and following the change
83:28 than the derivative, the pollen normal is of this form. Now then
83:40 want to have the same ideas would for P to find out in expression
83:51 that when we plug in Trump X to our into this p prime
84:00 The remainder in that expression is in the prime of art. And that's
84:09 we move on, then to try , because if you plug in X
84:14 , there are in this symbolic expression P prime. But you see,
84:19 that in fact, p prime of is a value on cue at
84:26 And so if then go back and at the first equation here we learned
84:34 p off our is the remainder in factor expression. So if they want
84:42 find out que of our q Q at X equals R. We can
84:51 Cube like we factor p here. that's what. So if you do
84:59 , in fact, if you like on there more or less in the
85:03 of the slide here than to um what is the remain determined?
85:12 factor and from p prime equals We can see that if you plug
85:19 X equals. The are here is Cuba of our because this term is
85:26 . So it may feel a little convoluted and circular, but it's not
85:32 , but it's just following the same as they used for p toe.
85:39 use it for this expression and then be useful, we want to factor
85:47 like we did p here because that's one that to pull anomalous the one
85:53 will give us the queue of our Remainder. When we factor this expression
86:00 this way, did it help? , it's answer my question. Thank
86:11 . And then the next slide was doing it completely. So in this
86:16 , the first part is this just the coefficients for the cube polynomial.
86:24 this is what this here and then directly just use these coefficients. So
86:30 on a cube correspondent to the ace was here when dealing with P.
86:36 we're dealing with Cube. And so these are the coefficients in the queue
86:41 . And then we still want to things that three. So we use
86:45 same our value, and then we the same processes. From now,
86:50 becomes the coefficients in the S polynomial is here. And the last term
86:56 is now the remainder off to in factory. Okay, Have a quick
87:04 . Yeah. Where does 36 and comes from again? Where the number
87:10 camps from 36 and 30. Okay, so that's fine. So
87:20 Horner scheme, all right, is are a little bit Mr Line
87:24 I'm sorry for that. But the column has a one in a
87:29 So there's something, although is the then the next in the scheme,
87:35 assume multiply the result in the first went this number three. So that's
87:42 . That's ah. Result in the column, times three. And then
87:47 add minus one and three, and you get to and then um you
87:54 to, as a result, and by three. And that becomes
87:57 And you add four and six. you get Ted. Thank you.
88:02 it's the same here. We did and zero becomes one. Then we
88:07 this one. Times three. That this number. Add those to get
88:11 one. Take minus one by three we get minus three. Add those
88:16 numbers. So the scheme is exactly same. This is the coefficients off
88:21 queue, polynomial here or there. so these two rules of the things
88:30 working on to find s thank Okay. Okay. Any more
88:53 It's things comes to mind either. know, send email our bring them
88:58 next time. Wait, What chapter the book is this? This is
89:07 Jeannie Kinkaid book. Argentina is the author Kincaid, American algorithms and
89:15 It's listed on the syllabus, and think the first lecture slides. You
89:23 what chapter in the book is this ? Okay, thanks. So I
89:30 I'm sorry. Maybe that should be . Hopes for it. Yeah.
89:43 it's, I think Chapter 1.1 and . It was e don't know where
89:48 slide disappeared. I had it on slide. I'm sorry about that.
89:52 right. That's fine, Thank Yeah, I'm sure. Yes.
89:58 it's not already in this, I have just hit the slide, but
90:02 not sure it is on blackboard in slide. Back on blackboard.
90:13 Any other questions? I'm sorry about . I know. I saw the
90:25 when I looked through the slide for lectures. I don't know where it
90:35 . Or maybe activity very first. , Okay, thank you for
90:41 And so, yes, we'll post of the email about posting on the
90:46 . Yep. Okay. Thank
-
+