Synopsis for Constructive Mathematics

Overview

- this course is an introduction to mathematical algorithms; that is procedures which one can carry out to achive a desired result. Such procedures arise throughout mathematics both Pure and Applied.

Learning Outcomes

- Students should appreciate the concept of an algorithm and be able to construct simple algorithms for the solution of certain elementary problems. Verification that certain procedures should work under appropriate conditions will give students good examples of the application of real analysis and implementation will require them to be able to make and run simple procedures in Matlab.

Synopsis

The Division Algorithm on Integers, Euclid's Algorithm including proof of termination with highest common factor. The solution of simple linear Diophantine equations. Examples.

Division and Euclid's algorithm for real polynomials. Examples.

Root finding for real polynomials. Fixed point iterations, examples. Convergence. Existence of fixed points and convergence of fixed point iterations by the contraction mapping theorem (using the mean value theorem).

Newton iteration. Quadratic convergence. Horner's Rule.

Reading

- You'll find much more than the small amount of constructive algebra covered in this course in most elementary algebra or number theory texts, for example: I.N. Herstein, Abstract Algebra, Wiley 1999

For the majority of the course, see:
Endre Suli and David Mayers, An Introduction to Numerical Analysis, CUP 2003 - Chapter 1