\magnification=\magstep1
\centerline{Mathematics 172 -- Numerical Analysis II}
\centerline{Information on Final Projects}
\centerline{March 16, 1999}
\bigskip
\noindent
{\bf General Information}
\bigskip
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 {\it before March 24} to make sure the idea you have in mind is 
acceptable.
\bigskip
\noindent
{\bf Timetable}
\bigskip
\item{1)}  By Thursday, March 24 {\it 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.
\item{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.
\item{3)}  The term project papers will be due Tuesday, May 4.  (This
is a {\it firm deadline\/}.  I will not be able to accept late work on 
this assignment!)
\bigskip
\noindent
{\bf Suggested Topics}
\bigskip
\noindent
{\it 1. Numerical Methods for Multiple Integrals.}  
\bigskip
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 {\it multiple} integrals as well:
$$\eqalign{\int\int_R f(x,y) dx dy &\cr
            \int\int\int_R f(x,y,z) dx dy dz & \cr}$$
over regions $R \subset {\bf R}^2$ and ${\bf 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 ${\bf R}^2$, you would need to consider:
$$\int_{-1}^1\int_{-\sqrt{1 - x^2}}^{\sqrt{1-x^2}} f(x,y) dy dx$$
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. 
\bigskip
\noindent
{\it 2. Gauss-Laguerre Quadrature.}
\bigskip
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
$$\int_{-1}^1 f(x)\ dx \doteq \sum_{i=1}^n c_i f(x_i)$$
where the $x_i$ were the roots of the $n$th 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
$$\int_{0}^{\infty} 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$.
\bigskip\noindent
\bigskip
\noindent
{\it 3.  A Boundary Value Problem for an ODE}
\bigskip
The shape of a rotating axle 
whose ends are fixed in bearings 
is given by a function $y = y(x)$ satisfying the differential equation
$${d^4 y \over dx^4} - (5.12 \times 10^{-4}) \omega^2 y = 0\leqno(1)$$
for $x \in [0, 8]$, and the boundary conditions:
$$y(0) = y^\prime(0) = 0; \qquad y(8) = y^\prime(8) = 0\leqno(2)$$
In the equation (1), $\omega$ 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 {\it critical} speeds, the shaft may distort to the 
shape of {\it another\/} solution of the boundary value problem
(with catastrophic consequences!)
Your job for this project is to
{\it 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 {\it initial value problems}, for instance for a first-order equation:
$$\cases{ y' = f(t,y) &\cr
          y(t_0) = \alpha&\cr}$$
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 {\it 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.
\bigskip
\noindent
 {\it 4. Chebyshev Polynomials and Approximation of Functions.} 
\bigskip
 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 {\it 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,  
${1 \over 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.
\bigskip
\noindent
{\it 5. Multistep Methods for Initial Value Problems.}  
\bigskip
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 {\it 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 {\it 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 \in [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 {\it difference equation} of a 
multistep method, the {\it characteristic polynomial} of the method, 
and explain the {\it root condition} for stability of the method.  Using 
this theoretical information, explain
why the Adams-Moulton method is preferable to Milne. 

\bigskip
\noindent
{\it 6.  Newton's Method for Systems of Equations}
\bigskip
The basic Newton-Raphson iteration for solving $f(x) = 0$ that 
we discussed last semester:
$$x_n = x_{n-1} - {f(x_{n-1})\over f'(x_{n-1})}$$
has a generalization for non-linear systems of $n$ equations in $n$ 
variables for all $n \ge 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 {\it 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.)
\bye


   

