Hello internet, this is Oscar Veliz again
In this video we'll go over Householder's
Method for finding roots, not to be confused
with Householder's Transformation
We'll discuss the derivation and history and
then go through some examples before also
generating some fractals using it
This video will assume that you have some
familiarity with Newton's Method and Halley's
Method.
I recommend watching my videos on these topics.
Recall that from the first order Taylor polynomial
we're able to generate Newton's Method and
with the second order Taylor polynomial we
can create Halley's Method, but why stop there?
What happens with the third order Taylor polynomial?
From our third order Taylor polynomial we
care for our next value for x to make that
function equal zero, so then simply plug in
x sub n + 1 into our equation afterwards we
can move our f term over and factor out the
subtraction of x sub n + 1 minus x sub n then
divide the other terms over and then move
our x term, the trouble is we're still left
with that x sub n term on the right side,
we can do another factoring but this still
doesn't help us.
Not all hope is lost though we can use the
Newton step and the Halley step and substitute
them into our equation to give us this form.
I removed the of x sub n terms just to keep
things simple.
Notice now we can do that multiplication on
the bottom to give us this form.
Now if we make our denominators match we can
get this equation.
We can then perform that subtraction and afterwards
multiply those two terms on the bottom to
give us this form.
We can factor out a 2f' from both of those
terms to come up with this equation equation
which still has a fraction on the bottom,
we can get rid of that by multiplying it by
the denominator in the denominator.
We're almost there.
Do that multiplication and expand the denominator
to come up with this form, then do one more
simplification and we have Householder's Method
Order 3.
In the paper "On Schröder's Families of Root-finding
Methods" by Petković et. al they write "In
1953 Householder presented a family of iteration
methods [with this equation] of the order
m." citing "Principles of Numerical Analysis"
by Householder
Let's very quickly look at that book.
This is my library's copy of "Principles of
Numerical Analysis" you'll notice it is very
close to "Elements of Numerical Analysis"
by Peter Henrici, you may recall that book
from my earlier videos on "Fixed Point Iteration
for Systems of Equations" and "Generalized
Aitken-Steffensen".
In Householder's book he approximates the
function 1/f(z) by this equation where h sub
r is equal to the rth derivative of 1/f divided
by r factorial.
He lets the function P sub r equal to h sub
r-1 divided by h sub r.
So if we do that substitution we can simplify
the equation by multiplying the top and bottom
by r factorial to come up with this equation
for P sub r. Householder writes "x + P sub
r defines an iteration of order r + 1, at
least.
Note that ... P sub 1 is equal to -f/f', which
yields Newton's Method."
Here is the more common representation of
Householder's Method these days.
Notice that you'll need to take d derivatives
of the function of 1/f.
So here are the first three derivatives for
1/f.
With d equal to 1 we plug in our derivatives
then multiply the top and bottom by negative
f squared to come up with this form which
is Newton's Method.
With d equal to 2, come up with this form,
multiply the top and bottom by f cubed to
come up with this equation which is Halley's
Method.
With d equal to 3 we do the same process and
simplify to come up with the equation that
we found earlier also known as Householder's
Method Order 3.
Let's look at an example of Householder's
Method in action for the function x cubed
minus x squared minus x minus one.
We'll need the first second and third derivatives
and let's just start from the value of two
for example.
Plug everything into our functions, then plug
all those numbers into Householder's Method
giving us the value for x2 of 1.8394
Then it only takes one more iteration to find
our root.
You'll notice that Householder's Method is
incredibly fast.
Let's look at another example but this time
with different values for d.
We'll use the values for one, two, three,
and eight.
Recall again that one gives us Newton's Method
and two gives us Halley's Method.
Newton's Method takes about eight iterations,
Halley's only about five, the third order
Householder Method takes four, and the eighth
order only takes two.
Let's take a closer look at those iteration
functions.
For d equal to one Newton's Method gives us
this form, two Halley's Method gives us this
form, and three Householder's Method gives
us this equation.
For eight which was our fastest term though
it is also by far our longest.
Householder writes "... one can in fact obtain
an iteration of any desired order...
However, one must expect that an iteration
of higher order is apt to require more laborious
computations.
The optimal compromise between simplicity
of algorithm and rapidity of convergence will
depend in large measure upon the nature of
available computing facilities."
Like I promised at the beginning of the video
we'll go over how to make fractals using Householder's
Method.
If you haven't already I would first recommend
watching my video on Newton Fractals.
The image on the left is the Newton Fractal
for the function arctangent plotting its convergence
behavior.
The image on the right is the same thing but
only using Halley's Method, you can see how
much more convergent it is.
Let's compare this to Householder's Method
order 3.
As you can see Householder's Method is much
faster but there are points that are giving
it trouble.
Her is the Newton Fractal for sin(z) and this
is Householder's Fractal which looks very
much the same.
This again is our Newton Fractal for z cubed
minus one compared with Halley's Method, compare
that to Householder's Method which looks very
similar to Halley.
Let's generalize our fractal by adding an
a term in front such as the value of one half;
but recall that we can make a any complex
number like the number one half plus i over
two giving us a sort of plasma lightning effect.
Let's look at one last function which is z
to eighth plus fifteen z to the fourth minus
sixteen.
Here's our Newton Fractal compared with Halley
compared with Householder.
Again Halley and Householder look very similar.
Here is a generalized version of that fractal
with the value of one half; and for the value
of one half plus i over two.
Let's pull an Ant-Man and zoom in going almost
sub-atomic.
Some things I want you to keep in mind when
using Householder's Method.
If you set d equal to one you get Newton's
Method, when its two you get Halley's.
It does require that you have d derivatives
in order to be able to use it but it does
give you d + 1 convergence order.
Keep in mind it is a matter of how fast you
want it to converge versus how complex you
want your iteration function to be.
I would personally recommend watching my video
on Laguerre's Method and also check out the
code I wrote which will be hosted on GitHub.
I'll also put the images there as well.
As always thank you for watching and for letting
me know what topics you guys want to see.
If you can leave a comment letting me know
which videos have been the most helpful to
you and what aspects of these videos you find
the most interesting.
Again, thank you for watching.
