Numerical Computing, V22.0421

Instructor: Denis Zorin,
Spring 2008
Tue, Thu 2:00 - 3:15 a.m., 719 Broadway, rm. 1221
Teaching Assistant: Yotam Gingold,
Mailing list:
Final: May 13, Tuesday, 2pm, 719 Broadway, rm. 1221. list of topics.


Course Description

This class covers basic topics in numerical computation: floating-point arithmetics, types of error, methods for solving linear and nonlinear systems, interpolation and basic discretizations of ordinary differential equations. Numerical algorithms will be presented in the context of a variety examples, primarily drawn from interactive physics and animation techniques used in games and computer graphics.


V22.0102 (intro to computer science II) and V63.0140 (linear algebra), or, in some cases, permission of instructor. Knowledge of Python in advance is not expected.


  1. Written and programming homeworks;
  2. written midterm exam;
  3. final exam.



We will use a Python-based numerical computing environment SciPy, which provides most of the functionality found in Matlab, in particular efficient vector and matrix manipulation through NumPy, but based on a general-purpose high-level language, and seamlessly integrated with a large number of libraries provided by Python.

Installation. First you will need to install Python 2.5 or later, if it is not available on your system. For Windows, binary installers for SciPy and NumPy are available at the SciPy download page. On a Mac, the recommended way to install SciPy is using fink. In addtion to SciPy, please install matplotlib.

More detailed installation instructions. If you have any trouble with installation, please contact the teaching assistant immediately!


Assignment 0, due Wednesday, January 30. Install Python, SciPy and matplotlib (please see the instructions below). Change student to your last name in and run this program. It should create a png file yourname_version_info.png; please send it to

Assignment 1, due Thursday, February 7. PDF If you typeset your assignment, you can send it to the instructor by e-mail. If parts of it are hand-written, please submit the whole assignment on paper.

Assignment 2, due Thursday, February 28. PDF

Assignment 3, due Thursday, April 3. PDF

Assignment 4, due Thursday, May 1. PDF


January 22Overview
January 24Introduction to Python.
I recommend reading sections 3-5 and 9 of Python Tutorial by Guido van Rossum. A somewhat more concise introduction covering most of what we need is Steven Thurlow's "A Beginner's Python Tutorial" You can find links to a large number of tutorials and resources at
January 29IEEE 754 floating point arithmetics.
A brief overview of the standard by Steve Hollasch.
Minifloats are useful for understanding the details of f.p. operations.
Lecture notes
by. W. Kahan, the architect of IEEE 754.
Python code for conversion of floats to binary strings.
January 31 Types of errors: modeling, discretization, roundoff, convergence. Absolute and relative error.
Textbook, Chapter 1 and (optionally) Chapter 2. example 1.1 from Ch. 1 in Python.
February 5 Linear equations and matrices, review.
Textbook, chapter 4.
February 7 Example: optimal curves. Optimization problem, differential equation, discretization.
February 12 Example: optimal curves, implementation using scipy and matplotlib.
Source files: (matrix construction and solve), (GUI), (array helper functions).
February 14 Gaussian elimination, LU factorization, pivoting.
Source file: (LU factorization with partial pivoting, back and forward substitution.
February 19 LU factorization continued, conditioning, condition number, solution errors.
February 21 (Yotam Gingold) Surface editing example, matrix conditioning in one and two dimensional case, bandedness. Code:;
Surface optimization:,
February 26 Least squares, normal equations. Code: Textbook, Section 7.4.
February 28 Least squares continued, implict curve fitting. QR factorization.
Textbook, Section 7.4. Additional reading (password required) Code:
March 4 QR factorization continued. Polynomial and piecewise polynomial interpolation, introduction. Code:,,,
March 6 Polynomial and piecewise polynomial interpolation: Lagrange polynomials, Bezier curves, B-splines. Textbook: Sections 10.1 and 10.2, 11.1-11.4 Notes: Bezier curves and B-splines (you do no have to read the part about blossoming)
March 11 Review.
March 13 Midterm
March 18 Spring break.
March 20 Spring break.
March 25 Solving nonlinear equations: bisection, one-dimensional Newton's method (Chapter 3).
March 27 Mass-spring system in equilibrium: formulation. derivation notes.
April 1 High-dimensional Newton method. Spring system in equilibrium: energy point of view.
Chapter 9 (not on the web page above, new revision of text!), linked here.
April 3 Ordinary differential equations: review of linear equations and systems of linear equations: reduction of high-order to first order, reduction of a system to the diagonal form.
April 8 Euler's method for integration of ODEs, forward and backward Euler, stability. Chapter 17, sections 17.1 and 17.5, (not on the web page above, new revision of text!), linked here.
April 10 Forward and backward Euler's method for a spring, osciallations. Increasing the order of accuracy; midpoint method. Chapter 17, sections 17.2, (not on the web page above, new revision of text!), linked here.
April 15 Dynamic mass-spring system: forward and backward Euler.,
April 18 Leapfrog(Verlet) integration. Review of integration techniques for ODEs. a brief explanation of the leapfrog method.
April 22 Computing eigenvalues and eigenvectors. Power method. Inverse power method.
Sections 7.1-7.2.
April 24 Iterative methods for linear systems. Stationary iteration: Jacobi and Gauss-Seidel. The idea of Krylov subspace methods.
Chapter 7 from new version of the book, linked here
April 28 Fourier series. Discerete Fourier Series, Fast Fourier transform. Application to sound analysis. Chapter 14, linked here
April 30 Review.