CPSC/Math 402: Exploring Root Finding
Go to the course Web page at cs.roanoke.edu/CPSC402A and save
the following files to your directory. These programs illustrate
properties of Newton's method and the Secant method for finding
roots of non-linear functions. Write down answers to the questions
as you go through the lab (you may collaborate!).
- Newton1.java -- Uses Newton's method for
the function f(x) = x3 - 3x2 + 2x + 0.1.
- Newton2.java -- Newton's method for the
function f(x) = x3 - 3x2 + 2x + 0.5.
- Newton3.java -- Newton's method for the
function f(x) = (x - 1)3
- Secant1.java -- Secant method for the
same function as Newton1
- Secant2.java -- Secant method for the
same function as Newton2
- StartPts1.java -- An applet that illustrates
which root Newton's method converges to for different starting points. The
function is the same as in Newton1.java.
- StartPts2.java -- Similar to the above but
the function is the one used in Newton2.java
- start1.html -- HTML file to run
the applet in StartPts1.java
- start2.html -- HTML file for the applet
- CubeRoots.java -- An applet to
illustrate the convergence to the cube roots of unity in the complex
- cube.html -- HTML file to run the cube
The three Newton programs perform Newton's method for three
different functions. The first two functions and their graphs are
on the Mathematica printout. The third function is (x - 1)3.
Each program asks for the starting point, a maximum number of iterations,
and a tolerance then prints out a table with the iterate number,
the value of the iterate, and the estimate of the error
(the error estimate used
is |xk+1 - xk|).
The iterates and the error are printed to
12 digits. The Mathematica printout shows what the roots should be
and also the values of the local maximum and minimum. The graphs should
help you understand the behavior you see in running the programs.
- Compile Newton1.java (javac Newton1.java) and run it
(java Newton1). Use 100 for the
maximum number of iterates and 1e-11 for the tolerance. Try the following
starting points: -100, -20, -1, 0.426, 0.4227, 1, 1.5, 1.6, 100
- Question: Recall that the convergence rate for Newon's method
is quadratic which basically means that the number of digits of accuracy
doubles with each iteration. Generally you can see this by looking
at the error estimates at each iterate. What happened in the examples you tried
if you start with no digits
- Do the same as #1 above for Newton2.java.
- Question: You should note some cyclic behavior for some starting
points. What feature on the graph is this related to?
- Run Newton3.java with several different starting points.
- Question: The function in Newton3 does not have a simple root --
the root has multiplicity 3 --
hence rate of convergence is no longer quadratic.
Describe the convergence -- how many digits
of accuracy are gained at each iterate once the iterates settle down and start converging?
- Edit Newton3.java to change the function to (x - 1)^5 (you need to
change both f and fprime). Compile and run the program. The root
here has multiplicity 5.
- Question: How does the convergence rate compare to that
for (x - 1)^3?
Now run the Secant1.java program and Secant2.java and try some
different starting points.
In particular find starting
points that illustrate the fact that the
order of the starting points makes a difference. Also find starting points
(for either function) for which the method does not converge in
100 iterates (if possible -- and it is! -- find starting points
that cause the method to cycle). Write down the examples you
find (and the behavior).
- Question The convergence rate for the Secant method is the golden ratio (approximately
1.618034), meaning that at each iterate the number of correct digits is
multiplied by 1.618 approximately. Is there support for that in the
output? Is it evident that the secant method tends to converge more
slowly than Newton's method?
Newton's method is a local method -- convergence to a specific root is guaranteed
only if the starting point is sufficiently close to the root. However, observing
the global behavior of the method can result in some interesting pictures.
The programs StartPt1.java and StartPt2.java draw pictures to illustrate what
Newton's method does for different starting points for the
functions in Newton1.java and Newton2.java, respectively.
For each starting point
in some range (an initial value for the range and an increment determine
the starting points used), Newton's method is applied. A vertical line is
then drawn on the graphics image to depict what happened to the iterates -- if
they don't converge in the given number of iterates a black line is drawn,
if they do, then the color of the
line drawn indicates which root the iterates converged to (see the
documentation to see which color corresponds to which root). The programs
let you put in new starting points and increments. To compile and
run the programs you need to use the following commands:
Put different starting points and increments in the textboxes
to see convergence behavior in different regions (sorry about the
way the numbers are sometimes displayed -- no time to make it pretty!).
The most interesting pictures occur when complex functions are used.
The program CubeRoots.java performs Newton's method on the
complex function z3 - 1 and paints a picture
showing the results. The roots are called the cube roots
of unity -- one is at (1,0), another at (cos(2Pi/3), sin(2Pi/3)) and the
third at (cos(4Pi/3), sin(4Pi/3)) -- that is they are spaced equally
around the unit circle. Again black represents lack of convergence, while
the other 3 colors indicate which of the 3 roots Newton's method
converges to if started at the given point.
- Compile and run the program (use
the cube.html file). It graphs the rectangular region from (-3,-3) to
- Edit the program to narrow the region -- change the starting value of
x and y to -0.5 and the increment to 0.002. Re-compile and run the