Course pages 2013–14
Numerical Methods
This is a new course of 11 lectures where 6 lecture's worth of material is almost the same as last year's Floating Point course.
Primary Materials
- Slides (including minor corrections and code fragments) SLIDES PDF.
- Slides as printed (R1) SLIDES PDF.
- Exercise sheets: There will be three sheets: 1. 2. and 3.. There are some exercises mentioned in small font at the bottom of some slides: these also appear in the exercise sheets. Exercise SHEETS 1+2+3 PDF.
- Demonstration programs in C: CPrograms.
- Demonstration programs in Java: JPrograms.
- Demonstration programs in C#: CSPrograms.
- Demonstation programs in ML: MLPrograms.
- Demonstration programs in Matlab/Octave (this can also be done in gnuplot I expect): poly.m.
Learners' Guide: What Was Lectured
Part 10 was not lectured : Slides 165 (weber-Fechner) to 177 (Musical Instrument Physical Modelling). Slides from 186 (Moniac) onwards were not covered.
Two example Tripos question fragments for the new material beyond the older Floating Point course are HERE Q1. and will be HERE Q2.
Regarding the new algorithms lectured, detailed coding is unlikely to be asked about but candidates must have full knowledge of their purpose and general behaviour:
- Base Conversions: the general approach for each of the four and why they differ.
- Newton Raphson: it's formula, basis, convergence and be able to apply it.
- Cordic: how the algorithm works (a decomposition into angles with easy to multiply tangents) and answer a question about it given a reminder of the code.
- Chebyshev Basis: to know that a good choice of basis vectors or knot positions will give a better result than a simplistic truncation of Taylor or evenly-spaced (cardinal) interpolation. Anything else needed for examination questions related to this will be provided in the question.
- Gaussian Elimination: a matrix phrasing of the standard technique to solve simulataneous linear equations and the need for pivoting and forwards and backwards substitution (the minor difference between Doolitle and Crout was not lectured).
- Cholesky Decomposition: that it is a sort of square-root of a matrix and it saves effort in Gaussian elimination for multiple right-hand-sides by not having to generate and save separate L and U matrices. One matrix serves for both.
- FDTD Simulation: what a forward difference is, the sort of error they introduce and that better approaches exist but require more design effort.
- SPICE Nodal Analysis: to understand the three flow quantities (conductance, potential and flow rate) and how to phrase these in a matrix form GV=I suitable for solving.
- SPICE Non-linear and time-varying components: that these can be handled by introducing a conductance equal to dI/dV and a flow generator to offset the origin. And that the non-linear requires iteration within a time step whereas time-varying components themselves are handled with forward differences.
Secondary Materials
Numerical Analysis is the oldest discipline in Computer Science. You will find many dusty books in your College library covering the subject. These will contain relevant chapters. Also, Wikipedia explains all of the topics we shall cover.
The following web resources will be referred to in lectures.
- Disasters: Some disasters caused by numerical errors: Kees Vuik's page, Two disasters, The sinking of the Sleipner A offshore platform.
- Mike O'Donohoe's notes for a previous course with a different syllabus
- Notes for Numerical Analysis Math 4445 by S. Adjerid
- IEEE 754.
- Java Math Doc link broken.
- Hackers Delight .
- Sinclair Calculator .
- CORDIC.
- Chris Lomont's Inverse Square .
- The MONIAC water-based computer.
- A lecture note on L/U Decomposition (McMasters/Kirbua).
- The problem with percentiles - topic not covered this year.
- List of optimisation software - topic not covered this year..
- The Logistic Map.
- Kahan Summation algorithm.
- An interesting iteration to find Pi.
- Wolfram Blume, Byte Magazine 1986, SPICE: Computer Circuit Simulation.
Further Material
- Resources for Michael Overton's book "Numerical Computing with IEEE Floating Point Arithmetic"
- An easy magazine article by Cleve Moler (The Mathworks, creators of MATLAB) conveying the feel of various ideas from this course.
- Annotated subset of past exam questions for an older Numerical Analysis course.
- Nick Maclaren's course "How Computers Handle Numbers – a.k.a. Computer Arithmetic Uncovered" for the Computing Service.
- Some further books:
- Numerical analysis : mathematics of scientific computing / David Kincaid, Ward Cheney. 2009.
- Handbook of floating-point arithmetic / Jean-Michel Muller ... [et al.]. 2010.
- Numerical Recipes in Fortran/C/Java/Younameit, William H. Press: http://www.nr.com.
- Inside SPICE by Ron Kielkowski - McGraw Hill 1993.
For the more adventurous:
- David Goldberg's article "What Every Computer Scientist Should Know About Floating-Point Arithmetic"
- David Monniaux's article "The pitfalls of verifying floating-point computations"
- Batching for percentiles.