Newtons Method for solving polynomials

From: 3blue1brown

Newton’s Method is a powerful algorithm used to find approximate solutions, or “roots,” for equations, particularly polynomials. While the method itself appears innocent, its application to finding complex roots of polynomials gives rise to intricate, infinitely detailed fractal shapes known as Newton’s fractals [00:00:05]. Understanding these fractals provides insight into the algorithm’s behavior and unpredictability [00:00:33].

The Problem: Finding Polynomial Roots

A fundamental problem in mathematics and engineering is determining when a polynomial equals zero [00:00:51]. These points are called the “roots” of the polynomial [00:01:01].

Practical Applications

While seemingly abstract, finding polynomial roots is crucial in many engineering fields [00:01:18]. One significant area is computer graphics [00:01:26]:

Pixel Coloring: Determining how a pixel should be colored often involves solving equations that use polynomials [00:01:30].
Font Rendering: Digital fonts are typically defined by polynomial curves, specifically Bezier curves [00:01:47]. To display these on a screen, each pixel must be evaluated to see if it should be colored in [00:02:02].
- Stroke Width: Calculating the distance of a pixel from a mathematical curve (which has zero width) is often required [00:02:27]. The square of this distance can be expressed as a polynomial [00:03:01]. Finding the minimum of this distance (and thus whether a pixel is within the stroke) involves taking its derivative (another polynomial) and finding where it equals zero [00:03:29].

Limitations of Exact Formulas

For lower-degree polynomials, exact formulas exist:

Quadratic Formula: Solves degree 2 polynomials (e.g., $a x^{2} + b x + c = 0$ ) [00:04:12]. This formula is used trillions of times in computer graphics for complex scenes, such as in the movie Coco [00:04:24].
Cubic Formula: Solves degree 3 polynomials [00:04:48].
Quartic Formula: Solves degree 4 polynomials, but is too complex for practical use [00:04:54].

However, for polynomials of degree 5 or higher (quintic and above), there is no general algebraic formula that can express their roots using standard functions (addition, subtraction, multiplication, division, and root extraction) [00:05:08]. This is known as the “unsolvability of the quintic” [00:05:27]. This limitation necessitates the use of approximation algorithms [00:05:36], of which Newton’s Method is a common example [00:05:43].

Newton’s Method Explained (Real Numbers)

Newton’s Method is an iterative numerical technique for finding increasingly better approximations to the roots of a real-valued function.

The Algorithm

The process begins with an initial guess, $x_{0}$ [00:05:55]. Since $P (x_{0})$ is likely not zero, the goal is to improve this guess [00:05:59].

Linear Approximation: At $x_{0}$ , a tangent line to the polynomial’s graph $P (x)$ is drawn [00:06:16]. This tangent line serves as a linear approximation of the function around $x_{0}$ .
Next Guess: The point where this tangent line crosses the x-axis is taken as the next, improved guess, $x_{1}$ [00:06:19]. The assumption is that if the tangent line is a good approximation, its root will be closer to the true root of $P (x)$ [00:06:26].
Iteration: This process is repeated with $x_{1}$ to find $x_{2}$ , and so on, until the guesses converge to a root with the desired precision [00:07:18].

The Formula

The slope of the tangent line at $x_{0}$ is given by the derivative of the polynomial, $P^{'} (x_{0})$ [00:07:00]. Using the rise-over-run concept for the slope: $P^{'} (x_{0}) = \frac{P ( x _{0} ) - 0}{step size}$ [00:06:55]

Rearranging for the step size, we get: $step size = \frac{P ( x _{0} )}{P ^{'} ( x _{0} )}$ [00:07:05]

The next guess, $x_{1}$ , is then calculated as: $x_{1} = x_{0} - \frac{P ( x _{0} )}{P ^{'} ( x _{0} )}$ [00:07:12]

This generalizes to the iterative update rule: $x_{n + 1} = x_{n} - \frac{P ( x _{n} )}{P ^{'} ( x _{n} )}$

Intuition Behind the Formula

If $P (x)$ is large (graph is high), a bigger step is needed to reach the x-axis [00:07:49].
If $P^{'} (x)$ is large (graph is steep), the step size should be smaller, as the function quickly approaches the x-axis [00:07:55].

History

This method is also known as the Newton-Raphson method, as Joseph Raphson published a simpler version than Newton’s original formulation [00:08:12]. It is a common topic in calculus classes [00:08:22] and can be used to approximate square roots [00:08:28].

Limitations in Real Numbers

While generally effective when starting near a root, Newton’s Method can exhibit “foibles” if the initial guess is far from a root [00:08:45]. For example, the sequence of guesses might bounce around a local minimum above the x-axis, providing no useful information about a distant true root [00:09:07]. Convergence to the root only occurs by chance if a new guess happens to fall sufficiently close to it [00:09:31].

Newton’s Method in the Complex Plane

The true complexity and fascinating behavior of Newton’s Method emerge when applied to finding roots in the complex plane [00:09:42].

Fundamental Theorem of Algebra

A key concept in complex numbers is the Fundamental Theorem of Algebra, which states that any non-constant polynomial with complex coefficients has at least one complex root. More specifically, a polynomial of degree $n$ will always have exactly $n$ complex roots (counting multiplicity) [00:09:52].

Applying the Formula

Even though the visual interpretation of tangent lines and graphs doesn’t apply to complex inputs and outputs, the iterative formula for Newton’s Method remains valid in the complex plane [00:10:16]: $z_{n + 1} = z_{n} - \frac{P ( z _{n} )}{P ^{'} ( z _{n} )}$ where $z$ is a complex number. The underlying logic of using a linear approximation to find the next guess still holds [00:10:49].

When many different initial complex guesses are simultaneously tracked, most quickly converge to one of the polynomial’s roots [00:11:32]. However, some “stragglers” spend a while bouncing around, similar to the real-number case [00:11:36].

The Newton’s Fractal

To visualize the behavior of Newton’s Method in the complex plane, each initial guess (represented as a pixel) is colored based on which of the polynomial’s roots it ultimately converges to [00:11:56]. When this is done for every pixel in a region of the complex plane, the resulting image is a Newton’s fractal [00:12:33].

Characteristics

Infinite Detail: Newton’s fractals exhibit infinite detail, meaning no matter how far one zooms in, new intricate patterns and complexity are revealed [00:00:11].
Sensitivity to Initial Conditions: The fractal illustrates regions where a minuscule change in the initial guess can lead to convergence to a completely different root [00:13:04]. This highlights the inherent unpredictability of the root-finding algorithm in certain areas of the complex plane [00:13:27].
Root Influence: Regions immediately surrounding a specific root will consistently lead to that root, as the linear approximation works well in that vicinity [00:13:45].
Variability: The fractal pattern changes depending on the specific polynomial and the placement of its roots [00:13:37]. However, the fractal boundaries are consistently present regardless of root placement for polynomials of degree 3 or higher [00:14:04].
Iterations: The intricacy of the fractal increases with the number of iterations of Newton’s Method applied [00:14:54]. The “true” fractal is the limit as an arbitrarily large number of iterations is allowed [00:15:01].
- Voronoi Diagram: If zero steps of Newton’s Method are taken, and pixels are colored based on their closest root, the result is a Voronoi diagram, which has straight-line boundaries and lacks fractal complexity [00:14:22].

Why the Complexity? The Boundary Property

The unexpected complexity of Newton’s fractals, particularly the endlessly complicated boundaries between convergence regions, stems from a peculiar mathematical property [00:15:36].

The Shared Boundary Property

For polynomials with three or more roots, a surprising property emerges: the boundary of any one colored region (representing convergence to a specific root) is precisely the same set as the boundary of all other colored regions [00:18:17].

Mathematically, a point is on the “boundary” of a set if any arbitrarily small circle centered at that point contains points both inside and outside the set [00:18:36].

This property implies that if you draw any small circle on the complex plane, it either contains only points that converge to a single root (if it’s in the interior of a region) or it contains points that converge to all possible roots (if it intersects the shared boundary) [00:19:10].
Crucially, you should never be able to find a circle that contains points converging to just two of the colors/roots [00:19:27].

Implications for the Fractal Shape

This shared boundary property explains the fractal nature:

No Smooth Boundaries: If a boundary segment were smooth, it would only be touching two colors [00:21:06]. Since the boundary must touch all colors (for 3+ roots), it must consist entirely of “sharp corners” and intricate, self-similar structures [00:21:18]. This means the boundary remains rough at any zoom level [00:21:23].
Unpredictability: Near a “sensitive point” on this boundary, a slight adjustment to the initial guess means that every possible root is accessible within that small neighborhood [00:21:48].
“Blobs on Blobs”: The visual appearance of the fractal, with its nested “blobs on blobs” pattern, is a direct consequence of this property, as the method tries to “correct” boundaries to include all colors [00:20:53].

The Quadratic Case

Quadratic polynomials, with only two roots, behave differently [00:17:05]. In this case, each initial guess typically tends towards whichever root it is closest to [00:17:09]. The resulting diagram is much simpler, with a smooth boundary between the two regions, because the shared boundary property (touching all roots) is satisfied by simply touching the only two roots available [00:22:48]. The complexity only arises when jumping from two to three or more roots [00:17:32].

The mathematical field that studies these kinds of questions is called holomorphic dynamics [00:23:22].

Future Explorations

While known as “Newton’s fractal,” Isaac Newton himself had no knowledge of these complex images, as they require modern computational technology [00:23:38]. This highlights how simple mathematical ideas, even centuries old, can contain hidden complexity and new domains of relevance waiting to be discovered [00:24:10].

Further questions about Newton’s Method, such as whether the iterative process can ever get trapped in a cycle, lead to surprising connections with other famous fractals like the Mandelbrot set [00:24:42].

Tubegraph

Explorer

Table of Contents