Mathematics 172 – Numerical Analysis II Information on Final Projects March 16, 1999

General Information

As announced in the course syllabus, one of your assignments for this course will be a group term project, leading to a paper of 10 - 15 pages. You may work individually, or in groups of 2, 3 on the term project; I will leave the selection of groups up to you, unless problems develop. All members of a group are expected to participate fully in the development of the project, and as a part of the final submission of materials, all members of each group will be asked to give evaluations of the contributions of the others. I will be assigning individual grades for the project based on the paper, and the “peer reviews” from your fellow group members. The following gives a timetable to help you structure your work on this assignment and several suggested topics for you to consider. Other topics of your choice are also possible, but you will need to consult with me before March 24 to make sure the idea you have in mind is acceptable.

Timetable

1) By Thursday, March 24 at the latest, notify me of the group you have chosen to work with, and the topic you will be pursuing. I will be happy to make suggestions and/or help you locate materials. Mr. Stankus the Science Librarian and the other library staff will also be happy to assist you if you need to find other presentations of the material.

2) The week of April 19, I will schedule a short “progress report” session with each of the groups (at mutually convenient times outside of class). By this time, you should be prepared to discuss what you want to put in the paper. I will be more than happy to meet with you before and after these formal progress report sessions as well to help you tackle your projects.

3) The term project papers will be due Tuesday, May 4. (This is a firm deadline. I will not be able to accept late work on this assignment!)

Suggested Topics

1. Numerical Methods for Multiple Integrals.

The techniques that we developed for approximating definite integrals (in particular Trapezoidal Rule, Simpson’s Rule, Romberg Integration, and Gaussian Quadrature) can all be extended to give methods for approximating multiple integrals as well:

\begin{matrix}∫ ∫_{R} f(x, y)dxdy \\ ∫ ∫ ∫_{R} f(x, y, z)dxdydz \end{matrix}

over regions R ⊂ R^{2} and R^{3} as well. For this project, you would research these methods and write up a paper explaining them. You should explain the derivations of any formulas that you use, and you should include several original examples illustrating the methods “in action.” Be sure to include an example of a region with “curved” boundaries, where the integral will involve variable limits of integration. (For instance, to integrate over the unit disk in R^{2}, you would need to consider:

∫_{−1}^{1} ∫_{−\sqrt{1−x^{2}}}^{√\overline{1−x^{2}}} f(x, y)dydx

Then, develop Maple programs to perform these calculations. Test them on several examples, and compare with Maple’s built-in routines for evaluation of integrals. Section 4.8 of our text is an excellent place to start.

2. Gauss-Laguerre Quadrature.

In class, we studied the Gaussian Quadrature method, which approximate values for definite integrals that are as good as possible for the number of function evaluations used. Recall, we had

∫_{−1}^{1} f(x) dx ≐ ∑_{i=1}^{n} c_{i}f(x_{i})

where the x_{i} were the roots of the nth Legendre polynomial, and the c_{i} are the corresponding weight factors obtained by integrating a Lagrange interpolating polynomial for f. This Gaussian quadrature method is just one of a class of methods that are based on properties of families of orthogonal polynomials. For this topic you would research another such method, called Gauss-Laguerre quadrature. This method is used on improper integrals of the form

∫_{0}^{∞} f(x)e^{−x} dx

For your paper, start out by presenting the the Laguerre polynomials. Give one or more definitions, compute the first few of them, and give a proof that they are orthogonal with respect to a certain inner product on a vector space of functions. Then develop the Gauss-Laguerre quadrature method, state and prove a theorem describing the accuracy of the method. Calculate a table of x_{i} and weight factors for this method for n-term quadrature formulas with n = 2, 3, 4, 5, 6 to 6 decimal-place accuracy at least (and compare with standard tables). Give some examples using your tabulated x_{i} and c_{i}.

3. A Boundary Value Problem for an ODE

The shape of a rotating axle whose ends are fixed in bearings is given by a function y = y(x) satisfying the differential equation

(1)  \frac{d^{4}y}{dx^{4}} − (5.12 × 10^{−4})ω^{2}y = 0

for x ∈ [0, 8], and the boundary conditions:

(2)  y(0) = y′(0) = 0;  y(8) = y′(8) = 0

In the equation (1), ω represents the “rotational speed” (angular velocity) of the shaft. Of course, y(x) = 0 is one solution of (1) and (2) corresponding to a straight, undistorted shaft. However, for certain critical speeds, the shaft may distort to the shape of another solution of the boundary value problem (with catastrophic consequences!) Your job for this project is to find an approximate value for the smallest such critical speed.

In our study of ODE in the second unit this semester, we dealt exclusively with initial value problems, for instance for a first-order equation:

\{ \begin{matrix}y′ = f(t, y) \\ y(t_{0}) = α \end{matrix}

For a second-order equation, y′′ = F (t, y, y′), initial conditions would be specified values for y(t_{0}) and y′(t_{0}). In other applications such as your problem above, we seek a solution y = y(x) of a differential equation on an interval [t_{0}, t_{f}], subject to conditions on the function (and possibly derivatives) at the endpoints. For this topic, you would research and present one of the usual methods for solving such problems – the Finite-Difference Method, which generates a system of equations to be solved for the approximate values of the solution function y(x) at a collection of points on [a, b]. If the ODE is linear, then the equations to be solved are a system of linear equations, and there is an interesting “twist” to the story, which you will learn about in the course of solving the problem above! There is a good discussion of the Finite-Difference Method in Section 11.3 of Burden and Faires; the “twist” mentioned above comes in carrying out the finite-difference method in this example, and is not covered in Burden and Faires. You will need to think carefully about connections with other topics we have discussed this semester.

4. Chebyshev Polynomials and Approximation of Functions.

The Legendre polynomials that we “ran into” in studying the Gaussian quadrature method is just one example of an orthogonal family of polynomials. There are many other similar families that have numerous applications in numerical analysis and other branches of applied mathematics. For this topic, you would research and present one such family, called the Chebyshev (Tchebysheff, etc. – there’s no standard method of transliterating Russian names!) polynomials. The first place to look here will be sections 8.3 and 8.4 of our text. Your paper should present the recursion relation for the Chebyshev polynomials. You should then derive the orthogonality relations. Next, give a formal proof of the fact about the Chebyshev polynomials discussed starting of Theorem 8.10 in the text: Of all polynomials of degree n, with leading coefficient equal to 1, \frac{1}{2^{n−1}} T_{n}(x) has the smallest maximum value on [−1, 1]. Explain how this observation leads to a method for picking the x_{i} for construcing an interpolating polynomial for a function that minimizes the error of interpolation. Finally, you should explain how functions on [-1,1] can be expanded in terms of the Chebshev polynomials, and how this leads to a method for “economizing” power series expansions of functions, leading to more efficient methods for approximate function evaluation.

5. Multistep Methods for Initial Value Problems.

The Runge-Kutta methods (including Euler and Modified Euler) that we discussed in class solve initial value problems by generating a sequence of approximate values of the solution function(s). At each step, only the immediately previous value is used. (That is, in the Runge Kutta equations for w_{n+1}, only w_{n} appears, not w_{n−1}, or previous values.) There are other methods, called multistep methods that use more than one previous value as well. For this project topic, you would research two such methods called the Adams-Bashforth and Adams-Moulton methods. (See section 5.6 of Burden and Faires.) Write up full descriptions of the methods in (5.24) and (5.25) and illustrate with one or more examples selected from the exercises in that section (not the text examples!). How does the accuracy of Adams-Moulton compare with that of the 4th order Runge-Kutta method? Also explain how Adams-Bashforth and Adams-Moulton methods can be combined in a predictor-corrector scheme.

Another multistep method for solving initial value problems called Milne’s method is discussed in section 5.6 of the text. However, Milne’s method is prey to a condition known as instability, in which (under certain circumstances) the errors in the computed approximate solutions grow uncontrollably (even reducing the step size h has no effect). Approximate the solution of y′ = −10y, y(0) = .1 for t ∈ [0, 2] using Milne’s method with h = .04, .004 calculate the errors, and discuss the results.

Then read section 5.10 of Burden and Faires, which includes a more complete theoretical discussion of criteria for stability. For your paper, you should discuss the difference equation of a multistep method, the characteristic polynomial of the method, and explain the root condition for stability of the method. Using this theoretical information, explain why the Adams-Moulton method is preferable to Milne.

6. Newton’s Method for Systems of Equations

The basic Newton-Raphson iteration for solving f(x) = 0 that we discussed last semester:

x_{n} = x_{n−1} − \frac{f(x_{n−1})}{f′(x_{n−1})}

has a generalization for non-linear systems of n equations in n variables for all n ≥ 1. For this project, you would research the Newton method for systems starting with section 10.2 in Burden and Faires, describe the method, provide a proof for Theorem 10.7, which shows that this generalization also has quadratic convergence, implement the method in Maple, and apply it to solve problems 7, 8, 9 in that section. (These are applied problems where you must solve a system of non-linear equations.)