Math 6644:
Iterative
Methods for Systems of Equations
Spring
2012
Lecture Meetings: Tuesday
and Thursday 3:05 – 4:25 p.m.
Classroom: Klaus 2447.
Instructor: Professor Silas
Alben
Email: alben at math.gatech.edu
(the best way to contact me).
Office: Skiles 250, tel.
404-894-3312
Office hours: Tues., Thurs. 2 p.m. - 3 p.m. (subject to change) or by
appointment.
Course Introduction:
This
course is intended for advanced undergraduates and graduate students
in mathematics and all fields of science and engineering who want to
solve linear and nonlinear systems of
equations numerically. Such equations often arise when solving
differential and integral equations. This course will cover the
state-of-the-art methods in their basic form. The theoretical
material will focus on understanding why a given method works. The
practical material will involve writing programs in Matlab and
occasionally using built-in Matlab functions to try out different
methods. The topics are fundamental for practical work in scientific
computing, since many equations are impossible or impractical to
solve without the iterative methods we’ll consider. This course is
a math class, so we will spend some time understanding the
mathematics which make these methods effective.
Prerequisites:
You
are expected to know the material taught in MATH 2406 (Abstract
Vector Spaces) or MATH 4305 (Topics in Linear Algebra). Very
helpful, but is not absolutely required are: 1. some prior experience
in programming in Matlab, and 2. a prior course in numerical linear
algebra along the lines of MATH 6643.
Course
materials:
There
is one required text for the course:
Iterative Methods for Linear and
Nonlinear Equations (IMLNE) by C.T.
Kelley, SIAM: Society for Industrial and Applied Mathematics
(1995). It may be downloaded from:
http://www.siam.org/books/textbooks/download.php
Additional useful references on iterative methods for linear systems
(click to download):
1. An Introduction to the
Conjugate Gradient Method Without the Agonizing Pain
2. Templates for the Solution of Linear Systems
3. Iterative methods for sparse
linear systems (1st edition)
Towards
the middle of the course we may also cover
material from Solving Nonlinear
Equations with Newton's Method, also by
C.T. Kelley, SIAM: Society for Industrial and Applied
Mathematics (2003). This text has more information on the
practicalities of solving nonlinear equations numerically. The text
is not currently required for the course. We will let you know if it
becomes required later in the course.
Grading:
30%: Exam, tentatively set for April 19 in class (please
let me know of any conflicts immediately)
Download Spring 2010 exam for practice
50%: Three to five homework assignments.
20%: Course Project and in-class presentation.
The project is meant to be an application of a
few of the course methods to a problem from your own area of research.
The assessment for the project will be based partly on a short
presentation (5-15 minutes) with 5-10 Powerpoint slides during the last
week of class. The goal is to expose the class to the many possible
applications of these methods. More details will be given towards the
end of the course.
All HW assignments should be submitted electronically to
6644Spring2012 at gmail.
You
should scan any handwritten work into .pdf format, and merge it
with the output of any computer programs (figures, tables, typed
answers) into a single .pdf file. You should also submit any computer
codes together with the pdf in a single .zip archive to
the above address.
Note: Matlab codes for the book are provided here:
http://www.siam.org/books/kelley/fr16/matlabcode.php
The
codes were written for Matlab 15 years ago; hence they will sometimes
need some updating--consider this part of the HW assignment.
If
one of the codes does not run properly, you should either fix it or
write your
own code from scratch using the given code as a template.
Typically a subset of the HW problems will be graded.
HW1, due Tuesday, Feb. 14 at 3 p.m. (by email):
From the text: 1.5.1, 1.5.3, 1.5.4, 2.8.3, 2.8.5, 2.8.7, 2.8.11,
2.8.12, 2.8.13.
HW1 Solutions
HW2, due Tuesday Mar. 13 at 3 p.m.:
From IMLNE (the required text), with
some modifications:
1: 3.9.3
2: 3.9.6. Use the mesh sizes N = 50, 100, 200 (not including the
boundary points).
The centered difference discretizations are:
u''_i = (u_{i+1}-2*u_i + u_{i-1})/h^2, i = 1,...,N.
u'_i = (0.5*u_{i+1}-0.5*u_{i-1})/h, i = 1,...,N.
The preconditioner M should be the inverse of the second-derivative
term in the ODE.
Answer the following questions:
a. How does the performance of the iteration depend on the mesh, with
and without the preconditioner M?
b.
Try the other preconditioners Gauss–Seidel and Jacobi. How do the
results (relative residual versus iteration count) of these
preconditioners compare with the preconditioner M above for N = 50,
100, 200?
c. Resolve the problem with BiCGSTAB and TFQMR (codes
available online) with no preconditioner and with preconditioner M.
Compare the relative residual versus iteration count in these
cases with GMRES (part a).
3: Redo #2a with restarts. To do
this, call the gmres.m code (available online) within another code you
write which has an outer loop to control the restarting as in Algorithm
gmresm (in the text). Plot the relative residual versus the number of
iterations, for restart intervals m = 3, 6, 10, 15, infinity.
Rank the values in terms of number of iterations required, and the
total time required (use Matlab's etime function).
4: 3.9.9
5: 5.7.6
6: 5.7.9
7: 5.7.14
8: 5.7.20
HW2 Solutions
Course project
Instructions:
Select
one linear system of equations (for #1) and one nonlinear system of
equations (for #2) from your own research or your research area.
1. Do either a or b (not both):
a. Select a symmetric linear system of equations. Apply CG to it with no preconditioner and with a preconditioner and
plot the residual versus iteration count in each case. Also record and compare CPU times in matlab.
b. Select a nonsymmetric linear system. Apply preconditioned GMRES to it and one of the other methods
in sections 2.6 or 3.6 and compare the plots of residual versus iteration count.
2. Select a nonlinear system of equations and then do all of the following:
a. Apply the basic Newton's method and the Shamanskii method with a few different
values of m. Try to find the m which minimizes CPU time in matlab.
b. Apply Newton-GMRES with restarts to the system in the previous step (#2a). Try to find the restart number
which minimizes CPU time for a given convergence tolerance.
c. Apply Broyden's method to the same system as in #2b and #2c, and compare cputime as a function of the size
of the linear system with Newton-GMRES with nearly optimal restarting and the basic Newton method.
Two due dates:
1. Apr. 1 at 5 p.m.: Submit an email to 6644Spring2012@gmail.com which describes
a. the problem area,
b. some possible equations (abbreviated for plain text)--you can change these later if desired,
c. some preliminary results.
2. Apr. 15 at 5 p.m. Submit by email to 6644Spring2012@gmail.com 5-10 final slides (in horizontal "landscape" format)
explaining the equations and results in a single pdf file.
You will have 8-10 minutes to present these slides to the class during Apr. 17--26.
(I will announce who presents on which dates later on).
HW3, due Thursday, Apr. 26 at 3 p.m.:
1: 6.5.9
2: 7.5.8
3: 8.5.7