You've seen the title so you know this is leading
to a certain fractal. Actually it's an infinite family of fractals. And yeah, it'll be one of
those mind-bogglingly intricate shapes that has infinite detail no matter how far you zoom in. But
this is not really a video about generating some pretty picture for us to gawk at. Well, okay,
maybe that's part of it, but the real story here has a much more pragmatic starting point
than the story behind a lot of other fractals. And more than that, the final images that we get to will become a lot more meaningful
if we make an effort to understand why given what they represent they kind of
have to look as complicated as they do, and what this complexity reflects about an algorithm
that is used all over the place in engineering. The starting point here will be to assume that
you have some kind of polynomial and that you want to know when it equals zero. So for the one
graphed here you can visually see there are three different places where it crosses the x-axis, and
you can kind of eyeball what those values might be. We'd call those the roots of the polynomial.
But how do you actually compute them exactly? Now, this is the kind of question where
if you're already bought into math maybe it's interesting enough in its own right to
move forward. But if you just pull someone on the street aside and ask them this,
I mean they're already falling asleep, because who cares? But the thing is this kind of
question comes up all the time in engineering. Where I'm personally most familiar
with equations like this popping up is in the setting of computer graphics, where
polynomials are just littered all over the place. So it's not uncommon that when you're figuring
out how a given pixel should be colored that somehow involves solving an
equation that uses these polynomials. Here let me give you one fun example. When
a computer renders text on the screen, those fonts are typically not
defined using pixel values. They're defined as a bunch of polynomial curves,
known in the business as "Bézier curves", and any of you who've messed around with vector
graphics, maybe in some design software, would be well familiar with these kinds of curves. But
to actually display one of them on the screen you need a way to tell each one of the pixels of your
screen whether it should be colored in or not. These curves can be displayed either with some
kind of stroke width or, if they enclose a region, some kind of fill for that region. But if
you step back and you really think about it, it's an interesting puzzle to figure out
how each one of the pixels knows whether it should be colored in or not just
based on the pure mathematical curve. I mean, take the case of stroke width. This
comes down to understanding how far away a given pixel is from this pure mathematical
curve, which itself is some platonic ideal, it has zero width. You would think of it as
a parametric curve that has some parameter t. Now one thing that you could do to figure out
this distance is to compute the distance between your pixel and a bunch of sample points on that
curve, then figure out the smallest. But that's both inefficient and imprecise. Better is to get
a little mathematical and acknowledge that this distance to the curve at all the possible points
is itself some smooth function of the parameter, and as it happens the square of that
distance will itself be a polynomial, which makes it pretty nice to deal with. And if this were meant to be a full lesson on
rendering vector graphics we could expand all that out and embrace the mess. But right now
the only salient point that I want to highlight is that in principle this function whose
minimum you want to know is some polynomial. Finding this minimum, and hence
determining how close the pixel is to the curve and whether it should get filled in, is now just a classic calculus problem. What you
do is figure out the slope of this function graph, which is to say its derivative, again some
polynomial, and you ask when does that equal zero. So to actually carry out this seemingly simple
task of just displaying a curve, wouldn't it be nice if you had a systematic and general way to
figure out when a given polynomial equals zero. Of course, we could draw a hundred other
examples from a hundred other disciplines, I just want you to keep in mind that
as we seek the roots of polynomials, even though we always display it in a
way that's cleanly abstracted away from the messiness of any real-world problem, the
task is hardly just an academic one. But again ask yourself, how do you actually
compute one of those roots? If whatever problem you're working
on leads you to a quadratic function, then happy days, you can use the quadratic
formula that we all know and love. And as a fun side note by the way, again
relevant to root-finding in computer graphics, I once had a Pixar engineer give me the
estimate that considering how many lights were used in some of the scenes for the movie
Coco, and given the nature of some of these per-pixel calculations when polynomially
defined things like spheres are involved, the quadratic formula was easily used multiple
trillions of times in the production of that film. When your problem leads you to a higher-order
polynomial things start to get trickier. For cubic polynomials, there is also a formula, which
Mathologer has done a wonderful video on. There's even a quartic formula, something that solves
degree-4 polynomials, although honestly that one is such a god-awful nightmare of a formula that
essentially no one actually uses it in practice. But after that, and I find this one of the
most fascinating results in all of math, you cannot have an analogous formula to solve
polynomials that have a degree five or more. More specifically, for a pretty
extensive set of standard functions, you can prove that there is no possible way
that you can combine those functions together that allows you to plug in the coefficients of
a quintic polynomial and always get out a root. This is known as the unsolvability of the quintic, which is a whole other can of worms we
can hopefully get into it some other time, but in practice, it kind of doesn't matter
because we have algorithms to approximate solutions to these kinds of equations
with whatever level of precision you want. A common one, and the main topic for
you and me today, is Newton's method. And yes, this is what will lead
us to the fractals, but I want you to pay attention to just how innocent and
benign the whole procedure seems at first. The algorithm begins with a random guess let's
call it x_0. Almost certainly the output of your polynomial at x_0 is not zero, so you
haven't found a solution, it's some other value visible as the height of this graph
at that point. So to improve the guess, the idea is to ask when does a linear approximation
to the function around that value equal zero? In other words if you were to draw a tangent line
to the graph at this point, when does that tangent line cross the x-axis? Now assuming this tangent
line is a decent approximation of the function in the loose vicinity of some true root, the place
where this approximation equals zero should take you closer to that true root. As long as you're
able to take a derivative of this function, and with polynomials you'll always be able to do that,
you can concretely compute the slope of this line. So here's where the active viewers among you
might want to pause and ask how do you figure out the difference between the current guess
and the improved guess. What is the size of this step? One way to think of it is to consider
the fact that the slope of this tangent line, its rise over run, looks like the height of
this graph divided by the length of that step. But on the other hand of course, the slope of the
tangent line is the derivative of the polynomial at that point. If we rearrange this equation
here, this gives you a super concrete way that you can compute that step size. So the next guess
which we might call x1, is the previous guess adjusted by this step size. And after that you
can just repeat the process. You compute the value of this function and the slope at this new
guess which gives you a new linear approximation, and then you make the next guess x2 wherever
that tangent line crosses the x-axis. And then apply the same calculation to x2
and this gives you x3, and before too long you find yourself extremely close to a true root
pretty much as close as you could ever want to be It's always worth gut-checking that
a formula actually makes sense, and in this case, hopefully it does. If p(x)
is large, meaning the graph is really high, you need to take a bigger step to get down to
a root. But if P'(x) is also large meaning, the graph is quite steep, you should maybe
ease off on just how big you make that step. As the name suggests this was a method that
newton used to solve polynomial expressions, but he sort of made it look a lot
more complicated than it needed to be, and a fellow named Joesph Raphson published
a much simpler version, more like what you and I are looking at now, so you also often hear
this algorithm called the Newton-Raphson method. These days it's a common topic in calculus
classes. One nice little exercise to try to get a feel for it, by the way, is to try using
this method to approximate square roots by hand. But what most calculus students
don't see, which is unfortunate, is just how deep things can get
when you let yourself play around with this seemingly simple procedure and
start kind of picking at some of its scabs. You see while newton's method works great
if you start near a root where it converges really quickly, if your initial guess is far
from a root it can have a couple foibles. For example let's take the function we
were just looking at but shifted upward, and play the same game with the same initial guess Notice how the sequence of new guesses that
we're getting kind of bounces around the local minimum of this function sitting above the
x-axis. And this should kind of make sense, I mean a linear approximation of the function
around these values all the way to the right is pretty much entirely unrelated to the nature of
the function around the one true root that it has off to the left. So they're sort of giving you
no useful information about that true root. It's only when this process just happens to throw
the new guess off far enough to the left by chance that the sequence of new guesses does anything
productive and actually approaches that true root. Where things get especially interesting is if
we ask about finding roots in the complex plane. Even if a polynomial like the one shown
here has only a single real number root, you'll always be able to factor this polynomial
into five terms like this if you allow these roots to potentially be complex numbers. This
is the famous fundamental theorem of algebra. In the happy-go-lucky land of functions with
real number inputs and real number outputs, where you can picture the association between
inputs and outputs as a graph, Newton's method has this really nice visual meaning with tangent
lines and intersecting the x-axis. But if you want to allow these inputs to be any complex number,
which means our corresponding outputs might also be any complex number, you can't think about
tangent lines and graphs anymore. But the formula doesn't really care how you visualize it. You can
still play the same game, starting with a random guess and evaluating the polynomial at this point,
as well as its derivative, then using this update rule to generate a new guess. And hopefully,
that new guess is closer to the true root. But I do want to be clear, even if we can't
visualize these steps with a tangent line, it really is the same logic. We're figuring out
where a linear approximation of the function around your guess would equal zero, and then
you use that zero of the linear approximation as your next guess. It's not like we're blindly
applying the rule to a new context with no reason to expect it to work. And indeed, with at least
the one I'm showing here, after a few iterations you can see that we land on a value whose
corresponding output is essentially zero. Now here's the fun part. Let's apply this idea to many
different possible initial guesses. For reference, I'll put up the five true roots of
this particular polynomial in the complex plane. With each iteration, each one of our little
dots takes some step based on Newton's method. Most of the dots will quickly
converge to one of the five true roots but there are some noticeable stragglers
which seem to spend a while bouncing around. In particular, notice how the ones that are
trapped on the positive real number line... well they look a little bit lost. And this
is exactly what we already saw before for the same polynomial when we were looking
at the real number case with its graph Now what I'm going to do is color
each one of these dots based on which of those five roots it ended
up closest to, and then we'll kind of roll back the clock so that every
dot goes back to where it started. As I've done it here, this isn't quite
enough resolution to get the full story, so let me show you what it would look like if we
started with an even finer grid of initial guesses and played the same game: Applying Newton's method
a whole bunch of times, letting each dot march forward, coloring each dot based on what root
it lands on, then rolling back the clock to see where it originally came from. But even this isn't
really a high enough resolution to appreciate the pattern. If we did this process for every single
pixel on the plane, here's what you would get. At this level of detail, the color scheme
is a little jarring to my eye at least, so let me calm it down a little. Really, whatever resolution I try to use to show this
to you here could never possibly be enough, because the finer details of the shape we
get will go on with endless complexity. But take a moment to think about
what this is actually saying. It means that there are regions in the complex
plane where if you slightly adjust that seed value, you know you just kind of bump it to the
side by 1 one-millionth or 1 one-trillionth, it can completely change which of the
5 true roots it ends up landing on. We saw some foreshadowing of this kind of
chaos with the real graph and the problematic guess shown earlier, but picturing all of
this in the complex plane really shines a light on just how unpredictable this kind
of root-finding algorithm can be, and how there are whole swaths of initial values where
the sort of unpredictability will take place. Now if I grab one of these roots and change it
around, meaning that we're using a different polynomial for the process, you can see
how the resulting fractal pattern changes. Notice for example how the
regions around a given root always have the same color since those are
the points that are close enough to the root where this linear approximation scheme works
as a way of finding that root with no problem. All of the chaos seems to be happening at the
boundaries between the region, remember that. And it seems like no matter where I place these
roots, those fractal boundaries are always there. It clearly wasn't just some one-off for
the polynomial we happen to start with, it seems to be a general fact
for any given polynomial. Another facet we can tweak here just to better
illustrate what's going on is how many steps of newton's method we're using. For example, if I had
the computer just take zero steps meaning it just colors each point of the plane based on whatever
root it's already closest to, this is what we'd get. And this kind of diagram actually has a
special name, it's called a "Voronoi diagram". And if we let each point of the plane
take a single step of Newton's method, then color it based on what root that single step
result is closest to, here's what we would get. Similarly, if we allow for two steps, we get a
slightly more intricate pattern, and so on and so on, where the more steps you allow the more
intricate an image you get, bringing us closer to the original fractal. And this is important, keep
in mind that the true shape we're studying here is not any one of these it's the limit as we allow
for an arbitrarily large number of iterations. At this point, there are so many
questions we might ask. Like, maybe you want to try this out with some
other polynomials see how general it is. Or maybe you want to dig deeper into what dynamics
are exactly possible with these iterated points, or see if there's connections with some other
pieces of math that have a similar theme. But i think the most pertinent question should be
something like, "what the **** is going on here?!" I mean, all we're doing here is repeatedly solving
linear approximations, why would that produce something that's so endlessly complicated.
It almost feels like the underlying rule just shouldn't carry enough information
to actually produce an image like this. And before seeing this don't you think a
reasonable initial guess might have been that each seed value simply tends towards whichever route
it's closest to? And in that case, you know, if you colored each point based on the root it lands
on and move it back to the original position, the final image would look like one of these
Voronoi diagrams with straight-line boundaries. Since I referenced earlier the unsolvability
of the quintic, maybe you would wonder if the complexity here has anything to do with that. That
would be cool, but they're essentially unrelated ideas. In fact using only degree-5 polynomials
so far might have been a little misleading. Watch what happens if we play the same game
but with a cubic polynomial with three roots somewhere in the complex plane. Notice how
again while most points nestle into a root some of them are kind of flying all over the place
more chaotically. In fact, those ones are the most noticeable ones in an animation like this, with
the ones going towards the roots just quietly nestled in to their ending points. And again if we
stopped this at some number of iterations and we colored all the points based on what root they're
closest to and roll back the clock the relevant picture for all possible starting points, it
forms this fractal pattern with infinite detail. However, quadratic polynomials,
with only two roots, are different. In that case, each seed value does simply
tend towards whichever root it's closest to, the way that you might expect. There is a
little bit of meandering behavior from all the points that are an equal distance from
each root, it's kind of like they're not able to decide which one to go to but,
that's just a single line of points, and when we play the game of coloring the diagram,
what we end up with is decidedly more boring. So something new seems to happen when you jump
from 2 to 3, and the question is what exactly? If you had asked me a month ago, I
probably would have shrugged and just said, you know math is what it is, sometimes
the answers look simple sometimes not. It's not always clear what it would mean
to ask "why?" in a setting like this. But i would have been wrong, there actually is a
reason that we can give for why this image has to look as complicated as it does. You see, there's
a very peculiar property that we can prove this diagram must have. Focus your attention on just
one of the colored regions, say this blue one. In other words, the set of all points that
eventually tend towards just one particular root of the polynomial. Now consider the
boundary of that region, which for the example shown on screen has this kind of nice
three-fold symmetry. What's surprising is that if you look at any other color and consider
its boundary, you get precisely the same set. Now when i say the word "boundary", you probably
have an intuitive sense of what it means, but mathematicians have a pretty clever way to
formalize it, and this makes it easier to reason about in the context of more wild sets like our
fractal. We say that a point is on the boundary of a set if, when you draw a small circle
centered at that point, no matter how small, it will always contain points that
are both inside that set and outside. So if you have a point that's on the
interior, a small enough circle would eventually only contain points inside
the set. And for a point on the exterior, a small enough circle contains no points of
the set at all. But when it's on the boundary, what it means to be on the boundary, is that
your tiny tiny circles will always contain both. So looking back at our property, one way to
read it is to say that if you draw a circle, no matter how small that circle is,
it either contains all of the colors, which happens when this shared boundary
of the colors is inside that circle, or it contains just one color, and this happens
when it's in the interior of one of the regions. In particular, what this implies is you should
never be able to find a circle that contains just two of the colors since that
would require that you have points on the boundary between two
regions but not all of them. And before explaining where this fact actually
comes from, it's fun to try just wrapping your mind around it a little bit. You could
imagine presenting this to someone as a kind of art puzzle, completely out of context, never
mentioning Newton's method or anything like that. You say that the challenge is to construct a
picture with at least three colors, maybe we say red green and blue, so that the boundary of
one color is the boundary of all of them. So if you started with something simple like this, that
clearly doesn't work because we have this whole line of points that are on the boundary of green
and red but not touching any blue. And likewise you have these other lines of disallowed points.
So to correct that you might go and add some blue blobs along the boundary and then likewise add
some green blobs between the red and blue and some red blobs between the green and blue. But of
course, now the boundary of those blobs are a problem, for example, touching just blue and
red but no green. So maybe you go and you try to add even smaller blobs with the relevant third
color around those smaller boundaries to help try to correct. And likewise you have to do this for
every one of the blobs that you initially added But then all the boundaries of those
tiny blobs are problems of their own and you would have to somehow
keep doing this process forever. If you look at newton's fractal itself this
sort of blobs on blobs on blob's pattern seems to be exactly what it's doing. The main thing i want you to notice is
how this property implies you could never have a boundary which is smooth or even
partially smooth on some small segment, since any smooth segment would
only be touching two colors. Instead the boundary has to consist
entirely of sharp corners, so to speak. So if you believe the property it explains why
the boundary remains rough no matter how far you zoom in, and for those of you who are familiar
with the concept of fractal dimension you can measure the dimension of the particular boundary
I'm showing you right now to be around 1.44. Considering what our colors actually
represent–remember this isn't just a picture for pictures sake–think about
what the property is really telling us. It says that if you're near a sensitive point
where some of the seed values go to one root but other seed values nearby would go to another
root, then in fact every possible route has to be accessible from within that small neighborhood.
For any tiny little circle that you draw either all of the points in that circle tend to just one
root or they tend to all of the roots but there's never going to be anything in between, just
tending to a subset of the roots. For a little intuition, I found it enlightening to simply
watch a cluster like the one on screen undergo this process. It starts off mostly sticking
together but at one iteration they all kind of explode outward and after that it feels a lot
more reasonable that any root is up for grabs. And keep in mind, i'm just showing you finitely
many points but in principle you would want to think about what happens to all uncountably
infinitely many points inside some small disk. This property also kind of explains why it's
okay for things to look normal in the case of quadratic polynomials with just two roots,
because there a smooth boundary is fine there are only two colors to touch anyway. To be clear,
it doesn't guarantee that the quadratic case would have a smooth boundary, it is perfectly possible
to have a fractal boundary between two colors, it just looks like our newton's method diagram
is not doing anything more complicated than it needs to under the constraint of
this strange boundary condition. But of course all of this simply raises
the question of why this bizarre boundary property would have to be true in the first
place, where does it even come from? For that, I'd like to tell you about a field of
math which studies this kind of question, it's called holomorphic dynamics. And I
think we've covered enough ground today, and there's certainly enough left to tell, so it
makes sense to pull that out as a separate video. To close things off here, there is something
sort of funny to me about the fact that we call this Newton's fractal despite the fact that
Newton had no clue about any of this, and could never have possibly played with these images the
way that you and I can with modern technology. It happens a lot through math that people's names
get attached to things well beyond what they could have dreamed of. Hamiltonians are central to
quantum mechanics despite Hamilton knowing nothing about quantum mechanics. Fourier himself never
once computed a Fast Fourier Transform. The list goes on. Tut this over-extension of nomenclature
carries with it what I think is an inspiring point. It reflects how even the simple ideas,
ones that could be discovered centuries ago, often hold within them some new angle or a new
domain of relevance they can sit waiting to be discovered hundreds of years later. It's not just
that Newton had no idea about Newton's fractal. There are probably many other facts about
newton's method, or about all sorts of math that may seem like old news, that come from
questions that no one has thought to ask yet. Questions that are just sitting there
waiting for someone like you to ask them For example if you were to ask about whether
this process we've been talking about today ever gets trapped in a cycle, it leads you to a
surprising connection with the Mandelbrot set, and we'll talk a bit about that in the next part. At the time that I'm posting this, that second
part, by the way, is available as an early release to patrons. I always like to give new content
a little bit of time there to gather feedback and catch errors. The finalized version should
be out shortly. And on the topic of patrons, I do just want to say a quick thanks to everyone
whose name is on the screen. I know that in recent history new videos have been a little slow coming.
Part of this has to do with other projects that have been in the works, things I'm proud of by
the way, things like the Summer of Math Exposition which was....a surprising amount of work, to be
honest, but so worth it given the outcome. I will be talking all about that and announcing winners
very shortly, so stay tuned. I just want you to know that the plan for the foreseeable future is
definitely to shift gears more wholeheartedly back to making new videos, and more than anything I
want to say thanks for your continued support even during times of trying a few new things. It means
a lot to me it's what keeps the channel going and I'll do my best to make the new lessons in the
pipeline live up to your vote of confidence there.
Great video as usual. One thing to point out is that a coloring with that boundary property doesn’t necessarily need to look anything like a Newton fractal. For example, there’s also the lakes of Wada.
If this is used in industry to solve quintics, how do they make sure they dont fall near one of these boundaries for their initial guess?
This video is aming me wonder how we would create a function that resists Newton's Method. Are there some functions we can create where no matter what value you select, Newton's Method forces you to go in a cycle?. You keep selecting the same points over and over again.
I need a spoiler, where does the boundary property come from?
What happens in the case where the polynomial has a multiple root (e.g. (z-r1)(z-r2)2 )?
Here’s what I want to see: a coloring for how many iterations it takes to get “close” to a root (I guess this would be like a standard fractal), and a graph of sin(z), where presumably the boundaries would be surrounded by infinitely many colors.
Give a non trivial function f(z) in complex numbers, is there a function g(z) that can return 1 if z will converge to a root of f using newton’s method and zero if it doesn’t. I am guessing this is undecidable