Let's take a look at some open methods for finding roots.
By open method I mean we don't need brackets around the roots.
Sometimes I start with one point, sometimes I start with two points, but they are not
required to be on either side of the root.
So let's start with Newton-Raphson, it's one of the most common and the simplest ways to
find roots, and it's also very powerful, if we're near the answer it converges very, very
quickly.
Quadratic action, so the number of decimal places, and the number of significant digits
you get to the root doubles with every iteration, which is pretty powerful, if you're right
within 1% then on the next iteration you're going to be right within 0.01%, so let's take
a look to see how this works in practice.
We got some root, so we're drawing the line f(x)=0 to see where that root is that we're
trying to find, and we start out with x(i).
We need some guess for the root.
So once we have some guess for the root then what we do we know that near the root that
a linear approximation will be pretty good, so we know the slope of that line too, it's
the derivative of f(x), so we go up to f(x), and from that value we draw a derivative line
down.
Now if the function we're an exact line that would intersect exactly at the root.
It's not quite a straight line, so it doesn't go quite to the root, but it gets pretty close
with just one guess.
So that's our new point, x(i)+1.
Well that's great if we have a graph, but what if we need to actually calculate it?
So in that case we can just use a little geometry, we know that the slope of this triangle is
going to be the rise over the run, and so there we know the f '(x) is just the rise,
(f(x(i))-0)/(x(i)-x(i+1)).
So once we've got that we've got our slope, and then we know f(x(i)), and we know x(i),
and we know the derivative of f at x(i), so all we need to do is figure out x(i+1).
So just a little manipulation here to find both sides by f ' and x(i), and the difference
between x(i) and x(i+1), then we just solve that, do a little addition and subtraction,
solve for x(i+1).
Now we've got x(i+1) in terms of things we know.,(x(i)-f(x(i)))/f '(x(i)).
Now there are some issues with this, for example if the slope is 0 at that point then the denominator
is zero, and that blows up.
In fact if the slope is very flat we actually can have some real problems, because it might
send us off in a very wrong direction, but if we're near the root, and the root isn't
exactly flat, then this could converge very quickly.
So that's the first step, so the next step we just repeat the process, we go up and compute
the derivative at that point, draw the tangent line down, and that gives us a new guess for
the function, so you can see in this case graphically we can see that it converges to
the correct answer very, very quickly.
Let's do the graphs.
Now, one key to this is that we need to have an analytical derivative.
If we have an analytical derivative then we're all set, but maybe the function we're interested
in is the output of some much larger program, we can't really go in and compute that derivative
exactly, so what we need is a way to approximate the derivative.
So that takes us to the Secant method.
So the Secant method again, we have some initial point, we actually start with two initial
points, and then what we can do is if these points are close together we can approximate
the derivative with these two points.
if we know the function values of those two points we take that difference and divide
by the distance between the points, that gives us the approximate slope, that's the average
slope between those two points.
So if they're close together it's a pretty good estimate of the slope, as you can see
here it's not quite at the tangent line, but it's pretty good.
And so we draw that line down and that gives us our new x(i+1).
We've got our approximation for the derivative, then all we do is we take the new graphs and
formula and we plug the first equation into the second equation, do a little bit of algebra,
and now we have a formula for x(i+1), it's the same x(i+1) that's depicted graphically
on that screen, and it's in terms of things we know, x(i), x(i-1), f(x(i)), f(x(i-1)).
So there we go, and then we just repeat that procedure.
We need the value of the function and the value of it's derivative at x(i+1).
To compute the slope we take our last value, x(i), and the next one x(i+1), so now x(i)
is taking the place of x(i-1), and x(i+1) is taking the place of x(i), so we draw that
slope, follow the same procedure, and again we see that with this curve we get very close
to the answer very quickly, and that's our new x(i+2).
So one downside of the Secant method is that if our gap between the two ends up being rather
large we might have a bad approximation for the derivative.
Here it's pretty flat, but in other cases it might be a bad approximation.
So we can approximate the derivative numerically another way, and that brings us to the Modified
Secant method.
Here we have some initial x(i), but instead of having a separate x(i-1) we have some small
perturbations, some small change, and we increment the x(i) by that amount, and then we compute
an approximate derivative by, it's the same thing, it's the value of x(i) and the value
of the function of x(i), and the value of the function at x(i+h)/h, so that gives us
a derivative.
That gives us the value of x(i+1).
We follow the same procedure along, we have a new x(i+1), and now the new value we use
to approximate the derivative is not x(i), it's just x(i+1) plus some small amount.
So we compute the derivative with that slope, the intersection of that line with the axis
will give us our new approximation, and we keep on going.
The algebra is exactly the same as with the Secant method.
So now we've got three methods that have the same basic ideas, that we want to approximate,
that we want to calculate the next value in our series of approximations using the derivative,
using an analytical derivative, and two different ways of approximating a numerical derivative.
There's trade offs of different methods, of each of these methods, that they might be
slightly better in different situations.