Programming Assignment III

Due on Friday, December 10, 2010 @ 11pm

100 points

In this programming assignment, you are to write a Fortran 90 program that uses modules to compute interpolating polynomials. Your program should include two modules: Lagrange and Newton. Each module contains two PUBLIC subroutines, and all other data items and/or subprograms should be PRIVATE.

Module Lagrange has two public subroutines L_Coef() and L_Eval() defined as follows:

Subroutine L_Coef(x, y, a, n):
This subroutine has four arguments as follows:
- Array x contains the input values of x₀, x₁, ..., x_n, and array y contains the input values of y₀, y₁, ..., y_n.
- n is an integer larger than 1 giving the highest subscript of the input data points.
- Array a is used to return the computed coefficients of the interpolating polynomial of degree n. Therefore, its subscript also goes from 0 to n.
After receiving input arrays x and y and the highest subscript n, subroutine L_Coef() computes the coefficients of the interpolating polynomial of degree n with Lagrange method, and returns these coefficients with array a. You should not change the values in x, y, and n.
Subroutine L_Eval(x, a, n, p, q, m):
This subroutine has six arguments as follows:
- Array x is the input array that contains x₀, x₁, ..., x_n.
- Array a contains the coefficients of the interpolating polynomial of degree n computed by subroutine L_Coef().
- n is an integer giving the highest subscript of the input data points.
- Array p contains a set of m values p₁, p₂, ..., p_m passed to this subroutine.
- m is the number of data values in array p.
- Array q is an output array that will contain the results obtained by evaluating the interpolating polynomial at the values in array p.
After receiving array x, coefficients a and new data values in array p, for each value in p(k), where 1 <= k <= m, this subroutine uses input array x and coefficient array a to compute its corresponding value with the interpolating polynomial, and stores the result in q(k). Therefore, on return, array q contains m computed values. You should not change the values in x, a, p, n and m.

Module Newton also has two public subroutines N_Coef() and N_Eval(). The use and meaning of arguments in these two subroutines are identical to those in module Lagrange, and, hence, will not be repeated. However, you must (1) implement Newton's method with divided difference using a rank 1 array, and (2) evaluate this interpolating polynomial with the nested form. Otherwise, you will receive zero point for this part.

After designing these two modules, you should write a Fortran 90 main program to read in a set of input, compute the coefficients with Lagrange method and evaluate the values at new data points. Then, this same main program should compute the coefficients with Newton divided difference method and evaluate the values at new data points. Note that since Lagrange method and Newton divided difference method use the same data points to compute the coefficients and the same new data points, the computed new values should be identical.

Input and Output

The input to your program has the following format. The first line contains a positive integer larger than 1, giving the highest subscript of the input data points. This is followed by n+1 lines, on each of which there is a pair of real numbers for x_i and y_i. This is followed by the value of m on a single input line. Finally, there are m values for array p.


n  <-- the maximum index of the input data points
xx.xx  xx.xx values for data point 0
xx.xx  xx.xx values for data point 1
    .....    values for other data points
xx.xx  xx.xx values for data point n
m            m = # of new values
xx.yy  xx.yy ...... xx.yy xx.yy's are the new values

Your program should use the given input to find the Lagrange and Newton interpolating polynomials and use these polynomials to interpolate some new data points. The following is the output format of your program:


*****************************************************
*** Lagrange and Newton Interpolating Polynomials ***
*****************************************************
a blank line
*** Input data ***
a blank line
xx.xx  xx.xx values of x₀ and y₀
xx.xx  xx.xx values of x₁ and y₁
    .....    other data points
xx.xx  xx.xx values of x_n and y_n
a blank line
***********************
*** Lagrange Method ***
***********************
a blank line
*** Computed Coefficients ***
a blank line
0 - xx.yy values of a₀
1 - xx.yy values of a₁
  .....	values of other coefficients
n - xx.yy values of a_n
a blank line
*** Interpolated Values ***
a blank line
1 -- xx.yy  xx.yy values of p₁ and q₁
2 -- xx.yy  xx.yy values of p₂ and q₂
    ......        values of other p's and q's
m -- xx.yy  xx.yy values of p_m and q_m
a blank line
****************************************
*** Newton Divided Difference Method ***
****************************************
a blank line
*** Computed Coefficients ***
a blank line
0 - xx.yy values of a₀
1 - xx.yy values of a₁
  .....	values of other coefficients
n - xx.yy values of a_n
a blank line
*** Interpolated Values ***
a blank line
1 -- xx.yy  xx.yy values of p₁ and q₁
2 -- xx.yy  xx.yy values of p₂ and q₂
    ......        values of other p's and q's
m -- xx.yy  xx.yy values of p_m and q_m

There are a number of important notes:

Study Fortran 90 format here. Use appropriate format editing in your program. You should show at least seven significant digits.
While the computed coefficients from Lagrange method are different from those from Newton method, the interpolated values are the same in theory. However, in reality, you may not be able to get exactly the same results due to different ways of obtaining these values.
You have to use the one-dimensional array version to implement Newton divided difference method and use the nest form for evaluation. Otherwise, you will receive ZERO point for the Newton divided different method.
Use single precision and assumed-shape array in all subprograms. Therefore, your program must show at least seven significant digits.

Sample Input

The following shows three sample input files. Since the degrees are not high, you may use your calculator to validate the answer.

The first sample input is generated from the LOG() (natural logarithm) function. Click here to download a copy of this file.

4
1.00000000   0.00000000
1.25000000   0.22314355
1.50000000   0.40546510
1.75000000   0.55961579
2.00000000   0.69314718
8  
1.0  1.2  1.25  1.4  1.6  1.75  1.8  2.0

The second sample input is generated from function EXP(-x*x). Click here to download a copy of this file.

5
0.00000000   1.00000000
0.40000001   0.85214376
0.80000001   0.52729237
1.20000005   0.23692775
1.60000002   0.07730473
2.00000000   0.01831564
11   
0.00  0.25  0.40  0.50  0.75  1.00  
1.20  1.50  1.60  
      1.75  2.00

The gamma function Γ(x) is a real transcendental function that interpolates factorial values at positive integers. At any positive integer n, the gamma function is Γ(n) = (n-1)!. For example, we have Γ(1) = (1-1)! = 1, Γ(2) = (2-1)! = 1! = 1, Γ(3) = (3-1)! = 2! = 1, Γ(4) = (4-1)! = 3! = 6, Γ(5) = (5-1)! = 4! = 24, Γ(6) = (6-1)! = 5! = 120, Γ(7) = (7-1)! = 6! = 720, and so on. The third sample input is generated from factorial, hopefully, to interpolate the well-known gamma function. Click here to download a copy of this file.

6
1.0   1.0
2.0   1.0
3.0   2.0
4.0   6.0
5.0   24.0
6.0   120.0
7.0   720.0
10  
1.0   1.5   2.5   3.5   4.0   
4.5   5.5   6.0   6.5   7.0

There are other test problems with known solutions in examples and exercises in Chapter 8 of our textbook.

Submission Guidelines

General Rules

All programs must be written in ANSI Fortran 90.
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.
Your programs should be named as
- prog3.f90 for your main program.
- Lagrange.f90 for module Lagrange.
- Newton.f90 for module Newton
Note that Unix filename is case sensitive. As a result, prog3.f90, lagrange.F90, NEWton.f90, etc are not acceptable.
We will use the following approach to compile and test your programs:
```
f90 Lagrange.f90 Newton.f90 prog3.f90 -o prog3 <-- compile your program
prog3 < 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.
Your implementation should fulfill the program specification as stated. Any deviation from the specification will cause you to receive zero point.
A README file is always required.
No late submission will be graded.
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.

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

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          
! -----------------------------------------------------------

Your programs must contain enough concise and to-the-point comments. Do not write a novel!
Your program should have good indentation.
Your program must use IMPLICIT NONE, INTENT, PUBLIC, PRIVATE and assumed-shape arrays properly, and should not use GOTO. Feel free to use ALLOCATABLE arrays.

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.

Your program does not use the indicated algorithms/methods to solve this problem.
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.
Your FUNCTIONs or SUBROUTINEs should not use identifiers/entities declared in the main program.
Only assumed-shape arrays are allowed for passing arrays around. Using any other method will receive a zero.
Any other significant violation of the given program specification.
Incorrect output format. This will cost you some points depending on how serious the violations are. Our 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:

Question: The third input file used to "interpolate" the gamma function can have large errors. One of them may be very obvious from your program's output. Use other systems such as Mathlab or gnuplot to plot graphs of the gamma function and your interpolating polynomial to find out how poor the interpolation you get can be. Present a summary of your analysis.
Question: This is a self-study question. Consider the following function. First, generate some number of equally spaced data points from -3 to 3. For example, if n = 6, then the x_i's are -3, -2, -1, 0, 1, 2, and 3. Write a simple program to compute the corresponding y_i's. Then, use Lagrange or Newton method to find an interpolating polynomial of degree 6, and compute some values, also equally spaced (e.g., -2.5, -1.5, -0.5, 0, 0.5, 1.5, 2.5 and other values). Do you see some strange results? What would be the result if n is increased to 8 and even 10? Report your findings and analyze the errors.

Now, write a program to generate n+1 Chebyshev points between -3 and +3, and use them to find an interpolating polynomial. Compare the results you obtain using Chebyshev points with the one obtained with equally spaced data points. Do you see the same problems? How well the Chebyshev points perform? Analyze your results and report your findings. Note that there is an error bound formula discussed in class. You may use it as an initial guide for your analysis.

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

Your submission should include the following files, namely: prog3.f90, Lagrange.f90, Newton.f90 and README. Please note the way of spelling filenames.
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.
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.
Click here to see how your program will be graded.