Project
Numerical Integration
Computer Science Majors
Introduction
The purpose of this project is two-fold: to develop software to numerically approximate definite integrals via two different algorithms, and to compare the efficiency of those algorithms. Both activities are representative of what computer scientists do: write code and analyze algorithms.
Backgroundrequired: ability to program in some higher level language, presence in or completion of Calculus II.
Details.
The two methods we wish to compare are the Trapezoidal Rule and Simpson's Rule. Both are used for approximating integrals.
"Why would you want to approximate an integral? Why not just do it? You know – will antiderivatives like we learned!"
Some functions simply do not have antiderivatives. And they are not mathematically contrived functions but important ones with vast applications. By far the best example of this is the following exponential function
This function has as its graph the well known bell shaped curve that appears in many statistical applications with most of those requiring computation of the area underneath some portion of the curve such as
Approximating Definite Integrals
Since there is no antiderivative of such a function, to get an integral, all we can do is specify how much accuracy (decimal places) we want and then approximate it to within that accuracy.
How to approximate it? In Calculus II you began with rectangles and Riemann Sums. This provides a nice conceptual basis for the rest of the course but is not very efficient. By efficient we mean that you have to do a lot of computations to get a little accuracy.
Geometrically, by using rectangles, you are treating the function locally as if it is flat or horizontal. This is rarely true and not very accurate.
Two better approximations are
the Trapezoidal Rule which treats the function locally as a straight line and
the area as sums of areas of trapezoids
Simpson's Rule which treats the function locally as a parabola and the area as the
sum of areas of rectangles with parabolic tops.
where by "better" we mean that one can get the same accuracy as with rectangles with much less work (computations).
Reading to be done:
in Calculus byVarberg, Purcell and Rigdon (8th edition), please read section 11.2 Numerical Integration.
in Edwards and Penney please read
Your project
Part One
develop code to perform both algorithms. This means, for each one,
obtaining interactively from the user
the left endpoint of the interval of integration
the right endpoint
n, the number of subdivisions of the interval (see reading)
and outputting the numerical estimate
This leaves the issue of the function to be integrated. Allowing the user
to enter in the function at run time would be a formidable programming task.
Why? Essentially they would be typing in characters which you would have
to parse and form into a mathematical expression. At that point you would
encounter the problem of generating machine code for it since your program
would have already been compiled.
So we will leave that issue aside for now and allow you to hard code a "sample"
function in to your program as a demo. Of course if you wish to tackle the
general problem of inputting a function, go right ahead!!
Once your program is running, you need to test it, an important step in software
development.
You can compare to exact answers by picking functions whose integrals you can
do by hand (pick two and do this).
You can compare to the correct numerical approximations by using Maple and
the Maple functions trapezoid and simpson , both of which are in the student
library there. Your answers should match theirs as they are the same numerical
algorithm.
Provide in your write up all comparisons you made.
Questions on testing:
- what should happen if you approximate the integral of a linear function with the Trapezoid Rule? Try this out
- what should happen if you approximate the integral of a quadratic function with Simpson's Rule? Try this out!
Part Two Efficiency and Accuracy
Using a test function such as the one above and an interval of your choice, pick 10 different values of n and approximate the integral with both the Trapezoid Rule and Simpson's Rule. Find the exact answer either by hand or with Maple.
Having collected this data, organize it into a table that has 6 columns: n , the exact value, the value with the Trapezoid Rule, the error with the Trapezoid Rule, the value with Simpson's Rule and the error with Simpson's Rule. Your table should have 11 rows including the titles at the top.
Use the data from your table and plot Error vs n for both Trapezoid and Simpson's Rule on the same graph (so 20 data points total).
Discuss your findings and also relate them to the error formulas in the section that you did the background reading on. This should result in a Conclusion section for your paper.
Part Three What you turn in when finished
A paper which includes
Introduction to Numerical Integration including background on
the Trapezoidal and Simpson's Rules
Your Software
hardcopy which should be documented
electronic version which can be run so include all necessary
instructions
Data Collection (see Part Two) including plot
Analysis and Conclusion
Note to instructor: the project may be shortened by having the students use Maple to generate the estimates rather than writing their own software. This would put the emphasis more on efficiency of the algorithm than generation of code.