Programming Assignment I

Due on Friday, October 8, 2010 @ 11pm

100 points

In a research work, you must solve the following non-linear equation for the smallest positive root. Since this is not a lower degree polynomial, there is no close-form for the solution and an iterative method must be used. To make sure the smallest positive root is found accurately, you intend to use Newton's method and the fixed-point iteration to check each other's result. Moreover, the accuracy of the root is expected to be less than 0.000005.

The task for you to do is very simple:

Use Newton's method and the fixed-point iteration to find the smallest positive root of the above equation with an accuracy of 0.000005. Use the default single precision only (i.e., REAL without any KIND). Use Fortran FUNCTION for function value, derivative, fixed-point iteration, etc. Moreover, no global variables should be used in these functions.

However, experience shows that this may not be a well-behaved equation and can lead to strange results and/or infinite loop. You should do your best to avoid numerical issues such as cancellation, rounding, overflow and underflow, and ensure the computed answer is indeed the smallest positive root.

Input and Output

Your program should include both methods. The input to your program consists of a number of lines. Each line has a real number, an initial guess (x0), and an integer, the maximum number of iterations to be performed. These two values are for both methods. For example, the following is a sample input to your program. The first line provides an initial value of 1.1 and a maximum number of iterations 20, while the second has initial value 1.5 and maximum number of iterations 15. The next two lines have the same meaning. 

1.1  20
1.5  15
2.0  100
3.1  99

For each input value x0, your program output should include two sections, one for Newton's method and the other for the fixed-point iteration. Output of Newton's method should look like the following. It has five columns: iteration number, the x for this iteration, its function value, its derivative, and the new x for the next iteration. If the computation converges after k iterations, your program should print out the last two lines, showing the number of iterations, the approximate root xk, its function value f(xk) and derivative f'(xk). 


a blank line
*** Newton's Method ***
a blank line
Iter: 1  x0   f(x0)   f'(x0)   x1
Iter: 2  x1   f(x1)   f'(x1)   x2
Iter: 3  x2   f(x2)   f'(x2)   x3
   ..... other output .....
Iter: k  xk-1   f(xk-1)   f'(xk-1)   xk
a blank line
Converged after k iterations:
x* = xk   f(x*) = f(xk)   f'(x*) = f'(xk)
a blank line

If computation does not converge after the maximum number of iterations, the last two output lines should be as follows, where k is the maximum number of iterations: 


Does not converged after k iterations:
x* = xk   f(x*) = f(xk)   f'(x*) = f'(xk)

As for the fixed-point iteration, the output is slightly different but simpler. The last two output lines follow the rule for Newton's method. 


a blank line
*** Fixed-Point Method ***
a blank line
Iter: 1  x0   g(x0)
Iter: 2  x1   g(x1)
Iter: 3  x2   g(x2)
   ..... other output .....
Iter: k  xk-1   g(xk-1)
a blank line
Converged after k iterations:
x* = xk   g(x*) = g(xk)   Error = |xk - g(xk)|
a blank line

The above two sections should be repeated for each input value. The complete output should look like the following: 


*** CS3911 Programming Assignment #1 ***
*** Newton's and Fixed-Point Methods ***

--- output of Newton's method for the first input value ---

--- output of Fixed-Point Method for the first input value  ---

--- output of Newton's method for the second input value ---

--- output of Fixed-Point Method for the second input value  ---

--- output for other input values ---

*** Done due to end-of-file ***

Submission Guidelines

General Rules

  1. All programs must be written in ANSI Fortran 90.
  2. Use the submit command to submit your work. You can submit as many times as you want, but only the last on-time one will be graded.
  3. Your program should be named as prog1.f90. Note that Unix filename is case sensitive. As a result, PROG1.f90, prog1.F90, pROG1.f90, etc are not acceptable.
  4. We will use the following approach to compile and test your programs: 
    f90 prog1.f90 -o prog1  <-- compile your program
prog1 < our-test-file   <-- test your program
    This procedure may be repeated a number of times with different input files to see if your program works correctly.
  5. Your implementation should fulfill the program specification as stated. Any deviation from the specification will cause you to receive zero point.
  6. A README file is always required.
  7. No late submission will be graded.
  8. Programs submitted to wrong class and/or wrong section will not be graded.

Compiling and Running Your Programs

This is about the way of compiling and running your program. If we cannot compile your program due to syntax error, wrong file names, etc, we cannot test your program, and, as a result, you receive 0 point. If your program compiles successfully but fails to run, we cannot test your program, and, again, you receive 0 point. Therefore, before submitting your work, make sure your program can compile and run properly.
  1. Not-compile programs receive 0 point. By not-compile, I mean any reason that could cause an unsuccessful compilation, including missing files, incorrect filenames, syntax errors in your programs, and so on. Double check your files before you submit, since I will not change your program. Note again: Unix filenames are case sensitive.
  2. Compile-but-not-run programs receive 0 point. Compile-but-not-run usually means you have attempted to solve the problem to some degree but you failed to make it working properly. For example, a wrong transformation for the fixed-point iteration or incorrect derivative computation could cause divergence and/or floating-point exceptions. This is considered as a case of compile-but-not-run. Hence, make sure you have a correct derivative and proper transformation.
  3. A meaningless or vague program receives 0 point even though it compiles successfully. This usually means your program does not solve the problem but serves as a placeholder or template just making it to compile and run.

Program Style and Documentation

This section is about program style and documentation.
  1. For each file, the first piece should be a program header to identify yourself like this: 
    ! ----------------------------------------------------------- 
! NAME : John Smith                         User ID: xxxxxxxx 
! DUE DATE : mm/dd/yyyy                                       
! PROGRAM ASSIGNMENT #                                        
! FILE NAME : xxxx.yyyy.zzzz (your unix file name)            
! PROGRAM PURPOSE :                                           
!    A couple of lines describing your program briefly        
! -----------------------------------------------------------

    Here, User ID is the one you use to login. It is not your social security number!

    For each function in your program, include a simple description like this: 

    ! ----------------------------------------------------------- 
! FUNCTION  xxyyzz : (function name)                          
!     the purpose of this function                            
! PARAMETER USAGE :                                           
!    a list of all parameters and their meaning               
! FUNCTION CALLED :                                           
!    a list of functions that are called by this one          
! -----------------------------------------------------------
  2. Your programs must contain enough concise and to-the-point comments. Do not write a novel!
  3. Your program should have good indentation.
  4. Your program must use IMPLICIT NONE and INTENT properly, and should not use GOTO.

Program Specification

Your program must follow exactly the requirements of this programming assignment. Otherwise, you receive 0 point even though your program runs and produces correct output. The following is a list of potential problems.
  1. Your program does not use the indicated algorithms/methods to solve this problem.
  2. Your program does not follow the structure given in the specification. For example, your program is not divided into FUNCTION, SUBROUTINE, MODULE, etc when the specification says you should.
  3. Any other significant violation of the given program specification.
  4. Incorrect output format. This will cost you some points depending on how serious the violations are. The grader will make a decision. Hence, carefully check your program output against the required one.

Program Correctness

If your program compiles and runs, we will check its correctness. We normally run your program with two sets of input data, one posted on this programming assignment page (the public one) and the other prepared by the grader (the private one). You program must deliver correct results for both data sets. Depending on the seriousness of the problem(s), significant deduction may be applied. For example, if your program delivers all wrong results for the public data set, you receive 0 point for that component.

The README File

A file named README is required to answer the following questions:
  1. Question: What is the range of initial values you used for both methods in order to find the smallest positive root? What is this root?
  2. Question: Since the given equation is not in the form of x = g(x), how did you transform the original equation to x = g(x)? Show your calculations. Would this transformation always yield the same result as that of Newton's method does?
  3. Question: What is the largest root that is less than 10? What is your initial guess in order to find it? How many iterations does each method require? Do the results from these two methods agree with each other? If one method fails, provide your analysis for the failure. The use of a plotting program such as gnuplot is very helpful. Show your output and discussion here.
  4. Question: We mentioned in class that Newton's method can be slow if the desired root is a multiple root. Equation f(x) = (x - 1)10 = 0 is an example, where x* = 1 is a root of multiplicity 10. Two methods were discussed in class to address this multiple root issue. Modify your Newton's method program (no fixed-point iteration) so that you could solve this equation faster. Use a table discussed in class to compare the results and answer this question: with the same initial value as used on the class note how many iterations are needed to converge to the only root x* = 1? In this table, list the result of each iteration generated from Newton's method and the two modified method.

You should elaborate your answer and provide details. When answering the above questions, make sure each answer starts with a new line and have the question number (e.g., Question X:) clearly shown. Separate two answers with a blank line.

Note that the file name has to be README rather than readme or Readme. Note also that there is no filename extension, which means filename such as README.TXT is NOT acceptable.

README must be a plain text file. We do not accept files produced by any word processor. Moreover, watch for very long lines. More precisely, limit the length of each line to no more than 80 characters with the Return/Enter key for line separation. Missing this file, submitting non-text file, file with long lines, or providing incorrect and/or vague answers will cost you many points. Suggestion: Use a Unix text editor to prepare your README rather than a word processor.

Final Notes

  1. Your submission should include two files, namely: prog1.f90 and README. Please note the way of spelling filenames.
  2. Always start early, because I will not grant any extension if your home machine, network connection, your phone line or the department machines crash in the last minute.
  3. Since the rules are all clearly stated, no leniency will be given and none of the above conditions is negotiable. So, if you have anything in doubt, please ask for clarification.
  4. Click here to see how your program will be graded.