CPSC 303, Term 2, Winter 2006-2007 Class Home Page

Numerical Approximation and Discretization

Contents of this page

• Late breaking news
• Things to print
  • Handouts
  • Homeworks
• Course Overview
• Course Details
  • Audience
  • Prerequisites
  • Instructor & TAs
  • Lecture Time and Location
  • Grades
  • Textbooks & References
• Tentative Schedule
• Related Links

Late Breaking News:

• 2007/05/02: Final grades have been submitted. If you would like to examine your final exam, you must make an appointment with me.
• 2007/05/01: Homework #6 has been graded, and may be retrieved from outside Ian's office (ICICS 217). Unclaimed homeworks will be discarded at the end of May.

Handouts

Course Notes:

A First Course on Numerical Methods by Uri M. Ascher and Chen Greif. These notes are provided for the private use of students enrolled in CPSC 303 at UBC in 2006-2007, and are not to be redistributed.

Additional Handouts:

Homeworks

Collaboration Policy:

You may collaborate with other students in the class on homework questions prior to writing up the version that you will submit. This collaboration may include pseudo-code solutions to programming components. Once you begin writing the version that you will submit, you may no longer collaborate on that question, either by discussing the solution with other students, showing your solution to other students, or looking at the solutions written by other students. Some additional prohibitions:

• You may never share executable code (including Matlab m-files) for homework questions.
• You may not re-submit an assignment solution from another course or a previous offering of this course without acknowledgement, regardless of authorship.
• You may not make your solution available as an aid to others.

You may seek help from the course instructor or TA at any time while preparing your homework solutions. You may not receive help from any other person.

If you feel that you have broken this collaboration policy, you may cite in your homework solution the name of the person from whom you received help, and your grade will be suitably adjusted to take this collaboration into account. If you break this collaboration policy and fail to cite your collaborator, you will be charged with plagarism as outlined in the university calendar. If you have any questions, please contact the instructor.

More information is available from (among other sources):

• Department of Computer Science Collaboration Policy
• UBC Academic Regulations on Student Discipline
• UBC Library's Plagarism Resource Center (not what it sounds like...)

Homework Submission Policy:

• Homeworks should be submitted in hardcopy form to handin box 3 in the basement of the (old) ICICS building by 11am on the due date. They may also be submitted at the beginning of class to the professor. There is no electronic submission.
• Each student gets four late days to use during the term. Late days run from 11am to 11am. A weekend counts for 1 late day.
• Apart from using late days, late assignments are not accepted for any reason.
• Once a solution set has been posted, no more late assignments are permitted. Consequently, you may not always be able to use your late days.
• Before submitting your homework, print the CPSC 303 cover sheet, fill it out and attach it to the front. Homeworks will not be accepted without a completed cover sheet attached.

Homeworks:

Course Overview

From the Calendar

Course Topics

• Numerical algorithms and error (briefly).
• Interpolating approximations.
• Best approximations.
• Numerical differentiation and integration.
• Numerical solution of initial value ordinary differential equations.

Course Details

Intended Audience: Undergraduates in

• Computer Science,
• Applied Mathematics,
• Quantitative Sciences,
• Engineering.

Prerequisites:

• All of MATH 200 (Calculus III) and MATH 221 (Matrix Algebra).
• One of CPSC 111 (Introduction to Computation), CPSC 260 (Object-Oriented Program Design) or the no longer offered CPSC 122, CPSC 126, CPSC 152.
• The assignments will require some programming, and Matlab is the language for the course; however, basic experience in Java, C, C++ or Fortran should be sufficient. See the Links section for more discussion of Matlab, or Ian Mitchell's Matlab Resources web page for tutorials and demos.
• CPSC 302 (Numerical Computation for Algebraic Problems) is not a prerequisite.

Course Communication:

• Most information will be disseminated through this web site or in class.
• A newsgroup (ubc.courses.cpsc.303) is available for questions and discussion about course material, homeworks and exams. Students are expected to read the newsgroup or check the web site regularly for updates.
• Questions regarding homework should be directed to the newsgroup or to the TAs at their email addresses above.
• Questions of a confidential nature can be directed to the instructor at the email address above. General questions regarding homework directed to the instructor will be ignored.

Lectures: 11:00 - 12:00, Monday / Wednesday / Friday, Dempster 110

• Dempster Pavilion is the shorter of the two new buildings between CICSR/CS and the Pulp & Paper center, facing the Forestry building. It can be accessed from Agronomy Road (which runs between CICSR/CS and Forestry) or from Engineering Road (which runs between the two new buildings).
• Location is subject to change; check here or the UBC Course Web Site for updates.
• There are no lectures Monday February 19 to Friday February 23 (Midterm break).
• There are no lectures Friday April 6 (Good Friday) or Monday April 9 (Easter Monday).
• There are no scheduled labs or tutorials for this course.

Grades: After the adjustment to take account of the lack of pop quizzes, your final grade will be based on a combination of:

• 5-6 homework assignments (including bonus points for the quizzes) (22%)
• 2 midterms (22%)
• 1 final (44%)
• Best total score for all homeworks, both midterms, or final (12%)

Textbooks:

• Scientific Computing: An Introductory Survey (second edition) by Michael T. Heath. Hardcover, strongly recommended, available at the bookstore.
• A First Course on Numerical Methods by Uri M. Ascher and Chen Greif. Available online to students enrolled in the course.

Other References:

• Numerical Analysis (seventh edition) by Burden and Faires (the textbook for previous versions of this course).
• Numerical Analysis by Kincaid and Cheney.
• Single Variable Calculus and Calculus of Several Variables by Adams (or any other undergraduate multivariable calculus text).
• Elementary Differential Equations and Boundary Value Problems by Boyce and DiPrima.

The Schedule:

• Topics of future lectures are subject to change.
• Readings are from Heath second edition (H), the Ascher & Greif course notes (AG), or Burden & Faires seventh edition (BF).
• The reading assigned for a lecture should be done before the lecture.
• Links for future material may not yet be live.

Links:

• CPSC 303 Term 2 Winter 2006-2007 Course Web Page (this page): http://www.ugrad.cs.ubc.ca/~cs303/2006W2/index.html
• CPSC 303 is offered by:
• Ian Mitchell
• Department Computer Science
• University of British Columbia
• We will use Mathworks' Matlab package for the programming components of this course.
  • It includes powerful visualization, a standard imperative programming language, a full featured debugger, and many standard numerical algorithms for linear algebra and the approximation and discretization tasks we will encounter in this course.
  • If you are unfamiliar with Matlab, take a look at Ian Mitchell's Matlab Resources web page or Mathworks' Introduction to Matlab.
  • There are also many other tutorials available on the web, although many are quite old. The current version is 7.2 and should be available on the undergraduate machines.
  • If you prefer to work from home, a student version of Matlab should be available for purchase from the UBC Bookstore. While the student version does not include all the toolboxes available on the undergraduate machines, it should be sufficient for the homework in this course.
• Other links related to numerical computing. Contact the instructor if you find more suitable links.
  • Michael Heath's Interactive Educational Modules in Scientific Computing which supplement the textbook with a collection of Java based interactive demos.
  • Some open source alternatives to Matlab: GNU Octave or Scilab. I have not used them myself, but would definitely be interested if it is possible to do the homeworks on either or both systems (or what components of the homework could not be done).
  • Netlib, a repository of freely available software, documents and databases related to numerical and scientific computing.
  • The Guide to Available Mathematical Software (GAMS), another repository of numerical software with a search engine.
  • Numerical Recipes (in C, Fortran, C++), a well known but not always perfect collection of numerical routines.
  • Mathworld and the Wikipedia are two places to look for definitions of mathematical concepts and terminology, although like anything on the web they should only be trusted so far.
  • TOP500 Supercomputer Sites, which twice a year updates the list of the fastest publically known supercomputers in the world. Beyond the publicity, this site demonstrates interesting trends in computer architecture and world-wide government funding initiatives.
  • Thomas Huckle has a large collection of software bugs, many related to errors in numerical algorithms or floating point arithmetic.
  • Nick Trefethen has a number of interesting essays at his home page, including a discussion of the definition of numerical analysis.
  • William Kahan has written many papers relating to floating point computation, including an interview reminiscences about the IEEE standard as well as some lecture notes on the IEEE 754 standard (.ps file).
  • John Polking's dfield and pplane software for phase plane plots of two dimensional ODEs in Matlab.
  • SUNDIALS (SUite of Nonlinear and DIfferential/ALgebraic equation Solvers), a collection of C code (with Fortran interfaces) for solving ODE IVPs and DAEs.
• Relating to ODEs, here are some examples of how standard methods, such as Matlab's ode45 and ode23, can perform poorly even though they have excellent control over their truncation error.
  • stiff.m shows a system with an equilibrium solution at y(t) = 1. If y(t) is not at the equilibrium, it will quickly go towards the equilibrium. Even though the explicit ode45 can approximate this solution well, it takes a very long time (lots of small timesteps) because this system has a common property called stiffness. For stiff systems, it is better to use implicit methods, such as ode15s. We will look at stiff systems briefly in 303.
  • circle.m shows an ODE whose solution should form a circle when plotted in phase space (y1 vs y2). Points on a circle have an invariant (distance from the origin) which is not maintained by ode23. Schemes which would work well on this system (would maintain the invariant) are called "symplectic", although we will not discuss them further in 303.
  • matlabFailure.m shows an ODE describing a coupled oscillator system. The true solution quickly achieves a constant phase offset, and then stays coupled for all time. If ode45 is used, the numerical solution incorrectly decouples at about t = 100 but otherwise looks fine (it does not blow up). The system is not stiff, as evidenced by the reasonable step-size that ode45 chooses throughout the integration. In fact, the failure has to do with how ode45 estimates truncation error; for more details, see Joseph D. Skufca, "Analysis Still Matters...", SIAM Review, v.46, n.4, pp.729-737 (2004). It turns out that ode15s happens to provide a good approximation, although it must be emphasized again that the system is not stiff, so the success is for reasons other than those typically used to justify choosing ode15s.
• This course provides basic background material in the field of scientific computing and numerical analysis.
  • How will this material help you get a job? The Society for Industrial and Applied Mathematics (SIAM) has a web site and brochure about careers in applied mathematics, of which scientific computing is a huge component.
  • There are a wide variety of groups doing scientific computing, numerical analysis and applied mathematics research at UBC. Those connected most closely with the Department of Computer Science are the Scientific Computing Laboratory (SCL), the Scientific Computing, Applied and Industrial Mathematics (SCAIM) group, and the Institute for Applied Mathmatics (IAM). If you are thinking about graduate school in computational science, you can find further links and people to talk with about your options.
  • If you are interested in broader thoughts about scientific computing and numerical analysis, Nick Trefethen at Oxford has written a number of more philosophical essays on the subject, in addition to his outstanding technical contributions to the field. For example, consider "The definition of Numerical Analysis" (also pdf format), "Maxims about Numerical Analysis, Computers, Science and Life," "Predictions for Scientific Computing 50 Years from Now" (also pdf format), and a recent short survey "Numerical Analysis."
• Additional resources for students:
  • UBC's LEAP (Learning Enhancement Academic Partnership) web site for all sorts of tips and hints on how to cope with the demands of university study.
  • If you already spend too much time in front of the computer, try the Study and Research Skills Workshops, free workshops offered during the term and covering topics such as exam prep, group projects, stress management and presentation skills.
  • If you are feeling stressed out or overwhelmed by courses, committments or university life, consider visiting one of the free counselling services available at UBC: UBC Student Counselling, AMS Speakeasy or Student Health Services.