Root-finding fractals

If I understood correctly, "fractality" of the plot is a measure of the inaccuracy of the root finding method. What kind of fractals the other root finding algorithms produce?

For Degree >= 3, it's fractal. If I recall correctly, any "boundary" point between basins of attraction for any roots must be a boundary for the basins of all the roots. With >= 3 distinct roots, this makes a fractal-y nested structure at the boundaries.

Do quaternions change the solvability?

Mike O'Dell

You've elevated my spirit. Finding fractal geometry in the solution of a simple polynomial inspires awe and wonder. I would encourage you to keep this a separate video, though link it in your introduction to the larger project of the impossibility of finding a closed solution to the roots of a quintic equation. I'm eager to see your Arnol'd-inspired solution. Thank you for all you do, and for how effectively, elegantly and beautifully you do it.

Robert Berkowitz

As I understand it the proof is regarding polynomials of degree 5 or higher. In the lower degree cases you can find the exact roots, so it is manifested in the corresponding images as "simple" boundaries instead of fractals.

gorgeous

Leonardo Taglialegne

If there’s a way to do this without breaking the flow of the video, you might mention something about how moving the roots around (as you do when showing how the fractal changes) necessarily changes the original polynomial from a real one to a complex one, as it breaks the complex conjugate symmetry of the roots. Or maybe you could change the programming so that, when you drag a root around, its conjugate root moves in a similar fashion to preserve that symmetry? Just a thought 😄

Dan Kinch

I support making this its own video and linking to it in the quintic unsolvability video! I feel making it an integrated part of that video might take us a bit far afield, and especially for people who are struggling to follow the main through-line of the quintic video, diverging into a discussion of fractals might lose them entirely. A quick “by the way, running Newton’s method in the complex plane generates some really interesting patterns” ought to do the trick 😊

Dan Kinch

I’m not quite convinced that “the fractal is a manifestation of the proof that you can’t find the exact roots”… to see whether this is the case, i suspect we’d need to run Newton’s method on polynomials of degree 4 or lower in the complex plane, and see whether we still get fractals in those cases 😊

Dan Kinch

This is a general opinion I have of most fractal videos/content, but one angle of fractals that I'd like to see discussed more is the sheer inevitability of the image being a fractal. Sometimes the narrative focuses mostly on "look how we've made an infinitely complex object emerge from simple arithmetic" but also interesting is "how could it NOT be infinitely complex, considering the underlying math is undecidable?". For the quintic the fractal is a manifestation of the proof that you can't find the exact roots, or for the Mandelbrot set it's a manifestation of the undecidability of whether the value will ever shoot off to infinity. That isomorphism is really fascinating to me because they're expressed in such highly different forms.

So beautiful. Sometimes math study doesn't have to have any particular purpose, it's just really really pretty.

Rosuav

https://github.com/3b1b/videos/blob/master/_2021/poly_fractal.py https://github.com/3b1b/manim/tree/quintic/manimlib/shaders/poly_fractal In general, all source code should be visible (at least eventually) in that repo.

3blue1brown

You hit the nail on the with 1&2 for why any narrative connection here is probably too loose to lean on in any way. I do see a slight qualitative difference between something like Newton's method and Descarte's method of signs, at least as they relate to the Vladimir Arnold-inspired proof that I'll show. I do want to include some discussion about the squishiness of an expression like "closed-form", so thank you for comments 3-5.

3blue1brown

I did see that one, which is indeed quite beautiful. As to time limits, what I said in the description is that people are welcomed to make longer videos since those are often the best IMO, it's just that for the sake of judging it should be understood that someone judging it's quality should be able to do so within 5-10 minutes.

3blue1brown

With the increased steps, it is the same polynomial at each interaction. The thing that's changing is the number of times we let each seed value undergo an update from Newton's method. The color of a pixel is always determined by what root the seed starting at the pixel will end up closest to after n steps, its just that n is changing.

3blue1brown

I'll be sure to show it in an expanded video here, but you get similar patterns for cubics (just a little less complex).

3blue1brown

Interesting, I never thought about that. I'll put that on the now-fast-growing list of things to try.

3blue1brown

Yes, I think any final video here should make a connection to Mandelbrot (which is evidently a closer connection than I initially realized). As usual, the tooling for it all is manim: https://github.com/3b1b/manim https://github.com/3b1b/videos/blob/master/_2021/poly_fractal.py

3blue1brown

Nice!

3blue1brown

Damn this is a really good question; I'm wondering the same thing now.

Adam

My immediate desire is - I wanna know what this looks like for degree<5. In other words, is it significantly less fractal-esque, or are we choosing 5 simply because we absolutely need an approximation? No matter which answer that is, I still wanna see it! I'd also be interested if degree>5 is different in any significant way.

C.J. Smith

This is beautiful! Make it its own video, please :) What's the connection to the Mandelbrot set and Julia sets?

Rion Boom Crabhands Keon

Wow, ingenious, illuminating - great stuff Grant!

's method to

Wonderful video as always. Would love a hint at why these patterns show up here or with any other function you might apply Newton

can you change intensity or color saturation based on how many steps a given point takes until it converges to a solution?

This is beautiful! Would this fractal go away if a continuous time version of Newton's method is used?

Memming Park

There were a couple of good points here already about connections to the Mandelbrot set, and I think this would be a great addition to the video, showing how in both cases we have an iterated map over the complex numbers and it's long term behavior gives this fractal structure. I was also curious what tool you used for the dynamic parts where you dragged around the roots.

Eric Severson

Some years back I was using Newton's Method to on a couple of transcendental equations to find roots for them within a specific region for a project that I was working on. This graphic representation is an eye-opener. I can see in your representation that something that might have appeared chaotic in regions could be fractal behavior! Wow.

It looks to me like the fractal behavior appears when the algorithm crosses a local minimum or maximum to get from the initial point to the root. I don't believe that a quadratic function will do that, but a cubic or any higher degree could.

MBP

I decided to build a little of this in Smoothstep.io. https://www.instagram.com/p/CTKm7usFW0J/

Kevin McCurdy

Regarding "the unsolvability of the quintic" ( https://en.wikipedia.org/wiki/Abel%E2%80%93Ruffini_theorem ), I had read about that as a high school student, but I was really surprised to learn years later that there are algorithms for solving polynomials of arbitrary degree ( https://en.wikipedia.org/wiki/Factorization_of_polynomials , https://en.m.wikipedia.org/wiki/Berlekamp%27s_algorithm ), and if I'm not mistaken these solve them exactly, not numerically like Newton's method. It would be great if your video mentions this.

Michael McGuffin

Delightful, thanks for the added detail!

3blue1brown

I know about Newton's method, I know how to generate a fractal (Mandelbrot's or Julia's), I understand every word you say in that video and if you had just told me "try to use Newton's method on a complex plain to generate a fractal", maybe I could have done that instead of you... But how do you connect the dots and actually think about doing that? Mark Rober has a course where he explains how he thinks as an engineer. Do you think you could make a video explaining your train of thought? Because being a mathematician is more than just applying formulas and solving equations, it's also being able to find a way to make a 350 years old method work with a computer era geometric shape. Such a video, not about maths, but about the mathematician himself, would be amazing!

Oltarus

Hey, Grant! Thanks for an exciting and visual video about Newton's method! I happened to work on it from the perspective of holomorphic dynamics and I wanted to give some more comments and suggestions about the topic. 1) The fractal behavior and the beauty of the picture always arises when you start to iterate something. This is a principle of holomorphic dynamics: Julia sets of complex functions (almost) always have intricate details which look stunning when shown in a correct color scheme. What we look at here are filled-in Julia sets of so-called Newton function, they are rational functions you get when you write down Newton's method for a polynomial. The roots of p are the attracting/ superattracting points of the Newton function, infinity is a repelling point, there is a lot of similarity with polynomial filled-in Julia sets (even z^2+c). 2) Maybe another nice visual thing to speak about and show are the points of non-convergence. When we draw a Newton fractal we might ask ourselves whether all points on the plane converge to some root, in other words how careful we need to be when picking a starting point for iteration. Quite clearly there is a fractal boundary between basins of attraction of various roots, this is the Julia set of Newton function and it is invariant, but it has 0 measure. However it is possible that Newton function has (super-)attracting cycles which don't converge to roots, e.g. this happens for z^3-2z+2, you can find a picture here: (https://www.math.stonybrook.edu/~scott/Papers/Newton-HSS.pdf, Figure 1). This is what one should expect from dynamical systems: many inconvenient things that may happen will, in fact, happen for some dynamical systems. 3) There is even a catchy connection between Newton fractals and the Mandelbrot set! If you try to visualize a parameter plane for Newton maps for degree 3 polynomials, you get some fractal in complex plane and inside this fractal there will be clearly visible Mandelbrot set. Some details are here on slides 15-16: (http://math.jacobs-university.de/archive/summerschool/handouts2015/Dierk_Schleicher_Newton_SummerSchool2015.pdf) 4) Also Newton's method doesn't just produce nice pictures, it is a reasonably efficient root-finding method that can be theoretically analyzed using tools of holomorphic dynamics. Here is a paper where some polynomials of degree 1 million are solved: https://arxiv.org/abs/1508.02935, there is a follow-up where they get it 1 billion. Anyway, I could be going on and on with this :) If you are interested to learn even more or get some clarifications on what I wrote, please feel free to reach out to me! Best, Sergey.

One, it's beautiful and you should make a separate video on it. Two, source code please?

Poker Chen

Let me give a short description of the first paper: it's a theoretical paper which shows how you can pick the starting points to find the roots of any polynomial. It also computes the asymptotics of the number of starting points and algorithmic complexity (depending on the degree of the polynomial). It's very nice because it defines several very useful notions to speak about the Newton fractals: immediate basins, channels, widths of channels to name some.

Hey, Dave! I have the answers to your questions :) The fractals that you see here happen sort of for all holomorphic functions. You can define the complex Newton method for all functions where f' exists and the domains of convergence will look really similar in spirit, independently of the function. You can do this for degree 2 polynomial, degree 1000 polynomial, you can even do this to the exponential function. There will be clearly visible domain of convergence, one for each root, and fractal fuzzy behavior on the boundary. The fractal behavior is only related to the fact that there is some sort of iteration going on.

Can polynomials of lower degree (2,3,4) also have the same kind of fractal behavior? The shapes that this process creates are really beautiful. This space would be fun to explore to see what artistic results come out of some situations. (for example double roots)

William Smith

After viewing the video, I thought it should be a stand-alone. After reading the comments, I think it should be the first in a series!

An animation of the rotational CORDIC algorithm as it finds sin or cos would be illuminating, along the lines of how you've shown the Newton method of approximation in this video. CORDIC was the method of choice for computing transcendental functions in handheld calculators and signal processors (aka bomb sights) before there were multiplier functions embedded in microprocessors. An elegant and flexible digital algorithm.

This is very beautiful. I would make it another video, though. For the following reasons, beyond the length. 1. The fractal character has nothing to do with solvability by radicals. 2. There are other ways to solve quintics. Descartes's method of signs, together with binary search, is not subject to the same problems as Newton's method, though it is not as fast. 3. There is a closed form solution to the quintic, if you allow elliptic functions, due to Hermite. This is like the trigonometric solution of the cubic. You will find this in Klein's book, "Lectures on the Icosahedron" 4. You can put any quintic in terms of a certain form with one variable, called Bring's form, which means if you define a function to be the solution to such a Bring quintic, then that function, together with +, -, *, /, and radicals, can be used to solve any quintic. A similar statement could be made for sextics. 5. The question of whether there is a function in 1 variable that will help solve the septic is Hilbert's 13th problem and depends on what you mean by a "function".

Kevin Iga

I taught this long, long ago, to enhance a little unit in calculus on Newton's method. I used images created on a Commodore 64. I called this "Newton's Nightmare" for the example and invite you to do the same!

Very nice video! You may find interesting either the paper by Hubbard, Schleicher and Sutherland https://www.math.stonybrook.edu/~scott/Papers/Newton-HSS.pdf or the very well known more general paper by McMullen https://people.math.harvard.edu/~ctm/papers/home/text/papers/braids/braids.pdf

Concerning the topic of this video: I love the topic. I don't know how much you want to expand this. But if you want to talk about lower degrees than 3 and chip in a little historical trivia bit, I think I once read in James Gleick's "Chaos - Making a new Science" that John Hubbard supposedly was surprised by this behavior for deg>2 after answering a student's question .

Lionel Pöffel

Concerning the larger project "unsolvability of the quintic", you might take a look at one of the SoME1 submissions: https://www.youtube.com/watch?v=BSHv9Elk1MU I find it very beautiful (although perhaps a bit long given the 5-10min limit of the contest)

Lionel Pöffel

Can you maybe also try to do it on the Riemann sphere, where you add the point at infinity (which at least in this case is another fixed point of the operation)? I think that the image will be even more natural there in a sense. Anyway, as some people already wrote, I think that this should be mentioned together with the standard goto chaos fractals from the Julia\Mandelbrot set (and then convince them to change the standard to this operation of finding roots, which I now think is much more natural...)

I NEED to see this same animation but for complex polynomials of varying degrees. Do quadratics or cubics also produce fractals? What about other analytic functions that have roots? Is this fractal behavior related to the unsolvability of quintics by radicals or is it better explained as a feature of the iterative nature of Newton's method? PLEASE Grant T_T

That's great. I love this video by itself. I am currently researching gradient descent using second-order directional Newton Methods. Maybe you could do something with that. It is pretty nische but maybe interesting for you and your audience. Take it as a loose recommendation. Have a look at AdaSecant in case you are interested https://arxiv.org/abs/1412.7419.

Do you have a link to what you were using to create the fractal and drag the points around?

Soon, my friend, soon…

3blue1brown

This is really cool! This probably would work as a supplemental video the same way you did the 256 bit security supplement to the block chain video

Stephen Phillips

I'm curious why polynomials with degree <=4 have closed-form solutions, and degree >=5 don't.

A semi-related tangent: this reminds me of a different fractal, where a pendulum is placed between three magnets. The pendulum will definitely stop at one magnet, and the behavior shows the same extreme sensitivity to initial conditions: http://fractalfoundation.org/OFC/OFC-7-2.html Of course I'm also curious whether there's any fundamental relationship between these two problems, but that's an even further tangent. It might be nice to toss this in for 5-10 seconds, just to show that the same type of behavior also shows up in real-world systems.

I really like how the variable steps give a more intuitive explanation of how these weird shapes can arise from simpler geometries. Complex Mandelbrot-style fractals always seemed fundamentally different to me from Sierpinski-style fractals that are just collections of basic shapes.

Pithonian

Surprisingly soothing to watch.

This should 100% be its own video, and this should be just the beginning. This is a great surprising mystery type setup to a really substantive explanation of some technical concept - like the crashing pi blocks video, etc.

Sachin Shukla

Just want to chime in to say that this video was beautiful. I agree that it can definitely be it's own video. Especially if you expand it to explore polynomials of different degrees and if you also explore points that never reach a root! Also just wanted to say that the point where you drag around the roots with your mouse and it dynamically computes the fractal (at least it looked like that was real-time?) was quite technically impressive! Kinda want to code this thing myself now haha!

Cool video. Minor suggestion -- I assume at the part near the end when you are showing what happens when you only do one step of Newton's method, or two steps, that you are changing the polynomial to make the picture change. You might want to mention that. I am also curious about how many steps you used for the most detailed pictures (like at the very end of the video). Also, when you first start coloring the dots, it is hard (at least for me) to distinguish the five colors. Maybe just start out with the color scheme that you use later?

MBP

I'd love to see a side video where you explore various different iterative processes related to Newton fractals, Julia and Mandelbrot sets, etc. In particular, what their potential uses are, other than their beauty, such as helping to visual the problem in an original way (something you tend to focus on anyway) and pointing to possible new approaches to solving problems like the zeroes of the Zeta.

Stacey Greenstein

What happens if you replace Newton's method by an approximation of Newton's method, where derivatives are replaced by difference quotients, maybe based on the most recent two iterates, so that it's still super-linearly convergent?

Completely beautiful, as always.

Good point, I'll be sure to make a mention of that. It strikes me as a fun puzzle to dig into why that particular cycle 1) arises, and 2) is attractive.

3blue1brown

Will do, thanks!

3blue1brown

Hi Max, Good question! First off, I should mention this actually also happens with cubic polynomials (and others with 3+ roots), it's not unique to quintics. If you think about the real case, you can perhaps convince yourself that no points will approach infinity, since if you go far enough to the right the value and slope of the function will both be positive, which means the tangent line intersection point will be farther to the left. Likewise, if you get flung out to the left too far, the value is negative with a positive slope, which pushes you back to the right. There is the (measure zero) possibility that you land on a point where P'(x) = 0, in which case the next step of Newton's method is undefined, or perhaps if you're thinking projectively the next step takes you to the point at infinity. It's a similar story with the complex case as well. For huge values of z, P(z) basically looks just like z^5, and P'(z) basically just looks like 5z^4. So the step size of - P(z) / P'(z) would evaluate to something which is approximately -z^5 / (5z^4) = -(1/5)z. Note, this points directly back at the origin. Now, all of this is to say that you can't approach infinity, but the other way to avoid approaching a root is to fall into a cycle. This is certainly possible (fun puzzle to construct a 2 cycle!), and in some cases the cycles can actually be attractors, meaning nearby points will tend to fall into that cycle rather than approaching any particular root. I think this would be a very fun topic to explore for a future expansion here!

3blue1brown

It's a good idea, I can show some of that.

3blue1brown

Certainly not on purpose, just a last minute title thrown in without double checking. Thanks for the catch!

3blue1brown

Excellent. It would be interesting to see a similar approach to polynomials of different powers - higher or lower than the quintic.

John Klinkner

Wow! it's getting better and better! Thanks!!

Great stuff. If you decide to make a separate video (which I think you should), I would like to learn a bit more on how you define an "infinitely complex" pattern, and how you prove it such. Sure it looks fractalish in the anymation, but that's not proving anything, it might just be very complex but still "finitely complex".

Andrea Bedin

This was a joy to watch :) It can totally be its own video. Maybe publish a few days before or after the main video. A nice addition would be to show what happens if you add more roots, or move roots together into a double or tripple root.

Nice! I'd only mention, for the sake of completeness, that the fractal can have periodic attractors, as shown on https://en.wikipedia.org/wiki/Newton_fractal for z^3 - 2z + 2. (Minor point: I'd have expected you to draw the tangent line around 2:15 rather than 2:05, just to line up with you saying "tangent line". But I guess it depends on whether this is meant as an introduction to or a refresher of Newton's method.)

This was wonderful. Thank you for it. I would also like to applaud your naming the mathematical tool "Newton's method" explicitly.

Burt Humburg

This is very good. The illustration of that issue with Newton's method in 1-D is very enlightening. This would be a great video to have on its own, analysis on the rate of convergence might round it out if you think it's not long enough, but that could probably be its own video too. I would be very interested in rate of convergence content.

Jeremy

I think you did a great job with the progressive explanation, I was able to say, "yup, I could code that up if I wanted to" each step of the way. If there's one thing that's missing, it's how does this relate to other fractals like the Mandelbrot set? That one has to do with points being attracted in or flung to infinity, which makes me wonder: is it true that for any quintic (or higher?), does every point on the complex plane eventually converge to a root? Or do some oscillate forever or go to infinity?

Max Goldstein

Interested to see this for other numbers of roots. Especially wondering whether/how the complexity varies.

Kevin McCurdy

I love the aha moment when you increase resolution to reveal the fractals. Grant magic. You did misspell "unsolvability" at the start of the video unless that's some clever reference I missed :-)

Ron Goodman

I would like to know the answer to this as well please !

This definitely deserves to be a video of its own.

Bob Dowling

Great video. The only question I have is whether this chaos is intrinsic only to Newton's method, or whether it exists for other approximate root finding techniques as well.

Brian Michalowski

I found this very enlightening. I saw newton's method before and understood how it works for functions of one variable, but the process of visualizing the root-finding steps by using two 2d graphs of complex plane was a big aha moment for me. This video was a big eye-opener for me even in the current form.

Jan Hrček

Maybe you're referring to these? https://youtu.be/M7k5AfKXFKE https://youtu.be/mN08b25xgX8 Apologies for the low audio quality there.

3blue1brown

It happens with cubics as well, which would certainly be worth mentioning in an expanded version of this. The fractal nature has more to do with points where the process is unstable, not so much the solvability of the polynomial, which has more to do with the nature of how you can permute its roots. The connection I was planning to make to unsolvability was more to emphasize that quintic (and higher) polynomials are perfectly solvable in a certain sense, but the other method available often come with drawbacks that make you wish for a closed formula akin to the quadratic. Even the quadratic requires some approximating algorithm, at the point of evaluating square roots, but there is a qualitative difference between the algorithm there and something like Newton's method.

3blue1brown

Does this only happen with quintics? Or does it happen with solvable polynomials too? Does the fractal nature have anything to do with the fact it isn't solvable?

where can i find ben, ben and blue patreon episode???? BTW THANKS to you i understood trig functions and log from lockdown math. Really appreciate your hard work :)

Sanveer Singh