Hello Internet this is Oscar Veliz back again with another video and root finding
this time a hybrid of Newton's method and bisection this video assumes that
you have some familiarity with bisection and Newton's method and I recommend
watching my videos on these topics I've also made another video discussing
Brent's method which is a hybrid of iqi secant and bisection which might be
helpful to understand this video it was on that video that somebody asked if I
knew anything about a method which mixed bisection and Newton's method to which
I did look into I did some digging and found slides from Mark Spiegelman
discussing a method he called NewtSafe he also referenced a book called
Numerical Recipes which I found at my library this book also referenced
another book called Numerical Methods That Work
this is my library's copy of that book in it they write
"While Newton-Raphson's global convergence properties are poor it is fairly easy to
design a fail-safe routine that utilizes a combination of bisection and
Newton-Raphson the hybrid algorithm takes a bisection step whenever Newton-Raphson
would take a solution out of bounds or whenever Newton-Raphson is not reducing
the size of the brackets rapidly enough" and this is my library's copy of
Numerical Methods That Work by Foreman S. Acton you'll notice that the cover
also has the word "usually" and then my library has three more copies of this
book Acton writes "...we see that we are in
trouble if f'(x) is zero or even if it is small in any automatic computer
application Newton's method you must be sure to check the size of the step we
are about to take reject it if it is improbably large such a rejection could
call for an automatic switch to a less sensitive algorithm... [like bisection] or it
might merely print out the values of the function and it's derivative in effect
yelling for help but it should never quietly take the
giant step and thereby create a mess for somebody else to clean up"
let's use the arctangent as an example for Newton's method folks will
recognize the same example from my video on Newton's Method Interval of
Convergence if we use a starting value of 1 Newton's method converges to the
root in about five iterations but if we start the value 1.5 this causes
Newton's method to diverge you could also get really unlucky and choose a
starting point which causes it to loop infinitely there's another issue with
Newton's method that could happen and allow me to quote myself from an earlier video
"if the point that you get has a slope of 0 then you'll never know where to
calculate your next X" let's look at one final problem with Newton's method given
the function y is equal to X minus 1.75 to the quantity cubed let's
zoom in a little bit on the root a little more
Newton's method has a hard time as you get closer and closer to the roots of
very flat functions for example these points 1.7, 1.717
1.728 are taking very small steps to get to the
next point to recap the problems with Newton's method we can diverge, get stuck
in an infinite loop, divide by zero, or have issues with root multiplicity the
answer for our hybrid method is to simply switch to bisection whenever this
happens Newt-Safe says to start with an interval a b where the function has
different signs at a and b so therefore the root must be between them then
compute a starting point of x equal to a plus b over two afterwards
check to see if f of x is less than some epsilon absolute value if it is this is
a root and we can stop otherwise check to make sure we're not going to end up
dividing by zero when we are will force a bisection and then restart otherwise
when we're safe to divide we'll go ahead and use Newton's method and check to
make sure that our new step is inside of our boundaries when it isn't we'll do
bisection again otherwise we'll simply shrink the boundary and then restart the
process for this first Newt-Safe example let's use the arc-tangent function from
earlier and specify the interval of -1, 4 this means our starting
point X is a plus b over two which is the value 1.5 if we do Newton's method
we'll end up going outside of our boundary therefore we'll force a
bisection giving us a new interval a b and we can restart the process in
this example let's use a smaller interval of -1, 3
giving us our starting x value of 1 when we apply Newton's method we'll get
a point that is inside the boundary giving us our new value for X now we
have to check our signs to shrink our boundary in this case we'll move a over
then using the X from earlier we'll compute our next X and then check the
signs to shrink the boundary repeat this process until a meets b or we end up
converging on the root there are still a few more things we need to do for newt-safe
the first is that whenever we do a bisection check our interval a b to
make sure it's still valid the second recall our quote from earlier "the hybrid algorithm
takes a bisection step whenever Newton's method would take the solution out of
bounds or whenever Newton's method is not reducing the size the brackets
rapidly enough checking the bounds is easy enough with this condition here but
what about that "reducing the size of the brackets rapidly enough" part numerical
recipes gives this condition saying if f of X times 2 in absolute value is greater
than Delta x times F Prime at X in absolute value then will force a
bisection where Delta X is simply our change in step but what does this
condition mean let's take a closer look at this condition recall Newton's method
if we make one change and subtract X sub n from both sides we can get this form for
Newton's method then if we only care about the magnitude of these values we
can do absolute value of both sides this gives us a new equation for Delta X
using what we know now for Delta X we can replace part of that condition with the
absolute value of f of X sub n divided by 8 the derivative of f of X sub n when we
multiply it by the derivative of f of X sub n plus 1 as n increases these
derivatives shouldn't change very much so we get approximately the absolute
value of f of X sub n this means our condition is actually saying if our
function our new point times 2 in absolute value is greater than our
function at our old point in absolute value then it's not converging fast
enough using what we know now about reducing bracket size let's compare this
to how Newton's method behaved for the function earlier of X minus 1.75
quantity cubed it takes about nine iterations for this to converge with
Newt-Safe from the same starting point of 1.5 using the interval one two we do
one iteration of Newton's method then the next iteration would cause it to go
too slow and therefore well force of bisection this gives us a new starting
value for Newt-Safe which we then use in the next iteration of Newton's method
then the next step would actually cause us to go too slow again
so we forced another bisection giving us our root if we include the two
bisection steps we actually save two iterations using Newt-Safe here
are some other variations that you can make to Newt-Safe first you could try
starting without an interval or just a single starting point and use Newton's
method or Damped Newton's method until the function changes sign at which case you
would have an interval a b the problem is that you still have all the problems
in Newton's method so maybe this isn't such a great way to go
you could also allow an interval that has the same sign and just iterate until
it changes sign like earlier but if your function is something like y equals X
minus 1.75 quantity squared then it'll never change sign at which point
you could just use an extremum finding algorithm to find the minimum or maximum
you could replace Newton's method in Newt-Safe to create other hybrid methods
for example if you can compute the second derivative then you might use
Halley's method to make a method called Hal-Safe or if we can compute even
higher derivatives then Householders method to make House-Safe what if f is
a polynomial in which case you can use Horner's method to create Horn-Safe but
what if you don't have a derivative at all then you might consider using
Steffensen's method to create Steff-Safe or a hybrid between secant and bisection
gives you Dekker's method which I have a video on as well as IQI Secant and bisection
to create Brent's method it is important to note that Newt-Safe will
give you guaranteed convergence when newton's method might diverge switching
the bisection would force it to converge at least linearly although note that
switching to bisection could speed up convergence when Newton's method is
behaving poorly none of the sources that I looked at proved the order of
convergence so I'll leave this as an exercise for the viewer although note it is
likely quadratic the code that I used for this video will be hosted on github
special shout out to Karim for suggesting this video topic I had a lot of fun
making this video and searching inside my library if you have other suggestions
for future videos please be sure to leave them in the comments