Fall 2012:
Numerical Methods for Differential Equations
Class Information:
Office Hour: 2-4pm, Thursday, INS 624
email: lzhang2012 AT sjtu
TA Office Hour: 2-4pm, Friday
TA Office Location: NO.16 in Ph.D students' office of Department of Mathematics (Computation Centre 325 close to INS)
email: shs3701001 AT sjtu
Homework out: Wednesday
Homework due: Tuesday in class
Homework 20%
Projects 20%
Midterm 20%
Final 40%
Homework:
Homework 1, Homework 2, Homework 3, Homework 4, Homework 5, Homework 6, Homework 7, Homework 8
Homework 9, Homework 10, Homework 11, Homework 12, Homework 13, Homework 14
Exams:
Midterm
Example Code:
Forward Euler: euler_forward.m.
Backward Euler: euler_backward.m, newton4euler.m.
Stability Region: stabilityregion.m
Syllabus:
Week 1:
Euler method, convergence proof of Euler method, truncation error,
trapezoidal rule, order of the numerical method, convergence proof,
\theta-method, truncation error
Readings: Iserles 3-10, 13-15, Süli 4-6, 7-9.
Week 2:
Multistep method: Construction of multistep method by Lagrange polynomial, Adams-Bashforth method, order condition for general multistep method, characteristic polynomial, zero-stability, convergence.
Readings: Iserles 19-23, Süli 21-22, 24-29.
Week 3:
Runge-Kutta Method: General one-step method, consistency, convergence, Taylor expansion method, Runge-Kutta method - idea from numerical quadrature, general formulation of Runge-Kutta method, parameters (R-K matrix, R-K nodes, R-K weights), constraints on the parameters, order condition, absolute stability, region of absolute stability, absolute stability for multistep method.
Readings: Iserles 33-34, 38-41, Süli 9-20, 43.
Week 4:
Symplectic Method: Geometric integration, Hamiltonian system, symplecity, Poincare theorem, symplectic Euler method, implicit midpoint method, conservation of energy, conservation of quadratic invariants.
Readings: Iserles 73-77, 87-95.
Hairer's lectures on geometric integration: http://www.unige.ch/~hairer/poly_geoint/week1.pdf, http://www.unige.ch/~hairer/poly_geoint/week2.pdf
Vilmart's animation: http://w3.bretagne.ens-cachan.fr/math/people/gilles.vilmart/java.html
Week 5:
Finite Difference Method for Poisson Equation: Formulation of 5-point method, linear system, existence and uniqueness of the solution, error estimate of the solution, higher order method, treatment of curved boundary.
Readings: Iserles 147-155.
Week 6:
Finite Element Method for Poisson Equation: derivation of Poisson equation, solution as an energy minimizer, weak formulation, finite element discretization (mesh, approximation space and basis), Ritz formulation of FEM (energy minimization), Galerkin formulation of FEM (virtual work), weighted residual, discrete equations (stiffness matrix A_h, load vector F, and mass matrix M), error estimate in energy norm and H^1 norm.
Readings: Notes from MIT Opencourse website, Finite Element Methods for Elliptic Problems; Variational Formulation: The Poisson Problem (PDF), Discretization of the Poisson Problem in IR1: Formulation (PDF), and Discretization of the Poisson Problem in IR1: Theory and Implementation (PDF).
Week 7:
Poincare-Fredrichs inequality, equivalence of energy norm and H^1 norm for functions in H^0_1, finite element error can be controled by interpolation error.
Solve Ax = b: LU factorization for sparse banded matrix, operation count, order rearrangement, graph of sparse matrix.
Iterative method: linear one-step stationary scheme, necessary and sufficient condition for convergence.
Readings: Iserles 233-243, 251-254.
Week 8
Iterative method: Convergence of iterative method, incomplete LU factorization, Jacobi iteration, Gauss-Seidel iteration, SOR, eigensystem for TST matrix, convergence
rate of Jacobi, G-S and SOR methods for TST matrix.
Steepest descent, conjugate gradient, preconditioner
Readings: Iserles 252-260, 264-267, 309-317.
A more 'transparent' illustration of conjugate gradient can be found at http://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf (An Introduction to
the Conjugate Gradient Method Without the Agonizing Pain Edition 1.25, by Jonathan Richard Shewchuk).
Week 9
Discrete Fourier Transform: Fourier transform, Fourier series expansion, Nyquist Sampling theorem, aliasing, Fast Fourier transform, bit-reversal, Fast Poisson solver,
Fast Sine transform.
Readings: for FFT, Numerical Recipe in C 496-507, 514-515 http://apps.nrbook.com/c/index.html.
for fast Poisson solver, http://ocw.mit.edu/courses/mathematics/18-086-mathematical-methods-for-engineers-ii-spring-2006/readings/am35.pdf
Week 10
Solving hyperbolic equations: advection equaitons, boundary conditions (inflow, outflow), initital condition, characteristics,
General defintions: convergence, local truncation error, consistency, stability (Lax-Richtmyer), Lax equivalence theorem,
Method of lines discretization: semi-discretization analysis, forward Euler, Leap Frog, Lax-Fredrichs.
Readings: LeVeque 201-205, the definition of local truncation error 183-184, the definition of convergence and stability, Lax equivalence theorem 189-190.
Week 11
Solving hyperbolic equations:
Stability of Forward Euler method, Lax-Richtmyer stable but not absolute stable. Stability of Leap-Frog method, non-dissipative,
Lax-Wendroff method, upwind method, Beam-Warming method.
Readings: LeVeque 206-212.
Week 12
Solving hyperbolic equations:
von Neumann analysis, characteristic tracing, interpolation construction of numerical methods, Courant-Friedrichs-Lewy condition,
Fourier analysis of linear PDEs (advection equation, heat equation, backward heat equation), dispersive waves, dispersive relation,
Modified equation.
Readings: LeVeque 212-223, Fourier analysis of linear PDEs LeVeque 317-327.
A good exposition of von Neumann analysis can be found in http://people.maths.ox.ac.uk/trefethen/4all.pdf P20-24.
Week 13
Solving hyperbolic equations:
Modified equation for Leap-Frog method, negative group velocity, hyperpolic system and its numerical methods, initial boundary value problem (IBVP), analysis of
upwind method on IBVP, outflow condition,
Solving parabolic equations:
Crank-Nicolson method, method of lines discretization, stability, convergence.
Readings: LeVeque 181-195, 222-229.
Week 14
Various topics: Fast Fourier transform, Fast Sine transform, butterfly algorithm, Fast Poisson solver, Fourier (pseudo)spectral method, Monte-Carlo
Readings: see the readings of week9 for fast Fourier transform fast Sine transform, and fast Poisson solver; see http://www.cmlab.csie.ntu.edu.tw/cml/dsp/training/coding/transform/fft.html for
butterfly algorithm; see http://people.maths.ox.ac.uk/trefethen/7all.pdf for Fourier (pseudo)spectral method;
References:
Ordinary Differential Equations
The first two are our main references. The third one together with its volume II on stiff problems is the most comprehensive text on numerical integration of ODEs.
A First Course in the Numerical Analysis of Differential Equations
by Arieh Iserles
Endre Süli's notes
by Endre Süli
Solving Ordinary Differential Equations I: Nonstiff Problems
by Ernst Hairer, Syvert P. Nřrsett, Gerhard Wanner
Partial Differential Equations
A First Course in the Numerical Analysis of Differential Equations
by Arieh Iserles
Finite Difference Methods for Ordinary and Partial Differential Equations
by Randy LeVeque
Class Information:
Office Hour: 2-4pm, Thursday, INS 624
email: lzhang2012 AT sjtu
TA Office Hour: 2-4pm, Friday
TA Office Location: NO.16 in Ph.D students' office of Department of Mathematics (Computation Centre 325 close to INS)
email: shs3701001 AT sjtu
Homework out: Wednesday
Homework due: Tuesday in class
Homework 20%
Projects 20%
Midterm 20%
Final 40%
Homework:
Homework 1, Homework 2, Homework 3, Homework 4, Homework 5, Homework 6, Homework 7, Homework 8
Homework 9, Homework 10, Homework 11, Homework 12, Homework 13, Homework 14
Exams:
Midterm
Example Code:
Forward Euler: euler_forward.m.
Backward Euler: euler_backward.m, newton4euler.m.
Stability Region: stabilityregion.m
Syllabus:
Week 1:
Euler method, convergence proof of Euler method, truncation error,
trapezoidal rule, order of the numerical method, convergence proof,
\theta-method, truncation error
Readings: Iserles 3-10, 13-15, Süli 4-6, 7-9.
Week 2:
Multistep method: Construction of multistep method by Lagrange polynomial, Adams-Bashforth method, order condition for general multistep method, characteristic polynomial, zero-stability, convergence.
Readings: Iserles 19-23, Süli 21-22, 24-29.
Week 3:
Runge-Kutta Method: General one-step method, consistency, convergence, Taylor expansion method, Runge-Kutta method - idea from numerical quadrature, general formulation of Runge-Kutta method, parameters (R-K matrix, R-K nodes, R-K weights), constraints on the parameters, order condition, absolute stability, region of absolute stability, absolute stability for multistep method.
Readings: Iserles 33-34, 38-41, Süli 9-20, 43.
Week 4:
Symplectic Method: Geometric integration, Hamiltonian system, symplecity, Poincare theorem, symplectic Euler method, implicit midpoint method, conservation of energy, conservation of quadratic invariants.
Readings: Iserles 73-77, 87-95.
Hairer's lectures on geometric integration: http://www.unige.ch/~hairer/poly_geoint/week1.pdf, http://www.unige.ch/~hairer/poly_geoint/week2.pdf
Vilmart's animation: http://w3.bretagne.ens-cachan.fr/math/people/gilles.vilmart/java.html
Week 5:
Finite Difference Method for Poisson Equation: Formulation of 5-point method, linear system, existence and uniqueness of the solution, error estimate of the solution, higher order method, treatment of curved boundary.
Readings: Iserles 147-155.
Week 6:
Finite Element Method for Poisson Equation: derivation of Poisson equation, solution as an energy minimizer, weak formulation, finite element discretization (mesh, approximation space and basis), Ritz formulation of FEM (energy minimization), Galerkin formulation of FEM (virtual work), weighted residual, discrete equations (stiffness matrix A_h, load vector F, and mass matrix M), error estimate in energy norm and H^1 norm.
Readings: Notes from MIT Opencourse website, Finite Element Methods for Elliptic Problems; Variational Formulation: The Poisson Problem (PDF), Discretization of the Poisson Problem in IR1: Formulation (PDF), and Discretization of the Poisson Problem in IR1: Theory and Implementation (PDF).
Week 7:
Poincare-Fredrichs inequality, equivalence of energy norm and H^1 norm for functions in H^0_1, finite element error can be controled by interpolation error.
Solve Ax = b: LU factorization for sparse banded matrix, operation count, order rearrangement, graph of sparse matrix.
Iterative method: linear one-step stationary scheme, necessary and sufficient condition for convergence.
Readings: Iserles 233-243, 251-254.
Week 8
Iterative method: Convergence of iterative method, incomplete LU factorization, Jacobi iteration, Gauss-Seidel iteration, SOR, eigensystem for TST matrix, convergence
rate of Jacobi, G-S and SOR methods for TST matrix.
Steepest descent, conjugate gradient, preconditioner
Readings: Iserles 252-260, 264-267, 309-317.
A more 'transparent' illustration of conjugate gradient can be found at http://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf (An Introduction to
the Conjugate Gradient Method Without the Agonizing Pain Edition 1.25, by Jonathan Richard Shewchuk).
Week 9
Discrete Fourier Transform: Fourier transform, Fourier series expansion, Nyquist Sampling theorem, aliasing, Fast Fourier transform, bit-reversal, Fast Poisson solver,
Fast Sine transform.
Readings: for FFT, Numerical Recipe in C 496-507, 514-515 http://apps.nrbook.com/c/index.html.
for fast Poisson solver, http://ocw.mit.edu/courses/mathematics/18-086-mathematical-methods-for-engineers-ii-spring-2006/readings/am35.pdf
Week 10
Solving hyperbolic equations: advection equaitons, boundary conditions (inflow, outflow), initital condition, characteristics,
General defintions: convergence, local truncation error, consistency, stability (Lax-Richtmyer), Lax equivalence theorem,
Method of lines discretization: semi-discretization analysis, forward Euler, Leap Frog, Lax-Fredrichs.
Readings: LeVeque 201-205, the definition of local truncation error 183-184, the definition of convergence and stability, Lax equivalence theorem 189-190.
Week 11
Solving hyperbolic equations:
Stability of Forward Euler method, Lax-Richtmyer stable but not absolute stable. Stability of Leap-Frog method, non-dissipative,
Lax-Wendroff method, upwind method, Beam-Warming method.
Readings: LeVeque 206-212.
Week 12
Solving hyperbolic equations:
von Neumann analysis, characteristic tracing, interpolation construction of numerical methods, Courant-Friedrichs-Lewy condition,
Fourier analysis of linear PDEs (advection equation, heat equation, backward heat equation), dispersive waves, dispersive relation,
Modified equation.
Readings: LeVeque 212-223, Fourier analysis of linear PDEs LeVeque 317-327.
A good exposition of von Neumann analysis can be found in http://people.maths.ox.ac.uk/trefethen/4all.pdf P20-24.
Week 13
Solving hyperbolic equations:
Modified equation for Leap-Frog method, negative group velocity, hyperpolic system and its numerical methods, initial boundary value problem (IBVP), analysis of
upwind method on IBVP, outflow condition,
Solving parabolic equations:
Crank-Nicolson method, method of lines discretization, stability, convergence.
Readings: LeVeque 181-195, 222-229.
Week 14
Various topics: Fast Fourier transform, Fast Sine transform, butterfly algorithm, Fast Poisson solver, Fourier (pseudo)spectral method, Monte-Carlo
Readings: see the readings of week9 for fast Fourier transform fast Sine transform, and fast Poisson solver; see http://www.cmlab.csie.ntu.edu.tw/cml/dsp/training/coding/transform/fft.html for
butterfly algorithm; see http://people.maths.ox.ac.uk/trefethen/7all.pdf for Fourier (pseudo)spectral method;
References:
Ordinary Differential Equations
The first two are our main references. The third one together with its volume II on stiff problems is the most comprehensive text on numerical integration of ODEs.
A First Course in the Numerical Analysis of Differential Equations
by Arieh Iserles
Endre Süli's notes
by Endre Süli
Solving Ordinary Differential Equations I: Nonstiff Problems
by Ernst Hairer, Syvert P. Nřrsett, Gerhard Wanner
Partial Differential Equations
A First Course in the Numerical Analysis of Differential Equations
by Arieh Iserles
Finite Difference Methods for Ordinary and Partial Differential Equations
by Randy LeVeque