Newton's Basin

(Difference between revisions)
 Revision as of 12:43, 4 June 2009 (edit)← Previous diff Revision as of 12:59, 4 June 2009 (edit) (undo)Next diff → Line 8: Line 8: - The colors in a Newton's Basin usually correspond to each individual root of the equation, and can be used to infer where each root is located. Each color region reflects the set of coordinates (x,y) whose x-values, after undergoing iteration with the equation describing the fractal, will eventually get closer and closer to the value of the root. + The colors in a Newton's Basin usually correspond to each individual root of the equation, and can be used to infer where each root is located. Each color region reflects the set of coordinates whose x-values, after undergoing iteration with the equation describing the fractal, will eventually get closer and closer to the value of the root. - The animation emphasizes the roots in a Newton's Basin, whose equation clearly has three roots. The image featured on this page is also a Newton's Basin with three roots, presented more artistically. + The animation emphasizes the roots in a Newton's Basin, whose equation clearly has three roots. The image featured on this page is also a Newton's Basin with three roots. |ImageDesc=The featured image on this page is a visual representation of Newton's Method for calculus expanded into the [[Complex Numbers|complex plane]]. To read a brief explanation on this method, read the following section entitled ''Newton's Method''. |ImageDesc=The featured image on this page is a visual representation of Newton's Method for calculus expanded into the [[Complex Numbers|complex plane]]. To read a brief explanation on this method, read the following section entitled ''Newton's Method''. Line 40: Line 40: ====Creating Newton's Basin==== ====Creating Newton's Basin==== [[Image:NewtonBasin_5Roots.gif|thumb|left|200px|Newton Basin with 5 Roots]] [[Image:NewtonBasin_5Roots.gif|thumb|left|200px|Newton Basin with 5 Roots]] - To produce an interesting fractal, the Newton Method needs to be extended to the complex plane and to imaginary numbers. Newton's Basin is created using a complex polynomial, with real and/or complex roots. In addition, each root in a Newton's Basin fractal is usually given a distinctive color. It is clear that the fractal on the left has a total of five roots colored magenta, yellow, red, green, and blue. + To produce an interesting fractal, the Newton Method needs to be extended to the complex plane and to imaginary numbers. Newton's Basin is created using a complex polynomial, with real and/or complex roots. In addition, each root in a Newton's Basin fractal is usually given a distinctive color. Thus, the fractal on the left has a total of five roots colored magenta, yellow, red, green, and blue. Every pixel in the image is assigned a complex number coordinate. The coordinates are applied to the equation and iterated continually with the output of the previous iteration becoming the input of the next iteration. If the iterations lead the x-values of the coordinates to converge towards a particular root, the pixel is colored accordingly. If the iterations lead to a loop and not a root, then the pixel is usually colored black because the x-values do not converge. Every pixel in the image is assigned a complex number coordinate. The coordinates are applied to the equation and iterated continually with the output of the previous iteration becoming the input of the next iteration. If the iterations lead the x-values of the coordinates to converge towards a particular root, the pixel is colored accordingly. If the iterations lead to a loop and not a root, then the pixel is usually colored black because the x-values do not converge. - Each root has a set of initial (or pixel) coordinates $x_0$ that converge to the root. This set of coordinates that are complex number values is called the root's ''basin of attraction''- where the name of this fractal comes from. In addition, some images including shading in each basin. The shading is determined by the number of iterations it takes each pixel to converge to a particular root, and it allows us to see the location of the root more clearly. + Each root has a set of initial (or pixel) coordinates $x_0$ that converge to the root. This set of coordinates that are complex number values is called the root's ''basin of attraction''- where the name of this fractal comes from. In addition, some images including shading in each basin. The shading is determined by the number of iterations (aka. escape time) it takes each pixel to converge to a particular root, and it allows us to see the location of the root more clearly. Line 51: Line 51: [[Image:Roots.gif|thumb|right|Solutions $p(z) = z^3 - 2z + 2$]] [[Image:Roots.gif|thumb|right|Solutions $p(z) = z^3 - 2z + 2$]] - For example, the image below, as well as the featured image, was created from the equation $p(z) = z^3 - 2z + 2$. Since this equation is a 3rd degree complex polynomial, it has three roots, two of which are complex: z = -1.7693, 0.8846 + 0.5897i, and 0.8846 - 0.5897i. The resulting solution map of these solutions are to the right, and you can see that the Newton's Basin created from this complex polynomial has three roots (yellow, blue, and green) that correspond to the solution map. + For example, the image below, as well as the featured image, was created from the equation $p(z) = z^3 - 2z + 2$. Since this equation is a 3rd degree complex polynomial, it has three roots, two of which are complex: z = -1.7693, 0.8846 + 0.5897i, and 0.8846 - 0.5897i. The resulting map of these solutions are to the right, and you can see that the Newton's Basin created from this complex polynomial has three roots (yellow, blue, and green) that correspond to the solution map. [[Image:NewtonFractalZoom.png|600px|center|Newton Basin with 3 Roots]] [[Image:NewtonFractalZoom.png|600px|center|Newton Basin with 3 Roots]] Line 59: Line 59: ====Self-Similarity==== ====Self-Similarity==== - As with all other fractals, Newton's Basin exhibits self-similarity. The video to the left is an interactive representation of the continual self-similarity displayed by a Newton's Basin with a root degree of 5 (similar to the fractal shown in the previous section). Towards the end of the video, you will notice that the pixels are no longer adequate to continue magnifying the image...however, the fractal still goes on. + As with all other fractals, Newton's Basin exhibits self-similarity. The video below is an interactive representation of the continual self-similarity displayed by a Newton's Basin with a root degree of 5 (similar to the fractal shown in the previous section). Towards the end of the video, you will notice that the pixels are no longer adequate to continue magnifying the image...however, the fractal still goes on. {{#ev:tubechop|gh6e95OmoAk&start=5&end=70|300|left}} {{#ev:tubechop|gh6e95OmoAk&start=5&end=70|300|left}} }} }}

Revision as of 12:59, 4 June 2009

Newton's Basin
Newton's Basin is a visual representation of Newton's Method, which is a procedure for estimating the root of a function.

Basic Description

Animation Emphasizing Roots

This image is one of many examples of Newton's Basin or Newton's Fractal. Newton's Basin is based on a calculus concept called Newton's Method, a procedure Newton developed to estimate a root of an equation.

The colors in a Newton's Basin usually correspond to each individual root of the equation, and can be used to infer where each root is located. Each color region reflects the set of coordinates whose x-values, after undergoing iteration with the equation describing the fractal, will eventually get closer and closer to the value of the root.

The animation emphasizes the roots in a Newton's Basin, whose equation clearly has three roots. The image featured on this page is also a Newton's Basin with three roots.

A More Mathematical Explanation

Note: understanding of this explanation requires: *Calculus

The featured image on this page is a visual representation of Newton's Method for calculus expanded i [...]

The featured image on this page is a visual representation of Newton's Method for calculus expanded into the complex plane. To read a brief explanation on this method, read the following section entitled Newton's Method.

Newton's Method

Newton's Method for calculus is a procedure to find a root of a polynomial, using an estimated coordinate as a starting point. Usually, the roots of a linear equation: $y = mx + b$ can be simply found by setting y = 0 and solving for x. However, with higher degree polynomials, this method can be much more complicated.

Newton devised an iterated method (animated to the right) with the following steps:

• Estimate a starting coordinate on the graph near to the root
• Find the tangent line at that starting coordinate
• Find the root of the tangent line
• Using the root as the x-coordinate of the new starting coordinate, iterate the method to find a better estimate

The results of this method lead to very close estimates to the actual root. Newton's Method can also be expressed:

$f'(x_n) = \frac{\mathrm{\Delta y}}{\mathrm{\Delta x}} = \frac{f(x_n)}{x_n - x_{n+1}}$
$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$

Newton's Basin

Creating Newton's Basin

Newton Basin with 5 Roots

To produce an interesting fractal, the Newton Method needs to be extended to the complex plane and to imaginary numbers. Newton's Basin is created using a complex polynomial, with real and/or complex roots. In addition, each root in a Newton's Basin fractal is usually given a distinctive color. Thus, the fractal on the left has a total of five roots colored magenta, yellow, red, green, and blue.

Every pixel in the image is assigned a complex number coordinate. The coordinates are applied to the equation and iterated continually with the output of the previous iteration becoming the input of the next iteration. If the iterations lead the x-values of the coordinates to converge towards a particular root, the pixel is colored accordingly. If the iterations lead to a loop and not a root, then the pixel is usually colored black because the x-values do not converge.

Each root has a set of initial (or pixel) coordinates $x_0$ that converge to the root. This set of coordinates that are complex number values is called the root's basin of attraction- where the name of this fractal comes from. In addition, some images including shading in each basin. The shading is determined by the number of iterations (aka. escape time) it takes each pixel to converge to a particular root, and it allows us to see the location of the root more clearly.

Solutions $p(z) = z^3 - 2z + 2$

For example, the image below, as well as the featured image, was created from the equation $p(z) = z^3 - 2z + 2$. Since this equation is a 3rd degree complex polynomial, it has three roots, two of which are complex: z = -1.7693, 0.8846 + 0.5897i, and 0.8846 - 0.5897i. The resulting map of these solutions are to the right, and you can see that the Newton's Basin created from this complex polynomial has three roots (yellow, blue, and green) that correspond to the solution map.

Self-Similarity

As with all other fractals, Newton's Basin exhibits self-similarity. The video below is an interactive representation of the continual self-similarity displayed by a Newton's Basin with a root degree of 5 (similar to the fractal shown in the previous section). Towards the end of the video, you will notice that the pixels are no longer adequate to continue magnifying the image...however, the fractal still goes on.

Teaching Materials

http://www.chiark.greenend.org.uk/~sgtatham/newton/ for further mathematical explanation