Continuous Mathematics: 2022-2023
Lecturer | |
Degrees | |
Term | Hilary Term 2023 (16 lectures) |
Overview
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, 2023.
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.