Continuous Mathematics: 2021-2022

Lecturer

Jonathan Whiteley

Degrees

Preliminary Examinations — Computer Science

Preliminary Examinations — Mathematics and Computer Science

Term

Hilary Term 2022 (16 lectures)

Overview

The Continuous Maths course this term will be taught using recorded lectures that are available on the course materials webpage. These lectures will be supplemented by live sessions on Wednesdays at 9am in Lecture Theatre A. Ideally these live sessions will be driven by questions from the students; iplease submit questions by 5pm on Tuesday so that the lecturer can identify common themes when answering these questions. He will also answer questions asked on the day. Please do get in touch with him if you have any queries.

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.

Learning outcomes

Learning how to differentiate multivariate functions. Understanding Taylor’s theorem and its application in approximation of univariate and multivariate functions. Finding and classifying stationary points of univariate and multivariate 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.

Prerequisites

None

Synopsis

*[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: 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.

Sections marked * cover the syllabus for the Continuous Maths part of Mathematics for Computer Science and Philosophy.

Syllabus

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.

Reading list

A. D. Ker. Continuous Mathematics. Lecture notes, 2022.

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 topics. 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-dimensional methods, but also includes a lot of material that is not in this course. There is an international edition that is cheaply available.

Taking our courses

This form is not to be used by students studying for a degree in the Department of Computer Science, or for Visiting Students who are registered for Computer Science courses

Other matriculated University of Oxford students who are interested in taking this, or other, courses in the Department of Computer Science, must complete this online form by 17.00 on Friday of 0th week of term in which the course is taught. Late requests, and requests sent by email, will not be considered. All requests must be approved by the relevant Computer Science departmental committee and can only be submitted using this form.