0:00

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