CPSC/Math 402: 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!). Put your answers in my mailbox or under my door.

Convergence Properties

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.
  1. 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
  2. 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 of accuracy?

     

     

  3. Do the same as #1 above for Newton2.java.
  4. Question: You should note some cyclic behavior for some starting points. What feature on the graph is this related to?

     

     

  5. Run Newton3.java with several different starting points.
  6. 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?

     

     

     

     

  7. 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.
  8. Question: How does the convergence rate compare to that for (x - a)^3?

     

     

  9. 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).

     

     

     

     

  10. 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?

     

     

     

     

Interesting Pictures

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: 
        javac StartPts1.java
        appletviewer start1.html
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.