Newton's Basin

From Math Images

(Difference between revisions)
Jump to: navigation, search
Current revision (10:18, 28 June 2012) (edit) (undo)
(Removed excess hides and fixed template formatting for the explanation)
 
(47 intermediate revisions not shown.)
Line 1: Line 1:
-
{{Image Description
+
{{Image Description Ready
|ImageName=Newton's Basin
|ImageName=Newton's Basin
-
|Image=NewtonBasin.jpg
+
|Image=NewtonBasin2.jpg
|ImageIntro=Newton's Basin is a visual representation of Newton's Method, which is a procedure for estimating the root of a function.
|ImageIntro=Newton's Basin is a visual representation of Newton's Method, which is a procedure for estimating the root of a function.
|ImageDescElem=
|ImageDescElem=
-
[[Image:NewtonBasin_Animate.gif|thumb|left|200px|Animation Emphasizing Roots]]
+
[[Image:NewtonBasin_Animate.gif|thumb|left|250px|Animation Emphasizing Roots]]
-
[[Image:NewtonBasin2.jpg|thumb|right|200px|Newton Basin with 3 Roots]]
+
This image is one of many examples of Newton's Basin or Newton's Fractal. Newton's Basin is based on a calculus technique called Newton's Method, a procedure Newton developed to estimate <balloon title="load:myContent">roots</balloon><span id="myContent" style="display:none">A root is the x-value where y = 0 and the graph of an equation crosses the horizontal x-axis [[Image:Root.gif|200px]]</span> (or solutions) of equations.
-
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 <balloon title="load:myContent">root</balloon><span id="myContent" style="display:none">A root is located where y = 0 and the graph of an equation crosses the horizontal x-axis [[Image:Root.gif|200px]]</span> 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. The region of each color 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.
+
Each pixel in a Newton's Basin corresponds to a unique coordinate, or point. 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 points, which, after undergoing iteration with the equation describing the fractal, will eventually get closer and closer to the value of the root associated with that color.
 +
The animation emphasizes the roots in a Newton's Basin, whose equation clearly has three roots. The image featured at the top of this page is also a Newton's Basin with three roots.
-
The animation emphasizes the roots in a Newton's Basin, whose equation clearly has three roots. The image to the right is also a Newton's Basin with three roots, presented more artistically.
+
|ImageDesc=The image at the top of this page is a visual representation of Newton's Method in calculus expanded into the [[Complex Numbers|complex plane]].
-
 
+
-
|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''.
+
===Newton's Method===
===Newton's Method===
-
{{hide|1=
 
-
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: <math>y = mx + b</math> can be simply found by setting y = 0 and solving for x. However, with higher degree polynomials, this method can be much more complicated.
 
[[Image:NewtonRoot_Animation.gif|right]]
[[Image:NewtonRoot_Animation.gif|right]]
 +
Newton's Method in calculus is a procedure to find roots of polynomials, using an estimated value as a starting point. Newton devised an iterated method (animated to the right) with the following steps:
 +
:#Estimate a starting x-value (<math>x_o</math>) on the graph near to the root
 +
:#Find the tangent line at that starting x-value
 +
:#Find the root of the tangent line
 +
:#Using the tangent's root as new starting x-value (<math>x_{n}, x_{n+1},...</math>), iterate the method to find a better estimate
-
Newton devised an iterated method (animated to the right) with the following steps:
+
The results of this method lead to very close estimates to the root of the polynomial. Newton's Method can also be expressed algebraically as follows, where <math>x_n</math> is the nth estimate:
-
:*Estimate a starting coordinate on the graph near to the root
+
[[Image:NewtonsMethod.gif|left|210px]]
-
:*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:
 
-
:<math>f'(x_n) = \frac{\mathrm{\Delta y}}{\mathrm{\Delta x}} = \frac{f(x_n)}{x_n - x_{n+1}}</math>
+
<math>f'(x_n) = \frac{\mathrm{\Delta y}}{\mathrm{\Delta x}} = \frac{0 - y_n}{x_n - x_{n+1}}</math>
 +
 
 +
<math>f'(x_n) = \frac{f(x_n)}{x_n - x_{n+1}}</math>
 +
 
 +
<math>x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}</math>
 +
 
-
:<math>x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}</math>
 
-
}}
 
===Newton's Basin===
===Newton's Basin===
-
{{hide|1=
 
-
====Creating Newton's Basin====
+
[[Image:NewtonFractalZoom.png|600px|center|Newton Basin with 3 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 <balloon title="load:Content">complex polynomial</balloon><span id="Content" style="display:none">Or a polynomial with co-efficients that are complex, such as <math> p(z) = z^3 - 2z + 2</math></span>, 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.
+
-
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.
+
[[Image:NewtonBasin_5Roots.gif|thumb|right|220px|Newton Basin with 5 Roots]]
 +
To produce an interesting fractal, the Newton Method needs to be extended to the complex plane. Newton's Basin is created using a <balloon title="load:Content">complex polynomial</balloon><span id="Content" style="display:none">Or a polynomial with co-efficients that are complex, such as <math> p(z) = z^3 - 2z + 2</math>, where ''z'' is in the form a + b''i''</span>, 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 right is generated by a polynomial with a total of five roots colored magenta, yellow, red, green, and blue.
 +
 
 +
Every pixel in the image represents a complex number. Each complex number is applied to the equation and iterated continually with the output of the previous iteration becoming the input of the next iteration. This iteration is done by using the same equations discussed in the previous '''Newton's method''' section, where ''x'' is now a complex number ''z'', ''y'' is now a complex number ''p'', and <math>z_n</math> is the nth estimate:
 +
 
 +
::<math>f'(z_n) = \frac{\mathrm{\Delta p}}{\mathrm{\Delta z}} = \frac{f(z_n)}{z_n - z_{n+1}}</math>
 +
 
 +
::<math>z_{n+1} = z_n - \frac{f(z_n)}{f'(z_n)}</math>
 +
 
 +
 
 +
====Coloring====
 +
[[Image:Newton Basin x5-1.png|left|thumb|<math>f(z) = z^5 - 1</math>]]
 +
 
 +
 
 +
If the iterations lead the complex number to converge towards a particular root, the pixel is colored according to the color of that root. If the iterations lead to a loop and not a root, then the pixel is colored black because the complex number does not converge.
 +
 
 +
 
 +
Each root has a set of complex numbers (or pixels)that converge to the root (algebraically, this set would include all of the <math>z_0</math> values referenced above). This set of coordinates 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 its root, and it allows us to see the location of the root more clearly. The darker the shading of a pixel is, the more iterations it requires for that pixel to converge to its respective root.
 +
 
 +
 
 +
 
 +
 
 +
 
 +
====An Example====
 +
[[Image:Roots.gif|thumb|200px|right]]
 +
For example, the image below, as well as the image at the top of the page, was created from the equation <math> p(z) = z^3 - 2z + 2</math>. Since this equation is a 3rd degree complex polynomial, it has three roots, two of which are complex:
 +
 
 +
::<math>z_1 = -1.7693</math>
 +
::<math>z_2 = 0.8846 + 0.5897i</math>
 +
::<math>z_3 = 0.8846 - 0.5897i</math>
 +
 
 +
The resulting map of these solutions are to the right. 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]]
-
Each root has a set of initial (or pixel) coordinates <math>x_0</math> 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.
 
-
<gallery caption="" widths="100px" heights="100px" perrow="2">
 
-
Image:NewtonFractal_Zoom.png|Newton Basin with 3 Roots
 
-
Image:NewtonFractal_ZoomClose.png|Close up of Newton Basin with 3 Roots
 
-
</gallery>
 
-
For example, the image above was created from the equation <math> p(z) = z^3 - 2z + 2</math>.
 
-
roots...
 
-
wolfram alpha image
 
====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 the Newton's Basin shown in an above section with a <balloon title="load:basin2">root degree of 5</balloon><span id="basin2" style="display:none">
-
{{#ev:tubechop|gh6e95OmoAk&start=5&end=70|300|left}}
+
[[Image:Newton Basin x5-1.png|150px]]<math>f(z) = z^5 - 1</math></span>. 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|mute}}
 +
 
|other=Calculus
|other=Calculus
-
|AuthorName=Nicholas Buroojy
+
|AuthorName=Ashley T.
-
|AuthorDesc=Nicholas Buroojy has created many math images including Newton's Lab fractals, Julia and Mandelbrot Sets, Cantor Sets...
+
|AuthorDesc=
-
|SiteName=Wikipedia
+
|SiteName=Fractal Foundation
-
|SiteURL=http://en.wikipedia.org/wiki/File:Timelapse34.jpg
+
|SiteURL=http://www.fractalfoundation.org/images/photo/3261826823/ashley-t-washington-ms.html
|Field=Fractals
|Field=Fractals
|Field2=Calculus
|Field2=Calculus
-
|FieldLinks=:http://www.chiark.greenend.org.uk/~sgtatham/newton/ for further mathematical explanation
+
|FieldLinks=
-
|InProgress=Yes
+
|References=
 +
Wikipedia, [http://en.wikipedia.org/wiki/Newton_fractal Newton fractal page] and [http://en.wikipedia.org/wiki/Newton%27s_method Newton's Method page]
 +
 
 +
Simon Tatham, [http://www.chiark.greenend.org.uk/~sgtatham/newton/ Fractals derived from Newton-Raphson iteration]
 +
 
 +
David E. Joyce, [http://aleph0.clarku.edu/~djoyce/newton/newton.html Newton Basins]
}}
}}

Current revision


Newton's Basin
Fields: Fractals and Calculus
Image Created By: Ashley T.
Website: Fractal Foundation

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.


Contents

Basic Description

Animation Emphasizing Roots
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 technique called Newton's Method, a procedure Newton developed to estimate roots (or solutions) of equations.


Each pixel in a Newton's Basin corresponds to a unique coordinate, or point. 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 points, which, after undergoing iteration with the equation describing the fractal, will eventually get closer and closer to the value of the root associated with that color.

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

A More Mathematical Explanation

Note: understanding of this explanation requires: *Calculus

The image at the top of this page is a visual representation of Newton's Method in calculus expanded [...]

The image at the top of this page is a visual representation of Newton's Method in calculus expanded into the complex plane.

Newton's Method

Newton's Method in calculus is a procedure to find roots of polynomials, using an estimated value as a starting point. Newton devised an iterated method (animated to the right) with the following steps:

  1. Estimate a starting x-value (x_o) on the graph near to the root
  2. Find the tangent line at that starting x-value
  3. Find the root of the tangent line
  4. Using the tangent's root as new starting x-value (x_{n}, x_{n+1},...), iterate the method to find a better estimate


The results of this method lead to very close estimates to the root of the polynomial. Newton's Method can also be expressed algebraically as follows, where x_n is the nth estimate:


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

f'(x_n) = \frac{f(x_n)}{x_n - x_{n+1}}

x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}



Newton's Basin

Newton Basin with 3 Roots
Newton Basin with 5 Roots
Newton Basin with 5 Roots

To produce an interesting fractal, the Newton Method needs to be extended to the complex plane. 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 right is generated by a polynomial with a total of five roots colored magenta, yellow, red, green, and blue.

Every pixel in the image represents a complex number. Each complex number is applied to the equation and iterated continually with the output of the previous iteration becoming the input of the next iteration. This iteration is done by using the same equations discussed in the previous Newton's method section, where x is now a complex number z, y is now a complex number p, and z_n is the nth estimate:

f'(z_n) = \frac{\mathrm{\Delta p}}{\mathrm{\Delta z}} = \frac{f(z_n)}{z_n - z_{n+1}}
z_{n+1} = z_n - \frac{f(z_n)}{f'(z_n)}


Coloring

f(z) = z^5 - 1


If the iterations lead the complex number to converge towards a particular root, the pixel is colored according to the color of that root. If the iterations lead to a loop and not a root, then the pixel is colored black because the complex number does not converge.


Each root has a set of complex numbers (or pixels)that converge to the root (algebraically, this set would include all of the z_0 values referenced above). This set of coordinates 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 its root, and it allows us to see the location of the root more clearly. The darker the shading of a pixel is, the more iterations it requires for that pixel to converge to its respective root.



An Example

For example, the image below, as well as the image at the top of the page, 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 = -1.7693
z_2 = 0.8846 + 0.5897i
z_3 = 0.8846 - 0.5897i

The resulting map of these solutions are to the right. 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.

Newton Basin with 3 Roots




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 the Newton's Basin shown in an above section with a root degree of 5. 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

There are currently no teaching materials for this page. Add teaching materials.




References

Wikipedia, Newton fractal page and Newton's Method page

Simon Tatham, Fractals derived from Newton-Raphson iteration

David E. Joyce, Newton Basins





If you are able, please consider adding to or editing this page!

Have questions about the image or the explanations on this page?
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.






Personal tools