[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.