Home
Search
 
What's New
Index
Books
Links
Q & A
Newsletter
Banners
 
Feedback
Tip Jar
 
C# Helper...
 
XML RSS Feed
Follow VBHelper on Twitter
 
 
 
MSDN Visual Basic Community
 
 
 
 
 
TitleUse Newton's method on the equation Z^n - 1 to draw fractals in Visual Basic .NET
DescriptionThis example shows how to use Newton's method on the equation Z^n - 1 to draw fractals in Visual Basic .NET.
KeywordsNewton's method, polynomial, root, function, fractal, VB .NET
CategoriesAlgorithms, Graphics, VB.NET
 
Newton's method calculates the roots of equations. In other words, it finds the values of X for which F(X) = 0. For more information on the part of the code that calculates Newton's method, see Use Newton's method to find the roots of an equation in Visual Basic .NET.

To draw a fractal, the program applies Newton's method to complex numbers in a region of the complex plane. It then colors each point in the region to indicate the root of the equation to which Newton's method leads for that point.

For example, the equation Z^4 - 1 has four roots (values of Z that make the equation zero): 1, -1, i, and -i.

To make the calculations easier to understand, the program uses the following Complex class.

 
Private Class Complex
    Public Re As Double
    Public Im As Double

    Public Sub New(ByVal real_part As Double, ByVal _
         imaginary_part As
Double)
        Re = real_part
        Im = imaginary_part
    End Sub

    Public Function Clone() As Complex
        Return New Complex(Re, Im)
    End Function

    Public Function MagnitudeSquared() As Double
        Return Re * Re + Im * Im
    End Function

    Public Function Magnitude() As Double
        Return Sqrt(MagnitudeSquared)
    End Function

    Public Function Times(ByVal x As Complex) As Complex
        Return New Complex(Re * x.Re - Im * x.Im, Re * x.Im _
            + Im * x.Re)
    End Function

    Public Function Times(ByVal new_re As Double, ByVal _
         new_im As Double) As
Complex
        Return New Complex(Re * new_re - Im * new_im, Re * _
             new_im + Im *
new_re)
    End Function

    Public Function Plus(ByVal x As Complex) As Complex
        Return New Complex(Re + x.Re, Im + x.Im)
    End Function

    Public Function Plus(ByVal new_re As Double, ByVal _
         new_im As Double) As
Complex
        Return New Complex(Re + new_re, Im + new_im)
    End Function

    Public Function DividedBy(ByVal denominator As Complex) _
        As Complex
        Dim conjugate As New Complex(denominator.Re, _
            -denominator.Im)
        denominator = denominator.Times(conjugate)
        Dim numerator As Complex = Me.Times(conjugate)
        numerator.Re /= denominator.Re
        numerator.Im /= denominator.Re
        Return numerator
    End Function

    Public Function IsCloseTo(ByVal x As Complex) As Boolean
        Return Abs(Re - x.Re) + Abs(Im - x.Im) < 0.001
    End Function

    Public Overrides Function ToString() As String
        If Im < 0 Then
            Return Re.ToString() & " - " & _
                Abs(Im).ToString() & "i"
        Else
            Return Re.ToString() & " + " & Im.ToString() & _
                "i"
        End If
    End Function
End Class
 
The following code shows how the program calculates the function Z^N - 1 and its derivative N * Z^(N - 1).
 
Private Const NUM_ROOTS As Integer = 7
Private m_Roots(NUM_ROOTS) As Complex

' The function.
' F(x) = x^NUM_ROOTS - 1.
Private Function F(ByVal x As Complex) As Complex
    Dim result As Complex = x.Clone()   ' x.

    ' x^NUM_ROOTS.
    For i As Integer = 1 To NUM_ROOTS - 1
        result = result.Times(x)
    Next i

    ' x^NUM_ROOTS - 1.
    Return result.Plus(-1, 0)
End Function

' The function's derivative.
' dFdx(x) = NUM_ROOTS * x^(NUM_ROOTS - 1).
Private Function dFdx(ByVal x As Complex) As Complex
    Dim result As Complex = x.Clone()   ' x.

    ' x^(NUM_ROOTS - 1).
    For i As Integer = 1 To NUM_ROOTS - 2
        result = result.Times(x)
    Next i

    ' NUM_ROOTS * x^(NUM_ROOTS - 1).
    Return result.Times(NUM_ROOTS, 0)
End Function
 
The following code draws the fractal. The code loops over the points in an area and uses Newton's method to find a root of the equation starting with that point as its initial guess. It then looks through a list of the equation's roots to see which one it found and plots the point with a corresponding color.
 
' Draw the fractal.
Private Sub DrawFractal()
    ' Do nothing when the form is initially created.
    If Not m_FormVisible Then Exit Sub

    ' Do nothing if the canvas has zero size.
    If picCanvas.ClientSize.Width < 1 Or _
       picCanvas.ClientSize.Height < 1 Then Exit Sub

    ' Create the Bitmap and Graphic objects.
    If Not (m_Graphics Is Nothing) Then
        picCanvas.Image = Nothing
        m_Graphics.Dispose()
        m_Bitmap.Dispose()
    End If
    m_Bitmap = New Bitmap(picCanvas.ClientSize.Width, 
picCanvas.ClientSize.Height)
    m_Graphics = Graphics.FromImage(m_Bitmap)

    ' Clear the bitmap.
    m_Graphics.Clear(Me.BackColor)
    picCanvas.Image = m_Bitmap
    picCanvas.Refresh()

    ' Work until the epsilon squared < this.
    Const CUTOFF As Single = 0.0000001

    ' Adjust the coordinate bounds to fit picCanvas.
    AdjustAspect()

    Dim clr As Integer
    Dim x0, x, epsilon As Complex
    Dim dx, dy As Double

    ' dx and dy are the changes in the real
    ' and imaginary parts across pixels.
    Dim wid As Integer = picCanvas.ClientSize.Width
    Dim hgt As Integer = picCanvas.ClientSize.Height
    dx = (m_Wxmax - m_Wxmin) / (wid - 1)
    dy = (m_Wymax - m_Wymin) / (hgt - 1)

    ' Calculate the values.
    x0 = New Complex(m_Wxmin, 0)
    For i As Integer = 0 To wid - 1
        x0.Im = m_Wymin
        For j As Integer = 0 To hgt - 1
            x = x0
            Const MAX_ITER As Integer = 200
            Dim iter As Integer = 0
            Do
                iter += 1
                If iter > MAX_ITER Then Exit Do
                epsilon = F(x).DividedBy(dFdx(x)).Times(-1, _
                    0)
                x = x.Plus(epsilon)
            Loop While epsilon.MagnitudeSquared() > CUTOFF

            ' Set which root this is.
            If iter > MAX_ITER Then
                clr = 0 ' Black.
            Else
                ' Find the root.
                clr = 1 ' White.
                For r As Integer = 0 To _
                    m_Roots.GetUpperBound(0)
                    If x.IsCloseTo(m_Roots(r)) Then
                        clr = r + 2 ' +2 to skip black and
                            ' white.
                        Exit For
                    End If
                Next r
            End If

            ' Set the pixel's color.
            m_Bitmap.SetPixel(i, j, m_Colors(clr))

            ' Move to the next point.
            x0.Im += dy
        Next j
        x0.Re += dx

        ' Let the user know we're not dead.
        If i Mod 10 = 0 Then picCanvas.Refresh()
    Next i

    ' Update the image.
    picCanvas.Refresh()

    Me.Text = "Newton's Method (" & _
        Format$(m_Wxmin) & ", " & _
        Format$(m_Wymin) & ")-(" & _
        Format$(m_Wxmax) & ", " & _
        Format$(m_Wymax) & ")"
End Sub
 
See the code for additional details.

For more information on Newton's method, see Eric W. Weisstein's article Newton's Method from MathWorld--A Wolfram Web Resource.

 
 
Copyright © 1997-2010 Rocky Mountain Computer Consulting, Inc.   All rights reserved.
  Updated