Continuous Mathematics: 2019-2020
Computer science applications increasingly rely on calculus, particularly differentiation of multivariate functions. This course introduces the concept with a view to later applications in Machine Learning, some aspects of Security using information theory, and with relevance to Computer Graphics. It does so by presenting first the mathematical basis and then introductory algorithms for numerical computing. The common point of the course is Taylor’s theorem; we see how some algorithms arise from it, and some others can be analysed using it.
The lectures for this course are not going to be recorded in Hilary Term 2019.
Learning outcomesLearning how to differentiate multivariate functions. Understanding Taylor’s theorem and its application in approximation of functions. Finding and classifying stationary points of functions. Understanding the concept and relevance of convexity. Understanding what iterative numerical algorithms are, and how their convergence is measured. Deriving algorithms for numerical integration, root finding, and optimization, in 1- and n-dimensions, and learning how to analyse their accuracy. Seeing some real applications of these methods in Computer Science research.
[3 lectures] Derivatives, partial derivatives, differentiation with respect to a vector, gradient, Hessian and Jacobian. Taylor's theorem in 1 dimension (Lagrange remainder), Taylor's theorem in n dimensions (remainder only briefly). Examples.
[3 lectures] Optimization in 1 and n dimensions. Classification of turning points via Taylor's theorem. Convexity. Constrained optimization: Lagrange multipliers. Examples.
[2-3 lectures] Numerical integration in 1 dimension: trapezium, midpoint, and Simpson’s rules, complexity and error analysis. Briefly, integration in n dimensions and Monte Carlo methods. Examples.
[1 lecture] Floating-point numbers and rules of thumb for accuracy in practice. Convergence rates of iterative methods.
[2-3 lectures] Numerical root finding in 1 dimension by bisection, Newton's method, secant method. Root finding in n dimensions by Newton's method, and briefly quasi-Newton methods. Complexity and error analysis. Examples.
[2-3 lectures] Numerical optimization in 1 and n dimensions: root finding for gradient and gradient descent methods. Complexity and error analysis. Examples.
[1-2 lectures] Applications.
Derivatives, partial derivatives, differentiation with respect to a vector; gradient, Hessian, Jacobian. Taylor's theorem in 1- and n-dimensions, with Lagrange remainder. Optimization in 1- and n-dimensions, classification of stationary points. Constrained optimization and the method of Lagrange multipliers. Methods for numerical integration in 1- and n-dimensions, complexity and error analysis. Iterative numerical methods and rates of convergence. Methods for numerical root finding and numerical optimization in 1- and n-dimensions, complexity and (simple cases of) error analysis. Applications.
A. D. Ker. Continuous Mathematics. Lecture notes, 2019.
Self-contained notes with the core material and practice exercises.
Sadly there seem to be few textbooks at the appropriate level: most either only cover 1-dimensional numerical methods, or are graduate texts, or contain advanced mathematical treatments.
H. Neill. Calculus: A Complete Introduction. Teach Yourself, 2013.
A very gentle introduction to calculus suitable for preparation before this course. Many, many, examples of simple differentiation. Does not cover our syllabus beyond the very first part.
U. M. Ascher and C. Greif. A First Course Numerical Methods. SIAM, 2011.
Nicely written, with good examples. Does not have much material on the chapter 2 material. A bit more advanced than in the lecture notes, and this course will only cover a fraction of what is in the book. Expensive.
E. W. Cheney and D. R. Kincaid. Numerical Mathematics and Computing (Seventh Edition). Wadsworth Publishing Co Inc, 2012.
Rarely goes beyond 1-dimensional methods, but what it covers is done at an appropriate level. A good counterpart to the above. Second-hand copies seem to be cheap.
R. Burden and J. Faires. Numerical Analysis (Ninth Edition). Brooks Cole, 2010.
Goes a bit further into n-dimesional methods, but also includes a lot of material that is not in this course. There is an international edition that is cheaply available.