|
|
Title | Use Newton's method to find the roots of an equation in Visual Basic .NET |
Description | This example shows how to use Newton's method to find the roots of an equation in Visual Basic .NET. |
Keywords | Newton's method, equation, root, zero |
Categories | Algorithms, 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.
This program graphs the equation X^3/3 - 2*X + 5. When you click on the
graph, it uses Newton's method to find a root of the equation, starting from
the X value that you clicked.
|
|
' The function.
Private Function F(ByVal x As Double) As Single
Return x * x * x / 3 - 2 * x * x + 5
End Function
' Draw the background graph.
Private Sub DrawGraph(ByVal gr As Graphics)
gr.Clear(Me.BackColor)
' Scale for convenience.
gr.ScaleTransform(SCALE_FACTOR, -SCALE_FACTOR)
gr.TranslateTransform( _
Me.ClientRectangle.Width / 2, _
Me.ClientRectangle.Height / 2, _
Drawing2D.MatrixOrder.Append)
' Draw the axes.
Dim blue_pen As New Pen(Color.Blue, 0)
For x As Integer = -10 To 10
gr.DrawLine(blue_pen, x, -0.5!, x, 0.5!)
Next x
For y As Integer = -10 To 10
gr.DrawLine(blue_pen, -0.5!, y, 0.5!, y)
Next y
gr.DrawLine(blue_pen, -10, 0, 10, 0)
gr.DrawLine(blue_pen, 0, -10, 0, 10)
blue_pen.Dispose()
' Draw the curve.
Dim red_pen As New Pen(Color.Red, 0)
Dim y1 As Single
Dim y2 As Single = F(-10)
Const STEP_SIZE As Single = 0.1
For x As Single = -10 + STEP_SIZE To 10 Step STEP_SIZE
y1 = y2
y2 = F(x)
gr.DrawLine(red_pen, x - STEP_SIZE, y1, x, y2)
Next x
red_pen.Dispose()
End Sub
|
|
The way Newton's method works is it starts from an initial guess X0 (given
by the point you clicked). It then estimates the difference between that
value and root:
epsilon = -F(x) / dFdx(x)
The method then sets its next guess for x to be the current value plus
epsilon (X(n+1) = X(n) + epsilon). It repeats this process until epsilon is
smaller than some cutoff value.
|
|
' The function's derivative.
Private Function dFdx(ByVal x As Double) As Single
Return x * x - 4 * x
End Function
' Find the roots by using Newton's method.
Private Sub Form1_MouseDown(ByVal sender As Object, ByVal e _
As
System.Windows.Forms.MouseEventArgs) Handles _
MyBase.MouseDown
' Clear previous results.
Dim gr As Graphics = Me.CreateGraphics()
DrawGraph(gr)
' Convert the X coordinate into world coordinates.
Dim m As Matrix = gr.Transform()
m.Invert()
Dim pts() As PointF = {New PointF(e.X, e.Y)}
m.TransformPoints(pts)
Dim x0 As Single = pts(0).X
Const CUTOFF As Single = 0.0000001
Dim epsilon As Single
Dim the_pen As New Pen(Color.Black, 0)
Dim iterations As Integer = 0
Do
iterations += 1
gr.DrawLine(the_pen, x0, -1.5!, x0, 1.5!)
epsilon = -F(x0) / dFdx(x0)
x0 = x0 + epsilon
Loop While Abs(epsilon) > CUTOFF
gr.DrawLine(the_pen, x0, -3.0!, x0, 3.0!)
the_pen.Dispose()
Me.Text = x0 & " +/-" & epsilon & " in " & iterations & _
" iterations"
End Sub
|
|
Newton's method uses the function's derivative to make its next X value
guess. If the curve is relatively flat for the current value of X, then the
derivative (which is the slope of the function) gives a value far away from
the current one and the method is unstable. In this example, try clicking on
a point where X is at or near 0 and see what happens.
For more information on Newton's method, see Eric W. Weisstein's article
Newton's Method from MathWorld--A Wolfram Web Resource.
|
|
|
|
|
|