Okay. Good morning, everybody. I hope you've done the quiz.
So let's just look at that and see if you got the right answers. Every square matrix has an eigenvalue decomposition false.
And the simplest example of one that doesn't. Would be that.
In other words, not every matrix is diagonal sizeable. Every matrix, rectangular or square has an SVD.
Yes, that's true. If A and these are square, etc., etc., then they have the same eigenvalues.
Yes, that's true. That's a similarity transformation. So let's see.
We have false, true, true number for a square matrix of singular if and only if it has a zero eigenvalue.
True. Number five, the singular values of an orthogonal matrix are all equal to one.
That's true. Remember, the singular values may tell you about a hyper ellipsoid.
Well, an orthogonal matrix maps a ball to a ball, so all the singular values are one.
Finally, the eigenvalues of an orthogonal matrix are all equal to one.
That's false. The eigenvalues of an orthogonal matrix have to be equal to those of its inverse.
But that could be minus one. So they're plus or minus one? Not necessarily one.
Okay. So today we begin the last bit of this term, which is about optimisation.
We've been talking about linear algebra. Now optimisation.
This is a subject that I mentioned at the beginning was one of the pillars of scientific computing.
Remember, I drew a tree in which I identified three traditional main areas of numerical analysis scientific computing.
One was linear algebra, one was differential equations, pdes odes, and the other was optimisation.
I think if anything, over the years, this one just keeps getting more and more important.
It's just an amazingly exciting, flourishing area that's everywhere in science and engineering.
Let me mention a couple of facts about optimisation that make it diverse and interesting.
One is that, of course, we're typically dealing with functions of several variables or many variables.
So optimisation is all about minimising functions of many variables.
And the other thing without which the field wouldn't be so variegated is that typically there are constraints.
So what is optimisation?
Well, it's the subject of minimising or maximising functions, typically with several or many variables and typically with constraints.
So it's minimisation and maximisation also more or less in the same domain is finding routes of functions maximisation.
So that's what optimisation is all about. Nobody ever maximises in practice you always minimise.
So if you have a if you want a maximum of something, multiply it by minus one.
The standard is always to talk about minimisation. So this is a field where there is a totally dominant, great textbook.
And that's this book by No Saddle and Right. The second edition came out nine years ago.
I think it's just a beautiful, straightforward,
knowledgeable book that talks about all the basic and a little more than basic ideas of numerical optimisation.
So there's absolutely no doubt that if you want to learn about something in this area, the place to start is with this book.
Let me pass that around. Oh, before I pass it around, let me read the first two sentences.
So it's a big, thick book, but well organised.
Don't worry. The first two paragraphs are just these little paragraphs.
The first paragraph begins People optimise.
What they mean by that is, well, let me say what they mean by that. Investors seek to create portfolios.
Da da da. Manufacturers aim for maximum efficiency.
Engineers adjust parameters to optimise performance and so on.
So people optimise. Then the second paragraph says Nature optimises.
Physical systems tend to a state of minimum energy.
The molecules in an isolated chemical system react with each other until the total potential energy of their electrons is minimised.
Rays of light follow paths that minimise their travel time.
I think that's an intellectually fascinating beginning of the book because it really is true that optimisation is
something that's both at the heart of science because of so many processes that minimise energy or something.
And at the heart of engineering, for even more obvious reasons.
Okay. So the beginning point of optimisation and it's not just the beginning,
it's a pervasive idea throughout everything is Newton's method, which of course we've all heard of.
But that's certainly where we're going to start discussing the matter.
And we're going to begin with Newton's method in one dimension, which is the kind of thing I hope you all learned in high school.
So Newton's. Method, and I'll put it like this Newton's method for a single equation.
And the reason for putting it like that is to emphasise that I'm beginning with root finding rather than minimisation.
I remember once a teacher told me that really mathematics boiled down to two things.
One is Taylor series. The other is linear algebra.
Everything else is variations on those themes. Well, this is Taylor series.
Newton's great idea is Taylor series. Indeed,
I think Arnold wrote a book about the history of mathematics in which he essentially claimed that Newton's great contribution was Taylor series,
exploiting the smoothness of a function to approximate it by a constant plus slope plus curvature, that sort of thing.
So let's write down the notation we're going to use.
Let's suppose we're given a function, and the notation I'll use for root finding is capital F of X.
When we turn to minimisation, it'll be lowercase F. So suppose we have a function which we assume is nonlinear.
And we want to find a zero. So our goal is to find a zero of F, also called a root of F.
And the notation will use is that that's going to be X star.
So we're looking for an X star such that f of X star is equal to zero.
And you all know Newton's method. Let me write it down in this format that I'll write down a bunch of these iterations.
So suppose we're given an initial guess. Which I'll call, of course, X not.
And then we enter the loop. And I won't ever talk about termination criteria.
So I'll just say four k equals 01... define s sub k to be minus f evaluated at x sub k divided by f prime evaluated that x sub k now s.
Okay. Stands for step. Because we're going to take a step in that direction.
The new iterate is then x, k plus one is equal to x, k plus k.
So there's the iteration that you all learned in high school.
Now, let me ask I'm curious. Raise your hand if you did learn that in high school.
Oh, okay. Pretty good. And of course, you know, the picture associated with this, we have some kind of function.
We're trying to find X star, we have some guess x not we evaluate the function, then extrapolate along the tangent,
and that process converges quickly, in fact, just to say a word about how fast it does converge.
I won't state it formally as a theorem, but this is the idea if F is twice differentiable.
So that means the second derivative exists. And moreover.
The derivative evaluated at a route x star is nonzero.
Then if X not is sufficiently close to x star.
We have convergence and it's quadratic. So we say the convergence is quadratic.
Which means the number of digits doubles at each step, essentially.
Later, I may write that down. More precisely, the error at one step is proportional asymptotically to the square of the error at the previous step.
And this is a prototype for the kind of theorem you find all over optimisation.
Notice some key assumptions. Always turn up. You need some smoothness in your function.
If you lose that, then there may be no convergence or slower convergence.
You need some kind of generic behaviour at the solution you're looking for.
Otherwise you may have no convergence or slower convergence.
And especially with Newton's method, you certainly need to be close enough to the solution.
So of course, if this function keeps doing crazy things.
Depending where we start, we may converge to nothing or we may converge to different routes.
It's obvious from the picture that if we start near this route, will converge to it.
Start near that will converge to that. Things get more complicated if your function is less smooth or the derivatives are non-zero at the roots.
So of course, a route is by no means necessarily unique.
Newton's method is all about finding one route, not necessarily all of them.
Now I want to show you, as usual, some stuff. So let's go to MATLAB.
The first code is the one called M 18, which is not a program you're really supposed to look at because all it does is fiddle around with graphics.
But I was giving a public lecture once, so it was worthwhile making such a code.
So it's called Pretty Newton. So what Pretty Newton does is take a particular function and just colourfully illustrate Newton's method.
So there you have the function, which of course is the blue curve, and we're trying to find that point.
And there's our initial gas and you can see that the initial gas is 0.8.
None of the digits are correct. So they're all in red. You evaluate the function at your current gas.
And then you extrapolate along the tangent line. So that gives you a new point.
0.208. Still, none of the digits are correct.
So they're still all in red. Then we evaluate the function there.
Extrapolate along the tangent. Still none of the digits are correct.
So they're still all in red. Of course, the remainder you won't see very well.
You're mostly going to see the red digits. We evaluate and extrapolate and now suddenly we have three digits of accuracy.
.373 are correct. And from now on, every time we keep going, the number of correct digits will approximately double.
So I evaluate and then I extrapolate.
And it exactly doubled from three digits to six digits.
Do it again. We expect to get about 12 digits. I evaluate and then extrapolate.
And as it happens, we got exactly 12 digits on my machine.
It won't go beyond that.
I might be able to nail the final one, but of course, I'm working in 16 digit arithmetic, so that's as far as I'll get on this computer.
Great idea. Newton, by the way, didn't do as much with Newton's method as you probably think.
I think he mainly applied it only to polynomials, not to general functions.
And Simpson, as in Simpson's rule, was the person who really put Newton's method on its feet.
Simpson and Robson both. Okay.
Now, I also want to look at the other codes that are called M 19.
So there are three of these just to explore this problem from different angles.
Excuse me. Okay.
So here we have a problem. I might as well write it down.
We're solving. An M 19 where solving f of x equals x cubed minus two.
So we're trying to find the cube root of two.
And incidentally, on computers, sometimes Newton's method is used even for elementary things like square root sets.
It's an algorithm so useful that even in the hardware, sometimes it will be implemented.
So let's look at this from various angles. The first of the codes em 19 Newton.
A just as straightforward matlab.
So I will close that. And let's just type em 19.
Newton. A So what you see there is we've taken our initial guesses.
One, we're trying to find the cube root of two. We iterate, we get 4/3, we iterate again and again.
So you could guess now that we have several digits of accuracy.
It looks clear that now that we have four or five digits of accuracy now, it would seem we have maybe nine.
And now, from now on, it just keeps agreeing.
So, of course, it's not a proof, but it's pretty clear that we have more or less full precision in the cube root of two.
Let's see what happens if I type two to the one third.
Looks good. That doesn't mean they're the same. By the way, I could say Ant's minus X.
They might. That might be zero. Or it might be some small multiple of machine epsilon.
It turns out at zero we were lucky. The next one is doing the same.
But symbolically now I would love to show you this properly, but my laptop doesn't have the symbolic toolbox.
So you can try this at home. And therefore what I did was printed out a couple of the outputs on the sheet of paper here.
So here we're running in MATLAB symbolic toolbox, which is by no means the world's most beautiful symbolic calculator.
But anyway, it works for something like this. In MATLAB, you can declare a variable to be sim of a string,
and so one then becomes a symbolic one and you can go through this whole thing in a symbolic mode.
And Newton's method for this problem has a succession of iterates that are all rational numbers.
So you see, the first is one and then 4/3, which we identified immediately when we ran Newton.
But they keep being rational numbers at every stage.
So 91, 70 seconds and 112. Yeah, whatever.
Now, the striking thing about these numbers is that they keep getting longer.
And if you quantify that, roughly speaking, the numerator is tripling and that's number of digits at each step.
And so is the denominator because this is a cubic.
If it had been a quintillion, the numerator would have become five times as long at each step or a 20th degree polynomial, 20 times as long.
So what you're seeing here is the combinatorial explosion of symbolic computing.
Rational arithmetic is sadly just not a good idea for scientific computing because this happens all the time at combinatorial explodes.
So that's why rational arithmetic has such a small niche in computational science.
Usually it just isn't feasible. And if you're even looking at this for theatre, it said we have won 4/3 91 and then going down three more steps.
That approximation to the cube root of two will surely be accurate to 16 digits or so, but it won't be accurate to this many digits.
So most of that exactness in the rational numbers is irrelevant to the problem you're trying to solve.
And that would be very typical of symbolic or exact arithmetic computing.
Now the third one and 19 Newton C is also something I can't run on my laptop because I don't have the symbolic toolbox.
But it's the other variation on the theme of standard numerical computing.
So standard is floating point arithmetic. One variation is symbolic.
The other variation is extended precision. Another important beautiful idea.
So here in this code M 19, Newton C, I said let's run in 75 digit arithmetic.
So there you see, print it out the first few steps and 75 digit arithmetic.
And sure enough, the second one has one digit, the third one has one digit, the fourth one has three digits.
And then if you follow along, you see that the last two lines of the output are identical.
So sure enough, Newton is doubling the number of digits at each step.
Variable precision is a beautiful, wonderful thing. And I think everyone in my field wishes it were effortlessly available all the time.
If only every computer had a knob, you could turn and just change the position.
Sadly, from an engineering point of view, that doesn't seem to be worth the cost.
But for an academic like me, it would be delightful to be able to do that.
Maybe in 50 years computers will do that. So in practice, if you want to do variable precision arithmetic,
you go into some rather different mode and usually there's a significant cost associated with that.
When I was your age, quadruple precision was more common than it is now.
It's still out there. But when I was your age, single, double and quadruple were all very much part of the landscape.
So we would computed eight digit, 16 digits or 32 digits.
Now, that's kind of compressed where most people, most of the time are just working in 16 digits.
Okay. So that's Newton's method in the scalar case.
But of course, optimisation is about systems of equations.
So let's talk about that. So Newton's method for a system of equations.
And again, I'm writing that out explicitly to emphasise that we're not yet minimising, we're still finding routes of equations.
So now we're going to have a function that maps from a vector space to a vector space.
So let's say that capital F maps from our end to our N.
So we have variables and equations, if you like. We're seeking a vector x star in our n such that f of x star is zero and these are vectors.
So zero here would be the end dimensional zero vector.
So another way to say that is we have a system of equations.
And if you want, we could write them out. The first one would be f one of x one through x, n equals zero.
And that's now the scalar 0... up to f n of x1 through x n is equal to zero.
So a system of equations is the same as a single equation in a vector space.
Now, Newton's method in principle carries over. Exactly.
Although Newton himself never did that, he never did systems of equations.
And I don't remember to what extent it's thought that he sort of understood the idea of calculus with more than one variable.
Probably he did. He was smart. The idea is to do exactly the same.
We need to extrapolate along a tangent, but now a tangent will be defined by some linear algebra rather than just a derivative scalar.
So we're going to have to solve a linear system of equations at each step.
And for that to make sense, we have to talk about a linear ization of the function f.
So here's the definition, and I'll define this in the general sense of a function from one dimensional space to another.
The key thing we need is the derivative of F, which usually one would call the Jacoby and the Jacoby and matrix.
So the derivative. Of S at a point X in our end.
It's a matrix. It's the M by n matrix.
Of partial derivatives. So J for Jacoby and I could say Jay of X, that's my matrix.
And the I j component of that matrix is you could also write as f prime of x AJ component is the partial
derivative of the ice component of F with respect to the JTH component of X evaluated at the point x.
By the way, you notice I don't use special symbols to distinguish vectors.
Of course you can. You can write them in bold face, or you can put arrows over them or Tilda's over them in mathematics.
Often one doesn't do that, so people get used to just using the same thing, both for a vector as for a scalar.
I realise in other fields you may have different habits. So let's just do an example.
You all know partial derivatives and presumably most of, you know, Jacobean matrices.
The example I'll pick, we'll go from our two to our three.
So suppose we had for example, F1 of x1 x2 is equal to x1 squared and f two of x1 x2 is equal to x1 plus x1 x2 and f three of x1.
X2 is equal to x1 e to the x2.
So the Jacoby and Matrix is a three by two matrix.
Let me just write it down. F prime of x. So it's three by two.
So we differentiate the first thing with respect to x one and x two.
So we get two X1 zero, then we differentiate the second one with respect to X1 and x2.
So we get one plus x2 and x1. Then we differentiate the third with respect to X1 and x2.
So we get either the X2 and X1, either the x2.
So Newton's method is going to have to do this kind of thing all the time.
Of course, usually the derivative will be calculated numerically rather than symbolically.
Said, okay, I guess to continue for just a second on the general idea of a Jacobean,
this is Newton's idea that locally any function, if it's smooth, looks linear.
So that idea, the motivation for Jacobins.
Is that if you have this function capital F, mapping r m to our end and you evaluate it at X plus a small perturbation delta x,
so that's an M, an n vector and another n vector.
Then that should be equal to. F of X plus some suitable perturbation.
And that perturbation will be the vector, the matrix F, prime times the perturbation.
So that's the whole point of vector calculus, if you like.
These are both end vectors, as I said. And these.
Are both m vectors. Sorry.
Yeah, right. So this amp vector arises by this one by multiplying an N by an matrix by a an end vector.
So that's what vector calculus starts from. And Newton's method is simply exploiting this property in the case of a square capital F.
So let's write that down. So now it's Newton's method for a system of equations in its purest form.
So we would be given an initial guess, which is now a vector.
Ex not and then we enter into our loop for k equals 01... we evaluate.
The function. So that's F of x, k, and also the derivative Jacobean, which is f prime of x k.
Now, I'm assuming here that any calls anywhere in the square case, you can imagine that in practice, evaluating the Jacoby is a non-trivial matter.
That's a huge issue of different ways to do that. Exactly.
Or approximately. And now we want to do our update.
We need a step. And the step is now defined by a linear system of equations.
So here's the system of equations. F prime of x times s k is equal to minus F of x k.
And we're solving that for the step. So before in the scalar case we just said S.K. equals two minus F over F prime.
But now that's the system of equations. We have to solve this end by end system of equations that gives us our step.
And then x, k plus one is equal to x, k plus k.
So that's a pretty straightforward idea. A lot of optimisation consists of how to make that idea practical for big problems.
Now let's look at it in its simplest form. So what I'm going to do here is look at the code called M20 Newton's system.
So if you look at that on the back of the other ones. I guess once again I might as well write down.
Well, now it's not important you can see the function. So the function F that we're working with here is two variables and two equations.
So sine of x one plus x two minus e to the minus x one squared.
Then the second equation is 3x1 plus x1x2 squared minus one equals zero.
So we're trying to find a root of those two equations in two unknowns.
And in this case, I've explicitly written down a formula for the giacobbe, which of course would not typically be possible in a numerical calculation.
So this little code will just explicitly do Newton's iteration for that system of two equations.
Let's see what happens. I'll type M20 Newton system.
Oh, dear. Where am I not in the system? Yeah.
What did I do wrong here? Hmm.
That's interesting. Either I tested this on my desktop, but not on this laptop.
Let's see what's going on in line 32. Column one. Oh sorry.
I added some comments. That's the problem and forgot to make them into comments.
My apologies. So. They're in your output there.
And I added them at the last minute. Right.
Okay. So the code is set up to start from the initial guess of zero zero and then it solves
this two by two system of equations and gets one third two thirds and it goes on.
Now you can guess at this point, we probably have a couple of digits of accuracy.
You can guess now that we still probably have a couple of digits of accuracy.
Or maybe your best guess would be about four digits now because this either it agrees with the last 1 to 2 places,
so it's probably accurate to about four places. Sure enough, we had about five digits of accuracy and of course, numerically beautiful convergence.
So that was an easy problem.
Now, of course, you don't know looking at that, whether that's the unique solution, you're pretty certain that is a solution.
But there might be others you simply don't know from looking at that. Let me do the comments that I added there.
So of course, FUN has a lot of fun with minimising and finding routes and so on.
Two functions. Let's look at this function in fun. It's two equations and two unknowns, so I'll do the second first.
One way to do that would be to declare.
A function corresponding to X on the unit square by default and another function corresponding to Y on the unit square.
And then I could create. F1 to be sign of x plus y minus E to the minus x squared and F2 to be three times x minus x times y squared minus one.
If I have a typo, please let me know.
So to have fun too is doing its usual thing of representing functions by polynomials that match them to about 16 digits of precision.
And then there's the roots command, which in principle aims to find all the roots.
Of this system of two equations in the region where they are defined, which was the unit square.
So -1 to 1, -1 to 1. So one would hope that we'll find the root that we just found.
Maybe we'll find others, too, because Newton's method didn't tell us.
Are there others to. So we proceed and we seem to find just one.
That's not a proof, of course, but it's maybe some evidence that that's the unique route in the unit square.
Of course you could try enlarging. Suppose I changed it to the interval from.
-3 to 3. -3 to 3. So now we're in a box nine times as big.
I haven't tried this, so I don't know what will happen if I now say a defined F as before.
I've now created a global representation of these functions on these bigger domains.
I don't know what routes we'll find. Oh, okay.
So that's new to me. Hopefully those are all correct. We could get some numerical evidence of whether they're correct.
So suppose I say f one events or I'll say R equals.
And so then I'll say F1 of ah, I'm doing something wrong, so maybe I won't waste your time on that, but I'm probably those are all valid routes.
Do we recognise among them the one that Newton's method got?
I think that's the fourth one in the list, right .387.
So I currently believe that there are six routes of this pair of equations in the box.
Minus three, three, minus three, three, seven.
Also lets you work with vector calculus sort of directly.
So another way to do it would be to say F equals seven to V.
V for vector, and then we could simply make a vector function of both things.
So I could say sine of x plus y minus e to the minus x squared.
That's the first component. And then the second component is the other function, three x minus X times y.
Squared. Stop me if you see an error minus one.
So that's now a vector. Capital F is now a the proper vector function and you can ask for the roots of vector.
And there they are. Let's do the experiment of doing it on -33.
We hope this matches what we got before. Right. Seems to.
So whether that's further evidence or just the same old evidence is an interesting question.
Since I'm doing this fun stuff, let me just go to the more trivial,
one dimensional case to highlight the significance of local versus global root finding.
So suppose we take an example we looked at before. Suppose I guess say F equals a one dimensional function and I'll pick a Bessel function.
So suppose I say Bessel j and I'll do that on the interval from 0 to 20.
So if I plot f. Yup.
That's not going to be interesting. Thank you. Uh, zero x right.
So if I plot f. I find a function with several zeros.
Now, of course, Newton's method, if you started at any point, probably will converge to one of these zeros, but only one.
If you wanted to find all of them, you would need to enlarge your discourse somehow.
In the olden days, when I was your age, that was almost a taboo subject.
Global optimisation was considered provably impossible, so nobody talked about it.
But that's all sort of changes. There are now various context in which you can meaningfully do global optimisation.
Of course, a one day problem like this is very easy and Tetfund would do that.
Let me remind you how if I say R equals roots of F, of course I get all of them so I could plot them.
But let's talk about why.
What they do wrong here. That's worrisome.
Did I? What did I do wrong? Oh.
Oops. Sorry. Hold on.
Plot are against FFR. Is that what I want to do? Thank you.
Yes. Okay. So, of course, we see some kind of global route finding.
But let's talk for a moment. Why was this global?
The answer is that Ted often happens to represent functions by polynomials and find roots as eigenvalues of matrices.
And it's a fact of scientific computing that the standard way of finding eigenvalues of matrices is global.
You find all of them. So there's some matrix involved here, which has a lot of eigenvalues, six of which are those dots.
It's because the standard algorithms for eigenvalue problems get all of them that it becomes easy to do global root finding,
at least in one dimension for fun. And as I think I demonstrated before, it's pretty powerful.
So if I made that the interval from 0 to 20000, for example, I don't I haven't tried one this big.
Let's see what happens. I'll plot f. So there's your Bessel function.
The that's a polynomial of degree, 10,000.
Let's say R equals roots of F and see how long it takes.
I predict about half a minute, actually. We're finding the roots of a polynomial of degree.
10,000 in order to do global roots.
Well, 15 seconds maybe. So suppose, I guess say plot F and I'll restrict it to a small interval I'll go from.
8082 8175.
Okay. And now I'll say plot are against FLIR.
Hold on. Plot are against FFR.
Will that work? Yeah.
Okay. So in 15 seconds, we found all the roots of the Bessel function out to 20,000.
There they are. I don't know exactly how accurate they are, but probably 14 or 15 digits.
And that's an example of Global Zero finding. And I think as the decades go on, optimisation has a larger and larger part that's global.
It's still a very small minority for serious scientific problems like protein folding.
Let's say you don't have any realistic hope of global optimisation in a provable sense, but of course people are always striving for that.
Okay, so for the last few minutes, I want to begin to talk about minimisation.
And for whatever reason, minimisation is in practice a much vaster scientific enterprise than zero.
Finding it just comes up more of the time. So this is really the heart of the field of optimisation.
So let's talk about Newton's method. For minimising and we'll get start in one day.
Well, there's no great mystery mathematically about what's involved here to minimise you want to find a zero of the derivative,
and that's what Newton's method does. So we're now going to use a lowercase letter.
So we suppose now we have lowercase F. A function of a scalar variable.
And our goal is to find x star.
Such that f of x star equals minimum.
So it's interesting already, if you think about it, you can begin to see a slight difference between minimisation and zero finding.
So suppose we have some function and we want to find its minima. Well.
Of course, these are some local minima and they all have the property that the zero of the derivative is zero.
So it's interesting that from a global point of view, these are not all equal.
That's a better minimum than this one. Whereas in the zero finding problem, of course, by definition all zero zeros.
So you can see that minimisation has a complication there,
global versus local that goes deeper somehow than the analogous situation with zero finding.
So we want to find a minimum. So a.
Usually 90% of the time we were going to seek a local minimum.
And it's obvious what that means. Let's write it down.
We'll say F of X should be bigger than or equal to f of x star for all.
Ex in a neighbourhood. Neighbourhood of Star.
So that's our definition of a local minimum. And the obvious idea is to use Newton's method defined as zero of the derivative.
So if prime of x star equals zero would be the condition we apply.
And if you'll excuse my being so methodical here, I'm going to write it down.
So this is Newton's method for minimisation of a scalar function.
We're given an initial gas. Which would be ex not.
We enter our loop. 4K equals 01...
We define our step. As Sub K, we're now finding a0 of the derivative, so it's the same formula as before but differentiated.
So it's minus f, prime of x k divided by F double prime.
Of x k and then we update exactly as before x k plus one equals x k plus s-k and.
So from that, you can perhaps begin to see that minimisation is going to have some problems.
It's a whole nother derivative beyond what we had before it.
This pure Newton method depends on the curvature of the function. That's first of all, it's a lot more information.
Second of all, it's demanding more of the smoothness of a function for that to really work.
So, of course, in many applications, it will be hard to evaluate that, or maybe the derivative won't even exist if your function isn't very smooth.
And that gives a hint as to the complexity of the problem.
Let me finish by saying another way that one would interpret this.
So. Let me call it an equivalent formulation,
while at the same time hinting that it's in some sense a better formulation because it generalises very broadly,
the equivalent way of looking at Newton's method is that we approximate F of X.
Locally by a parabola. And of course the particular parabola we choose is determined by the derivative in the second derivative at our current point,
and then we set x, k plus one equal to the minimum of the parabola.
Now the reason that somehow a better formulation is that it immediately generalises.
And this in some sense is really a picture for all kinds of optimisation algorithms.
You do a local approximation and what changes is, instead of saying just a parabola,
you have some model of your function based on whatever data you've got.
And then you minimise that model. So at least for unconstrained optimisation, this is sort of the universal picture of the way most algorithms work.
You locally find some model of what your function looks like.
Use that model to get the next step. And as you go, keep improving the accuracy and probably improving the model.
So next time we'll go into multiple dimensions, but also talk about more realistic aspects beyond Newton's method.