Hello internet this is Oscar Veliz again and this video we'll go over
Halley's method for finding roots we'll discuss the history and derivation
and then some examples and finally I'll show you how to make cool fractals using
it if you haven't already I do recommend watching my videos on Newton's Method
and Newton's Method Interval of Convergence
recall that with Newton's method we use tangent lines to approximate our next
point Halley's method does something different
we instead use tangent hyperbolas but
first let's go back in time There was a comet that came by in 1682
we'll come back to this or rather it will come back
in January 1684 Edmond Halley Christopher Ren and Robert Hooke met to
discuss planetary motion and the inverse square law Hooke claimed to have
derived it but after some time was never able to provide evidence of doing so
in August of that year Halley then turned to Newton who also claimed to
have solved the inverse-square law but he was actually able to provide evidence
Newton then gave Halley a paper called of the motion of bodies in an orbit
that paper became the basis for a series of books that we call Principia which
has its own drama and history associated with it
two years later Halley nominated Joseph Raphson to join the Royal Society this is
his signature in the charter Raphson is best known from the Newton-Raphson
method originally published in this book
then in 1692 a French mathematician named de Lagny created this new method
for finding cube roots which intrigued Halley
in 1694 Halley published a new exact and easy method of finding the roots of any
equation generally without any reduction which we can now refer to as the basis
of Halley's Method he built upon the work of de Lagny and Raphson
we'll now skip to 1705 when Halley published what is probably his most
famous work his synopsis of comets
in the English translation he writes hitherto I have considered the orbits
comets as exactly parabolic but since they appear frequently enough and since
none of them can be found to move with an hyperbolic motion tis highly probable
they rather move in very eccentric orbits and make their returns after long
periods of time though the period of its revolution be vastly long
then whenever a new comet shall appear, we may be able to know whether it be any
of those which has appeared before and consequently to determine its period
axis of orbit and to foretell its return he then goes on to note three comet
sightings which were probably the same one in 1531 1607 and one that he saw in
1682 hence I dare venture to foretell that it will return again in the year
1758
on Christmas 1758 Johann Georg Palitzsch spotted Halley's Comet
or what we now refer to as Halley's Comet if Halley had lived to see it
he would have been well over hundred years old
let's jump back in time now to 1712 to one brook taylor and a letter to John
Machin he writes while I was thinking of solving the Kepler problem I fell
into a general method of applying dr. Halley's extraction of roots to all
polynomials and it is comprehended in this theorem we now refer to that as
Taylor's theorem Feigenbaum writes if I interpret Taylor's notes correctly he
arrived at Taylor's Theorem in the following way he first noticed what Holly had
failed to realize before him that the coefficients in a generalized version of
his equations are directly related to successive derivatives of the original
polynomial let's now jump to a most excellent paper called on the geometry
of Halley's method by Scavo and Thoo they write despite Taylor's achievements
he was unable to provide a general formula for Halley's method
it remained to Schroder more than one and a half centuries later to derive Halley's
iteration function as we now know it but Schroder made no reference to Hally
indeed Schroder mentioned Halley's formula only in passing Frame on the
other hand was the first to drive Halley's iteration function via a second degree
Taylor polynomial Salehov in 1952 was apparently the first suggest that Halley's
iteration function could be derived using an oscillating rational function
of the form this equation in other words Halley's formula can be derived using an
oscillating hyperbola indeed Halley's method is sometimes it called the method
of tangent hyperbolas with Halley's method we draw that
tangent hyperbola to come up with our new value for x2 this may not look like
a tangent hyperbola unless we use zoom out or use a different function which is
much more clear here to come up with our next value for x2 our equation for the
tangent hyperbola is given by this function
this equation is designed to go through our point at xn and to also be tangent
using the variables a b and c we'll also having a helper variable d which
looks like this from this equation we can actually derive Halley's method with
our hyperbola all we really care about for our next value for x is where our
hyperbola is zero so if we plug in X sub n plus 1 all we really need is for that
numerator to be equal to zero therefore if we move our X sub N and C terms over
and substitute what we know for c this gives us Halley's method although it's not
the traditional derivation let's imagine a line and have that line
go through our function at X sub n and have the same derivative at X sub n giving us
an equation that looks something like this where that line intersects the x
axis we care to be zero to give us our next value for x therefore plug in X sub n
plus 1 move the F term over and divide by the derivative term then move the X
term over and we get Newton's method there's a strange coincidence though
that line equation is actually our first order Taylor polynomial what if we
instead used the second-order Taylor polynomial using the same process plug
in X sub n plus 1 where our function will give us 0 then move our F term to the
right and this time we'll factor out the subtraction of x sub n plus 1 minus X
sub n then divide our other term over and finally move our X term and the
problem is we're still left with an X sub n plus 1 term on the right side there
actually is a way to get rid of this term recall our Newton's method function
if we replace that subtraction with the Newton step it can come up with this
form then do some clean up and we get Halley's method
let's look at an example of x squared minus X minus 1
using Halley's method we'll need the derivative and the second derivative
with an end condition of 10 to the minus 7 if we start from the value of 0 we do
3 function evaluations then plug them into Halley's method to give us our next
value for X in this case negative 1/2
after 2 more iterations we're able to come up with the solution of negative
0.618
let's look at this example of X cubed minus x squared minus X minus one we'll
need the first and second derivatives and this time we'll start from a very
bad starting guess of -2 do our three function evaluations and then plug
everything into Halley's method giving us a value of negative one point
something this one does eventually converge but
after 16 iterations let's compare this to how newton's method would behave
starting from the same point
here's one iteration of both methods then after about five iterations
and then after about 10 notice that Newton's method is actually doubling back
on itself in fact Newton's method takes a very long time to converge
we'll do one last example which is the arctangent using Halley's method find
our first and second derivatives plug in our starting value it takes about three
iterations to converge let's compare how Halley's method does in this case against
Newton's method in this example Newton's method diverges
while Halley's converges and in fact Halley's method is usually much more
convergent overall and converges with a faster order
let's compare the convergence behaviors in the complex plane using a Newton
fractal if you haven't already I would highly suggest watching my video on Newton
fractals only now will use Halley's method this is the Newton fractal for the
arctangent and here's the Halley's version of that fractal let's expand it
you can see how this is much more convergent let's look at another example
in this case the sine of Z using Newton's method Halley's method actually
looks very similar there isn't a whole lot of difference for the sine function just
note that for real numbers where the imaginary part is zero this one has a
much better convergent behavior than the Newton version
here is the Newton fractal for Z cubed minus one which we'll then compare to
Halley's method with Halley's method we have far fewer
extremum points causing the function to diverge and it also converges much
more quickly recall though that we can add a variable a in front to make a
generalized fractal which looks something like this here's the value of
a of 1/2 but recall that we can make a any complex number
such as the value of 1/2 plus i over two giving us a look of spirals within
spirals
this is the Newton fractal for Z to the eighth plus fifteen Z to the fourth
minus sixteen let's compare that to the Halley version
again for the Halley version there is a lot fewer extremum points and it
converges much faster overall let's generalize things
such as the value of a of 1/2 and even better still a complex number
like 1/2 plus i over 2 if this had director I'd say was Christopher Nolan
dreams within dreams it seems
Final thoughts Halley's method is more complex than Newton's method requiring a second
derivative but this does give you cubic convergence and better convergence
overall but we still can diverge or divide by zero
Halley's comet will come back again in the year 2061 I'm looking forward to it
I'd also recommend checking Laguerre's method and Householder's method the code
that I used as well as the images that created will be hosted on github as
always thank you for watching I hope you found the history of Halley's method as
fascinating as I did if you would like for me to cover the history of other methods
like newton-raphson let me know in the comments down below thank you