Numerical Methods II (88-377)

• Integration of ordinary differential equations. Finite difference methods for initial value problems: basic methods (explicit and implicit, one step and multistep), order, stability, stiff systems, convergence, stepsize control, matlab functions. Boundary value and eigenvalue problems: shooting, finite difference, collocation and finite element (Galerkin) methods, singular problems.
• Optimization. Unconstrained minimization of functions in one dimension and in multiple dimensions: steepest descent, Newton's method, conjugate gradient method. Nonlinear least squares. Minimization of linear functions with linear constraints (simplex method).
• Discrete Spectral Methods. Discrete Fourier transform, inversion, convolution and Parseval theorems. Fast Fourier transform. Interpolation and decimation of data by spectral methods. Digital filtering: FIR and IIR approximations for low, high and band pass filters. Optimal (Wiener) filtering.
• Random numbers and simulation. Random number generators, generation of random numbers with given distributions, Monte Carlo method for computing integrals.

Students are expected to be familiar with Matlab

Course technicalities: lecture Thursday 5-6:30pm, targil Wednesday. The metargelet is Shira Zur. The exam (open book, 2.5 hours) will comprise 80% of the course grade, the other 20% will be based on exercises which must be submitted on time and done individually.

You may need a postscript viewer (gv or ghostview) to view many of the links below

Useful Stuff

• Here you can find some help building a matlab routine for integrating the autonomous system x'=f(x) using the (implicit, first order) backward Euler method. Here you can find the same thing for the (implicit, second order) trapezoid method.
• See this maple file if you want to be really sure that the classical Runge-Kutta method is 4th order.
• See this file to look at the stability region for the classical Runge-Kutta method.
• Matlab help for solving boundary value problems. See also this paper about the command bvp4c.
• Jonathan Shewchuk's paper on the conjugate gradient method
• For unconstrained minimization of functions of several variables, Matlab (the function "fminsearch") uses the simplex method of Nelder and Mead. The original article of Nelder and Mead appeared in volume 7 of The Computer Journal in 1965 you will only be able to access the article from computers on campus). The Matlab manual refers to this article of Lagarias, Reeds, Wright and Wright.
• Remarkably, volume 7 of The Computer Journal also contains 2 significant articles on the conjugate gradient method, by Fletcher and Reeves and Powell.
• Links to some other numerical methods courses (contributed by Eran Yavetz):
  • Waterloo (see especially the HOWTOs)
  • Cambridge (see here for pdf files)
• See Reuven Kashi's course page to see an example of FFT from the course Algorithms II in the CS department (thanks to Ilya Kotel for this link).
• FIR Digital Filter Design Applet
• IIR Digital Filter Design applet

Exercise Sets

• 1. ODE Methods: implementation of basic methods, order Submit before the targil Thursday Feb 27.
• 2. ODE Methods: stability, stepsize contol Submit first 3 questions before the targil Thursday March 13, last 3 questions before the targil Thursday March 20.
• 3. ODE Methods: boundary value and eigenvalue problems You must use all 4 boundary value problem methods (shooting, finite differences, collocation and Galerkin) on at least 1 problem, and at least 2 methods on at least 2.
• 4. Unconstrained Optimization
• 5. Spectral Methods
• 6. Random Numbers and Simulation

Exams

• Moed Aleph 2003
• Moed Bet 2003
• Moed Aleph 2004
• Moed Bet 2004

Back to my main teaching page
Back to my main page