Course 18.086: Mathematical Methods for Engineers II (Spring 2007) Department of Mathematics Massachusetts Institute of Technology

Information

• Lecturer: Benjamin Seibold. Email: seibold(at)math.mit.edu  Tel.: 324-2614. Office: 2-346. Office hours: WF 2-3
• Lecture: MWF 1 in room 2-132
• Grader: Hila Hashemi. Email: hhashemi(at)mit.edu  Office: 2-333. Office hours: by appointment
• Textbooks:
  • required: Gilbert Strang, Applied Mathematics and Scientific Computing
  • recommended: Gilbert Strang, Introduction to Applied Mathematics, Wellesley-Cambridge Press, 1986
• Course information, syllabus and grading policy

Policy

• Homework exercises: Most homework problems will involve small programs. The focus will be on Matlab.
• Computational project: Over the whole lecture time, each participant works on an extended problem related to the content of the course. Project may relate to your thesis work, but must not be too similar. Please consult the course information for more details.
  • Till Friday, 02/16/2007 (second week): Submit project proposal
  • Till Friday, 03/23/2007 (mid term): Submit intermediate report on project
  • Saturday, 05/12/2007: Project presentations, 10:00am-3:00pm, 2-132 (may be continued in last lectures)
  • Till Monday, 05/14/2007: Submit final report on project
  The 2006 list of projects may be helpful for ideas.

Outline

1. Initial value problems
   Linear initial value problems such as the wave equation and the heat equation admit closed form solutions in simple geometries. In a more complex setup they have to be solved numerically. Many important aspects seen for the linear problems regarding stability and covergence transfer to nonlinear initial value problems. Important examples for these are flow problems (fluid flow, traffic flow, etc.). Solutions to nonlinear problems may become non-smooth, and numerical methods have to consider this fact.
   Topics: Stiff problems, wave equation, heat equation, Airy equation, convection-diffusion, conservations laws, front propagation, Navier-Stokes equations, Fourier methods, finite differences, consistency, stability, covergence order, Lax equivalence theorem, CFL-condition, leapfrog method, staggered grids, shocks, upwind, Lax-Wendroff, finite volume methods, level set method
2. Solving large systems
   The discretization of partial differential equations by finite difference or finite element methods leads to large sparse linear systems, either directly for linear problems or as an auxiliary subproblem for many nonlinear problems. Gaussian elimination destroys the sparse structure, so solvers are required which make use of the specific sparse matrix structure.
   Topics: Applications yielding sparse matrices, elimination with reordering, iterative methods, preconditioning, incomplete LU, multigrid, Krylov subspaces, conjugate gradient method
3. Optimization and minimum principles
   Optimization problems search for the minimizer of some quantity (cost function), possibly given constraints. Quadratic cost functions lead to linear systems using Lagrange multipliers and Kuhn-Tucker conditions. Saddle point problems, regularization and calculus of variations will be presented as fundamental concepts. A different world in encountered in the case of linear cost functions. Applications are operations research and network problems. Solution algorithms are the simplex method or interior point methods. The underlying principle in all approaches is the concept of duality.
   Topics: Weighted least squares, duality, constrained minimization, inverse problems, calculus of variations, saddle point problems, linear programming, network problems, simplex method, interior point methods

Schedule

Course Materials

• Required. The course is based on the new book Applied Mathematics and Scientific Computing (2007) by Gilbert Strang.
• Recommended. For some chapters and background reading the book Introduction to Applied Mathematics by Gilbert Strang is recommended.
• Other Books The following books may be used for reference in single chapters, as noted
  • LeVeque: Numerical Methods for Conservation Laws, Birkhauser-Verlag, Basel, 1990, ISBN 3-7643-2464-3
  • Griebel, Dornseifer, Neunhoeffer: Numerical simulation in fluid dynamics: a practical introduction, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1998, ISBN 0-89871-398-6
• Notes and papers on specific topics:
  • Level Set Method (materials by Per Olof Persson):
    • notes on level sets (pdf)
    • presentation on level sets (pdf)
    • lsdemo (m-files)
  • Saddle point problems: M. Benzi, G. H. Golub and J. Liesen, Numerical solution of saddle point problems, Acta Numerica, 14 (2005), pp. 1-137

Homework Exercises

• Exercise Sheet 1 (due 02/21/07)
  Remarks:
  • Part 3.&4.: The given times were thought for a sine wave with periodic b.c. If you implement other b.c. or use more oscillatory i.c., there might not be much information visible after larger times. Feel free to plot the solution at two other times.
  • Part 4.: If you stabilize the central difference approximation by cu_xx, you can submit your code for this method, if you are happy with the results. In my tests, this approach turned out to be too diffusive, and -cu_xxxx worked much better. But maybe you come up with more clever approximations.
  • Part 3.&4.: You are not required to provide strict stability estimates in the sense: "What is the minimum amount of super-diffusion necessary to stabilize the method?" You are allowed to provide plots of the growth factor as arguments. Good formal estimates are of course better.
• Exercise Sheet 2 (due 03/09/07)
• Exercise Sheet 3 (due 03/23/07)
• Exercise Sheet 4 (due 04/18/07)
  Remarks:
  • Multigrid has to be done only for the 2d case.
• Exercise Sheet 5 (due 05/04/07)

• Theoretical parts: On paper. Submit in the lecture or in office hours.
• Programming parts: Matlab m-files. Submit by email, in the following way:
  • Name your matlab file: ex{#}_part{#}_{yourname}[_{more}].m.
    Examples: My program, solving u_t=-u_xxxx would be named ex1_part2_seibold.m. Hila's program, solving u_t=u_xxx with a superdiffusion-Lax-Friedrichs method could be named ex1_part4_hashemi_uxxxx.m.
  • Email your files as attachments to both the lecturer (seibold) and the grader (hhashemi). Use subject: 18.086 homework {#}
  • Write clean code. Comment your programs appropriately. Programs which do not run on our matlab are not graded.

Matlab Programs

• Finite differences for the heat equation: mit18086_fd_heateqn.m
  Example uses homogeneous Dirichlet b.c. on the left, and homogeneous Neumann b.c. on the right, and explicit Euler in time, which can easily be changed to implicit Euler.
• Four linear PDE solved by Fourier series: mit18086_linpde_fourier.m
  Shows the solution to the IVPs u_t=u_x, u_t=u_xx, u_t=u_xxx, and u_t=u_xxxx, with periodic b.c., computed using Fourier series. The initial condition is given by its Fourier coefficients. In the example a box function is approximated.
• Finite differences for the one-way wave equation, additionally plots von Neumann growth factor: mit18086_fd_transport_growth.m
  Approximates solution to u_t=u_x, which is a pulse travelling to the left. The methods of choice are upwind, downwind, centered, Lax-Friedrichs, Lax-Wendroff, and Crank-Nicolson. For each method, the corresponding growth factor for von Neumann stability analysis is shown.
• Compute stencil approximating a derivative given a set of points and plot von Neumann growth factor: mit18086_stencil_stability.m
  Computes the stencil weights which approximate the n-th derivative for a given set of points. Also plots the von Neumann growth factor of an explicit time step method (with Courant number r), solving the initial value problem u_t = u_nx.
  Example for third derivative of four points to the left:
  >> mit18086_stencil_stability(-3:0,3,.1)
• Numerical error analysis for upwind, Lax-Friedrichs, and Lax-Wendroff for transport equation: mit18086_error_analysis.m
  Applies the upwind, Lax-Friedrichs, and Lax-Wendroff method to the transport equation u_t=u_x for a sequence of step sizes for final time and Courant number fixed. The norm of the errors is plotted and compared to the theoretical expected results.
• Finite differences for the wave equation: mit18086_fd_waveeqn.m
  Solves the wave equation u_tt=u_xx by the Leapfrog method. The example has a fixed end on the left, and a loose end on the right.
• Traffic flow solved by a characteristic particle method: mit18086_traffic.m
  Shows the approximate weak entropyy solution plus a set of cars moving on the road. Observe that the velocity of the cars differs from the velocity of information. Note that the computation is done by a particle method, which is a different approach as a fixed grid finite difference method.
• Nonlinear finite differences for the one-way wave equation with discontinuous initial conditions: mit18086_fd_transport_limiter.m
  Solves u_t+cu_x=0 by finite difference methods. Of interest are discontinuous initial conditions. The methods of choice are upwind, Lax-Friedrichs and Lax-Wendroff as linear methods, and as a nonlinear method Lax-Wendroff-upwind with van Leer and Superbee flux limiter.
• Shallow water equations solved by a particle method: mit18086_shallowwater.m
  Shows the solution of the nonlinear shallow water equations with particles moving with the flow. As disturbances get small, the solution behaves like the linear wave equation with a base flow velocity.
• Level set method for front propagation under a given front velocity field: mit18086_levelsetmethod.m
  Uses the level set method with reinitialization to compute the movement of fronts under a given velocity field.
• Finite differences for the incompressible Navier-Stokes equations in a box: mit18086_navierstokes.m
  Solves the incompressible Navier-Stokes equations in a rectangular domain with prescribed velocities along the boundary. The standard setup solves a lid driven cavity problem.
  This Matlab code is compact and fast, and can be modified for more general fluid computations. You can download a Documentation for the program.
• Sets up and solves a sparse system for the 1d, 2d and 3d Poisson equation: mit18086_poisson.m
  Sets up a sparse system by finite differences for the 1d Poisson equation, and uses Kronecker products to set up 2d and 3d Poisson matrices from it. The systems are solved by the backslash operator, and the solutions plotted for 1d and 2d.
• Computes the LU decomposition of a 2d Poisson matrix with different node ordering: mit18086_fillin.m
  Sets up a 2d Poisson problem and computes the LU decomposition of the system matrix, firstly with lexicographic ordering, then with red-black ordering and then with symamd ordering.
• Demo for elimination with reordering: moe.m
  Visulizes elimination with various reordering methods for a 2d Poisson problem. Reordering methods are reverse Cuthill-McKee, minimum degree, symamd, and nested dissection.
• Computes the incomplete LU factorization of a 2d Poisson matrix for different tolerances: mit18086_ilu.m
  Sets up a 2d Poisson problem and computes the LU factorization and the incomplete LU factorization for different tolerances. Run times, condition numbers and nonzero pattern are plotted for comparison.
• Smoothing and convergence for Jacobi and Gauss-Seidel iteration: mit18086_smoothing.m
  Sets up a 1d Poisson problem with an oscillatory right hand side and applies Jacobi and Gauss-Seidel iteration to it. One can observe how the error gets smoothed very quickly, but the actual convergence to the correct solution is very slow.
• Multigrid solver for 1d Poisson problem: mit18086_multigrid.m
  Sets up a 1d Poisson test problem and solves it by multigrid. The method uses twogrid recursively using Gauss-Seidel for smoothing and elimination to solve at coarsest level. The number of pre- and postsmoothing and coarse grid iteration steps can be prescribed.
• Conjugate gradient method for 2d Poisson problem: mit18086_cg.m
  Sets up a 2d Poisson problem and solves the arising linear system by a conjugate gradient method. The error over iteration steps is plotted.

Course Projects

• Matt Abrahamson: Spacecraft thrust control optimization from surface to orbit
• Sherif Akl: Coupled numerical analysis of consolidation process in two-dimensional form for soils
• Marco Ayala: Understanding the boundary conditions in the diffusion equation that yield different results than those expected by simpler resistor model
• Sayed Bateni: Estimation of aquifer parameters by Ant-colony, genetic algorithm and nonlinear optimization techniques
• Duane Hudgins: Solving Navier-Stokes and the advection/diffusion equation for 2-D flow in a backwards facing step
• Matt Karmondy: Navier-Stokes solution to a two-dimensional body in hypersonic flow
• Raymond Lam: A computational model of oxygen transport in a multifluidic oxygenator for biological culture
• Sueann Lee: Numerical solution to Navier-Stokes equation for flow through and around a high drag region
• Masood Qazi: The impact of process fluctuations on the behavior of the six-transistor SRAM cell
• Fuxian Song: Analysis of different FD schemes in modeling elastic wave propagation in a fluid-filled borehole surrounded by an isotropic elastic formation
• Josh Taylor: The Fokker-Planck equation with many variables and the curse of dimensionality
• Michael Yeung: Full multigrid, W-cycle multigrid, and other iterative methods to solve the phase unwrapping problem in Interferometric Synthetic Aperture Radar (InSAR) systems

Video Lectures

There is information about the previous year's courses available on the MIT OpenCourseWare. In particular the video lectures by Gilbert Strang are strongly recommendable. 18.086 spring 2006    Course home    Video lectures
The course 18.085 is not a prerequisite for 18.086. Still, if you have not heard 18.085, you can watch some of the video lectures to get into the mood for numerical methods. 18.085 fall 2005    Course home    Video lectures

Documentations

• Matlab Documentation:
  
  • Matlab Documentation
  • Matlab Helpdesk

Copyright © 2007 Massachusetts Institute of Technology