Chapter 1.3 - Iteration Methods: Newton Raphson

0:08 we're going to talk about iteration methods and as they are some one of the more F foundational things that we do in Computing is we do iterations is is what your computer is actually in fact best at is is essentially setting up into iteration loops and you'll see that this can solve many problems for us as we advance forward in looking at our model in data driven modeling and scientific comput computation techniques many of them are foundationally set upon

0:36 iteration schemes and so today I want to talk about iteration but also related to Newton rafson method which is one of the classic iteration schemes for finding roots of functions so let's go to it so iteration is fundamental it's one of the most common things that our computer can actually do for solving complex problem problems the computer iterates towards a solution of some form so as you'll see as we progress in this course

1:09 you'll see that iteration plays this foundational role in almost everything we do iteration also is foundationally built upon a for Loop so in other words iteration is structured so that you do four and then you would do an iteration type structure within that for Loop so what kind of things can we solve well obviously we can think think think about root solving F ofx equal Z that's what we're going to do with Newton rafson today but you can

1:36 also do things like solve ax equal to B in other words the most common linear algebra problem that you might have or even solve something like differential equations you'll find that as you time step forward in this differential equation as you advance solution in time it's fundamentally built upon an iteration scheme of sorts so almost everything we're going to do is foundationally built upon it some kind of iteration scheme because this is ultimately what you're training your

2:06 computer to do is iterate for you to get to a solution so here's the generic structure of iteration there's some function G where you put in some value of P let's call it K it's indexed by K so this is the K value of it and you put in this Ki value and out comes P of k + 1 by the way the P of K can be a vector it can be a matrix it's an input through some

2:36 function G that produces an output an updated value so that updated value is the if you have the kith value the updated value the k + one value okay and generically here's how we're going to do it you're going to take for instance an initial value like p 0 which is going to generate P1 you're going to take P1 to generate P2 P2 to generate P3 three and so forth so this is kind of the structure we're looking at in

3:05 iteration is that you just plug in values and the way you would do something like this is just simply by a for Loop for instance so some interesting things one of things that's very interesting to this is to look for fix points in these iteration schemes and this is going to be directly related for us in terms of root finding so fixed points are when you plug in a value and what comes out is the same value so you

3:31 put in P of K you go through G you get back exactly the same values that you started with in other words you've achieved what's called a fix point and in fact in many cases in Computing convergence to a fix point is actually the goal of the computation and that is the solution we are looking for so let's talk about what this might look like so here for instance is some function G of X the function here is this curve and

3:59 and this point here is where we put in a value of p and the value output value is also P so this point is very special for us it's along the line yals X in other words Y is the output X is the input is when they are equal okay and that only happens for this curve at this point right here and so we are looking for this point and trying to find it so how would we do this in some kind of

4:26 iteration scheme so let me show you some of these these iteration schemes or iteration type behaviors so what I'm giving you here is four different functions and kind of behaviors that can happen with iteration so here in this this screen here this function y ofx which you can see here I start out some value of p of0 and the output I put in P of Z to the function is P1 so to find where P1 is I bring it

4:55 back to the yal X line plug in P1 to the system this is the next Point here where my fingertip is that's where P1 is okay if I want to find what the next Val put in P1 to that function it gives me back P2 which is now here and notice What's Happening Here my values progressively as I March forward the P not P1 P2 are going to converge to this point here where the dot is so this is a

5:21 monotone convergence of this iteration scheme okay the second one over here is known as oscillatory convergence I put in p 0 I go to my Axis here and say this is where the value is but my output Y is now my P1 so I plug in P1 to the system and then my output is P2 and what happens is I'm essentially iterating around this curve and I'm going to eventually end up at this point by essentially walking around here and

5:52 getting closer and closer and closer into that point but now not in an monotone way but in an oscillatory way you can also diverge and of course this is not ideal most of the time when you're doing iterations is you would like the convergence however if you are diverging this is where you want a good if statement saying well if the value gets really large that means you're probably diverging so here is for instance this curve this G of X I plug

6:22 in p 0 the next value is P1 okay that's up here I can plug that into the function now I'm here PL it that value in to get P2 that's now out here what I'm doing is I'm moving away from this crossing point so the iteration scheme itself even though there is a fix point the fix point is what's called unstable in other words when I'm near it the iteration scheme just moves away from that point okay so that does it in a monotone

6:52 way and you can also just like above do it in an oscillatory way you can move away from this fix point so these iteration Behavior are really important for us to understand because as we go forward in Computing we want to know is are we are we you know are we going to go ahead and converge to something or are we going to diverge and those are important things to for us to understand and also under what conditions do these

7:17 things happen Okay so the most classic way to do this and by the way a lot of this we're going to just talk in detail about throughout this course because we're just introducing the first iteration scheme here which is going to be this Newton rapson but you'll see throughout that iteration becomes the center point of almost all of our scientific Computing operations as we move forward in the course so let's start off with the simplest example which is Newton

7:46 rafson which is looking for zeros of a function so here's F ofx and R which means the root I'm looking for the roots right those are the zero the values that are the roots of this function okay so the question is how would I find this in practice now in the last lecture we actually did it through bisection but new rapson was a is a much in some sense a much more commonly used technique that we that is used in practice because in

8:15 the Newton iteration or sorry in the bisection we actually had to know we had to first of all figure out the left point and the right Point first before we started the algorithm whereas Newton rafson just starts with a guess and starts to iterate towards the solution so here's how it might work there's a function I give you this is the F of xn here it is this function here that you see and I'm going to give it some guess

8:41 let's say I'm at The X of nth Point what I'm going to do from this point is I'm going to decide to get to look for the solution by taking off on the tangent at this point now the tangent takes me up to here this point x of n + one and then I can evaluate the function at that Point that's the iteration scheme you start off with a guess or you start off with a value X of N and what you're

9:08 going to do is your next guess is just going to be well what's the derivative when does the derivative hit the where the where this zero line is and ask the question am I above or below this line right and how far okay so what I'm going to do is use this as a very simple way to construct the Newton rafson scheme so so first of all what we know is that the slope is given by rise over

9:38 run okay but by the way the slope is also the derivative at this point so the derivative at this point in fact is the slope and the and the rise overrun here so look at the rise the rise goes It goes the second point is zero the first point F ofx of n right that's where I'm looking at hitting this point right here and the run is X of n + 1 - x of n so that's it that's the slope

10:04 formula and that slope is equal to the derivative at that point so all I'm doing is saying the slope is equal to the derivative which is rise over one which is this formula here and what I'm going to do now is solve for x of n + one from this and when you do this and rearrange here is your formula this is the Newton rafson scheme it says that the next point is equal to the current

10:30 Point minus the function evaluated X of N and its derivative evalu of x of n that's it so that is the Newton rsom scheme it's guaranteed to converge if you are sufficiently close it's not clear what sufficiently close means so it's one of those theorems that's not clear that it's that useful because sufficiently close means you might have to be within 10 to- 16 or it could be you're within a billion so it it doesn't say in the theorem how what sufficiently

11:02 close means really so in practice it's not a very good theorem but let's execute this on a simple example and in fact it's the example we used with bsection of the last lecture which is f ofx e the x minus Tan x so first of all I'm going to need the derivative so I can simply take the derivative of this which is e the xus secant 2 x so I have those because that is the structure we need to compute the up

11:35 update rule so here is what I have the point x of n plus one is X of n whatever I had and then this is the function evaluated X of N and it's derivative evaluative X of n so this is the iteration scheme we're going to set up we're going to write a python code for doing this for solving this transcendental the roots of this transcendental equation okay so here is where we're going to do we're going to go ahead and

11:59 write this it's as simple as this here so first of all I'm going to take a guess my guess is -4 so I guess where the zero is and I just so I guess4 and now I'm going to go into a loop and what the loop does here's the loop for J equal 1 0 to 100 the value of x is equal to so notice what I'm doing here I'm actually just coding in this line this formula right here it

12:32 says the next point is equal to what the current point is minus the value of the function over the value of the derivative and then I can plot what that value is now if that value is less than 10 and minus 5 in other words if I'm close to being zero I break out of this Loop okay okay the other thing I could do excuse me sorry so that's that's the Newton standard Newton wphs and iteration and what I'm doing here is I'm

12:59 just rewrite I'm writing over the previous values with this little structure I could keep a vector of all the values as I've iterating by doing this here this is just a different version of the same python code which is X is going to be NP a pend what that's going to do is I'm going to make an array and keep all the values that I have and so what I'm doing is instead of overwriting the previous value I'm just

13:25 adding on to my Vector so my first value is -4 the next one is the next value the next value and so forth so the NP aen command allows me to add on to this so X is NP append my previous value of x and then here this here is my Newton rafson formula the current value minus the function value over the derivative and then I write out the value of the function and then I can compute the

13:52 actual functional value and if it's less than 10 - 5 break okay so if I do this here is sort of what the iteration looks like so after only four iterations I guessed a value of -4 and then what it does is it starts Marching In and by the time it hits four iterations I'm within 10us 6 so this is a very fast way to get to this zero right and again luckily for us it actually is a converging iteration

14:24 right Newton rson is not guaranteed to converge unless you're sufficiently close so it wasn't clear if my -4 was sufficiently close but it looks like it did the trick okay and by the way this took four iterations versus when I did bsection in the last exam in the last lecture it took 13 iterations so this is a pretty efficient way to do this and a very simple code to write right I mean this is as simple as it gets right there

14:54 okay that's very few lines of code again you have access to this on the GitHub page so you can just have both these codes available to you so again what this really setting up for us is iteration schemes are going to play a huge role for us in terms of how we manipulate and solve many of our problems both in machine learning and traditional scientific Computing iteration is sort of this foundational piece it's going to sort of dictate so

15:25 many of the algorithms we're going to actually execute and practice for solving scientific problems so again you can find everything here at this website and also download the Clone that GitHub page so you'll have access to it and again iteration methods going to be foundational and now you have Newton rson which is probably the most sort kind of one of the oldest and most important in practice in many ways