CCS110   Computational Problem Solving

Many systems in the natural sciences can be represented by means of a mathematical expression, known as a mathematical model.  This expression may be fairly complex in form, and thus it may not be possible to make a reasonable application of the standard methods of evaluation to the expression.  If this is true, then it is standard practice to make an attempt at evaluating the expression by various approximation methods.  In particular, by methods that involve computational algorithms.

For any problem that we must consider there are a number of steps that are suggested for one to take in the process of finding a computational solution of the problem, and then for assessing the viability of this solution.  We suggest the following five steps:

The Five Step Process



1)   Identify the problem.

2)   Express the problem in terms of a mathematical model.

3)   Construct a computational method for solving the model.

4)   Implement the computational method on a computer.

5)   Assess the results; if there is a relatively large disparity between your solution and the actual solution, or what you know can actually be true for the problem, then reassess the problem and try the process again.




Applying the Five Step Process

Gaining a better understanding of this five step process can best be accomplished by applying it to an actual problem.  One such problem would be that of finding the area of a region bounded within a set of known curves.



Example:    Consider the area of the region in the xy-plane that is above the x-axis and below the curve y = x² (a parabola) for those values of x that range over the interval from 0 to 4.  By implementing this five step process, we shall attempt to find an approximation of the area of this region.



1.   Identify the problem. We wish to find the area of the region that lies above the x-axis and below the parabola y = x² for values of x between 0 and 4.  We try to incorporate all directly or indirectly supplied information such as the equation y = x² for the parabola, the equation y = 0 for the x-axis, and the interval [0, 4] on which the values of x are restricted.

2.   Express the problem in terms of a mathematical model. This problem can be approached by finding the definite integral of the function x² from 0 to 4, in which we will obtain the exact value of the area of the region, or it can be approached by approximating the region defined by our curves with a collection of rectangles and then by approximating the area of the region by summing the areas of the rectangles.

3.   Construct a computational method. Since integration is more of an analytical method, and one for which the reader may be unfamiliar, we are going to take the numerical approach of approximating the area with the sum of areas of rectangles.  To do this we will need to construct a series of rectangles that not only approximate the region, but also we need rectangles whose areas are easy to compute.  This can be accomplished by constructing rectangles, lying side by side across the region, whose sides are parallel to the coordinate axes--rectangles with vertical and horizontal sides.

4.   Implement the computational method. Let us take the graph of our curves and build a series of four rectangles of equal width, whose bases lie along the line y = 0 (the x-axis), and whose heights reach the curve y = x² at the point above the right endpoint of each base (which also happens to be the highest point on y = x² above each base).  This can best be accomplished with rectangles of width 1 unit having bases along the intervals [0, 1], [1, 2], [2, 3], and [3, 4].  The resulting graph gives you a series of rectangles of width 1 and heights 1, 4, 9, and 16.  Finding the sum of their areas, one obtains a value of 30 square units.

5.   Assess the results. With this computational method providing an answer of 30 square units, we must now consider how this compares with the actual area of the region.  Since the area of our region lies within a triangle of base 4 and height 16, we see that our region must have an area that is greater than 0 and less than the area of this triangle, which is 32 square units.  Since our approximation of 30 square units does lie within these bounds (although our approximation is necessarily greater than the actual area), we see that our model yields a value that is consistent with what we would expect of the solution of the problem, although it may not yield a satisfactory approximation.  Assuming that there is no fault in our model, how can we obtain a more accurate approximation?  Increase the number of rectangles (say, eight rectangles, each of width 0.5 units), and see how the corresponding solution is affected.  (This should yield a better approximation.)



Now, as we can see from this example, if we know very little about the characteristics of the solution of the problem that we are modeling, then we will have little which we can use to determine if the resulting approximation of the solution of the model is a feasible representation of the solution of the problem.  This then raises the question of how we can tell if a computational solution of a model is a good approximation of the solution of a problem in the real world.

There are two things that we are dealing with in the types of problems we are considering.  One is the mathematical model that we use to represent the problem, and the other is the computational method that we incorporate to approximate the solution of the mathematical model.  If either of these is faulty, then we would suspect that our approximation might be an unreliable representation of the solution of the original problem.

We verify the reliability of a mathematical model by how well its solution represents the original problem, and by the viability of the conclusions that can be made from the model.  It is not likely that a model will yield a perfect representation of the problem--there is usually a trade-off between simplicity and precision.  Sometimes finding the best model for a problem involves a considerable amount of experimentation in itself.  However, once a model has been chosen, we must consider the conclusions that can be derived from the model.  If the assumptions that are made in the construction of the model are true, then the conclusions that can be made from the model must also be true.  Thus, if from the model we make a conclusion that is not true, then something about our assumptions must be incorrect, and we may need to reconsider the model.

Verification of a computational method can be difficult.  There are a number of things that we must consider with computational methods.  A computational method may yield a solution that fits reasonably well with what we would expect from our mathematical model, but it may do so in error--as a fluke.  A slight change in the model or in some of the parameters that make up the model may bring out evidence of a fault in the computational method.  Thus it is always best to test a computational method by applying it to model whose solution is known exactly, and even, if possible, to apply the method to a model in which the method should yield the exact solution (in the above case, find the area of a large rectangle by summing the areas of smaller rectangles).  In contrast, a computational method may be designed well in theory, but not work well in practice.  Error from the round-off of various numerical values may propagate through subsequent computations and affect the solution, although the method of deriving the solution is without fault.  Human error may also make a deceptive contribution to the application of a computational method.

There are a number of things that we must take into consideration when attempting to derive a computational solution of a problem, and the prospect of making such an approach on a problem may seem a bit foreboding.  However, with practice, the standard techniques of application will become more familiar, and these considerations more routine.


Exercises

I. The Five Step Process.



Follow the example of the five step process given above to approximate the area of the region below the given curve and above the x-axis on the given interval.  Use four rectangles of equal width for each approximation.



1.   y = 2 x + 3 on [0, 4]
2.   y = 4 - x² on [-2, 2]
3.   y = 1/x on [1, 3]



II. Using a Java applet.



Using a Riemann Sum applet will allow you to further explore the effects of increasing and decreasing the number of rectangles used to approximate the area of a region in the plane.  (Be sure to give the applet a sufficient amount of time to load before trying to implement it.)

For each of the following, use the Riemann Sum applet to approximate the value of the area below the given curve and above the x-axis on the interval [-1, 1].  (Enter the formula in the box provided and press the DRAW button.)



1.   y = x²          (Note: enter this as x^2)
2.   y = 2 x² + 3          (Note: enter this as 2*x^2+3)
3.   y = sin(10 x) + 5
4.   y = log(7 x + 7) + cos(7 x)          (This is the default equation)