# Newton’s fractal (which Newton knew nothing about) ## Метаданные - **Канал:** 3Blue1Brown - **YouTube:** https://www.youtube.com/watch?v=-RdOwhmqP5s - **Дата:** 12.10.2021 - **Длительность:** 26:05 - **Просмотры:** 3,094,080 - **Источник:** https://ekstraktznaniy.ru/video/16182 ## Описание Who knew root-finding could be so complicated? Next part: https://youtu.be/LqbZpur38nw Special thanks to the following supporters: https://3b1b.co/lessons/newtons-fractal#thanks An equally valuable form of support is to simply share the videos. Thanks to these viewers for their contributions to translations German: Luatic Hebrew: Omer Tuchfeld Portuguese: luiz12apn ------------------ Interactive for this video: https://www.3blue1brown.com/lessons/newtons-fractal On fractal dimension: https://youtu.be/gB9n2gHsHN4 Mathologer on the cubic formula: https://youtu.be/N-KXStupwsc Some articles on Newton's Fractal, and its cousins: https://www.chiark.greenend.org.uk/~sgtatham/newton/ https://blbadger.github.io/polynomial-roots.html Some of the videos from this year's Summer of Math Exposition are fairly relevant to the topics covered here. Take a look at these ones, The Beauty of Bézier Curves https://youtu.be/aVwxzDHniEw The insolubility of the quintic: https://youtu.be/BSHv9Elk1MU ## Транскрипт ### Intro [] You've seen the title, so you know this is leading to a certain fractal. And 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. ### Roots of polynomials [0:48] 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. For the one graphed here, you can visually see there's 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, what are known in the business as Bezier 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, and 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 100 other examples from 100 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. Now, 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, and 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 5 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. ### Newton’s method [5:55] The algorithm begins with a random guess, let's call it x0. Almost certainly, the output of your polynomial at x0 is not 0, 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 0? 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 0 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 kind of 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 of 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' of x is also large, meaning the graph is quite steep, 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, and a fellow named Joseph Rafson 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-Rafson 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 shift it upward, and play the same game with the same initial guess. 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 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. 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 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. ### The fractal [11:16] 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 this 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. Now 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 root 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. And 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 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,1 millionth or 1,1 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 light on just how unpredictable this kind of root finding algorithm can be, and how there are whole swaths of initial values where this 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. 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 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. 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 happened to start with, this 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, and 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. 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 here 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 root 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. And 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 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 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 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 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? 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, 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. ### The boundary property [17:56] 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 threefold 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 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, 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, where 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 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. And if you look at Newton's fractal itself, this sort of 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 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 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 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 I'm showing 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's 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. ### Closing thoughts [23:13] 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 you and I can with modern technology. And 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. But this overextension 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 that 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. 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.