Computer Laboratory

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.

Further Material

For the more adventurous: