[music]. I often want to find approximate roots.
Well, here's the set up. I start with some nice function, f, nice
meaning differentiable. Maybe the derivative is continuous, a, a
reasonable function. And then I want to find some input, x, so
that the function evaluated at that input is equal to 0.
Now in practice, this is way too much to ask for.
I'm not really going to be able to find some particular input x.
I mean I might not even be able to write down that input in any reasonable sense.
But what I can ask for is I can find some x so that, f of x is very close to 0.
Right I mean, maybe I can't find it so that the output of the function is equal
to zero. But maybe I can find an input so that the
output there is really close to 0, really small.
If you think back, we've already done this.
Right. If you remember this video, where I use
the Intermediate Value Theorem, I was able to proximate a root of a function just by
interrogating the function, evaluating it at a handful of points.
And, there was that bisection trick. So in this example it looks like the
function evaluated that a is positive and the function evaluated b is negative.
This function looks like a reasonable nice function who's continuous so the
intermediate value theorem applies. And that mean in-between a and b, there's
some input, where the function's output is 0.
I can cut this interval in half and if I look in the middle of interval the
function's output there is positive, and that means just in between these two
inputs there must be some input where the function's output is 0.
And then I could cut that in half again. And if I look at the input there, the
output of the function is negative. And that means in between these two inputs
there must be some input so the functions output is 0.
And then I could cut that in half again. And if I look there the functions output
is positive. So I've got a negative output Put in a
positive output, so in between, by the intermediate value theorem, there must be
some input where the function's output is 0.
And so on and so forth, right? I'm getting closer and closer to the point
where the function output is actually equal to 0, at least I can approximate it
this way. The downside to this bisection method is
just speed, it takes a really long time. So a different method, called Newton's
method, is much faster than this bisection trick.
Well, this is faster when it actually works.
So what is Newton's method. What I'm trying to do is find the x
coordinate, where the graph of this function crosses the x-axis right.
I want to know an input so this function's output there is 0.
And instead of marching in from either side, as in intermediate value theorem,
Newton's method has us just start by making a potentially bad guess.
Here's my 1st guess. I'm going to call it x of 0.
And yeah, that's, that's not a very good guess.
Because the function's output is all the way up here.
Not that close to 0. But after I've made that first guess,
Newton tells us to draw the tangent line to the curve.
Through, through that point. So here's the tangent line to the curve
through that point. And then my next guess will be wherever
that tangent line crosses the x axis. So here would be my next guess x of 1.
And then I just hope that, that next guess is better.
But I could repeat the process. Right?
I could do the same game here. This point is closer to 0.
And then I could again draw another tangent line to the curve, through that
point. And then this next place where that
tangent line crosses the x axis that'll be x of 2, my next guess.
And at least from this picture it looks like that's an even better guess as to
where the graph of this function crosses the x axis.
So at least pictorily that's what Newton's method is telling us what to do.
Let's write down the steps. Well here is Newton's method in words.
You start with some initial guess x0. The next step is to draw the tangent line
through the point x0 f of x0, right. That's exactly what I did here.
I started with x0 and then I drew this 1st red Tangent line.
Now the next step is to figure out where that tangent line.
All right, the tangent line right there. Crosses the x-axis.
Now I'm going to use that for my new guess, x of 1.
Which I hope will be a better guess from my original guess.
All right, my original guess was pretty far away from 0.
X1, Which is where the tangent line here crosses the x-axis.
I'm hoping that's a better guess. And yeah, at least in this example it is.
And then I'm going to repeat the process. Right?
In this picture, once I had my new guess X of 1 I then drew the tangent line to the
graph at X 1 comma F of X 1 and that tangent line intesect the X access at a
point I'm calling X of 2 and I'm just hoping then that, that's even a better
guess as to the actual point where the graph crosses the X access.
All right, so that's this repeat process. And you can just keep repeating this as
long as you want. And, you know, hopefully you're getting
better and better guesses every time. As to exactly where that graph crosses the
x-axis. Those worked this all out with equations.
Right? I'm going to write down the equation in
the tangent line. And then solve for wherever that tangent
line crosses the x-axis. So I'm going to start by thinking about
this red line, right? This red line is the tangent line to the
orange graph at the point x0, f of x0. And as a tangent line, so it has slope the
derivative at x0. And here I've written down the point slope
form Of the red line. Right?
It's y minus the y coordinate on the line, which is fx0, is equal to the slope of the
line which is the derivative add x 0. Times x minus the x coordinate on the
line, which is x0. Now, Newton's method tells me that I
should use that linear approximation to the graph, figure out where the linear
approximation crosses the x axis and just hope that's a better approximation to
where the orange curve actually crosses the x axis.
So to do that, I'm going to set y equals 0 and I'm going to solve for x.
Right. And that'll tell me where the red line
crosses the x axis, if I solve this equation for x.
Well, I can expand out, this side. Right?
And, the right-hand side of this equation is f prime, x 0 times x minus f prime x0
times x0. I'm going to add f prime x0 times x0 to
both sides. So the equation becomes f prime x0 times
x0 minus f of x 0 is equal to f prime x 0 times x, right?
I just added f prime of x 0 times x 0 to both sides.
And 0 here went away. Right?
So f prime x 0 times x 0 minus f of x 0 is equal to this f prime x 0 times x.
Now assuming that the derivative not equal to 0 at this point I'm going to divide
both sides by f prime x 0. We're going to divide this side by f prime
f 0, I just get x0. 0 minus f of x0 divided by f prime x0, so
that's this left-hand side divided by f prime of x0.
The f prime x0 here cancelled, and the f x0 divided by f prime of x0 is what I got
here. And I'm dividing both sides by f prime of
x0, so this side is just x. So the x coordinate where this red line
crosses the x axis is this. And I'm going to call this my new
hopefully improved guess, x sub 1. With this equation in hand, I can now
write down the step by step process for Newtons method just using a formula.
Here's the step by step process. I start with some initial guess x sub 0,
and then I'm drawing that tangent line to the graph x 0 x of f 0, looking where that
tangent line crosses the x axis to get my new guess, right?
And this is the formula we just computed. X1, my new guess, is X 0 minus the
functions value there divided by the functions derived there.
And with that new guess, I can then play the same game.
Drawing the tangent line to the graph at X1, F of X1.
Figure out where that tangent line crosses the x-axis, to get a newer guess x of 2.
Same formula works for that. It's the old guess minus the function at
the old guess divided by the derivative at the old guess, to get my new guess.
And I can just keep playing this game over and over again.
Hoping that each generation brings me closer To a place where the function's
value is in fact 0. Let's just summarize the formula.
So in summering I could say that my new guess which I'll call x of n plus 1, is my
old guess minus the function's value of my old guess divided by the function's
derivative at my old guess. And I can just keep repeating this over
and over again. When this works, all right, when Newton's
method actually succeeds, it works really well and it zooms in on that root really
quickly. The problem is that I can't promise you
that Newton's method will actually work.