this video will assume that you have some knowledge of newton's method
which is a topic i've covered on this channel many times
in my lesson on brent's method i received this comment asking about a method which mixed
bisection and newton's method it became the newton bisection hybrid video that same comment
also mentioned a global newton method which stuck with me and as i was reading papers
on newton fractals you know as you do i came across this paper which mentioned such a method
the author write "a well-known weakness on newton's method is that it is locally but
regularly globally convergent to improve the situation researchers have invented dapping
methods that try to increase the likelihood that an initial condition lead to convergence"
they cite these two books owned by dennis jr and schnabel and the other by hager
both include chapters on a globally convergent newton method
citing the same paper this one by armijo
we can modify newton's method to instead of taking a normal step take a partial step this
is the damp newton's method using a scaling factor a this example 0.9 will cause our
method to go from diverging to converging trouble then becomes how do you find a good value for a
from our normal step size you could try for example 0.8 cause a variable change there
0.4 would be closer in reality we need to find a such that plugging a into
this equation will give us zero meaning we've changed one root finding problem for another
there's also the problem of when newton's method doesn't have a solution
and this is what our mijo was looking into
in this example starting from any point it will eventually converge to a minimum
and then shoot off to infinity
what we really want is for newton's method to stop right there meaning we want a value for a
which will minimize this function of course that means we've now changed a root finding
problem for a minimization one or have we what armijo realized was that all we really need is
for our next point to be smaller than our current one this actually works for root finding as well
here's an example of what i mean let's just take our distances to zero and evaluate them
what we notice is that on the left we are diverging on the right we are converging when each
of our next points is getting smaller armijo's strategy says try a value for a of 1 check that
it is indeed getting smaller if it is then keep going but if it doesn't divide a by 2 and restart
here's what that algorithm will look like given our starting point and initial value for x f and
f prime compute fx being f(x) and deltax starting at infinity then check if our f is small enough
or our step was small enough when either was the case x is the solution and we can stop
otherwise let deltax be our step and create a temporary value t and f(t) then let a equal to one
check if our next point would be smaller if it isn't
divide a by two and create a new value for t and f(t) and recheck
otherwise let deltax be our actual step and assign t to x and f(t) to f(x) and restart the process
let's look at our arctan and example from earlier with normal newton's methods starting at the point
1.5 this inch diverging but the global version of newton's method we'll do one backtracking
step with a of a half otherwise letting a be one and this converges the same is true if we start
very far away for example the point 100 this still converges with global newton method
let's change gears now and look at what it does to fractals
here is the newton fractal for z cubed minus 1 showing
the convergence behavior in the complex plane
and this is how the behavior changes with the global newton method you'll notice a lot
more blue which you might think means it's taking longer to converge but when we look at the actual
color mappings it actually converges much faster to be fair this does hide the backtracking steps
what if after this we now made a modification to our fractal behavior
by instead of dividing by 2 dividing by 2i
the result looks like something out of an m c escher painting
let's look at one other function which is z squared plus one which has
no real solution when you start with a real number
here are the fractals we get for the normal and global versions of the newton
method but actually picking a real number with the global one
will converge to a minimum and even some points around the real numbers will converge to minimum
let's examine those extra function calls on the left we have the arctangent on the right x squared
plus one on the left starting from even very far away a starts as a small number and then goes
to one as we iterate to find a solution on the right even starting kind of close to the minimum
a starts as one and as we iterate a gets smaller this is because on the left we're converted to
a root and the right we're converting to a minimum but hold on in our fractal example
didn't it converge quickly well that's because our final ending epsilon was 10 to the minus 3
so it didn't really show let's change gears and look at solving systems of nonlinear equations
i'm going to refer to a nonlinear system example from :iterative
methods for the solution of equations" by jf traub
traub gives example of x cubed minus 3xy squared equal to one
and three x squared y minus y cubed equal to zero which my plotting tool had difficulty with
so i had to change a different solver it has these three solutions and for
a nonlinear system we're going to need to use the inverse jacobian
and this is actually our jacobian that we'll be using let's zoom in
if we solve the system starting at every point we'll end up creating this fractal
which looks oddly familiar in fact z cubed minus 1 given into a system with x referring to the real
numbers and y referring to the imaginary ones is the same what happens if we use the global method
now adding a variable a in front of our inverse jacobian
we get this kaleidoscopic result if you're wondering why the output
formatting changed that's because i used a different program in this case julia
to make the system solving easier let's look at one other example
here are the newton and global newton fractals from that system
notice that the colors aren't that different that's because
these points here where the matrix is singular is causing everything to go awry let's fix that
giving this fractal that converges much faster
although again the backtracking steps are being hidden let's look at a larger version
let me know which artist you think this resembles in the comments
to recap global newton method will converge although that solution might be a minimum
instead of a root it also works with complex functions and systems of nonlinear equations
don't forget about the hidden cost of those extra function calls you can also modify this approach
to work with other methods like steffensen's method or finite difference and they can be
used to make fractals the code i wrote as well as the images are created will be hosted on github
as always thanks for watching and for your continued support on this channel
videos like this one take a very long time to make and i always appreciate your feedback in
the comments also don't forget to post which artist would have made that fractal from earlier
again thank you for watching