Newton's Fractal Explained — Full Breakdown & Transcript

[00:02] And actually it's an infinite family of fractals. shapes that has infinite detail no matter how far you zoom in.

[00:14] But this is not really a video about generating some pretty picture for us to gawk at. more pragmatic starting point than the story behind a lot of other fractals.

[00:26] meaningful if we make an effort to understand why, given what they represent, and what this complexity reflects about an algorithm that is used all over

[00:40] the place in engineering. and that you want to know when it equals zero.

[00:54] where it crosses the x-axis, and you can kind of eyeball what those values might be. But how do you actually compute them exactly?

[01:07] maybe it's interesting enough in its own right to move forward. 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,

[01:22] 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,

[01:34] that somehow involves solving an equation that uses these polynomials. When a computer renders text on the screen, those They're defined as a bunch of polynomial curves,

[01:49] what are known in the business as Bezier curves. maybe in some design software, would be well familiar with these kinds of curves. you need a way to tell each one of the pixels of your screen whether it

[02:06] 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. it's an interesting puzzle to figure out how each one of the pixels

[02:20] knows whether it should be colored in or not, just based on the pure mathematical curve. 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.

[02:36] You would think of it as a parametric curve that has some parameter t. is to compute the distance between your pixel and a bunch of sample points on that curve, But that's both inefficient and imprecise.

[02:52] 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,

[03:05] And if this were meant to be a full lesson on rendering vector graphics, But right now, the only salient point that I want to highlight is that in principle,

[03:17] 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.

[03:29] which is to say its derivative, again some polynomial, and you ask, So, to actually carry out this seemingly simple task of just displaying a curve,

[03:43] wouldn't it be nice if you had a systematic and general way to Of course, we could draw 100 other examples from 100 other disciplines, I just want you to keep in mind that as we seek the roots of polynomials,

[03:58] 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?

[04:12] 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,

[04:24] I once had a Pixar engineer give me the estimate that considering how many lights were 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

[04:39] trillions of times in the production of that film. things start to get trickier. which Mathologer has done a wonderful video on, and there's even a quartic formula,

[04:54] something that solves degree 4 polynomials, although honestly that one is uses it in practice. But after that, and I find this one of the most fascinating results in all of math,

[05:08] you cannot have an analogous formula to solve polynomials that have a degree 5 or more. you can prove that there is no possible way that you can combine those functions

[05:21] together that allows you to plug in the coefficients of a quintic polynomial and 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,

[05:36] equations with whatever level of precision you want. A common one, and the main topic for you and me today, is Newton's method. but I want you to pay attention to just how innocent and benign the whole

[05:53] The algorithm begins with a random guess, let's call it x0. so you haven't found a solution, it's some other value visible as the height of this

[06:06] So to improve the guess, the idea is to ask, when does a linear approximation to the function around that value equal 0? when does that tangent line cross the x-axis?

[06:23] function in the loose vicinity of some true root, the place where this approximation equals 0 should take you closer to that true root. and with polynomials you'll always be able to do that,

[06:38] you can concretely compute the slope of this line. how do you figure out the difference between the current guess and the improved guess? One way to think of it is to consider the fact that the slope of this tangent line,

[06:55] its rise over run, looks like the height of this graph divided by the length of that step. line is the derivative of the polynomial at that point. a super concrete way that you can compute that step size.

[07:12] So the next guess, which we might call x1, is the previous guess, And after that, you can just repeat the process. You compute the value of this function, and the slope, at this new guess,

[07:25] which gives you a new linear approximation, and then you make the next guess, And then apply the same calculation to x2, and this gives you x3, pretty much as close as you could ever want to be.

[07:44] and in this case, hopefully it does. you need to take a bigger step to get down to a root. But if p' of x is also large, meaning the graph is quite steep,

[07:59] you should maybe ease off on just how big you make that step. Now 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,

[08:12] more like what you and I are looking at now, so you also often hear this algorithm called These days it's a common topic in calculus classes.

[08:25] is to try using this method to approximate square roots by hand. is just how deep things can get when you let yourself play around with

[08:40] this seemingly simple procedure and start kind of picking at some of its scabs. where it converges really quickly, if your initial guess is far from a root,

[08:52] For example, let's take the function we were just looking at, but shift it upward, and play the same game with the same initial guess.

[09:07] Notice, how the sequence of new guesses we're getting kind of bounces around the local minimum of this function sitting above the x-axis. This should kind of make sense, I mean, a linear approximation of the function

[09:19] 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.

[09:31] off far enough to the left, by chance, that the sequence of new guesses does anything productive and actually approaches that true root. we ask about finding roots in the complex plane.

[09:48] 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.

[10:00] Now 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

[10:15] But if you want to allow these inputs to be any complex number, you can't think about tangent lines and graphs anymore. You can still play the same game, starting with a random guess,

[10:32] and evaluating the polynomial at this point, as well as its derivative, and hopefully that new guess is closer to the true root.

[10:45] But I do want to be clear, even if we can't visualize these steps with a tangent line, 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.

[11:01] 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.

[11:15] Let's apply this idea to many different possible initial guesses. this particular polynomial in the complex plane.

[11:27] 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.

[11:41] In particular, notice how the ones that are trapped on the positive real number line, And this is exactly what we already saw before for this same polynomial when we were looking at the real number case with its graph.

[11:56] 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 Now as I've done it here, this isn't quite enough resolution to get the full story,

[12:13] so let me show you what it would look like if we started with an even finer grid bunch of times, letting each root march forward, then rolling back the clock to see where it originally came from.

[12:29] 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. And at this level of detail the color scheme is a little jarring to my eye at least,

[12:44] 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 go on with endless complexity.

[13:01] 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,1 millionth or 1,1

[13:13] trillionth, it can completely change which of the five 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

[13:27] and how there are whole swaths of initial values where this sort of unpredictability Now if I grab one of these roots and change it around,

[13:39] you can see how the resulting fractal pattern changes. And 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

[13:53] 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 regions. And it seems like no matter where I place these roots,

[14:06] It clearly wasn't just some one-off for the polynomial we happened to start with, this seems to be a general fact for any given polynomial. what's going on is how many steps of Newton's method we're using.

[14:22] meaning it just colors each point of the plane based on whatever root it's already And this kind of diagram actually has a special name, it's called a Voronoi Diagram.

[14:36] And if we let each point of the plane take a single step of Newton's method, here's what we would get.

[14:50] Similarly, if we allow for two steps, we get a slightly more intricate pattern, 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

[15:05] one of these, it's the limit as we allow for an arbitrarily large number of iterations. Maybe you want to try this out with some other polynomials, see how general it is,

[15:21] 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 But I think the most pertinent question should be something like,

[15:34] I mean, all we're doing here is repeatedly solving linear approximations. Why would that produce something that's so endlessly complicated? carry enough information to actually produce an image like this.

[15:50] been that each seed value simply tends towards whichever root it's closest to? it lands on and move it back to the original position,

[16:04] straight-line boundaries. maybe you would wonder if the complexity here has anything to do with that. That would be cool, but they're essentially unrelated ideas.

[16:19] In fact, using only degree-5 polynomials so far might have been a little misleading. with three roots somewhere in the complex plane. some of them are kind of flying all over the place more chaotically.

[16:38] with the ones going towards the roots just quietly nestled in in 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,

[16:53] the relevant picture for all possible starting points forms this fractal pattern with infinite detail.

[17:05] 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, There is a little bit of meandering behavior from all the points that are an

[17:19] equal distance from each root, it's kind of like they're not able to decide and when we play the game of coloring, the diagram we end up with is decidedly So something new seems to happen when you jump from 2 to 3,

[17:35] And 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,

[17:49] 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. say this blue one, in other words, the set of all points that

[18:06] eventually tend towards just one particular root of the polynomial. example shown on screen has this kind of nice threefold symmetry. What's surprising is that if you look at any other color and consider its boundary,

[18:21] you get precisely the same set. Now when I say the word boundary, you probably have an intuitive sense of what it means, and this makes it easier to reason about in the context of more wild sets like

[18:35] 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.

[18:47] 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 But when it's on the boundary, what it means to be on the

[19:01] 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, it either contains all of the colors,

[19:14] 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.

[19:27] 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. it's fun to try just wrapping your mind around it a little bit.

[19:44] 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, maybe we say red, green, and blue, so that the boundary of one color is the boundary

[19:59] 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 and likewise you have these other lines of disallowed points.

[20:13] So to correct that, you might go and add some blue blobs along the boundary, 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,

[20:28] So maybe you go and 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.

[20:44] 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. And if you look at Newton's fractal itself, this sort of blobs

[20:57] on blobs on blobs pattern seems to be exactly what it's doing. The main thing I want you to notice is how this property implies you could

[21:10] never have a boundary which is smooth, or even partially smooth on some small segment, Instead, the boundary has to consist entirely of sharp corners, so to speak.

[21:23] boundary remains rough no matter how far you zoom in. you can measure the dimension of the particular boundary I'm showing you right now to be

[21:37] Considering what our colors actually represent, 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

[21:52] to one root but other seed values nearby would go to another root, then in fact every possible root has to be accessible from within that small neighborhood. For any tiny little circle that you draw, either all of the points in that

[22:05] but there's never going to be anything in between, just tending to a subset of the roots. a cluster like the one I'm showing on screen undergo this process.

[22:20] 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. but in principle you would want to think about what happens

[22:37] to all uncountably infinitely many points inside some small disk. This property also kind of explains why it's okay for things to look because there a smooth boundary is fine, there's only two colors to touch anyway.

[22:56] To be clear, it doesn't guarantee that the quadratic case would have a smooth boundary, it just looks like our Newton's method diagram is not doing anything more

[23:08] 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?

[23:22] For that I'd like to tell you about a field of math which studies this kind of question, And I think we've covered enough ground today, and there's certainly enough left to tell, To close things off here, there is something sort of funny to me about

[23:38] Newton had no clue about any of this, and could never have possibly played with these images the way you and I can with modern technology. attached to things well beyond what they could have dreamed of.

[23:54] despite Hamilton knowing nothing about quantum mechanics. Fourier himself never once computed a fast Fourier transform, the list goes on. But this overextension of nomenclature carries with it what I think is an inspiring point.

[24:10] 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 that It's not just that Newton had no idea about Newton's fractal.

[24:25] 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.

[24:42] 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.

[24:55] by the way is available as an early release to patrons. of time there to gather feedback and catch errors. On the topic of patrons, I do just want to say a

[25:08] I know that in recent history new videos have been a little slow coming. Things I'm proud of, by the way, things like the Summer of Math Exposition,

[25:20] 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

[25:33] and more than anything I want to say thanks for your continued support, It means a lot to me, it's what keeps the channel going, of confidence there.