The College of the Holy Cross

Mathematics 372 -- Numerical Linear Algebra

Syllabus, Spring 2007

Professor: John Little
Office: Swords 335
Office Phone: 793-2274
email: little@mathcs.holycross.edu (preferred) or jlittle@holycross.edu
Office Hours: MWF 10-12, TR 1-3, and by appointment.

Course Description

Numerical linear algebra is the mathematics of

computing approximate solutions of systems of linear equations,
computing eigenvalues and eigenvectors of matrices and other quantities from linear algebra, and
applications of these techniques to problems in various parts of applied mathematics.

In basic linear algebra (MATH 244), you learned (some version of) the basic Gaussian elimination strategy for solving linear systems. You probably only dealt with very ``small systems'' however (certainly no more than 6 or 8 variables and equations) because you were performing all the calculations by hand.

Essentially the same mathematics is now a mainstay of many areas of applied mathematics. For example, a standard method to obtain solutions of realistically complicated ordinary or partial differential equations is to discretize the domain of the independent variables and replace the differential equations by algebraic (e.g. linear) equations on the values of solutions at the discrete set of points. A similar discretization approach leads to systems of linear equations modeling the image reconstruction problem in computed tomography (such as SPECT scans in medical imaging).

One of the features of contemporary applications of linear algebra, however, is that much larger systems are typical (systems of equations with hundreds or thousands of variables and equations). This means that computations must be done using the computer, and also typically using the machine floating-point representation of decimal numbers. As we will see, this ``computer simulation'' of real numbers has some undesirable properties -- not all coefficients in linear systems can be represented exactly, and round-off errors can accumulate in computations. Thus, for reliability, numerical software for linear algebra computations must be designed to minimize or control round-off error as much as possible.

For problems dealing with eigenvalues, and a generalization called the singular value decomposition for general (not necessarily square) matrices, the algorithms you learned in MATH 244 (based on the characteristic polynomial and root-finding) are also too cumbersome to apply to large problems. Thus another major aspect of the course will be the development of several new techniques based on matrix factorizations.

In this course, we will consider the following topics (a more detailed, day-by-day, schedule will be maintained on the course homepage).

Introduction: How linear equations arise in several types of applications, the MATLAB software system, floating-point arithmetic and round-off error phenomena (about 5 days).
Unit II: Direct methods for systems of linear equations -- Gaussian Elimination interpreted as matrix factorization, pivoting strategies, techniques for special classes of matrices, vector and matrix norms, condition numbers and error analysis (about 9 days)
Unit III: Least-squares problems, QR factorization, the singular value decomposition, and applications (about 12 days)
Unit IV: Numerical eigenvalue techniques -- the basic and shifted inverse power methods, and the QR algorithm (about 6 days)
Unit V: Iterative techniques for systems of linear equations -- Jacobi and Gauss-Seidel iteration, their analysis via matrix and vector norms, applications to computed tomography (about 8 days)

As always, some additions, deletions, or rearrangement of topics may become necessary as we progress through the course. Any changes will be announced in class and on the class homepage.

Text

The primary text for the course is Fundamentals of Matrix Computations, 2nd Edition, by David S. Watkins, published by Wiley, ISBN: 978-0-471-21394-9. Xeroxed notes will also be distributed for the section of the course dealing with applications to computed tomography.

Course Format

We will be using the software package MATLAB on the departmental Sun workstation network quite extensively throughout the course to implement the techniques we discuss and to generate numerical solutions to problems. About 6 class meetings will take place in the SW 219 computer lab and many of the individual problem sets will include problems for which you will need to use MATLAB. Most of the other meetings of the class will be structured as lecture/discussions. Each person will also give oral problem presentations based on assigned (``theoretical'') problems from the weekly problem sets two or three times during the semester.

Grading

The assignments for the course will consist of:

One takehome midterm exam worth 25% of the course grade. Tentative dates: given out March 16, due March 23.
Takehome final exam worth 30% of the course grade. This will be due on May 9 (the day inclass finals will be given for 1:00pm MWF classes).
Weekly problem sets/lab writeups, worth 40% of the course grade. (For the last three weeks of the semester, you will be working on a larger final lab project assignment which will be worth 15% included in this total)
Oral problem presentations, worth 5% of the course grade.

If you ever have a question about the grading policy, or about your standing in the course, please feel free to consult with me.

Departmental Statement on Academic Integrity

Why is academic integrity important?

All education is a cooperative enterprise between teachers and students. This cooperation works well only when there is trust and mutual respect between everyone involved. One of our main aims as a department is to help students become knowledgeable and sophisticated learners, able to think and work both independently and in concert with their peers. Representing another person's work as your own in any form (plagiarism or ``cheating''), and providing or receiving unauthorized assistance on assignments (collusion) are lapses of academic integrity because they subvert the learning process and show a fundamental lack of respect for the educational enterprise.

How does this apply to our courses?

You will encounter a variety of types of assignments and examination formats in mathematics and computer science courses. For instance, many problem sets in mathematics classes and laboratory assignments in computer science courses are individual assignments. While some faculty members may allow or even encourage discussion among students during work on problem sets, it is the expectation that the solutions submitted by each student will be that student's own work, written up in that student's own words. When consultation with other students or sources other than the textbook occurs, students should identify their co-workers, and/or cite their sources as they would for other writing assignments. Some courses also make use of collaborative assignments; part of the evaluation in that case may be a rating of each individual's contribution to the group effort. Some advanced classes may use take-home examinations, in which case the ground rules will usually allow no collaboration or consultation. In many computer science classes, programming projects are strictly individual assignments; the ground rules do not allow any collaboration or consultation here either.

What are the responsibilities of faculty?

It is the responsibility of faculty in the department to lay out the guidelines to be followed for specific assignments in their classes as clearly and fully as possible, and to offer clarification and advice concerning those guidelines as needed as students work on those assignments. The Department of Mathematics and Computer Science upholds the College's policy on academic honesty. We advise all students taking mathematics or computer science courses to read the statement in the current College catalog carefully and to familiarize themselves with the procedures which may be applied when infractions are determined to have occurred.

What are the responsibilities of students?

A student's main responsibility is to follow the guidelines laid down by the instructor of the course. If there is some point about the expectations for an assignment that is not clear, the student is responsible for seeking clarification. If such clarification is not immediately available, students should err on the side of caution and follow the strictest possible interpretation of the guidelines they have been given. It is also a student's responsibility to protect his/her own work to prevent unauthorized use of exam papers, problem solutions, computer accounts and files, scratch paper, and any other materials used in carrying out an assignment. We expect students to have the integrity to say ``no'' to requests for assistance from other students when offering that assistance would violate the guidelines for an assignment.

Specific Guidelines for this Course

In this course, collaboration on the regular weekly problem sets/labs is allowed, even encouraged. If you do take advantage of this option, you will be required to state that fact in a "footnote" accompanying the problem solution. The midterm and final exams will operate under different ground rules, though. Those will be strictly individual assignments and consultation will be permitted only with Prof. Little. A statement of this policy will accompany the assignments when they are given out. Failure to follow this rule will be treated as a violation of the College's Academic Integrity policy.