This is a visualization of Newton's method for finding roots (more information on Wikipedia and Wolfram MathWorld). Click anywhere on the graph above to choose a starting guess for the method and watch as it either converges to a solution or fails to do so.
| Function |
Reason |
|---|---|
|
f(x) = 0.3(x+3)^2 - 3
|
This is a simple function that demonstrates the method. |
|
f(x) = \sin(x)
|
Basic function with multiple roots. Two different initial guesses which are right next to each other may converge to two different roots. |
|
f(x) = x^2 - 25
|
Newton's method can be used to find square roots of functions. This reveals that the square root of 25 is ±5. However, note that in this specific visualization, if your starting guess is negative, it will converge to -5.02 instead of -5.0, which is due to discretization error. |
|
f(x) = \tfrac{1}{3}x
|
This is a simple linear function, so the method should converge in one iteration. However, due to discretitaztion and rounding errors specific to this program, it sometimes takes more than one. |
|
f(x) = x^2 - 2x + 2
|
This is a function where Newton's method can easily fail. If you choose an initial guess of x_0 = 0, increasing iterations will fall into a circular pattern, meaning that iterations will never go out of bounds, but it will never converge to a solution either. In addition, many other starting guesses will result in an absurdly large amount of iterations before converging, and others won't converge at all. |
Right now, you can only choose from 5 pre-selected functions. However, the source code is easy to modify if you want to add your own — it's only a one line modification, and I point out where you should change it in the code.
The implementation of this program is far from perfect. Essentially, I store (x, y) coordinate pairs on the function that are in the display in an array. This is why you will sometimes get the message "Iteration out of bounds." This message doesn't mean the method won't converge with that starting guess; rather, it means that it would have to index a value outside of the array to find what the next iteration is. Using arrays was an easy way to map discrete points on a function to pixels on a screen, but at the same time they don't allow much flexibility in allowing the algorithm to pick points outside of the displayed part of the function. If I were to implement this again, I definitely would do it a different way.
Also, due to the fact that the continuous function is being mapped to pixels, there are discretization errors. Because of this, this page is meant exclusively as a visual tool to see how Newton's method works, and is not meant to produce precise results (Ex: -5.02 is not actually a solution to x^2-25 = 0).
On a related note, this is technically a quasi-Newton method (secant) since I use a first-order finite difference approximation to calculate the derivative, but there's enough error already that this shouldn't matter much in the grand scheme of things.
This project (and the plotting classes I use both here and in my Matrix visualization) was originally part of my final project in a computer science I took on graphics and visualization.
You can get the source code here (ZIP file, 23 kB). You will need the Processing software package to run the program.